diff options
Diffstat (limited to 'contrib/gcc/cfgcleanup.c')
-rw-r--r-- | contrib/gcc/cfgcleanup.c | 664 |
1 files changed, 412 insertions, 252 deletions
diff --git a/contrib/gcc/cfgcleanup.c b/contrib/gcc/cfgcleanup.c index df914ec..06fb913 100644 --- a/contrib/gcc/cfgcleanup.c +++ b/contrib/gcc/cfgcleanup.c @@ -1,6 +1,6 @@ /* Control flow optimization code for GNU compiler. Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, - 1999, 2000, 2001, 2002 Free Software Foundation, Inc. + 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc. This file is part of GCC. @@ -33,6 +33,8 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "config.h" #include "system.h" +#include "coretypes.h" +#include "tm.h" #include "rtl.h" #include "hard-reg-set.h" #include "basic-block.h" @@ -46,6 +48,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "params.h" #include "tm_p.h" #include "target.h" +#include "expr.h" /* cleanup_cfg maintains following flags for each basic block. */ @@ -65,36 +68,29 @@ enum bb_flags #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK) -static bool try_crossjump_to_edge PARAMS ((int, edge, edge)); -static bool try_crossjump_bb PARAMS ((int, basic_block)); -static bool outgoing_edges_match PARAMS ((int, - basic_block, basic_block)); -static int flow_find_cross_jump PARAMS ((int, basic_block, basic_block, - rtx *, rtx *)); -static bool insns_match_p PARAMS ((int, rtx, rtx)); - -static bool label_is_jump_target_p PARAMS ((rtx, rtx)); -static bool tail_recursion_label_p PARAMS ((rtx)); -static void merge_blocks_move_predecessor_nojumps PARAMS ((basic_block, - basic_block)); -static void merge_blocks_move_successor_nojumps PARAMS ((basic_block, - basic_block)); -static bool merge_blocks PARAMS ((edge,basic_block,basic_block, - int)); -static bool try_optimize_cfg PARAMS ((int)); -static bool try_simplify_condjump PARAMS ((basic_block)); -static bool try_forward_edges PARAMS ((int, basic_block)); -static edge thread_jump PARAMS ((int, edge, basic_block)); -static bool mark_effect PARAMS ((rtx, bitmap)); -static void notice_new_block PARAMS ((basic_block)); -static void update_forwarder_flag PARAMS ((basic_block)); -static int mentions_nonequal_regs PARAMS ((rtx *, void *)); +static bool try_crossjump_to_edge (int, edge, edge); +static bool try_crossjump_bb (int, basic_block); +static bool outgoing_edges_match (int, basic_block, basic_block); +static int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *); +static bool insns_match_p (int, rtx, rtx); + +static bool tail_recursion_label_p (rtx); +static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block); +static void merge_blocks_move_successor_nojumps (basic_block, basic_block); +static bool try_optimize_cfg (int); +static bool try_simplify_condjump (basic_block); +static bool try_forward_edges (int, basic_block); +static edge thread_jump (int, edge, basic_block); +static bool mark_effect (rtx, bitmap); +static void notice_new_block (basic_block); +static void update_forwarder_flag (basic_block); +static int mentions_nonequal_regs (rtx *, void *); +static void merge_memattrs (rtx, rtx); /* Set flags for newly created block. */ static void -notice_new_block (bb) - basic_block bb; +notice_new_block (basic_block bb) { if (!bb) return; @@ -106,8 +102,7 @@ notice_new_block (bb) /* Recompute forwarder flag after block has been modified. */ static void -update_forwarder_flag (bb) - basic_block bb; +update_forwarder_flag (basic_block bb) { if (forwarder_block_p (bb)) BB_SET_FLAG (bb, BB_FORWARDER_BLOCK); @@ -119,8 +114,7 @@ update_forwarder_flag (bb) Return true if something changed. */ static bool -try_simplify_condjump (cbranch_block) - basic_block cbranch_block; +try_simplify_condjump (basic_block cbranch_block) { basic_block jump_block, jump_dest_block, cbranch_dest_block; edge cbranch_jump_edge, cbranch_fallthru_edge; @@ -136,7 +130,7 @@ try_simplify_condjump (cbranch_block) /* Verify that we've got a normal conditional branch at the end of the block. */ - cbranch_insn = cbranch_block->end; + cbranch_insn = BB_END (cbranch_block); if (!any_condjump_p (cbranch_insn)) return false; @@ -166,7 +160,7 @@ try_simplify_condjump (cbranch_block) if (rtl_dump_file) fprintf (rtl_dump_file, "Simplifying condjump %i around jump %i\n", - INSN_UID (cbranch_insn), INSN_UID (jump_block->end)); + INSN_UID (cbranch_insn), INSN_UID (BB_END (jump_block))); /* Success. Update the CFG to match. Note that after this point the edge variable names appear backwards; the redirection is done @@ -179,19 +173,19 @@ try_simplify_condjump (cbranch_block) cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU; update_br_prob_note (cbranch_block); - end = jump_block->end; + end = BB_END (jump_block); /* Deleting a block may produce unreachable code warning even when we are - not deleting anything live. Supress it by moving all the line number + not deleting anything live. Suppress it by moving all the line number notes out of the block. */ - for (insn = jump_block->head; insn != NEXT_INSN (jump_block->end); + for (insn = BB_HEAD (jump_block); insn != NEXT_INSN (BB_END (jump_block)); insn = next) { next = NEXT_INSN (insn); if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0) { - if (insn == jump_block->end) + if (insn == BB_END (jump_block)) { - jump_block->end = PREV_INSN (insn); + BB_END (jump_block) = PREV_INSN (insn); if (insn == end) break; } @@ -200,7 +194,7 @@ try_simplify_condjump (cbranch_block) } } /* Delete the block with the unconditional jump, and clean up the mess. */ - flow_delete_block (jump_block); + delete_block (jump_block); tidy_fallthru_edge (cbranch_jump_edge, cbranch_block, cbranch_dest_block); return true; @@ -210,9 +204,7 @@ try_simplify_condjump (cbranch_block) on register. Used by jump threading. */ static bool -mark_effect (exp, nonequal) - rtx exp; - regset nonequal; +mark_effect (rtx exp, regset nonequal) { int regno; rtx dest; @@ -258,12 +250,10 @@ mark_effect (exp, nonequal) } } -/* Return nonzero if X is an register set in regset DATA. +/* Return nonzero if X is a register set in regset DATA. Called via for_each_rtx. */ static int -mentions_nonequal_regs (x, data) - rtx *x; - void *data; +mentions_nonequal_regs (rtx *x, void *data) { regset nonequal = (regset) data; if (REG_P (*x)) @@ -284,14 +274,11 @@ mentions_nonequal_regs (x, data) return 0; } /* Attempt to prove that the basic block B will have no side effects and - allways continues in the same edge if reached via E. Return the edge + always continues in the same edge if reached via E. Return the edge if exist, NULL otherwise. */ static edge -thread_jump (mode, e, b) - int mode; - edge e; - basic_block b; +thread_jump (int mode, edge e, basic_block b) { rtx set1, set2, cond1, cond2, insn; enum rtx_code code1, code2, reversed_code2; @@ -314,17 +301,17 @@ thread_jump (mode, e, b) } /* Second branch must end with onlyjump, as we will eliminate the jump. */ - if (!any_condjump_p (e->src->end)) + if (!any_condjump_p (BB_END (e->src))) return NULL; - if (!any_condjump_p (b->end) || !onlyjump_p (b->end)) + if (!any_condjump_p (BB_END (b)) || !onlyjump_p (BB_END (b))) { BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK); return NULL; } - set1 = pc_set (e->src->end); - set2 = pc_set (b->end); + set1 = pc_set (BB_END (e->src)); + set2 = pc_set (BB_END (b)); if (((e->flags & EDGE_FALLTHRU) != 0) != (XEXP (SET_SRC (set1), 1) == pc_rtx)) reverse1 = true; @@ -332,19 +319,19 @@ thread_jump (mode, e, b) cond1 = XEXP (SET_SRC (set1), 0); cond2 = XEXP (SET_SRC (set2), 0); if (reverse1) - code1 = reversed_comparison_code (cond1, e->src->end); + code1 = reversed_comparison_code (cond1, BB_END (e->src)); else code1 = GET_CODE (cond1); code2 = GET_CODE (cond2); - reversed_code2 = reversed_comparison_code (cond2, b->end); + reversed_code2 = reversed_comparison_code (cond2, BB_END (b)); if (!comparison_dominates_p (code1, code2) && !comparison_dominates_p (code1, reversed_code2)) return NULL; /* Ensure that the comparison operators are equivalent. - ??? This is far too pesimistic. We should allow swapped operands, + ??? This is far too pessimistic. We should allow swapped operands, different CCmodes, or for example comparisons for interval, that dominate even when operands are not equivalent. */ if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0)) @@ -353,7 +340,7 @@ thread_jump (mode, e, b) /* Short circuit cases where block B contains some side effects, as we can't safely bypass it. */ - for (insn = NEXT_INSN (b->head); insn != NEXT_INSN (b->end); + for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b)); insn = NEXT_INSN (insn)) if (INSN_P (insn) && side_effects_p (PATTERN (insn))) { @@ -364,7 +351,7 @@ thread_jump (mode, e, b) cselib_init (); /* First process all values computed in the source basic block. */ - for (insn = NEXT_INSN (e->src->head); insn != NEXT_INSN (e->src->end); + for (insn = NEXT_INSN (BB_HEAD (e->src)); insn != NEXT_INSN (BB_END (e->src)); insn = NEXT_INSN (insn)) if (INSN_P (insn)) cselib_process_insn (insn); @@ -376,7 +363,7 @@ thread_jump (mode, e, b) processing as if it were same basic block. Our goal is to prove that whole block is an NOOP. */ - for (insn = NEXT_INSN (b->head); insn != NEXT_INSN (b->end) && !failed; + for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b)) && !failed; insn = NEXT_INSN (insn)) { if (INSN_P (insn)) @@ -433,9 +420,7 @@ failed_exit: Return true if successful. */ static bool -try_forward_edges (mode, b) - basic_block b; - int mode; +try_forward_edges (int mode, basic_block b) { bool changed = false; edge e, next, *threaded_edges = NULL; @@ -525,7 +510,7 @@ try_forward_edges (mode, b) if ((mode & CLEANUP_PRE_LOOP) && optimize) { rtx insn = (target->succ->flags & EDGE_FALLTHRU - ? target->head : prev_nonnote_insn (target->end)); + ? BB_HEAD (target) : prev_nonnote_insn (BB_END (target))); if (GET_CODE (insn) != NOTE) insn = NEXT_INSN (insn); @@ -543,7 +528,7 @@ try_forward_edges (mode, b) at this time; it can mess up the loop optimizer's recognition of some patterns. */ - insn = PREV_INSN (target->head); + insn = PREV_INSN (BB_HEAD (target)); if (insn && GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) break; @@ -662,43 +647,10 @@ try_forward_edges (mode, b) return changed; } -/* Return true if LABEL is a target of JUMP_INSN. This applies only - to non-complex jumps. That is, direct unconditional, conditional, - and tablejumps, but not computed jumps or returns. It also does - not apply to the fallthru case of a conditional jump. */ - -static bool -label_is_jump_target_p (label, jump_insn) - rtx label, jump_insn; -{ - rtx tmp = JUMP_LABEL (jump_insn); - - if (label == tmp) - return true; - - if (tmp != NULL_RTX - && (tmp = NEXT_INSN (tmp)) != NULL_RTX - && GET_CODE (tmp) == JUMP_INSN - && (tmp = PATTERN (tmp), - GET_CODE (tmp) == ADDR_VEC - || GET_CODE (tmp) == ADDR_DIFF_VEC)) - { - rtvec vec = XVEC (tmp, GET_CODE (tmp) == ADDR_DIFF_VEC); - int i, veclen = GET_NUM_ELEM (vec); - - for (i = 0; i < veclen; ++i) - if (XEXP (RTVEC_ELT (vec, i), 0) == label) - return true; - } - - return false; -} - /* Return true if LABEL is used for tail recursion. */ static bool -tail_recursion_label_p (label) - rtx label; +tail_recursion_label_p (rtx label) { rtx x; @@ -714,12 +666,11 @@ tail_recursion_label_p (label) any jumps (aside from the jump from A to B). */ static void -merge_blocks_move_predecessor_nojumps (a, b) - basic_block a, b; +merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b) { rtx barrier; - barrier = next_nonnote_insn (a->end); + barrier = next_nonnote_insn (BB_END (a)); if (GET_CODE (barrier) != BARRIER) abort (); delete_insn (barrier); @@ -731,12 +682,12 @@ merge_blocks_move_predecessor_nojumps (a, b) and adjust the block trees appropriately. Even better would be to have a tighter connection between block trees and rtl so that this is not necessary. */ - if (squeeze_notes (&a->head, &a->end)) + if (squeeze_notes (&BB_HEAD (a), &BB_END (a))) abort (); /* Scramble the insn chain. */ - if (a->end != PREV_INSN (b->head)) - reorder_insns_nobb (a->head, a->end, PREV_INSN (b->head)); + if (BB_END (a) != PREV_INSN (BB_HEAD (b))) + reorder_insns_nobb (BB_HEAD (a), BB_END (a), PREV_INSN (BB_HEAD (b))); a->flags |= BB_DIRTY; if (rtl_dump_file) @@ -749,7 +700,7 @@ merge_blocks_move_predecessor_nojumps (a, b) link_block (a, b->prev_bb); /* Now blocks A and B are contiguous. Merge them. */ - merge_blocks_nomove (a, b); + merge_blocks (a, b); } /* Blocks A and B are to be merged into a single block. B has no outgoing @@ -757,29 +708,23 @@ merge_blocks_move_predecessor_nojumps (a, b) any jumps (aside from the jump from A to B). */ static void -merge_blocks_move_successor_nojumps (a, b) - basic_block a, b; +merge_blocks_move_successor_nojumps (basic_block a, basic_block b) { rtx barrier, real_b_end; + rtx label, table; - real_b_end = b->end; - barrier = NEXT_INSN (b->end); + real_b_end = BB_END (b); - /* Recognize a jump table following block B. */ - if (barrier - && GET_CODE (barrier) == CODE_LABEL - && NEXT_INSN (barrier) - && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN - && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC - || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC)) + /* If there is a jump table following block B temporarily add the jump table + to block B so that it will also be moved to the correct location. */ + if (tablejump_p (BB_END (b), &label, &table) + && prev_active_insn (label) == BB_END (b)) { - /* Temporarily add the table jump insn to b, so that it will also - be moved to the correct location. */ - b->end = NEXT_INSN (barrier); - barrier = NEXT_INSN (b->end); + BB_END (b) = table; } /* There had better have been a barrier there. Delete it. */ + barrier = NEXT_INSN (BB_END (b)); if (barrier && GET_CODE (barrier) == BARRIER) delete_insn (barrier); @@ -790,53 +735,60 @@ merge_blocks_move_successor_nojumps (a, b) and adjust the block trees appropriately. Even better would be to have a tighter connection between block trees and rtl so that this is not necessary. */ - if (squeeze_notes (&b->head, &b->end)) + if (squeeze_notes (&BB_HEAD (b), &BB_END (b))) abort (); /* Scramble the insn chain. */ - reorder_insns_nobb (b->head, b->end, a->end); + reorder_insns_nobb (BB_HEAD (b), BB_END (b), BB_END (a)); /* Restore the real end of b. */ - b->end = real_b_end; + BB_END (b) = real_b_end; if (rtl_dump_file) fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n", b->index, a->index); /* Now blocks A and B are contiguous. Merge them. */ - merge_blocks_nomove (a, b); + merge_blocks (a, b); } /* Attempt to merge basic blocks that are potentially non-adjacent. - Return true iff the attempt succeeded. */ - -static bool -merge_blocks (e, b, c, mode) - edge e; - basic_block b, c; - int mode; + Return NULL iff the attempt failed, otherwise return basic block + where cleanup_cfg should continue. Because the merging commonly + moves basic block away or introduces another optimization + possibility, return basic block just before B so cleanup_cfg don't + need to iterate. + + It may be good idea to return basic block before C in the case + C has been moved after B and originally appeared earlier in the + insn sequence, but we have no information available about the + relative ordering of these two. Hopefully it is not too common. */ + +static basic_block +merge_blocks_move (edge e, basic_block b, basic_block c, int mode) { + basic_block next; /* If C has a tail recursion label, do not merge. There is no edge recorded from the call_placeholder back to this label, as that would make optimize_sibling_and_tail_recursive_calls more complex for no gain. */ if ((mode & CLEANUP_PRE_SIBCALL) - && GET_CODE (c->head) == CODE_LABEL - && tail_recursion_label_p (c->head)) - return false; + && GET_CODE (BB_HEAD (c)) == CODE_LABEL + && tail_recursion_label_p (BB_HEAD (c))) + return NULL; /* If B has a fallthru edge to C, no need to move anything. */ if (e->flags & EDGE_FALLTHRU) { int b_index = b->index, c_index = c->index; - merge_blocks_nomove (b, c); + merge_blocks (b, c); update_forwarder_flag (b); if (rtl_dump_file) fprintf (rtl_dump_file, "Merged %d and %d without moving.\n", b_index, c_index); - return true; + return b->prev_bb == ENTRY_BLOCK_PTR ? b : b->prev_bb; } /* Otherwise we will need to move code around. Do that only if expensive @@ -852,7 +804,7 @@ merge_blocks (e, b, c, mode) been if B is a forwarder block and C has no fallthru edge, but that should be cleaned up by bb-reorder instead. */ if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c)) - return false; + return NULL; /* We must make sure to not munge nesting of lexical blocks, and loop notes. This is done by squeezing out all the notes @@ -870,6 +822,9 @@ merge_blocks (e, b, c, mode) b_has_incoming_fallthru = (tmp_edge != NULL); b_fallthru_edge = tmp_edge; + next = b->prev_bb; + if (next == c) + next = next->prev_bb; /* Otherwise, we're going to try to move C after B. If C does not have an outgoing fallthru, then it can be moved @@ -877,7 +832,7 @@ merge_blocks (e, b, c, mode) if (! c_has_outgoing_fallthru) { merge_blocks_move_successor_nojumps (b, c); - return true; + return next == ENTRY_BLOCK_PTR ? next->next_bb : next; } /* If B does not have an incoming fallthru, then it can be moved @@ -890,26 +845,106 @@ merge_blocks (e, b, c, mode) basic_block bb; if (b_fallthru_edge->src == ENTRY_BLOCK_PTR) - return false; + return NULL; bb = force_nonfallthru (b_fallthru_edge); if (bb) notice_new_block (bb); } merge_blocks_move_predecessor_nojumps (b, c); - return true; + return next == ENTRY_BLOCK_PTR ? next->next_bb : next; } - return false; + return NULL; } +/* Removes the memory attributes of MEM expression + if they are not equal. */ + +void +merge_memattrs (rtx x, rtx y) +{ + int i; + int j; + enum rtx_code code; + const char *fmt; + + if (x == y) + return; + if (x == 0 || y == 0) + return; + + code = GET_CODE (x); + + if (code != GET_CODE (y)) + return; + + if (GET_MODE (x) != GET_MODE (y)) + return; + + if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y)) + { + if (! MEM_ATTRS (x)) + MEM_ATTRS (y) = 0; + else if (! MEM_ATTRS (y)) + MEM_ATTRS (x) = 0; + else + { + if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y)) + { + set_mem_alias_set (x, 0); + set_mem_alias_set (y, 0); + } + + if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y))) + { + set_mem_expr (x, 0); + set_mem_expr (y, 0); + set_mem_offset (x, 0); + set_mem_offset (y, 0); + } + else if (MEM_OFFSET (x) != MEM_OFFSET (y)) + { + set_mem_offset (x, 0); + set_mem_offset (y, 0); + } + + set_mem_size (x, MAX (MEM_SIZE (x), MEM_SIZE (y))); + set_mem_size (y, MEM_SIZE (x)); + + set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y))); + set_mem_align (y, MEM_ALIGN (x)); + } + } + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + switch (fmt[i]) + { + case 'E': + /* Two vectors must have the same length. */ + if (XVECLEN (x, i) != XVECLEN (y, i)) + return; + + for (j = 0; j < XVECLEN (x, i); j++) + merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j)); + + break; + + case 'e': + merge_memattrs (XEXP (x, i), XEXP (y, i)); + } + } + return; +} + + /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */ static bool -insns_match_p (mode, i1, i2) - int mode ATTRIBUTE_UNUSED; - rtx i1, i2; +insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2) { rtx p1, p2; @@ -974,7 +1009,15 @@ insns_match_p (mode, i1, i2) #endif if (reload_completed - ? ! rtx_renumbered_equal_p (p1, p2) : ! rtx_equal_p (p1, p2)) + ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2)) + return true; + + /* Do not do EQUIV substitution after reload. First, we're undoing the + work of reload_cse. Second, we may be undoing the work of the post- + reload splitting pass. */ + /* ??? Possibly add a new phase switch variable that can be used by + targets to disallow the troublesome insns after splitting. */ + if (!reload_completed) { /* The following code helps take care of G++ cleanups. */ rtx equiv1 = find_reg_equal_equiv_note (i1); @@ -1001,11 +1044,9 @@ insns_match_p (mode, i1, i2) return true; } } - - return false; } - return true; + return false; } /* Look through the insns at the end of BB1 and BB2 and find the longest @@ -1016,10 +1057,8 @@ insns_match_p (mode, i1, i2) store the head of the blocks in *F1 and *F2. */ static int -flow_find_cross_jump (mode, bb1, bb2, f1, f2) - int mode ATTRIBUTE_UNUSED; - basic_block bb1, bb2; - rtx *f1, *f2; +flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1, + basic_block bb2, rtx *f1, rtx *f2) { rtx i1, i2, last1, last2, afterlast1, afterlast2; int ninsns = 0; @@ -1027,7 +1066,7 @@ flow_find_cross_jump (mode, bb1, bb2, f1, f2) /* Skip simple jumps at the end of the blocks. Complex jumps still need to be compared for equivalence, which we'll do below. */ - i1 = bb1->end; + i1 = BB_END (bb1); last1 = afterlast1 = last2 = afterlast2 = NULL_RTX; if (onlyjump_p (i1) || (returnjump_p (i1) && !side_effects_p (PATTERN (i1)))) @@ -1036,7 +1075,7 @@ flow_find_cross_jump (mode, bb1, bb2, f1, f2) i1 = PREV_INSN (i1); } - i2 = bb2->end; + i2 = BB_END (bb2); if (onlyjump_p (i2) || (returnjump_p (i2) && !side_effects_p (PATTERN (i2)))) { @@ -1050,18 +1089,20 @@ flow_find_cross_jump (mode, bb1, bb2, f1, f2) while (true) { /* Ignore notes. */ - while (!INSN_P (i1) && i1 != bb1->head) + while (!INSN_P (i1) && i1 != BB_HEAD (bb1)) i1 = PREV_INSN (i1); - while (!INSN_P (i2) && i2 != bb2->head) + while (!INSN_P (i2) && i2 != BB_HEAD (bb2)) i2 = PREV_INSN (i2); - if (i1 == bb1->head || i2 == bb2->head) + if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2)) break; if (!insns_match_p (mode, i1, i2)) break; + merge_memattrs (i1, i2); + /* Don't begin a cross-jump with a NOTE insn. */ if (INSN_P (i1)) { @@ -1102,16 +1143,16 @@ flow_find_cross_jump (mode, bb1, bb2, f1, f2) Two, it keeps line number notes as matched as may be. */ if (ninsns) { - while (last1 != bb1->head && !INSN_P (PREV_INSN (last1))) + while (last1 != BB_HEAD (bb1) && !INSN_P (PREV_INSN (last1))) last1 = PREV_INSN (last1); - if (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == CODE_LABEL) + if (last1 != BB_HEAD (bb1) && GET_CODE (PREV_INSN (last1)) == CODE_LABEL) last1 = PREV_INSN (last1); - while (last2 != bb2->head && !INSN_P (PREV_INSN (last2))) + while (last2 != BB_HEAD (bb2) && !INSN_P (PREV_INSN (last2))) last2 = PREV_INSN (last2); - if (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == CODE_LABEL) + if (last2 != BB_HEAD (bb2) && GET_CODE (PREV_INSN (last2)) == CODE_LABEL) last2 = PREV_INSN (last2); *f1 = last1; @@ -1128,10 +1169,7 @@ flow_find_cross_jump (mode, bb1, bb2, f1, f2) We may assume that there exists one edge with a common destination. */ static bool -outgoing_edges_match (mode, bb1, bb2) - int mode; - basic_block bb1; - basic_block bb2; +outgoing_edges_match (int mode, basic_block bb1, basic_block bb2) { int nehedges1 = 0, nehedges2 = 0; edge fallthru1 = 0, fallthru2 = 0; @@ -1141,18 +1179,18 @@ outgoing_edges_match (mode, bb1, bb2) unconditional jump, or a fake edge to exit. */ if (bb1->succ && !bb1->succ->succ_next && (bb1->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0 - && (GET_CODE (bb1->end) != JUMP_INSN || simplejump_p (bb1->end))) + && (GET_CODE (BB_END (bb1)) != JUMP_INSN || simplejump_p (BB_END (bb1)))) return (bb2->succ && !bb2->succ->succ_next && (bb2->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0 - && (GET_CODE (bb2->end) != JUMP_INSN || simplejump_p (bb2->end))); + && (GET_CODE (BB_END (bb2)) != JUMP_INSN || simplejump_p (BB_END (bb2)))); /* Match conditional jumps - this may get tricky when fallthru and branch edges are crossed. */ if (bb1->succ && bb1->succ->succ_next && !bb1->succ->succ_next->succ_next - && any_condjump_p (bb1->end) - && onlyjump_p (bb1->end)) + && any_condjump_p (BB_END (bb1)) + && onlyjump_p (BB_END (bb1))) { edge b1, f1, b2, f2; bool reverse, match; @@ -1162,19 +1200,8 @@ outgoing_edges_match (mode, bb1, bb2) if (!bb2->succ || !bb2->succ->succ_next || bb2->succ->succ_next->succ_next - || !any_condjump_p (bb2->end) - || !onlyjump_p (bb2->end)) - return false; - - /* Do not crossjump across loop boundaries. This is a temporary - workaround for the common scenario in which crossjumping results - in killing the duplicated loop condition, making bb-reorder rotate - the loop incorectly, leaving an extra unconditional jump inside - the loop. - - This check should go away once bb-reorder knows how to duplicate - code in this case or rotate the loops to avoid this scenario. */ - if (bb1->loop_depth != bb2->loop_depth) + || !any_condjump_p (BB_END (bb2)) + || !onlyjump_p (BB_END (bb2))) return false; b1 = BRANCH_EDGE (bb1); @@ -1206,8 +1233,8 @@ outgoing_edges_match (mode, bb1, bb2) else return false; - set1 = pc_set (bb1->end); - set2 = pc_set (bb2->end); + set1 = pc_set (BB_END (bb1)); + set2 = pc_set (BB_END (bb2)); if ((XEXP (SET_SRC (set1), 1) == pc_rtx) != (XEXP (SET_SRC (set2), 1) == pc_rtx)) reverse = !reverse; @@ -1216,7 +1243,7 @@ outgoing_edges_match (mode, bb1, bb2) cond2 = XEXP (SET_SRC (set2), 0); code1 = GET_CODE (cond1); if (reverse) - code2 = reversed_comparison_code (cond2, bb2->end); + code2 = reversed_comparison_code (cond2, BB_END (bb2)); else code2 = GET_CODE (cond2); @@ -1274,11 +1301,85 @@ outgoing_edges_match (mode, bb1, bb2) /* Generic case - we are seeing a computed jump, table jump or trapping instruction. */ +#ifndef CASE_DROPS_THROUGH + /* Check whether there are tablejumps in the end of BB1 and BB2. + Return true if they are identical. */ + { + rtx label1, label2; + rtx table1, table2; + + if (tablejump_p (BB_END (bb1), &label1, &table1) + && tablejump_p (BB_END (bb2), &label2, &table2) + && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2))) + { + /* The labels should never be the same rtx. If they really are same + the jump tables are same too. So disable crossjumping of blocks BB1 + and BB2 because when deleting the common insns in the end of BB1 + by delete_block () the jump table would be deleted too. */ + /* If LABEL2 is referenced in BB1->END do not do anything + because we would loose information when replacing + LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */ + if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1))) + { + /* Set IDENTICAL to true when the tables are identical. */ + bool identical = false; + rtx p1, p2; + + p1 = PATTERN (table1); + p2 = PATTERN (table2); + if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2)) + { + identical = true; + } + else if (GET_CODE (p1) == ADDR_DIFF_VEC + && (XVECLEN (p1, 1) == XVECLEN (p2, 1)) + && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2)) + && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3))) + { + int i; + + identical = true; + for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--) + if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i))) + identical = false; + } + + if (identical) + { + replace_label_data rr; + bool match; + + /* Temporarily replace references to LABEL1 with LABEL2 + in BB1->END so that we could compare the instructions. */ + rr.r1 = label1; + rr.r2 = label2; + rr.update_label_nuses = false; + for_each_rtx (&BB_END (bb1), replace_label, &rr); + + match = insns_match_p (mode, BB_END (bb1), BB_END (bb2)); + if (rtl_dump_file && match) + fprintf (rtl_dump_file, + "Tablejumps in bb %i and %i match.\n", + bb1->index, bb2->index); + + /* Set the original label in BB1->END because when deleting + a block whose end is a tablejump, the tablejump referenced + from the instruction is deleted too. */ + rr.r1 = label2; + rr.r2 = label1; + for_each_rtx (&BB_END (bb1), replace_label, &rr); + + return match; + } + } + return false; + } + } +#endif + /* First ensure that the instructions match. There may be many outgoing - edges so this test is generally cheaper. - ??? Currently the tablejumps will never match, as they do have - different tables. */ - if (!insns_match_p (mode, bb1->end, bb2->end)) + edges so this test is generally cheaper. */ + if (!insns_match_p (mode, BB_END (bb1), BB_END (bb2))) return false; /* Search the outgoing edges, ensure that the counts do match, find possible @@ -1317,17 +1418,19 @@ outgoing_edges_match (mode, bb1, bb2) return false; } - /* In case we do have EH edges, ensure we are in the same region. */ - if (nehedges1) - { - rtx n1 = find_reg_note (bb1->end, REG_EH_REGION, 0); - rtx n2 = find_reg_note (bb2->end, REG_EH_REGION, 0); + /* Ensure the same EH region. */ + { + rtx n1 = find_reg_note (BB_END (bb1), REG_EH_REGION, 0); + rtx n2 = find_reg_note (BB_END (bb2), REG_EH_REGION, 0); - if (XEXP (n1, 0) != XEXP (n2, 0)) - return false; - } + if (!n1 && n2) + return false; - /* We don't need to match the rest of edges as above checks should be enought + if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0))) + return false; + } + + /* We don't need to match the rest of edges as above checks should be enough to ensure that they are equivalent. */ return true; } @@ -1337,9 +1440,7 @@ outgoing_edges_match (mode, bb1, bb2) (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */ static bool -try_crossjump_to_edge (mode, e1, e2) - int mode; - edge e1, e2; +try_crossjump_to_edge (int mode, edge e1, edge e2) { int nmatch; basic_block src1 = e1->src, src2 = e2->src; @@ -1390,8 +1491,41 @@ try_crossjump_to_edge (mode, e1, e2) if (!nmatch) return false; +#ifndef CASE_DROPS_THROUGH + /* Here we know that the insns in the end of SRC1 which are common with SRC2 + will be deleted. + If we have tablejumps in the end of SRC1 and SRC2 + they have been already compared for equivalence in outgoing_edges_match () + so replace the references to TABLE1 by references to TABLE2. */ + { + rtx label1, label2; + rtx table1, table2; + + if (tablejump_p (BB_END (src1), &label1, &table1) + && tablejump_p (BB_END (src2), &label2, &table2) + && label1 != label2) + { + replace_label_data rr; + rtx insn; + + /* Replace references to LABEL1 with LABEL2. */ + rr.r1 = label1; + rr.r2 = label2; + rr.update_label_nuses = true; + for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) + { + /* Do not replace the label in SRC1->END because when deleting + a block whose end is a tablejump, the tablejump referenced + from the instruction is deleted too. */ + if (insn != BB_END (src1)) + for_each_rtx (&insn, replace_label, &rr); + } + } + } +#endif + /* Avoid splitting if possible. */ - if (newpos2 == src2->head) + if (newpos2 == BB_HEAD (src2)) redirect_to = src2; else { @@ -1478,7 +1612,7 @@ try_crossjump_to_edge (mode, e1, e2) to_remove = redirect_from->succ->dest; redirect_edge_and_branch_force (redirect_from->succ, redirect_to); - flow_delete_block (to_remove); + delete_block (to_remove); update_forwarder_flag (redirect_from); @@ -1490,9 +1624,7 @@ try_crossjump_to_edge (mode, e1, e2) any changes made. */ static bool -try_crossjump_bb (mode, bb) - int mode; - basic_block bb; +try_crossjump_bb (int mode, basic_block bb) { edge e, e2, nexte2, nexte, fallthru; bool changed; @@ -1585,13 +1717,12 @@ try_crossjump_bb (mode, bb) instructions etc. Return nonzero if changes were made. */ static bool -try_optimize_cfg (mode) - int mode; +try_optimize_cfg (int mode) { bool changed_overall = false; bool changed; int iterations = 0; - basic_block bb, b; + basic_block bb, b, next; if (mode & CLEANUP_CROSSJUMP) add_noreturn_fake_exit_edges (); @@ -1631,8 +1762,9 @@ try_optimize_cfg (mode) fprintf (rtl_dump_file, "Deleting block %i.\n", b->index); - flow_delete_block (b); - changed = true; + delete_block (b); + if (!(mode & CLEANUP_CFGLAYOUT)) + changed = true; b = c; } @@ -1642,9 +1774,9 @@ try_optimize_cfg (mode) if (b->pred->pred_next == NULL && (b->pred->flags & EDGE_FALLTHRU) && !(b->pred->flags & EDGE_COMPLEX) - && GET_CODE (b->head) == CODE_LABEL + && GET_CODE (BB_HEAD (b)) == CODE_LABEL && (!(mode & CLEANUP_PRE_SIBCALL) - || !tail_recursion_label_p (b->head)) + || !tail_recursion_label_p (BB_HEAD (b))) /* If the previous block ends with a branch to this block, we can't delete the label. Normally this is a condjump that is yet to be simplified, but @@ -1652,23 +1784,32 @@ try_optimize_cfg (mode) some element going to the same place as the default (fallthru). */ && (b->pred->src == ENTRY_BLOCK_PTR - || GET_CODE (b->pred->src->end) != JUMP_INSN - || ! label_is_jump_target_p (b->head, - b->pred->src->end))) + || GET_CODE (BB_END (b->pred->src)) != JUMP_INSN + || ! label_is_jump_target_p (BB_HEAD (b), + BB_END (b->pred->src)))) { - rtx label = b->head; + rtx label = BB_HEAD (b); - b->head = NEXT_INSN (b->head); delete_insn_chain (label, label); + /* In the case label is undeletable, move it after the + BASIC_BLOCK note. */ + if (NOTE_LINE_NUMBER (BB_HEAD (b)) == NOTE_INSN_DELETED_LABEL) + { + rtx bb_note = NEXT_INSN (BB_HEAD (b)); + + reorder_insns_nobb (label, label, bb_note); + BB_HEAD (b) = bb_note; + } if (rtl_dump_file) fprintf (rtl_dump_file, "Deleted label in block %i.\n", b->index); } /* If we fall through an empty block, we can remove it. */ - if (b->pred->pred_next == NULL + if (!(mode & CLEANUP_CFGLAYOUT) + && b->pred->pred_next == NULL && (b->pred->flags & EDGE_FALLTHRU) - && GET_CODE (b->head) != CODE_LABEL + && GET_CODE (BB_HEAD (b)) != CODE_LABEL && FORWARDER_BLOCK_P (b) /* Note that forwarder_block_p true ensures that there is a successor for this block. */ @@ -1682,42 +1823,61 @@ try_optimize_cfg (mode) c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb; redirect_edge_succ_nodup (b->pred, b->succ->dest); - flow_delete_block (b); + delete_block (b); changed = true; b = c; } - /* Merge blocks. Loop because chains of blocks might be - combineable. */ - while ((s = b->succ) != NULL - && s->succ_next == NULL - && !(s->flags & EDGE_COMPLEX) - && (c = s->dest) != EXIT_BLOCK_PTR - && c->pred->pred_next == NULL - && b != c - /* If the jump insn has side effects, - we can't kill the edge. */ - && (GET_CODE (b->end) != JUMP_INSN - || (flow2_completed - ? simplejump_p (b->end) - : onlyjump_p (b->end))) - && merge_blocks (s, b, c, mode)) - changed_here = true; + if ((s = b->succ) != NULL + && s->succ_next == NULL + && !(s->flags & EDGE_COMPLEX) + && (c = s->dest) != EXIT_BLOCK_PTR + && c->pred->pred_next == NULL + && b != c) + { + /* When not in cfg_layout mode use code aware of reordering + INSN. This code possibly creates new basic blocks so it + does not fit merge_blocks interface and is kept here in + hope that it will become useless once more of compiler + is transformed to use cfg_layout mode. */ + + if ((mode & CLEANUP_CFGLAYOUT) + && can_merge_blocks_p (b, c)) + { + merge_blocks (b, c); + update_forwarder_flag (b); + changed_here = true; + } + else if (!(mode & CLEANUP_CFGLAYOUT) + /* If the jump insn has side effects, + we can't kill the edge. */ + && (GET_CODE (BB_END (b)) != JUMP_INSN + || (reload_completed + ? simplejump_p (BB_END (b)) + : onlyjump_p (BB_END (b)))) + && (next = merge_blocks_move (s, b, c, mode))) + { + b = next; + changed_here = true; + } + } /* Simplify branch over branch. */ - if ((mode & CLEANUP_EXPENSIVE) && try_simplify_condjump (b)) + if ((mode & CLEANUP_EXPENSIVE) + && !(mode & CLEANUP_CFGLAYOUT) + && try_simplify_condjump (b)) changed_here = true; /* If B has a single outgoing edge, but uses a non-trivial jump instruction without side-effects, we can either delete the jump entirely, or replace it - with a simple unconditional jump. Use - redirect_edge_and_branch to do the dirty work. */ + with a simple unconditional jump. */ if (b->succ && ! b->succ->succ_next && b->succ->dest != EXIT_BLOCK_PTR - && onlyjump_p (b->end) - && redirect_edge_and_branch (b->succ, b->succ->dest)) + && onlyjump_p (BB_END (b)) + && try_redirect_by_replacing_jump (b->succ, b->succ->dest, + (mode & CLEANUP_CFGLAYOUT) != 0)) { update_forwarder_flag (b); changed_here = true; @@ -1765,7 +1925,7 @@ try_optimize_cfg (mode) /* Delete all unreachable basic blocks. */ bool -delete_unreachable_blocks () +delete_unreachable_blocks (void) { bool changed = false; basic_block b, next_bb; @@ -1780,7 +1940,7 @@ delete_unreachable_blocks () if (!(b->flags & BB_REACHABLE)) { - flow_delete_block (b); + delete_block (b); changed = true; } } @@ -1793,8 +1953,7 @@ delete_unreachable_blocks () /* Tidy the CFG by deleting unreachable code and whatnot. */ bool -cleanup_cfg (mode) - int mode; +cleanup_cfg (int mode) { bool changed = false; @@ -1803,7 +1962,7 @@ cleanup_cfg (mode) { changed = true; /* We've possibly created trivially dead code. Cleanup it right - now to introduce more oppurtunities for try_optimize_cfg. */ + now to introduce more opportunities for try_optimize_cfg. */ if (!(mode & (CLEANUP_NO_INSN_DEL | CLEANUP_UPDATE_LIFE | CLEANUP_PRE_SIBCALL)) && !reload_completed) @@ -1817,14 +1976,15 @@ cleanup_cfg (mode) delete_unreachable_blocks (), changed = true; if (mode & CLEANUP_UPDATE_LIFE) { - /* Cleaning up CFG introduces more oppurtunities for dead code - removal that in turn may introduce more oppurtunities for + /* Cleaning up CFG introduces more opportunities for dead code + removal that in turn may introduce more opportunities for cleaning up the CFG. */ if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES, PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE | PROP_KILL_DEAD_CODE - | PROP_LOG_LINKS)) + | ((mode & CLEANUP_LOG_LINKS) + ? PROP_LOG_LINKS : 0))) break; } else if (!(mode & (CLEANUP_NO_INSN_DEL | CLEANUP_PRE_SIBCALL)) |