X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fcfgrtl.c;h=3563574bdeb95ffdbf874d3abe0f9689ba2f92ba;hb=56826b58158ef6eb7bbcea03dfd15dbed65b9199;hp=5209aa2b85f18f27a318100c93979a46f5f44b01;hpb=aaf52ffbaf8c218eee58f8a521b6ee85aac795ef;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/cfgrtl.c b/gcc/cfgrtl.c index 5209aa2b85f..3563574bdeb 100644 --- a/gcc/cfgrtl.c +++ b/gcc/cfgrtl.c @@ -1,6 +1,6 @@ /* Control flow graph manipulation 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. @@ -23,24 +23,19 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA that are aware of the RTL intermediate language. Available functionality: + - Basic CFG/RTL manipulation API documented in cfghooks.h - CFG-aware instruction chain manipulation delete_insn, delete_insn_chain - - Basic block manipulation - create_basic_block, flow_delete_block, split_block, - merge_blocks_nomove + - Edge splitting and committing to edges + insert_insn_on_edge, commit_edge_insertions + - CFG updating after insn simplification + purge_dead_edges, purge_all_dead_edges + + Functions not supposed for generic use: - Infrastructure to determine quickly basic block for insn compute_bb_for_insn, update_bb_for_insn, set_block_for_insn, - Edge redirection with updating and optimizing of insn chain - block_label, redirect_edge_and_branch, - redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru - - Edge splitting and committing to edges - split_edge, insert_insn_on_edge, commit_edge_insertions - - Dumping and debugging - print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n - - Consistency checking - verify_flow_info - - CFG updating after constant propagation - purge_dead_edges, purge_all_dead_edges */ + block_label, tidy_fallthru_edge, force_nonfallthru */ #include "config.h" #include "system.h" @@ -59,44 +54,52 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "tm_p.h" #include "obstack.h" #include "insn-config.h" +#include "cfglayout.h" +#include "expr.h" +#include "target.h" -/* Stubs in case we don't have a return insn. */ -#ifndef HAVE_return -#define HAVE_return 0 -#define gen_return() NULL_RTX -#endif /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */ /* ??? Should probably be using LABEL_NUSES instead. It would take a bit of surgery to be able to use or co-opt the routines in jump. */ rtx label_value_list; -rtx tail_recursion_label_list; - -static int can_delete_note_p PARAMS ((rtx)); -static int can_delete_label_p PARAMS ((rtx)); -static void commit_one_edge_insertion PARAMS ((edge, int)); -static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block)); -static rtx last_loop_beg_note PARAMS ((rtx)); -static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block)); -static basic_block force_nonfallthru_and_redirect PARAMS ((edge, basic_block)); + +static int can_delete_note_p (rtx); +static int can_delete_label_p (rtx); +static void commit_one_edge_insertion (edge, int); +static rtx last_loop_beg_note (rtx); +static bool back_edge_of_syntactic_loop_p (basic_block, basic_block); +static basic_block rtl_split_edge (edge); +static bool rtl_move_block_after (basic_block, basic_block); +static int rtl_verify_flow_info (void); +static basic_block cfg_layout_split_block (basic_block, void *); +static edge cfg_layout_redirect_edge_and_branch (edge, basic_block); +static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block); +static void cfg_layout_delete_block (basic_block); +static void rtl_delete_block (basic_block); +static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block); +static edge rtl_redirect_edge_and_branch (edge, basic_block); +static basic_block rtl_split_block (basic_block, void *); +static void rtl_dump_bb (basic_block, FILE *, int); +static int rtl_verify_flow_info_1 (void); +static void mark_killed_regs (rtx, rtx, void *); +static void rtl_make_forwarder_block (edge); /* Return true if NOTE is not one of the ones that must be kept paired, so that we may simply delete it. */ static int -can_delete_note_p (note) - rtx note; +can_delete_note_p (rtx note) { return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK - || NOTE_LINE_NUMBER (note) == NOTE_INSN_PREDICTION); + || NOTE_LINE_NUMBER (note) == NOTE_INSN_UNLIKELY_EXECUTED_CODE); } /* True if a given label can be deleted. */ static int -can_delete_label_p (label) - rtx label; +can_delete_label_p (rtx label) { return (!LABEL_PRESERVE_P (label) /* User declared labels must be preserved. */ @@ -108,14 +111,13 @@ can_delete_label_p (label) /* Delete INSN by patching it out. Return the next insn. */ rtx -delete_insn (insn) - rtx insn; +delete_insn (rtx insn) { rtx next = NEXT_INSN (insn); rtx note; bool really_delete = true; - if (GET_CODE (insn) == CODE_LABEL) + if (LABEL_P (insn)) { /* Some labels can't be directly removed from the INSN chain, as they might be references via variables, constant pool etc. @@ -127,7 +129,7 @@ delete_insn (insn) really_delete = false; PUT_CODE (insn, NOTE); NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL; - NOTE_SOURCE_FILE (insn) = name; + NOTE_DELETED_LABEL_NAME (insn) = name; } remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels); @@ -136,25 +138,30 @@ delete_insn (insn) if (really_delete) { /* If this insn has already been deleted, something is very wrong. */ - if (INSN_DELETED_P (insn)) - abort (); + gcc_assert (!INSN_DELETED_P (insn)); remove_insn (insn); INSN_DELETED_P (insn) = 1; } /* If deleting a jump, decrement the use count of the label. Deleting the label itself should happen in the normal course of block merging. */ - if (GET_CODE (insn) == JUMP_INSN + if (JUMP_P (insn) && JUMP_LABEL (insn) - && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL) + && LABEL_P (JUMP_LABEL (insn))) LABEL_NUSES (JUMP_LABEL (insn))--; /* Also if deleting an insn that references a label. */ - else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX - && GET_CODE (XEXP (note, 0)) == CODE_LABEL) - LABEL_NUSES (XEXP (note, 0))--; + else + { + while ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX + && LABEL_P (XEXP (note, 0))) + { + LABEL_NUSES (XEXP (note, 0))--; + remove_note (insn, note); + } + } - if (GET_CODE (insn) == JUMP_INSN + if (JUMP_P (insn) && (GET_CODE (PATTERN (insn)) == ADDR_VEC || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)) { @@ -170,7 +177,7 @@ delete_insn (insn) /* When deleting code in bulk (e.g. removing many unreachable blocks) we can delete a label that's a target of the vector before deleting the vector itself. */ - if (GET_CODE (label) != NOTE) + if (!NOTE_P (label)) LABEL_NUSES (label)--; } } @@ -180,15 +187,14 @@ delete_insn (insn) /* Like delete_insn but also purge dead edges from BB. */ rtx -delete_insn_and_edges (insn) - rtx insn; +delete_insn_and_edges (rtx insn) { rtx x; bool purge = false; if (INSN_P (insn) && BLOCK_FOR_INSN (insn) - && BLOCK_FOR_INSN (insn)->end == insn) + && BB_END (BLOCK_FOR_INSN (insn)) == insn) purge = true; x = delete_insn (insn); if (purge) @@ -200,8 +206,7 @@ delete_insn_and_edges (insn) that must be paired. */ void -delete_insn_chain (start, finish) - rtx start, finish; +delete_insn_chain (rtx start, rtx finish) { rtx next; @@ -211,7 +216,7 @@ delete_insn_chain (start, finish) while (1) { next = NEXT_INSN (start); - if (GET_CODE (start) == NOTE && !can_delete_note_p (start)) + if (NOTE_P (start) && !can_delete_note_p (start)) ; else next = delete_insn (start); @@ -224,14 +229,13 @@ delete_insn_chain (start, finish) /* Like delete_insn but also purge dead edges from BB. */ void -delete_insn_chain_and_edges (first, last) - rtx first, last; +delete_insn_chain_and_edges (rtx first, rtx last) { bool purge = false; if (INSN_P (last) && BLOCK_FOR_INSN (last) - && BLOCK_FOR_INSN (last)->end == last) + && BB_END (BLOCK_FOR_INSN (last)) == last) purge = true; delete_insn_chain (first, last); if (purge) @@ -247,14 +251,11 @@ delete_insn_chain_and_edges (first, last) AFTER is the basic block we should be put after. */ basic_block -create_basic_block_structure (head, end, bb_note, after) - rtx head, end, bb_note; - basic_block after; +create_basic_block_structure (rtx head, rtx end, rtx bb_note, basic_block after) { basic_block bb; if (bb_note - && ! RTX_INTEGRATED_P (bb_note) && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL && bb->aux == NULL) { @@ -262,7 +263,7 @@ create_basic_block_structure (head, end, bb_note, after) rtx after; - if (GET_CODE (head) == CODE_LABEL) + if (LABEL_P (head)) after = head; else { @@ -282,7 +283,7 @@ create_basic_block_structure (head, end, bb_note, after) if (!head && !end) head = end = bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ()); - else if (GET_CODE (head) == CODE_LABEL && end) + else if (LABEL_P (head) && end) { bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head); if (head == end) @@ -303,13 +304,14 @@ create_basic_block_structure (head, end, bb_note, after) if (NEXT_INSN (end) == bb_note) end = bb_note; - bb->head = head; - bb->end = end; + BB_HEAD (bb) = head; + BB_END (bb) = end; bb->index = last_basic_block++; bb->flags = BB_NEW; link_block (bb, after); BASIC_BLOCK (bb->index) = bb; update_bb_for_insn (bb); + BB_SET_PARTITION (bb, BB_UNPARTITIONED); /* Tag the block so that we know it has been used when considering other basic block notes. */ @@ -323,15 +325,18 @@ create_basic_block_structure (head, end, bb_note, after) create new empty basic block before HEAD. Both END and HEAD can be NULL to create basic block at the end of INSN chain. */ -basic_block -create_basic_block (head, end, after) - rtx head, end; - basic_block after; +static basic_block +rtl_create_basic_block (void *headp, void *endp, basic_block after) { + rtx head = headp, end = endp; basic_block bb; - /* Place the new block just after the end. */ - VARRAY_GROW (basic_block_info, last_basic_block+1); + /* Grow the basic block array if needed. */ + if ((size_t) last_basic_block >= VARRAY_SIZE (basic_block_info)) + { + size_t new_size = last_basic_block + (last_basic_block + 3) / 4; + VARRAY_GROW (basic_block_info, new_size); + } n_basic_blocks++; @@ -339,6 +344,15 @@ create_basic_block (head, end, after) bb->aux = NULL; return bb; } + +static basic_block +cfg_layout_create_basic_block (void *head, void *end, basic_block after) +{ + basic_block newbb = rtl_create_basic_block (head, end, after); + + initialize_bb_rbi (newbb); + return newbb; +} /* Delete the insns in a (non-live) block. We physically delete every non-deleted-note insn, and update the flow graph appropriately. @@ -348,11 +362,9 @@ create_basic_block (head, end, after) /* ??? Preserving all such notes strikes me as wrong. It would be nice to post-process the stream to remove empty blocks, loops, ranges, etc. */ -int -flow_delete_block_noexpunge (b) - basic_block b; +static void +rtl_delete_block (basic_block b) { - int deleted_handler = 0; rtx insn, end, tmp; /* If the head of this block is a CODE_LABEL, then it might be the @@ -362,82 +374,39 @@ flow_delete_block_noexpunge (b) and remove the associated NOTE_INSN_EH_REGION_BEG and NOTE_INSN_EH_REGION_END notes. */ - /* Get rid of all NOTE_INSN_PREDICTIONs and NOTE_INSN_LOOP_CONTs - hanging before the block. */ - - for (insn = PREV_INSN (b->head); insn; insn = PREV_INSN (insn)) - { - if (GET_CODE (insn) != NOTE) - break; - if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_PREDICTION - || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT) - NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED; - } - - insn = b->head; - - never_reached_warning (insn, b->end); + insn = BB_HEAD (b); - if (GET_CODE (insn) == CODE_LABEL) + if (LABEL_P (insn)) maybe_remove_eh_handler (insn); /* Include any jump table following the basic block. */ - end = b->end; - if (GET_CODE (end) == JUMP_INSN - && (tmp = JUMP_LABEL (end)) != NULL_RTX - && (tmp = NEXT_INSN (tmp)) != NULL_RTX - && GET_CODE (tmp) == JUMP_INSN - && (GET_CODE (PATTERN (tmp)) == ADDR_VEC - || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC)) + end = BB_END (b); + if (tablejump_p (end, NULL, &tmp)) end = tmp; /* Include any barrier that may follow the basic block. */ tmp = next_nonnote_insn (end); - if (tmp && GET_CODE (tmp) == BARRIER) + if (tmp && BARRIER_P (tmp)) end = tmp; /* Selectively delete the entire chain. */ - b->head = NULL; + BB_HEAD (b) = NULL; delete_insn_chain (insn, end); - - /* Remove the edges into and out of this block. Note that there may - indeed be edges in, if we are removing an unreachable loop. */ - while (b->pred != NULL) - remove_edge (b->pred); - while (b->succ != NULL) - remove_edge (b->succ); - - b->pred = NULL; - b->succ = NULL; - - return deleted_handler; -} - -int -flow_delete_block (b) - basic_block b; -{ - int deleted_handler = flow_delete_block_noexpunge (b); - - /* Remove the basic block from the array. */ - expunge_block (b); - - return deleted_handler; } /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */ void -compute_bb_for_insn () +compute_bb_for_insn (void) { basic_block bb; FOR_EACH_BB (bb) { - rtx end = bb->end; + rtx end = BB_END (bb); rtx insn; - for (insn = bb->head; ; insn = NEXT_INSN (insn)) + for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) { BLOCK_FOR_INSN (insn) = bb; if (insn == end) @@ -449,63 +418,75 @@ compute_bb_for_insn () /* Release the basic_block_for_insn array. */ void -free_bb_for_insn () +free_bb_for_insn (void) { rtx insn; for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) - if (GET_CODE (insn) != BARRIER) + if (!BARRIER_P (insn)) BLOCK_FOR_INSN (insn) = NULL; } +/* Return RTX to emit after when we want to emit code on the entry of function. */ +rtx +entry_of_function (void) +{ + return (n_basic_blocks ? BB_HEAD (ENTRY_BLOCK_PTR->next_bb) : get_insns ()); +} + /* Update insns block within BB. */ void -update_bb_for_insn (bb) - basic_block bb; +update_bb_for_insn (basic_block bb) { rtx insn; - for (insn = bb->head; ; insn = NEXT_INSN (insn)) + for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) { - set_block_for_insn (insn, bb); - if (insn == bb->end) + if (!BARRIER_P (insn)) + set_block_for_insn (insn, bb); + if (insn == BB_END (bb)) break; } } -/* Split a block BB after insn INSN creating a new fallthru edge. - Return the new edge. Note that to keep other parts of the compiler happy, - this function renumbers all the basic blocks so that the new - one has a number one greater than the block split. */ +/* Creates a new basic block just after basic block B by splitting + everything after specified instruction I. */ -edge -split_block (bb, insn) - basic_block bb; - rtx insn; +static basic_block +rtl_split_block (basic_block bb, void *insnp) { basic_block new_bb; - edge new_edge; + rtx insn = insnp; edge e; + edge_iterator ei; - /* There is no point splitting the block after its end. */ - if (bb->end == insn) - return 0; + if (!insn) + { + insn = first_insn_after_basic_block_note (bb); + + if (insn) + insn = PREV_INSN (insn); + else + insn = get_last_insn (); + } + + /* We probably should check type of the insn so that we do not create + inconsistent cfg. It is checked in verify_flow_info anyway, so do not + bother. */ + if (insn == BB_END (bb)) + emit_note_after (NOTE_INSN_DELETED, insn); /* Create the new basic block. */ - new_bb = create_basic_block (NEXT_INSN (insn), bb->end, bb); - new_bb->count = bb->count; - new_bb->frequency = bb->frequency; - new_bb->loop_depth = bb->loop_depth; - bb->end = insn; + new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb); + BB_COPY_PARTITION (new_bb, bb); + BB_END (bb) = insn; /* Redirect the outgoing edges. */ - new_bb->succ = bb->succ; - bb->succ = NULL; - for (e = new_bb->succ; e; e = e->succ_next) + new_bb->succs = bb->succs; + bb->succs = NULL; + FOR_EACH_EDGE (e, ei, new_bb->succs) e->src = new_bb; - new_edge = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU); - if (bb->global_live_at_start) { new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack); @@ -532,23 +513,21 @@ split_block (bb, insn) #endif } - return new_edge; + return new_bb; } /* Blocks A and B are to be merged into a single block A. The insns - are already contiguous, hence `nomove'. */ + are already contiguous. */ -void -merge_blocks_nomove (a, b) - basic_block a, b; +static void +rtl_merge_blocks (basic_block a, basic_block b) { - rtx b_head = b->head, b_end = b->end, a_end = a->end; + rtx b_head = BB_HEAD (b), b_end = BB_END (b), a_end = BB_END (a); rtx del_first = NULL_RTX, del_last = NULL_RTX; int b_empty = 0; - edge e; /* If there was a CODE_LABEL beginning B, delete it. */ - if (GET_CODE (b_head) == CODE_LABEL) + if (LABEL_P (b_head)) { /* Detect basic blocks with nothing but a label. This can happen in particular at the end of a function. */ @@ -573,14 +552,14 @@ merge_blocks_nomove (a, b) } /* If there was a jump out of A, delete it. */ - if (GET_CODE (a_end) == JUMP_INSN) + if (JUMP_P (a_end)) { rtx prev; for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev)) - if (GET_CODE (prev) != NOTE + if (!NOTE_P (prev) || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK - || prev == a->head) + || prev == BB_HEAD (a)) break; del_first = a_end; @@ -594,37 +573,19 @@ merge_blocks_nomove (a, b) prev = prev_nonnote_insn (prev); if (!prev) - prev = a->head; + prev = BB_HEAD (a); del_first = tmp; } #endif a_end = PREV_INSN (del_first); } - else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER) + else if (BARRIER_P (NEXT_INSN (a_end))) del_first = NEXT_INSN (a_end); - /* Normally there should only be one successor of A and that is B, but - partway though the merge of blocks for conditional_execution we'll - be merging a TEST block with THEN and ELSE successors. Free the - whole lot of them and hope the caller knows what they're doing. */ - while (a->succ) - remove_edge (a->succ); - - /* Adjust the edges out of B for the new owner. */ - for (e = b->succ; e; e = e->succ_next) - e->src = a; - a->succ = b->succ; - a->flags |= b->flags; - - /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */ - b->pred = b->succ = NULL; - a->global_live_at_end = b->global_live_at_end; - - expunge_block (b); - /* Delete everything marked above as well as crap that might be hanging out between the two blocks. */ + BB_HEAD (b) = NULL; delete_insn_chain (del_first, del_last); /* Reassociate the insns of B with A. */ @@ -640,25 +601,60 @@ merge_blocks_nomove (a, b) a_end = b_end; } - a->end = a_end; + BB_END (a) = a_end; +} + +/* Return true when block A and B can be merged. */ +static bool +rtl_can_merge_blocks (basic_block a,basic_block b) +{ + /* If we are partitioning hot/cold basic blocks, we don't want to + mess up unconditional or indirect jumps that cross between hot + and cold sections. + + Basic block partitioning may result in some jumps that appear to + be optimizable (or blocks that appear to be mergeable), but which really + must be left untouched (they are required to make it safely across + partition boundaries). See the comments at the top of + bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ + + if (flag_reorder_blocks_and_partition + && (find_reg_note (BB_END (a), REG_CROSSING_JUMP, NULL_RTX) + || find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX) + || BB_PARTITION (a) != BB_PARTITION (b))) + return false; + + /* There must be exactly one edge in between the blocks. */ + return (EDGE_COUNT (a->succs) == 1 + && EDGE_SUCC (a, 0)->dest == b + && EDGE_COUNT (b->preds) == 1 + && a != b + /* Must be simple edge. */ + && !(EDGE_SUCC (a, 0)->flags & EDGE_COMPLEX) + && a->next_bb == b + && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR + /* If the jump insn has side effects, + we can't kill the edge. */ + && (!JUMP_P (BB_END (a)) + || (reload_completed + ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a))))); } /* Return the label in the head of basic block BLOCK. Create one if it doesn't exist. */ rtx -block_label (block) - basic_block block; +block_label (basic_block block) { if (block == EXIT_BLOCK_PTR) return NULL_RTX; - if (GET_CODE (block->head) != CODE_LABEL) + if (!LABEL_P (BB_HEAD (block))) { - block->head = emit_label_before (gen_label_rtx (), block->head); + BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block)); } - return block->head; + return BB_HEAD (block); } /* Attempt to perform edge redirection by replacing possibly complex jump @@ -666,35 +662,45 @@ block_label (block) apply only if all edges now point to the same block. The parameters and return values are equivalent to redirect_edge_and_branch. */ -static bool -try_redirect_by_replacing_jump (e, target) - edge e; - basic_block target; +edge +try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout) { basic_block src = e->src; - rtx insn = src->end, kill_from; + rtx insn = BB_END (src), kill_from; edge tmp; - rtx set, table; + rtx set; int fallthru = 0; + edge_iterator ei; + + /* If we are partitioning hot/cold basic blocks, we don't want to + mess up unconditional or indirect jumps that cross between hot + and cold sections. + + Basic block partitioning may result in some jumps that appear to + be optimizable (or blocks that appear to be mergeable), but which really + must be left untouched (they are required to make it safely across + partition boundaries). See the comments at the top of + bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ + + if (flag_reorder_blocks_and_partition + && (find_reg_note (insn, REG_CROSSING_JUMP, NULL_RTX) + || BB_PARTITION (src) != BB_PARTITION (target))) + return NULL; /* Verify that all targets will be TARGET. */ - for (tmp = src->succ; tmp; tmp = tmp->succ_next) + FOR_EACH_EDGE (tmp, ei, src->succs) if (tmp->dest != target && tmp != e) break; if (tmp || !onlyjump_p (insn)) - return false; - if (reload_completed && JUMP_LABEL (insn) - && (table = NEXT_INSN (JUMP_LABEL (insn))) != NULL_RTX - && GET_CODE (table) == JUMP_INSN - && (GET_CODE (PATTERN (table)) == ADDR_VEC - || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC)) - return false; + return NULL; + if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL)) + return NULL; /* Avoid removing branch with side effects. */ set = single_set (insn); if (!set || side_effects_p (set)) - return false; + return NULL; /* In case we zap a conditional jump, we'll need to kill the cc0 setter too. */ @@ -705,48 +711,71 @@ try_redirect_by_replacing_jump (e, target) #endif /* See if we can create the fallthru edge. */ - if (can_fallthru (src, target)) + if (in_cfglayout || can_fallthru (src, target)) { - if (rtl_dump_file) - fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn)); + if (dump_file) + fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn)); fallthru = 1; /* Selectively unlink whole insn chain. */ - delete_insn_chain (kill_from, PREV_INSN (target->head)); + if (in_cfglayout) + { + rtx insn = src->rbi->footer; + + delete_insn_chain (kill_from, BB_END (src)); + + /* Remove barriers but keep jumptables. */ + while (insn) + { + if (BARRIER_P (insn)) + { + if (PREV_INSN (insn)) + NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn); + else + src->rbi->footer = NEXT_INSN (insn); + if (NEXT_INSN (insn)) + PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn); + } + if (LABEL_P (insn)) + break; + insn = NEXT_INSN (insn); + } + } + else + delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target))); } /* If this already is simplejump, redirect it. */ else if (simplejump_p (insn)) { if (e->dest == target) - return false; - if (rtl_dump_file) - fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n", + return NULL; + if (dump_file) + fprintf (dump_file, "Redirecting jump %i from %i to %i.\n", INSN_UID (insn), e->dest->index, target->index); if (!redirect_jump (insn, block_label (target), 0)) { - if (target == EXIT_BLOCK_PTR) - return false; - abort (); + gcc_assert (target == EXIT_BLOCK_PTR); + return NULL; } } /* Cannot do anything for target exit block. */ else if (target == EXIT_BLOCK_PTR) - return false; + return NULL; /* Or replace possibly complicated jump insn by simple jump insn. */ else { rtx target_label = block_label (target); - rtx barrier, tmp; + rtx barrier, label, table; - emit_jump_insn_after (gen_jump (target_label), insn); - JUMP_LABEL (src->end) = target_label; + emit_jump_insn_after_noloc (gen_jump (target_label), insn); + JUMP_LABEL (BB_END (src)) = target_label; LABEL_NUSES (target_label)++; - if (rtl_dump_file) - fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n", - INSN_UID (insn), INSN_UID (src->end)); + if (dump_file) + fprintf (dump_file, "Replacing insn %i by jump %i\n", + INSN_UID (insn), INSN_UID (BB_END (src))); delete_insn_chain (kill_from, insn); @@ -754,24 +783,43 @@ try_redirect_by_replacing_jump (e, target) /* Recognize a tablejump that we are converting to a simple jump and remove its associated CODE_LABEL and ADDR_VEC or ADDR_DIFF_VEC. */ - if ((tmp = JUMP_LABEL (insn)) != NULL_RTX - && (tmp = NEXT_INSN (tmp)) != NULL_RTX - && GET_CODE (tmp) == JUMP_INSN - && (GET_CODE (PATTERN (tmp)) == ADDR_VEC - || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC)) + if (tablejump_p (insn, &label, &table)) + delete_insn_chain (label, table); + + barrier = next_nonnote_insn (BB_END (src)); + if (!barrier || !BARRIER_P (barrier)) + emit_barrier_after (BB_END (src)); + else { - delete_insn_chain (JUMP_LABEL (insn), tmp); - } + if (barrier != NEXT_INSN (BB_END (src))) + { + /* Move the jump before barrier so that the notes + which originally were or were created before jump table are + inside the basic block. */ + rtx new_insn = BB_END (src); + rtx tmp; - barrier = next_nonnote_insn (src->end); - if (!barrier || GET_CODE (barrier) != BARRIER) - emit_barrier_after (src->end); + for (tmp = NEXT_INSN (BB_END (src)); tmp != barrier; + tmp = NEXT_INSN (tmp)) + set_block_for_insn (tmp, src); + + NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn); + PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn); + + NEXT_INSN (new_insn) = barrier; + NEXT_INSN (PREV_INSN (barrier)) = new_insn; + + PREV_INSN (new_insn) = PREV_INSN (barrier); + PREV_INSN (barrier) = new_insn; + } + } } /* Keep only one edge out and set proper flags. */ - while (src->succ->succ_next) - remove_edge (src->succ); - e = src->succ; + while (EDGE_COUNT (src->succs) > 1) + remove_edge (e); + + e = EDGE_SUCC (src, 0); if (fallthru) e->flags = EDGE_FALLTHRU; else @@ -782,14 +830,14 @@ try_redirect_by_replacing_jump (e, target) /* We don't want a block to end on a line-number note since that has the potential of changing the code between -g and not -g. */ - while (GET_CODE (e->src->end) == NOTE - && NOTE_LINE_NUMBER (e->src->end) >= 0) - delete_insn (e->src->end); + while (NOTE_P (BB_END (e->src)) + && NOTE_LINE_NUMBER (BB_END (e->src)) >= 0) + delete_insn (BB_END (e->src)); if (e->dest != target) redirect_edge_succ (e, target); - return true; + return e; } /* Return last loop_beg note appearing after INSN, before start of next @@ -801,12 +849,11 @@ try_redirect_by_replacing_jump (e, target) test. */ static rtx -last_loop_beg_note (insn) - rtx insn; +last_loop_beg_note (rtx insn) { rtx last = insn; - for (insn = NEXT_INSN (insn); insn && GET_CODE (insn) == NOTE + for (insn = NEXT_INSN (insn); insn && NOTE_P (insn) && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK; insn = NEXT_INSN (insn)) if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) @@ -815,57 +862,31 @@ last_loop_beg_note (insn) return last; } -/* Attempt to change code to redirect edge E to TARGET. Don't do that on - expense of adding new instructions or reordering basic blocks. - - Function can be also called with edge destination equivalent to the TARGET. - Then it should try the simplifications and do nothing if none is possible. - - Return true if transformation succeeded. We still return false in case E - already destinated TARGET and we didn't managed to simplify instruction - stream. */ - -bool -redirect_edge_and_branch (e, target) - edge e; - basic_block target; +/* Redirect edge representing branch of (un)conditional jump or tablejump, + NULL on failure */ +static edge +redirect_branch_edge (edge e, basic_block target) { rtx tmp; - rtx old_label = e->dest->head; + rtx old_label = BB_HEAD (e->dest); basic_block src = e->src; - rtx insn = src->end; - - if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) - return false; - - if (try_redirect_by_replacing_jump (e, target)) - return true; - - /* Do this fast path late, as we want above code to simplify for cases - where called on single edge leaving basic block containing nontrivial - jump insn. */ - else if (e->dest == target) - return false; + rtx insn = BB_END (src); /* We can only redirect non-fallthru edges of jump insn. */ if (e->flags & EDGE_FALLTHRU) - return false; - else if (GET_CODE (insn) != JUMP_INSN) - return false; + return NULL; + else if (!JUMP_P (insn)) + return NULL; /* Recognize a tablejump and adjust all matching cases. */ - if ((tmp = JUMP_LABEL (insn)) != NULL_RTX - && (tmp = NEXT_INSN (tmp)) != NULL_RTX - && GET_CODE (tmp) == JUMP_INSN - && (GET_CODE (PATTERN (tmp)) == ADDR_VEC - || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC)) + if (tablejump_p (insn, NULL, &tmp)) { rtvec vec; int j; rtx new_label = block_label (target); if (target == EXIT_BLOCK_PTR) - return false; + return NULL; if (GET_CODE (PATTERN (tmp)) == ADDR_VEC) vec = XVEC (PATTERN (tmp), 0); else @@ -879,7 +900,7 @@ redirect_edge_and_branch (e, target) ++LABEL_NUSES (new_label); } - /* Handle casesi dispatch insns */ + /* Handle casesi dispatch insns. */ if ((tmp = single_set (insn)) != NULL && SET_DEST (tmp) == pc_rtx && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE @@ -900,98 +921,172 @@ redirect_edge_and_branch (e, target) if (computed_jump_p (insn) /* A return instruction can't be redirected. */ || returnjump_p (insn)) - return false; + return NULL; /* If the insn doesn't go where we think, we're confused. */ - if (JUMP_LABEL (insn) != old_label) - abort (); + gcc_assert (JUMP_LABEL (insn) == old_label); /* If the substitution doesn't succeed, die. This can happen if the back end emitted unrecognizable instructions or if target is exit block on some arches. */ if (!redirect_jump (insn, block_label (target), 0)) { - if (target == EXIT_BLOCK_PTR) - return false; - abort (); + gcc_assert (target == EXIT_BLOCK_PTR); + return NULL; } } - if (rtl_dump_file) - fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n", + if (dump_file) + fprintf (dump_file, "Edge %i->%i redirected to %i\n", e->src->index, e->dest->index, target->index); if (e->dest != target) - redirect_edge_succ_nodup (e, target); + e = redirect_edge_succ_nodup (e, target); + return e; +} - return true; +/* Attempt to change code to redirect edge E to TARGET. Don't do that on + expense of adding new instructions or reordering basic blocks. + + Function can be also called with edge destination equivalent to the TARGET. + Then it should try the simplifications and do nothing if none is possible. + + Return edge representing the branch if transformation succeeded. Return NULL + on failure. + We still return NULL in case E already destinated TARGET and we didn't + managed to simplify instruction stream. */ + +static edge +rtl_redirect_edge_and_branch (edge e, basic_block target) +{ + edge ret; + basic_block src = e->src; + + if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) + return NULL; + + if (e->dest == target) + return e; + + if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL) + { + src->flags |= BB_DIRTY; + return ret; + } + + ret = redirect_branch_edge (e, target); + if (!ret) + return NULL; + + src->flags |= BB_DIRTY; + return ret; } /* Like force_nonfallthru below, but additionally performs redirection Used by redirect_edge_and_branch_force. */ static basic_block -force_nonfallthru_and_redirect (e, target) - edge e; - basic_block target; +force_nonfallthru_and_redirect (edge e, basic_block target) { basic_block jump_block, new_bb = NULL, src = e->src; rtx note; edge new_edge; int abnormal_edge_flags = 0; + /* In the case the last instruction is conditional jump to the next + instruction, first redirect the jump itself and then continue + by creating a basic block afterwards to redirect fallthru edge. */ + if (e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR + && any_condjump_p (BB_END (e->src)) + /* When called from cfglayout, fallthru edges do not + necessarily go to the next block. */ + && e->src->next_bb == e->dest + && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest)) + { + rtx note; + edge b = unchecked_make_edge (e->src, target, 0); + bool redirected; + + redirected = redirect_jump (BB_END (e->src), block_label (target), 0); + gcc_assert (redirected); + + note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX); + if (note) + { + int prob = INTVAL (XEXP (note, 0)); + + b->probability = prob; + b->count = e->count * prob / REG_BR_PROB_BASE; + e->probability -= e->probability; + e->count -= b->count; + if (e->probability < 0) + e->probability = 0; + if (e->count < 0) + e->count = 0; + } + } + if (e->flags & EDGE_ABNORMAL) { /* Irritating special case - fallthru edge to the same block as abnormal edge. We can't redirect abnormal edge, but we still can split the fallthru - one and create separate abnormal edge to original destination. + one and create separate abnormal edge to original destination. This allows bb-reorder to make such edge non-fallthru. */ - if (e->dest != target) - abort (); + gcc_assert (e->dest == target); abnormal_edge_flags = e->flags & ~(EDGE_FALLTHRU | EDGE_CAN_FALLTHRU); e->flags &= EDGE_FALLTHRU | EDGE_CAN_FALLTHRU; } - else if (!(e->flags & EDGE_FALLTHRU)) - abort (); - else if (e->src == ENTRY_BLOCK_PTR) + else { - /* We can't redirect the entry block. Create an empty block at the - start of the function which we use to add the new jump. */ - edge *pe1; - basic_block bb = create_basic_block (e->dest->head, NULL, ENTRY_BLOCK_PTR); - - /* Change the existing edge's source to be the new block, and add - a new edge from the entry block to the new block. */ - e->src = bb; - for (pe1 = &ENTRY_BLOCK_PTR->succ; *pe1; pe1 = &(*pe1)->succ_next) - if (*pe1 == e) - { - *pe1 = e->succ_next; - break; - } - e->succ_next = 0; - bb->succ = e; - make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU); + gcc_assert (e->flags & EDGE_FALLTHRU); + if (e->src == ENTRY_BLOCK_PTR) + { + /* We can't redirect the entry block. Create an empty block + at the start of the function which we use to add the new + jump. */ + edge tmp; + edge_iterator ei; + bool found = false; + + basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL, ENTRY_BLOCK_PTR); + + /* Change the existing edge's source to be the new block, and add + a new edge from the entry block to the new block. */ + e->src = bb; + for (ei = ei_start (ENTRY_BLOCK_PTR->succs); (tmp = ei_safe_edge (ei)); ) + { + if (tmp == e) + { + VEC_unordered_remove (edge, ENTRY_BLOCK_PTR->succs, ei.index); + found = true; + break; + } + else + ei_next (&ei); + } + + gcc_assert (found); + + VEC_safe_push (edge, bb->succs, e); + make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU); + } } - if (e->src->succ->succ_next || abnormal_edge_flags) + if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags) { /* Create the new structures. */ + /* If the old block ended with a tablejump, skip its table + by searching forward from there. Otherwise start searching + forward from the last instruction of the old block. */ + if (!tablejump_p (BB_END (e->src), NULL, ¬e)) + note = BB_END (e->src); + /* Position the new block correctly relative to loop notes. */ - note = last_loop_beg_note (e->src->end); + note = last_loop_beg_note (note); note = NEXT_INSN (note); - /* ... and ADDR_VECs. */ - if (note != NULL - && GET_CODE (note) == CODE_LABEL - && NEXT_INSN (note) - && GET_CODE (NEXT_INSN (note)) == JUMP_INSN - && (GET_CODE (PATTERN (NEXT_INSN (note))) == ADDR_DIFF_VEC - || GET_CODE (PATTERN (NEXT_INSN (note))) == ADDR_VEC)) - note = NEXT_INSN (NEXT_INSN (note)); - jump_block = create_basic_block (note, NULL, e->src); jump_block->count = e->count; jump_block->frequency = EDGE_FREQUENCY (e); @@ -1009,6 +1104,33 @@ force_nonfallthru_and_redirect (e, target) target->global_live_at_start); } + /* Make sure new block ends up in correct hot/cold section. */ + + BB_COPY_PARTITION (jump_block, e->src); + if (flag_reorder_blocks_and_partition + && targetm.have_named_sections) + { + if (BB_PARTITION (jump_block) == BB_COLD_PARTITION) + { + rtx bb_note, new_note; + for (bb_note = BB_HEAD (jump_block); + bb_note && bb_note != NEXT_INSN (BB_END (jump_block)); + bb_note = NEXT_INSN (bb_note)) + if (NOTE_P (bb_note) + && NOTE_LINE_NUMBER (bb_note) == NOTE_INSN_BASIC_BLOCK) + break; + new_note = emit_note_after (NOTE_INSN_UNLIKELY_EXECUTED_CODE, + bb_note); + NOTE_BASIC_BLOCK (new_note) = jump_block; + } + if (JUMP_P (BB_END (jump_block)) + && !any_condjump_p (BB_END (jump_block)) + && (EDGE_SUCC (jump_block, 0)->flags & EDGE_CROSSING)) + REG_NOTES (BB_END (jump_block)) = gen_rtx_EXPR_LIST + (REG_CROSSING_JUMP, NULL_RTX, + REG_NOTES (BB_END (jump_block))); + } + /* Wire edge in. */ new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU); new_edge->probability = e->probability; @@ -1026,20 +1148,21 @@ force_nonfallthru_and_redirect (e, target) e->flags &= ~EDGE_FALLTHRU; if (target == EXIT_BLOCK_PTR) { - if (HAVE_return) - emit_jump_insn_after (gen_return (), jump_block->end); - else - abort (); +#ifdef HAVE_return + emit_jump_insn_after_noloc (gen_return (), BB_END (jump_block)); +#else + gcc_unreachable (); +#endif } else { rtx label = block_label (target); - emit_jump_insn_after (gen_jump (label), jump_block->end); - JUMP_LABEL (jump_block->end) = label; + emit_jump_insn_after_noloc (gen_jump (label), BB_END (jump_block)); + JUMP_LABEL (BB_END (jump_block)) = label; LABEL_NUSES (label)++; } - emit_barrier_after (jump_block->end); + emit_barrier_after (BB_END (jump_block)); redirect_edge_succ_nodup (e, target); if (abnormal_edge_flags) @@ -1053,8 +1176,7 @@ force_nonfallthru_and_redirect (e, target) Return newly created BB or NULL if none. */ basic_block -force_nonfallthru (e) - edge e; +force_nonfallthru (edge e) { return force_nonfallthru_and_redirect (e, e->dest); } @@ -1063,10 +1185,8 @@ force_nonfallthru (e) basic block. Return new basic block if created, NULL otherwise. Abort if conversion is impossible. */ -basic_block -redirect_edge_and_branch_force (e, target) - edge e; - basic_block target; +static basic_block +rtl_redirect_edge_and_branch_force (edge e, basic_block target) { if (redirect_edge_and_branch (e, target) || e->dest == target) @@ -1080,12 +1200,17 @@ redirect_edge_and_branch_force (e, target) /* The given edge should potentially be a fallthru edge. If that is in fact true, delete the jump and barriers that are in the way. */ -void -tidy_fallthru_edge (e, b, c) - edge e; - basic_block b, c; +static void +rtl_tidy_fallthru_edge (edge e) { rtx q; + basic_block b = e->src, c = b->next_bb; + edge e2; + edge_iterator ei; + + FOR_EACH_EDGE (e2, ei, b->succs) + if (e == e2) + break; /* ??? In a late-running flow pass, other folks may have deleted basic blocks by nopping out blocks, leaving multiple BARRIERs between here @@ -1097,18 +1222,18 @@ tidy_fallthru_edge (e, b, c) So search through a sequence of barriers, labels, and notes for the head of block C and assert that we really do fall through. */ - for (q = NEXT_INSN (b->end); q != c->head; q = NEXT_INSN (q)) + for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q)) if (INSN_P (q)) return; /* Remove what will soon cease being the jump insn from the source block. If block B consisted only of this single jump, turn it into a deleted note. */ - q = b->end; - if (GET_CODE (q) == JUMP_INSN + q = BB_END (b); + if (JUMP_P (q) && onlyjump_p (q) && (any_uncondjump_p (q) - || (b->succ == e && e->succ_next == NULL))) + || (EDGE_SUCC (b, 0) == e && ei.index == EDGE_COUNT (b->succs) - 1))) { #ifdef HAVE_cc0 /* If this was a conditional jump, we need to also delete @@ -1121,65 +1246,22 @@ tidy_fallthru_edge (e, b, c) /* We don't want a block to end on a line-number note since that has the potential of changing the code between -g and not -g. */ - while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0) + while (NOTE_P (q) && NOTE_LINE_NUMBER (q) >= 0) q = PREV_INSN (q); } /* Selectively unlink the sequence. */ - if (q != PREV_INSN (c->head)) - delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head)); + if (q != PREV_INSN (BB_HEAD (c))) + delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c))); e->flags |= EDGE_FALLTHRU; } - -/* Fix up edges that now fall through, or rather should now fall through - but previously required a jump around now deleted blocks. Simplify - the search by only examining blocks numerically adjacent, since this - is how find_basic_blocks created them. */ - -void -tidy_fallthru_edges () -{ - basic_block b, c; - - if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR) - return; - - FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb) - { - edge s; - - c = b->next_bb; - - /* We care about simple conditional or unconditional jumps with - a single successor. - - If we had a conditional branch to the next instruction when - find_basic_blocks was called, then there will only be one - out edge for the block which ended with the conditional - branch (since we do not create duplicate edges). - - Furthermore, the edge will be marked as a fallthru because we - merge the flags for the duplicate edges. So we do not want to - check that the edge is not a FALLTHRU edge. */ - - if ((s = b->succ) != NULL - && ! (s->flags & EDGE_COMPLEX) - && s->succ_next == NULL - && s->dest == c - /* If the jump insn has side effects, we can't tidy the edge. */ - && (GET_CODE (b->end) != JUMP_INSN - || onlyjump_p (b->end))) - tidy_fallthru_edge (s, b, c); - } -} /* Helper function for split_edge. Return true in case edge BB2 to BB1 is back edge of syntactic loop. */ static bool -back_edge_of_syntactic_loop_p (bb1, bb2) - basic_block bb1, bb2; +back_edge_of_syntactic_loop_p (basic_block bb1, basic_block bb2) { rtx insn; int count = 0; @@ -1196,9 +1278,9 @@ back_edge_of_syntactic_loop_p (bb1, bb2) if (!bb) return false; - for (insn = bb1->end; insn != bb2->head && count >= 0; + for (insn = BB_END (bb1); insn != BB_HEAD (bb2) && count >= 0; insn = NEXT_INSN (insn)) - if (GET_CODE (insn) == NOTE) + if (NOTE_P (insn)) { if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) count++; @@ -1209,6 +1291,15 @@ back_edge_of_syntactic_loop_p (bb1, bb2) return count >= 0; } +/* Should move basic block BB after basic block AFTER. NIY. */ + +static bool +rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED, + basic_block after ATTRIBUTE_UNUSED) +{ + return false; +} + /* Split a (typically critical) edge. Return the new block. Abort on abnormal edges. @@ -1216,24 +1307,23 @@ back_edge_of_syntactic_loop_p (bb1, bb2) The case of a block ending in an unconditional jump to a block with multiple predecessors is not handled optimally. */ -basic_block -split_edge (edge_in) - edge edge_in; +static basic_block +rtl_split_edge (edge edge_in) { basic_block bb; rtx before; /* Abnormal edges cannot be split. */ - if ((edge_in->flags & EDGE_ABNORMAL) != 0) - abort (); + gcc_assert (!(edge_in->flags & EDGE_ABNORMAL)); /* We are going to place the new block in front of edge destination. Avoid existence of fallthru predecessors. */ if ((edge_in->flags & EDGE_FALLTHRU) == 0) { edge e; + edge_iterator ei; - for (e = edge_in->dest->pred; e; e = e->pred_next) + FOR_EACH_EDGE (e, ei, edge_in->dest->preds) if (e->flags & EDGE_FALLTHRU) break; @@ -1260,20 +1350,35 @@ split_edge (edge_in) we confuse the loop optimizer into thinking the loop is a phony. */ if (edge_in->dest != EXIT_BLOCK_PTR - && PREV_INSN (edge_in->dest->head) - && GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE - && (NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head)) + && PREV_INSN (BB_HEAD (edge_in->dest)) + && NOTE_P (PREV_INSN (BB_HEAD (edge_in->dest))) + && (NOTE_LINE_NUMBER (PREV_INSN (BB_HEAD (edge_in->dest))) == NOTE_INSN_LOOP_BEG) && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src)) - before = PREV_INSN (edge_in->dest->head); + before = PREV_INSN (BB_HEAD (edge_in->dest)); else if (edge_in->dest != EXIT_BLOCK_PTR) - before = edge_in->dest->head; + before = BB_HEAD (edge_in->dest); else before = NULL_RTX; - bb = create_basic_block (before, NULL, edge_in->dest->prev_bb); - bb->count = edge_in->count; - bb->frequency = EDGE_FREQUENCY (edge_in); + /* If this is a fall through edge to the exit block, the blocks might be + not adjacent, and the right place is the after the source. */ + if (edge_in->flags & EDGE_FALLTHRU && edge_in->dest == EXIT_BLOCK_PTR) + { + before = NEXT_INSN (BB_END (edge_in->src)); + if (before + && NOTE_P (before) + && NOTE_LINE_NUMBER (before) == NOTE_INSN_LOOP_END) + before = NEXT_INSN (before); + bb = create_basic_block (before, NULL, edge_in->src); + BB_COPY_PARTITION (bb, edge_in->src); + } + else + { + bb = create_basic_block (before, NULL, edge_in->dest->prev_bb); + /* ??? Why not edge_in->dest->prev_bb here? */ + BB_COPY_PARTITION (bb, edge_in->dest); + } /* ??? This info is likely going to be out of date very soon. */ if (edge_in->dest->global_live_at_start) @@ -1288,12 +1393,12 @@ split_edge (edge_in) make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU); - /* For non-fallthry edges, we must adjust the predecessor's + /* For non-fallthru edges, we must adjust the predecessor's jump instruction to target our new block. */ if ((edge_in->flags & EDGE_FALLTHRU) == 0) { - if (!redirect_edge_and_branch (edge_in, bb)) - abort (); + edge redirected = redirect_edge_and_branch (edge_in, bb); + gcc_assert (redirected); } else redirect_edge_succ (edge_in, bb); @@ -1306,49 +1411,141 @@ split_edge (edge_in) CFG until commit_edge_insertions is called. */ void -insert_insn_on_edge (pattern, e) - rtx pattern; - edge e; +insert_insn_on_edge (rtx pattern, edge e) { /* We cannot insert instructions on an abnormal critical edge. It will be easier to find the culprit if we die now. */ - if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)) - abort (); + gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))); - if (e->insns == NULL_RTX) + if (e->insns.r == NULL_RTX) start_sequence (); else - push_to_sequence (e->insns); + push_to_sequence (e->insns.r); emit_insn (pattern); - e->insns = get_insns (); + e->insns.r = get_insns (); end_sequence (); } +/* Called from safe_insert_insn_on_edge through note_stores, marks live + registers that are killed by the store. */ +static void +mark_killed_regs (rtx reg, rtx set ATTRIBUTE_UNUSED, void *data) +{ + regset killed = data; + int regno, i; + + if (GET_CODE (reg) == SUBREG) + reg = SUBREG_REG (reg); + if (!REG_P (reg)) + return; + regno = REGNO (reg); + if (regno >= FIRST_PSEUDO_REGISTER) + SET_REGNO_REG_SET (killed, regno); + else + { + for (i = 0; i < (int) hard_regno_nregs[regno][GET_MODE (reg)]; i++) + SET_REGNO_REG_SET (killed, regno + i); + } +} + +/* Similar to insert_insn_on_edge, tries to put INSN to edge E. Additionally + it checks whether this will not clobber the registers that are live on the + edge (i.e. it requires liveness information to be up-to-date) and if there + are some, then it tries to save and restore them. Returns true if + successful. */ +bool +safe_insert_insn_on_edge (rtx insn, edge e) +{ + rtx x; + regset_head killed_head; + regset killed = INITIALIZE_REG_SET (killed_head); + rtx save_regs = NULL_RTX; + unsigned regno; + int noccmode; + enum machine_mode mode; + reg_set_iterator rsi; + +#ifdef AVOID_CCMODE_COPIES + noccmode = true; +#else + noccmode = false; +#endif + + for (x = insn; x; x = NEXT_INSN (x)) + if (INSN_P (x)) + note_stores (PATTERN (x), mark_killed_regs, killed); + bitmap_and_into (killed, e->dest->global_live_at_start); + + EXECUTE_IF_SET_IN_REG_SET (killed, 0, regno, rsi) + { + mode = regno < FIRST_PSEUDO_REGISTER + ? reg_raw_mode[regno] + : GET_MODE (regno_reg_rtx[regno]); + if (mode == VOIDmode) + return false; + + if (noccmode && mode == CCmode) + return false; + + save_regs = alloc_EXPR_LIST (0, + alloc_EXPR_LIST (0, + gen_reg_rtx (mode), + gen_raw_REG (mode, regno)), + save_regs); + } + + if (save_regs) + { + rtx from, to; + + start_sequence (); + for (x = save_regs; x; x = XEXP (x, 1)) + { + from = XEXP (XEXP (x, 0), 1); + to = XEXP (XEXP (x, 0), 0); + emit_move_insn (to, from); + } + emit_insn (insn); + for (x = save_regs; x; x = XEXP (x, 1)) + { + from = XEXP (XEXP (x, 0), 0); + to = XEXP (XEXP (x, 0), 1); + emit_move_insn (to, from); + } + insn = get_insns (); + end_sequence (); + free_EXPR_LIST_list (&save_regs); + } + insert_insn_on_edge (insn, e); + + FREE_REG_SET (killed); + return true; +} + /* Update the CFG for the instructions queued on edge E. */ static void -commit_one_edge_insertion (e, watch_calls) - edge e; - int watch_calls; +commit_one_edge_insertion (edge e, int watch_calls) { rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last; basic_block bb = NULL; /* Pull the insns off the edge now since the edge might go away. */ - insns = e->insns; - e->insns = NULL_RTX; + insns = e->insns.r; + e->insns.r = NULL_RTX; /* Special case -- avoid inserting code between call and storing its return value. */ - if (watch_calls && (e->flags & EDGE_FALLTHRU) && !e->dest->pred->pred_next + if (watch_calls && (e->flags & EDGE_FALLTHRU) + && EDGE_COUNT (e->dest->preds) == 1 && e->src != ENTRY_BLOCK_PTR - && GET_CODE (e->src->end) == CALL_INSN) + && CALL_P (BB_END (e->src))) { - rtx next = next_nonnote_insn (e->src->end); + rtx next = next_nonnote_insn (BB_END (e->src)); - after = e->dest->head; + after = BB_HEAD (e->dest); /* The first insn after the call may be a stack pop, skip it. */ while (next && keep_with_call_p (next)) @@ -1362,18 +1559,22 @@ commit_one_edge_insertion (e, watch_calls) { /* Figure out where to put these things. If the destination has one predecessor, insert there. Except for the exit block. */ - if (e->dest->pred->pred_next == NULL && e->dest != EXIT_BLOCK_PTR) + if (EDGE_COUNT (e->dest->preds) == 1 && e->dest != EXIT_BLOCK_PTR) { bb = e->dest; /* Get the location correct wrt a code label, and "nice" wrt a basic block note, and before everything else. */ - tmp = bb->head; - if (GET_CODE (tmp) == CODE_LABEL) + tmp = BB_HEAD (bb); + if (LABEL_P (tmp)) tmp = NEXT_INSN (tmp); if (NOTE_INSN_BASIC_BLOCK_P (tmp)) tmp = NEXT_INSN (tmp); - if (tmp == bb->head) + if (tmp + && NOTE_P (tmp) + && NOTE_LINE_NUMBER (tmp) == NOTE_INSN_UNLIKELY_EXECUTED_CODE) + tmp = NEXT_INSN (tmp); + if (tmp == BB_HEAD (bb)) before = tmp; else if (tmp) after = PREV_INSN (tmp); @@ -1384,7 +1585,7 @@ commit_one_edge_insertion (e, watch_calls) /* If the source has one successor and the edge is not abnormal, insert there. Except for the entry block. */ else if ((e->flags & EDGE_ABNORMAL) == 0 - && e->src->succ->succ_next == NULL + && EDGE_COUNT (e->src->succs) == 1 && e->src != ENTRY_BLOCK_PTR) { bb = e->src; @@ -1395,26 +1596,56 @@ commit_one_edge_insertion (e, watch_calls) We know this block has a single successor, so we can just emit the queued insns before the jump. */ - if (GET_CODE (bb->end) == JUMP_INSN) - for (before = bb->end; - GET_CODE (PREV_INSN (before)) == NOTE + if (JUMP_P (BB_END (bb))) + for (before = BB_END (bb); + NOTE_P (PREV_INSN (before)) && NOTE_LINE_NUMBER (PREV_INSN (before)) == NOTE_INSN_LOOP_BEG; before = PREV_INSN (before)) ; else { - /* We'd better be fallthru, or we've lost track of what's what. */ - if ((e->flags & EDGE_FALLTHRU) == 0) - abort (); + /* We'd better be fallthru, or we've lost track of + what's what. */ + gcc_assert (e->flags & EDGE_FALLTHRU); - after = bb->end; + after = BB_END (bb); } } /* Otherwise we must split the edge. */ else { bb = split_edge (e); - after = bb->end; + after = BB_END (bb); + + if (flag_reorder_blocks_and_partition + && targetm.have_named_sections + && e->src != ENTRY_BLOCK_PTR + && BB_PARTITION (e->src) == BB_COLD_PARTITION + && !(e->flags & EDGE_CROSSING)) + { + rtx bb_note, new_note, cur_insn; + + bb_note = NULL_RTX; + for (cur_insn = BB_HEAD (bb); cur_insn != NEXT_INSN (BB_END (bb)); + cur_insn = NEXT_INSN (cur_insn)) + if (NOTE_P (cur_insn) + && NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_BASIC_BLOCK) + { + bb_note = cur_insn; + break; + } + + new_note = emit_note_after (NOTE_INSN_UNLIKELY_EXECUTED_CODE, + bb_note); + NOTE_BASIC_BLOCK (new_note) = bb; + if (JUMP_P (BB_END (bb)) + && !any_condjump_p (BB_END (bb)) + && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING)) + REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST + (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb))); + if (after == bb_note) + after = new_note; + } } } @@ -1422,11 +1653,11 @@ commit_one_edge_insertion (e, watch_calls) if (before) { - emit_insn_before (insns, before); + emit_insn_before_noloc (insns, before); last = prev_nonnote_insn (before); } else - last = emit_insn_after (insns, after); + last = emit_insn_after_noloc (insns, after); if (returnjump_p (last)) { @@ -1435,10 +1666,9 @@ commit_one_edge_insertion (e, watch_calls) for the (single) epilogue, which already has a fallthru edge to EXIT. */ - e = bb->succ; - if (e->dest != EXIT_BLOCK_PTR - || e->succ_next != NULL || (e->flags & EDGE_FALLTHRU) == 0) - abort (); + e = EDGE_SUCC (bb, 0); + gcc_assert (e->dest == EXIT_BLOCK_PTR + && EDGE_COUNT (bb->succs) == 1 && (e->flags & EDGE_FALLTHRU)); e->flags &= ~EDGE_FALLTHRU; emit_barrier_after (last); @@ -1446,18 +1676,21 @@ commit_one_edge_insertion (e, watch_calls) if (before) delete_insn (before); } - else if (GET_CODE (last) == JUMP_INSN) - abort (); + else + gcc_assert (!JUMP_P (last)); - find_sub_basic_blocks (bb); + /* Mark the basic block for find_sub_basic_blocks. */ + bb->aux = &bb->aux; } /* Update the CFG for all queued instructions. */ void -commit_edge_insertions () +commit_edge_insertions (void) { basic_block bb; + sbitmap blocks; + bool changed = false; #ifdef ENABLE_CHECKING verify_flow_info (); @@ -1465,24 +1698,44 @@ commit_edge_insertions () FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) { - edge e, next; + edge e; + edge_iterator ei; - for (e = bb->succ; e; e = next) - { - next = e->succ_next; - if (e->insns) + FOR_EACH_EDGE (e, ei, bb->succs) + if (e->insns.r) + { + changed = true; commit_one_edge_insertion (e, false); - } + } } + + if (!changed) + return; + + blocks = sbitmap_alloc (last_basic_block); + sbitmap_zero (blocks); + FOR_EACH_BB (bb) + if (bb->aux) + { + SET_BIT (blocks, bb->index); + /* Check for forgotten bb->aux values before commit_edge_insertions + call. */ + gcc_assert (bb->aux == &bb->aux); + bb->aux = NULL; + } + find_many_sub_basic_blocks (blocks); + sbitmap_free (blocks); } /* Update the CFG for all queued instructions, taking special care of inserting code on edges between call and storing its return value. */ void -commit_edge_insertions_watch_calls () +commit_edge_insertions_watch_calls (void) { basic_block bb; + sbitmap blocks; + bool changed = false; #ifdef ENABLE_CHECKING verify_flow_info (); @@ -1490,77 +1743,67 @@ commit_edge_insertions_watch_calls () FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) { - edge e, next; + edge e; + edge_iterator ei; - for (e = bb->succ; e; e = next) - { - next = e->succ_next; - if (e->insns) + FOR_EACH_EDGE (e, ei, bb->succs) + if (e->insns.r) + { + changed = true; commit_one_edge_insertion (e, true); - } + } } + + if (!changed) + return; + + blocks = sbitmap_alloc (last_basic_block); + sbitmap_zero (blocks); + FOR_EACH_BB (bb) + if (bb->aux) + { + SET_BIT (blocks, bb->index); + /* Check for forgotten bb->aux values before commit_edge_insertions + call. */ + gcc_assert (bb->aux == &bb->aux); + bb->aux = NULL; + } + find_many_sub_basic_blocks (blocks); + sbitmap_free (blocks); } -/* Print out one basic block with live information at start and end. */ +/* Print out RTL-specific basic block information (live information + at start and end). */ -void -dump_bb (bb, outf) - basic_block bb; - FILE *outf; +static void +rtl_dump_bb (basic_block bb, FILE *outf, int indent) { rtx insn; rtx last; - edge e; + char *s_indent; - fprintf (outf, ";; Basic block %d, loop depth %d, count ", - bb->index, bb->loop_depth); - fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count); - putc ('\n', outf); - - fputs (";; Predecessors: ", outf); - for (e = bb->pred; e; e = e->pred_next) - dump_edge_info (outf, e, 0); - putc ('\n', outf); + s_indent = alloca ((size_t) indent + 1); + memset (s_indent, ' ', (size_t) indent); + s_indent[indent] = '\0'; - fputs (";; Registers live at start:", outf); + fprintf (outf, ";;%s Registers live at start: ", s_indent); dump_regset (bb->global_live_at_start, outf); putc ('\n', outf); - for (insn = bb->head, last = NEXT_INSN (bb->end); insn != last; + for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last; insn = NEXT_INSN (insn)) print_rtl_single (outf, insn); - fputs (";; Registers live at end:", outf); + fprintf (outf, ";;%s Registers live at end: ", s_indent); dump_regset (bb->global_live_at_end, outf); putc ('\n', outf); - - fputs (";; Successors: ", outf); - for (e = bb->succ; e; e = e->succ_next) - dump_edge_info (outf, e, 1); - putc ('\n', outf); -} - -void -debug_bb (bb) - basic_block bb; -{ - dump_bb (bb, stderr); -} - -void -debug_bb_n (n) - int n; -{ - dump_bb (BASIC_BLOCK (n), stderr); } /* Like print_rtl, but also print out live information for the start of each basic block. */ void -print_rtl_with_bb (outf, rtx_first) - FILE *outf; - rtx rtx_first; +print_rtl_with_bb (FILE *outf, rtx rtx_first) { rtx tmp_rtx; @@ -1570,12 +1813,9 @@ print_rtl_with_bb (outf, rtx_first) { enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB }; int max_uid = get_max_uid (); - basic_block *start - = (basic_block *) xcalloc (max_uid, sizeof (basic_block)); - basic_block *end - = (basic_block *) xcalloc (max_uid, sizeof (basic_block)); - enum bb_state *in_bb_p - = (enum bb_state *) xcalloc (max_uid, sizeof (enum bb_state)); + basic_block *start = xcalloc (max_uid, sizeof (basic_block)); + basic_block *end = xcalloc (max_uid, sizeof (basic_block)); + enum bb_state *in_bb_p = xcalloc (max_uid, sizeof (enum bb_state)); basic_block bb; @@ -1583,9 +1823,9 @@ print_rtl_with_bb (outf, rtx_first) { rtx x; - start[INSN_UID (bb->head)] = bb; - end[INSN_UID (bb->end)] = bb; - for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x)) + start[INSN_UID (BB_HEAD (bb))] = bb; + end[INSN_UID (BB_END (bb))] = bb; + for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x)) { enum bb_state state = IN_MULTIPLE_BB; @@ -1593,7 +1833,7 @@ print_rtl_with_bb (outf, rtx_first) state = IN_ONE_BB; in_bb_p[INSN_UID (x)] = state; - if (x == bb->end) + if (x == BB_END (bb)) break; } } @@ -1611,8 +1851,8 @@ print_rtl_with_bb (outf, rtx_first) } if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB - && GET_CODE (tmp_rtx) != NOTE - && GET_CODE (tmp_rtx) != BARRIER) + && !NOTE_P (tmp_rtx) + && !BARRIER_P (tmp_rtx)) fprintf (outf, ";; Insn is not within a basic block\n"); else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB) fprintf (outf, ";; Insn is in multiple basic blocks\n"); @@ -1646,80 +1886,52 @@ print_rtl_with_bb (outf, rtx_first) } void -update_br_prob_note (bb) - basic_block bb; +update_br_prob_note (basic_block bb) { rtx note; - if (GET_CODE (bb->end) != JUMP_INSN) + if (!JUMP_P (BB_END (bb))) return; - note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX); + note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX); if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability) return; XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability); } -/* Verify the CFG consistency. This function check some CFG invariants and - aborts when something is wrong. Hope that this function will help to - convert many optimization passes to preserve CFG consistent. +/* Verify the CFG and RTL consistency common for both underlying RTL and + cfglayout RTL. Currently it does following checks: - test head/end pointers - overlapping of basic blocks - - edge list correctness - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note) - tails of basic blocks (ensure that boundary is necessary) - scans body of the basic block for JUMP_INSN, CODE_LABEL and NOTE_INSN_BASIC_BLOCK - - check that all insns are in the basic blocks - (except the switch handling code, barriers and notes) - - check that all returns are followed by barriers + - verify that no fall_thru edge crosses hot/cold partition boundaries In future it can be extended check a lot of other stuff as well (reachability of basic blocks, life information, etc. etc.). */ -void -verify_flow_info () +static int +rtl_verify_flow_info_1 (void) { const int max_uid = get_max_uid (); - const rtx rtx_first = get_insns (); rtx last_head = get_last_insn (); - basic_block *bb_info, *last_visited; - size_t *edge_checksum; + basic_block *bb_info; rtx x; - int num_bb_notes, err = 0; + int err = 0; basic_block bb, last_bb_seen; - bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block)); - last_visited = (basic_block *) xcalloc (last_basic_block + 2, - sizeof (basic_block)); - edge_checksum = (size_t *) xcalloc (last_basic_block + 2, sizeof (size_t)); + bb_info = xcalloc (max_uid, sizeof (basic_block)); /* Check bb chain & numbers. */ last_bb_seen = ENTRY_BLOCK_PTR; - FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) - { - if (bb != EXIT_BLOCK_PTR - && bb != BASIC_BLOCK (bb->index)) - { - error ("bb %d on wrong place", bb->index); - err = 1; - } - - if (bb->prev_bb != last_bb_seen) - { - error ("prev_bb of %d should be %d, not %d", - bb->index, last_bb_seen->index, bb->prev_bb->index); - err = 1; - } - - last_bb_seen = bb; - } FOR_EACH_BB_REVERSE (bb) { - rtx head = bb->head; - rtx end = bb->end; + rtx head = BB_HEAD (bb); + rtx end = BB_END (bb); /* Verify the end of the basic block is in the INSN chain. */ for (x = last_head; x != NULL_RTX; x = PREV_INSN (x)) @@ -1766,60 +1978,44 @@ verify_flow_info () FOR_EACH_BB_REVERSE (bb) { int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0; - edge e; + edge e, fallthru = NULL; rtx note; + edge_iterator ei; - if (INSN_P (bb->end) - && (note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX)) - && bb->succ && bb->succ->succ_next - && any_condjump_p (bb->end)) + if (INSN_P (BB_END (bb)) + && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX)) + && EDGE_COUNT (bb->succs) >= 2 + && any_condjump_p (BB_END (bb))) { - if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability) + if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability + && profile_status != PROFILE_ABSENT) { - error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i", + error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i", INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability); err = 1; } } - if (bb->count < 0) - { - error ("verify_flow_info: Wrong count of block %i %i", - bb->index, (int)bb->count); - err = 1; - } - if (bb->frequency < 0) + FOR_EACH_EDGE (e, ei, bb->succs) { - error ("verify_flow_info: Wrong frequency of block %i %i", - bb->index, bb->frequency); - err = 1; - } - for (e = bb->succ; e; e = e->succ_next) - { - if (last_visited [e->dest->index + 2] == bb) - { - error ("verify_flow_info: Duplicate edge %i->%i", - e->src->index, e->dest->index); - err = 1; - } - if (e->probability < 0 || e->probability > REG_BR_PROB_BASE) - { - error ("verify_flow_info: Wrong probability of edge %i->%i %i", - e->src->index, e->dest->index, e->probability); - err = 1; - } - if (e->count < 0) + if (e->flags & EDGE_FALLTHRU) { - error ("verify_flow_info: Wrong count of edge %i->%i %i", - e->src->index, e->dest->index, (int)e->count); - err = 1; + n_fallthru++, fallthru = e; + if ((e->flags & EDGE_CROSSING) + || (BB_PARTITION (e->src) != BB_PARTITION (e->dest) + && e->src != ENTRY_BLOCK_PTR + && e->dest != EXIT_BLOCK_PTR)) + { + error ("Fallthru edge crosses section boundary (bb %i)", + e->src->index); + err = 1; + } } - last_visited [e->dest->index + 2] = bb; - - if (e->flags & EDGE_FALLTHRU) - n_fallthru++; - - if ((e->flags & ~(EDGE_DFS_BACK | EDGE_CAN_FALLTHRU)) == 0) + if ((e->flags & ~(EDGE_DFS_BACK + | EDGE_CAN_FALLTHRU + | EDGE_IRREDUCIBLE_LOOP + | EDGE_LOOP_EXIT + | EDGE_CROSSING)) == 0) n_branch++; if (e->flags & EDGE_ABNORMAL_CALL) @@ -1829,132 +2025,57 @@ verify_flow_info () n_eh++; else if (e->flags & EDGE_ABNORMAL) n_abnormal++; - - if ((e->flags & EDGE_FALLTHRU) - && e->src != ENTRY_BLOCK_PTR - && e->dest != EXIT_BLOCK_PTR) - { - rtx insn; - - if (e->src->next_bb != e->dest) - { - error - ("verify_flow_info: Incorrect blocks for fallthru %i->%i", - e->src->index, e->dest->index); - err = 1; - } - else - for (insn = NEXT_INSN (e->src->end); insn != e->dest->head; - insn = NEXT_INSN (insn)) - if (GET_CODE (insn) == BARRIER -#ifndef CASE_DROPS_THROUGH - || INSN_P (insn) -#else - || (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn)) -#endif - ) - { - error ("verify_flow_info: Incorrect fallthru %i->%i", - e->src->index, e->dest->index); - fatal_insn ("wrong insn in the fallthru edge", insn); - err = 1; - } - } - - if (e->src != bb) - { - error ("verify_flow_info: Basic block %d succ edge is corrupted", - bb->index); - fprintf (stderr, "Predecessor: "); - dump_edge_info (stderr, e, 0); - fprintf (stderr, "\nSuccessor: "); - dump_edge_info (stderr, e, 1); - fprintf (stderr, "\n"); - err = 1; - } - - edge_checksum[e->dest->index + 2] += (size_t) e; } - if (n_eh && GET_CODE (PATTERN (bb->end)) != RESX - && !find_reg_note (bb->end, REG_EH_REGION, NULL_RTX)) + if (n_eh && GET_CODE (PATTERN (BB_END (bb))) != RESX + && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX)) { error ("Missing REG_EH_REGION note in the end of bb %i", bb->index); err = 1; } if (n_branch - && (GET_CODE (bb->end) != JUMP_INSN - || (n_branch > 1 && (any_uncondjump_p (bb->end) - || any_condjump_p (bb->end))))) + && (!JUMP_P (BB_END (bb)) + || (n_branch > 1 && (any_uncondjump_p (BB_END (bb)) + || any_condjump_p (BB_END (bb)))))) { error ("Too many outgoing branch edges from bb %i", bb->index); err = 1; } - if (n_fallthru && any_uncondjump_p (bb->end)) + if (n_fallthru && any_uncondjump_p (BB_END (bb))) { error ("Fallthru edge after unconditional jump %i", bb->index); err = 1; } - if (n_branch != 1 && any_uncondjump_p (bb->end)) + if (n_branch != 1 && any_uncondjump_p (BB_END (bb))) { error ("Wrong amount of branch edges after unconditional jump %i", bb->index); err = 1; } - if (n_branch != 1 && any_condjump_p (bb->end) - && JUMP_LABEL (bb->end) != bb->next_bb->head) + if (n_branch != 1 && any_condjump_p (BB_END (bb)) + && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest)) { error ("Wrong amount of branch edges after conditional jump %i", bb->index); err = 1; } - if (n_call && GET_CODE (bb->end) != CALL_INSN) + if (n_call && !CALL_P (BB_END (bb))) { error ("Call edges for non-call insn in bb %i", bb->index); err = 1; } if (n_abnormal - && (GET_CODE (bb->end) != CALL_INSN && n_call != n_abnormal) - && (GET_CODE (bb->end) != JUMP_INSN - || any_condjump_p (bb->end) - || any_uncondjump_p (bb->end))) + && (!CALL_P (BB_END (bb)) && n_call != n_abnormal) + && (!JUMP_P (BB_END (bb)) + || any_condjump_p (BB_END (bb)) + || any_uncondjump_p (BB_END (bb)))) { error ("Abnormal edges for no purpose in bb %i", bb->index); err = 1; } - if (!n_fallthru) - { - rtx insn; - - /* Ensure existence of barrier in BB with no fallthru edges. */ - for (insn = bb->end; !insn || GET_CODE (insn) != BARRIER; - insn = NEXT_INSN (insn)) - if (!insn - || (GET_CODE (insn) == NOTE - && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK)) - { - error ("missing barrier after block %i", bb->index); - err = 1; - break; - } - } - - for (e = bb->pred; e; e = e->pred_next) - { - if (e->dest != bb) - { - error ("basic block %d pred edge is corrupted", bb->index); - fputs ("Predecessor: ", stderr); - dump_edge_info (stderr, e, 0); - fputs ("\nSuccessor: ", stderr); - dump_edge_info (stderr, e, 1); - fputc ('\n', stderr); - err = 1; - } - edge_checksum[e->dest->index + 2] -= (size_t) e; - } - - for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x)) - if (BLOCK_FOR_INSN (x) != bb) + for (x = BB_HEAD (bb); x != NEXT_INSN (BB_END (bb)); x = NEXT_INSN (x)) + /* We may have a barrier inside a basic block before dead code + elimination. There is no BLOCK_FOR_INSN field in a barrier. */ + if (!BARRIER_P (x) && BLOCK_FOR_INSN (x) != bb) { debug_rtx (x); if (! BLOCK_FOR_INSN (x)) @@ -1972,10 +2093,10 @@ verify_flow_info () /* OK pointers are correct. Now check the header of basic block. It ought to contain optional CODE_LABEL followed by NOTE_BASIC_BLOCK. */ - x = bb->head; - if (GET_CODE (x) == CODE_LABEL) + x = BB_HEAD (bb); + if (LABEL_P (x)) { - if (bb->end == x) + if (BB_END (bb) == x) { error ("NOTE_INSN_BASIC_BLOCK is missing for block %d", bb->index); @@ -1992,7 +2113,7 @@ verify_flow_info () err = 1; } - if (bb->end == x) + if (BB_END (bb) == x) /* Do checks for empty blocks her. e */ ; else @@ -2005,7 +2126,7 @@ verify_flow_info () err = 1; } - if (x == bb->end) + if (x == BB_END (bb)) break; if (control_flow_insn_p (x)) @@ -2016,23 +2137,84 @@ verify_flow_info () } } - /* Complete edge checksumming for ENTRY and EXIT. */ - { - edge e; + /* Clean up. */ + free (bb_info); + return err; +} - for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next) - edge_checksum[e->dest->index + 2] += (size_t) e; +/* Verify the CFG and RTL consistency common for both underlying RTL and + cfglayout RTL. - for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next) - edge_checksum[e->dest->index + 2] -= (size_t) e; - } + Currently it does following checks: + - all checks of rtl_verify_flow_info_1 + - check that all insns are in the basic blocks + (except the switch handling code, barriers and notes) + - check that all returns are followed by barriers + - check that all fallthru edge points to the adjacent blocks. */ +static int +rtl_verify_flow_info (void) +{ + basic_block bb; + int err = rtl_verify_flow_info_1 (); + rtx x; + int num_bb_notes; + const rtx rtx_first = get_insns (); + basic_block last_bb_seen = ENTRY_BLOCK_PTR, curr_bb = NULL; - FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) - if (edge_checksum[bb->index + 2]) - { - error ("basic block %i edge lists are corrupted", bb->index); - err = 1; - } + FOR_EACH_BB_REVERSE (bb) + { + edge e; + edge_iterator ei; + + FOR_EACH_EDGE (e, ei, bb->succs) + if (e->flags & EDGE_FALLTHRU) + break; + if (!e) + { + rtx insn; + + /* Ensure existence of barrier in BB with no fallthru edges. */ + for (insn = BB_END (bb); !insn || !BARRIER_P (insn); + insn = NEXT_INSN (insn)) + if (!insn + || (NOTE_P (insn) + && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK)) + { + error ("missing barrier after block %i", bb->index); + err = 1; + break; + } + } + else if (e->src != ENTRY_BLOCK_PTR + && e->dest != EXIT_BLOCK_PTR) + { + rtx insn; + + if (e->src->next_bb != e->dest) + { + error + ("verify_flow_info: Incorrect blocks for fallthru %i->%i", + e->src->index, e->dest->index); + err = 1; + } + else + for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest); + insn = NEXT_INSN (insn)) + if (BARRIER_P (insn) +#ifndef CASE_DROPS_THROUGH + || INSN_P (insn) +#else + || (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn)) +#endif + ) + { + error ("verify_flow_info: Incorrect fallthru %i->%i", + e->src->index, e->dest->index); + fatal_insn ("wrong insn in the fallthru edge", insn); + err = 1; + } + } + } num_bb_notes = 0; last_bb_seen = ENTRY_BLOCK_PTR; @@ -2045,12 +2227,12 @@ verify_flow_info () num_bb_notes++; if (bb != last_bb_seen->next_bb) - internal_error ("basic blocks not numbered consecutively"); + internal_error ("basic blocks not laid down consecutively"); - last_bb_seen = bb; + curr_bb = last_bb_seen = bb; } - if (!bb_info[INSN_UID (x)]) + if (!curr_bb) { switch (GET_CODE (x)) { @@ -2059,9 +2241,9 @@ verify_flow_info () break; case CODE_LABEL: - /* An addr_vec is placed outside any block block. */ + /* An addr_vec is placed outside any basic block. */ if (NEXT_INSN (x) - && GET_CODE (NEXT_INSN (x)) == JUMP_INSN + && JUMP_P (NEXT_INSN (x)) && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC)) x = NEXT_INSN (x); @@ -2075,10 +2257,12 @@ verify_flow_info () } if (INSN_P (x) - && GET_CODE (x) == JUMP_INSN + && JUMP_P (x) && returnjump_p (x) && ! condjump_p (x) - && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER)) + && ! (NEXT_INSN (x) && BARRIER_P (NEXT_INSN (x)))) fatal_insn ("return not followed by barrier", x); + if (curr_bb && x == BB_END (curr_bb)) + curr_bb = NULL; } if (num_bb_notes != n_basic_blocks) @@ -2086,13 +2270,7 @@ verify_flow_info () ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)", num_bb_notes, n_basic_blocks); - if (err) - internal_error ("verify_flow_info failed"); - - /* Clean up. */ - free (bb_info); - free (last_visited); - free (edge_checksum); + return err; } /* Assume that the preceding pass has possibly eliminated jump instructions @@ -2100,15 +2278,16 @@ verify_flow_info () Return true if any edges are eliminated. */ bool -purge_dead_edges (bb) - basic_block bb; +purge_dead_edges (basic_block bb) { - edge e, next; - rtx insn = bb->end, note; + edge e; + rtx insn = BB_END (bb), note; bool purged = false; + bool found; + edge_iterator ei; /* If this instruction cannot trap, remove REG_EH_REGION notes. */ - if (GET_CODE (insn) == INSN + if (NONJUMP_INSN_P (insn) && (note = find_reg_note (insn, REG_EH_REGION, NULL))) { rtx eqnote; @@ -2120,33 +2299,42 @@ purge_dead_edges (bb) } /* Cleanup abnormal edges caused by exceptions or non-local gotos. */ - for (e = bb->succ; e; e = next) + for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) { - next = e->succ_next; if (e->flags & EDGE_EH) { - if (can_throw_internal (bb->end)) - continue; + if (can_throw_internal (BB_END (bb))) + { + ei_next (&ei); + continue; + } } else if (e->flags & EDGE_ABNORMAL_CALL) { - if (GET_CODE (bb->end) == CALL_INSN + if (CALL_P (BB_END (bb)) && (! (note = find_reg_note (insn, REG_EH_REGION, NULL)) || INTVAL (XEXP (note, 0)) >= 0)) - continue; + { + ei_next (&ei); + continue; + } } else - continue; + { + ei_next (&ei); + continue; + } remove_edge (e); bb->flags |= BB_DIRTY; purged = true; } - if (GET_CODE (insn) == JUMP_INSN) + if (JUMP_P (insn)) { rtx note; edge b,f; + edge_iterator ei; /* We do care only about conditional jumps and simplejumps. */ if (!any_condjump_p (insn) @@ -2165,10 +2353,8 @@ purge_dead_edges (bb) remove_note (insn, note); } - for (e = bb->succ; e; e = next) + for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) { - next = e->succ_next; - /* Avoid abnormal flags to leak from computed jumps turned into simplejumps. */ @@ -2178,20 +2364,34 @@ purge_dead_edges (bb) if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn)) /* A conditional jump can fall through into the next block, so we should keep the edge. */ - continue; + { + ei_next (&ei); + continue; + } else if (e->dest != EXIT_BLOCK_PTR - && e->dest->head == JUMP_LABEL (insn)) + && BB_HEAD (e->dest) == JUMP_LABEL (insn)) /* If the destination block is the target of the jump, keep the edge. */ - continue; + { + ei_next (&ei); + continue; + } else if (e->dest == EXIT_BLOCK_PTR && returnjump_p (insn)) /* If the destination block is the exit block, and this instruction is a return, then keep the edge. */ - continue; + { + ei_next (&ei); + continue; + } else if ((e->flags & EDGE_EH) && can_throw_internal (insn)) /* Keep the edges that correspond to exceptions thrown by - this instruction. */ - continue; + this instruction and rematerialize the EDGE_ABNORMAL + flag we just cleared above. */ + { + e->flags |= EDGE_ABNORMAL; + ei_next (&ei); + continue; + } /* We do not need this edge. */ bb->flags |= BB_DIRTY; @@ -2199,20 +2399,20 @@ purge_dead_edges (bb) remove_edge (e); } - if (!bb->succ || !purged) + if (EDGE_COUNT (bb->succs) == 0 || !purged) return purged; - if (rtl_dump_file) - fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index); + if (dump_file) + fprintf (dump_file, "Purged edges from bb %i\n", bb->index); if (!optimize) return purged; /* Redistribute probabilities. */ - if (!bb->succ->succ_next) + if (EDGE_COUNT (bb->succs) == 1) { - bb->succ->probability = REG_BR_PROB_BASE; - bb->succ->count = bb->count; + EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE; + EDGE_SUCC (bb, 0)->count = bb->count; } else { @@ -2230,38 +2430,53 @@ purge_dead_edges (bb) return purged; } + else if (CALL_P (insn) && SIBLING_CALL_P (insn)) + { + /* First, there should not be any EH or ABCALL edges resulting + from non-local gotos and the like. If there were, we shouldn't + have created the sibcall in the first place. Second, there + should of course never have been a fallthru edge. */ + gcc_assert (EDGE_COUNT (bb->succs) == 1); + gcc_assert (EDGE_SUCC (bb, 0)->flags == (EDGE_SIBCALL | EDGE_ABNORMAL)); + + return 0; + } /* If we don't see a jump insn, we don't know exactly why the block would have been broken at this point. Look for a simple, non-fallthru edge, as these are only created by conditional branches. If we find such an edge we know that there used to be a jump here and can then safely remove all non-fallthru edges. */ - for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)); - e = e->succ_next) - ; + found = false; + FOR_EACH_EDGE (e, ei, bb->succs) + if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))) + { + found = true; + break; + } - if (!e) + if (!found) return purged; - for (e = bb->succ; e; e = next) + for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) { - next = e->succ_next; if (!(e->flags & EDGE_FALLTHRU)) { bb->flags |= BB_DIRTY; remove_edge (e); purged = true; } + else + ei_next (&ei); } - if (!bb->succ || bb->succ->succ_next) - abort (); + gcc_assert (EDGE_COUNT (bb->succs) == 1); - bb->succ->probability = REG_BR_PROB_BASE; - bb->succ->count = bb->count; + EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE; + EDGE_SUCC (bb, 0)->count = bb->count; - if (rtl_dump_file) - fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n", + if (dump_file) + fprintf (dump_file, "Purged non-fallthru edges from bb %i\n", bb->index); return purged; } @@ -2270,8 +2485,7 @@ purge_dead_edges (bb) true if some edge has been eliminated. */ bool -purge_all_dead_edges (update_life_p) - int update_life_p; +purge_all_dead_edges (int update_life_p) { int purged = false; sbitmap blocks = 0; @@ -2301,3 +2515,601 @@ purge_all_dead_edges (update_life_p) sbitmap_free (blocks); return purged; } + +/* Same as split_block but update cfg_layout structures. */ + +static basic_block +cfg_layout_split_block (basic_block bb, void *insnp) +{ + rtx insn = insnp; + basic_block new_bb = rtl_split_block (bb, insn); + + new_bb->rbi->footer = bb->rbi->footer; + bb->rbi->footer = NULL; + + return new_bb; +} + + +/* Redirect Edge to DEST. */ +static edge +cfg_layout_redirect_edge_and_branch (edge e, basic_block dest) +{ + basic_block src = e->src; + edge ret; + + if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) + return NULL; + + if (e->dest == dest) + return e; + + if (e->src != ENTRY_BLOCK_PTR + && (ret = try_redirect_by_replacing_jump (e, dest, true))) + { + src->flags |= BB_DIRTY; + return ret; + } + + if (e->src == ENTRY_BLOCK_PTR + && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX)) + { + if (dump_file) + fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n", + e->src->index, dest->index); + + e->src->flags |= BB_DIRTY; + redirect_edge_succ (e, dest); + return e; + } + + /* Redirect_edge_and_branch may decide to turn branch into fallthru edge + in the case the basic block appears to be in sequence. Avoid this + transformation. */ + + if (e->flags & EDGE_FALLTHRU) + { + /* Redirect any branch edges unified with the fallthru one. */ + if (JUMP_P (BB_END (src)) + && label_is_jump_target_p (BB_HEAD (e->dest), + BB_END (src))) + { + edge redirected; + + if (dump_file) + fprintf (dump_file, "Fallthru edge unified with branch " + "%i->%i redirected to %i\n", + e->src->index, e->dest->index, dest->index); + e->flags &= ~EDGE_FALLTHRU; + redirected = redirect_branch_edge (e, dest); + gcc_assert (redirected); + e->flags |= EDGE_FALLTHRU; + e->src->flags |= BB_DIRTY; + return e; + } + /* In case we are redirecting fallthru edge to the branch edge + of conditional jump, remove it. */ + if (EDGE_COUNT (src->succs) == 2) + { + bool found = false; + unsigned ix = 0; + edge tmp, s; + edge_iterator ei; + + FOR_EACH_EDGE (tmp, ei, src->succs) + if (e == tmp) + { + found = true; + ix = ei.index; + break; + } + + gcc_assert (found); + + if (EDGE_COUNT (src->succs) > (ix + 1)) + s = EDGE_SUCC (src, ix + 1); + else + s = EDGE_SUCC (src, 0); + + if (s->dest == dest + && any_condjump_p (BB_END (src)) + && onlyjump_p (BB_END (src))) + delete_insn (BB_END (src)); + } + ret = redirect_edge_succ_nodup (e, dest); + if (dump_file) + fprintf (dump_file, "Fallthru edge %i->%i redirected to %i\n", + e->src->index, e->dest->index, dest->index); + } + else + ret = redirect_branch_edge (e, dest); + + /* We don't want simplejumps in the insn stream during cfglayout. */ + gcc_assert (!simplejump_p (BB_END (src))); + + src->flags |= BB_DIRTY; + return ret; +} + +/* Simple wrapper as we always can redirect fallthru edges. */ +static basic_block +cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest) +{ + edge redirected = cfg_layout_redirect_edge_and_branch (e, dest); + + gcc_assert (redirected); + return NULL; +} + +/* Same as delete_basic_block but update cfg_layout structures. */ + +static void +cfg_layout_delete_block (basic_block bb) +{ + rtx insn, next, prev = PREV_INSN (BB_HEAD (bb)), *to, remaints; + + if (bb->rbi->header) + { + next = BB_HEAD (bb); + if (prev) + NEXT_INSN (prev) = bb->rbi->header; + else + set_first_insn (bb->rbi->header); + PREV_INSN (bb->rbi->header) = prev; + insn = bb->rbi->header; + while (NEXT_INSN (insn)) + insn = NEXT_INSN (insn); + NEXT_INSN (insn) = next; + PREV_INSN (next) = insn; + } + next = NEXT_INSN (BB_END (bb)); + if (bb->rbi->footer) + { + insn = bb->rbi->footer; + while (insn) + { + if (BARRIER_P (insn)) + { + if (PREV_INSN (insn)) + NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn); + else + bb->rbi->footer = NEXT_INSN (insn); + if (NEXT_INSN (insn)) + PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn); + } + if (LABEL_P (insn)) + break; + insn = NEXT_INSN (insn); + } + if (bb->rbi->footer) + { + insn = BB_END (bb); + NEXT_INSN (insn) = bb->rbi->footer; + PREV_INSN (bb->rbi->footer) = insn; + while (NEXT_INSN (insn)) + insn = NEXT_INSN (insn); + NEXT_INSN (insn) = next; + if (next) + PREV_INSN (next) = insn; + else + set_last_insn (insn); + } + } + if (bb->next_bb != EXIT_BLOCK_PTR) + to = &bb->next_bb->rbi->header; + else + to = &cfg_layout_function_footer; + rtl_delete_block (bb); + + if (prev) + prev = NEXT_INSN (prev); + else + prev = get_insns (); + if (next) + next = PREV_INSN (next); + else + next = get_last_insn (); + + if (next && NEXT_INSN (next) != prev) + { + remaints = unlink_insn_chain (prev, next); + insn = remaints; + while (NEXT_INSN (insn)) + insn = NEXT_INSN (insn); + NEXT_INSN (insn) = *to; + if (*to) + PREV_INSN (*to) = insn; + *to = remaints; + } +} + +/* Return true when blocks A and B can be safely merged. */ +static bool +cfg_layout_can_merge_blocks_p (basic_block a, basic_block b) +{ + /* If we are partitioning hot/cold basic blocks, we don't want to + mess up unconditional or indirect jumps that cross between hot + and cold sections. + + Basic block partitioning may result in some jumps that appear to + be optimizable (or blocks that appear to be mergeable), but which really + must be left untouched (they are required to make it safely across + partition boundaries). See the comments at the top of + bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ + + if (flag_reorder_blocks_and_partition + && (find_reg_note (BB_END (a), REG_CROSSING_JUMP, NULL_RTX) + || find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX) + || BB_PARTITION (a) != BB_PARTITION (b))) + return false; + + /* There must be exactly one edge in between the blocks. */ + return (EDGE_COUNT (a->succs) == 1 + && EDGE_SUCC (a, 0)->dest == b + && EDGE_COUNT (b->preds) == 1 + && a != b + /* Must be simple edge. */ + && !(EDGE_SUCC (a, 0)->flags & EDGE_COMPLEX) + && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR + /* If the jump insn has side effects, + we can't kill the edge. */ + && (!JUMP_P (BB_END (a)) + || (reload_completed + ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a))))); +} + +/* Merge block A and B, abort when it is not possible. */ +static void +cfg_layout_merge_blocks (basic_block a, basic_block b) +{ +#ifdef ENABLE_CHECKING + gcc_assert (cfg_layout_can_merge_blocks_p (a, b)); +#endif + + /* If there was a CODE_LABEL beginning B, delete it. */ + if (LABEL_P (BB_HEAD (b))) + delete_insn (BB_HEAD (b)); + + /* We should have fallthru edge in a, or we can do dummy redirection to get + it cleaned up. */ + if (JUMP_P (BB_END (a))) + try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true); + gcc_assert (!JUMP_P (BB_END (a))); + + /* Possible line number notes should appear in between. */ + if (b->rbi->header) + { + rtx first = BB_END (a), last; + + last = emit_insn_after_noloc (b->rbi->header, BB_END (a)); + delete_insn_chain (NEXT_INSN (first), last); + b->rbi->header = NULL; + } + + /* In the case basic blocks are not adjacent, move them around. */ + if (NEXT_INSN (BB_END (a)) != BB_HEAD (b)) + { + rtx first = unlink_insn_chain (BB_HEAD (b), BB_END (b)); + + emit_insn_after_noloc (first, BB_END (a)); + /* Skip possible DELETED_LABEL insn. */ + if (!NOTE_INSN_BASIC_BLOCK_P (first)) + first = NEXT_INSN (first); + gcc_assert (NOTE_INSN_BASIC_BLOCK_P (first)); + BB_HEAD (b) = NULL; + delete_insn (first); + } + /* Otherwise just re-associate the instructions. */ + else + { + rtx insn; + + for (insn = BB_HEAD (b); + insn != NEXT_INSN (BB_END (b)); + insn = NEXT_INSN (insn)) + set_block_for_insn (insn, a); + insn = BB_HEAD (b); + /* Skip possible DELETED_LABEL insn. */ + if (!NOTE_INSN_BASIC_BLOCK_P (insn)) + insn = NEXT_INSN (insn); + gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn)); + BB_HEAD (b) = NULL; + BB_END (a) = BB_END (b); + delete_insn (insn); + } + + /* Possible tablejumps and barriers should appear after the block. */ + if (b->rbi->footer) + { + if (!a->rbi->footer) + a->rbi->footer = b->rbi->footer; + else + { + rtx last = a->rbi->footer; + + while (NEXT_INSN (last)) + last = NEXT_INSN (last); + NEXT_INSN (last) = b->rbi->footer; + PREV_INSN (b->rbi->footer) = last; + } + b->rbi->footer = NULL; + } + + if (dump_file) + fprintf (dump_file, "Merged blocks %d and %d.\n", + a->index, b->index); +} + +/* Split edge E. */ + +static basic_block +cfg_layout_split_edge (edge e) +{ + edge new_e; + basic_block new_bb = + create_basic_block (e->src != ENTRY_BLOCK_PTR + ? NEXT_INSN (BB_END (e->src)) : get_insns (), + NULL_RTX, e->src); + + /* ??? This info is likely going to be out of date very soon, but we must + create it to avoid getting an ICE later. */ + if (e->dest->global_live_at_start) + { + new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack); + new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack); + COPY_REG_SET (new_bb->global_live_at_start, + e->dest->global_live_at_start); + COPY_REG_SET (new_bb->global_live_at_end, + e->dest->global_live_at_start); + } + + new_e = make_edge (new_bb, e->dest, EDGE_FALLTHRU); + redirect_edge_and_branch_force (e, new_bb); + + return new_bb; +} + +/* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */ + +static void +rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED) +{ +} + +/* Return 1 if BB ends with a call, possibly followed by some + instructions that must stay with the call, 0 otherwise. */ + +static bool +rtl_block_ends_with_call_p (basic_block bb) +{ + rtx insn = BB_END (bb); + + while (!CALL_P (insn) + && insn != BB_HEAD (bb) + && keep_with_call_p (insn)) + insn = PREV_INSN (insn); + return (CALL_P (insn)); +} + +/* Return 1 if BB ends with a conditional branch, 0 otherwise. */ + +static bool +rtl_block_ends_with_condjump_p (basic_block bb) +{ + return any_condjump_p (BB_END (bb)); +} + +/* Return true if we need to add fake edge to exit. + Helper function for rtl_flow_call_edges_add. */ + +static bool +need_fake_edge_p (rtx insn) +{ + if (!INSN_P (insn)) + return false; + + if ((CALL_P (insn) + && !SIBLING_CALL_P (insn) + && !find_reg_note (insn, REG_NORETURN, NULL) + && !find_reg_note (insn, REG_ALWAYS_RETURN, NULL) + && !CONST_OR_PURE_CALL_P (insn))) + return true; + + return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS + && MEM_VOLATILE_P (PATTERN (insn))) + || (GET_CODE (PATTERN (insn)) == PARALLEL + && asm_noperands (insn) != -1 + && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0))) + || GET_CODE (PATTERN (insn)) == ASM_INPUT); +} + +/* Add fake edges to the function exit for any non constant and non noreturn + calls, volatile inline assembly in the bitmap of blocks specified by + BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks + that were split. + + The goal is to expose cases in which entering a basic block does not imply + that all subsequent instructions must be executed. */ + +static int +rtl_flow_call_edges_add (sbitmap blocks) +{ + int i; + int blocks_split = 0; + int last_bb = last_basic_block; + bool check_last_block = false; + + if (n_basic_blocks == 0) + return 0; + + if (! blocks) + check_last_block = true; + else + check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index); + + /* In the last basic block, before epilogue generation, there will be + a fallthru edge to EXIT. Special care is required if the last insn + of the last basic block is a call because make_edge folds duplicate + edges, which would result in the fallthru edge also being marked + fake, which would result in the fallthru edge being removed by + remove_fake_edges, which would result in an invalid CFG. + + Moreover, we can't elide the outgoing fake edge, since the block + profiler needs to take this into account in order to solve the minimal + spanning tree in the case that the call doesn't return. + + Handle this by adding a dummy instruction in a new last basic block. */ + if (check_last_block) + { + basic_block bb = EXIT_BLOCK_PTR->prev_bb; + rtx insn = BB_END (bb); + + /* Back up past insns that must be kept in the same block as a call. */ + while (insn != BB_HEAD (bb) + && keep_with_call_p (insn)) + insn = PREV_INSN (insn); + + if (need_fake_edge_p (insn)) + { + edge e; + edge_iterator ei; + + FOR_EACH_EDGE (e, ei, bb->succs) + if (e->dest == EXIT_BLOCK_PTR) + { + insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e); + commit_edge_insertions (); + break; + } + } + } + + /* Now add fake edges to the function exit for any non constant + calls since there is no way that we can determine if they will + return or not... */ + + for (i = 0; i < last_bb; i++) + { + basic_block bb = BASIC_BLOCK (i); + rtx insn; + rtx prev_insn; + + if (!bb) + continue; + + if (blocks && !TEST_BIT (blocks, i)) + continue; + + for (insn = BB_END (bb); ; insn = prev_insn) + { + prev_insn = PREV_INSN (insn); + if (need_fake_edge_p (insn)) + { + edge e; + rtx split_at_insn = insn; + + /* Don't split the block between a call and an insn that should + remain in the same block as the call. */ + if (CALL_P (insn)) + while (split_at_insn != BB_END (bb) + && keep_with_call_p (NEXT_INSN (split_at_insn))) + split_at_insn = NEXT_INSN (split_at_insn); + + /* The handling above of the final block before the epilogue + should be enough to verify that there is no edge to the exit + block in CFG already. Calling make_edge in such case would + cause us to mark that edge as fake and remove it later. */ + +#ifdef ENABLE_CHECKING + if (split_at_insn == BB_END (bb)) + { + edge_iterator ei; + FOR_EACH_EDGE (e, ei, bb->succs) + gcc_assert (e->dest != EXIT_BLOCK_PTR); + } +#endif + + /* Note that the following may create a new basic block + and renumber the existing basic blocks. */ + if (split_at_insn != BB_END (bb)) + { + e = split_block (bb, split_at_insn); + if (e) + blocks_split++; + } + + make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); + } + + if (insn == BB_HEAD (bb)) + break; + } + } + + if (blocks_split) + verify_flow_info (); + + return blocks_split; +} + +/* Implementation of CFG manipulation for linearized RTL. */ +struct cfg_hooks rtl_cfg_hooks = { + "rtl", + rtl_verify_flow_info, + rtl_dump_bb, + rtl_create_basic_block, + rtl_redirect_edge_and_branch, + rtl_redirect_edge_and_branch_force, + rtl_delete_block, + rtl_split_block, + rtl_move_block_after, + rtl_can_merge_blocks, /* can_merge_blocks_p */ + rtl_merge_blocks, + rtl_predict_edge, + rtl_predicted_by_p, + NULL, /* can_duplicate_block_p */ + NULL, /* duplicate_block */ + rtl_split_edge, + rtl_make_forwarder_block, + rtl_tidy_fallthru_edge, + rtl_block_ends_with_call_p, + rtl_block_ends_with_condjump_p, + rtl_flow_call_edges_add +}; + +/* Implementation of CFG manipulation for cfg layout RTL, where + basic block connected via fallthru edges does not have to be adjacent. + This representation will hopefully become the default one in future + version of the compiler. */ + +/* We do not want to declare these functions in a header file, since they + should only be used through the cfghooks interface, and we do not want to + move them here since it would require also moving quite a lot of related + code. */ +extern bool cfg_layout_can_duplicate_bb_p (basic_block); +extern basic_block cfg_layout_duplicate_bb (basic_block); + +struct cfg_hooks cfg_layout_rtl_cfg_hooks = { + "cfglayout mode", + rtl_verify_flow_info_1, + rtl_dump_bb, + cfg_layout_create_basic_block, + cfg_layout_redirect_edge_and_branch, + cfg_layout_redirect_edge_and_branch_force, + cfg_layout_delete_block, + cfg_layout_split_block, + rtl_move_block_after, + cfg_layout_can_merge_blocks_p, + cfg_layout_merge_blocks, + rtl_predict_edge, + rtl_predicted_by_p, + cfg_layout_can_duplicate_bb_p, + cfg_layout_duplicate_bb, + cfg_layout_split_edge, + rtl_make_forwarder_block, + NULL, + rtl_block_ends_with_call_p, + rtl_block_ends_with_condjump_p, + rtl_flow_call_edges_add +}; +