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
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 2, 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 COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 /* This file contains optimizer of the control flow. The main entry point is
24 cleanup_cfg. Following optimizations are performed:
26 - Unreachable blocks removal
27 - Edge forwarding (edge to the forwarder block is forwarded to its
28 successor. Simplification of the branch instruction is performed by
29 underlying infrastructure so branch can be converted to simplejump or
31 - Cross jumping (tail merging)
32 - Conditional jump-around-simplejump simplification
33 - Basic block merging. */
37 #include "coretypes.h"
40 #include "hard-reg-set.h"
44 #include "insn-config.h"
52 #include "cfglayout.h"
54 #include "tree-pass.h"
58 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
60 /* Set to true when we are running first pass of try_optimize_cfg loop. */
61 static bool first_pass
;
62 static bool try_crossjump_to_edge (int, edge
, edge
);
63 static bool try_crossjump_bb (int, basic_block
);
64 static bool outgoing_edges_match (int, basic_block
, basic_block
);
65 static int flow_find_cross_jump (int, basic_block
, basic_block
, rtx
*, rtx
*);
66 static bool old_insns_match_p (int, rtx
, rtx
);
68 static void merge_blocks_move_predecessor_nojumps (basic_block
, basic_block
);
69 static void merge_blocks_move_successor_nojumps (basic_block
, basic_block
);
70 static bool try_optimize_cfg (int);
71 static bool try_simplify_condjump (basic_block
);
72 static bool try_forward_edges (int, basic_block
);
73 static edge
thread_jump (int, edge
, basic_block
);
74 static bool mark_effect (rtx
, bitmap
);
75 static void notice_new_block (basic_block
);
76 static void update_forwarder_flag (basic_block
);
77 static int mentions_nonequal_regs (rtx
*, void *);
78 static void merge_memattrs (rtx
, rtx
);
80 /* Set flags for newly created block. */
83 notice_new_block (basic_block bb
)
88 if (forwarder_block_p (bb
))
89 bb
->flags
|= BB_FORWARDER_BLOCK
;
92 /* Recompute forwarder flag after block has been modified. */
95 update_forwarder_flag (basic_block bb
)
97 if (forwarder_block_p (bb
))
98 bb
->flags
|= BB_FORWARDER_BLOCK
;
100 bb
->flags
&= ~BB_FORWARDER_BLOCK
;
103 /* Simplify a conditional jump around an unconditional jump.
104 Return true if something changed. */
107 try_simplify_condjump (basic_block cbranch_block
)
109 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
110 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
113 /* Verify that there are exactly two successors. */
114 if (EDGE_COUNT (cbranch_block
->succs
) != 2)
117 /* Verify that we've got a normal conditional branch at the end
119 cbranch_insn
= BB_END (cbranch_block
);
120 if (!any_condjump_p (cbranch_insn
))
123 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
124 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
126 /* The next block must not have multiple predecessors, must not
127 be the last block in the function, and must contain just the
128 unconditional jump. */
129 jump_block
= cbranch_fallthru_edge
->dest
;
130 if (!single_pred_p (jump_block
)
131 || jump_block
->next_bb
== EXIT_BLOCK_PTR
132 || !FORWARDER_BLOCK_P (jump_block
))
134 jump_dest_block
= single_succ (jump_block
);
136 /* If we are partitioning hot/cold basic blocks, we don't want to
137 mess up unconditional or indirect jumps that cross between hot
140 Basic block partitioning may result in some jumps that appear to
141 be optimizable (or blocks that appear to be mergeable), but which really
142 must be left untouched (they are required to make it safely across
143 partition boundaries). See the comments at the top of
144 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
146 if (BB_PARTITION (jump_block
) != BB_PARTITION (jump_dest_block
)
147 || (cbranch_jump_edge
->flags
& EDGE_CROSSING
))
150 /* The conditional branch must target the block after the
151 unconditional branch. */
152 cbranch_dest_block
= cbranch_jump_edge
->dest
;
154 if (cbranch_dest_block
== EXIT_BLOCK_PTR
155 || !can_fallthru (jump_block
, cbranch_dest_block
))
158 /* Invert the conditional branch. */
159 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
163 fprintf (dump_file
, "Simplifying condjump %i around jump %i\n",
164 INSN_UID (cbranch_insn
), INSN_UID (BB_END (jump_block
)));
166 /* Success. Update the CFG to match. Note that after this point
167 the edge variable names appear backwards; the redirection is done
168 this way to preserve edge profile data. */
169 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
171 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
173 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
174 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
175 update_br_prob_note (cbranch_block
);
177 /* Delete the block with the unconditional jump, and clean up the mess. */
178 delete_basic_block (jump_block
);
179 tidy_fallthru_edge (cbranch_jump_edge
);
180 update_forwarder_flag (cbranch_block
);
185 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
186 on register. Used by jump threading. */
189 mark_effect (rtx exp
, regset nonequal
)
193 switch (GET_CODE (exp
))
195 /* In case we do clobber the register, mark it as equal, as we know the
196 value is dead so it don't have to match. */
198 if (REG_P (XEXP (exp
, 0)))
200 dest
= XEXP (exp
, 0);
201 regno
= REGNO (dest
);
202 CLEAR_REGNO_REG_SET (nonequal
, regno
);
203 if (regno
< FIRST_PSEUDO_REGISTER
)
205 int n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
207 CLEAR_REGNO_REG_SET (nonequal
, regno
+ n
);
213 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
215 dest
= SET_DEST (exp
);
220 regno
= REGNO (dest
);
221 SET_REGNO_REG_SET (nonequal
, regno
);
222 if (regno
< FIRST_PSEUDO_REGISTER
)
224 int n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
226 SET_REGNO_REG_SET (nonequal
, regno
+ n
);
235 /* Return nonzero if X is a register set in regset DATA.
236 Called via for_each_rtx. */
238 mentions_nonequal_regs (rtx
*x
, void *data
)
240 regset nonequal
= (regset
) data
;
246 if (REGNO_REG_SET_P (nonequal
, regno
))
248 if (regno
< FIRST_PSEUDO_REGISTER
)
250 int n
= hard_regno_nregs
[regno
][GET_MODE (*x
)];
252 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
258 /* Attempt to prove that the basic block B will have no side effects and
259 always continues in the same edge if reached via E. Return the edge
260 if exist, NULL otherwise. */
263 thread_jump (int mode
, edge e
, basic_block b
)
265 rtx set1
, set2
, cond1
, cond2
, insn
;
266 enum rtx_code code1
, code2
, reversed_code2
;
267 bool reverse1
= false;
271 reg_set_iterator rsi
;
273 if (b
->flags
& BB_NONTHREADABLE_BLOCK
)
276 /* At the moment, we do handle only conditional jumps, but later we may
277 want to extend this code to tablejumps and others. */
278 if (EDGE_COUNT (e
->src
->succs
) != 2)
280 if (EDGE_COUNT (b
->succs
) != 2)
282 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
286 /* Second branch must end with onlyjump, as we will eliminate the jump. */
287 if (!any_condjump_p (BB_END (e
->src
)))
290 if (!any_condjump_p (BB_END (b
)) || !onlyjump_p (BB_END (b
)))
292 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
296 set1
= pc_set (BB_END (e
->src
));
297 set2
= pc_set (BB_END (b
));
298 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
299 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
302 cond1
= XEXP (SET_SRC (set1
), 0);
303 cond2
= XEXP (SET_SRC (set2
), 0);
305 code1
= reversed_comparison_code (cond1
, BB_END (e
->src
));
307 code1
= GET_CODE (cond1
);
309 code2
= GET_CODE (cond2
);
310 reversed_code2
= reversed_comparison_code (cond2
, BB_END (b
));
312 if (!comparison_dominates_p (code1
, code2
)
313 && !comparison_dominates_p (code1
, reversed_code2
))
316 /* Ensure that the comparison operators are equivalent.
317 ??? This is far too pessimistic. We should allow swapped operands,
318 different CCmodes, or for example comparisons for interval, that
319 dominate even when operands are not equivalent. */
320 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
321 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
324 /* Short circuit cases where block B contains some side effects, as we can't
326 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
));
327 insn
= NEXT_INSN (insn
))
328 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
330 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
336 /* First process all values computed in the source basic block. */
337 for (insn
= NEXT_INSN (BB_HEAD (e
->src
));
338 insn
!= NEXT_INSN (BB_END (e
->src
));
339 insn
= NEXT_INSN (insn
))
341 cselib_process_insn (insn
);
343 nonequal
= BITMAP_ALLOC (NULL
);
344 CLEAR_REG_SET (nonequal
);
346 /* Now assume that we've continued by the edge E to B and continue
347 processing as if it were same basic block.
348 Our goal is to prove that whole block is an NOOP. */
350 for (insn
= NEXT_INSN (BB_HEAD (b
));
351 insn
!= NEXT_INSN (BB_END (b
)) && !failed
;
352 insn
= NEXT_INSN (insn
))
356 rtx pat
= PATTERN (insn
);
358 if (GET_CODE (pat
) == PARALLEL
)
360 for (i
= 0; i
< (unsigned)XVECLEN (pat
, 0); i
++)
361 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
364 failed
|= mark_effect (pat
, nonequal
);
367 cselib_process_insn (insn
);
370 /* Later we should clear nonequal of dead registers. So far we don't
371 have life information in cfg_cleanup. */
374 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
378 /* cond2 must not mention any register that is not equal to the
380 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
383 /* In case liveness information is available, we need to prove equivalence
384 only of the live values. */
385 if (mode
& CLEANUP_UPDATE_LIFE
)
386 AND_REG_SET (nonequal
, b
->il
.rtl
->global_live_at_end
);
388 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, rsi
)
391 BITMAP_FREE (nonequal
);
393 if ((comparison_dominates_p (code1
, code2
) != 0)
394 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
395 return BRANCH_EDGE (b
);
397 return FALLTHRU_EDGE (b
);
400 BITMAP_FREE (nonequal
);
405 /* Attempt to forward edges leaving basic block B.
406 Return true if successful. */
409 try_forward_edges (int mode
, basic_block b
)
411 bool changed
= false;
413 edge e
, *threaded_edges
= NULL
;
415 /* If we are partitioning hot/cold basic blocks, we don't want to
416 mess up unconditional or indirect jumps that cross between hot
419 Basic block partitioning may result in some jumps that appear to
420 be optimizable (or blocks that appear to be mergeable), but which really m
421 ust be left untouched (they are required to make it safely across
422 partition boundaries). See the comments at the top of
423 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
425 if (find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
428 for (ei
= ei_start (b
->succs
); (e
= ei_safe_edge (ei
)); )
430 basic_block target
, first
;
432 bool threaded
= false;
433 int nthreaded_edges
= 0;
434 bool may_thread
= first_pass
| (b
->flags
& BB_DIRTY
);
436 /* Skip complex edges because we don't know how to update them.
438 Still handle fallthru edges, as we can succeed to forward fallthru
439 edge to the same place as the branch edge of conditional branch
440 and turn conditional branch to an unconditional branch. */
441 if (e
->flags
& EDGE_COMPLEX
)
447 target
= first
= e
->dest
;
448 counter
= NUM_FIXED_BLOCKS
;
450 /* If we are partitioning hot/cold basic_blocks, we don't want to mess
451 up jumps that cross between hot/cold sections.
453 Basic block partitioning may result in some jumps that appear
454 to be optimizable (or blocks that appear to be mergeable), but which
455 really must be left untouched (they are required to make it safely
456 across partition boundaries). See the comments at the top of
457 bb-reorder.c:partition_hot_cold_basic_blocks for complete
460 if (first
!= EXIT_BLOCK_PTR
461 && find_reg_note (BB_END (first
), REG_CROSSING_JUMP
, NULL_RTX
))
464 while (counter
< n_basic_blocks
)
466 basic_block new_target
= NULL
;
467 bool new_target_threaded
= false;
468 may_thread
|= target
->flags
& BB_DIRTY
;
470 if (FORWARDER_BLOCK_P (target
)
471 && !(single_succ_edge (target
)->flags
& EDGE_CROSSING
)
472 && single_succ (target
) != EXIT_BLOCK_PTR
)
474 /* Bypass trivial infinite loops. */
475 new_target
= single_succ (target
);
476 if (target
== new_target
)
477 counter
= n_basic_blocks
;
480 /* Allow to thread only over one edge at time to simplify updating
482 else if ((mode
& CLEANUP_THREADING
) && may_thread
)
484 edge t
= thread_jump (mode
, e
, target
);
488 threaded_edges
= XNEWVEC (edge
, n_basic_blocks
);
493 /* Detect an infinite loop across blocks not
494 including the start block. */
495 for (i
= 0; i
< nthreaded_edges
; ++i
)
496 if (threaded_edges
[i
] == t
)
498 if (i
< nthreaded_edges
)
500 counter
= n_basic_blocks
;
505 /* Detect an infinite loop across the start block. */
509 gcc_assert (nthreaded_edges
< n_basic_blocks
- NUM_FIXED_BLOCKS
);
510 threaded_edges
[nthreaded_edges
++] = t
;
512 new_target
= t
->dest
;
513 new_target_threaded
= true;
522 threaded
|= new_target_threaded
;
525 if (counter
>= n_basic_blocks
)
528 fprintf (dump_file
, "Infinite loop in BB %i.\n",
531 else if (target
== first
)
532 ; /* We didn't do anything. */
535 /* Save the values now, as the edge may get removed. */
536 gcov_type edge_count
= e
->count
;
537 int edge_probability
= e
->probability
;
541 /* Don't force if target is exit block. */
542 if (threaded
&& target
!= EXIT_BLOCK_PTR
)
544 notice_new_block (redirect_edge_and_branch_force (e
, target
));
546 fprintf (dump_file
, "Conditionals threaded.\n");
548 else if (!redirect_edge_and_branch (e
, target
))
552 "Forwarding edge %i->%i to %i failed.\n",
553 b
->index
, e
->dest
->index
, target
->index
);
558 /* We successfully forwarded the edge. Now update profile
559 data: for each edge we traversed in the chain, remove
560 the original edge's execution count. */
561 edge_frequency
= ((edge_probability
* b
->frequency
562 + REG_BR_PROB_BASE
/ 2)
565 if (!FORWARDER_BLOCK_P (b
) && forwarder_block_p (b
))
566 b
->flags
|= BB_FORWARDER_BLOCK
;
572 if (!single_succ_p (first
))
574 gcc_assert (n
< nthreaded_edges
);
575 t
= threaded_edges
[n
++];
576 gcc_assert (t
->src
== first
);
577 update_bb_profile_for_threading (first
, edge_frequency
,
579 update_br_prob_note (first
);
583 first
->count
-= edge_count
;
584 if (first
->count
< 0)
586 first
->frequency
-= edge_frequency
;
587 if (first
->frequency
< 0)
588 first
->frequency
= 0;
589 /* It is possible that as the result of
590 threading we've removed edge as it is
591 threaded to the fallthru edge. Avoid
592 getting out of sync. */
593 if (n
< nthreaded_edges
594 && first
== threaded_edges
[n
]->src
)
596 t
= single_succ_edge (first
);
599 t
->count
-= edge_count
;
604 while (first
!= target
);
613 free (threaded_edges
);
618 /* Blocks A and B are to be merged into a single block. A has no incoming
619 fallthru edge, so it can be moved before B without adding or modifying
620 any jumps (aside from the jump from A to B). */
623 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 /* Move block and loop notes out of the chain so that we do not
648 ??? A better solution would be to squeeze out all the non-nested notes
649 and adjust the block trees appropriately. Even better would be to have
650 a tighter connection between block trees and rtl so that this is not
652 only_notes
= squeeze_notes (&BB_HEAD (a
), &BB_END (a
));
653 gcc_assert (!only_notes
);
655 /* Scramble the insn chain. */
656 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
657 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
658 a
->flags
|= BB_DIRTY
;
661 fprintf (dump_file
, "Moved block %d before %d and merged.\n",
664 /* Swap the records for the two blocks around. */
667 link_block (a
, b
->prev_bb
);
669 /* Now blocks A and B are contiguous. Merge them. */
673 /* Blocks A and B are to be merged into a single block. B has no outgoing
674 fallthru edge, so it can be moved after A without adding or modifying
675 any jumps (aside from the jump from A to B). */
678 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
680 rtx barrier
, real_b_end
;
684 /* If we are partitioning hot/cold basic blocks, we don't want to
685 mess up unconditional or indirect jumps that cross between hot
688 Basic block partitioning may result in some jumps that appear to
689 be optimizable (or blocks that appear to be mergeable), but which really
690 must be left untouched (they are required to make it safely across
691 partition boundaries). See the comments at the top of
692 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
694 if (BB_PARTITION (a
) != BB_PARTITION (b
))
697 real_b_end
= BB_END (b
);
699 /* If there is a jump table following block B temporarily add the jump table
700 to block B so that it will also be moved to the correct location. */
701 if (tablejump_p (BB_END (b
), &label
, &table
)
702 && prev_active_insn (label
) == BB_END (b
))
707 /* There had better have been a barrier there. Delete it. */
708 barrier
= NEXT_INSN (BB_END (b
));
709 if (barrier
&& BARRIER_P (barrier
))
710 delete_insn (barrier
);
712 /* Move block and loop notes out of the chain so that we do not
715 ??? A better solution would be to squeeze out all the non-nested notes
716 and adjust the block trees appropriately. Even better would be to have
717 a tighter connection between block trees and rtl so that this is not
719 only_notes
= squeeze_notes (&BB_HEAD (b
), &BB_END (b
));
720 gcc_assert (!only_notes
);
723 /* Scramble the insn chain. */
724 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
726 /* Restore the real end of b. */
727 BB_END (b
) = real_b_end
;
730 fprintf (dump_file
, "Moved block %d after %d and merged.\n",
733 /* Now blocks A and B are contiguous. Merge them. */
737 /* Attempt to merge basic blocks that are potentially non-adjacent.
738 Return NULL iff the attempt failed, otherwise return basic block
739 where cleanup_cfg should continue. Because the merging commonly
740 moves basic block away or introduces another optimization
741 possibility, return basic block just before B so cleanup_cfg don't
744 It may be good idea to return basic block before C in the case
745 C has been moved after B and originally appeared earlier in the
746 insn sequence, but we have no information available about the
747 relative ordering of these two. Hopefully it is not too common. */
750 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
754 /* If we are partitioning hot/cold basic blocks, we don't want to
755 mess up unconditional or indirect jumps that cross between hot
758 Basic block partitioning may result in some jumps that appear to
759 be optimizable (or blocks that appear to be mergeable), but which really
760 must be left untouched (they are required to make it safely across
761 partition boundaries). See the comments at the top of
762 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
764 if (BB_PARTITION (b
) != BB_PARTITION (c
))
767 /* If B has a fallthru edge to C, no need to move anything. */
768 if (e
->flags
& EDGE_FALLTHRU
)
770 int b_index
= b
->index
, c_index
= c
->index
;
772 update_forwarder_flag (b
);
775 fprintf (dump_file
, "Merged %d and %d without moving.\n",
778 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
781 /* Otherwise we will need to move code around. Do that only if expensive
782 transformations are allowed. */
783 else if (mode
& CLEANUP_EXPENSIVE
)
785 edge tmp_edge
, b_fallthru_edge
;
786 bool c_has_outgoing_fallthru
;
787 bool b_has_incoming_fallthru
;
790 /* Avoid overactive code motion, as the forwarder blocks should be
791 eliminated by edge redirection instead. One exception might have
792 been if B is a forwarder block and C has no fallthru edge, but
793 that should be cleaned up by bb-reorder instead. */
794 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
797 /* We must make sure to not munge nesting of lexical blocks,
798 and loop notes. This is done by squeezing out all the notes
799 and leaving them there to lie. Not ideal, but functional. */
801 FOR_EACH_EDGE (tmp_edge
, ei
, c
->succs
)
802 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
805 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
807 FOR_EACH_EDGE (tmp_edge
, ei
, b
->preds
)
808 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
811 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
812 b_fallthru_edge
= tmp_edge
;
815 next
= next
->prev_bb
;
817 /* Otherwise, we're going to try to move C after B. If C does
818 not have an outgoing fallthru, then it can be moved
819 immediately after B without introducing or modifying jumps. */
820 if (! c_has_outgoing_fallthru
)
822 merge_blocks_move_successor_nojumps (b
, c
);
823 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
826 /* If B does not have an incoming fallthru, then it can be moved
827 immediately before C without introducing or modifying jumps.
828 C cannot be the first block, so we do not have to worry about
829 accessing a non-existent block. */
831 if (b_has_incoming_fallthru
)
835 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
837 bb
= force_nonfallthru (b_fallthru_edge
);
839 notice_new_block (bb
);
842 merge_blocks_move_predecessor_nojumps (b
, c
);
843 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
850 /* Removes the memory attributes of MEM expression
851 if they are not equal. */
854 merge_memattrs (rtx x
, rtx y
)
863 if (x
== 0 || y
== 0)
868 if (code
!= GET_CODE (y
))
871 if (GET_MODE (x
) != GET_MODE (y
))
874 if (code
== MEM
&& MEM_ATTRS (x
) != MEM_ATTRS (y
))
878 else if (! MEM_ATTRS (y
))
884 if (MEM_ALIAS_SET (x
) != MEM_ALIAS_SET (y
))
886 set_mem_alias_set (x
, 0);
887 set_mem_alias_set (y
, 0);
890 if (! mem_expr_equal_p (MEM_EXPR (x
), MEM_EXPR (y
)))
894 set_mem_offset (x
, 0);
895 set_mem_offset (y
, 0);
897 else if (MEM_OFFSET (x
) != MEM_OFFSET (y
))
899 set_mem_offset (x
, 0);
900 set_mem_offset (y
, 0);
905 else if (!MEM_SIZE (y
))
908 mem_size
= GEN_INT (MAX (INTVAL (MEM_SIZE (x
)),
909 INTVAL (MEM_SIZE (y
))));
910 set_mem_size (x
, mem_size
);
911 set_mem_size (y
, mem_size
);
913 set_mem_align (x
, MIN (MEM_ALIGN (x
), MEM_ALIGN (y
)));
914 set_mem_align (y
, MEM_ALIGN (x
));
918 fmt
= GET_RTX_FORMAT (code
);
919 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
924 /* Two vectors must have the same length. */
925 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
928 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
929 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
934 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
941 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
944 old_insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
948 /* Verify that I1 and I2 are equivalent. */
949 if (GET_CODE (i1
) != GET_CODE (i2
))
955 if (GET_CODE (p1
) != GET_CODE (p2
))
958 /* If this is a CALL_INSN, compare register usage information.
959 If we don't check this on stack register machines, the two
960 CALL_INSNs might be merged leaving reg-stack.c with mismatching
961 numbers of stack registers in the same basic block.
962 If we don't check this on machines with delay slots, a delay slot may
963 be filled that clobbers a parameter expected by the subroutine.
965 ??? We take the simple route for now and assume that if they're
966 equal, they were constructed identically. */
969 && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
970 CALL_INSN_FUNCTION_USAGE (i2
))
971 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
)))
975 /* If cross_jump_death_matters is not 0, the insn's mode
976 indicates whether or not the insn contains any stack-like
979 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
981 /* If register stack conversion has already been done, then
982 death notes must also be compared before it is certain that
983 the two instruction streams match. */
986 HARD_REG_SET i1_regset
, i2_regset
;
988 CLEAR_HARD_REG_SET (i1_regset
);
989 CLEAR_HARD_REG_SET (i2_regset
);
991 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
992 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
993 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
995 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
996 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
997 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
999 GO_IF_HARD_REG_EQUAL (i1_regset
, i2_regset
, done
);
1008 if (reload_completed
1009 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
1012 /* Do not do EQUIV substitution after reload. First, we're undoing the
1013 work of reload_cse. Second, we may be undoing the work of the post-
1014 reload splitting pass. */
1015 /* ??? Possibly add a new phase switch variable that can be used by
1016 targets to disallow the troublesome insns after splitting. */
1017 if (!reload_completed
)
1019 /* The following code helps take care of G++ cleanups. */
1020 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1021 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1023 if (equiv1
&& equiv2
1024 /* If the equivalences are not to a constant, they may
1025 reference pseudos that no longer exist, so we can't
1027 && (! reload_completed
1028 || (CONSTANT_P (XEXP (equiv1
, 0))
1029 && rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))))
1031 rtx s1
= single_set (i1
);
1032 rtx s2
= single_set (i2
);
1033 if (s1
!= 0 && s2
!= 0
1034 && rtx_renumbered_equal_p (SET_DEST (s1
), SET_DEST (s2
)))
1036 validate_change (i1
, &SET_SRC (s1
), XEXP (equiv1
, 0), 1);
1037 validate_change (i2
, &SET_SRC (s2
), XEXP (equiv2
, 0), 1);
1038 if (! rtx_renumbered_equal_p (p1
, p2
))
1040 else if (apply_change_group ())
1049 /* Look through the insns at the end of BB1 and BB2 and find the longest
1050 sequence that are equivalent. Store the first insns for that sequence
1051 in *F1 and *F2 and return the sequence length.
1053 To simplify callers of this function, if the blocks match exactly,
1054 store the head of the blocks in *F1 and *F2. */
1057 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED
, basic_block bb1
,
1058 basic_block bb2
, rtx
*f1
, rtx
*f2
)
1060 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
1063 /* Skip simple jumps at the end of the blocks. Complex jumps still
1064 need to be compared for equivalence, which we'll do below. */
1067 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
1069 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1072 i1
= PREV_INSN (i1
);
1077 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1080 /* Count everything except for unconditional jump as insn. */
1081 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1083 i2
= PREV_INSN (i2
);
1089 while (!INSN_P (i1
) && i1
!= BB_HEAD (bb1
))
1090 i1
= PREV_INSN (i1
);
1092 while (!INSN_P (i2
) && i2
!= BB_HEAD (bb2
))
1093 i2
= PREV_INSN (i2
);
1095 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1098 if (!old_insns_match_p (mode
, i1
, i2
))
1101 merge_memattrs (i1
, i2
);
1103 /* Don't begin a cross-jump with a NOTE insn. */
1106 /* If the merged insns have different REG_EQUAL notes, then
1108 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1109 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1111 if (equiv1
&& !equiv2
)
1112 remove_note (i1
, equiv1
);
1113 else if (!equiv1
&& equiv2
)
1114 remove_note (i2
, equiv2
);
1115 else if (equiv1
&& equiv2
1116 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1118 remove_note (i1
, equiv1
);
1119 remove_note (i2
, equiv2
);
1122 afterlast1
= last1
, afterlast2
= last2
;
1123 last1
= i1
, last2
= i2
;
1127 i1
= PREV_INSN (i1
);
1128 i2
= PREV_INSN (i2
);
1132 /* Don't allow the insn after a compare to be shared by
1133 cross-jumping unless the compare is also shared. */
1134 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1135 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
1138 /* Include preceding notes and labels in the cross-jump. One,
1139 this may bring us to the head of the blocks as requested above.
1140 Two, it keeps line number notes as matched as may be. */
1143 while (last1
!= BB_HEAD (bb1
) && !INSN_P (PREV_INSN (last1
)))
1144 last1
= PREV_INSN (last1
);
1146 if (last1
!= BB_HEAD (bb1
) && LABEL_P (PREV_INSN (last1
)))
1147 last1
= PREV_INSN (last1
);
1149 while (last2
!= BB_HEAD (bb2
) && !INSN_P (PREV_INSN (last2
)))
1150 last2
= PREV_INSN (last2
);
1152 if (last2
!= BB_HEAD (bb2
) && LABEL_P (PREV_INSN (last2
)))
1153 last2
= PREV_INSN (last2
);
1162 /* Return true iff the condbranches at the end of BB1 and BB2 match. */
1164 condjump_equiv_p (struct equiv_info
*info
, bool call_init
)
1166 basic_block bb1
= info
->x_block
;
1167 basic_block bb2
= info
->y_block
;
1168 edge b1
= BRANCH_EDGE (bb1
);
1169 edge b2
= BRANCH_EDGE (bb2
);
1170 edge f1
= FALLTHRU_EDGE (bb1
);
1171 edge f2
= FALLTHRU_EDGE (bb2
);
1172 bool reverse
, match
;
1173 rtx set1
, set2
, cond1
, cond2
;
1175 enum rtx_code code1
, code2
;
1177 /* Get around possible forwarders on fallthru edges. Other cases
1178 should be optimized out already. */
1179 if (FORWARDER_BLOCK_P (f1
->dest
))
1180 f1
= single_succ_edge (f1
->dest
);
1182 if (FORWARDER_BLOCK_P (f2
->dest
))
1183 f2
= single_succ_edge (f2
->dest
);
1185 /* To simplify use of this function, return false if there are
1186 unneeded forwarder blocks. These will get eliminated later
1187 during cleanup_cfg. */
1188 if (FORWARDER_BLOCK_P (f1
->dest
)
1189 || FORWARDER_BLOCK_P (f2
->dest
)
1190 || FORWARDER_BLOCK_P (b1
->dest
)
1191 || FORWARDER_BLOCK_P (b2
->dest
))
1194 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1196 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1201 set1
= pc_set (BB_END (bb1
));
1202 set2
= pc_set (BB_END (bb2
));
1203 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1204 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1207 src1
= SET_SRC (set1
);
1208 src2
= SET_SRC (set2
);
1209 cond1
= XEXP (src1
, 0);
1210 cond2
= XEXP (src2
, 0);
1211 code1
= GET_CODE (cond1
);
1213 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1215 code2
= GET_CODE (cond2
);
1217 if (code2
== UNKNOWN
)
1220 if (call_init
&& !struct_equiv_init (STRUCT_EQUIV_START
| info
->mode
, info
))
1222 /* Make the sources of the pc sets unreadable so that when we call
1223 insns_match_p it won't process them.
1224 The death_notes_match_p from insns_match_p won't see the local registers
1225 used for the pc set, but that could only cause missed optimizations when
1226 there are actually condjumps that use stack registers. */
1227 SET_SRC (set1
) = pc_rtx
;
1228 SET_SRC (set2
) = pc_rtx
;
1229 /* Verify codes and operands match. */
1232 match
= (insns_match_p (BB_END (bb1
), BB_END (bb2
), info
)
1233 && rtx_equiv_p (&XEXP (cond1
, 0), XEXP (cond2
, 0), 1, info
)
1234 && rtx_equiv_p (&XEXP (cond1
, 1), XEXP (cond2
, 1), 1, info
));
1237 else if (code1
== swap_condition (code2
))
1239 match
= (insns_match_p (BB_END (bb1
), BB_END (bb2
), info
)
1240 && rtx_equiv_p (&XEXP (cond1
, 1), XEXP (cond2
, 0), 1, info
)
1241 && rtx_equiv_p (&XEXP (cond1
, 0), XEXP (cond2
, 1), 1, info
));
1246 SET_SRC (set1
) = src1
;
1247 SET_SRC (set2
) = src2
;
1248 match
&= verify_changes (0);
1250 /* If we return true, we will join the blocks. Which means that
1251 we will only have one branch prediction bit to work with. Thus
1252 we require the existing branches to have probabilities that are
1256 && maybe_hot_bb_p (bb1
)
1257 && maybe_hot_bb_p (bb2
))
1261 if (b1
->dest
== b2
->dest
)
1262 prob2
= b2
->probability
;
1264 /* Do not use f2 probability as f2 may be forwarded. */
1265 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1267 /* Fail if the difference in probabilities is greater than 50%.
1268 This rules out two well-predicted branches with opposite
1270 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1274 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1275 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1281 if (dump_file
&& match
)
1282 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1283 bb1
->index
, bb2
->index
);
1290 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1291 the branch instruction. This means that if we commonize the control
1292 flow before end of the basic block, the semantic remains unchanged.
1294 We may assume that there exists one edge with a common destination. */
1297 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1299 int nehedges1
= 0, nehedges2
= 0;
1300 edge fallthru1
= 0, fallthru2
= 0;
1304 /* If BB1 has only one successor, we may be looking at either an
1305 unconditional jump, or a fake edge to exit. */
1306 if (single_succ_p (bb1
)
1307 && (single_succ_edge (bb1
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1308 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1309 return (single_succ_p (bb2
)
1310 && (single_succ_edge (bb2
)->flags
1311 & (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1312 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1314 /* Match conditional jumps - this may get tricky when fallthru and branch
1315 edges are crossed. */
1316 if (EDGE_COUNT (bb1
->succs
) == 2
1317 && any_condjump_p (BB_END (bb1
))
1318 && onlyjump_p (BB_END (bb1
)))
1320 edge b1
, f1
, b2
, f2
;
1321 bool reverse
, match
;
1322 rtx set1
, set2
, cond1
, cond2
;
1323 enum rtx_code code1
, code2
;
1325 if (EDGE_COUNT (bb2
->succs
) != 2
1326 || !any_condjump_p (BB_END (bb2
))
1327 || !onlyjump_p (BB_END (bb2
)))
1330 b1
= BRANCH_EDGE (bb1
);
1331 b2
= BRANCH_EDGE (bb2
);
1332 f1
= FALLTHRU_EDGE (bb1
);
1333 f2
= FALLTHRU_EDGE (bb2
);
1335 /* Get around possible forwarders on fallthru edges. Other cases
1336 should be optimized out already. */
1337 if (FORWARDER_BLOCK_P (f1
->dest
))
1338 f1
= single_succ_edge (f1
->dest
);
1340 if (FORWARDER_BLOCK_P (f2
->dest
))
1341 f2
= single_succ_edge (f2
->dest
);
1343 /* To simplify use of this function, return false if there are
1344 unneeded forwarder blocks. These will get eliminated later
1345 during cleanup_cfg. */
1346 if (FORWARDER_BLOCK_P (f1
->dest
)
1347 || FORWARDER_BLOCK_P (f2
->dest
)
1348 || FORWARDER_BLOCK_P (b1
->dest
)
1349 || FORWARDER_BLOCK_P (b2
->dest
))
1352 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1354 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1359 set1
= pc_set (BB_END (bb1
));
1360 set2
= pc_set (BB_END (bb2
));
1361 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1362 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1365 cond1
= XEXP (SET_SRC (set1
), 0);
1366 cond2
= XEXP (SET_SRC (set2
), 0);
1367 code1
= GET_CODE (cond1
);
1369 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1371 code2
= GET_CODE (cond2
);
1373 if (code2
== UNKNOWN
)
1376 /* Verify codes and operands match. */
1377 match
= ((code1
== code2
1378 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1379 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1380 || (code1
== swap_condition (code2
)
1381 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1383 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1386 /* If we return true, we will join the blocks. Which means that
1387 we will only have one branch prediction bit to work with. Thus
1388 we require the existing branches to have probabilities that are
1392 && maybe_hot_bb_p (bb1
)
1393 && maybe_hot_bb_p (bb2
))
1397 if (b1
->dest
== b2
->dest
)
1398 prob2
= b2
->probability
;
1400 /* Do not use f2 probability as f2 may be forwarded. */
1401 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1403 /* Fail if the difference in probabilities is greater than 50%.
1404 This rules out two well-predicted branches with opposite
1406 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1410 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1411 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1417 if (dump_file
&& match
)
1418 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1419 bb1
->index
, bb2
->index
);
1424 /* Generic case - we are seeing a computed jump, table jump or trapping
1427 /* Check whether there are tablejumps in the end of BB1 and BB2.
1428 Return true if they are identical. */
1433 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1434 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1435 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1437 /* The labels should never be the same rtx. If they really are same
1438 the jump tables are same too. So disable crossjumping of blocks BB1
1439 and BB2 because when deleting the common insns in the end of BB1
1440 by delete_basic_block () the jump table would be deleted too. */
1441 /* If LABEL2 is referenced in BB1->END do not do anything
1442 because we would loose information when replacing
1443 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1444 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1446 /* Set IDENTICAL to true when the tables are identical. */
1447 bool identical
= false;
1450 p1
= PATTERN (table1
);
1451 p2
= PATTERN (table2
);
1452 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1456 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1457 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1458 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1459 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1464 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1465 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1471 replace_label_data rr
;
1474 /* Temporarily replace references to LABEL1 with LABEL2
1475 in BB1->END so that we could compare the instructions. */
1478 rr
.update_label_nuses
= false;
1479 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1481 match
= old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
));
1482 if (dump_file
&& match
)
1484 "Tablejumps in bb %i and %i match.\n",
1485 bb1
->index
, bb2
->index
);
1487 /* Set the original label in BB1->END because when deleting
1488 a block whose end is a tablejump, the tablejump referenced
1489 from the instruction is deleted too. */
1492 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1501 /* First ensure that the instructions match. There may be many outgoing
1502 edges so this test is generally cheaper. */
1503 if (!old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
)))
1506 /* Search the outgoing edges, ensure that the counts do match, find possible
1507 fallthru and exception handling edges since these needs more
1509 if (EDGE_COUNT (bb1
->succs
) != EDGE_COUNT (bb2
->succs
))
1512 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1514 e2
= EDGE_SUCC (bb2
, ei
.index
);
1516 if (e1
->flags
& EDGE_EH
)
1519 if (e2
->flags
& EDGE_EH
)
1522 if (e1
->flags
& EDGE_FALLTHRU
)
1524 if (e2
->flags
& EDGE_FALLTHRU
)
1528 /* If number of edges of various types does not match, fail. */
1529 if (nehedges1
!= nehedges2
1530 || (fallthru1
!= 0) != (fallthru2
!= 0))
1533 /* fallthru edges must be forwarded to the same destination. */
1536 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1537 ? single_succ (fallthru1
->dest
): fallthru1
->dest
);
1538 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1539 ? single_succ (fallthru2
->dest
): fallthru2
->dest
);
1545 /* Ensure the same EH region. */
1547 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1548 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1553 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1557 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1558 version of sequence abstraction. */
1559 FOR_EACH_EDGE (e1
, ei
, bb2
->succs
)
1563 basic_block d1
= e1
->dest
;
1565 if (FORWARDER_BLOCK_P (d1
))
1566 d1
= EDGE_SUCC (d1
, 0)->dest
;
1568 FOR_EACH_EDGE (e2
, ei
, bb1
->succs
)
1570 basic_block d2
= e2
->dest
;
1571 if (FORWARDER_BLOCK_P (d2
))
1572 d2
= EDGE_SUCC (d2
, 0)->dest
;
1584 /* Returns true if BB basic block has a preserve label. */
1587 block_has_preserve_label (basic_block bb
)
1591 && LABEL_PRESERVE_P (block_label (bb
)));
1594 /* E1 and E2 are edges with the same destination block. Search their
1595 predecessors for common code. If found, redirect control flow from
1596 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1599 try_crossjump_to_edge (int mode
, edge e1
, edge e2
)
1602 basic_block src1
= e1
->src
, src2
= e2
->src
;
1603 basic_block redirect_to
, redirect_from
, to_remove
;
1604 rtx newpos1
, newpos2
;
1608 newpos1
= newpos2
= NULL_RTX
;
1610 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1611 to try this optimization.
1613 Basic block partitioning may result in some jumps that appear to
1614 be optimizable (or blocks that appear to be mergeable), but which really
1615 must be left untouched (they are required to make it safely across
1616 partition boundaries). See the comments at the top of
1617 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1619 if (flag_reorder_blocks_and_partition
&& no_new_pseudos
)
1622 /* Search backward through forwarder blocks. We don't need to worry
1623 about multiple entry or chained forwarders, as they will be optimized
1624 away. We do this to look past the unconditional jump following a
1625 conditional jump that is required due to the current CFG shape. */
1626 if (single_pred_p (src1
)
1627 && FORWARDER_BLOCK_P (src1
))
1628 e1
= single_pred_edge (src1
), src1
= e1
->src
;
1630 if (single_pred_p (src2
)
1631 && FORWARDER_BLOCK_P (src2
))
1632 e2
= single_pred_edge (src2
), src2
= e2
->src
;
1634 /* Nothing to do if we reach ENTRY, or a common source block. */
1635 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1640 /* Seeing more than 1 forwarder blocks would confuse us later... */
1641 if (FORWARDER_BLOCK_P (e1
->dest
)
1642 && FORWARDER_BLOCK_P (single_succ (e1
->dest
)))
1645 if (FORWARDER_BLOCK_P (e2
->dest
)
1646 && FORWARDER_BLOCK_P (single_succ (e2
->dest
)))
1649 /* Likewise with dead code (possibly newly created by the other optimizations
1651 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
1654 /* Look for the common insn sequence, part the first ... */
1655 if (!outgoing_edges_match (mode
, src1
, src2
))
1658 /* ... and part the second. */
1659 nmatch
= flow_find_cross_jump (mode
, src1
, src2
, &newpos1
, &newpos2
);
1661 /* Don't proceed with the crossjump unless we found a sufficient number
1662 of matching instructions or the 'from' block was totally matched
1663 (such that its predecessors will hopefully be redirected and the
1665 if ((nmatch
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
1666 && (newpos1
!= BB_HEAD (src1
)))
1669 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
1670 if (block_has_preserve_label (e1
->dest
)
1671 && (e1
->flags
& EDGE_ABNORMAL
))
1674 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1676 If we have tablejumps in the end of SRC1 and SRC2
1677 they have been already compared for equivalence in outgoing_edges_match ()
1678 so replace the references to TABLE1 by references to TABLE2. */
1683 if (tablejump_p (BB_END (src1
), &label1
, &table1
)
1684 && tablejump_p (BB_END (src2
), &label2
, &table2
)
1685 && label1
!= label2
)
1687 replace_label_data rr
;
1690 /* Replace references to LABEL1 with LABEL2. */
1693 rr
.update_label_nuses
= true;
1694 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1696 /* Do not replace the label in SRC1->END because when deleting
1697 a block whose end is a tablejump, the tablejump referenced
1698 from the instruction is deleted too. */
1699 if (insn
!= BB_END (src1
))
1700 for_each_rtx (&insn
, replace_label
, &rr
);
1705 /* Avoid splitting if possible. We must always split when SRC2 has
1706 EH predecessor edges, or we may end up with basic blocks with both
1707 normal and EH predecessor edges. */
1708 if (newpos2
== BB_HEAD (src2
)
1709 && !(EDGE_PRED (src2
, 0)->flags
& EDGE_EH
))
1713 if (newpos2
== BB_HEAD (src2
))
1715 /* Skip possible basic block header. */
1716 if (LABEL_P (newpos2
))
1717 newpos2
= NEXT_INSN (newpos2
);
1718 if (NOTE_P (newpos2
))
1719 newpos2
= NEXT_INSN (newpos2
);
1723 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
1724 src2
->index
, nmatch
);
1725 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1730 "Cross jumping from bb %i to bb %i; %i common insns\n",
1731 src1
->index
, src2
->index
, nmatch
);
1733 redirect_to
->count
+= src1
->count
;
1734 redirect_to
->frequency
+= src1
->frequency
;
1735 /* We may have some registers visible through the block. */
1736 redirect_to
->flags
|= BB_DIRTY
;
1738 /* Recompute the frequencies and counts of outgoing edges. */
1739 FOR_EACH_EDGE (s
, ei
, redirect_to
->succs
)
1743 basic_block d
= s
->dest
;
1745 if (FORWARDER_BLOCK_P (d
))
1746 d
= single_succ (d
);
1748 FOR_EACH_EDGE (s2
, ei
, src1
->succs
)
1750 basic_block d2
= s2
->dest
;
1751 if (FORWARDER_BLOCK_P (d2
))
1752 d2
= single_succ (d2
);
1757 s
->count
+= s2
->count
;
1759 /* Take care to update possible forwarder blocks. We verified
1760 that there is no more than one in the chain, so we can't run
1761 into infinite loop. */
1762 if (FORWARDER_BLOCK_P (s
->dest
))
1764 single_succ_edge (s
->dest
)->count
+= s2
->count
;
1765 s
->dest
->count
+= s2
->count
;
1766 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1769 if (FORWARDER_BLOCK_P (s2
->dest
))
1771 single_succ_edge (s2
->dest
)->count
-= s2
->count
;
1772 if (single_succ_edge (s2
->dest
)->count
< 0)
1773 single_succ_edge (s2
->dest
)->count
= 0;
1774 s2
->dest
->count
-= s2
->count
;
1775 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1776 if (s2
->dest
->frequency
< 0)
1777 s2
->dest
->frequency
= 0;
1778 if (s2
->dest
->count
< 0)
1779 s2
->dest
->count
= 0;
1782 if (!redirect_to
->frequency
&& !src1
->frequency
)
1783 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
1786 = ((s
->probability
* redirect_to
->frequency
+
1787 s2
->probability
* src1
->frequency
)
1788 / (redirect_to
->frequency
+ src1
->frequency
));
1791 update_br_prob_note (redirect_to
);
1793 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1795 /* Skip possible basic block header. */
1796 if (LABEL_P (newpos1
))
1797 newpos1
= NEXT_INSN (newpos1
);
1799 if (NOTE_P (newpos1
))
1800 newpos1
= NEXT_INSN (newpos1
);
1802 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
1803 to_remove
= single_succ (redirect_from
);
1805 redirect_edge_and_branch_force (single_succ_edge (redirect_from
), redirect_to
);
1806 delete_basic_block (to_remove
);
1808 update_forwarder_flag (redirect_from
);
1809 if (redirect_to
!= src2
)
1810 update_forwarder_flag (src2
);
1815 /* Search the predecessors of BB for common insn sequences. When found,
1816 share code between them by redirecting control flow. Return true if
1817 any changes made. */
1820 try_crossjump_bb (int mode
, basic_block bb
)
1822 edge e
, e2
, fallthru
;
1824 unsigned max
, ix
, ix2
;
1825 basic_block ev
, ev2
;
1828 /* Nothing to do if there is not at least two incoming edges. */
1829 if (EDGE_COUNT (bb
->preds
) < 2)
1832 /* Don't crossjump if this block ends in a computed jump,
1833 unless we are optimizing for size. */
1835 && bb
!= EXIT_BLOCK_PTR
1836 && computed_jump_p (BB_END (bb
)))
1839 /* If we are partitioning hot/cold basic blocks, we don't want to
1840 mess up unconditional or indirect jumps that cross between hot
1843 Basic block partitioning may result in some jumps that appear to
1844 be optimizable (or blocks that appear to be mergeable), but which really
1845 must be left untouched (they are required to make it safely across
1846 partition boundaries). See the comments at the top of
1847 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1849 if (BB_PARTITION (EDGE_PRED (bb
, 0)->src
) !=
1850 BB_PARTITION (EDGE_PRED (bb
, 1)->src
)
1851 || (EDGE_PRED (bb
, 0)->flags
& EDGE_CROSSING
))
1854 /* It is always cheapest to redirect a block that ends in a branch to
1855 a block that falls through into BB, as that adds no branches to the
1856 program. We'll try that combination first. */
1858 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
1860 if (EDGE_COUNT (bb
->preds
) > max
)
1863 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1865 if (e
->flags
& EDGE_FALLTHRU
)
1870 for (ix
= 0, ev
= bb
; ix
< EDGE_COUNT (ev
->preds
); )
1872 e
= EDGE_PRED (ev
, ix
);
1875 /* As noted above, first try with the fallthru predecessor. */
1878 /* Don't combine the fallthru edge into anything else.
1879 If there is a match, we'll do it the other way around. */
1882 /* If nothing changed since the last attempt, there is nothing
1885 && (!(e
->src
->flags
& BB_DIRTY
)
1886 && !(fallthru
->src
->flags
& BB_DIRTY
)))
1889 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1898 /* Non-obvious work limiting check: Recognize that we're going
1899 to call try_crossjump_bb on every basic block. So if we have
1900 two blocks with lots of outgoing edges (a switch) and they
1901 share lots of common destinations, then we would do the
1902 cross-jump check once for each common destination.
1904 Now, if the blocks actually are cross-jump candidates, then
1905 all of their destinations will be shared. Which means that
1906 we only need check them for cross-jump candidacy once. We
1907 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1908 choosing to do the check from the block for which the edge
1909 in question is the first successor of A. */
1910 if (EDGE_SUCC (e
->src
, 0) != e
)
1913 for (ix2
= 0, ev2
= bb
; ix2
< EDGE_COUNT (ev2
->preds
); )
1915 e2
= EDGE_PRED (ev2
, ix2
);
1921 /* We've already checked the fallthru edge above. */
1925 /* The "first successor" check above only prevents multiple
1926 checks of crossjump(A,B). In order to prevent redundant
1927 checks of crossjump(B,A), require that A be the block
1928 with the lowest index. */
1929 if (e
->src
->index
> e2
->src
->index
)
1932 /* If nothing changed since the last attempt, there is nothing
1935 && (!(e
->src
->flags
& BB_DIRTY
)
1936 && !(e2
->src
->flags
& BB_DIRTY
)))
1939 if (try_crossjump_to_edge (mode
, e
, e2
))
1952 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1953 instructions etc. Return nonzero if changes were made. */
1956 try_optimize_cfg (int mode
)
1958 bool changed_overall
= false;
1961 basic_block bb
, b
, next
;
1963 if (mode
& CLEANUP_CROSSJUMP
)
1964 add_noreturn_fake_exit_edges ();
1966 if (mode
& (CLEANUP_UPDATE_LIFE
| CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
1970 update_forwarder_flag (bb
);
1972 if (! targetm
.cannot_modify_jumps_p ())
1975 /* Attempt to merge blocks as made possible by edge removal. If
1976 a block has only one successor, and the successor has only
1977 one predecessor, they may be combined. */
1985 "\n\ntry_optimize_cfg iteration %i\n\n",
1988 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
1992 bool changed_here
= false;
1994 /* Delete trivially dead basic blocks. */
1995 while (EDGE_COUNT (b
->preds
) == 0)
1999 fprintf (dump_file
, "Deleting block %i.\n",
2002 delete_basic_block (b
);
2003 if (!(mode
& CLEANUP_CFGLAYOUT
))
2008 /* Remove code labels no longer used. */
2009 if (single_pred_p (b
)
2010 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2011 && !(single_pred_edge (b
)->flags
& EDGE_COMPLEX
)
2012 && LABEL_P (BB_HEAD (b
))
2013 /* If the previous block ends with a branch to this
2014 block, we can't delete the label. Normally this
2015 is a condjump that is yet to be simplified, but
2016 if CASE_DROPS_THRU, this can be a tablejump with
2017 some element going to the same place as the
2018 default (fallthru). */
2019 && (single_pred (b
) == ENTRY_BLOCK_PTR
2020 || !JUMP_P (BB_END (single_pred (b
)))
2021 || ! label_is_jump_target_p (BB_HEAD (b
),
2022 BB_END (single_pred (b
)))))
2024 rtx label
= BB_HEAD (b
);
2026 delete_insn_chain (label
, label
);
2027 /* In the case label is undeletable, move it after the
2028 BASIC_BLOCK note. */
2029 if (NOTE_LINE_NUMBER (BB_HEAD (b
)) == NOTE_INSN_DELETED_LABEL
)
2031 rtx bb_note
= NEXT_INSN (BB_HEAD (b
));
2033 reorder_insns_nobb (label
, label
, bb_note
);
2034 BB_HEAD (b
) = bb_note
;
2037 fprintf (dump_file
, "Deleted label in block %i.\n",
2041 /* If we fall through an empty block, we can remove it. */
2042 if (!(mode
& CLEANUP_CFGLAYOUT
)
2043 && single_pred_p (b
)
2044 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2045 && !LABEL_P (BB_HEAD (b
))
2046 && FORWARDER_BLOCK_P (b
)
2047 /* Note that forwarder_block_p true ensures that
2048 there is a successor for this block. */
2049 && (single_succ_edge (b
)->flags
& EDGE_FALLTHRU
)
2050 && n_basic_blocks
> NUM_FIXED_BLOCKS
+ 1)
2054 "Deleting fallthru block %i.\n",
2057 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
2058 redirect_edge_succ_nodup (single_pred_edge (b
),
2060 delete_basic_block (b
);
2065 if (single_succ_p (b
)
2066 && (s
= single_succ_edge (b
))
2067 && !(s
->flags
& EDGE_COMPLEX
)
2068 && (c
= s
->dest
) != EXIT_BLOCK_PTR
2069 && single_pred_p (c
)
2072 /* When not in cfg_layout mode use code aware of reordering
2073 INSN. This code possibly creates new basic blocks so it
2074 does not fit merge_blocks interface and is kept here in
2075 hope that it will become useless once more of compiler
2076 is transformed to use cfg_layout mode. */
2078 if ((mode
& CLEANUP_CFGLAYOUT
)
2079 && can_merge_blocks_p (b
, c
))
2081 merge_blocks (b
, c
);
2082 update_forwarder_flag (b
);
2083 changed_here
= true;
2085 else if (!(mode
& CLEANUP_CFGLAYOUT
)
2086 /* If the jump insn has side effects,
2087 we can't kill the edge. */
2088 && (!JUMP_P (BB_END (b
))
2089 || (reload_completed
2090 ? simplejump_p (BB_END (b
))
2091 : (onlyjump_p (BB_END (b
))
2092 && !tablejump_p (BB_END (b
),
2094 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
2097 changed_here
= true;
2101 /* Simplify branch over branch. */
2102 if ((mode
& CLEANUP_EXPENSIVE
)
2103 && !(mode
& CLEANUP_CFGLAYOUT
)
2104 && try_simplify_condjump (b
))
2105 changed_here
= true;
2107 /* If B has a single outgoing edge, but uses a
2108 non-trivial jump instruction without side-effects, we
2109 can either delete the jump entirely, or replace it
2110 with a simple unconditional jump. */
2111 if (single_succ_p (b
)
2112 && single_succ (b
) != EXIT_BLOCK_PTR
2113 && onlyjump_p (BB_END (b
))
2114 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
)
2115 && try_redirect_by_replacing_jump (single_succ_edge (b
),
2117 (mode
& CLEANUP_CFGLAYOUT
) != 0))
2119 update_forwarder_flag (b
);
2120 changed_here
= true;
2123 /* Simplify branch to branch. */
2124 if (try_forward_edges (mode
, b
))
2125 changed_here
= true;
2127 /* Look for shared code between blocks. */
2128 if ((mode
& CLEANUP_CROSSJUMP
)
2129 && try_crossjump_bb (mode
, b
))
2130 changed_here
= true;
2132 /* Don't get confused by the index shift caused by
2140 if ((mode
& CLEANUP_CROSSJUMP
)
2141 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
2144 #ifdef ENABLE_CHECKING
2146 verify_flow_info ();
2149 changed_overall
|= changed
;
2155 if (mode
& CLEANUP_CROSSJUMP
)
2156 remove_fake_exit_edges ();
2159 b
->flags
&= ~(BB_FORWARDER_BLOCK
| BB_NONTHREADABLE_BLOCK
);
2161 return changed_overall
;
2164 /* Delete all unreachable basic blocks. */
2167 delete_unreachable_blocks (void)
2169 bool changed
= false;
2170 basic_block b
, next_bb
;
2172 find_unreachable_blocks ();
2174 /* Delete all unreachable basic blocks. */
2176 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
; b
= next_bb
)
2178 next_bb
= b
->next_bb
;
2180 if (!(b
->flags
& BB_REACHABLE
))
2182 delete_basic_block (b
);
2188 tidy_fallthru_edges ();
2192 /* Merges sequential blocks if possible. */
2195 merge_seq_blocks (void)
2198 bool changed
= false;
2200 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
!= EXIT_BLOCK_PTR
; )
2202 if (single_succ_p (bb
)
2203 && can_merge_blocks_p (bb
, single_succ (bb
)))
2205 /* Merge the blocks and retry. */
2206 merge_blocks (bb
, single_succ (bb
));
2217 /* Tidy the CFG by deleting unreachable code and whatnot. */
2220 cleanup_cfg (int mode
)
2222 bool changed
= false;
2224 /* Set the cfglayout mode flag here. We could update all the callers
2225 but that is just inconvenient, especially given that we eventually
2226 want to have cfglayout mode as the default. */
2227 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2228 mode
|= CLEANUP_CFGLAYOUT
;
2230 timevar_push (TV_CLEANUP_CFG
);
2231 if (delete_unreachable_blocks ())
2234 /* We've possibly created trivially dead code. Cleanup it right
2235 now to introduce more opportunities for try_optimize_cfg. */
2236 if (!(mode
& (CLEANUP_NO_INSN_DEL
| CLEANUP_UPDATE_LIFE
))
2237 && !reload_completed
)
2238 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2243 while (try_optimize_cfg (mode
))
2245 delete_unreachable_blocks (), changed
= true;
2246 if (mode
& CLEANUP_UPDATE_LIFE
)
2248 /* Cleaning up CFG introduces more opportunities for dead code
2249 removal that in turn may introduce more opportunities for
2250 cleaning up the CFG. */
2251 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES
,
2253 | PROP_SCAN_DEAD_CODE
2254 | PROP_KILL_DEAD_CODE
2255 | ((mode
& CLEANUP_LOG_LINKS
)
2256 ? PROP_LOG_LINKS
: 0)))
2259 else if (!(mode
& CLEANUP_NO_INSN_DEL
)
2260 && (mode
& CLEANUP_EXPENSIVE
)
2261 && !reload_completed
)
2263 if (!delete_trivially_dead_insns (get_insns (), max_reg_num ()))
2269 /* Don't call delete_dead_jumptables in cfglayout mode, because
2270 that function assumes that jump tables are in the insns stream.
2271 But we also don't _have_ to delete dead jumptables in cfglayout
2272 mode because we shouldn't even be looking at things that are
2273 not in a basic block. Dead jumptables are cleaned up when
2274 going out of cfglayout mode. */
2275 if (!(mode
& CLEANUP_CFGLAYOUT
))
2276 delete_dead_jumptables ();
2279 timevar_pop (TV_CLEANUP_CFG
);
2285 rest_of_handle_jump (void)
2287 delete_unreachable_blocks ();
2289 if (cfun
->tail_call_emit
)
2290 fixup_tail_calls ();
2294 struct tree_opt_pass pass_jump
=
2296 "sibling", /* name */
2298 rest_of_handle_jump
, /* execute */
2301 0, /* static_pass_number */
2302 TV_JUMP
, /* tv_id */
2303 0, /* properties_required */
2304 0, /* properties_provided */
2305 0, /* properties_destroyed */
2306 TODO_ggc_collect
, /* todo_flags_start */
2308 TODO_verify_flow
, /* todo_flags_finish */
2314 rest_of_handle_jump2 (void)
2316 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2317 reg_scan (get_insns (), max_reg_num ());
2319 dump_flow_info (dump_file
, dump_flags
);
2320 cleanup_cfg ((optimize
? CLEANUP_EXPENSIVE
: 0)
2321 | (flag_thread_jumps
? CLEANUP_THREADING
: 0));
2326 struct tree_opt_pass pass_jump2
=
2330 rest_of_handle_jump2
, /* execute */
2333 0, /* static_pass_number */
2334 TV_JUMP
, /* tv_id */
2335 0, /* properties_required */
2336 0, /* properties_provided */
2337 0, /* properties_destroyed */
2338 TODO_ggc_collect
, /* todo_flags_start */
2339 TODO_dump_func
, /* todo_flags_finish */