1 /* Control flow optimization code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This file contains optimizer of the control flow. The main entry point is
23 cleanup_cfg. Following optimizations are performed:
25 - Unreachable blocks removal
26 - Edge forwarding (edge to the forwarder block is forwarded to its
27 successor. Simplification of the branch instruction is performed by
28 underlying infrastructure so branch can be converted to simplejump or
30 - Cross jumping (tail merging)
31 - Conditional jump-around-simplejump simplification
32 - Basic block merging. */
36 #include "coretypes.h"
39 #include "hard-reg-set.h"
40 #include "basic-block.h"
43 #include "insn-config.h"
52 #include "cfglayout.h"
55 /* cleanup_cfg maintains following flags for each basic block. */
59 /* Set if BB is the forwarder block to avoid too many
60 forwarder_block_p calls. */
61 BB_FORWARDER_BLOCK
= 1,
62 BB_NONTHREADABLE_BLOCK
= 2
65 #define BB_FLAGS(BB) (enum bb_flags) (BB)->aux
66 #define BB_SET_FLAG(BB, FLAG) \
67 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG))
68 #define BB_CLEAR_FLAG(BB, FLAG) \
69 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG))
71 #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
73 /* Set to true when we are running first pass of try_optimize_cfg loop. */
74 static bool first_pass
;
75 static bool try_crossjump_to_edge (int, edge
, edge
);
76 static bool try_crossjump_bb (int, basic_block
);
77 static bool outgoing_edges_match (int, basic_block
, basic_block
);
78 static int flow_find_cross_jump (int, basic_block
, basic_block
, rtx
*, rtx
*);
79 static bool insns_match_p (int, rtx
, rtx
);
81 static void merge_blocks_move_predecessor_nojumps (basic_block
, basic_block
);
82 static void merge_blocks_move_successor_nojumps (basic_block
, basic_block
);
83 static bool try_optimize_cfg (int);
84 static bool try_simplify_condjump (basic_block
);
85 static bool try_forward_edges (int, basic_block
);
86 static edge
thread_jump (int, edge
, basic_block
);
87 static bool mark_effect (rtx
, bitmap
);
88 static void notice_new_block (basic_block
);
89 static void update_forwarder_flag (basic_block
);
90 static int mentions_nonequal_regs (rtx
*, void *);
91 static void merge_memattrs (rtx
, rtx
);
93 /* Set flags for newly created block. */
96 notice_new_block (basic_block bb
)
101 if (forwarder_block_p (bb
))
102 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
105 /* Recompute forwarder flag after block has been modified. */
108 update_forwarder_flag (basic_block bb
)
110 if (forwarder_block_p (bb
))
111 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
113 BB_CLEAR_FLAG (bb
, BB_FORWARDER_BLOCK
);
116 /* Simplify a conditional jump around an unconditional jump.
117 Return true if something changed. */
120 try_simplify_condjump (basic_block cbranch_block
)
122 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
123 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
126 /* Verify that there are exactly two successors. */
127 if (EDGE_COUNT (cbranch_block
->succ
) != 2)
130 /* Verify that we've got a normal conditional branch at the end
132 cbranch_insn
= BB_END (cbranch_block
);
133 if (!any_condjump_p (cbranch_insn
))
136 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
137 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
139 /* The next block must not have multiple predecessors, must not
140 be the last block in the function, and must contain just the
141 unconditional jump. */
142 jump_block
= cbranch_fallthru_edge
->dest
;
143 if (EDGE_COUNT (jump_block
->pred
) >= 2
144 || jump_block
->next_bb
== EXIT_BLOCK_PTR
145 || !FORWARDER_BLOCK_P (jump_block
))
147 jump_dest_block
= EDGE_0 (jump_block
->succ
)->dest
;
149 /* If we are partitioning hot/cold basic blocks, we don't want to
150 mess up unconditional or indirect jumps that cross between hot
151 and cold sections. */
153 if (flag_reorder_blocks_and_partition
154 && (jump_block
->partition
!= jump_dest_block
->partition
155 || cbranch_jump_edge
->crossing_edge
))
158 /* The conditional branch must target the block after the
159 unconditional branch. */
160 cbranch_dest_block
= cbranch_jump_edge
->dest
;
162 if (cbranch_dest_block
== EXIT_BLOCK_PTR
163 || !can_fallthru (jump_block
, cbranch_dest_block
))
166 /* Invert the conditional branch. */
167 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
171 fprintf (dump_file
, "Simplifying condjump %i around jump %i\n",
172 INSN_UID (cbranch_insn
), INSN_UID (BB_END (jump_block
)));
174 /* Success. Update the CFG to match. Note that after this point
175 the edge variable names appear backwards; the redirection is done
176 this way to preserve edge profile data. */
177 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
179 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
181 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
182 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
183 update_br_prob_note (cbranch_block
);
185 /* Delete the block with the unconditional jump, and clean up the mess. */
186 delete_basic_block (jump_block
);
187 tidy_fallthru_edge (cbranch_jump_edge
);
192 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
193 on register. Used by jump threading. */
196 mark_effect (rtx exp
, regset nonequal
)
200 switch (GET_CODE (exp
))
202 /* In case we do clobber the register, mark it as equal, as we know the
203 value is dead so it don't have to match. */
205 if (REG_P (XEXP (exp
, 0)))
207 dest
= XEXP (exp
, 0);
208 regno
= REGNO (dest
);
209 CLEAR_REGNO_REG_SET (nonequal
, regno
);
210 if (regno
< FIRST_PSEUDO_REGISTER
)
212 int n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
214 CLEAR_REGNO_REG_SET (nonequal
, regno
+ n
);
220 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
222 dest
= SET_DEST (exp
);
227 regno
= REGNO (dest
);
228 SET_REGNO_REG_SET (nonequal
, regno
);
229 if (regno
< FIRST_PSEUDO_REGISTER
)
231 int n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
233 SET_REGNO_REG_SET (nonequal
, regno
+ n
);
242 /* Return nonzero if X is a register set in regset DATA.
243 Called via for_each_rtx. */
245 mentions_nonequal_regs (rtx
*x
, void *data
)
247 regset nonequal
= (regset
) data
;
253 if (REGNO_REG_SET_P (nonequal
, regno
))
255 if (regno
< FIRST_PSEUDO_REGISTER
)
257 int n
= hard_regno_nregs
[regno
][GET_MODE (*x
)];
259 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
265 /* Attempt to prove that the basic block B will have no side effects and
266 always continues in the same edge if reached via E. Return the edge
267 if exist, NULL otherwise. */
270 thread_jump (int mode
, edge e
, basic_block b
)
272 rtx set1
, set2
, cond1
, cond2
, insn
;
273 enum rtx_code code1
, code2
, reversed_code2
;
274 bool reverse1
= false;
279 if (BB_FLAGS (b
) & BB_NONTHREADABLE_BLOCK
)
282 /* At the moment, we do handle only conditional jumps, but later we may
283 want to extend this code to tablejumps and others. */
284 if (EDGE_COUNT (e
->src
->succ
) != 2)
286 if (EDGE_COUNT (b
->succ
) != 2)
288 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
292 /* Second branch must end with onlyjump, as we will eliminate the jump. */
293 if (!any_condjump_p (BB_END (e
->src
)))
296 if (!any_condjump_p (BB_END (b
)) || !onlyjump_p (BB_END (b
)))
298 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
302 set1
= pc_set (BB_END (e
->src
));
303 set2
= pc_set (BB_END (b
));
304 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
305 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
308 cond1
= XEXP (SET_SRC (set1
), 0);
309 cond2
= XEXP (SET_SRC (set2
), 0);
311 code1
= reversed_comparison_code (cond1
, BB_END (e
->src
));
313 code1
= GET_CODE (cond1
);
315 code2
= GET_CODE (cond2
);
316 reversed_code2
= reversed_comparison_code (cond2
, BB_END (b
));
318 if (!comparison_dominates_p (code1
, code2
)
319 && !comparison_dominates_p (code1
, reversed_code2
))
322 /* Ensure that the comparison operators are equivalent.
323 ??? This is far too pessimistic. We should allow swapped operands,
324 different CCmodes, or for example comparisons for interval, that
325 dominate even when operands are not equivalent. */
326 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
327 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
330 /* Short circuit cases where block B contains some side effects, as we can't
332 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
));
333 insn
= NEXT_INSN (insn
))
334 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
336 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
342 /* First process all values computed in the source basic block. */
343 for (insn
= NEXT_INSN (BB_HEAD (e
->src
)); insn
!= NEXT_INSN (BB_END (e
->src
));
344 insn
= NEXT_INSN (insn
))
346 cselib_process_insn (insn
);
348 nonequal
= BITMAP_XMALLOC();
349 CLEAR_REG_SET (nonequal
);
351 /* Now assume that we've continued by the edge E to B and continue
352 processing as if it were same basic block.
353 Our goal is to prove that whole block is an NOOP. */
355 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
)) && !failed
;
356 insn
= NEXT_INSN (insn
))
360 rtx pat
= PATTERN (insn
);
362 if (GET_CODE (pat
) == PARALLEL
)
364 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
365 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
368 failed
|= mark_effect (pat
, nonequal
);
371 cselib_process_insn (insn
);
374 /* Later we should clear nonequal of dead registers. So far we don't
375 have life information in cfg_cleanup. */
378 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
382 /* cond2 must not mention any register that is not equal to the
384 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
387 /* In case liveness information is available, we need to prove equivalence
388 only of the live values. */
389 if (mode
& CLEANUP_UPDATE_LIFE
)
390 AND_REG_SET (nonequal
, b
->global_live_at_end
);
392 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, goto failed_exit
;);
394 BITMAP_XFREE (nonequal
);
396 if ((comparison_dominates_p (code1
, code2
) != 0)
397 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
398 return BRANCH_EDGE (b
);
400 return FALLTHRU_EDGE (b
);
403 BITMAP_XFREE (nonequal
);
408 /* Attempt to forward edges leaving basic block B.
409 Return true if successful. */
412 try_forward_edges (int mode
, basic_block b
)
414 bool changed
= false;
415 edge e
, *threaded_edges
= NULL
;
418 /* If we are partitioning hot/cold basic blocks, we don't want to
419 mess up unconditional or indirect jumps that cross between hot
420 and cold sections. */
422 if (flag_reorder_blocks_and_partition
423 && find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
426 FOR_EACH_EDGE (e
, b
->succ
, ix
)
428 basic_block target
, first
;
430 bool threaded
= false;
431 int nthreaded_edges
= 0;
432 bool may_thread
= first_pass
| (b
->flags
& BB_DIRTY
);
434 /* Skip complex edges because we don't know how to update them.
436 Still handle fallthru edges, as we can succeed to forward fallthru
437 edge to the same place as the branch edge of conditional branch
438 and turn conditional branch to an unconditional branch. */
439 if (e
->flags
& EDGE_COMPLEX
)
442 target
= first
= e
->dest
;
445 while (counter
< n_basic_blocks
)
447 basic_block new_target
= NULL
;
448 bool new_target_threaded
= false;
449 may_thread
|= target
->flags
& BB_DIRTY
;
451 if (FORWARDER_BLOCK_P (target
)
452 && EDGE_0 (target
->succ
)->dest
!= EXIT_BLOCK_PTR
)
454 /* Bypass trivial infinite loops. */
455 if (target
== EDGE_0 (target
->succ
)->dest
)
456 counter
= n_basic_blocks
;
457 new_target
= EDGE_0 (target
->succ
)->dest
;
460 /* Allow to thread only over one edge at time to simplify updating
462 else if ((mode
& CLEANUP_THREADING
) && may_thread
)
464 edge t
= thread_jump (mode
, e
, target
);
468 threaded_edges
= xmalloc (sizeof (*threaded_edges
)
474 /* Detect an infinite loop across blocks not
475 including the start block. */
476 for (i
= 0; i
< nthreaded_edges
; ++i
)
477 if (threaded_edges
[i
] == t
)
479 if (i
< nthreaded_edges
)
481 counter
= n_basic_blocks
;
486 /* Detect an infinite loop across the start block. */
490 if (nthreaded_edges
>= n_basic_blocks
)
492 threaded_edges
[nthreaded_edges
++] = t
;
494 new_target
= t
->dest
;
495 new_target_threaded
= true;
502 /* Avoid killing of loop pre-headers, as it is the place loop
503 optimizer wants to hoist code to.
505 For fallthru forwarders, the LOOP_BEG note must appear between
506 the header of block and CODE_LABEL of the loop, for non forwarders
507 it must appear before the JUMP_INSN. */
508 if ((mode
& CLEANUP_PRE_LOOP
) && optimize
)
510 rtx insn
= (EDGE_0 (target
->succ
)->flags
& EDGE_FALLTHRU
511 ? BB_HEAD (target
) : prev_nonnote_insn (BB_END (target
)));
514 insn
= NEXT_INSN (insn
);
516 for (; insn
&& !LABEL_P (insn
) && !INSN_P (insn
);
517 insn
= NEXT_INSN (insn
))
519 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
525 /* Do not clean up branches to just past the end of a loop
526 at this time; it can mess up the loop optimizer's
527 recognition of some patterns. */
529 insn
= PREV_INSN (BB_HEAD (target
));
530 if (insn
&& NOTE_P (insn
)
531 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
537 threaded
|= new_target_threaded
;
540 if (counter
>= n_basic_blocks
)
543 fprintf (dump_file
, "Infinite loop in BB %i.\n",
546 else if (target
== first
)
547 ; /* We didn't do anything. */
550 /* Save the values now, as the edge may get removed. */
551 gcov_type edge_count
= e
->count
;
552 int edge_probability
= e
->probability
;
556 /* Don't force if target is exit block. */
557 if (threaded
&& target
!= EXIT_BLOCK_PTR
)
559 notice_new_block (redirect_edge_and_branch_force (e
, target
));
561 fprintf (dump_file
, "Conditionals threaded.\n");
563 else if (!redirect_edge_and_branch (e
, target
))
567 "Forwarding edge %i->%i to %i failed.\n",
568 b
->index
, e
->dest
->index
, target
->index
);
572 /* We successfully forwarded the edge. Now update profile
573 data: for each edge we traversed in the chain, remove
574 the original edge's execution count. */
575 edge_frequency
= ((edge_probability
* b
->frequency
576 + REG_BR_PROB_BASE
/ 2)
579 if (!FORWARDER_BLOCK_P (b
) && forwarder_block_p (b
))
580 BB_SET_FLAG (b
, BB_FORWARDER_BLOCK
);
586 first
->count
-= edge_count
;
587 if (first
->count
< 0)
589 first
->frequency
-= edge_frequency
;
590 if (first
->frequency
< 0)
591 first
->frequency
= 0;
592 if (EDGE_COUNT (first
->succ
) > 1)
596 if (n
>= nthreaded_edges
)
598 t
= threaded_edges
[n
++];
601 if (first
->frequency
)
602 prob
= edge_frequency
* REG_BR_PROB_BASE
/ first
->frequency
;
605 if (prob
> t
->probability
)
606 prob
= t
->probability
;
607 t
->probability
-= prob
;
608 prob
= REG_BR_PROB_BASE
- prob
;
611 EDGE_0 (first
->succ
)->probability
= REG_BR_PROB_BASE
;
612 EDGE_1 (first
->succ
)->probability
= 0;
617 FOR_EACH_EDGE (e
, first
->succ
, ix
)
618 e
->probability
= ((e
->probability
* REG_BR_PROB_BASE
)
621 update_br_prob_note (first
);
625 /* It is possible that as the result of
626 threading we've removed edge as it is
627 threaded to the fallthru edge. Avoid
628 getting out of sync. */
629 if (n
< nthreaded_edges
630 && first
== threaded_edges
[n
]->src
)
632 t
= EDGE_0 (first
->succ
);
635 t
->count
-= edge_count
;
640 while (first
!= target
);
647 free (threaded_edges
);
652 /* Blocks A and B are to be merged into a single block. A has no incoming
653 fallthru edge, so it can be moved before B without adding or modifying
654 any jumps (aside from the jump from A to B). */
657 merge_blocks_move_predecessor_nojumps (basic_block a
, basic_block b
)
661 /* If we are partitioning hot/cold basic blocks, we don't want to
662 mess up unconditional or indirect jumps that cross between hot
663 and cold sections. */
665 if (flag_reorder_blocks_and_partition
666 && (a
->partition
!= b
->partition
667 || find_reg_note (BB_END (a
), REG_CROSSING_JUMP
, NULL_RTX
)))
670 barrier
= next_nonnote_insn (BB_END (a
));
671 if (!BARRIER_P (barrier
))
673 delete_insn (barrier
);
675 /* Move block and loop notes out of the chain so that we do not
678 ??? A better solution would be to squeeze out all the non-nested notes
679 and adjust the block trees appropriately. Even better would be to have
680 a tighter connection between block trees and rtl so that this is not
682 if (squeeze_notes (&BB_HEAD (a
), &BB_END (a
)))
685 /* Scramble the insn chain. */
686 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
687 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
688 a
->flags
|= BB_DIRTY
;
691 fprintf (dump_file
, "Moved block %d before %d and merged.\n",
694 /* Swap the records for the two blocks around. */
697 link_block (a
, b
->prev_bb
);
699 /* Now blocks A and B are contiguous. Merge them. */
703 /* Blocks A and B are to be merged into a single block. B has no outgoing
704 fallthru edge, so it can be moved after A without adding or modifying
705 any jumps (aside from the jump from A to B). */
708 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
710 rtx barrier
, real_b_end
;
713 /* If we are partitioning hot/cold basic blocks, we don't want to
714 mess up unconditional or indirect jumps that cross between hot
715 and cold sections. */
717 if (flag_reorder_blocks_and_partition
718 && (find_reg_note (BB_END (a
), REG_CROSSING_JUMP
, NULL_RTX
)
719 || a
->partition
!= b
->partition
))
722 real_b_end
= BB_END (b
);
724 /* If there is a jump table following block B temporarily add the jump table
725 to block B so that it will also be moved to the correct location. */
726 if (tablejump_p (BB_END (b
), &label
, &table
)
727 && prev_active_insn (label
) == BB_END (b
))
732 /* There had better have been a barrier there. Delete it. */
733 barrier
= NEXT_INSN (BB_END (b
));
734 if (barrier
&& BARRIER_P (barrier
))
735 delete_insn (barrier
);
737 /* Move block and loop notes out of the chain so that we do not
740 ??? A better solution would be to squeeze out all the non-nested notes
741 and adjust the block trees appropriately. Even better would be to have
742 a tighter connection between block trees and rtl so that this is not
744 if (squeeze_notes (&BB_HEAD (b
), &BB_END (b
)))
747 /* Scramble the insn chain. */
748 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
750 /* Restore the real end of b. */
751 BB_END (b
) = real_b_end
;
754 fprintf (dump_file
, "Moved block %d after %d and merged.\n",
757 /* Now blocks A and B are contiguous. Merge them. */
761 /* Attempt to merge basic blocks that are potentially non-adjacent.
762 Return NULL iff the attempt failed, otherwise return basic block
763 where cleanup_cfg should continue. Because the merging commonly
764 moves basic block away or introduces another optimization
765 possibility, return basic block just before B so cleanup_cfg don't
768 It may be good idea to return basic block before C in the case
769 C has been moved after B and originally appeared earlier in the
770 insn sequence, but we have no information available about the
771 relative ordering of these two. Hopefully it is not too common. */
774 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
778 /* If we are partitioning hot/cold basic blocks, we don't want to
779 mess up unconditional or indirect jumps that cross between hot
780 and cold sections. */
782 if (flag_reorder_blocks_and_partition
783 && (find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
)
784 || find_reg_note (BB_END (c
), REG_CROSSING_JUMP
, NULL_RTX
)
785 || b
->partition
!= c
->partition
))
790 /* If B has a fallthru edge to C, no need to move anything. */
791 if (e
->flags
& EDGE_FALLTHRU
)
793 int b_index
= b
->index
, c_index
= c
->index
;
795 update_forwarder_flag (b
);
798 fprintf (dump_file
, "Merged %d and %d without moving.\n",
801 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
804 /* Otherwise we will need to move code around. Do that only if expensive
805 transformations are allowed. */
806 else if (mode
& CLEANUP_EXPENSIVE
)
808 edge tmp_edge
, b_fallthru_edge
;
809 bool c_has_outgoing_fallthru
;
810 bool b_has_incoming_fallthru
;
813 /* Avoid overactive code motion, as the forwarder blocks should be
814 eliminated by edge redirection instead. One exception might have
815 been if B is a forwarder block and C has no fallthru edge, but
816 that should be cleaned up by bb-reorder instead. */
817 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
820 /* We must make sure to not munge nesting of lexical blocks,
821 and loop notes. This is done by squeezing out all the notes
822 and leaving them there to lie. Not ideal, but functional. */
824 FOR_EACH_EDGE (tmp_edge
, c
->succ
, ix
)
825 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
828 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
830 FOR_EACH_EDGE (tmp_edge
, b
->pred
, ix
)
831 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
834 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
835 b_fallthru_edge
= tmp_edge
;
838 next
= next
->prev_bb
;
840 /* Otherwise, we're going to try to move C after B. If C does
841 not have an outgoing fallthru, then it can be moved
842 immediately after B without introducing or modifying jumps. */
843 if (! c_has_outgoing_fallthru
)
845 merge_blocks_move_successor_nojumps (b
, c
);
846 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
849 /* If B does not have an incoming fallthru, then it can be moved
850 immediately before C without introducing or modifying jumps.
851 C cannot be the first block, so we do not have to worry about
852 accessing a non-existent block. */
854 if (b_has_incoming_fallthru
)
858 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
860 bb
= force_nonfallthru (b_fallthru_edge
);
862 notice_new_block (bb
);
865 merge_blocks_move_predecessor_nojumps (b
, c
);
866 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
873 /* Removes the memory attributes of MEM expression
874 if they are not equal. */
877 merge_memattrs (rtx x
, rtx y
)
886 if (x
== 0 || y
== 0)
891 if (code
!= GET_CODE (y
))
894 if (GET_MODE (x
) != GET_MODE (y
))
897 if (code
== MEM
&& MEM_ATTRS (x
) != MEM_ATTRS (y
))
901 else if (! MEM_ATTRS (y
))
905 if (MEM_ALIAS_SET (x
) != MEM_ALIAS_SET (y
))
907 set_mem_alias_set (x
, 0);
908 set_mem_alias_set (y
, 0);
911 if (! mem_expr_equal_p (MEM_EXPR (x
), MEM_EXPR (y
)))
915 set_mem_offset (x
, 0);
916 set_mem_offset (y
, 0);
918 else if (MEM_OFFSET (x
) != MEM_OFFSET (y
))
920 set_mem_offset (x
, 0);
921 set_mem_offset (y
, 0);
924 set_mem_size (x
, MAX (MEM_SIZE (x
), MEM_SIZE (y
)));
925 set_mem_size (y
, MEM_SIZE (x
));
927 set_mem_align (x
, MIN (MEM_ALIGN (x
), MEM_ALIGN (y
)));
928 set_mem_align (y
, MEM_ALIGN (x
));
932 fmt
= GET_RTX_FORMAT (code
);
933 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
938 /* Two vectors must have the same length. */
939 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
942 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
943 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
948 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
955 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
958 insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
962 /* Verify that I1 and I2 are equivalent. */
963 if (GET_CODE (i1
) != GET_CODE (i2
))
969 if (GET_CODE (p1
) != GET_CODE (p2
))
972 /* If this is a CALL_INSN, compare register usage information.
973 If we don't check this on stack register machines, the two
974 CALL_INSNs might be merged leaving reg-stack.c with mismatching
975 numbers of stack registers in the same basic block.
976 If we don't check this on machines with delay slots, a delay slot may
977 be filled that clobbers a parameter expected by the subroutine.
979 ??? We take the simple route for now and assume that if they're
980 equal, they were constructed identically. */
983 && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
984 CALL_INSN_FUNCTION_USAGE (i2
))
985 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
)))
989 /* If cross_jump_death_matters is not 0, the insn's mode
990 indicates whether or not the insn contains any stack-like
993 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
995 /* If register stack conversion has already been done, then
996 death notes must also be compared before it is certain that
997 the two instruction streams match. */
1000 HARD_REG_SET i1_regset
, i2_regset
;
1002 CLEAR_HARD_REG_SET (i1_regset
);
1003 CLEAR_HARD_REG_SET (i2_regset
);
1005 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
1006 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1007 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
1009 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
1010 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1011 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
1013 GO_IF_HARD_REG_EQUAL (i1_regset
, i2_regset
, done
);
1022 if (reload_completed
1023 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
1026 /* Do not do EQUIV substitution after reload. First, we're undoing the
1027 work of reload_cse. Second, we may be undoing the work of the post-
1028 reload splitting pass. */
1029 /* ??? Possibly add a new phase switch variable that can be used by
1030 targets to disallow the troublesome insns after splitting. */
1031 if (!reload_completed
)
1033 /* The following code helps take care of G++ cleanups. */
1034 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1035 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1037 if (equiv1
&& equiv2
1038 /* If the equivalences are not to a constant, they may
1039 reference pseudos that no longer exist, so we can't
1041 && (! reload_completed
1042 || (CONSTANT_P (XEXP (equiv1
, 0))
1043 && rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))))
1045 rtx s1
= single_set (i1
);
1046 rtx s2
= single_set (i2
);
1047 if (s1
!= 0 && s2
!= 0
1048 && rtx_renumbered_equal_p (SET_DEST (s1
), SET_DEST (s2
)))
1050 validate_change (i1
, &SET_SRC (s1
), XEXP (equiv1
, 0), 1);
1051 validate_change (i2
, &SET_SRC (s2
), XEXP (equiv2
, 0), 1);
1052 if (! rtx_renumbered_equal_p (p1
, p2
))
1054 else if (apply_change_group ())
1063 /* Look through the insns at the end of BB1 and BB2 and find the longest
1064 sequence that are equivalent. Store the first insns for that sequence
1065 in *F1 and *F2 and return the sequence length.
1067 To simplify callers of this function, if the blocks match exactly,
1068 store the head of the blocks in *F1 and *F2. */
1071 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED
, basic_block bb1
,
1072 basic_block bb2
, rtx
*f1
, rtx
*f2
)
1074 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
1077 /* Skip simple jumps at the end of the blocks. Complex jumps still
1078 need to be compared for equivalence, which we'll do below. */
1081 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
1083 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1086 i1
= PREV_INSN (i1
);
1091 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1094 /* Count everything except for unconditional jump as insn. */
1095 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1097 i2
= PREV_INSN (i2
);
1103 while (!INSN_P (i1
) && i1
!= BB_HEAD (bb1
))
1104 i1
= PREV_INSN (i1
);
1106 while (!INSN_P (i2
) && i2
!= BB_HEAD (bb2
))
1107 i2
= PREV_INSN (i2
);
1109 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1112 if (!insns_match_p (mode
, i1
, i2
))
1115 merge_memattrs (i1
, i2
);
1117 /* Don't begin a cross-jump with a NOTE insn. */
1120 /* If the merged insns have different REG_EQUAL notes, then
1122 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1123 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1125 if (equiv1
&& !equiv2
)
1126 remove_note (i1
, equiv1
);
1127 else if (!equiv1
&& equiv2
)
1128 remove_note (i2
, equiv2
);
1129 else if (equiv1
&& equiv2
1130 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1132 remove_note (i1
, equiv1
);
1133 remove_note (i2
, equiv2
);
1136 afterlast1
= last1
, afterlast2
= last2
;
1137 last1
= i1
, last2
= i2
;
1141 i1
= PREV_INSN (i1
);
1142 i2
= PREV_INSN (i2
);
1146 /* Don't allow the insn after a compare to be shared by
1147 cross-jumping unless the compare is also shared. */
1148 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1149 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
1152 /* Include preceding notes and labels in the cross-jump. One,
1153 this may bring us to the head of the blocks as requested above.
1154 Two, it keeps line number notes as matched as may be. */
1157 while (last1
!= BB_HEAD (bb1
) && !INSN_P (PREV_INSN (last1
)))
1158 last1
= PREV_INSN (last1
);
1160 if (last1
!= BB_HEAD (bb1
) && LABEL_P (PREV_INSN (last1
)))
1161 last1
= PREV_INSN (last1
);
1163 while (last2
!= BB_HEAD (bb2
) && !INSN_P (PREV_INSN (last2
)))
1164 last2
= PREV_INSN (last2
);
1166 if (last2
!= BB_HEAD (bb2
) && LABEL_P (PREV_INSN (last2
)))
1167 last2
= PREV_INSN (last2
);
1176 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1177 the branch instruction. This means that if we commonize the control
1178 flow before end of the basic block, the semantic remains unchanged.
1180 We may assume that there exists one edge with a common destination. */
1183 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1185 int nehedges1
= 0, nehedges2
= 0;
1186 edge fallthru1
= 0, fallthru2
= 0;
1190 /* If BB1 has only one successor, we may be looking at either an
1191 unconditional jump, or a fake edge to exit. */
1192 if (EDGE_COUNT (bb1
->succ
) == 1
1193 && (EDGE_0 (bb1
->succ
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1194 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1195 return (EDGE_COUNT (bb2
->succ
) == 1
1196 && (EDGE_0 (bb2
->succ
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1197 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1199 /* Match conditional jumps - this may get tricky when fallthru and branch
1200 edges are crossed. */
1201 if (EDGE_COUNT (bb1
->succ
) == 2
1202 && any_condjump_p (BB_END (bb1
))
1203 && onlyjump_p (BB_END (bb1
)))
1205 edge b1
, f1
, b2
, f2
;
1206 bool reverse
, match
;
1207 rtx set1
, set2
, cond1
, cond2
;
1208 enum rtx_code code1
, code2
;
1210 if (EDGE_COUNT (bb2
->succ
) != 2
1211 || !any_condjump_p (BB_END (bb2
))
1212 || !onlyjump_p (BB_END (bb2
)))
1215 b1
= BRANCH_EDGE (bb1
);
1216 b2
= BRANCH_EDGE (bb2
);
1217 f1
= FALLTHRU_EDGE (bb1
);
1218 f2
= FALLTHRU_EDGE (bb2
);
1220 /* Get around possible forwarders on fallthru edges. Other cases
1221 should be optimized out already. */
1222 if (FORWARDER_BLOCK_P (f1
->dest
))
1223 f1
= EDGE_0 (f1
->dest
->succ
);
1225 if (FORWARDER_BLOCK_P (f2
->dest
))
1226 f2
= EDGE_0 (f2
->dest
->succ
);
1228 /* To simplify use of this function, return false if there are
1229 unneeded forwarder blocks. These will get eliminated later
1230 during cleanup_cfg. */
1231 if (FORWARDER_BLOCK_P (f1
->dest
)
1232 || FORWARDER_BLOCK_P (f2
->dest
)
1233 || FORWARDER_BLOCK_P (b1
->dest
)
1234 || FORWARDER_BLOCK_P (b2
->dest
))
1237 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1239 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1244 set1
= pc_set (BB_END (bb1
));
1245 set2
= pc_set (BB_END (bb2
));
1246 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1247 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1250 cond1
= XEXP (SET_SRC (set1
), 0);
1251 cond2
= XEXP (SET_SRC (set2
), 0);
1252 code1
= GET_CODE (cond1
);
1254 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1256 code2
= GET_CODE (cond2
);
1258 if (code2
== UNKNOWN
)
1261 /* Verify codes and operands match. */
1262 match
= ((code1
== code2
1263 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1264 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1265 || (code1
== swap_condition (code2
)
1266 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1268 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1271 /* If we return true, we will join the blocks. Which means that
1272 we will only have one branch prediction bit to work with. Thus
1273 we require the existing branches to have probabilities that are
1277 && maybe_hot_bb_p (bb1
)
1278 && maybe_hot_bb_p (bb2
))
1282 if (b1
->dest
== b2
->dest
)
1283 prob2
= b2
->probability
;
1285 /* Do not use f2 probability as f2 may be forwarded. */
1286 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1288 /* Fail if the difference in probabilities is greater than 50%.
1289 This rules out two well-predicted branches with opposite
1291 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1295 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1296 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1302 if (dump_file
&& match
)
1303 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1304 bb1
->index
, bb2
->index
);
1309 /* Generic case - we are seeing a computed jump, table jump or trapping
1312 #ifndef CASE_DROPS_THROUGH
1313 /* Check whether there are tablejumps in the end of BB1 and BB2.
1314 Return true if they are identical. */
1319 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1320 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1321 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1323 /* The labels should never be the same rtx. If they really are same
1324 the jump tables are same too. So disable crossjumping of blocks BB1
1325 and BB2 because when deleting the common insns in the end of BB1
1326 by delete_basic_block () the jump table would be deleted too. */
1327 /* If LABEL2 is referenced in BB1->END do not do anything
1328 because we would loose information when replacing
1329 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1330 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1332 /* Set IDENTICAL to true when the tables are identical. */
1333 bool identical
= false;
1336 p1
= PATTERN (table1
);
1337 p2
= PATTERN (table2
);
1338 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1342 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1343 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1344 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1345 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1350 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1351 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1357 replace_label_data rr
;
1360 /* Temporarily replace references to LABEL1 with LABEL2
1361 in BB1->END so that we could compare the instructions. */
1364 rr
.update_label_nuses
= false;
1365 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1367 match
= insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
));
1368 if (dump_file
&& match
)
1370 "Tablejumps in bb %i and %i match.\n",
1371 bb1
->index
, bb2
->index
);
1373 /* Set the original label in BB1->END because when deleting
1374 a block whose end is a tablejump, the tablejump referenced
1375 from the instruction is deleted too. */
1378 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1388 /* First ensure that the instructions match. There may be many outgoing
1389 edges so this test is generally cheaper. */
1390 if (!insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
)))
1393 /* Search the outgoing edges, ensure that the counts do match, find possible
1394 fallthru and exception handling edges since these needs more
1396 for (ix
= 0; ix
< MIN (EDGE_COUNT (bb1
->succ
), EDGE_COUNT (bb2
->succ
)); ix
++)
1398 e1
= EDGE_I (bb1
->succ
, ix
);
1399 e2
= EDGE_I (bb2
->succ
, ix
);
1401 if (e1
->flags
& EDGE_EH
)
1404 if (e2
->flags
& EDGE_EH
)
1407 if (e1
->flags
& EDGE_FALLTHRU
)
1409 if (e2
->flags
& EDGE_FALLTHRU
)
1413 /* If number of edges of various types does not match, fail. */
1414 if (EDGE_COUNT (bb1
->succ
) != EDGE_COUNT (bb2
->succ
)
1415 || nehedges1
!= nehedges2
1416 || (fallthru1
!= 0) != (fallthru2
!= 0))
1419 /* fallthru edges must be forwarded to the same destination. */
1422 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1423 ? EDGE_0 (fallthru1
->dest
->succ
)->dest
: fallthru1
->dest
);
1424 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1425 ? EDGE_0 (fallthru2
->dest
->succ
)->dest
: fallthru2
->dest
);
1431 /* Ensure the same EH region. */
1433 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1434 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1439 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1443 /* We don't need to match the rest of edges as above checks should be enough
1444 to ensure that they are equivalent. */
1448 /* E1 and E2 are edges with the same destination block. Search their
1449 predecessors for common code. If found, redirect control flow from
1450 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1453 try_crossjump_to_edge (int mode
, edge e1
, edge e2
)
1456 basic_block src1
= e1
->src
, src2
= e2
->src
;
1457 basic_block redirect_to
, redirect_from
, to_remove
;
1458 rtx newpos1
, newpos2
;
1462 newpos1
= newpos2
= NULL_RTX
;
1464 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1465 to try this optimization. */
1467 if (flag_reorder_blocks_and_partition
&& no_new_pseudos
)
1470 /* Search backward through forwarder blocks. We don't need to worry
1471 about multiple entry or chained forwarders, as they will be optimized
1472 away. We do this to look past the unconditional jump following a
1473 conditional jump that is required due to the current CFG shape. */
1474 if (EDGE_COUNT (src1
->pred
) == 1
1475 && FORWARDER_BLOCK_P (src1
))
1476 e1
= EDGE_0 (src1
->pred
), src1
= e1
->src
;
1478 if (EDGE_COUNT (src2
->pred
) == 1
1479 && FORWARDER_BLOCK_P (src2
))
1480 e2
= EDGE_0 (src2
->pred
), src2
= e2
->src
;
1482 /* Nothing to do if we reach ENTRY, or a common source block. */
1483 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1488 /* Seeing more than 1 forwarder blocks would confuse us later... */
1489 if (FORWARDER_BLOCK_P (e1
->dest
)
1490 && FORWARDER_BLOCK_P (EDGE_0 (e1
->dest
->succ
)->dest
))
1493 if (FORWARDER_BLOCK_P (e2
->dest
)
1494 && FORWARDER_BLOCK_P (EDGE_0 (e2
->dest
->succ
)->dest
))
1497 /* Likewise with dead code (possibly newly created by the other optimizations
1499 if (!src1
->pred
|| !src2
->pred
)
1502 /* Look for the common insn sequence, part the first ... */
1503 if (!outgoing_edges_match (mode
, src1
, src2
))
1506 /* ... and part the second. */
1507 nmatch
= flow_find_cross_jump (mode
, src1
, src2
, &newpos1
, &newpos2
);
1511 #ifndef CASE_DROPS_THROUGH
1512 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1514 If we have tablejumps in the end of SRC1 and SRC2
1515 they have been already compared for equivalence in outgoing_edges_match ()
1516 so replace the references to TABLE1 by references to TABLE2. */
1521 if (tablejump_p (BB_END (src1
), &label1
, &table1
)
1522 && tablejump_p (BB_END (src2
), &label2
, &table2
)
1523 && label1
!= label2
)
1525 replace_label_data rr
;
1528 /* Replace references to LABEL1 with LABEL2. */
1531 rr
.update_label_nuses
= true;
1532 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1534 /* Do not replace the label in SRC1->END because when deleting
1535 a block whose end is a tablejump, the tablejump referenced
1536 from the instruction is deleted too. */
1537 if (insn
!= BB_END (src1
))
1538 for_each_rtx (&insn
, replace_label
, &rr
);
1544 /* Avoid splitting if possible. */
1545 if (newpos2
== BB_HEAD (src2
))
1550 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
1551 src2
->index
, nmatch
);
1552 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1557 "Cross jumping from bb %i to bb %i; %i common insns\n",
1558 src1
->index
, src2
->index
, nmatch
);
1560 redirect_to
->count
+= src1
->count
;
1561 redirect_to
->frequency
+= src1
->frequency
;
1562 /* We may have some registers visible trought the block. */
1563 redirect_to
->flags
|= BB_DIRTY
;
1565 /* Recompute the frequencies and counts of outgoing edges. */
1566 FOR_EACH_EDGE (s
, redirect_to
->succ
, ix
)
1570 basic_block d
= s
->dest
;
1572 if (FORWARDER_BLOCK_P (d
))
1573 d
= EDGE_0 (d
->succ
)->dest
;
1575 FOR_EACH_EDGE (s2
, src1
->succ
, ix2
)
1577 basic_block d2
= s2
->dest
;
1578 if (FORWARDER_BLOCK_P (d2
))
1579 d2
= EDGE_0 (d2
->succ
)->dest
;
1584 s
->count
+= s2
->count
;
1586 /* Take care to update possible forwarder blocks. We verified
1587 that there is no more than one in the chain, so we can't run
1588 into infinite loop. */
1589 if (FORWARDER_BLOCK_P (s
->dest
))
1591 EDGE_0 (s
->dest
->succ
)->count
+= s2
->count
;
1592 s
->dest
->count
+= s2
->count
;
1593 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1596 if (FORWARDER_BLOCK_P (s2
->dest
))
1598 EDGE_0 (s2
->dest
->succ
)->count
-= s2
->count
;
1599 if (EDGE_0 (s2
->dest
->succ
)->count
< 0)
1600 EDGE_0 (s2
->dest
->succ
)->count
= 0;
1601 s2
->dest
->count
-= s2
->count
;
1602 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1603 if (s2
->dest
->frequency
< 0)
1604 s2
->dest
->frequency
= 0;
1605 if (s2
->dest
->count
< 0)
1606 s2
->dest
->count
= 0;
1609 if (!redirect_to
->frequency
&& !src1
->frequency
)
1610 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
1613 = ((s
->probability
* redirect_to
->frequency
+
1614 s2
->probability
* src1
->frequency
)
1615 / (redirect_to
->frequency
+ src1
->frequency
));
1618 update_br_prob_note (redirect_to
);
1620 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1622 /* Skip possible basic block header. */
1623 if (LABEL_P (newpos1
))
1624 newpos1
= NEXT_INSN (newpos1
);
1626 if (NOTE_P (newpos1
))
1627 newpos1
= NEXT_INSN (newpos1
);
1629 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
1630 to_remove
= EDGE_0 (redirect_from
->succ
)->dest
;
1632 redirect_edge_and_branch_force (EDGE_0 (redirect_from
->succ
), redirect_to
);
1633 delete_basic_block (to_remove
);
1635 update_forwarder_flag (redirect_from
);
1640 /* Search the predecessors of BB for common insn sequences. When found,
1641 share code between them by redirecting control flow. Return true if
1642 any changes made. */
1645 try_crossjump_bb (int mode
, basic_block bb
)
1647 edge e
, e2
, fallthru
;
1648 VEC(edge
) *ev
, *ev2
;
1650 unsigned n
, max
, ix
, ix2
;
1652 /* Nothing to do if there is not at least two incoming edges. */
1653 if (EDGE_COUNT (bb
->pred
) < 2)
1656 /* If we are partitioning hot/cold basic blocks, we don't want to
1657 mess up unconditional or indirect jumps that cross between hot
1658 and cold sections. */
1660 if (flag_reorder_blocks_and_partition
1661 && (EDGE_0 (bb
->pred
)->src
->partition
!= EDGE_1 (bb
->pred
)->src
->partition
1662 || EDGE_0 (bb
->pred
)->crossing_edge
))
1665 /* It is always cheapest to redirect a block that ends in a branch to
1666 a block that falls through into BB, as that adds no branches to the
1667 program. We'll try that combination first. */
1669 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
1670 FOR_EACH_EDGE (e
, bb
->pred
, n
)
1672 if (e
->flags
& EDGE_FALLTHRU
)
1679 for (ix
= 0, ev
= bb
->pred
; ix
< EDGE_COUNT (ev
); )
1681 e
= EDGE_I (ev
, ix
);
1684 /* As noted above, first try with the fallthru predecessor. */
1687 /* Don't combine the fallthru edge into anything else.
1688 If there is a match, we'll do it the other way around. */
1691 /* If nothing changed since the last attempt, there is nothing
1694 && (!(e
->src
->flags
& BB_DIRTY
)
1695 && !(fallthru
->src
->flags
& BB_DIRTY
)))
1698 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1707 /* Non-obvious work limiting check: Recognize that we're going
1708 to call try_crossjump_bb on every basic block. So if we have
1709 two blocks with lots of outgoing edges (a switch) and they
1710 share lots of common destinations, then we would do the
1711 cross-jump check once for each common destination.
1713 Now, if the blocks actually are cross-jump candidates, then
1714 all of their destinations will be shared. Which means that
1715 we only need check them for cross-jump candidacy once. We
1716 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1717 choosing to do the check from the block for which the edge
1718 in question is the first successor of A. */
1719 if (EDGE_0 (e
->src
->succ
) != e
)
1722 for (ix2
= 0, ev2
= bb
->pred
; ix2
< EDGE_COUNT (ev2
); )
1724 e2
= EDGE_I (ev2
, ix2
);
1730 /* We've already checked the fallthru edge above. */
1734 /* The "first successor" check above only prevents multiple
1735 checks of crossjump(A,B). In order to prevent redundant
1736 checks of crossjump(B,A), require that A be the block
1737 with the lowest index. */
1738 if (e
->src
->index
> e2
->src
->index
)
1741 /* If nothing changed since the last attempt, there is nothing
1744 && (!(e
->src
->flags
& BB_DIRTY
)
1745 && !(e2
->src
->flags
& BB_DIRTY
)))
1748 if (try_crossjump_to_edge (mode
, e
, e2
))
1761 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1762 instructions etc. Return nonzero if changes were made. */
1765 try_optimize_cfg (int mode
)
1767 bool changed_overall
= false;
1770 basic_block bb
, b
, next
;
1772 if (mode
& CLEANUP_CROSSJUMP
)
1773 add_noreturn_fake_exit_edges ();
1776 update_forwarder_flag (bb
);
1778 if (mode
& (CLEANUP_UPDATE_LIFE
| CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
1781 if (! targetm
.cannot_modify_jumps_p ())
1784 /* Attempt to merge blocks as made possible by edge removal. If
1785 a block has only one successor, and the successor has only
1786 one predecessor, they may be combined. */
1794 "\n\ntry_optimize_cfg iteration %i\n\n",
1797 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
1801 bool changed_here
= false;
1803 /* Delete trivially dead basic blocks. */
1804 while (EDGE_COUNT (b
->pred
) == 0)
1808 fprintf (dump_file
, "Deleting block %i.\n",
1811 delete_basic_block (b
);
1812 if (!(mode
& CLEANUP_CFGLAYOUT
))
1817 /* Remove code labels no longer used. */
1818 if (EDGE_COUNT (b
->pred
) == 1
1819 && (EDGE_0 (b
->pred
)->flags
& EDGE_FALLTHRU
)
1820 && !(EDGE_0 (b
->pred
)->flags
& EDGE_COMPLEX
)
1821 && LABEL_P (BB_HEAD (b
))
1822 /* If the previous block ends with a branch to this
1823 block, we can't delete the label. Normally this
1824 is a condjump that is yet to be simplified, but
1825 if CASE_DROPS_THRU, this can be a tablejump with
1826 some element going to the same place as the
1827 default (fallthru). */
1828 && (EDGE_0 (b
->pred
)->src
== ENTRY_BLOCK_PTR
1829 || !JUMP_P (BB_END (EDGE_0 (b
->pred
)->src
))
1830 || ! label_is_jump_target_p (BB_HEAD (b
),
1831 BB_END (EDGE_0 (b
->pred
)->src
))))
1833 rtx label
= BB_HEAD (b
);
1835 delete_insn_chain (label
, label
);
1836 /* In the case label is undeletable, move it after the
1837 BASIC_BLOCK note. */
1838 if (NOTE_LINE_NUMBER (BB_HEAD (b
)) == NOTE_INSN_DELETED_LABEL
)
1840 rtx bb_note
= NEXT_INSN (BB_HEAD (b
));
1842 reorder_insns_nobb (label
, label
, bb_note
);
1843 BB_HEAD (b
) = bb_note
;
1846 fprintf (dump_file
, "Deleted label in block %i.\n",
1850 /* If we fall through an empty block, we can remove it. */
1851 if (!(mode
& CLEANUP_CFGLAYOUT
)
1852 && EDGE_COUNT (b
->pred
) == 1
1853 && (EDGE_0 (b
->pred
)->flags
& EDGE_FALLTHRU
)
1854 && !LABEL_P (BB_HEAD (b
))
1855 && FORWARDER_BLOCK_P (b
)
1856 /* Note that forwarder_block_p true ensures that
1857 there is a successor for this block. */
1858 && (EDGE_0 (b
->succ
)->flags
& EDGE_FALLTHRU
)
1859 && n_basic_blocks
> 1)
1863 "Deleting fallthru block %i.\n",
1866 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
1867 redirect_edge_succ_nodup (EDGE_0 (b
->pred
), EDGE_0 (b
->succ
)->dest
);
1868 delete_basic_block (b
);
1873 if (EDGE_COUNT (b
->succ
) == 1
1874 && (s
= EDGE_0 (b
->succ
))
1875 && !(s
->flags
& EDGE_COMPLEX
)
1876 && (c
= s
->dest
) != EXIT_BLOCK_PTR
1877 && EDGE_COUNT (c
->pred
) == 1
1880 /* When not in cfg_layout mode use code aware of reordering
1881 INSN. This code possibly creates new basic blocks so it
1882 does not fit merge_blocks interface and is kept here in
1883 hope that it will become useless once more of compiler
1884 is transformed to use cfg_layout mode. */
1886 if ((mode
& CLEANUP_CFGLAYOUT
)
1887 && can_merge_blocks_p (b
, c
))
1889 merge_blocks (b
, c
);
1890 update_forwarder_flag (b
);
1891 changed_here
= true;
1893 else if (!(mode
& CLEANUP_CFGLAYOUT
)
1894 /* If the jump insn has side effects,
1895 we can't kill the edge. */
1896 && (!JUMP_P (BB_END (b
))
1897 || (reload_completed
1898 ? simplejump_p (BB_END (b
))
1899 : (onlyjump_p (BB_END (b
))
1900 && !tablejump_p (BB_END (b
),
1902 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
1905 changed_here
= true;
1909 /* Simplify branch over branch. */
1910 if ((mode
& CLEANUP_EXPENSIVE
)
1911 && !(mode
& CLEANUP_CFGLAYOUT
)
1912 && try_simplify_condjump (b
))
1913 changed_here
= true;
1915 /* If B has a single outgoing edge, but uses a
1916 non-trivial jump instruction without side-effects, we
1917 can either delete the jump entirely, or replace it
1918 with a simple unconditional jump. */
1919 if (EDGE_COUNT (b
->succ
) == 1
1920 && EDGE_0 (b
->succ
)->dest
!= EXIT_BLOCK_PTR
1921 && onlyjump_p (BB_END (b
))
1922 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
)
1923 && try_redirect_by_replacing_jump (EDGE_0 (b
->succ
), EDGE_0 (b
->succ
)->dest
,
1924 (mode
& CLEANUP_CFGLAYOUT
) != 0))
1926 update_forwarder_flag (b
);
1927 changed_here
= true;
1930 /* Simplify branch to branch. */
1931 if (try_forward_edges (mode
, b
))
1932 changed_here
= true;
1934 /* Look for shared code between blocks. */
1935 if ((mode
& CLEANUP_CROSSJUMP
)
1936 && try_crossjump_bb (mode
, b
))
1937 changed_here
= true;
1939 /* Don't get confused by the index shift caused by
1947 if ((mode
& CLEANUP_CROSSJUMP
)
1948 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
1951 #ifdef ENABLE_CHECKING
1953 verify_flow_info ();
1956 changed_overall
|= changed
;
1962 if (mode
& CLEANUP_CROSSJUMP
)
1963 remove_fake_exit_edges ();
1965 clear_aux_for_blocks ();
1967 return changed_overall
;
1970 /* Delete all unreachable basic blocks. */
1973 delete_unreachable_blocks (void)
1975 bool changed
= false;
1976 basic_block b
, next_bb
;
1978 find_unreachable_blocks ();
1980 /* Delete all unreachable basic blocks. */
1982 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
; b
= next_bb
)
1984 next_bb
= b
->next_bb
;
1986 if (!(b
->flags
& BB_REACHABLE
))
1988 delete_basic_block (b
);
1994 tidy_fallthru_edges ();
1998 /* Merges sequential blocks if possible. */
2001 merge_seq_blocks (void)
2004 bool changed
= false;
2006 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
!= EXIT_BLOCK_PTR
; )
2008 if (EDGE_COUNT (bb
->succ
) == 1
2009 && can_merge_blocks_p (bb
, EDGE_0 (bb
->succ
)->dest
))
2011 /* Merge the blocks and retry. */
2012 merge_blocks (bb
, EDGE_0 (bb
->succ
)->dest
);
2023 /* Tidy the CFG by deleting unreachable code and whatnot. */
2026 cleanup_cfg (int mode
)
2028 bool changed
= false;
2030 timevar_push (TV_CLEANUP_CFG
);
2031 if (delete_unreachable_blocks ())
2034 /* We've possibly created trivially dead code. Cleanup it right
2035 now to introduce more opportunities for try_optimize_cfg. */
2036 if (!(mode
& (CLEANUP_NO_INSN_DEL
| CLEANUP_UPDATE_LIFE
))
2037 && !reload_completed
)
2038 delete_trivially_dead_insns (get_insns(), max_reg_num ());
2043 while (try_optimize_cfg (mode
))
2045 delete_unreachable_blocks (), changed
= true;
2046 if (mode
& CLEANUP_UPDATE_LIFE
)
2048 /* Cleaning up CFG introduces more opportunities for dead code
2049 removal that in turn may introduce more opportunities for
2050 cleaning up the CFG. */
2051 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES
,
2053 | PROP_SCAN_DEAD_CODE
2054 | PROP_KILL_DEAD_CODE
2055 | ((mode
& CLEANUP_LOG_LINKS
)
2056 ? PROP_LOG_LINKS
: 0)))
2059 else if (!(mode
& CLEANUP_NO_INSN_DEL
)
2060 && (mode
& CLEANUP_EXPENSIVE
)
2061 && !reload_completed
)
2063 if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
2068 delete_dead_jumptables ();
2071 /* Kill the data we won't maintain. */
2072 free_EXPR_LIST_list (&label_value_list
);
2073 timevar_pop (TV_CLEANUP_CFG
);