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 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This file contains optimizer of the control flow. The main entrypoint 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"
40 #include "basic-block.h"
43 #include "insn-config.h"
54 /* cleanup_cfg maintains following flags for each basic block. */
58 /* Set if BB is the forwarder block to avoid too many
59 forwarder_block_p calls. */
60 BB_FORWARDER_BLOCK
= 1,
61 BB_NONTHREADABLE_BLOCK
= 2
64 #define BB_FLAGS(BB) (enum bb_flags) (BB)->aux
65 #define BB_SET_FLAG(BB, FLAG) \
66 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG))
67 #define BB_CLEAR_FLAG(BB, FLAG) \
68 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG))
70 #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
72 /* Set to true when we are running first pass of try_optimize_cfg loop. */
73 static bool first_pass
;
74 static bool try_crossjump_to_edge (int, edge
, edge
);
75 static bool try_crossjump_bb (int, basic_block
);
76 static bool outgoing_edges_match (int, basic_block
, basic_block
);
77 static int flow_find_cross_jump (int, basic_block
, basic_block
, rtx
*, rtx
*);
78 static bool insns_match_p (int, rtx
, rtx
);
80 static bool tail_recursion_label_p (rtx
);
81 static void merge_blocks_move_predecessor_nojumps (basic_block
, basic_block
);
82 static void merge_blocks_move_successor_nojumps (basic_block
, basic_block
);
83 static bool try_optimize_cfg (int);
84 static bool try_simplify_condjump (basic_block
);
85 static bool try_forward_edges (int, basic_block
);
86 static edge
thread_jump (int, edge
, basic_block
);
87 static bool mark_effect (rtx
, bitmap
);
88 static void notice_new_block (basic_block
);
89 static void update_forwarder_flag (basic_block
);
90 static int mentions_nonequal_regs (rtx
*, void *);
91 static void merge_memattrs (rtx
, rtx
);
93 /* Set flags for newly created block. */
96 notice_new_block (basic_block bb
)
101 if (forwarder_block_p (bb
))
102 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
105 /* Recompute forwarder flag after block has been modified. */
108 update_forwarder_flag (basic_block bb
)
110 if (forwarder_block_p (bb
))
111 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
113 BB_CLEAR_FLAG (bb
, BB_FORWARDER_BLOCK
);
116 /* Simplify a conditional jump around an unconditional jump.
117 Return true if something changed. */
120 try_simplify_condjump (basic_block cbranch_block
)
122 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
123 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
128 /* Verify that there are exactly two successors. */
129 if (!cbranch_block
->succ
130 || !cbranch_block
->succ
->succ_next
131 || cbranch_block
->succ
->succ_next
->succ_next
)
134 /* Verify that we've got a normal conditional branch at the end
136 cbranch_insn
= BB_END (cbranch_block
);
137 if (!any_condjump_p (cbranch_insn
))
140 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
141 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
143 /* The next block must not have multiple predecessors, must not
144 be the last block in the function, and must contain just the
145 unconditional jump. */
146 jump_block
= cbranch_fallthru_edge
->dest
;
147 if (jump_block
->pred
->pred_next
148 || jump_block
->next_bb
== EXIT_BLOCK_PTR
149 || !FORWARDER_BLOCK_P (jump_block
))
151 jump_dest_block
= jump_block
->succ
->dest
;
153 /* The conditional branch must target the block after the
154 unconditional branch. */
155 cbranch_dest_block
= cbranch_jump_edge
->dest
;
157 if (!can_fallthru (jump_block
, cbranch_dest_block
))
160 /* Invert the conditional branch. */
161 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
165 fprintf (dump_file
, "Simplifying condjump %i around jump %i\n",
166 INSN_UID (cbranch_insn
), INSN_UID (BB_END (jump_block
)));
168 /* Success. Update the CFG to match. Note that after this point
169 the edge variable names appear backwards; the redirection is done
170 this way to preserve edge profile data. */
171 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
173 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
175 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
176 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
177 update_br_prob_note (cbranch_block
);
179 end
= BB_END (jump_block
);
180 /* Deleting a block may produce unreachable code warning even when we are
181 not deleting anything live. Suppress it by moving all the line number
182 notes out of the block. */
183 for (insn
= BB_HEAD (jump_block
); insn
!= NEXT_INSN (BB_END (jump_block
));
186 next
= NEXT_INSN (insn
);
187 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
189 if (insn
== BB_END (jump_block
))
191 BB_END (jump_block
) = PREV_INSN (insn
);
195 reorder_insns_nobb (insn
, insn
, end
);
199 /* Delete the block with the unconditional jump, and clean up the mess. */
200 delete_basic_block (jump_block
);
201 tidy_fallthru_edge (cbranch_jump_edge
);
206 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
207 on register. Used by jump threading. */
210 mark_effect (rtx exp
, regset nonequal
)
214 switch (GET_CODE (exp
))
216 /* In case we do clobber the register, mark it as equal, as we know the
217 value is dead so it don't have to match. */
219 if (REG_P (XEXP (exp
, 0)))
221 dest
= XEXP (exp
, 0);
222 regno
= REGNO (dest
);
223 CLEAR_REGNO_REG_SET (nonequal
, regno
);
224 if (regno
< FIRST_PSEUDO_REGISTER
)
226 int n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
228 CLEAR_REGNO_REG_SET (nonequal
, regno
+ n
);
234 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
236 dest
= SET_DEST (exp
);
241 regno
= REGNO (dest
);
242 SET_REGNO_REG_SET (nonequal
, regno
);
243 if (regno
< FIRST_PSEUDO_REGISTER
)
245 int n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
247 SET_REGNO_REG_SET (nonequal
, regno
+ n
);
256 /* Return nonzero if X is a register set in regset DATA.
257 Called via for_each_rtx. */
259 mentions_nonequal_regs (rtx
*x
, void *data
)
261 regset nonequal
= (regset
) data
;
267 if (REGNO_REG_SET_P (nonequal
, regno
))
269 if (regno
< FIRST_PSEUDO_REGISTER
)
271 int n
= hard_regno_nregs
[regno
][GET_MODE (*x
)];
273 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
279 /* Attempt to prove that the basic block B will have no side effects and
280 always continues in the same edge if reached via E. Return the edge
281 if exist, NULL otherwise. */
284 thread_jump (int mode
, edge e
, basic_block b
)
286 rtx set1
, set2
, cond1
, cond2
, insn
;
287 enum rtx_code code1
, code2
, reversed_code2
;
288 bool reverse1
= false;
293 if (BB_FLAGS (b
) & BB_NONTHREADABLE_BLOCK
)
296 /* At the moment, we do handle only conditional jumps, but later we may
297 want to extend this code to tablejumps and others. */
298 if (!e
->src
->succ
->succ_next
|| e
->src
->succ
->succ_next
->succ_next
)
300 if (!b
->succ
|| !b
->succ
->succ_next
|| b
->succ
->succ_next
->succ_next
)
302 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
306 /* Second branch must end with onlyjump, as we will eliminate the jump. */
307 if (!any_condjump_p (BB_END (e
->src
)))
310 if (!any_condjump_p (BB_END (b
)) || !onlyjump_p (BB_END (b
)))
312 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
316 set1
= pc_set (BB_END (e
->src
));
317 set2
= pc_set (BB_END (b
));
318 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
319 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
322 cond1
= XEXP (SET_SRC (set1
), 0);
323 cond2
= XEXP (SET_SRC (set2
), 0);
325 code1
= reversed_comparison_code (cond1
, BB_END (e
->src
));
327 code1
= GET_CODE (cond1
);
329 code2
= GET_CODE (cond2
);
330 reversed_code2
= reversed_comparison_code (cond2
, BB_END (b
));
332 if (!comparison_dominates_p (code1
, code2
)
333 && !comparison_dominates_p (code1
, reversed_code2
))
336 /* Ensure that the comparison operators are equivalent.
337 ??? This is far too pessimistic. We should allow swapped operands,
338 different CCmodes, or for example comparisons for interval, that
339 dominate even when operands are not equivalent. */
340 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
341 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
344 /* Short circuit cases where block B contains some side effects, as we can't
346 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
));
347 insn
= NEXT_INSN (insn
))
348 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
350 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
356 /* First process all values computed in the source basic block. */
357 for (insn
= NEXT_INSN (BB_HEAD (e
->src
)); insn
!= NEXT_INSN (BB_END (e
->src
));
358 insn
= NEXT_INSN (insn
))
360 cselib_process_insn (insn
);
362 nonequal
= BITMAP_XMALLOC();
363 CLEAR_REG_SET (nonequal
);
365 /* Now assume that we've continued by the edge E to B and continue
366 processing as if it were same basic block.
367 Our goal is to prove that whole block is an NOOP. */
369 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
)) && !failed
;
370 insn
= NEXT_INSN (insn
))
374 rtx pat
= PATTERN (insn
);
376 if (GET_CODE (pat
) == PARALLEL
)
378 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
379 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
382 failed
|= mark_effect (pat
, nonequal
);
385 cselib_process_insn (insn
);
388 /* Later we should clear nonequal of dead registers. So far we don't
389 have life information in cfg_cleanup. */
392 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
396 /* cond2 must not mention any register that is not equal to the
398 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
401 /* In case liveness information is available, we need to prove equivalence
402 only of the live values. */
403 if (mode
& CLEANUP_UPDATE_LIFE
)
404 AND_REG_SET (nonequal
, b
->global_live_at_end
);
406 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, goto failed_exit
;);
408 BITMAP_XFREE (nonequal
);
410 if ((comparison_dominates_p (code1
, code2
) != 0)
411 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
412 return BRANCH_EDGE (b
);
414 return FALLTHRU_EDGE (b
);
417 BITMAP_XFREE (nonequal
);
422 /* Attempt to forward edges leaving basic block B.
423 Return true if successful. */
426 try_forward_edges (int mode
, basic_block b
)
428 bool changed
= false;
429 edge e
, next
, *threaded_edges
= NULL
;
431 for (e
= b
->succ
; e
; e
= next
)
433 basic_block target
, first
;
435 bool threaded
= false;
436 int nthreaded_edges
= 0;
437 bool may_thread
= first_pass
| (b
->flags
& BB_DIRTY
);
441 /* Skip complex edges because we don't know how to update them.
443 Still handle fallthru edges, as we can succeed to forward fallthru
444 edge to the same place as the branch edge of conditional branch
445 and turn conditional branch to an unconditional branch. */
446 if (e
->flags
& EDGE_COMPLEX
)
449 target
= first
= e
->dest
;
452 while (counter
< n_basic_blocks
)
454 basic_block new_target
= NULL
;
455 bool new_target_threaded
= false;
456 may_thread
|= target
->flags
& BB_DIRTY
;
458 if (FORWARDER_BLOCK_P (target
)
459 && target
->succ
->dest
!= EXIT_BLOCK_PTR
)
461 /* Bypass trivial infinite loops. */
462 if (target
== target
->succ
->dest
)
463 counter
= n_basic_blocks
;
464 new_target
= target
->succ
->dest
;
467 /* Allow to thread only over one edge at time to simplify updating
469 else if ((mode
& CLEANUP_THREADING
) && may_thread
)
471 edge t
= thread_jump (mode
, e
, target
);
475 threaded_edges
= xmalloc (sizeof (*threaded_edges
)
481 /* Detect an infinite loop across blocks not
482 including the start block. */
483 for (i
= 0; i
< nthreaded_edges
; ++i
)
484 if (threaded_edges
[i
] == t
)
486 if (i
< nthreaded_edges
)
488 counter
= n_basic_blocks
;
493 /* Detect an infinite loop across the start block. */
497 if (nthreaded_edges
>= n_basic_blocks
)
499 threaded_edges
[nthreaded_edges
++] = t
;
501 new_target
= t
->dest
;
502 new_target_threaded
= true;
509 /* Avoid killing of loop pre-headers, as it is the place loop
510 optimizer wants to hoist code to.
512 For fallthru forwarders, the LOOP_BEG note must appear between
513 the header of block and CODE_LABEL of the loop, for non forwarders
514 it must appear before the JUMP_INSN. */
515 if ((mode
& CLEANUP_PRE_LOOP
) && optimize
)
517 rtx insn
= (target
->succ
->flags
& EDGE_FALLTHRU
518 ? BB_HEAD (target
) : prev_nonnote_insn (BB_END (target
)));
520 if (GET_CODE (insn
) != NOTE
)
521 insn
= NEXT_INSN (insn
);
523 for (; insn
&& GET_CODE (insn
) != CODE_LABEL
&& !INSN_P (insn
);
524 insn
= NEXT_INSN (insn
))
525 if (GET_CODE (insn
) == NOTE
526 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
529 if (GET_CODE (insn
) == NOTE
)
532 /* Do not clean up branches to just past the end of a loop
533 at this time; it can mess up the loop optimizer's
534 recognition of some patterns. */
536 insn
= PREV_INSN (BB_HEAD (target
));
537 if (insn
&& GET_CODE (insn
) == NOTE
538 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
544 threaded
|= new_target_threaded
;
547 if (counter
>= n_basic_blocks
)
550 fprintf (dump_file
, "Infinite loop in BB %i.\n",
553 else if (target
== first
)
554 ; /* We didn't do anything. */
557 /* Save the values now, as the edge may get removed. */
558 gcov_type edge_count
= e
->count
;
559 int edge_probability
= e
->probability
;
563 /* Don't force if target is exit block. */
564 if (threaded
&& target
!= EXIT_BLOCK_PTR
)
566 notice_new_block (redirect_edge_and_branch_force (e
, target
));
568 fprintf (dump_file
, "Conditionals threaded.\n");
570 else if (!redirect_edge_and_branch (e
, target
))
574 "Forwarding edge %i->%i to %i failed.\n",
575 b
->index
, e
->dest
->index
, target
->index
);
579 /* We successfully forwarded the edge. Now update profile
580 data: for each edge we traversed in the chain, remove
581 the original edge's execution count. */
582 edge_frequency
= ((edge_probability
* b
->frequency
583 + REG_BR_PROB_BASE
/ 2)
586 if (!FORWARDER_BLOCK_P (b
) && forwarder_block_p (b
))
587 BB_SET_FLAG (b
, BB_FORWARDER_BLOCK
);
593 first
->count
-= edge_count
;
594 if (first
->count
< 0)
596 first
->frequency
-= edge_frequency
;
597 if (first
->frequency
< 0)
598 first
->frequency
= 0;
599 if (first
->succ
->succ_next
)
603 if (n
>= nthreaded_edges
)
605 t
= threaded_edges
[n
++];
608 if (first
->frequency
)
609 prob
= edge_frequency
* REG_BR_PROB_BASE
/ first
->frequency
;
612 if (prob
> t
->probability
)
613 prob
= t
->probability
;
614 t
->probability
-= prob
;
615 prob
= REG_BR_PROB_BASE
- prob
;
618 first
->succ
->probability
= REG_BR_PROB_BASE
;
619 first
->succ
->succ_next
->probability
= 0;
622 for (e
= first
->succ
; e
; e
= e
->succ_next
)
623 e
->probability
= ((e
->probability
* REG_BR_PROB_BASE
)
625 update_br_prob_note (first
);
629 /* It is possible that as the result of
630 threading we've removed edge as it is
631 threaded to the fallthru edge. Avoid
632 getting out of sync. */
633 if (n
< nthreaded_edges
634 && first
== threaded_edges
[n
]->src
)
639 t
->count
-= edge_count
;
644 while (first
!= target
);
651 free (threaded_edges
);
655 /* Return true if LABEL is used for tail recursion. */
658 tail_recursion_label_p (rtx label
)
662 for (x
= tail_recursion_label_list
; x
; x
= XEXP (x
, 1))
663 if (label
== XEXP (x
, 0))
669 /* Blocks A and B are to be merged into a single block. A has no incoming
670 fallthru edge, so it can be moved before B without adding or modifying
671 any jumps (aside from the jump from A to B). */
674 merge_blocks_move_predecessor_nojumps (basic_block a
, basic_block b
)
678 barrier
= next_nonnote_insn (BB_END (a
));
679 if (GET_CODE (barrier
) != BARRIER
)
681 delete_insn (barrier
);
683 /* Move block and loop notes out of the chain so that we do not
686 ??? A better solution would be to squeeze out all the non-nested notes
687 and adjust the block trees appropriately. Even better would be to have
688 a tighter connection between block trees and rtl so that this is not
690 if (squeeze_notes (&BB_HEAD (a
), &BB_END (a
)))
693 /* Scramble the insn chain. */
694 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
695 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
696 a
->flags
|= BB_DIRTY
;
699 fprintf (dump_file
, "Moved block %d before %d and merged.\n",
702 /* Swap the records for the two blocks around. */
705 link_block (a
, b
->prev_bb
);
707 /* Now blocks A and B are contiguous. Merge them. */
711 /* Blocks A and B are to be merged into a single block. B has no outgoing
712 fallthru edge, so it can be moved after A without adding or modifying
713 any jumps (aside from the jump from A to B). */
716 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
718 rtx barrier
, real_b_end
;
721 real_b_end
= BB_END (b
);
723 /* If there is a jump table following block B temporarily add the jump table
724 to block B so that it will also be moved to the correct location. */
725 if (tablejump_p (BB_END (b
), &label
, &table
)
726 && prev_active_insn (label
) == BB_END (b
))
731 /* There had better have been a barrier there. Delete it. */
732 barrier
= NEXT_INSN (BB_END (b
));
733 if (barrier
&& GET_CODE (barrier
) == BARRIER
)
734 delete_insn (barrier
);
736 /* Move block and loop notes out of the chain so that we do not
739 ??? A better solution would be to squeeze out all the non-nested notes
740 and adjust the block trees appropriately. Even better would be to have
741 a tighter connection between block trees and rtl so that this is not
743 if (squeeze_notes (&BB_HEAD (b
), &BB_END (b
)))
746 /* Scramble the insn chain. */
747 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
749 /* Restore the real end of b. */
750 BB_END (b
) = real_b_end
;
753 fprintf (dump_file
, "Moved block %d after %d and merged.\n",
756 /* Now blocks A and B are contiguous. Merge them. */
760 /* Attempt to merge basic blocks that are potentially non-adjacent.
761 Return NULL iff the attempt failed, otherwise return basic block
762 where cleanup_cfg should continue. Because the merging commonly
763 moves basic block away or introduces another optimization
764 possibility, return basic block just before B so cleanup_cfg don't
767 It may be good idea to return basic block before C in the case
768 C has been moved after B and originally appeared earlier in the
769 insn sequence, but we have no information available about the
770 relative ordering of these two. Hopefully it is not too common. */
773 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
776 /* If C has a tail recursion label, do not merge. There is no
777 edge recorded from the call_placeholder back to this label, as
778 that would make optimize_sibling_and_tail_recursive_calls more
779 complex for no gain. */
780 if ((mode
& CLEANUP_PRE_SIBCALL
)
781 && GET_CODE (BB_HEAD (c
)) == CODE_LABEL
782 && tail_recursion_label_p (BB_HEAD (c
)))
785 /* If B has a fallthru edge to C, no need to move anything. */
786 if (e
->flags
& EDGE_FALLTHRU
)
788 int b_index
= b
->index
, c_index
= c
->index
;
790 update_forwarder_flag (b
);
793 fprintf (dump_file
, "Merged %d and %d without moving.\n",
796 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
799 /* Otherwise we will need to move code around. Do that only if expensive
800 transformations are allowed. */
801 else if (mode
& CLEANUP_EXPENSIVE
)
803 edge tmp_edge
, b_fallthru_edge
;
804 bool c_has_outgoing_fallthru
;
805 bool b_has_incoming_fallthru
;
807 /* Avoid overactive code motion, as the forwarder blocks should be
808 eliminated by edge redirection instead. One exception might have
809 been if B is a forwarder block and C has no fallthru edge, but
810 that should be cleaned up by bb-reorder instead. */
811 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
814 /* We must make sure to not munge nesting of lexical blocks,
815 and loop notes. This is done by squeezing out all the notes
816 and leaving them there to lie. Not ideal, but functional. */
818 for (tmp_edge
= c
->succ
; tmp_edge
; tmp_edge
= tmp_edge
->succ_next
)
819 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
822 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
824 for (tmp_edge
= b
->pred
; tmp_edge
; tmp_edge
= tmp_edge
->pred_next
)
825 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
828 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
829 b_fallthru_edge
= tmp_edge
;
832 next
= next
->prev_bb
;
834 /* Otherwise, we're going to try to move C after B. If C does
835 not have an outgoing fallthru, then it can be moved
836 immediately after B without introducing or modifying jumps. */
837 if (! c_has_outgoing_fallthru
)
839 merge_blocks_move_successor_nojumps (b
, c
);
840 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
843 /* If B does not have an incoming fallthru, then it can be moved
844 immediately before C without introducing or modifying jumps.
845 C cannot be the first block, so we do not have to worry about
846 accessing a non-existent block. */
848 if (b_has_incoming_fallthru
)
852 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
854 bb
= force_nonfallthru (b_fallthru_edge
);
856 notice_new_block (bb
);
859 merge_blocks_move_predecessor_nojumps (b
, c
);
860 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
867 /* Removes the memory attributes of MEM expression
868 if they are not equal. */
871 merge_memattrs (rtx x
, rtx y
)
880 if (x
== 0 || y
== 0)
885 if (code
!= GET_CODE (y
))
888 if (GET_MODE (x
) != GET_MODE (y
))
891 if (code
== MEM
&& MEM_ATTRS (x
) != MEM_ATTRS (y
))
895 else if (! MEM_ATTRS (y
))
899 if (MEM_ALIAS_SET (x
) != MEM_ALIAS_SET (y
))
901 set_mem_alias_set (x
, 0);
902 set_mem_alias_set (y
, 0);
905 if (! mem_expr_equal_p (MEM_EXPR (x
), MEM_EXPR (y
)))
909 set_mem_offset (x
, 0);
910 set_mem_offset (y
, 0);
912 else if (MEM_OFFSET (x
) != MEM_OFFSET (y
))
914 set_mem_offset (x
, 0);
915 set_mem_offset (y
, 0);
918 set_mem_size (x
, MAX (MEM_SIZE (x
), MEM_SIZE (y
)));
919 set_mem_size (y
, MEM_SIZE (x
));
921 set_mem_align (x
, MIN (MEM_ALIGN (x
), MEM_ALIGN (y
)));
922 set_mem_align (y
, MEM_ALIGN (x
));
926 fmt
= GET_RTX_FORMAT (code
);
927 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
932 /* Two vectors must have the same length. */
933 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
936 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
937 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
942 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
949 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
952 insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
956 /* Verify that I1 and I2 are equivalent. */
957 if (GET_CODE (i1
) != GET_CODE (i2
))
963 if (GET_CODE (p1
) != GET_CODE (p2
))
966 /* If this is a CALL_INSN, compare register usage information.
967 If we don't check this on stack register machines, the two
968 CALL_INSNs might be merged leaving reg-stack.c with mismatching
969 numbers of stack registers in the same basic block.
970 If we don't check this on machines with delay slots, a delay slot may
971 be filled that clobbers a parameter expected by the subroutine.
973 ??? We take the simple route for now and assume that if they're
974 equal, they were constructed identically. */
976 if (GET_CODE (i1
) == CALL_INSN
977 && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
978 CALL_INSN_FUNCTION_USAGE (i2
))
979 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
)))
983 /* If cross_jump_death_matters is not 0, the insn's mode
984 indicates whether or not the insn contains any stack-like
987 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
989 /* If register stack conversion has already been done, then
990 death notes must also be compared before it is certain that
991 the two instruction streams match. */
994 HARD_REG_SET i1_regset
, i2_regset
;
996 CLEAR_HARD_REG_SET (i1_regset
);
997 CLEAR_HARD_REG_SET (i2_regset
);
999 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
1000 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1001 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
1003 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
1004 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1005 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
1007 GO_IF_HARD_REG_EQUAL (i1_regset
, i2_regset
, done
);
1016 if (reload_completed
1017 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
1020 /* Do not do EQUIV substitution after reload. First, we're undoing the
1021 work of reload_cse. Second, we may be undoing the work of the post-
1022 reload splitting pass. */
1023 /* ??? Possibly add a new phase switch variable that can be used by
1024 targets to disallow the troublesome insns after splitting. */
1025 if (!reload_completed
)
1027 /* The following code helps take care of G++ cleanups. */
1028 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1029 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1031 if (equiv1
&& equiv2
1032 /* If the equivalences are not to a constant, they may
1033 reference pseudos that no longer exist, so we can't
1035 && (! reload_completed
1036 || (CONSTANT_P (XEXP (equiv1
, 0))
1037 && rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))))
1039 rtx s1
= single_set (i1
);
1040 rtx s2
= single_set (i2
);
1041 if (s1
!= 0 && s2
!= 0
1042 && rtx_renumbered_equal_p (SET_DEST (s1
), SET_DEST (s2
)))
1044 validate_change (i1
, &SET_SRC (s1
), XEXP (equiv1
, 0), 1);
1045 validate_change (i2
, &SET_SRC (s2
), XEXP (equiv2
, 0), 1);
1046 if (! rtx_renumbered_equal_p (p1
, p2
))
1048 else if (apply_change_group ())
1057 /* Look through the insns at the end of BB1 and BB2 and find the longest
1058 sequence that are equivalent. Store the first insns for that sequence
1059 in *F1 and *F2 and return the sequence length.
1061 To simplify callers of this function, if the blocks match exactly,
1062 store the head of the blocks in *F1 and *F2. */
1065 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED
, basic_block bb1
,
1066 basic_block bb2
, rtx
*f1
, rtx
*f2
)
1068 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
1071 /* Skip simple jumps at the end of the blocks. Complex jumps still
1072 need to be compared for equivalence, which we'll do below. */
1075 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
1077 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1080 i1
= PREV_INSN (i1
);
1085 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1088 /* Count everything except for unconditional jump as insn. */
1089 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1091 i2
= PREV_INSN (i2
);
1097 while (!INSN_P (i1
) && i1
!= BB_HEAD (bb1
))
1098 i1
= PREV_INSN (i1
);
1100 while (!INSN_P (i2
) && i2
!= BB_HEAD (bb2
))
1101 i2
= PREV_INSN (i2
);
1103 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1106 if (!insns_match_p (mode
, i1
, i2
))
1109 merge_memattrs (i1
, i2
);
1111 /* Don't begin a cross-jump with a NOTE insn. */
1114 /* If the merged insns have different REG_EQUAL notes, then
1116 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1117 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1119 if (equiv1
&& !equiv2
)
1120 remove_note (i1
, equiv1
);
1121 else if (!equiv1
&& equiv2
)
1122 remove_note (i2
, equiv2
);
1123 else if (equiv1
&& equiv2
1124 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1126 remove_note (i1
, equiv1
);
1127 remove_note (i2
, equiv2
);
1130 afterlast1
= last1
, afterlast2
= last2
;
1131 last1
= i1
, last2
= i2
;
1135 i1
= PREV_INSN (i1
);
1136 i2
= PREV_INSN (i2
);
1140 /* Don't allow the insn after a compare to be shared by
1141 cross-jumping unless the compare is also shared. */
1142 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1143 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
1146 /* Include preceding notes and labels in the cross-jump. One,
1147 this may bring us to the head of the blocks as requested above.
1148 Two, it keeps line number notes as matched as may be. */
1151 while (last1
!= BB_HEAD (bb1
) && !INSN_P (PREV_INSN (last1
)))
1152 last1
= PREV_INSN (last1
);
1154 if (last1
!= BB_HEAD (bb1
) && GET_CODE (PREV_INSN (last1
)) == CODE_LABEL
)
1155 last1
= PREV_INSN (last1
);
1157 while (last2
!= BB_HEAD (bb2
) && !INSN_P (PREV_INSN (last2
)))
1158 last2
= PREV_INSN (last2
);
1160 if (last2
!= BB_HEAD (bb2
) && GET_CODE (PREV_INSN (last2
)) == CODE_LABEL
)
1161 last2
= PREV_INSN (last2
);
1170 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1171 the branch instruction. This means that if we commonize the control
1172 flow before end of the basic block, the semantic remains unchanged.
1174 We may assume that there exists one edge with a common destination. */
1177 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1179 int nehedges1
= 0, nehedges2
= 0;
1180 edge fallthru1
= 0, fallthru2
= 0;
1183 /* If BB1 has only one successor, we may be looking at either an
1184 unconditional jump, or a fake edge to exit. */
1185 if (bb1
->succ
&& !bb1
->succ
->succ_next
1186 && (bb1
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1187 && (GET_CODE (BB_END (bb1
)) != JUMP_INSN
|| simplejump_p (BB_END (bb1
))))
1188 return (bb2
->succ
&& !bb2
->succ
->succ_next
1189 && (bb2
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1190 && (GET_CODE (BB_END (bb2
)) != JUMP_INSN
|| simplejump_p (BB_END (bb2
))));
1192 /* Match conditional jumps - this may get tricky when fallthru and branch
1193 edges are crossed. */
1195 && bb1
->succ
->succ_next
1196 && !bb1
->succ
->succ_next
->succ_next
1197 && any_condjump_p (BB_END (bb1
))
1198 && onlyjump_p (BB_END (bb1
)))
1200 edge b1
, f1
, b2
, f2
;
1201 bool reverse
, match
;
1202 rtx set1
, set2
, cond1
, cond2
;
1203 enum rtx_code code1
, code2
;
1206 || !bb2
->succ
->succ_next
1207 || bb2
->succ
->succ_next
->succ_next
1208 || !any_condjump_p (BB_END (bb2
))
1209 || !onlyjump_p (BB_END (bb2
)))
1212 b1
= BRANCH_EDGE (bb1
);
1213 b2
= BRANCH_EDGE (bb2
);
1214 f1
= FALLTHRU_EDGE (bb1
);
1215 f2
= FALLTHRU_EDGE (bb2
);
1217 /* Get around possible forwarders on fallthru edges. Other cases
1218 should be optimized out already. */
1219 if (FORWARDER_BLOCK_P (f1
->dest
))
1220 f1
= f1
->dest
->succ
;
1222 if (FORWARDER_BLOCK_P (f2
->dest
))
1223 f2
= f2
->dest
->succ
;
1225 /* To simplify use of this function, return false if there are
1226 unneeded forwarder blocks. These will get eliminated later
1227 during cleanup_cfg. */
1228 if (FORWARDER_BLOCK_P (f1
->dest
)
1229 || FORWARDER_BLOCK_P (f2
->dest
)
1230 || FORWARDER_BLOCK_P (b1
->dest
)
1231 || FORWARDER_BLOCK_P (b2
->dest
))
1234 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1236 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1241 set1
= pc_set (BB_END (bb1
));
1242 set2
= pc_set (BB_END (bb2
));
1243 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1244 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1247 cond1
= XEXP (SET_SRC (set1
), 0);
1248 cond2
= XEXP (SET_SRC (set2
), 0);
1249 code1
= GET_CODE (cond1
);
1251 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1253 code2
= GET_CODE (cond2
);
1255 if (code2
== UNKNOWN
)
1258 /* Verify codes and operands match. */
1259 match
= ((code1
== code2
1260 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1261 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1262 || (code1
== swap_condition (code2
)
1263 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1265 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1268 /* If we return true, we will join the blocks. Which means that
1269 we will only have one branch prediction bit to work with. Thus
1270 we require the existing branches to have probabilities that are
1274 && maybe_hot_bb_p (bb1
)
1275 && maybe_hot_bb_p (bb2
))
1279 if (b1
->dest
== b2
->dest
)
1280 prob2
= b2
->probability
;
1282 /* Do not use f2 probability as f2 may be forwarded. */
1283 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1285 /* Fail if the difference in probabilities is greater than 50%.
1286 This rules out two well-predicted branches with opposite
1288 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1292 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1293 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1299 if (dump_file
&& match
)
1300 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1301 bb1
->index
, bb2
->index
);
1306 /* Generic case - we are seeing a computed jump, table jump or trapping
1309 #ifndef CASE_DROPS_THROUGH
1310 /* Check whether there are tablejumps in the end of BB1 and BB2.
1311 Return true if they are identical. */
1316 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1317 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1318 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1320 /* The labels should never be the same rtx. If they really are same
1321 the jump tables are same too. So disable crossjumping of blocks BB1
1322 and BB2 because when deleting the common insns in the end of BB1
1323 by delete_block () the jump table would be deleted too. */
1324 /* If LABEL2 is referenced in BB1->END do not do anything
1325 because we would loose information when replacing
1326 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1327 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1329 /* Set IDENTICAL to true when the tables are identical. */
1330 bool identical
= false;
1333 p1
= PATTERN (table1
);
1334 p2
= PATTERN (table2
);
1335 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1339 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1340 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1341 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1342 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1347 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1348 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1354 replace_label_data rr
;
1357 /* Temporarily replace references to LABEL1 with LABEL2
1358 in BB1->END so that we could compare the instructions. */
1361 rr
.update_label_nuses
= false;
1362 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1364 match
= insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
));
1365 if (dump_file
&& match
)
1367 "Tablejumps in bb %i and %i match.\n",
1368 bb1
->index
, bb2
->index
);
1370 /* Set the original label in BB1->END because when deleting
1371 a block whose end is a tablejump, the tablejump referenced
1372 from the instruction is deleted too. */
1375 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1385 /* First ensure that the instructions match. There may be many outgoing
1386 edges so this test is generally cheaper. */
1387 if (!insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
)))
1390 /* Search the outgoing edges, ensure that the counts do match, find possible
1391 fallthru and exception handling edges since these needs more
1393 for (e1
= bb1
->succ
, e2
= bb2
->succ
; e1
&& e2
;
1394 e1
= e1
->succ_next
, e2
= e2
->succ_next
)
1396 if (e1
->flags
& EDGE_EH
)
1399 if (e2
->flags
& EDGE_EH
)
1402 if (e1
->flags
& EDGE_FALLTHRU
)
1404 if (e2
->flags
& EDGE_FALLTHRU
)
1408 /* If number of edges of various types does not match, fail. */
1410 || nehedges1
!= nehedges2
1411 || (fallthru1
!= 0) != (fallthru2
!= 0))
1414 /* fallthru edges must be forwarded to the same destination. */
1417 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1418 ? fallthru1
->dest
->succ
->dest
: fallthru1
->dest
);
1419 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1420 ? fallthru2
->dest
->succ
->dest
: fallthru2
->dest
);
1426 /* Ensure the same EH region. */
1428 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1429 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1434 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1438 /* We don't need to match the rest of edges as above checks should be enough
1439 to ensure that they are equivalent. */
1443 /* E1 and E2 are edges with the same destination block. Search their
1444 predecessors for common code. If found, redirect control flow from
1445 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1448 try_crossjump_to_edge (int mode
, edge e1
, edge e2
)
1451 basic_block src1
= e1
->src
, src2
= e2
->src
;
1452 basic_block redirect_to
, redirect_from
, to_remove
;
1453 rtx newpos1
, newpos2
;
1456 /* Search backward through forwarder blocks. We don't need to worry
1457 about multiple entry or chained forwarders, as they will be optimized
1458 away. We do this to look past the unconditional jump following a
1459 conditional jump that is required due to the current CFG shape. */
1461 && !src1
->pred
->pred_next
1462 && FORWARDER_BLOCK_P (src1
))
1463 e1
= src1
->pred
, src1
= e1
->src
;
1466 && !src2
->pred
->pred_next
1467 && FORWARDER_BLOCK_P (src2
))
1468 e2
= src2
->pred
, src2
= e2
->src
;
1470 /* Nothing to do if we reach ENTRY, or a common source block. */
1471 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1476 /* Seeing more than 1 forwarder blocks would confuse us later... */
1477 if (FORWARDER_BLOCK_P (e1
->dest
)
1478 && FORWARDER_BLOCK_P (e1
->dest
->succ
->dest
))
1481 if (FORWARDER_BLOCK_P (e2
->dest
)
1482 && FORWARDER_BLOCK_P (e2
->dest
->succ
->dest
))
1485 /* Likewise with dead code (possibly newly created by the other optimizations
1487 if (!src1
->pred
|| !src2
->pred
)
1490 /* Look for the common insn sequence, part the first ... */
1491 if (!outgoing_edges_match (mode
, src1
, src2
))
1494 /* ... and part the second. */
1495 nmatch
= flow_find_cross_jump (mode
, src1
, src2
, &newpos1
, &newpos2
);
1499 #ifndef CASE_DROPS_THROUGH
1500 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1502 If we have tablejumps in the end of SRC1 and SRC2
1503 they have been already compared for equivalence in outgoing_edges_match ()
1504 so replace the references to TABLE1 by references to TABLE2. */
1509 if (tablejump_p (BB_END (src1
), &label1
, &table1
)
1510 && tablejump_p (BB_END (src2
), &label2
, &table2
)
1511 && label1
!= label2
)
1513 replace_label_data rr
;
1516 /* Replace references to LABEL1 with LABEL2. */
1519 rr
.update_label_nuses
= true;
1520 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1522 /* Do not replace the label in SRC1->END because when deleting
1523 a block whose end is a tablejump, the tablejump referenced
1524 from the instruction is deleted too. */
1525 if (insn
!= BB_END (src1
))
1526 for_each_rtx (&insn
, replace_label
, &rr
);
1532 /* Avoid splitting if possible. */
1533 if (newpos2
== BB_HEAD (src2
))
1538 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
1539 src2
->index
, nmatch
);
1540 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1545 "Cross jumping from bb %i to bb %i; %i common insns\n",
1546 src1
->index
, src2
->index
, nmatch
);
1548 redirect_to
->count
+= src1
->count
;
1549 redirect_to
->frequency
+= src1
->frequency
;
1550 /* We may have some registers visible trought the block. */
1551 redirect_to
->flags
|= BB_DIRTY
;
1553 /* Recompute the frequencies and counts of outgoing edges. */
1554 for (s
= redirect_to
->succ
; s
; s
= s
->succ_next
)
1557 basic_block d
= s
->dest
;
1559 if (FORWARDER_BLOCK_P (d
))
1562 for (s2
= src1
->succ
; ; s2
= s2
->succ_next
)
1564 basic_block d2
= s2
->dest
;
1565 if (FORWARDER_BLOCK_P (d2
))
1566 d2
= d2
->succ
->dest
;
1571 s
->count
+= s2
->count
;
1573 /* Take care to update possible forwarder blocks. We verified
1574 that there is no more than one in the chain, so we can't run
1575 into infinite loop. */
1576 if (FORWARDER_BLOCK_P (s
->dest
))
1578 s
->dest
->succ
->count
+= s2
->count
;
1579 s
->dest
->count
+= s2
->count
;
1580 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1583 if (FORWARDER_BLOCK_P (s2
->dest
))
1585 s2
->dest
->succ
->count
-= s2
->count
;
1586 if (s2
->dest
->succ
->count
< 0)
1587 s2
->dest
->succ
->count
= 0;
1588 s2
->dest
->count
-= s2
->count
;
1589 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1590 if (s2
->dest
->frequency
< 0)
1591 s2
->dest
->frequency
= 0;
1592 if (s2
->dest
->count
< 0)
1593 s2
->dest
->count
= 0;
1596 if (!redirect_to
->frequency
&& !src1
->frequency
)
1597 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
1600 = ((s
->probability
* redirect_to
->frequency
+
1601 s2
->probability
* src1
->frequency
)
1602 / (redirect_to
->frequency
+ src1
->frequency
));
1605 update_br_prob_note (redirect_to
);
1607 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1609 /* Skip possible basic block header. */
1610 if (GET_CODE (newpos1
) == CODE_LABEL
)
1611 newpos1
= NEXT_INSN (newpos1
);
1613 if (GET_CODE (newpos1
) == NOTE
)
1614 newpos1
= NEXT_INSN (newpos1
);
1616 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
1617 to_remove
= redirect_from
->succ
->dest
;
1619 redirect_edge_and_branch_force (redirect_from
->succ
, redirect_to
);
1620 delete_basic_block (to_remove
);
1622 update_forwarder_flag (redirect_from
);
1627 /* Search the predecessors of BB for common insn sequences. When found,
1628 share code between them by redirecting control flow. Return true if
1629 any changes made. */
1632 try_crossjump_bb (int mode
, basic_block bb
)
1634 edge e
, e2
, nexte2
, nexte
, fallthru
;
1638 /* Nothing to do if there is not at least two incoming edges. */
1639 if (!bb
->pred
|| !bb
->pred
->pred_next
)
1642 /* It is always cheapest to redirect a block that ends in a branch to
1643 a block that falls through into BB, as that adds no branches to the
1644 program. We'll try that combination first. */
1646 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
1647 for (e
= bb
->pred
; e
; e
= e
->pred_next
, n
++)
1649 if (e
->flags
& EDGE_FALLTHRU
)
1656 for (e
= bb
->pred
; e
; e
= nexte
)
1658 nexte
= e
->pred_next
;
1660 /* As noted above, first try with the fallthru predecessor. */
1663 /* Don't combine the fallthru edge into anything else.
1664 If there is a match, we'll do it the other way around. */
1667 /* If nothing changed since the last attempt, there is nothing
1670 && (!(e
->src
->flags
& BB_DIRTY
)
1671 && !(fallthru
->src
->flags
& BB_DIRTY
)))
1674 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1682 /* Non-obvious work limiting check: Recognize that we're going
1683 to call try_crossjump_bb on every basic block. So if we have
1684 two blocks with lots of outgoing edges (a switch) and they
1685 share lots of common destinations, then we would do the
1686 cross-jump check once for each common destination.
1688 Now, if the blocks actually are cross-jump candidates, then
1689 all of their destinations will be shared. Which means that
1690 we only need check them for cross-jump candidacy once. We
1691 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1692 choosing to do the check from the block for which the edge
1693 in question is the first successor of A. */
1694 if (e
->src
->succ
!= e
)
1697 for (e2
= bb
->pred
; e2
; e2
= nexte2
)
1699 nexte2
= e2
->pred_next
;
1704 /* We've already checked the fallthru edge above. */
1708 /* The "first successor" check above only prevents multiple
1709 checks of crossjump(A,B). In order to prevent redundant
1710 checks of crossjump(B,A), require that A be the block
1711 with the lowest index. */
1712 if (e
->src
->index
> e2
->src
->index
)
1715 /* If nothing changed since the last attempt, there is nothing
1718 && (!(e
->src
->flags
& BB_DIRTY
)
1719 && !(e2
->src
->flags
& BB_DIRTY
)))
1722 if (try_crossjump_to_edge (mode
, e
, e2
))
1734 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1735 instructions etc. Return nonzero if changes were made. */
1738 try_optimize_cfg (int mode
)
1740 bool changed_overall
= false;
1743 basic_block bb
, b
, next
;
1745 if (mode
& CLEANUP_CROSSJUMP
)
1746 add_noreturn_fake_exit_edges ();
1749 update_forwarder_flag (bb
);
1751 if (mode
& (CLEANUP_UPDATE_LIFE
| CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
1754 if (! targetm
.cannot_modify_jumps_p ())
1757 /* Attempt to merge blocks as made possible by edge removal. If
1758 a block has only one successor, and the successor has only
1759 one predecessor, they may be combined. */
1767 "\n\ntry_optimize_cfg iteration %i\n\n",
1770 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
1774 bool changed_here
= false;
1776 /* Delete trivially dead basic blocks. */
1777 while (b
->pred
== NULL
)
1781 fprintf (dump_file
, "Deleting block %i.\n",
1784 delete_basic_block (b
);
1785 if (!(mode
& CLEANUP_CFGLAYOUT
))
1790 /* Remove code labels no longer used. Don't do this
1791 before CALL_PLACEHOLDER is removed, as some branches
1792 may be hidden within. */
1793 if (b
->pred
->pred_next
== NULL
1794 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1795 && !(b
->pred
->flags
& EDGE_COMPLEX
)
1796 && GET_CODE (BB_HEAD (b
)) == CODE_LABEL
1797 && (!(mode
& CLEANUP_PRE_SIBCALL
)
1798 || !tail_recursion_label_p (BB_HEAD (b
)))
1799 /* If the previous block ends with a branch to this
1800 block, we can't delete the label. Normally this
1801 is a condjump that is yet to be simplified, but
1802 if CASE_DROPS_THRU, this can be a tablejump with
1803 some element going to the same place as the
1804 default (fallthru). */
1805 && (b
->pred
->src
== ENTRY_BLOCK_PTR
1806 || GET_CODE (BB_END (b
->pred
->src
)) != JUMP_INSN
1807 || ! label_is_jump_target_p (BB_HEAD (b
),
1808 BB_END (b
->pred
->src
))))
1810 rtx label
= BB_HEAD (b
);
1812 delete_insn_chain (label
, label
);
1813 /* In the case label is undeletable, move it after the
1814 BASIC_BLOCK note. */
1815 if (NOTE_LINE_NUMBER (BB_HEAD (b
)) == NOTE_INSN_DELETED_LABEL
)
1817 rtx bb_note
= NEXT_INSN (BB_HEAD (b
));
1819 reorder_insns_nobb (label
, label
, bb_note
);
1820 BB_HEAD (b
) = bb_note
;
1823 fprintf (dump_file
, "Deleted label in block %i.\n",
1827 /* If we fall through an empty block, we can remove it. */
1828 if (!(mode
& CLEANUP_CFGLAYOUT
)
1829 && b
->pred
->pred_next
== NULL
1830 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1831 && GET_CODE (BB_HEAD (b
)) != CODE_LABEL
1832 && FORWARDER_BLOCK_P (b
)
1833 /* Note that forwarder_block_p true ensures that
1834 there is a successor for this block. */
1835 && (b
->succ
->flags
& EDGE_FALLTHRU
)
1836 && n_basic_blocks
> 1)
1840 "Deleting fallthru block %i.\n",
1843 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
1844 redirect_edge_succ_nodup (b
->pred
, b
->succ
->dest
);
1845 delete_basic_block (b
);
1850 if ((s
= b
->succ
) != NULL
1851 && s
->succ_next
== NULL
1852 && !(s
->flags
& EDGE_COMPLEX
)
1853 && (c
= s
->dest
) != EXIT_BLOCK_PTR
1854 && c
->pred
->pred_next
== NULL
1857 /* When not in cfg_layout mode use code aware of reordering
1858 INSN. This code possibly creates new basic blocks so it
1859 does not fit merge_blocks interface and is kept here in
1860 hope that it will become useless once more of compiler
1861 is transformed to use cfg_layout mode. */
1863 if ((mode
& CLEANUP_CFGLAYOUT
)
1864 && can_merge_blocks_p (b
, c
))
1866 merge_blocks (b
, c
);
1867 update_forwarder_flag (b
);
1868 changed_here
= true;
1870 else if (!(mode
& CLEANUP_CFGLAYOUT
)
1871 /* If the jump insn has side effects,
1872 we can't kill the edge. */
1873 && (GET_CODE (BB_END (b
)) != JUMP_INSN
1874 || (reload_completed
1875 ? simplejump_p (BB_END (b
))
1876 : onlyjump_p (BB_END (b
))))
1877 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
1880 changed_here
= true;
1884 /* Simplify branch over branch. */
1885 if ((mode
& CLEANUP_EXPENSIVE
)
1886 && !(mode
& CLEANUP_CFGLAYOUT
)
1887 && try_simplify_condjump (b
))
1888 changed_here
= true;
1890 /* If B has a single outgoing edge, but uses a
1891 non-trivial jump instruction without side-effects, we
1892 can either delete the jump entirely, or replace it
1893 with a simple unconditional jump. */
1895 && ! b
->succ
->succ_next
1896 && b
->succ
->dest
!= EXIT_BLOCK_PTR
1897 && onlyjump_p (BB_END (b
))
1898 && try_redirect_by_replacing_jump (b
->succ
, b
->succ
->dest
,
1899 (mode
& CLEANUP_CFGLAYOUT
) != 0))
1901 update_forwarder_flag (b
);
1902 changed_here
= true;
1905 /* Simplify branch to branch. */
1906 if (try_forward_edges (mode
, b
))
1907 changed_here
= true;
1909 /* Look for shared code between blocks. */
1910 if ((mode
& CLEANUP_CROSSJUMP
)
1911 && try_crossjump_bb (mode
, b
))
1912 changed_here
= true;
1914 /* Don't get confused by the index shift caused by
1922 if ((mode
& CLEANUP_CROSSJUMP
)
1923 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
1926 #ifdef ENABLE_CHECKING
1928 verify_flow_info ();
1931 changed_overall
|= changed
;
1937 if (mode
& CLEANUP_CROSSJUMP
)
1938 remove_fake_edges ();
1940 clear_aux_for_blocks ();
1942 return changed_overall
;
1945 /* Delete all unreachable basic blocks. */
1948 delete_unreachable_blocks (void)
1950 bool changed
= false;
1951 basic_block b
, next_bb
;
1953 find_unreachable_blocks ();
1955 /* Delete all unreachable basic blocks. */
1957 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
; b
= next_bb
)
1959 next_bb
= b
->next_bb
;
1961 if (!(b
->flags
& BB_REACHABLE
))
1963 delete_basic_block (b
);
1969 tidy_fallthru_edges ();
1973 /* Tidy the CFG by deleting unreachable code and whatnot. */
1976 cleanup_cfg (int mode
)
1978 bool changed
= false;
1980 timevar_push (TV_CLEANUP_CFG
);
1981 if (delete_unreachable_blocks ())
1984 /* We've possibly created trivially dead code. Cleanup it right
1985 now to introduce more opportunities for try_optimize_cfg. */
1986 if (!(mode
& (CLEANUP_NO_INSN_DEL
1987 | CLEANUP_UPDATE_LIFE
| CLEANUP_PRE_SIBCALL
))
1988 && !reload_completed
)
1989 delete_trivially_dead_insns (get_insns(), max_reg_num ());
1994 while (try_optimize_cfg (mode
))
1996 delete_unreachable_blocks (), changed
= true;
1997 if (mode
& CLEANUP_UPDATE_LIFE
)
1999 /* Cleaning up CFG introduces more opportunities for dead code
2000 removal that in turn may introduce more opportunities for
2001 cleaning up the CFG. */
2002 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES
,
2004 | PROP_SCAN_DEAD_CODE
2005 | PROP_KILL_DEAD_CODE
2006 | ((mode
& CLEANUP_LOG_LINKS
)
2007 ? PROP_LOG_LINKS
: 0)))
2010 else if (!(mode
& (CLEANUP_NO_INSN_DEL
| CLEANUP_PRE_SIBCALL
))
2011 && (mode
& CLEANUP_EXPENSIVE
)
2012 && !reload_completed
)
2014 if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
2019 delete_dead_jumptables ();
2022 /* Kill the data we won't maintain. */
2023 free_EXPR_LIST_list (&label_value_list
);
2024 timevar_pop (TV_CLEANUP_CFG
);