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 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 it's
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"
52 /* cleanup_cfg maintains following flags for each basic block. */
56 /* Set if BB is the forwarder block to avoid too many
57 forwarder_block_p calls. */
58 BB_FORWARDER_BLOCK
= 1,
59 BB_NONTHREADABLE_BLOCK
= 2
62 #define BB_FLAGS(BB) (enum bb_flags) (BB)->aux
63 #define BB_SET_FLAG(BB, FLAG) \
64 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG))
65 #define BB_CLEAR_FLAG(BB, FLAG) \
66 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG))
68 #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
70 static bool try_crossjump_to_edge (int, edge
, edge
);
71 static bool try_crossjump_bb (int, basic_block
);
72 static bool outgoing_edges_match (int, basic_block
, basic_block
);
73 static int flow_find_cross_jump (int, basic_block
, basic_block
, rtx
*, rtx
*);
74 static bool insns_match_p (int, rtx
, rtx
);
76 static bool label_is_jump_target_p (rtx
, rtx
);
77 static bool tail_recursion_label_p (rtx
);
78 static void merge_blocks_move_predecessor_nojumps (basic_block
, basic_block
);
79 static void merge_blocks_move_successor_nojumps (basic_block
, basic_block
);
80 static bool try_optimize_cfg (int);
81 static bool try_simplify_condjump (basic_block
);
82 static bool try_forward_edges (int, basic_block
);
83 static edge
thread_jump (int, edge
, basic_block
);
84 static bool mark_effect (rtx
, bitmap
);
85 static void notice_new_block (basic_block
);
86 static void update_forwarder_flag (basic_block
);
87 static int mentions_nonequal_regs (rtx
*, void *);
89 /* Set flags for newly created block. */
92 notice_new_block (basic_block bb
)
97 if (forwarder_block_p (bb
))
98 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
101 /* Recompute forwarder flag after block has been modified. */
104 update_forwarder_flag (basic_block bb
)
106 if (forwarder_block_p (bb
))
107 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
109 BB_CLEAR_FLAG (bb
, BB_FORWARDER_BLOCK
);
112 /* Simplify a conditional jump around an unconditional jump.
113 Return true if something changed. */
116 try_simplify_condjump (basic_block cbranch_block
)
118 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
119 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
122 /* Verify that there are exactly two successors. */
123 if (!cbranch_block
->succ
124 || !cbranch_block
->succ
->succ_next
125 || cbranch_block
->succ
->succ_next
->succ_next
)
128 /* Verify that we've got a normal conditional branch at the end
130 cbranch_insn
= cbranch_block
->end
;
131 if (!any_condjump_p (cbranch_insn
))
134 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
135 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
137 /* The next block must not have multiple predecessors, must not
138 be the last block in the function, and must contain just the
139 unconditional jump. */
140 jump_block
= cbranch_fallthru_edge
->dest
;
141 if (jump_block
->pred
->pred_next
142 || jump_block
->next_bb
== EXIT_BLOCK_PTR
143 || !FORWARDER_BLOCK_P (jump_block
))
145 jump_dest_block
= jump_block
->succ
->dest
;
147 /* The conditional branch must target the block after the
148 unconditional branch. */
149 cbranch_dest_block
= cbranch_jump_edge
->dest
;
151 if (!can_fallthru (jump_block
, cbranch_dest_block
))
154 /* Invert the conditional branch. */
155 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
159 fprintf (rtl_dump_file
, "Simplifying condjump %i around jump %i\n",
160 INSN_UID (cbranch_insn
), INSN_UID (jump_block
->end
));
162 /* Success. Update the CFG to match. Note that after this point
163 the edge variable names appear backwards; the redirection is done
164 this way to preserve edge profile data. */
165 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
167 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
169 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
170 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
171 update_br_prob_note (cbranch_block
);
173 /* Delete the block with the unconditional jump, and clean up the mess. */
174 delete_block (jump_block
);
175 tidy_fallthru_edge (cbranch_jump_edge
, cbranch_block
, cbranch_dest_block
);
180 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
181 on register. Used by jump threading. */
184 mark_effect (rtx exp
, regset nonequal
)
188 switch (GET_CODE (exp
))
190 /* In case we do clobber the register, mark it as equal, as we know the
191 value is dead so it don't have to match. */
193 if (REG_P (XEXP (exp
, 0)))
195 dest
= XEXP (exp
, 0);
196 regno
= REGNO (dest
);
197 CLEAR_REGNO_REG_SET (nonequal
, regno
);
198 if (regno
< FIRST_PSEUDO_REGISTER
)
200 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
202 CLEAR_REGNO_REG_SET (nonequal
, regno
+ n
);
208 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
210 dest
= SET_DEST (exp
);
215 regno
= REGNO (dest
);
216 SET_REGNO_REG_SET (nonequal
, regno
);
217 if (regno
< FIRST_PSEUDO_REGISTER
)
219 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
221 SET_REGNO_REG_SET (nonequal
, regno
+ n
);
230 /* Return nonzero if X is an register set in regset DATA.
231 Called via for_each_rtx. */
233 mentions_nonequal_regs (rtx
*x
, void *data
)
235 regset nonequal
= (regset
) data
;
241 if (REGNO_REG_SET_P (nonequal
, regno
))
243 if (regno
< FIRST_PSEUDO_REGISTER
)
245 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (*x
));
247 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
253 /* Attempt to prove that the basic block B will have no side effects and
254 always continues in the same edge if reached via E. Return the edge
255 if exist, NULL otherwise. */
258 thread_jump (int mode
, edge e
, basic_block b
)
260 rtx set1
, set2
, cond1
, cond2
, insn
;
261 enum rtx_code code1
, code2
, reversed_code2
;
262 bool reverse1
= false;
267 if (BB_FLAGS (b
) & BB_NONTHREADABLE_BLOCK
)
270 /* At the moment, we do handle only conditional jumps, but later we may
271 want to extend this code to tablejumps and others. */
272 if (!e
->src
->succ
->succ_next
|| e
->src
->succ
->succ_next
->succ_next
)
274 if (!b
->succ
|| !b
->succ
->succ_next
|| b
->succ
->succ_next
->succ_next
)
276 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
280 /* Second branch must end with onlyjump, as we will eliminate the jump. */
281 if (!any_condjump_p (e
->src
->end
))
284 if (!any_condjump_p (b
->end
) || !onlyjump_p (b
->end
))
286 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
290 set1
= pc_set (e
->src
->end
);
291 set2
= pc_set (b
->end
);
292 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
293 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
296 cond1
= XEXP (SET_SRC (set1
), 0);
297 cond2
= XEXP (SET_SRC (set2
), 0);
299 code1
= reversed_comparison_code (cond1
, e
->src
->end
);
301 code1
= GET_CODE (cond1
);
303 code2
= GET_CODE (cond2
);
304 reversed_code2
= reversed_comparison_code (cond2
, b
->end
);
306 if (!comparison_dominates_p (code1
, code2
)
307 && !comparison_dominates_p (code1
, reversed_code2
))
310 /* Ensure that the comparison operators are equivalent.
311 ??? This is far too pessimistic. We should allow swapped operands,
312 different CCmodes, or for example comparisons for interval, that
313 dominate even when operands are not equivalent. */
314 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
315 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
318 /* Short circuit cases where block B contains some side effects, as we can't
320 for (insn
= NEXT_INSN (b
->head
); insn
!= NEXT_INSN (b
->end
);
321 insn
= NEXT_INSN (insn
))
322 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
324 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
330 /* First process all values computed in the source basic block. */
331 for (insn
= NEXT_INSN (e
->src
->head
); insn
!= NEXT_INSN (e
->src
->end
);
332 insn
= NEXT_INSN (insn
))
334 cselib_process_insn (insn
);
336 nonequal
= BITMAP_XMALLOC();
337 CLEAR_REG_SET (nonequal
);
339 /* Now assume that we've continued by the edge E to B and continue
340 processing as if it were same basic block.
341 Our goal is to prove that whole block is an NOOP. */
343 for (insn
= NEXT_INSN (b
->head
); insn
!= NEXT_INSN (b
->end
) && !failed
;
344 insn
= NEXT_INSN (insn
))
348 rtx pat
= PATTERN (insn
);
350 if (GET_CODE (pat
) == PARALLEL
)
352 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
353 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
356 failed
|= mark_effect (pat
, nonequal
);
359 cselib_process_insn (insn
);
362 /* Later we should clear nonequal of dead registers. So far we don't
363 have life information in cfg_cleanup. */
366 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
370 /* cond2 must not mention any register that is not equal to the
372 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
375 /* In case liveness information is available, we need to prove equivalence
376 only of the live values. */
377 if (mode
& CLEANUP_UPDATE_LIFE
)
378 AND_REG_SET (nonequal
, b
->global_live_at_end
);
380 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, goto failed_exit
;);
382 BITMAP_XFREE (nonequal
);
384 if ((comparison_dominates_p (code1
, code2
) != 0)
385 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
386 return BRANCH_EDGE (b
);
388 return FALLTHRU_EDGE (b
);
391 BITMAP_XFREE (nonequal
);
396 /* Attempt to forward edges leaving basic block B.
397 Return true if successful. */
400 try_forward_edges (int mode
, basic_block b
)
402 bool changed
= false;
403 edge e
, next
, *threaded_edges
= NULL
;
405 for (e
= b
->succ
; e
; e
= next
)
407 basic_block target
, first
;
409 bool threaded
= false;
410 int nthreaded_edges
= 0;
414 /* Skip complex edges because we don't know how to update them.
416 Still handle fallthru edges, as we can succeed to forward fallthru
417 edge to the same place as the branch edge of conditional branch
418 and turn conditional branch to an unconditional branch. */
419 if (e
->flags
& EDGE_COMPLEX
)
422 target
= first
= e
->dest
;
425 while (counter
< n_basic_blocks
)
427 basic_block new_target
= NULL
;
428 bool new_target_threaded
= false;
430 if (FORWARDER_BLOCK_P (target
)
431 && target
->succ
->dest
!= EXIT_BLOCK_PTR
)
433 /* Bypass trivial infinite loops. */
434 if (target
== target
->succ
->dest
)
435 counter
= n_basic_blocks
;
436 new_target
= target
->succ
->dest
;
439 /* Allow to thread only over one edge at time to simplify updating
441 else if (mode
& CLEANUP_THREADING
)
443 edge t
= thread_jump (mode
, e
, target
);
447 threaded_edges
= xmalloc (sizeof (*threaded_edges
)
453 /* Detect an infinite loop across blocks not
454 including the start block. */
455 for (i
= 0; i
< nthreaded_edges
; ++i
)
456 if (threaded_edges
[i
] == t
)
458 if (i
< nthreaded_edges
)
460 counter
= n_basic_blocks
;
465 /* Detect an infinite loop across the start block. */
469 if (nthreaded_edges
>= n_basic_blocks
)
471 threaded_edges
[nthreaded_edges
++] = t
;
473 new_target
= t
->dest
;
474 new_target_threaded
= true;
481 /* Avoid killing of loop pre-headers, as it is the place loop
482 optimizer wants to hoist code to.
484 For fallthru forwarders, the LOOP_BEG note must appear between
485 the header of block and CODE_LABEL of the loop, for non forwarders
486 it must appear before the JUMP_INSN. */
487 if ((mode
& CLEANUP_PRE_LOOP
) && optimize
)
489 rtx insn
= (target
->succ
->flags
& EDGE_FALLTHRU
490 ? target
->head
: prev_nonnote_insn (target
->end
));
492 if (GET_CODE (insn
) != NOTE
)
493 insn
= NEXT_INSN (insn
);
495 for (; insn
&& GET_CODE (insn
) != CODE_LABEL
&& !INSN_P (insn
);
496 insn
= NEXT_INSN (insn
))
497 if (GET_CODE (insn
) == NOTE
498 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
501 if (GET_CODE (insn
) == NOTE
)
504 /* Do not clean up branches to just past the end of a loop
505 at this time; it can mess up the loop optimizer's
506 recognition of some patterns. */
508 insn
= PREV_INSN (target
->head
);
509 if (insn
&& GET_CODE (insn
) == NOTE
510 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
516 threaded
|= new_target_threaded
;
519 if (counter
>= n_basic_blocks
)
522 fprintf (rtl_dump_file
, "Infinite loop in BB %i.\n",
525 else if (target
== first
)
526 ; /* We didn't do anything. */
529 /* Save the values now, as the edge may get removed. */
530 gcov_type edge_count
= e
->count
;
531 int edge_probability
= e
->probability
;
535 /* Don't force if target is exit block. */
536 if (threaded
&& target
!= EXIT_BLOCK_PTR
)
538 notice_new_block (redirect_edge_and_branch_force (e
, target
));
540 fprintf (rtl_dump_file
, "Conditionals threaded.\n");
542 else if (!redirect_edge_and_branch (e
, target
))
545 fprintf (rtl_dump_file
,
546 "Forwarding edge %i->%i to %i failed.\n",
547 b
->index
, e
->dest
->index
, target
->index
);
551 /* We successfully forwarded the edge. Now update profile
552 data: for each edge we traversed in the chain, remove
553 the original edge's execution count. */
554 edge_frequency
= ((edge_probability
* b
->frequency
555 + REG_BR_PROB_BASE
/ 2)
558 if (!FORWARDER_BLOCK_P (b
) && forwarder_block_p (b
))
559 BB_SET_FLAG (b
, BB_FORWARDER_BLOCK
);
565 first
->count
-= edge_count
;
566 if (first
->count
< 0)
568 first
->frequency
-= edge_frequency
;
569 if (first
->frequency
< 0)
570 first
->frequency
= 0;
571 if (first
->succ
->succ_next
)
575 if (n
>= nthreaded_edges
)
577 t
= threaded_edges
[n
++];
580 if (first
->frequency
)
581 prob
= edge_frequency
* REG_BR_PROB_BASE
/ first
->frequency
;
584 if (prob
> t
->probability
)
585 prob
= t
->probability
;
586 t
->probability
-= prob
;
587 prob
= REG_BR_PROB_BASE
- prob
;
590 first
->succ
->probability
= REG_BR_PROB_BASE
;
591 first
->succ
->succ_next
->probability
= 0;
594 for (e
= first
->succ
; e
; e
= e
->succ_next
)
595 e
->probability
= ((e
->probability
* REG_BR_PROB_BASE
)
597 update_br_prob_note (first
);
601 /* It is possible that as the result of
602 threading we've removed edge as it is
603 threaded to the fallthru edge. Avoid
604 getting out of sync. */
605 if (n
< nthreaded_edges
606 && first
== threaded_edges
[n
]->src
)
611 t
->count
-= edge_count
;
616 while (first
!= target
);
623 free (threaded_edges
);
627 /* Return true if LABEL is a target of JUMP_INSN. This applies only
628 to non-complex jumps. That is, direct unconditional, conditional,
629 and tablejumps, but not computed jumps or returns. It also does
630 not apply to the fallthru case of a conditional jump. */
633 label_is_jump_target_p (rtx label
, rtx jump_insn
)
635 rtx tmp
= JUMP_LABEL (jump_insn
);
640 if (tablejump_p (jump_insn
, NULL
, &tmp
))
642 rtvec vec
= XVEC (tmp
, GET_CODE (tmp
) == ADDR_DIFF_VEC
);
643 int i
, veclen
= GET_NUM_ELEM (vec
);
645 for (i
= 0; i
< veclen
; ++i
)
646 if (XEXP (RTVEC_ELT (vec
, i
), 0) == label
)
653 /* Return true if LABEL is used for tail recursion. */
656 tail_recursion_label_p (rtx label
)
660 for (x
= tail_recursion_label_list
; x
; x
= XEXP (x
, 1))
661 if (label
== XEXP (x
, 0))
667 /* Blocks A and B are to be merged into a single block. A has no incoming
668 fallthru edge, so it can be moved before B without adding or modifying
669 any jumps (aside from the jump from A to B). */
672 merge_blocks_move_predecessor_nojumps (basic_block a
, basic_block b
)
676 barrier
= next_nonnote_insn (a
->end
);
677 if (GET_CODE (barrier
) != BARRIER
)
679 delete_insn (barrier
);
681 /* Move block and loop notes out of the chain so that we do not
684 ??? A better solution would be to squeeze out all the non-nested notes
685 and adjust the block trees appropriately. Even better would be to have
686 a tighter connection between block trees and rtl so that this is not
688 if (squeeze_notes (&a
->head
, &a
->end
))
691 /* Scramble the insn chain. */
692 if (a
->end
!= PREV_INSN (b
->head
))
693 reorder_insns_nobb (a
->head
, a
->end
, PREV_INSN (b
->head
));
694 a
->flags
|= BB_DIRTY
;
697 fprintf (rtl_dump_file
, "Moved block %d before %d and merged.\n",
700 /* Swap the records for the two blocks around. */
703 link_block (a
, b
->prev_bb
);
705 /* Now blocks A and B are contiguous. Merge them. */
709 /* Blocks A and B are to be merged into a single block. B has no outgoing
710 fallthru edge, so it can be moved after A without adding or modifying
711 any jumps (aside from the jump from A to B). */
714 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
716 rtx barrier
, real_b_end
;
719 barrier
= NEXT_INSN (b
->end
);
721 /* Recognize a jump table following block B. */
723 && GET_CODE (barrier
) == CODE_LABEL
724 && NEXT_INSN (barrier
)
725 && GET_CODE (NEXT_INSN (barrier
)) == JUMP_INSN
726 && (GET_CODE (PATTERN (NEXT_INSN (barrier
))) == ADDR_VEC
727 || GET_CODE (PATTERN (NEXT_INSN (barrier
))) == ADDR_DIFF_VEC
))
729 /* Temporarily add the table jump insn to b, so that it will also
730 be moved to the correct location. */
731 b
->end
= NEXT_INSN (barrier
);
732 barrier
= NEXT_INSN (b
->end
);
735 /* There had better have been a barrier there. Delete it. */
736 if (barrier
&& GET_CODE (barrier
) == BARRIER
)
737 delete_insn (barrier
);
739 /* Move block and loop notes out of the chain so that we do not
742 ??? A better solution would be to squeeze out all the non-nested notes
743 and adjust the block trees appropriately. Even better would be to have
744 a tighter connection between block trees and rtl so that this is not
746 if (squeeze_notes (&b
->head
, &b
->end
))
749 /* Scramble the insn chain. */
750 reorder_insns_nobb (b
->head
, b
->end
, a
->end
);
752 /* Restore the real end of b. */
756 fprintf (rtl_dump_file
, "Moved block %d after %d and merged.\n",
759 /* Now blocks A and B are contiguous. Merge them. */
763 /* Attempt to merge basic blocks that are potentially non-adjacent.
764 Return NULL iff the attempt failed, otherwise return basic block
765 where cleanup_cfg should continue. Because the merging commonly
766 moves basic block away or introduces another optimization
767 possibility, return basic block just before B so cleanup_cfg don't
770 It may be good idea to return basic block before C in the case
771 C has been moved after B and originally appeared earlier in the
772 insn sequence, but we have no information available about the
773 relative ordering of these two. Hopefully it is not too common. */
776 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
779 /* If C has a tail recursion label, do not merge. There is no
780 edge recorded from the call_placeholder back to this label, as
781 that would make optimize_sibling_and_tail_recursive_calls more
782 complex for no gain. */
783 if ((mode
& CLEANUP_PRE_SIBCALL
)
784 && GET_CODE (c
->head
) == CODE_LABEL
785 && tail_recursion_label_p (c
->head
))
788 /* If B has a fallthru edge to C, no need to move anything. */
789 if (e
->flags
& EDGE_FALLTHRU
)
791 int b_index
= b
->index
, c_index
= c
->index
;
793 update_forwarder_flag (b
);
796 fprintf (rtl_dump_file
, "Merged %d and %d without moving.\n",
799 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
802 /* Otherwise we will need to move code around. Do that only if expensive
803 transformations are allowed. */
804 else if (mode
& CLEANUP_EXPENSIVE
)
806 edge tmp_edge
, b_fallthru_edge
;
807 bool c_has_outgoing_fallthru
;
808 bool b_has_incoming_fallthru
;
810 /* Avoid overactive code motion, as the forwarder blocks should be
811 eliminated by edge redirection instead. One exception might have
812 been if B is a forwarder block and C has no fallthru edge, but
813 that should be cleaned up by bb-reorder instead. */
814 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
817 /* We must make sure to not munge nesting of lexical blocks,
818 and loop notes. This is done by squeezing out all the notes
819 and leaving them there to lie. Not ideal, but functional. */
821 for (tmp_edge
= c
->succ
; tmp_edge
; tmp_edge
= tmp_edge
->succ_next
)
822 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
825 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
827 for (tmp_edge
= b
->pred
; tmp_edge
; tmp_edge
= tmp_edge
->pred_next
)
828 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
831 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
832 b_fallthru_edge
= tmp_edge
;
835 next
= next
->prev_bb
;
837 /* Otherwise, we're going to try to move C after B. If C does
838 not have an outgoing fallthru, then it can be moved
839 immediately after B without introducing or modifying jumps. */
840 if (! c_has_outgoing_fallthru
)
842 merge_blocks_move_successor_nojumps (b
, c
);
843 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
846 /* If B does not have an incoming fallthru, then it can be moved
847 immediately before C without introducing or modifying jumps.
848 C cannot be the first block, so we do not have to worry about
849 accessing a non-existent block. */
851 if (b_has_incoming_fallthru
)
855 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
857 bb
= force_nonfallthru (b_fallthru_edge
);
859 notice_new_block (bb
);
862 merge_blocks_move_predecessor_nojumps (b
, c
);
863 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
870 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
873 insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
877 /* Verify that I1 and I2 are equivalent. */
878 if (GET_CODE (i1
) != GET_CODE (i2
))
884 if (GET_CODE (p1
) != GET_CODE (p2
))
887 /* If this is a CALL_INSN, compare register usage information.
888 If we don't check this on stack register machines, the two
889 CALL_INSNs might be merged leaving reg-stack.c with mismatching
890 numbers of stack registers in the same basic block.
891 If we don't check this on machines with delay slots, a delay slot may
892 be filled that clobbers a parameter expected by the subroutine.
894 ??? We take the simple route for now and assume that if they're
895 equal, they were constructed identically. */
897 if (GET_CODE (i1
) == CALL_INSN
898 && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
899 CALL_INSN_FUNCTION_USAGE (i2
))
900 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
)))
904 /* If cross_jump_death_matters is not 0, the insn's mode
905 indicates whether or not the insn contains any stack-like
908 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
910 /* If register stack conversion has already been done, then
911 death notes must also be compared before it is certain that
912 the two instruction streams match. */
915 HARD_REG_SET i1_regset
, i2_regset
;
917 CLEAR_HARD_REG_SET (i1_regset
);
918 CLEAR_HARD_REG_SET (i2_regset
);
920 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
921 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
922 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
924 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
925 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
926 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
928 GO_IF_HARD_REG_EQUAL (i1_regset
, i2_regset
, done
);
938 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
941 /* Do not do EQUIV substitution after reload. First, we're undoing the
942 work of reload_cse. Second, we may be undoing the work of the post-
943 reload splitting pass. */
944 /* ??? Possibly add a new phase switch variable that can be used by
945 targets to disallow the troublesome insns after splitting. */
946 if (!reload_completed
)
948 /* The following code helps take care of G++ cleanups. */
949 rtx equiv1
= find_reg_equal_equiv_note (i1
);
950 rtx equiv2
= find_reg_equal_equiv_note (i2
);
953 /* If the equivalences are not to a constant, they may
954 reference pseudos that no longer exist, so we can't
956 && (! reload_completed
957 || (CONSTANT_P (XEXP (equiv1
, 0))
958 && rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))))
960 rtx s1
= single_set (i1
);
961 rtx s2
= single_set (i2
);
962 if (s1
!= 0 && s2
!= 0
963 && rtx_renumbered_equal_p (SET_DEST (s1
), SET_DEST (s2
)))
965 validate_change (i1
, &SET_SRC (s1
), XEXP (equiv1
, 0), 1);
966 validate_change (i2
, &SET_SRC (s2
), XEXP (equiv2
, 0), 1);
967 if (! rtx_renumbered_equal_p (p1
, p2
))
969 else if (apply_change_group ())
978 /* Look through the insns at the end of BB1 and BB2 and find the longest
979 sequence that are equivalent. Store the first insns for that sequence
980 in *F1 and *F2 and return the sequence length.
982 To simplify callers of this function, if the blocks match exactly,
983 store the head of the blocks in *F1 and *F2. */
986 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED
, basic_block bb1
,
987 basic_block bb2
, rtx
*f1
, rtx
*f2
)
989 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
992 /* Skip simple jumps at the end of the blocks. Complex jumps still
993 need to be compared for equivalence, which we'll do below. */
996 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
998 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1001 i1
= PREV_INSN (i1
);
1006 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1009 /* Count everything except for unconditional jump as insn. */
1010 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1012 i2
= PREV_INSN (i2
);
1018 while (!INSN_P (i1
) && i1
!= bb1
->head
)
1019 i1
= PREV_INSN (i1
);
1021 while (!INSN_P (i2
) && i2
!= bb2
->head
)
1022 i2
= PREV_INSN (i2
);
1024 if (i1
== bb1
->head
|| i2
== bb2
->head
)
1027 if (!insns_match_p (mode
, i1
, i2
))
1030 /* Don't begin a cross-jump with a NOTE insn. */
1033 /* If the merged insns have different REG_EQUAL notes, then
1035 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1036 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1038 if (equiv1
&& !equiv2
)
1039 remove_note (i1
, equiv1
);
1040 else if (!equiv1
&& equiv2
)
1041 remove_note (i2
, equiv2
);
1042 else if (equiv1
&& equiv2
1043 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1045 remove_note (i1
, equiv1
);
1046 remove_note (i2
, equiv2
);
1049 afterlast1
= last1
, afterlast2
= last2
;
1050 last1
= i1
, last2
= i2
;
1054 i1
= PREV_INSN (i1
);
1055 i2
= PREV_INSN (i2
);
1059 /* Don't allow the insn after a compare to be shared by
1060 cross-jumping unless the compare is also shared. */
1061 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1062 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
1065 /* Include preceding notes and labels in the cross-jump. One,
1066 this may bring us to the head of the blocks as requested above.
1067 Two, it keeps line number notes as matched as may be. */
1070 while (last1
!= bb1
->head
&& !INSN_P (PREV_INSN (last1
)))
1071 last1
= PREV_INSN (last1
);
1073 if (last1
!= bb1
->head
&& GET_CODE (PREV_INSN (last1
)) == CODE_LABEL
)
1074 last1
= PREV_INSN (last1
);
1076 while (last2
!= bb2
->head
&& !INSN_P (PREV_INSN (last2
)))
1077 last2
= PREV_INSN (last2
);
1079 if (last2
!= bb2
->head
&& GET_CODE (PREV_INSN (last2
)) == CODE_LABEL
)
1080 last2
= PREV_INSN (last2
);
1089 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1090 the branch instruction. This means that if we commonize the control
1091 flow before end of the basic block, the semantic remains unchanged.
1093 We may assume that there exists one edge with a common destination. */
1096 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1098 int nehedges1
= 0, nehedges2
= 0;
1099 edge fallthru1
= 0, fallthru2
= 0;
1102 /* If BB1 has only one successor, we may be looking at either an
1103 unconditional jump, or a fake edge to exit. */
1104 if (bb1
->succ
&& !bb1
->succ
->succ_next
1105 && (bb1
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1106 && (GET_CODE (bb1
->end
) != JUMP_INSN
|| simplejump_p (bb1
->end
)))
1107 return (bb2
->succ
&& !bb2
->succ
->succ_next
1108 && (bb2
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1109 && (GET_CODE (bb2
->end
) != JUMP_INSN
|| simplejump_p (bb2
->end
)));
1111 /* Match conditional jumps - this may get tricky when fallthru and branch
1112 edges are crossed. */
1114 && bb1
->succ
->succ_next
1115 && !bb1
->succ
->succ_next
->succ_next
1116 && any_condjump_p (bb1
->end
)
1117 && onlyjump_p (bb1
->end
))
1119 edge b1
, f1
, b2
, f2
;
1120 bool reverse
, match
;
1121 rtx set1
, set2
, cond1
, cond2
;
1122 enum rtx_code code1
, code2
;
1125 || !bb2
->succ
->succ_next
1126 || bb2
->succ
->succ_next
->succ_next
1127 || !any_condjump_p (bb2
->end
)
1128 || !onlyjump_p (bb2
->end
))
1131 b1
= BRANCH_EDGE (bb1
);
1132 b2
= BRANCH_EDGE (bb2
);
1133 f1
= FALLTHRU_EDGE (bb1
);
1134 f2
= FALLTHRU_EDGE (bb2
);
1136 /* Get around possible forwarders on fallthru edges. Other cases
1137 should be optimized out already. */
1138 if (FORWARDER_BLOCK_P (f1
->dest
))
1139 f1
= f1
->dest
->succ
;
1141 if (FORWARDER_BLOCK_P (f2
->dest
))
1142 f2
= f2
->dest
->succ
;
1144 /* To simplify use of this function, return false if there are
1145 unneeded forwarder blocks. These will get eliminated later
1146 during cleanup_cfg. */
1147 if (FORWARDER_BLOCK_P (f1
->dest
)
1148 || FORWARDER_BLOCK_P (f2
->dest
)
1149 || FORWARDER_BLOCK_P (b1
->dest
)
1150 || FORWARDER_BLOCK_P (b2
->dest
))
1153 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1155 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1160 set1
= pc_set (bb1
->end
);
1161 set2
= pc_set (bb2
->end
);
1162 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1163 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1166 cond1
= XEXP (SET_SRC (set1
), 0);
1167 cond2
= XEXP (SET_SRC (set2
), 0);
1168 code1
= GET_CODE (cond1
);
1170 code2
= reversed_comparison_code (cond2
, bb2
->end
);
1172 code2
= GET_CODE (cond2
);
1174 if (code2
== UNKNOWN
)
1177 /* Verify codes and operands match. */
1178 match
= ((code1
== code2
1179 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1180 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1181 || (code1
== swap_condition (code2
)
1182 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1184 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1187 /* If we return true, we will join the blocks. Which means that
1188 we will only have one branch prediction bit to work with. Thus
1189 we require the existing branches to have probabilities that are
1193 && maybe_hot_bb_p (bb1
)
1194 && maybe_hot_bb_p (bb2
))
1198 if (b1
->dest
== b2
->dest
)
1199 prob2
= b2
->probability
;
1201 /* Do not use f2 probability as f2 may be forwarded. */
1202 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1204 /* Fail if the difference in probabilities is greater than 50%.
1205 This rules out two well-predicted branches with opposite
1207 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1210 fprintf (rtl_dump_file
,
1211 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1212 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1218 if (rtl_dump_file
&& match
)
1219 fprintf (rtl_dump_file
, "Conditionals in bb %i and %i match.\n",
1220 bb1
->index
, bb2
->index
);
1225 /* Generic case - we are seeing a computed jump, table jump or trapping
1228 #ifndef CASE_DROPS_THROUGH
1229 /* Check whether there are tablejumps in the end of BB1 and BB2.
1230 Return true if they are identical. */
1235 if (tablejump_p (bb1
->end
, &label1
, &table1
)
1236 && tablejump_p (bb2
->end
, &label2
, &table2
)
1237 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1239 /* The labels should never be the same rtx. If they really are same
1240 the jump tables are same too. So disable crossjumping of blocks BB1
1241 and BB2 because when deleting the common insns in the end of BB1
1242 by delete_block () the jump table would be deleted too. */
1243 /* If LABEL2 is referenced in BB1->END do not do anything
1244 because we would loose information when replacing
1245 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1246 if (label1
!= label2
&& !rtx_referenced_p (label2
, bb1
->end
))
1248 /* Set IDENTICAL to true when the tables are identical. */
1249 bool identical
= false;
1252 p1
= PATTERN (table1
);
1253 p2
= PATTERN (table2
);
1254 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1258 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1259 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1260 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1261 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1266 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1267 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1273 replace_label_data rr
;
1276 /* Temporarily replace references to LABEL1 with LABEL2
1277 in BB1->END so that we could compare the instructions. */
1280 rr
.update_label_nuses
= false;
1281 for_each_rtx (&bb1
->end
, replace_label
, &rr
);
1283 match
= insns_match_p (mode
, bb1
->end
, bb2
->end
);
1284 if (rtl_dump_file
&& match
)
1285 fprintf (rtl_dump_file
,
1286 "Tablejumps in bb %i and %i match.\n",
1287 bb1
->index
, bb2
->index
);
1289 /* Set the original label in BB1->END because when deleting
1290 a block whose end is a tablejump, the tablejump referenced
1291 from the instruction is deleted too. */
1294 for_each_rtx (&bb1
->end
, replace_label
, &rr
);
1304 /* First ensure that the instructions match. There may be many outgoing
1305 edges so this test is generally cheaper. */
1306 if (!insns_match_p (mode
, bb1
->end
, bb2
->end
))
1309 /* Search the outgoing edges, ensure that the counts do match, find possible
1310 fallthru and exception handling edges since these needs more
1312 for (e1
= bb1
->succ
, e2
= bb2
->succ
; e1
&& e2
;
1313 e1
= e1
->succ_next
, e2
= e2
->succ_next
)
1315 if (e1
->flags
& EDGE_EH
)
1318 if (e2
->flags
& EDGE_EH
)
1321 if (e1
->flags
& EDGE_FALLTHRU
)
1323 if (e2
->flags
& EDGE_FALLTHRU
)
1327 /* If number of edges of various types does not match, fail. */
1329 || nehedges1
!= nehedges2
1330 || (fallthru1
!= 0) != (fallthru2
!= 0))
1333 /* fallthru edges must be forwarded to the same destination. */
1336 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1337 ? fallthru1
->dest
->succ
->dest
: fallthru1
->dest
);
1338 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1339 ? fallthru2
->dest
->succ
->dest
: fallthru2
->dest
);
1345 /* In case we do have EH edges, ensure we are in the same region. */
1348 rtx n1
= find_reg_note (bb1
->end
, REG_EH_REGION
, 0);
1349 rtx n2
= find_reg_note (bb2
->end
, REG_EH_REGION
, 0);
1351 if (XEXP (n1
, 0) != XEXP (n2
, 0))
1355 /* We don't need to match the rest of edges as above checks should be enough
1356 to ensure that they are equivalent. */
1360 /* E1 and E2 are edges with the same destination block. Search their
1361 predecessors for common code. If found, redirect control flow from
1362 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1365 try_crossjump_to_edge (int mode
, edge e1
, edge e2
)
1368 basic_block src1
= e1
->src
, src2
= e2
->src
;
1369 basic_block redirect_to
, redirect_from
, to_remove
;
1370 rtx newpos1
, newpos2
;
1373 /* Search backward through forwarder blocks. We don't need to worry
1374 about multiple entry or chained forwarders, as they will be optimized
1375 away. We do this to look past the unconditional jump following a
1376 conditional jump that is required due to the current CFG shape. */
1378 && !src1
->pred
->pred_next
1379 && FORWARDER_BLOCK_P (src1
))
1380 e1
= src1
->pred
, src1
= e1
->src
;
1383 && !src2
->pred
->pred_next
1384 && FORWARDER_BLOCK_P (src2
))
1385 e2
= src2
->pred
, src2
= e2
->src
;
1387 /* Nothing to do if we reach ENTRY, or a common source block. */
1388 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1393 /* Seeing more than 1 forwarder blocks would confuse us later... */
1394 if (FORWARDER_BLOCK_P (e1
->dest
)
1395 && FORWARDER_BLOCK_P (e1
->dest
->succ
->dest
))
1398 if (FORWARDER_BLOCK_P (e2
->dest
)
1399 && FORWARDER_BLOCK_P (e2
->dest
->succ
->dest
))
1402 /* Likewise with dead code (possibly newly created by the other optimizations
1404 if (!src1
->pred
|| !src2
->pred
)
1407 /* Look for the common insn sequence, part the first ... */
1408 if (!outgoing_edges_match (mode
, src1
, src2
))
1411 /* ... and part the second. */
1412 nmatch
= flow_find_cross_jump (mode
, src1
, src2
, &newpos1
, &newpos2
);
1416 #ifndef CASE_DROPS_THROUGH
1417 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1419 If we have tablejumps in the end of SRC1 and SRC2
1420 they have been already compared for equivalence in outgoing_edges_match ()
1421 so replace the references to TABLE1 by references to TABLE2. */
1426 if (tablejump_p (src1
->end
, &label1
, &table1
)
1427 && tablejump_p (src2
->end
, &label2
, &table2
)
1428 && label1
!= label2
)
1430 replace_label_data rr
;
1433 /* Replace references to LABEL1 with LABEL2. */
1436 rr
.update_label_nuses
= true;
1437 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1439 /* Do not replace the label in SRC1->END because when deleting
1440 a block whose end is a tablejump, the tablejump referenced
1441 from the instruction is deleted too. */
1442 if (insn
!= src1
->end
)
1443 for_each_rtx (&insn
, replace_label
, &rr
);
1449 /* Avoid splitting if possible. */
1450 if (newpos2
== src2
->head
)
1455 fprintf (rtl_dump_file
, "Splitting bb %i before %i insns\n",
1456 src2
->index
, nmatch
);
1457 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1461 fprintf (rtl_dump_file
,
1462 "Cross jumping from bb %i to bb %i; %i common insns\n",
1463 src1
->index
, src2
->index
, nmatch
);
1465 redirect_to
->count
+= src1
->count
;
1466 redirect_to
->frequency
+= src1
->frequency
;
1467 /* We may have some registers visible trought the block. */
1468 redirect_to
->flags
|= BB_DIRTY
;
1470 /* Recompute the frequencies and counts of outgoing edges. */
1471 for (s
= redirect_to
->succ
; s
; s
= s
->succ_next
)
1474 basic_block d
= s
->dest
;
1476 if (FORWARDER_BLOCK_P (d
))
1479 for (s2
= src1
->succ
; ; s2
= s2
->succ_next
)
1481 basic_block d2
= s2
->dest
;
1482 if (FORWARDER_BLOCK_P (d2
))
1483 d2
= d2
->succ
->dest
;
1488 s
->count
+= s2
->count
;
1490 /* Take care to update possible forwarder blocks. We verified
1491 that there is no more than one in the chain, so we can't run
1492 into infinite loop. */
1493 if (FORWARDER_BLOCK_P (s
->dest
))
1495 s
->dest
->succ
->count
+= s2
->count
;
1496 s
->dest
->count
+= s2
->count
;
1497 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1500 if (FORWARDER_BLOCK_P (s2
->dest
))
1502 s2
->dest
->succ
->count
-= s2
->count
;
1503 if (s2
->dest
->succ
->count
< 0)
1504 s2
->dest
->succ
->count
= 0;
1505 s2
->dest
->count
-= s2
->count
;
1506 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1507 if (s2
->dest
->frequency
< 0)
1508 s2
->dest
->frequency
= 0;
1509 if (s2
->dest
->count
< 0)
1510 s2
->dest
->count
= 0;
1513 if (!redirect_to
->frequency
&& !src1
->frequency
)
1514 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
1517 = ((s
->probability
* redirect_to
->frequency
+
1518 s2
->probability
* src1
->frequency
)
1519 / (redirect_to
->frequency
+ src1
->frequency
));
1522 update_br_prob_note (redirect_to
);
1524 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1526 /* Skip possible basic block header. */
1527 if (GET_CODE (newpos1
) == CODE_LABEL
)
1528 newpos1
= NEXT_INSN (newpos1
);
1530 if (GET_CODE (newpos1
) == NOTE
)
1531 newpos1
= NEXT_INSN (newpos1
);
1533 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
1534 to_remove
= redirect_from
->succ
->dest
;
1536 redirect_edge_and_branch_force (redirect_from
->succ
, redirect_to
);
1537 delete_block (to_remove
);
1539 update_forwarder_flag (redirect_from
);
1544 /* Search the predecessors of BB for common insn sequences. When found,
1545 share code between them by redirecting control flow. Return true if
1546 any changes made. */
1549 try_crossjump_bb (int mode
, basic_block bb
)
1551 edge e
, e2
, nexte2
, nexte
, fallthru
;
1555 /* Nothing to do if there is not at least two incoming edges. */
1556 if (!bb
->pred
|| !bb
->pred
->pred_next
)
1559 /* It is always cheapest to redirect a block that ends in a branch to
1560 a block that falls through into BB, as that adds no branches to the
1561 program. We'll try that combination first. */
1563 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
1564 for (e
= bb
->pred
; e
; e
= e
->pred_next
, n
++)
1566 if (e
->flags
& EDGE_FALLTHRU
)
1573 for (e
= bb
->pred
; e
; e
= nexte
)
1575 nexte
= e
->pred_next
;
1577 /* As noted above, first try with the fallthru predecessor. */
1580 /* Don't combine the fallthru edge into anything else.
1581 If there is a match, we'll do it the other way around. */
1585 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1593 /* Non-obvious work limiting check: Recognize that we're going
1594 to call try_crossjump_bb on every basic block. So if we have
1595 two blocks with lots of outgoing edges (a switch) and they
1596 share lots of common destinations, then we would do the
1597 cross-jump check once for each common destination.
1599 Now, if the blocks actually are cross-jump candidates, then
1600 all of their destinations will be shared. Which means that
1601 we only need check them for cross-jump candidacy once. We
1602 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1603 choosing to do the check from the block for which the edge
1604 in question is the first successor of A. */
1605 if (e
->src
->succ
!= e
)
1608 for (e2
= bb
->pred
; e2
; e2
= nexte2
)
1610 nexte2
= e2
->pred_next
;
1615 /* We've already checked the fallthru edge above. */
1619 /* The "first successor" check above only prevents multiple
1620 checks of crossjump(A,B). In order to prevent redundant
1621 checks of crossjump(B,A), require that A be the block
1622 with the lowest index. */
1623 if (e
->src
->index
> e2
->src
->index
)
1626 if (try_crossjump_to_edge (mode
, e
, e2
))
1638 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1639 instructions etc. Return nonzero if changes were made. */
1642 try_optimize_cfg (int mode
)
1644 bool changed_overall
= false;
1647 basic_block bb
, b
, next
;
1649 if (mode
& CLEANUP_CROSSJUMP
)
1650 add_noreturn_fake_exit_edges ();
1653 update_forwarder_flag (bb
);
1655 if (mode
& CLEANUP_UPDATE_LIFE
)
1658 if (! (* targetm
.cannot_modify_jumps_p
) ())
1660 /* Attempt to merge blocks as made possible by edge removal. If
1661 a block has only one successor, and the successor has only
1662 one predecessor, they may be combined. */
1669 fprintf (rtl_dump_file
,
1670 "\n\ntry_optimize_cfg iteration %i\n\n",
1673 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
1677 bool changed_here
= false;
1679 /* Delete trivially dead basic blocks. */
1680 while (b
->pred
== NULL
)
1684 fprintf (rtl_dump_file
, "Deleting block %i.\n",
1688 if (!(mode
& CLEANUP_CFGLAYOUT
))
1693 /* Remove code labels no longer used. Don't do this
1694 before CALL_PLACEHOLDER is removed, as some branches
1695 may be hidden within. */
1696 if (b
->pred
->pred_next
== NULL
1697 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1698 && !(b
->pred
->flags
& EDGE_COMPLEX
)
1699 && GET_CODE (b
->head
) == CODE_LABEL
1700 && (!(mode
& CLEANUP_PRE_SIBCALL
)
1701 || !tail_recursion_label_p (b
->head
))
1702 /* If the previous block ends with a branch to this
1703 block, we can't delete the label. Normally this
1704 is a condjump that is yet to be simplified, but
1705 if CASE_DROPS_THRU, this can be a tablejump with
1706 some element going to the same place as the
1707 default (fallthru). */
1708 && (b
->pred
->src
== ENTRY_BLOCK_PTR
1709 || GET_CODE (b
->pred
->src
->end
) != JUMP_INSN
1710 || ! label_is_jump_target_p (b
->head
,
1711 b
->pred
->src
->end
)))
1713 rtx label
= b
->head
;
1715 delete_insn_chain (label
, label
);
1716 /* In the case label is undeletable, move it after the
1717 BASIC_BLOCK note. */
1718 if (NOTE_LINE_NUMBER (b
->head
) == NOTE_INSN_DELETED_LABEL
)
1720 rtx bb_note
= NEXT_INSN (b
->head
);
1722 reorder_insns_nobb (label
, label
, bb_note
);
1726 fprintf (rtl_dump_file
, "Deleted label in block %i.\n",
1730 /* If we fall through an empty block, we can remove it. */
1731 if (!(mode
& CLEANUP_CFGLAYOUT
)
1732 && b
->pred
->pred_next
== NULL
1733 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1734 && GET_CODE (b
->head
) != CODE_LABEL
1735 && FORWARDER_BLOCK_P (b
)
1736 /* Note that forwarder_block_p true ensures that
1737 there is a successor for this block. */
1738 && (b
->succ
->flags
& EDGE_FALLTHRU
)
1739 && n_basic_blocks
> 1)
1742 fprintf (rtl_dump_file
,
1743 "Deleting fallthru block %i.\n",
1746 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
1747 redirect_edge_succ_nodup (b
->pred
, b
->succ
->dest
);
1753 if ((s
= b
->succ
) != NULL
1754 && s
->succ_next
== NULL
1755 && !(s
->flags
& EDGE_COMPLEX
)
1756 && (c
= s
->dest
) != EXIT_BLOCK_PTR
1757 && c
->pred
->pred_next
== NULL
1760 /* When not in cfg_layout mode use code aware of reordering
1761 INSN. This code possibly creates new basic blocks so it
1762 does not fit merge_blocks interface and is kept here in
1763 hope that it will become useless once more of compiler
1764 is transformed to use cfg_layout mode. */
1766 if ((mode
& CLEANUP_CFGLAYOUT
)
1767 && can_merge_blocks_p (b
, c
))
1769 merge_blocks (b
, c
);
1770 update_forwarder_flag (b
);
1771 changed_here
= true;
1773 else if (!(mode
& CLEANUP_CFGLAYOUT
)
1774 /* If the jump insn has side effects,
1775 we can't kill the edge. */
1776 && (GET_CODE (b
->end
) != JUMP_INSN
1778 ? simplejump_p (b
->end
)
1779 : onlyjump_p (b
->end
)))
1780 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
1783 changed_here
= true;
1787 /* Simplify branch over branch. */
1788 if ((mode
& CLEANUP_EXPENSIVE
)
1789 && !(mode
& CLEANUP_CFGLAYOUT
)
1790 && try_simplify_condjump (b
))
1791 changed_here
= true;
1793 /* If B has a single outgoing edge, but uses a
1794 non-trivial jump instruction without side-effects, we
1795 can either delete the jump entirely, or replace it
1796 with a simple unconditional jump. Use
1797 redirect_edge_and_branch to do the dirty work. */
1799 && ! b
->succ
->succ_next
1800 && b
->succ
->dest
!= EXIT_BLOCK_PTR
1801 && onlyjump_p (b
->end
)
1802 && redirect_edge_and_branch (b
->succ
, b
->succ
->dest
))
1804 update_forwarder_flag (b
);
1805 changed_here
= true;
1808 /* Simplify branch to branch. */
1809 if (try_forward_edges (mode
, b
))
1810 changed_here
= true;
1812 /* Look for shared code between blocks. */
1813 if ((mode
& CLEANUP_CROSSJUMP
)
1814 && try_crossjump_bb (mode
, b
))
1815 changed_here
= true;
1817 /* Don't get confused by the index shift caused by
1825 if ((mode
& CLEANUP_CROSSJUMP
)
1826 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
1829 #ifdef ENABLE_CHECKING
1831 verify_flow_info ();
1834 changed_overall
|= changed
;
1839 if (mode
& CLEANUP_CROSSJUMP
)
1840 remove_fake_edges ();
1842 clear_aux_for_blocks ();
1844 return changed_overall
;
1847 /* Delete all unreachable basic blocks. */
1850 delete_unreachable_blocks (void)
1852 bool changed
= false;
1853 basic_block b
, next_bb
;
1855 find_unreachable_blocks ();
1857 /* Delete all unreachable basic blocks. */
1859 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
; b
= next_bb
)
1861 next_bb
= b
->next_bb
;
1863 if (!(b
->flags
& BB_REACHABLE
))
1871 tidy_fallthru_edges ();
1875 /* Tidy the CFG by deleting unreachable code and whatnot. */
1878 cleanup_cfg (int mode
)
1880 bool changed
= false;
1882 timevar_push (TV_CLEANUP_CFG
);
1883 if (delete_unreachable_blocks ())
1886 /* We've possibly created trivially dead code. Cleanup it right
1887 now to introduce more opportunities for try_optimize_cfg. */
1888 if (!(mode
& (CLEANUP_NO_INSN_DEL
1889 | CLEANUP_UPDATE_LIFE
| CLEANUP_PRE_SIBCALL
))
1890 && !reload_completed
)
1891 delete_trivially_dead_insns (get_insns(), max_reg_num ());
1896 while (try_optimize_cfg (mode
))
1898 delete_unreachable_blocks (), changed
= true;
1899 if (mode
& CLEANUP_UPDATE_LIFE
)
1901 /* Cleaning up CFG introduces more opportunities for dead code
1902 removal that in turn may introduce more opportunities for
1903 cleaning up the CFG. */
1904 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES
,
1906 | PROP_SCAN_DEAD_CODE
1907 | PROP_KILL_DEAD_CODE
1911 else if (!(mode
& (CLEANUP_NO_INSN_DEL
| CLEANUP_PRE_SIBCALL
))
1912 && (mode
& CLEANUP_EXPENSIVE
)
1913 && !reload_completed
)
1915 if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
1920 delete_dead_jumptables ();
1923 /* Kill the data we won't maintain. */
1924 free_EXPR_LIST_list (&label_value_list
);
1925 timevar_pop (TV_CLEANUP_CFG
);