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
;
721 /* If there is a jump table following block B temporarily add the jump table
722 to block B so that it will also be moved to the correct location. */
723 if (tablejump_p (b
->end
, &label
, &table
)
724 && prev_active_insn (label
) == b
->end
)
729 /* There had better have been a barrier there. Delete it. */
730 barrier
= NEXT_INSN (b
->end
);
731 if (barrier
&& GET_CODE (barrier
) == BARRIER
)
732 delete_insn (barrier
);
734 /* Move block and loop notes out of the chain so that we do not
737 ??? A better solution would be to squeeze out all the non-nested notes
738 and adjust the block trees appropriately. Even better would be to have
739 a tighter connection between block trees and rtl so that this is not
741 if (squeeze_notes (&b
->head
, &b
->end
))
744 /* Scramble the insn chain. */
745 reorder_insns_nobb (b
->head
, b
->end
, a
->end
);
747 /* Restore the real end of b. */
751 fprintf (rtl_dump_file
, "Moved block %d after %d and merged.\n",
754 /* Now blocks A and B are contiguous. Merge them. */
758 /* Attempt to merge basic blocks that are potentially non-adjacent.
759 Return NULL iff the attempt failed, otherwise return basic block
760 where cleanup_cfg should continue. Because the merging commonly
761 moves basic block away or introduces another optimization
762 possibility, return basic block just before B so cleanup_cfg don't
765 It may be good idea to return basic block before C in the case
766 C has been moved after B and originally appeared earlier in the
767 insn sequence, but we have no information available about the
768 relative ordering of these two. Hopefully it is not too common. */
771 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
774 /* If C has a tail recursion label, do not merge. There is no
775 edge recorded from the call_placeholder back to this label, as
776 that would make optimize_sibling_and_tail_recursive_calls more
777 complex for no gain. */
778 if ((mode
& CLEANUP_PRE_SIBCALL
)
779 && GET_CODE (c
->head
) == CODE_LABEL
780 && tail_recursion_label_p (c
->head
))
783 /* If B has a fallthru edge to C, no need to move anything. */
784 if (e
->flags
& EDGE_FALLTHRU
)
786 int b_index
= b
->index
, c_index
= c
->index
;
788 update_forwarder_flag (b
);
791 fprintf (rtl_dump_file
, "Merged %d and %d without moving.\n",
794 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
797 /* Otherwise we will need to move code around. Do that only if expensive
798 transformations are allowed. */
799 else if (mode
& CLEANUP_EXPENSIVE
)
801 edge tmp_edge
, b_fallthru_edge
;
802 bool c_has_outgoing_fallthru
;
803 bool b_has_incoming_fallthru
;
805 /* Avoid overactive code motion, as the forwarder blocks should be
806 eliminated by edge redirection instead. One exception might have
807 been if B is a forwarder block and C has no fallthru edge, but
808 that should be cleaned up by bb-reorder instead. */
809 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
812 /* We must make sure to not munge nesting of lexical blocks,
813 and loop notes. This is done by squeezing out all the notes
814 and leaving them there to lie. Not ideal, but functional. */
816 for (tmp_edge
= c
->succ
; tmp_edge
; tmp_edge
= tmp_edge
->succ_next
)
817 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
820 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
822 for (tmp_edge
= b
->pred
; tmp_edge
; tmp_edge
= tmp_edge
->pred_next
)
823 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
826 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
827 b_fallthru_edge
= tmp_edge
;
830 next
= next
->prev_bb
;
832 /* Otherwise, we're going to try to move C after B. If C does
833 not have an outgoing fallthru, then it can be moved
834 immediately after B without introducing or modifying jumps. */
835 if (! c_has_outgoing_fallthru
)
837 merge_blocks_move_successor_nojumps (b
, c
);
838 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
841 /* If B does not have an incoming fallthru, then it can be moved
842 immediately before C without introducing or modifying jumps.
843 C cannot be the first block, so we do not have to worry about
844 accessing a non-existent block. */
846 if (b_has_incoming_fallthru
)
850 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
852 bb
= force_nonfallthru (b_fallthru_edge
);
854 notice_new_block (bb
);
857 merge_blocks_move_predecessor_nojumps (b
, c
);
858 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
865 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
868 insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
872 /* Verify that I1 and I2 are equivalent. */
873 if (GET_CODE (i1
) != GET_CODE (i2
))
879 if (GET_CODE (p1
) != GET_CODE (p2
))
882 /* If this is a CALL_INSN, compare register usage information.
883 If we don't check this on stack register machines, the two
884 CALL_INSNs might be merged leaving reg-stack.c with mismatching
885 numbers of stack registers in the same basic block.
886 If we don't check this on machines with delay slots, a delay slot may
887 be filled that clobbers a parameter expected by the subroutine.
889 ??? We take the simple route for now and assume that if they're
890 equal, they were constructed identically. */
892 if (GET_CODE (i1
) == CALL_INSN
893 && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
894 CALL_INSN_FUNCTION_USAGE (i2
))
895 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
)))
899 /* If cross_jump_death_matters is not 0, the insn's mode
900 indicates whether or not the insn contains any stack-like
903 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
905 /* If register stack conversion has already been done, then
906 death notes must also be compared before it is certain that
907 the two instruction streams match. */
910 HARD_REG_SET i1_regset
, i2_regset
;
912 CLEAR_HARD_REG_SET (i1_regset
);
913 CLEAR_HARD_REG_SET (i2_regset
);
915 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
916 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
917 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
919 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
920 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
921 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
923 GO_IF_HARD_REG_EQUAL (i1_regset
, i2_regset
, done
);
933 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
936 /* Do not do EQUIV substitution after reload. First, we're undoing the
937 work of reload_cse. Second, we may be undoing the work of the post-
938 reload splitting pass. */
939 /* ??? Possibly add a new phase switch variable that can be used by
940 targets to disallow the troublesome insns after splitting. */
941 if (!reload_completed
)
943 /* The following code helps take care of G++ cleanups. */
944 rtx equiv1
= find_reg_equal_equiv_note (i1
);
945 rtx equiv2
= find_reg_equal_equiv_note (i2
);
948 /* If the equivalences are not to a constant, they may
949 reference pseudos that no longer exist, so we can't
951 && (! reload_completed
952 || (CONSTANT_P (XEXP (equiv1
, 0))
953 && rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))))
955 rtx s1
= single_set (i1
);
956 rtx s2
= single_set (i2
);
957 if (s1
!= 0 && s2
!= 0
958 && rtx_renumbered_equal_p (SET_DEST (s1
), SET_DEST (s2
)))
960 validate_change (i1
, &SET_SRC (s1
), XEXP (equiv1
, 0), 1);
961 validate_change (i2
, &SET_SRC (s2
), XEXP (equiv2
, 0), 1);
962 if (! rtx_renumbered_equal_p (p1
, p2
))
964 else if (apply_change_group ())
973 /* Look through the insns at the end of BB1 and BB2 and find the longest
974 sequence that are equivalent. Store the first insns for that sequence
975 in *F1 and *F2 and return the sequence length.
977 To simplify callers of this function, if the blocks match exactly,
978 store the head of the blocks in *F1 and *F2. */
981 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED
, basic_block bb1
,
982 basic_block bb2
, rtx
*f1
, rtx
*f2
)
984 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
987 /* Skip simple jumps at the end of the blocks. Complex jumps still
988 need to be compared for equivalence, which we'll do below. */
991 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
993 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1001 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1004 /* Count everything except for unconditional jump as insn. */
1005 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1007 i2
= PREV_INSN (i2
);
1013 while (!INSN_P (i1
) && i1
!= bb1
->head
)
1014 i1
= PREV_INSN (i1
);
1016 while (!INSN_P (i2
) && i2
!= bb2
->head
)
1017 i2
= PREV_INSN (i2
);
1019 if (i1
== bb1
->head
|| i2
== bb2
->head
)
1022 if (!insns_match_p (mode
, i1
, i2
))
1025 /* Don't begin a cross-jump with a NOTE insn. */
1028 /* If the merged insns have different REG_EQUAL notes, then
1030 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1031 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1033 if (equiv1
&& !equiv2
)
1034 remove_note (i1
, equiv1
);
1035 else if (!equiv1
&& equiv2
)
1036 remove_note (i2
, equiv2
);
1037 else if (equiv1
&& equiv2
1038 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1040 remove_note (i1
, equiv1
);
1041 remove_note (i2
, equiv2
);
1044 afterlast1
= last1
, afterlast2
= last2
;
1045 last1
= i1
, last2
= i2
;
1049 i1
= PREV_INSN (i1
);
1050 i2
= PREV_INSN (i2
);
1054 /* Don't allow the insn after a compare to be shared by
1055 cross-jumping unless the compare is also shared. */
1056 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1057 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
1060 /* Include preceding notes and labels in the cross-jump. One,
1061 this may bring us to the head of the blocks as requested above.
1062 Two, it keeps line number notes as matched as may be. */
1065 while (last1
!= bb1
->head
&& !INSN_P (PREV_INSN (last1
)))
1066 last1
= PREV_INSN (last1
);
1068 if (last1
!= bb1
->head
&& GET_CODE (PREV_INSN (last1
)) == CODE_LABEL
)
1069 last1
= PREV_INSN (last1
);
1071 while (last2
!= bb2
->head
&& !INSN_P (PREV_INSN (last2
)))
1072 last2
= PREV_INSN (last2
);
1074 if (last2
!= bb2
->head
&& GET_CODE (PREV_INSN (last2
)) == CODE_LABEL
)
1075 last2
= PREV_INSN (last2
);
1084 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1085 the branch instruction. This means that if we commonize the control
1086 flow before end of the basic block, the semantic remains unchanged.
1088 We may assume that there exists one edge with a common destination. */
1091 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1093 int nehedges1
= 0, nehedges2
= 0;
1094 edge fallthru1
= 0, fallthru2
= 0;
1097 /* If BB1 has only one successor, we may be looking at either an
1098 unconditional jump, or a fake edge to exit. */
1099 if (bb1
->succ
&& !bb1
->succ
->succ_next
1100 && (bb1
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1101 && (GET_CODE (bb1
->end
) != JUMP_INSN
|| simplejump_p (bb1
->end
)))
1102 return (bb2
->succ
&& !bb2
->succ
->succ_next
1103 && (bb2
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1104 && (GET_CODE (bb2
->end
) != JUMP_INSN
|| simplejump_p (bb2
->end
)));
1106 /* Match conditional jumps - this may get tricky when fallthru and branch
1107 edges are crossed. */
1109 && bb1
->succ
->succ_next
1110 && !bb1
->succ
->succ_next
->succ_next
1111 && any_condjump_p (bb1
->end
)
1112 && onlyjump_p (bb1
->end
))
1114 edge b1
, f1
, b2
, f2
;
1115 bool reverse
, match
;
1116 rtx set1
, set2
, cond1
, cond2
;
1117 enum rtx_code code1
, code2
;
1120 || !bb2
->succ
->succ_next
1121 || bb2
->succ
->succ_next
->succ_next
1122 || !any_condjump_p (bb2
->end
)
1123 || !onlyjump_p (bb2
->end
))
1126 b1
= BRANCH_EDGE (bb1
);
1127 b2
= BRANCH_EDGE (bb2
);
1128 f1
= FALLTHRU_EDGE (bb1
);
1129 f2
= FALLTHRU_EDGE (bb2
);
1131 /* Get around possible forwarders on fallthru edges. Other cases
1132 should be optimized out already. */
1133 if (FORWARDER_BLOCK_P (f1
->dest
))
1134 f1
= f1
->dest
->succ
;
1136 if (FORWARDER_BLOCK_P (f2
->dest
))
1137 f2
= f2
->dest
->succ
;
1139 /* To simplify use of this function, return false if there are
1140 unneeded forwarder blocks. These will get eliminated later
1141 during cleanup_cfg. */
1142 if (FORWARDER_BLOCK_P (f1
->dest
)
1143 || FORWARDER_BLOCK_P (f2
->dest
)
1144 || FORWARDER_BLOCK_P (b1
->dest
)
1145 || FORWARDER_BLOCK_P (b2
->dest
))
1148 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1150 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1155 set1
= pc_set (bb1
->end
);
1156 set2
= pc_set (bb2
->end
);
1157 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1158 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1161 cond1
= XEXP (SET_SRC (set1
), 0);
1162 cond2
= XEXP (SET_SRC (set2
), 0);
1163 code1
= GET_CODE (cond1
);
1165 code2
= reversed_comparison_code (cond2
, bb2
->end
);
1167 code2
= GET_CODE (cond2
);
1169 if (code2
== UNKNOWN
)
1172 /* Verify codes and operands match. */
1173 match
= ((code1
== code2
1174 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1175 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1176 || (code1
== swap_condition (code2
)
1177 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1179 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1182 /* If we return true, we will join the blocks. Which means that
1183 we will only have one branch prediction bit to work with. Thus
1184 we require the existing branches to have probabilities that are
1188 && maybe_hot_bb_p (bb1
)
1189 && maybe_hot_bb_p (bb2
))
1193 if (b1
->dest
== b2
->dest
)
1194 prob2
= b2
->probability
;
1196 /* Do not use f2 probability as f2 may be forwarded. */
1197 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1199 /* Fail if the difference in probabilities is greater than 50%.
1200 This rules out two well-predicted branches with opposite
1202 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1205 fprintf (rtl_dump_file
,
1206 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1207 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1213 if (rtl_dump_file
&& match
)
1214 fprintf (rtl_dump_file
, "Conditionals in bb %i and %i match.\n",
1215 bb1
->index
, bb2
->index
);
1220 /* Generic case - we are seeing a computed jump, table jump or trapping
1223 #ifndef CASE_DROPS_THROUGH
1224 /* Check whether there are tablejumps in the end of BB1 and BB2.
1225 Return true if they are identical. */
1230 if (tablejump_p (bb1
->end
, &label1
, &table1
)
1231 && tablejump_p (bb2
->end
, &label2
, &table2
)
1232 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1234 /* The labels should never be the same rtx. If they really are same
1235 the jump tables are same too. So disable crossjumping of blocks BB1
1236 and BB2 because when deleting the common insns in the end of BB1
1237 by delete_block () the jump table would be deleted too. */
1238 /* If LABEL2 is referenced in BB1->END do not do anything
1239 because we would loose information when replacing
1240 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1241 if (label1
!= label2
&& !rtx_referenced_p (label2
, bb1
->end
))
1243 /* Set IDENTICAL to true when the tables are identical. */
1244 bool identical
= false;
1247 p1
= PATTERN (table1
);
1248 p2
= PATTERN (table2
);
1249 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1253 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1254 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1255 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1256 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1261 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1262 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1268 replace_label_data rr
;
1271 /* Temporarily replace references to LABEL1 with LABEL2
1272 in BB1->END so that we could compare the instructions. */
1275 rr
.update_label_nuses
= false;
1276 for_each_rtx (&bb1
->end
, replace_label
, &rr
);
1278 match
= insns_match_p (mode
, bb1
->end
, bb2
->end
);
1279 if (rtl_dump_file
&& match
)
1280 fprintf (rtl_dump_file
,
1281 "Tablejumps in bb %i and %i match.\n",
1282 bb1
->index
, bb2
->index
);
1284 /* Set the original label in BB1->END because when deleting
1285 a block whose end is a tablejump, the tablejump referenced
1286 from the instruction is deleted too. */
1289 for_each_rtx (&bb1
->end
, replace_label
, &rr
);
1299 /* First ensure that the instructions match. There may be many outgoing
1300 edges so this test is generally cheaper. */
1301 if (!insns_match_p (mode
, bb1
->end
, bb2
->end
))
1304 /* Search the outgoing edges, ensure that the counts do match, find possible
1305 fallthru and exception handling edges since these needs more
1307 for (e1
= bb1
->succ
, e2
= bb2
->succ
; e1
&& e2
;
1308 e1
= e1
->succ_next
, e2
= e2
->succ_next
)
1310 if (e1
->flags
& EDGE_EH
)
1313 if (e2
->flags
& EDGE_EH
)
1316 if (e1
->flags
& EDGE_FALLTHRU
)
1318 if (e2
->flags
& EDGE_FALLTHRU
)
1322 /* If number of edges of various types does not match, fail. */
1324 || nehedges1
!= nehedges2
1325 || (fallthru1
!= 0) != (fallthru2
!= 0))
1328 /* fallthru edges must be forwarded to the same destination. */
1331 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1332 ? fallthru1
->dest
->succ
->dest
: fallthru1
->dest
);
1333 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1334 ? fallthru2
->dest
->succ
->dest
: fallthru2
->dest
);
1340 /* Ensure the same EH region. */
1342 rtx n1
= find_reg_note (bb1
->end
, REG_EH_REGION
, 0);
1343 rtx n2
= find_reg_note (bb2
->end
, REG_EH_REGION
, 0);
1348 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1352 /* We don't need to match the rest of edges as above checks should be enough
1353 to ensure that they are equivalent. */
1357 /* E1 and E2 are edges with the same destination block. Search their
1358 predecessors for common code. If found, redirect control flow from
1359 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1362 try_crossjump_to_edge (int mode
, edge e1
, edge e2
)
1365 basic_block src1
= e1
->src
, src2
= e2
->src
;
1366 basic_block redirect_to
, redirect_from
, to_remove
;
1367 rtx newpos1
, newpos2
;
1370 /* Search backward through forwarder blocks. We don't need to worry
1371 about multiple entry or chained forwarders, as they will be optimized
1372 away. We do this to look past the unconditional jump following a
1373 conditional jump that is required due to the current CFG shape. */
1375 && !src1
->pred
->pred_next
1376 && FORWARDER_BLOCK_P (src1
))
1377 e1
= src1
->pred
, src1
= e1
->src
;
1380 && !src2
->pred
->pred_next
1381 && FORWARDER_BLOCK_P (src2
))
1382 e2
= src2
->pred
, src2
= e2
->src
;
1384 /* Nothing to do if we reach ENTRY, or a common source block. */
1385 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1390 /* Seeing more than 1 forwarder blocks would confuse us later... */
1391 if (FORWARDER_BLOCK_P (e1
->dest
)
1392 && FORWARDER_BLOCK_P (e1
->dest
->succ
->dest
))
1395 if (FORWARDER_BLOCK_P (e2
->dest
)
1396 && FORWARDER_BLOCK_P (e2
->dest
->succ
->dest
))
1399 /* Likewise with dead code (possibly newly created by the other optimizations
1401 if (!src1
->pred
|| !src2
->pred
)
1404 /* Look for the common insn sequence, part the first ... */
1405 if (!outgoing_edges_match (mode
, src1
, src2
))
1408 /* ... and part the second. */
1409 nmatch
= flow_find_cross_jump (mode
, src1
, src2
, &newpos1
, &newpos2
);
1413 #ifndef CASE_DROPS_THROUGH
1414 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1416 If we have tablejumps in the end of SRC1 and SRC2
1417 they have been already compared for equivalence in outgoing_edges_match ()
1418 so replace the references to TABLE1 by references to TABLE2. */
1423 if (tablejump_p (src1
->end
, &label1
, &table1
)
1424 && tablejump_p (src2
->end
, &label2
, &table2
)
1425 && label1
!= label2
)
1427 replace_label_data rr
;
1430 /* Replace references to LABEL1 with LABEL2. */
1433 rr
.update_label_nuses
= true;
1434 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1436 /* Do not replace the label in SRC1->END because when deleting
1437 a block whose end is a tablejump, the tablejump referenced
1438 from the instruction is deleted too. */
1439 if (insn
!= src1
->end
)
1440 for_each_rtx (&insn
, replace_label
, &rr
);
1446 /* Avoid splitting if possible. */
1447 if (newpos2
== src2
->head
)
1452 fprintf (rtl_dump_file
, "Splitting bb %i before %i insns\n",
1453 src2
->index
, nmatch
);
1454 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1458 fprintf (rtl_dump_file
,
1459 "Cross jumping from bb %i to bb %i; %i common insns\n",
1460 src1
->index
, src2
->index
, nmatch
);
1462 redirect_to
->count
+= src1
->count
;
1463 redirect_to
->frequency
+= src1
->frequency
;
1464 /* We may have some registers visible trought the block. */
1465 redirect_to
->flags
|= BB_DIRTY
;
1467 /* Recompute the frequencies and counts of outgoing edges. */
1468 for (s
= redirect_to
->succ
; s
; s
= s
->succ_next
)
1471 basic_block d
= s
->dest
;
1473 if (FORWARDER_BLOCK_P (d
))
1476 for (s2
= src1
->succ
; ; s2
= s2
->succ_next
)
1478 basic_block d2
= s2
->dest
;
1479 if (FORWARDER_BLOCK_P (d2
))
1480 d2
= d2
->succ
->dest
;
1485 s
->count
+= s2
->count
;
1487 /* Take care to update possible forwarder blocks. We verified
1488 that there is no more than one in the chain, so we can't run
1489 into infinite loop. */
1490 if (FORWARDER_BLOCK_P (s
->dest
))
1492 s
->dest
->succ
->count
+= s2
->count
;
1493 s
->dest
->count
+= s2
->count
;
1494 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1497 if (FORWARDER_BLOCK_P (s2
->dest
))
1499 s2
->dest
->succ
->count
-= s2
->count
;
1500 if (s2
->dest
->succ
->count
< 0)
1501 s2
->dest
->succ
->count
= 0;
1502 s2
->dest
->count
-= s2
->count
;
1503 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1504 if (s2
->dest
->frequency
< 0)
1505 s2
->dest
->frequency
= 0;
1506 if (s2
->dest
->count
< 0)
1507 s2
->dest
->count
= 0;
1510 if (!redirect_to
->frequency
&& !src1
->frequency
)
1511 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
1514 = ((s
->probability
* redirect_to
->frequency
+
1515 s2
->probability
* src1
->frequency
)
1516 / (redirect_to
->frequency
+ src1
->frequency
));
1519 update_br_prob_note (redirect_to
);
1521 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1523 /* Skip possible basic block header. */
1524 if (GET_CODE (newpos1
) == CODE_LABEL
)
1525 newpos1
= NEXT_INSN (newpos1
);
1527 if (GET_CODE (newpos1
) == NOTE
)
1528 newpos1
= NEXT_INSN (newpos1
);
1530 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
1531 to_remove
= redirect_from
->succ
->dest
;
1533 redirect_edge_and_branch_force (redirect_from
->succ
, redirect_to
);
1534 delete_block (to_remove
);
1536 update_forwarder_flag (redirect_from
);
1541 /* Search the predecessors of BB for common insn sequences. When found,
1542 share code between them by redirecting control flow. Return true if
1543 any changes made. */
1546 try_crossjump_bb (int mode
, basic_block bb
)
1548 edge e
, e2
, nexte2
, nexte
, fallthru
;
1552 /* Nothing to do if there is not at least two incoming edges. */
1553 if (!bb
->pred
|| !bb
->pred
->pred_next
)
1556 /* It is always cheapest to redirect a block that ends in a branch to
1557 a block that falls through into BB, as that adds no branches to the
1558 program. We'll try that combination first. */
1560 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
1561 for (e
= bb
->pred
; e
; e
= e
->pred_next
, n
++)
1563 if (e
->flags
& EDGE_FALLTHRU
)
1570 for (e
= bb
->pred
; e
; e
= nexte
)
1572 nexte
= e
->pred_next
;
1574 /* As noted above, first try with the fallthru predecessor. */
1577 /* Don't combine the fallthru edge into anything else.
1578 If there is a match, we'll do it the other way around. */
1582 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1590 /* Non-obvious work limiting check: Recognize that we're going
1591 to call try_crossjump_bb on every basic block. So if we have
1592 two blocks with lots of outgoing edges (a switch) and they
1593 share lots of common destinations, then we would do the
1594 cross-jump check once for each common destination.
1596 Now, if the blocks actually are cross-jump candidates, then
1597 all of their destinations will be shared. Which means that
1598 we only need check them for cross-jump candidacy once. We
1599 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1600 choosing to do the check from the block for which the edge
1601 in question is the first successor of A. */
1602 if (e
->src
->succ
!= e
)
1605 for (e2
= bb
->pred
; e2
; e2
= nexte2
)
1607 nexte2
= e2
->pred_next
;
1612 /* We've already checked the fallthru edge above. */
1616 /* The "first successor" check above only prevents multiple
1617 checks of crossjump(A,B). In order to prevent redundant
1618 checks of crossjump(B,A), require that A be the block
1619 with the lowest index. */
1620 if (e
->src
->index
> e2
->src
->index
)
1623 if (try_crossjump_to_edge (mode
, e
, e2
))
1635 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1636 instructions etc. Return nonzero if changes were made. */
1639 try_optimize_cfg (int mode
)
1641 bool changed_overall
= false;
1644 basic_block bb
, b
, next
;
1646 if (mode
& CLEANUP_CROSSJUMP
)
1647 add_noreturn_fake_exit_edges ();
1650 update_forwarder_flag (bb
);
1652 if (mode
& CLEANUP_UPDATE_LIFE
)
1655 if (! (* targetm
.cannot_modify_jumps_p
) ())
1657 /* Attempt to merge blocks as made possible by edge removal. If
1658 a block has only one successor, and the successor has only
1659 one predecessor, they may be combined. */
1666 fprintf (rtl_dump_file
,
1667 "\n\ntry_optimize_cfg iteration %i\n\n",
1670 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
1674 bool changed_here
= false;
1676 /* Delete trivially dead basic blocks. */
1677 while (b
->pred
== NULL
)
1681 fprintf (rtl_dump_file
, "Deleting block %i.\n",
1685 if (!(mode
& CLEANUP_CFGLAYOUT
))
1690 /* Remove code labels no longer used. Don't do this
1691 before CALL_PLACEHOLDER is removed, as some branches
1692 may be hidden within. */
1693 if (b
->pred
->pred_next
== NULL
1694 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1695 && !(b
->pred
->flags
& EDGE_COMPLEX
)
1696 && GET_CODE (b
->head
) == CODE_LABEL
1697 && (!(mode
& CLEANUP_PRE_SIBCALL
)
1698 || !tail_recursion_label_p (b
->head
))
1699 /* If the previous block ends with a branch to this
1700 block, we can't delete the label. Normally this
1701 is a condjump that is yet to be simplified, but
1702 if CASE_DROPS_THRU, this can be a tablejump with
1703 some element going to the same place as the
1704 default (fallthru). */
1705 && (b
->pred
->src
== ENTRY_BLOCK_PTR
1706 || GET_CODE (b
->pred
->src
->end
) != JUMP_INSN
1707 || ! label_is_jump_target_p (b
->head
,
1708 b
->pred
->src
->end
)))
1710 rtx label
= b
->head
;
1712 delete_insn_chain (label
, label
);
1713 /* In the case label is undeletable, move it after the
1714 BASIC_BLOCK note. */
1715 if (NOTE_LINE_NUMBER (b
->head
) == NOTE_INSN_DELETED_LABEL
)
1717 rtx bb_note
= NEXT_INSN (b
->head
);
1719 reorder_insns_nobb (label
, label
, bb_note
);
1723 fprintf (rtl_dump_file
, "Deleted label in block %i.\n",
1727 /* If we fall through an empty block, we can remove it. */
1728 if (!(mode
& CLEANUP_CFGLAYOUT
)
1729 && b
->pred
->pred_next
== NULL
1730 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1731 && GET_CODE (b
->head
) != CODE_LABEL
1732 && FORWARDER_BLOCK_P (b
)
1733 /* Note that forwarder_block_p true ensures that
1734 there is a successor for this block. */
1735 && (b
->succ
->flags
& EDGE_FALLTHRU
)
1736 && n_basic_blocks
> 1)
1739 fprintf (rtl_dump_file
,
1740 "Deleting fallthru block %i.\n",
1743 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
1744 redirect_edge_succ_nodup (b
->pred
, b
->succ
->dest
);
1750 if ((s
= b
->succ
) != NULL
1751 && s
->succ_next
== NULL
1752 && !(s
->flags
& EDGE_COMPLEX
)
1753 && (c
= s
->dest
) != EXIT_BLOCK_PTR
1754 && c
->pred
->pred_next
== NULL
1757 /* When not in cfg_layout mode use code aware of reordering
1758 INSN. This code possibly creates new basic blocks so it
1759 does not fit merge_blocks interface and is kept here in
1760 hope that it will become useless once more of compiler
1761 is transformed to use cfg_layout mode. */
1763 if ((mode
& CLEANUP_CFGLAYOUT
)
1764 && can_merge_blocks_p (b
, c
))
1766 merge_blocks (b
, c
);
1767 update_forwarder_flag (b
);
1768 changed_here
= true;
1770 else if (!(mode
& CLEANUP_CFGLAYOUT
)
1771 /* If the jump insn has side effects,
1772 we can't kill the edge. */
1773 && (GET_CODE (b
->end
) != JUMP_INSN
1775 ? simplejump_p (b
->end
)
1776 : onlyjump_p (b
->end
)))
1777 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
1780 changed_here
= true;
1784 /* Simplify branch over branch. */
1785 if ((mode
& CLEANUP_EXPENSIVE
)
1786 && !(mode
& CLEANUP_CFGLAYOUT
)
1787 && try_simplify_condjump (b
))
1788 changed_here
= true;
1790 /* If B has a single outgoing edge, but uses a
1791 non-trivial jump instruction without side-effects, we
1792 can either delete the jump entirely, or replace it
1793 with a simple unconditional jump. Use
1794 redirect_edge_and_branch to do the dirty work. */
1796 && ! b
->succ
->succ_next
1797 && b
->succ
->dest
!= EXIT_BLOCK_PTR
1798 && onlyjump_p (b
->end
)
1799 && redirect_edge_and_branch (b
->succ
, b
->succ
->dest
))
1801 update_forwarder_flag (b
);
1802 changed_here
= true;
1805 /* Simplify branch to branch. */
1806 if (try_forward_edges (mode
, b
))
1807 changed_here
= true;
1809 /* Look for shared code between blocks. */
1810 if ((mode
& CLEANUP_CROSSJUMP
)
1811 && try_crossjump_bb (mode
, b
))
1812 changed_here
= true;
1814 /* Don't get confused by the index shift caused by
1822 if ((mode
& CLEANUP_CROSSJUMP
)
1823 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
1826 #ifdef ENABLE_CHECKING
1828 verify_flow_info ();
1831 changed_overall
|= changed
;
1836 if (mode
& CLEANUP_CROSSJUMP
)
1837 remove_fake_edges ();
1839 clear_aux_for_blocks ();
1841 return changed_overall
;
1844 /* Delete all unreachable basic blocks. */
1847 delete_unreachable_blocks (void)
1849 bool changed
= false;
1850 basic_block b
, next_bb
;
1852 find_unreachable_blocks ();
1854 /* Delete all unreachable basic blocks. */
1856 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
; b
= next_bb
)
1858 next_bb
= b
->next_bb
;
1860 if (!(b
->flags
& BB_REACHABLE
))
1868 tidy_fallthru_edges ();
1872 /* Tidy the CFG by deleting unreachable code and whatnot. */
1875 cleanup_cfg (int mode
)
1877 bool changed
= false;
1879 timevar_push (TV_CLEANUP_CFG
);
1880 if (delete_unreachable_blocks ())
1883 /* We've possibly created trivially dead code. Cleanup it right
1884 now to introduce more opportunities for try_optimize_cfg. */
1885 if (!(mode
& (CLEANUP_NO_INSN_DEL
1886 | CLEANUP_UPDATE_LIFE
| CLEANUP_PRE_SIBCALL
))
1887 && !reload_completed
)
1888 delete_trivially_dead_insns (get_insns(), max_reg_num ());
1893 while (try_optimize_cfg (mode
))
1895 delete_unreachable_blocks (), changed
= true;
1896 if (mode
& CLEANUP_UPDATE_LIFE
)
1898 /* Cleaning up CFG introduces more opportunities for dead code
1899 removal that in turn may introduce more opportunities for
1900 cleaning up the CFG. */
1901 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES
,
1903 | PROP_SCAN_DEAD_CODE
1904 | PROP_KILL_DEAD_CODE
1908 else if (!(mode
& (CLEANUP_NO_INSN_DEL
| CLEANUP_PRE_SIBCALL
))
1909 && (mode
& CLEANUP_EXPENSIVE
)
1910 && !reload_completed
)
1912 if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
1917 delete_dead_jumptables ();
1920 /* Kill the data we won't maintain. */
1921 free_EXPR_LIST_list (&label_value_list
);
1922 timevar_pop (TV_CLEANUP_CFG
);