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 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
PARAMS ((int, edge
, edge
));
71 static bool try_crossjump_bb
PARAMS ((int, basic_block
));
72 static bool outgoing_edges_match
PARAMS ((int,
73 basic_block
, basic_block
));
74 static int flow_find_cross_jump
PARAMS ((int, basic_block
, basic_block
,
76 static bool insns_match_p
PARAMS ((int, rtx
, rtx
));
78 static bool label_is_jump_target_p
PARAMS ((rtx
, rtx
));
79 static bool tail_recursion_label_p
PARAMS ((rtx
));
80 static void merge_blocks_move_predecessor_nojumps
PARAMS ((basic_block
,
82 static void merge_blocks_move_successor_nojumps
PARAMS ((basic_block
,
84 static basic_block merge_blocks
PARAMS ((edge
,basic_block
,basic_block
,
86 static bool try_optimize_cfg
PARAMS ((int));
87 static bool try_simplify_condjump
PARAMS ((basic_block
));
88 static bool try_forward_edges
PARAMS ((int, basic_block
));
89 static edge thread_jump
PARAMS ((int, edge
, basic_block
));
90 static bool mark_effect
PARAMS ((rtx
, bitmap
));
91 static void notice_new_block
PARAMS ((basic_block
));
92 static void update_forwarder_flag
PARAMS ((basic_block
));
93 static int mentions_nonequal_regs
PARAMS ((rtx
*, void *));
95 /* Set flags for newly created block. */
104 if (forwarder_block_p (bb
))
105 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
108 /* Recompute forwarder flag after block has been modified. */
111 update_forwarder_flag (bb
)
114 if (forwarder_block_p (bb
))
115 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
117 BB_CLEAR_FLAG (bb
, BB_FORWARDER_BLOCK
);
120 /* Simplify a conditional jump around an unconditional jump.
121 Return true if something changed. */
124 try_simplify_condjump (cbranch_block
)
125 basic_block cbranch_block
;
127 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
128 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
131 /* Verify that there are exactly two successors. */
132 if (!cbranch_block
->succ
133 || !cbranch_block
->succ
->succ_next
134 || cbranch_block
->succ
->succ_next
->succ_next
)
137 /* Verify that we've got a normal conditional branch at the end
139 cbranch_insn
= cbranch_block
->end
;
140 if (!any_condjump_p (cbranch_insn
))
143 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
144 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
146 /* The next block must not have multiple predecessors, must not
147 be the last block in the function, and must contain just the
148 unconditional jump. */
149 jump_block
= cbranch_fallthru_edge
->dest
;
150 if (jump_block
->pred
->pred_next
151 || jump_block
->next_bb
== EXIT_BLOCK_PTR
152 || !FORWARDER_BLOCK_P (jump_block
))
154 jump_dest_block
= jump_block
->succ
->dest
;
156 /* The conditional branch must target the block after the
157 unconditional branch. */
158 cbranch_dest_block
= cbranch_jump_edge
->dest
;
160 if (!can_fallthru (jump_block
, cbranch_dest_block
))
163 /* Invert the conditional branch. */
164 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
168 fprintf (rtl_dump_file
, "Simplifying condjump %i around jump %i\n",
169 INSN_UID (cbranch_insn
), INSN_UID (jump_block
->end
));
171 /* Success. Update the CFG to match. Note that after this point
172 the edge variable names appear backwards; the redirection is done
173 this way to preserve edge profile data. */
174 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
176 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
178 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
179 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
180 update_br_prob_note (cbranch_block
);
182 /* Delete the block with the unconditional jump, and clean up the mess. */
183 flow_delete_block (jump_block
);
184 tidy_fallthru_edge (cbranch_jump_edge
, cbranch_block
, cbranch_dest_block
);
189 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
190 on register. Used by jump threading. */
193 mark_effect (exp
, nonequal
)
199 switch (GET_CODE (exp
))
201 /* In case we do clobber the register, mark it as equal, as we know the
202 value is dead so it don't have to match. */
204 if (REG_P (XEXP (exp
, 0)))
206 dest
= XEXP (exp
, 0);
207 regno
= REGNO (dest
);
208 CLEAR_REGNO_REG_SET (nonequal
, regno
);
209 if (regno
< FIRST_PSEUDO_REGISTER
)
211 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
213 CLEAR_REGNO_REG_SET (nonequal
, regno
+ n
);
219 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
221 dest
= SET_DEST (exp
);
226 regno
= REGNO (dest
);
227 SET_REGNO_REG_SET (nonequal
, regno
);
228 if (regno
< FIRST_PSEUDO_REGISTER
)
230 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
232 SET_REGNO_REG_SET (nonequal
, regno
+ n
);
241 /* Return nonzero if X is an register set in regset DATA.
242 Called via for_each_rtx. */
244 mentions_nonequal_regs (x
, data
)
248 regset nonequal
= (regset
) data
;
254 if (REGNO_REG_SET_P (nonequal
, regno
))
256 if (regno
< FIRST_PSEUDO_REGISTER
)
258 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (*x
));
260 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
266 /* Attempt to prove that the basic block B will have no side effects and
267 always continues in the same edge if reached via E. Return the edge
268 if exist, NULL otherwise. */
271 thread_jump (mode
, e
, b
)
276 rtx set1
, set2
, cond1
, cond2
, insn
;
277 enum rtx_code code1
, code2
, reversed_code2
;
278 bool reverse1
= false;
283 if (BB_FLAGS (b
) & BB_NONTHREADABLE_BLOCK
)
286 /* At the moment, we do handle only conditional jumps, but later we may
287 want to extend this code to tablejumps and others. */
288 if (!e
->src
->succ
->succ_next
|| e
->src
->succ
->succ_next
->succ_next
)
290 if (!b
->succ
|| !b
->succ
->succ_next
|| b
->succ
->succ_next
->succ_next
)
292 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
296 /* Second branch must end with onlyjump, as we will eliminate the jump. */
297 if (!any_condjump_p (e
->src
->end
))
300 if (!any_condjump_p (b
->end
) || !onlyjump_p (b
->end
))
302 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
306 set1
= pc_set (e
->src
->end
);
307 set2
= pc_set (b
->end
);
308 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
309 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
312 cond1
= XEXP (SET_SRC (set1
), 0);
313 cond2
= XEXP (SET_SRC (set2
), 0);
315 code1
= reversed_comparison_code (cond1
, e
->src
->end
);
317 code1
= GET_CODE (cond1
);
319 code2
= GET_CODE (cond2
);
320 reversed_code2
= reversed_comparison_code (cond2
, b
->end
);
322 if (!comparison_dominates_p (code1
, code2
)
323 && !comparison_dominates_p (code1
, reversed_code2
))
326 /* Ensure that the comparison operators are equivalent.
327 ??? This is far too pessimistic. We should allow swapped operands,
328 different CCmodes, or for example comparisons for interval, that
329 dominate even when operands are not equivalent. */
330 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
331 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
334 /* Short circuit cases where block B contains some side effects, as we can't
336 for (insn
= NEXT_INSN (b
->head
); insn
!= NEXT_INSN (b
->end
);
337 insn
= NEXT_INSN (insn
))
338 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
340 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
346 /* First process all values computed in the source basic block. */
347 for (insn
= NEXT_INSN (e
->src
->head
); insn
!= NEXT_INSN (e
->src
->end
);
348 insn
= NEXT_INSN (insn
))
350 cselib_process_insn (insn
);
352 nonequal
= BITMAP_XMALLOC();
353 CLEAR_REG_SET (nonequal
);
355 /* Now assume that we've continued by the edge E to B and continue
356 processing as if it were same basic block.
357 Our goal is to prove that whole block is an NOOP. */
359 for (insn
= NEXT_INSN (b
->head
); insn
!= NEXT_INSN (b
->end
) && !failed
;
360 insn
= NEXT_INSN (insn
))
364 rtx pat
= PATTERN (insn
);
366 if (GET_CODE (pat
) == PARALLEL
)
368 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
369 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
372 failed
|= mark_effect (pat
, nonequal
);
375 cselib_process_insn (insn
);
378 /* Later we should clear nonequal of dead registers. So far we don't
379 have life information in cfg_cleanup. */
382 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
386 /* cond2 must not mention any register that is not equal to the
388 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
391 /* In case liveness information is available, we need to prove equivalence
392 only of the live values. */
393 if (mode
& CLEANUP_UPDATE_LIFE
)
394 AND_REG_SET (nonequal
, b
->global_live_at_end
);
396 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, goto failed_exit
;);
398 BITMAP_XFREE (nonequal
);
400 if ((comparison_dominates_p (code1
, code2
) != 0)
401 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
402 return BRANCH_EDGE (b
);
404 return FALLTHRU_EDGE (b
);
407 BITMAP_XFREE (nonequal
);
412 /* Attempt to forward edges leaving basic block B.
413 Return true if successful. */
416 try_forward_edges (mode
, b
)
420 bool changed
= false;
421 edge e
, next
, *threaded_edges
= NULL
;
423 for (e
= b
->succ
; e
; e
= next
)
425 basic_block target
, first
;
427 bool threaded
= false;
428 int nthreaded_edges
= 0;
432 /* Skip complex edges because we don't know how to update them.
434 Still handle fallthru edges, as we can succeed to forward fallthru
435 edge to the same place as the branch edge of conditional branch
436 and turn conditional branch to an unconditional branch. */
437 if (e
->flags
& EDGE_COMPLEX
)
440 target
= first
= e
->dest
;
443 while (counter
< n_basic_blocks
)
445 basic_block new_target
= NULL
;
446 bool new_target_threaded
= false;
448 if (FORWARDER_BLOCK_P (target
)
449 && target
->succ
->dest
!= EXIT_BLOCK_PTR
)
451 /* Bypass trivial infinite loops. */
452 if (target
== target
->succ
->dest
)
453 counter
= n_basic_blocks
;
454 new_target
= target
->succ
->dest
;
457 /* Allow to thread only over one edge at time to simplify updating
459 else if (mode
& CLEANUP_THREADING
)
461 edge t
= thread_jump (mode
, e
, target
);
465 threaded_edges
= xmalloc (sizeof (*threaded_edges
)
471 /* Detect an infinite loop across blocks not
472 including the start block. */
473 for (i
= 0; i
< nthreaded_edges
; ++i
)
474 if (threaded_edges
[i
] == t
)
476 if (i
< nthreaded_edges
)
478 counter
= n_basic_blocks
;
483 /* Detect an infinite loop across the start block. */
487 if (nthreaded_edges
>= n_basic_blocks
)
489 threaded_edges
[nthreaded_edges
++] = t
;
491 new_target
= t
->dest
;
492 new_target_threaded
= true;
499 /* Avoid killing of loop pre-headers, as it is the place loop
500 optimizer wants to hoist code to.
502 For fallthru forwarders, the LOOP_BEG note must appear between
503 the header of block and CODE_LABEL of the loop, for non forwarders
504 it must appear before the JUMP_INSN. */
505 if ((mode
& CLEANUP_PRE_LOOP
) && optimize
)
507 rtx insn
= (target
->succ
->flags
& EDGE_FALLTHRU
508 ? target
->head
: prev_nonnote_insn (target
->end
));
510 if (GET_CODE (insn
) != NOTE
)
511 insn
= NEXT_INSN (insn
);
513 for (; insn
&& GET_CODE (insn
) != CODE_LABEL
&& !INSN_P (insn
);
514 insn
= NEXT_INSN (insn
))
515 if (GET_CODE (insn
) == NOTE
516 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
519 if (GET_CODE (insn
) == NOTE
)
522 /* Do not clean up branches to just past the end of a loop
523 at this time; it can mess up the loop optimizer's
524 recognition of some patterns. */
526 insn
= PREV_INSN (target
->head
);
527 if (insn
&& GET_CODE (insn
) == NOTE
528 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
534 threaded
|= new_target_threaded
;
537 if (counter
>= n_basic_blocks
)
540 fprintf (rtl_dump_file
, "Infinite loop in BB %i.\n",
543 else if (target
== first
)
544 ; /* We didn't do anything. */
547 /* Save the values now, as the edge may get removed. */
548 gcov_type edge_count
= e
->count
;
549 int edge_probability
= e
->probability
;
553 /* Don't force if target is exit block. */
554 if (threaded
&& target
!= EXIT_BLOCK_PTR
)
556 notice_new_block (redirect_edge_and_branch_force (e
, target
));
558 fprintf (rtl_dump_file
, "Conditionals threaded.\n");
560 else if (!redirect_edge_and_branch (e
, target
))
563 fprintf (rtl_dump_file
,
564 "Forwarding edge %i->%i to %i failed.\n",
565 b
->index
, e
->dest
->index
, target
->index
);
569 /* We successfully forwarded the edge. Now update profile
570 data: for each edge we traversed in the chain, remove
571 the original edge's execution count. */
572 edge_frequency
= ((edge_probability
* b
->frequency
573 + REG_BR_PROB_BASE
/ 2)
576 if (!FORWARDER_BLOCK_P (b
) && forwarder_block_p (b
))
577 BB_SET_FLAG (b
, BB_FORWARDER_BLOCK
);
583 first
->count
-= edge_count
;
584 if (first
->count
< 0)
586 first
->frequency
-= edge_frequency
;
587 if (first
->frequency
< 0)
588 first
->frequency
= 0;
589 if (first
->succ
->succ_next
)
593 if (n
>= nthreaded_edges
)
595 t
= threaded_edges
[n
++];
598 if (first
->frequency
)
599 prob
= edge_frequency
* REG_BR_PROB_BASE
/ first
->frequency
;
602 if (prob
> t
->probability
)
603 prob
= t
->probability
;
604 t
->probability
-= prob
;
605 prob
= REG_BR_PROB_BASE
- prob
;
608 first
->succ
->probability
= REG_BR_PROB_BASE
;
609 first
->succ
->succ_next
->probability
= 0;
612 for (e
= first
->succ
; e
; e
= e
->succ_next
)
613 e
->probability
= ((e
->probability
* REG_BR_PROB_BASE
)
615 update_br_prob_note (first
);
619 /* It is possible that as the result of
620 threading we've removed edge as it is
621 threaded to the fallthru edge. Avoid
622 getting out of sync. */
623 if (n
< nthreaded_edges
624 && first
== threaded_edges
[n
]->src
)
629 t
->count
-= edge_count
;
634 while (first
!= target
);
641 free (threaded_edges
);
645 /* Return true if LABEL is a target of JUMP_INSN. This applies only
646 to non-complex jumps. That is, direct unconditional, conditional,
647 and tablejumps, but not computed jumps or returns. It also does
648 not apply to the fallthru case of a conditional jump. */
651 label_is_jump_target_p (label
, jump_insn
)
652 rtx label
, jump_insn
;
654 rtx tmp
= JUMP_LABEL (jump_insn
);
660 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
661 && GET_CODE (tmp
) == JUMP_INSN
662 && (tmp
= PATTERN (tmp
),
663 GET_CODE (tmp
) == ADDR_VEC
664 || GET_CODE (tmp
) == ADDR_DIFF_VEC
))
666 rtvec vec
= XVEC (tmp
, GET_CODE (tmp
) == ADDR_DIFF_VEC
);
667 int i
, veclen
= GET_NUM_ELEM (vec
);
669 for (i
= 0; i
< veclen
; ++i
)
670 if (XEXP (RTVEC_ELT (vec
, i
), 0) == label
)
677 /* Return true if LABEL is used for tail recursion. */
680 tail_recursion_label_p (label
)
685 for (x
= tail_recursion_label_list
; x
; x
= XEXP (x
, 1))
686 if (label
== XEXP (x
, 0))
692 /* Blocks A and B are to be merged into a single block. A has no incoming
693 fallthru edge, so it can be moved before B without adding or modifying
694 any jumps (aside from the jump from A to B). */
697 merge_blocks_move_predecessor_nojumps (a
, b
)
702 barrier
= next_nonnote_insn (a
->end
);
703 if (GET_CODE (barrier
) != BARRIER
)
705 delete_insn (barrier
);
707 /* Move block and loop notes out of the chain so that we do not
710 ??? A better solution would be to squeeze out all the non-nested notes
711 and adjust the block trees appropriately. Even better would be to have
712 a tighter connection between block trees and rtl so that this is not
714 if (squeeze_notes (&a
->head
, &a
->end
))
717 /* Scramble the insn chain. */
718 if (a
->end
!= PREV_INSN (b
->head
))
719 reorder_insns_nobb (a
->head
, a
->end
, PREV_INSN (b
->head
));
720 a
->flags
|= BB_DIRTY
;
723 fprintf (rtl_dump_file
, "Moved block %d before %d and merged.\n",
726 /* Swap the records for the two blocks around. */
729 link_block (a
, b
->prev_bb
);
731 /* Now blocks A and B are contiguous. Merge them. */
732 merge_blocks_nomove (a
, b
);
735 /* Blocks A and B are to be merged into a single block. B has no outgoing
736 fallthru edge, so it can be moved after A without adding or modifying
737 any jumps (aside from the jump from A to B). */
740 merge_blocks_move_successor_nojumps (a
, b
)
743 rtx barrier
, real_b_end
;
746 barrier
= NEXT_INSN (b
->end
);
748 /* Recognize a jump table following block B. */
750 && GET_CODE (barrier
) == CODE_LABEL
751 && NEXT_INSN (barrier
)
752 && GET_CODE (NEXT_INSN (barrier
)) == JUMP_INSN
753 && (GET_CODE (PATTERN (NEXT_INSN (barrier
))) == ADDR_VEC
754 || GET_CODE (PATTERN (NEXT_INSN (barrier
))) == ADDR_DIFF_VEC
))
756 /* Temporarily add the table jump insn to b, so that it will also
757 be moved to the correct location. */
758 b
->end
= NEXT_INSN (barrier
);
759 barrier
= NEXT_INSN (b
->end
);
762 /* There had better have been a barrier there. Delete it. */
763 if (barrier
&& GET_CODE (barrier
) == BARRIER
)
764 delete_insn (barrier
);
766 /* Move block and loop notes out of the chain so that we do not
769 ??? A better solution would be to squeeze out all the non-nested notes
770 and adjust the block trees appropriately. Even better would be to have
771 a tighter connection between block trees and rtl so that this is not
773 if (squeeze_notes (&b
->head
, &b
->end
))
776 /* Scramble the insn chain. */
777 reorder_insns_nobb (b
->head
, b
->end
, a
->end
);
779 /* Restore the real end of b. */
783 fprintf (rtl_dump_file
, "Moved block %d after %d and merged.\n",
786 /* Now blocks A and B are contiguous. Merge them. */
787 merge_blocks_nomove (a
, b
);
790 /* Attempt to merge basic blocks that are potentially non-adjacent.
791 Return NULL iff the attempt failed, otherwise return basic block
792 where cleanup_cfg should continue. Because the merging commonly
793 moves basic block away or introduces another optimization
794 possiblity, return basic block just before B so cleanup_cfg don't
797 It may be good idea to return basic block before C in the case
798 C has been moved after B and originally appeared earlier in the
799 insn seqeunce, but we have no infromation available about the
800 relative ordering of these two. Hopefully it is not too common. */
803 merge_blocks (e
, b
, c
, mode
)
809 /* If C has a tail recursion label, do not merge. There is no
810 edge recorded from the call_placeholder back to this label, as
811 that would make optimize_sibling_and_tail_recursive_calls more
812 complex for no gain. */
813 if ((mode
& CLEANUP_PRE_SIBCALL
)
814 && GET_CODE (c
->head
) == CODE_LABEL
815 && tail_recursion_label_p (c
->head
))
818 /* If B has a fallthru edge to C, no need to move anything. */
819 if (e
->flags
& EDGE_FALLTHRU
)
821 int b_index
= b
->index
, c_index
= c
->index
;
822 merge_blocks_nomove (b
, c
);
823 update_forwarder_flag (b
);
826 fprintf (rtl_dump_file
, "Merged %d and %d without moving.\n",
829 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
832 /* Otherwise we will need to move code around. Do that only if expensive
833 transformations are allowed. */
834 else if (mode
& CLEANUP_EXPENSIVE
)
836 edge tmp_edge
, b_fallthru_edge
;
837 bool c_has_outgoing_fallthru
;
838 bool b_has_incoming_fallthru
;
840 /* Avoid overactive code motion, as the forwarder blocks should be
841 eliminated by edge redirection instead. One exception might have
842 been if B is a forwarder block and C has no fallthru edge, but
843 that should be cleaned up by bb-reorder instead. */
844 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
847 /* We must make sure to not munge nesting of lexical blocks,
848 and loop notes. This is done by squeezing out all the notes
849 and leaving them there to lie. Not ideal, but functional. */
851 for (tmp_edge
= c
->succ
; tmp_edge
; tmp_edge
= tmp_edge
->succ_next
)
852 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
855 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
857 for (tmp_edge
= b
->pred
; tmp_edge
; tmp_edge
= tmp_edge
->pred_next
)
858 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
861 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
862 b_fallthru_edge
= tmp_edge
;
865 next
= next
->prev_bb
;
867 /* Otherwise, we're going to try to move C after B. If C does
868 not have an outgoing fallthru, then it can be moved
869 immediately after B without introducing or modifying jumps. */
870 if (! c_has_outgoing_fallthru
)
872 merge_blocks_move_successor_nojumps (b
, c
);
873 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
876 /* If B does not have an incoming fallthru, then it can be moved
877 immediately before C without introducing or modifying jumps.
878 C cannot be the first block, so we do not have to worry about
879 accessing a non-existent block. */
881 if (b_has_incoming_fallthru
)
885 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
887 bb
= force_nonfallthru (b_fallthru_edge
);
889 notice_new_block (bb
);
892 merge_blocks_move_predecessor_nojumps (b
, c
);
893 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
900 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
903 insns_match_p (mode
, i1
, i2
)
904 int mode ATTRIBUTE_UNUSED
;
909 /* Verify that I1 and I2 are equivalent. */
910 if (GET_CODE (i1
) != GET_CODE (i2
))
916 if (GET_CODE (p1
) != GET_CODE (p2
))
919 /* If this is a CALL_INSN, compare register usage information.
920 If we don't check this on stack register machines, the two
921 CALL_INSNs might be merged leaving reg-stack.c with mismatching
922 numbers of stack registers in the same basic block.
923 If we don't check this on machines with delay slots, a delay slot may
924 be filled that clobbers a parameter expected by the subroutine.
926 ??? We take the simple route for now and assume that if they're
927 equal, they were constructed identically. */
929 if (GET_CODE (i1
) == CALL_INSN
930 && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
931 CALL_INSN_FUNCTION_USAGE (i2
))
932 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
)))
936 /* If cross_jump_death_matters is not 0, the insn's mode
937 indicates whether or not the insn contains any stack-like
940 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
942 /* If register stack conversion has already been done, then
943 death notes must also be compared before it is certain that
944 the two instruction streams match. */
947 HARD_REG_SET i1_regset
, i2_regset
;
949 CLEAR_HARD_REG_SET (i1_regset
);
950 CLEAR_HARD_REG_SET (i2_regset
);
952 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
953 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
954 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
956 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
957 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
958 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
960 GO_IF_HARD_REG_EQUAL (i1_regset
, i2_regset
, done
);
970 ? ! rtx_renumbered_equal_p (p1
, p2
) : ! rtx_equal_p (p1
, p2
))
972 /* The following code helps take care of G++ cleanups. */
973 rtx equiv1
= find_reg_equal_equiv_note (i1
);
974 rtx equiv2
= find_reg_equal_equiv_note (i2
);
977 /* If the equivalences are not to a constant, they may
978 reference pseudos that no longer exist, so we can't
980 && (! reload_completed
981 || (CONSTANT_P (XEXP (equiv1
, 0))
982 && rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))))
984 rtx s1
= single_set (i1
);
985 rtx s2
= single_set (i2
);
986 if (s1
!= 0 && s2
!= 0
987 && rtx_renumbered_equal_p (SET_DEST (s1
), SET_DEST (s2
)))
989 validate_change (i1
, &SET_SRC (s1
), XEXP (equiv1
, 0), 1);
990 validate_change (i2
, &SET_SRC (s2
), XEXP (equiv2
, 0), 1);
991 if (! rtx_renumbered_equal_p (p1
, p2
))
993 else if (apply_change_group ())
1004 /* Look through the insns at the end of BB1 and BB2 and find the longest
1005 sequence that are equivalent. Store the first insns for that sequence
1006 in *F1 and *F2 and return the sequence length.
1008 To simplify callers of this function, if the blocks match exactly,
1009 store the head of the blocks in *F1 and *F2. */
1012 flow_find_cross_jump (mode
, bb1
, bb2
, f1
, f2
)
1013 int mode ATTRIBUTE_UNUSED
;
1014 basic_block bb1
, bb2
;
1017 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
1020 /* Skip simple jumps at the end of the blocks. Complex jumps still
1021 need to be compared for equivalence, which we'll do below. */
1024 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
1026 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1029 i1
= PREV_INSN (i1
);
1034 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1037 /* Count everything except for unconditional jump as insn. */
1038 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1040 i2
= PREV_INSN (i2
);
1046 while (!active_insn_p (i1
) && i1
!= bb1
->head
)
1047 i1
= PREV_INSN (i1
);
1049 while (!active_insn_p (i2
) && i2
!= bb2
->head
)
1050 i2
= PREV_INSN (i2
);
1052 if (i1
== bb1
->head
|| i2
== bb2
->head
)
1055 if (!insns_match_p (mode
, i1
, i2
))
1058 /* Don't begin a cross-jump with a USE or CLOBBER insn. */
1059 if (active_insn_p (i1
))
1061 /* If the merged insns have different REG_EQUAL notes, then
1063 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1064 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1066 if (equiv1
&& !equiv2
)
1067 remove_note (i1
, equiv1
);
1068 else if (!equiv1
&& equiv2
)
1069 remove_note (i2
, equiv2
);
1070 else if (equiv1
&& equiv2
1071 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1073 remove_note (i1
, equiv1
);
1074 remove_note (i2
, equiv2
);
1077 afterlast1
= last1
, afterlast2
= last2
;
1078 last1
= i1
, last2
= i2
;
1082 i1
= PREV_INSN (i1
);
1083 i2
= PREV_INSN (i2
);
1087 /* Don't allow the insn after a compare to be shared by
1088 cross-jumping unless the compare is also shared. */
1089 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1090 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
1093 /* Include preceding notes and labels in the cross-jump. One,
1094 this may bring us to the head of the blocks as requested above.
1095 Two, it keeps line number notes as matched as may be. */
1098 while (last1
!= bb1
->head
&& !active_insn_p (PREV_INSN (last1
)))
1099 last1
= PREV_INSN (last1
);
1101 if (last1
!= bb1
->head
&& GET_CODE (PREV_INSN (last1
)) == CODE_LABEL
)
1102 last1
= PREV_INSN (last1
);
1104 while (last2
!= bb2
->head
&& !active_insn_p (PREV_INSN (last2
)))
1105 last2
= PREV_INSN (last2
);
1107 if (last2
!= bb2
->head
&& GET_CODE (PREV_INSN (last2
)) == CODE_LABEL
)
1108 last2
= PREV_INSN (last2
);
1117 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1118 the branch instruction. This means that if we commonize the control
1119 flow before end of the basic block, the semantic remains unchanged.
1121 We may assume that there exists one edge with a common destination. */
1124 outgoing_edges_match (mode
, bb1
, bb2
)
1129 int nehedges1
= 0, nehedges2
= 0;
1130 edge fallthru1
= 0, fallthru2
= 0;
1133 /* If BB1 has only one successor, we may be looking at either an
1134 unconditional jump, or a fake edge to exit. */
1135 if (bb1
->succ
&& !bb1
->succ
->succ_next
1136 && (bb1
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1137 && (GET_CODE (bb1
->end
) != JUMP_INSN
|| simplejump_p (bb1
->end
)))
1138 return (bb2
->succ
&& !bb2
->succ
->succ_next
1139 && (bb2
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1140 && (GET_CODE (bb2
->end
) != JUMP_INSN
|| simplejump_p (bb2
->end
)));
1142 /* Match conditional jumps - this may get tricky when fallthru and branch
1143 edges are crossed. */
1145 && bb1
->succ
->succ_next
1146 && !bb1
->succ
->succ_next
->succ_next
1147 && any_condjump_p (bb1
->end
)
1148 && onlyjump_p (bb1
->end
))
1150 edge b1
, f1
, b2
, f2
;
1151 bool reverse
, match
;
1152 rtx set1
, set2
, cond1
, cond2
;
1153 enum rtx_code code1
, code2
;
1156 || !bb2
->succ
->succ_next
1157 || bb2
->succ
->succ_next
->succ_next
1158 || !any_condjump_p (bb2
->end
)
1159 || !onlyjump_p (bb2
->end
))
1162 b1
= BRANCH_EDGE (bb1
);
1163 b2
= BRANCH_EDGE (bb2
);
1164 f1
= FALLTHRU_EDGE (bb1
);
1165 f2
= FALLTHRU_EDGE (bb2
);
1167 /* Get around possible forwarders on fallthru edges. Other cases
1168 should be optimized out already. */
1169 if (FORWARDER_BLOCK_P (f1
->dest
))
1170 f1
= f1
->dest
->succ
;
1172 if (FORWARDER_BLOCK_P (f2
->dest
))
1173 f2
= f2
->dest
->succ
;
1175 /* To simplify use of this function, return false if there are
1176 unneeded forwarder blocks. These will get eliminated later
1177 during cleanup_cfg. */
1178 if (FORWARDER_BLOCK_P (f1
->dest
)
1179 || FORWARDER_BLOCK_P (f2
->dest
)
1180 || FORWARDER_BLOCK_P (b1
->dest
)
1181 || FORWARDER_BLOCK_P (b2
->dest
))
1184 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1186 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1191 set1
= pc_set (bb1
->end
);
1192 set2
= pc_set (bb2
->end
);
1193 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1194 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1197 cond1
= XEXP (SET_SRC (set1
), 0);
1198 cond2
= XEXP (SET_SRC (set2
), 0);
1199 code1
= GET_CODE (cond1
);
1201 code2
= reversed_comparison_code (cond2
, bb2
->end
);
1203 code2
= GET_CODE (cond2
);
1205 if (code2
== UNKNOWN
)
1208 /* Verify codes and operands match. */
1209 match
= ((code1
== code2
1210 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1211 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1212 || (code1
== swap_condition (code2
)
1213 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1215 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1218 /* If we return true, we will join the blocks. Which means that
1219 we will only have one branch prediction bit to work with. Thus
1220 we require the existing branches to have probabilities that are
1224 && maybe_hot_bb_p (bb1
)
1225 && maybe_hot_bb_p (bb2
))
1229 if (b1
->dest
== b2
->dest
)
1230 prob2
= b2
->probability
;
1232 /* Do not use f2 probability as f2 may be forwarded. */
1233 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1235 /* Fail if the difference in probabilities is greater than 50%.
1236 This rules out two well-predicted branches with opposite
1238 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1241 fprintf (rtl_dump_file
,
1242 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1243 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1249 if (rtl_dump_file
&& match
)
1250 fprintf (rtl_dump_file
, "Conditionals in bb %i and %i match.\n",
1251 bb1
->index
, bb2
->index
);
1256 /* Generic case - we are seeing a computed jump, table jump or trapping
1259 #ifndef CASE_DROPS_THROUGH
1260 /* Check whether there are tablejumps in the end of BB1 and BB2.
1261 Return true if they are identical. */
1266 if (tablejump_p (bb1
->end
, &label1
, &table1
)
1267 && tablejump_p (bb2
->end
, &label2
, &table2
)
1268 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1270 /* The labels should never be the same rtx. If they really are same
1271 the jump tables are same too. So disable crossjumping of blocks BB1
1272 and BB2 because when deleting the common insns in the end of BB1
1273 by flow_delete_block () the jump table would be deleted too. */
1274 /* If LABEL2 is contained in BB1->END do not do anything
1275 because we would loose information when replacing
1276 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1277 if (label1
!= label2
&& !subrtx_p (label2
, bb1
->end
))
1279 /* Set IDENTICAL to true when the tables are identical. */
1280 bool identical
= false;
1283 p1
= PATTERN (table1
);
1284 p2
= PATTERN (table2
);
1285 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1289 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1290 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1291 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1292 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1297 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1298 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1307 /* Temporarily replace references to LABEL1 with LABEL2
1308 in BB1->END so that we could compare the instructions. */
1311 for_each_rtx (&bb1
->end
, replace_label
, &rr
);
1313 match
= insns_match_p (mode
, bb1
->end
, bb2
->end
);
1314 if (rtl_dump_file
&& match
)
1315 fprintf (rtl_dump_file
,
1316 "Tablejumps in bb %i and %i match.\n",
1317 bb1
->index
, bb2
->index
);
1319 /* Set the original label in BB1->END because when deleting
1320 a block whose end is a tablejump, the tablejump referenced
1321 from the instruction is deleted too. */
1324 for_each_rtx (&bb1
->end
, replace_label
, &rr
);
1334 /* First ensure that the instructions match. There may be many outgoing
1335 edges so this test is generally cheaper. */
1336 if (!insns_match_p (mode
, bb1
->end
, bb2
->end
))
1339 /* Search the outgoing edges, ensure that the counts do match, find possible
1340 fallthru and exception handling edges since these needs more
1342 for (e1
= bb1
->succ
, e2
= bb2
->succ
; e1
&& e2
;
1343 e1
= e1
->succ_next
, e2
= e2
->succ_next
)
1345 if (e1
->flags
& EDGE_EH
)
1348 if (e2
->flags
& EDGE_EH
)
1351 if (e1
->flags
& EDGE_FALLTHRU
)
1353 if (e2
->flags
& EDGE_FALLTHRU
)
1357 /* If number of edges of various types does not match, fail. */
1359 || nehedges1
!= nehedges2
1360 || (fallthru1
!= 0) != (fallthru2
!= 0))
1363 /* fallthru edges must be forwarded to the same destination. */
1366 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1367 ? fallthru1
->dest
->succ
->dest
: fallthru1
->dest
);
1368 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1369 ? fallthru2
->dest
->succ
->dest
: fallthru2
->dest
);
1375 /* In case we do have EH edges, ensure we are in the same region. */
1378 rtx n1
= find_reg_note (bb1
->end
, REG_EH_REGION
, 0);
1379 rtx n2
= find_reg_note (bb2
->end
, REG_EH_REGION
, 0);
1381 if (XEXP (n1
, 0) != XEXP (n2
, 0))
1385 /* We don't need to match the rest of edges as above checks should be enought
1386 to ensure that they are equivalent. */
1390 /* E1 and E2 are edges with the same destination block. Search their
1391 predecessors for common code. If found, redirect control flow from
1392 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1395 try_crossjump_to_edge (mode
, e1
, e2
)
1400 basic_block src1
= e1
->src
, src2
= e2
->src
;
1401 basic_block redirect_to
, redirect_from
, to_remove
;
1402 rtx newpos1
, newpos2
;
1405 /* Search backward through forwarder blocks. We don't need to worry
1406 about multiple entry or chained forwarders, as they will be optimized
1407 away. We do this to look past the unconditional jump following a
1408 conditional jump that is required due to the current CFG shape. */
1410 && !src1
->pred
->pred_next
1411 && FORWARDER_BLOCK_P (src1
))
1412 e1
= src1
->pred
, src1
= e1
->src
;
1415 && !src2
->pred
->pred_next
1416 && FORWARDER_BLOCK_P (src2
))
1417 e2
= src2
->pred
, src2
= e2
->src
;
1419 /* Nothing to do if we reach ENTRY, or a common source block. */
1420 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1425 /* Seeing more than 1 forwarder blocks would confuse us later... */
1426 if (FORWARDER_BLOCK_P (e1
->dest
)
1427 && FORWARDER_BLOCK_P (e1
->dest
->succ
->dest
))
1430 if (FORWARDER_BLOCK_P (e2
->dest
)
1431 && FORWARDER_BLOCK_P (e2
->dest
->succ
->dest
))
1434 /* Likewise with dead code (possibly newly created by the other optimizations
1436 if (!src1
->pred
|| !src2
->pred
)
1439 /* Look for the common insn sequence, part the first ... */
1440 if (!outgoing_edges_match (mode
, src1
, src2
))
1443 /* ... and part the second. */
1444 nmatch
= flow_find_cross_jump (mode
, src1
, src2
, &newpos1
, &newpos2
);
1448 #ifndef CASE_DROPS_THROUGH
1449 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1451 If we have tablejumps in the end of SRC1 and SRC2
1452 they have been already compared for equivalence in outgoing_edges_match ()
1453 so replace the references to TABLE1 by references to TABLE2. */
1458 if (tablejump_p (src1
->end
, &label1
, &table1
)
1459 && tablejump_p (src2
->end
, &label2
, &table2
)
1460 && label1
!= label2
)
1465 /* Replace references to LABEL1 with LABEL2. */
1468 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1470 /* Do not replace the label in SRC1->END because when deleting
1471 a block whose end is a tablejump, the tablejump referenced
1472 from the instruction is deleted too. */
1473 if (insn
!= src1
->end
)
1474 for_each_rtx (&insn
, replace_label
, &rr
);
1480 /* Avoid splitting if possible. */
1481 if (newpos2
== src2
->head
)
1486 fprintf (rtl_dump_file
, "Splitting bb %i before %i insns\n",
1487 src2
->index
, nmatch
);
1488 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1492 fprintf (rtl_dump_file
,
1493 "Cross jumping from bb %i to bb %i; %i common insns\n",
1494 src1
->index
, src2
->index
, nmatch
);
1496 redirect_to
->count
+= src1
->count
;
1497 redirect_to
->frequency
+= src1
->frequency
;
1498 /* We may have some registers visible trought the block. */
1499 redirect_to
->flags
|= BB_DIRTY
;
1501 /* Recompute the frequencies and counts of outgoing edges. */
1502 for (s
= redirect_to
->succ
; s
; s
= s
->succ_next
)
1505 basic_block d
= s
->dest
;
1507 if (FORWARDER_BLOCK_P (d
))
1510 for (s2
= src1
->succ
; ; s2
= s2
->succ_next
)
1512 basic_block d2
= s2
->dest
;
1513 if (FORWARDER_BLOCK_P (d2
))
1514 d2
= d2
->succ
->dest
;
1519 s
->count
+= s2
->count
;
1521 /* Take care to update possible forwarder blocks. We verified
1522 that there is no more than one in the chain, so we can't run
1523 into infinite loop. */
1524 if (FORWARDER_BLOCK_P (s
->dest
))
1526 s
->dest
->succ
->count
+= s2
->count
;
1527 s
->dest
->count
+= s2
->count
;
1528 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1531 if (FORWARDER_BLOCK_P (s2
->dest
))
1533 s2
->dest
->succ
->count
-= s2
->count
;
1534 if (s2
->dest
->succ
->count
< 0)
1535 s2
->dest
->succ
->count
= 0;
1536 s2
->dest
->count
-= s2
->count
;
1537 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1538 if (s2
->dest
->frequency
< 0)
1539 s2
->dest
->frequency
= 0;
1540 if (s2
->dest
->count
< 0)
1541 s2
->dest
->count
= 0;
1544 if (!redirect_to
->frequency
&& !src1
->frequency
)
1545 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
1548 = ((s
->probability
* redirect_to
->frequency
+
1549 s2
->probability
* src1
->frequency
)
1550 / (redirect_to
->frequency
+ src1
->frequency
));
1553 update_br_prob_note (redirect_to
);
1555 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1557 /* Skip possible basic block header. */
1558 if (GET_CODE (newpos1
) == CODE_LABEL
)
1559 newpos1
= NEXT_INSN (newpos1
);
1561 if (GET_CODE (newpos1
) == NOTE
)
1562 newpos1
= NEXT_INSN (newpos1
);
1564 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
1565 to_remove
= redirect_from
->succ
->dest
;
1567 redirect_edge_and_branch_force (redirect_from
->succ
, redirect_to
);
1568 flow_delete_block (to_remove
);
1570 update_forwarder_flag (redirect_from
);
1575 /* Search the predecessors of BB for common insn sequences. When found,
1576 share code between them by redirecting control flow. Return true if
1577 any changes made. */
1580 try_crossjump_bb (mode
, bb
)
1584 edge e
, e2
, nexte2
, nexte
, fallthru
;
1588 /* Nothing to do if there is not at least two incoming edges. */
1589 if (!bb
->pred
|| !bb
->pred
->pred_next
)
1592 /* It is always cheapest to redirect a block that ends in a branch to
1593 a block that falls through into BB, as that adds no branches to the
1594 program. We'll try that combination first. */
1596 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
1597 for (e
= bb
->pred
; e
; e
= e
->pred_next
, n
++)
1599 if (e
->flags
& EDGE_FALLTHRU
)
1606 for (e
= bb
->pred
; e
; e
= nexte
)
1608 nexte
= e
->pred_next
;
1610 /* As noted above, first try with the fallthru predecessor. */
1613 /* Don't combine the fallthru edge into anything else.
1614 If there is a match, we'll do it the other way around. */
1618 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1626 /* Non-obvious work limiting check: Recognize that we're going
1627 to call try_crossjump_bb on every basic block. So if we have
1628 two blocks with lots of outgoing edges (a switch) and they
1629 share lots of common destinations, then we would do the
1630 cross-jump check once for each common destination.
1632 Now, if the blocks actually are cross-jump candidates, then
1633 all of their destinations will be shared. Which means that
1634 we only need check them for cross-jump candidacy once. We
1635 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1636 choosing to do the check from the block for which the edge
1637 in question is the first successor of A. */
1638 if (e
->src
->succ
!= e
)
1641 for (e2
= bb
->pred
; e2
; e2
= nexte2
)
1643 nexte2
= e2
->pred_next
;
1648 /* We've already checked the fallthru edge above. */
1652 /* The "first successor" check above only prevents multiple
1653 checks of crossjump(A,B). In order to prevent redundant
1654 checks of crossjump(B,A), require that A be the block
1655 with the lowest index. */
1656 if (e
->src
->index
> e2
->src
->index
)
1659 if (try_crossjump_to_edge (mode
, e
, e2
))
1671 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1672 instructions etc. Return nonzero if changes were made. */
1675 try_optimize_cfg (mode
)
1678 bool changed_overall
= false;
1681 basic_block bb
, b
, next
;
1683 if (mode
& CLEANUP_CROSSJUMP
)
1684 add_noreturn_fake_exit_edges ();
1687 update_forwarder_flag (bb
);
1689 if (mode
& CLEANUP_UPDATE_LIFE
)
1692 if (! (* targetm
.cannot_modify_jumps_p
) ())
1694 /* Attempt to merge blocks as made possible by edge removal. If
1695 a block has only one successor, and the successor has only
1696 one predecessor, they may be combined. */
1703 fprintf (rtl_dump_file
,
1704 "\n\ntry_optimize_cfg iteration %i\n\n",
1707 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
1711 bool changed_here
= false;
1713 /* Delete trivially dead basic blocks. */
1714 while (b
->pred
== NULL
)
1718 fprintf (rtl_dump_file
, "Deleting block %i.\n",
1721 flow_delete_block (b
);
1726 /* Remove code labels no longer used. Don't do this
1727 before CALL_PLACEHOLDER is removed, as some branches
1728 may be hidden within. */
1729 if (b
->pred
->pred_next
== NULL
1730 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1731 && !(b
->pred
->flags
& EDGE_COMPLEX
)
1732 && GET_CODE (b
->head
) == CODE_LABEL
1733 && (!(mode
& CLEANUP_PRE_SIBCALL
)
1734 || !tail_recursion_label_p (b
->head
))
1735 /* If the previous block ends with a branch to this
1736 block, we can't delete the label. Normally this
1737 is a condjump that is yet to be simplified, but
1738 if CASE_DROPS_THRU, this can be a tablejump with
1739 some element going to the same place as the
1740 default (fallthru). */
1741 && (b
->pred
->src
== ENTRY_BLOCK_PTR
1742 || GET_CODE (b
->pred
->src
->end
) != JUMP_INSN
1743 || ! label_is_jump_target_p (b
->head
,
1744 b
->pred
->src
->end
)))
1746 rtx label
= b
->head
;
1748 b
->head
= NEXT_INSN (b
->head
);
1749 delete_insn_chain (label
, label
);
1751 fprintf (rtl_dump_file
, "Deleted label in block %i.\n",
1755 /* If we fall through an empty block, we can remove it. */
1756 if (b
->pred
->pred_next
== NULL
1757 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1758 && GET_CODE (b
->head
) != CODE_LABEL
1759 && FORWARDER_BLOCK_P (b
)
1760 /* Note that forwarder_block_p true ensures that
1761 there is a successor for this block. */
1762 && (b
->succ
->flags
& EDGE_FALLTHRU
)
1763 && n_basic_blocks
> 1)
1766 fprintf (rtl_dump_file
,
1767 "Deleting fallthru block %i.\n",
1770 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
1771 redirect_edge_succ_nodup (b
->pred
, b
->succ
->dest
);
1772 flow_delete_block (b
);
1777 if ((s
= b
->succ
) != NULL
1778 && s
->succ_next
== NULL
1779 && !(s
->flags
& EDGE_COMPLEX
)
1780 && (c
= s
->dest
) != EXIT_BLOCK_PTR
1781 && c
->pred
->pred_next
== NULL
1783 /* If the jump insn has side effects,
1784 we can't kill the edge. */
1785 && (GET_CODE (b
->end
) != JUMP_INSN
1786 || simplejump_p (b
->end
))
1787 && (next
= merge_blocks (s
, b
, c
, mode
)))
1790 changed_here
= true;
1793 /* Simplify branch over branch. */
1794 if ((mode
& CLEANUP_EXPENSIVE
) && try_simplify_condjump (b
))
1795 changed_here
= true;
1797 /* If B has a single outgoing edge, but uses a
1798 non-trivial jump instruction without side-effects, we
1799 can either delete the jump entirely, or replace it
1800 with a simple unconditional jump. Use
1801 redirect_edge_and_branch to do the dirty work. */
1803 && ! b
->succ
->succ_next
1804 && b
->succ
->dest
!= EXIT_BLOCK_PTR
1805 && onlyjump_p (b
->end
)
1806 && redirect_edge_and_branch (b
->succ
, b
->succ
->dest
))
1808 update_forwarder_flag (b
);
1809 changed_here
= true;
1812 /* Simplify branch to branch. */
1813 if (try_forward_edges (mode
, b
))
1814 changed_here
= true;
1816 /* Look for shared code between blocks. */
1817 if ((mode
& CLEANUP_CROSSJUMP
)
1818 && try_crossjump_bb (mode
, b
))
1819 changed_here
= true;
1821 /* Don't get confused by the index shift caused by
1829 if ((mode
& CLEANUP_CROSSJUMP
)
1830 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
1833 #ifdef ENABLE_CHECKING
1835 verify_flow_info ();
1838 changed_overall
|= changed
;
1843 if (mode
& CLEANUP_CROSSJUMP
)
1844 remove_fake_edges ();
1846 clear_aux_for_blocks ();
1848 return changed_overall
;
1851 /* Delete all unreachable basic blocks. */
1854 delete_unreachable_blocks ()
1856 bool changed
= false;
1857 basic_block b
, next_bb
;
1859 find_unreachable_blocks ();
1861 /* Delete all unreachable basic blocks. */
1863 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
; b
= next_bb
)
1865 next_bb
= b
->next_bb
;
1867 if (!(b
->flags
& BB_REACHABLE
))
1869 flow_delete_block (b
);
1875 tidy_fallthru_edges ();
1879 /* Tidy the CFG by deleting unreachable code and whatnot. */
1885 bool changed
= false;
1887 timevar_push (TV_CLEANUP_CFG
);
1888 if (delete_unreachable_blocks ())
1891 /* We've possibly created trivially dead code. Cleanup it right
1892 now to introduce more opportunities for try_optimize_cfg. */
1893 if (!(mode
& (CLEANUP_NO_INSN_DEL
1894 | CLEANUP_UPDATE_LIFE
| CLEANUP_PRE_SIBCALL
))
1895 && !reload_completed
)
1896 delete_trivially_dead_insns (get_insns(), max_reg_num ());
1901 while (try_optimize_cfg (mode
))
1903 delete_unreachable_blocks (), changed
= true;
1904 if (mode
& CLEANUP_UPDATE_LIFE
)
1906 /* Cleaning up CFG introduces more opportunities for dead code
1907 removal that in turn may introduce more opportunities for
1908 cleaning up the CFG. */
1909 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES
,
1911 | PROP_SCAN_DEAD_CODE
1912 | PROP_KILL_DEAD_CODE
1916 else if (!(mode
& (CLEANUP_NO_INSN_DEL
| CLEANUP_PRE_SIBCALL
))
1917 && (mode
& CLEANUP_EXPENSIVE
)
1918 && !reload_completed
)
1920 if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
1925 delete_dead_jumptables ();
1928 /* Kill the data we won't maintain. */
1929 free_EXPR_LIST_list (&label_value_list
);
1930 timevar_pop (TV_CLEANUP_CFG
);