| /* Control flow graph manipulation code for GNU compiler. |
| Copyright (C) 1987-2017 Free Software Foundation, Inc. |
| |
| This file is part of GCC. |
| |
| GCC is free software; you can redistribute it and/or modify it under |
| the terms of the GNU General Public License as published by the Free |
| Software Foundation; either version 3, or (at your option) any later |
| version. |
| |
| GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
| WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GCC; see the file COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| /* This file contains low level functions to manipulate the CFG and analyze it |
| 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 |
| - 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 |
| - CFG fixing after coarse manipulation |
| fixup_abnormal_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, tidy_fallthru_edge, force_nonfallthru */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "backend.h" |
| #include "target.h" |
| #include "rtl.h" |
| #include "tree.h" |
| #include "cfghooks.h" |
| #include "df.h" |
| #include "insn-config.h" |
| #include "memmodel.h" |
| #include "emit-rtl.h" |
| #include "cfgrtl.h" |
| #include "cfganal.h" |
| #include "cfgbuild.h" |
| #include "cfgcleanup.h" |
| #include "bb-reorder.h" |
| #include "rtl-error.h" |
| #include "insn-attr.h" |
| #include "dojump.h" |
| #include "expr.h" |
| #include "cfgloop.h" |
| #include "tree-pass.h" |
| #include "print-rtl.h" |
| |
| /* Holds the interesting leading and trailing notes for the function. |
| Only applicable if the CFG is in cfglayout mode. */ |
| static GTY(()) rtx_insn *cfg_layout_function_footer; |
| static GTY(()) rtx_insn *cfg_layout_function_header; |
| |
| static rtx_insn *skip_insns_after_block (basic_block); |
| static void record_effective_endpoints (void); |
| static void fixup_reorder_chain (void); |
| |
| void verify_insn_chain (void); |
| static void fixup_fallthru_exit_predecessor (void); |
| static int can_delete_note_p (const rtx_note *); |
| static int can_delete_label_p (const rtx_code_label *); |
| 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 (FILE *, basic_block, int, int); |
| static int rtl_verify_flow_info_1 (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 (const rtx_note *note) |
| { |
| switch (NOTE_KIND (note)) |
| { |
| case NOTE_INSN_DELETED: |
| case NOTE_INSN_BASIC_BLOCK: |
| case NOTE_INSN_EPILOGUE_BEG: |
| return true; |
| |
| default: |
| return false; |
| } |
| } |
| |
| /* True if a given label can be deleted. */ |
| |
| static int |
| can_delete_label_p (const rtx_code_label *label) |
| { |
| return (!LABEL_PRESERVE_P (label) |
| /* User declared labels must be preserved. */ |
| && LABEL_NAME (label) == 0 |
| && !vec_safe_contains<rtx_insn *> (forced_labels, |
| const_cast<rtx_code_label *> (label))); |
| } |
| |
| /* Delete INSN by patching it out. */ |
| |
| void |
| delete_insn (rtx_insn *insn) |
| { |
| rtx note; |
| bool really_delete = true; |
| |
| 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. |
| Convert them to the special NOTE_INSN_DELETED_LABEL note. */ |
| if (! can_delete_label_p (as_a <rtx_code_label *> (insn))) |
| { |
| const char *name = LABEL_NAME (insn); |
| basic_block bb = BLOCK_FOR_INSN (insn); |
| rtx_insn *bb_note = NEXT_INSN (insn); |
| |
| really_delete = false; |
| PUT_CODE (insn, NOTE); |
| NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL; |
| NOTE_DELETED_LABEL_NAME (insn) = name; |
| |
| /* If the note following the label starts a basic block, and the |
| label is a member of the same basic block, interchange the two. */ |
| if (bb_note != NULL_RTX |
| && NOTE_INSN_BASIC_BLOCK_P (bb_note) |
| && bb != NULL |
| && bb == BLOCK_FOR_INSN (bb_note)) |
| { |
| reorder_insns_nobb (insn, insn, bb_note); |
| BB_HEAD (bb) = bb_note; |
| if (BB_END (bb) == bb_note) |
| BB_END (bb) = insn; |
| } |
| } |
| |
| remove_node_from_insn_list (insn, &nonlocal_goto_handler_labels); |
| } |
| |
| if (really_delete) |
| { |
| /* If this insn has already been deleted, something is very wrong. */ |
| gcc_assert (!insn->deleted ()); |
| if (INSN_P (insn)) |
| df_insn_delete (insn); |
| remove_insn (insn); |
| insn->set_deleted (); |
| } |
| |
| /* 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 (JUMP_P (insn)) |
| { |
| if (JUMP_LABEL (insn) |
| && LABEL_P (JUMP_LABEL (insn))) |
| LABEL_NUSES (JUMP_LABEL (insn))--; |
| |
| /* If there are more targets, remove them too. */ |
| while ((note |
| = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX |
| && LABEL_P (XEXP (note, 0))) |
| { |
| LABEL_NUSES (XEXP (note, 0))--; |
| remove_note (insn, note); |
| } |
| } |
| |
| /* Also if deleting any insn that references a label as an operand. */ |
| while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX |
| && LABEL_P (XEXP (note, 0))) |
| { |
| LABEL_NUSES (XEXP (note, 0))--; |
| remove_note (insn, note); |
| } |
| |
| if (rtx_jump_table_data *table = dyn_cast <rtx_jump_table_data *> (insn)) |
| { |
| rtvec vec = table->get_labels (); |
| int len = GET_NUM_ELEM (vec); |
| int i; |
| |
| for (i = 0; i < len; i++) |
| { |
| rtx label = XEXP (RTVEC_ELT (vec, i), 0); |
| |
| /* 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 (!NOTE_P (label)) |
| LABEL_NUSES (label)--; |
| } |
| } |
| } |
| |
| /* Like delete_insn but also purge dead edges from BB. |
| Return true if any edges are eliminated. */ |
| |
| bool |
| delete_insn_and_edges (rtx_insn *insn) |
| { |
| bool purge = false; |
| |
| if (INSN_P (insn) |
| && BLOCK_FOR_INSN (insn) |
| && BB_END (BLOCK_FOR_INSN (insn)) == insn) |
| purge = true; |
| delete_insn (insn); |
| if (purge) |
| return purge_dead_edges (BLOCK_FOR_INSN (insn)); |
| return false; |
| } |
| |
| /* Unlink a chain of insns between START and FINISH, leaving notes |
| that must be paired. If CLEAR_BB is true, we set bb field for |
| insns that cannot be removed to NULL. */ |
| |
| void |
| delete_insn_chain (rtx start, rtx_insn *finish, bool clear_bb) |
| { |
| /* Unchain the insns one by one. It would be quicker to delete all of these |
| with a single unchaining, rather than one at a time, but we need to keep |
| the NOTE's. */ |
| rtx_insn *current = finish; |
| while (1) |
| { |
| rtx_insn *prev = PREV_INSN (current); |
| if (NOTE_P (current) && !can_delete_note_p (as_a <rtx_note *> (current))) |
| ; |
| else |
| delete_insn (current); |
| |
| if (clear_bb && !current->deleted ()) |
| set_block_for_insn (current, NULL); |
| |
| if (current == start) |
| break; |
| current = prev; |
| } |
| } |
| |
| /* Create a new basic block consisting of the instructions between HEAD and END |
| inclusive. This function is designed to allow fast BB construction - reuses |
| the note and basic block struct in BB_NOTE, if any and do not grow |
| BASIC_BLOCK chain and should be used directly only by CFG construction code. |
| END can be NULL in to create new empty basic block before HEAD. Both END |
| and HEAD can be NULL to create basic block at the end of INSN chain. |
| AFTER is the basic block we should be put after. */ |
| |
| basic_block |
| create_basic_block_structure (rtx_insn *head, rtx_insn *end, rtx_note *bb_note, |
| basic_block after) |
| { |
| basic_block bb; |
| |
| if (bb_note |
| && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL |
| && bb->aux == NULL) |
| { |
| /* If we found an existing note, thread it back onto the chain. */ |
| |
| rtx_insn *after; |
| |
| if (LABEL_P (head)) |
| after = head; |
| else |
| { |
| after = PREV_INSN (head); |
| head = bb_note; |
| } |
| |
| if (after != bb_note && NEXT_INSN (after) != bb_note) |
| reorder_insns_nobb (bb_note, bb_note, after); |
| } |
| else |
| { |
| /* Otherwise we must create a note and a basic block structure. */ |
| |
| bb = alloc_block (); |
| |
| init_rtl_bb_info (bb); |
| if (!head && !end) |
| head = end = bb_note |
| = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ()); |
| else if (LABEL_P (head) && end) |
| { |
| bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head); |
| if (head == end) |
| end = bb_note; |
| } |
| else |
| { |
| bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head); |
| head = bb_note; |
| if (!end) |
| end = head; |
| } |
| |
| NOTE_BASIC_BLOCK (bb_note) = bb; |
| } |
| |
| /* Always include the bb note in the block. */ |
| if (NEXT_INSN (end) == bb_note) |
| end = bb_note; |
| |
| BB_HEAD (bb) = head; |
| BB_END (bb) = end; |
| bb->index = last_basic_block_for_fn (cfun)++; |
| bb->flags = BB_NEW | BB_RTL; |
| link_block (bb, after); |
| SET_BASIC_BLOCK_FOR_FN (cfun, bb->index, bb); |
| df_bb_refs_record (bb->index, false); |
| 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. */ |
| bb->aux = bb; |
| |
| return bb; |
| } |
| |
| /* Create new basic block consisting of instructions in between HEAD and END |
| and place it to the BB chain after block AFTER. END can be NULL to |
| create a new empty basic block before HEAD. Both END and HEAD can be |
| NULL to create basic block at the end of INSN chain. */ |
| |
| static basic_block |
| rtl_create_basic_block (void *headp, void *endp, basic_block after) |
| { |
| rtx_insn *head = (rtx_insn *) headp; |
| rtx_insn *end = (rtx_insn *) endp; |
| basic_block bb; |
| |
| /* Grow the basic block array if needed. */ |
| if ((size_t) last_basic_block_for_fn (cfun) |
| >= basic_block_info_for_fn (cfun)->length ()) |
| { |
| size_t new_size = |
| (last_basic_block_for_fn (cfun) |
| + (last_basic_block_for_fn (cfun) + 3) / 4); |
| vec_safe_grow_cleared (basic_block_info_for_fn (cfun), new_size); |
| } |
| |
| n_basic_blocks_for_fn (cfun)++; |
| |
| bb = create_basic_block_structure (head, end, NULL, 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); |
| |
| return newbb; |
| } |
| |
| /* Delete the insns in a (non-live) block. We physically delete every |
| non-deleted-note insn, and update the flow graph appropriately. |
| |
| Return nonzero if we deleted an exception handler. */ |
| |
| /* ??? Preserving all such notes strikes me as wrong. It would be nice |
| to post-process the stream to remove empty blocks, loops, ranges, etc. */ |
| |
| static void |
| rtl_delete_block (basic_block b) |
| { |
| rtx_insn *insn, *end; |
| |
| /* If the head of this block is a CODE_LABEL, then it might be the |
| label for an exception handler which can't be reached. We need |
| to remove the label from the exception_handler_label list. */ |
| insn = BB_HEAD (b); |
| |
| end = get_last_bb_insn (b); |
| |
| /* Selectively delete the entire chain. */ |
| BB_HEAD (b) = NULL; |
| delete_insn_chain (insn, end, true); |
| |
| |
| if (dump_file) |
| fprintf (dump_file, "deleting block %d\n", b->index); |
| df_bb_delete (b->index); |
| } |
| |
| /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */ |
| |
| void |
| compute_bb_for_insn (void) |
| { |
| basic_block bb; |
| |
| FOR_EACH_BB_FN (bb, cfun) |
| { |
| rtx_insn *end = BB_END (bb); |
| rtx_insn *insn; |
| |
| for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) |
| { |
| BLOCK_FOR_INSN (insn) = bb; |
| if (insn == end) |
| break; |
| } |
| } |
| } |
| |
| /* Release the basic_block_for_insn array. */ |
| |
| unsigned int |
| free_bb_for_insn (void) |
| { |
| rtx_insn *insn; |
| for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) |
| if (!BARRIER_P (insn)) |
| BLOCK_FOR_INSN (insn) = NULL; |
| return 0; |
| } |
| |
| namespace { |
| |
| const pass_data pass_data_free_cfg = |
| { |
| RTL_PASS, /* type */ |
| "*free_cfg", /* name */ |
| OPTGROUP_NONE, /* optinfo_flags */ |
| TV_NONE, /* tv_id */ |
| 0, /* properties_required */ |
| 0, /* properties_provided */ |
| PROP_cfg, /* properties_destroyed */ |
| 0, /* todo_flags_start */ |
| 0, /* todo_flags_finish */ |
| }; |
| |
| class pass_free_cfg : public rtl_opt_pass |
| { |
| public: |
| pass_free_cfg (gcc::context *ctxt) |
| : rtl_opt_pass (pass_data_free_cfg, ctxt) |
| {} |
| |
| /* opt_pass methods: */ |
| virtual unsigned int execute (function *); |
| |
| }; // class pass_free_cfg |
| |
| unsigned int |
| pass_free_cfg::execute (function *) |
| { |
| /* The resource.c machinery uses DF but the CFG isn't guaranteed to be |
| valid at that point so it would be too late to call df_analyze. */ |
| if (DELAY_SLOTS && optimize > 0 && flag_delayed_branch) |
| { |
| df_note_add_problem (); |
| df_analyze (); |
| } |
| |
| if (crtl->has_bb_partition) |
| insert_section_boundary_note (); |
| |
| free_bb_for_insn (); |
| return 0; |
| } |
| |
| } // anon namespace |
| |
| rtl_opt_pass * |
| make_pass_free_cfg (gcc::context *ctxt) |
| { |
| return new pass_free_cfg (ctxt); |
| } |
| |
| /* Return RTX to emit after when we want to emit code on the entry of function. */ |
| rtx_insn * |
| entry_of_function (void) |
| { |
| return (n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS ? |
| BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) : get_insns ()); |
| } |
| |
| /* Emit INSN at the entry point of the function, ensuring that it is only |
| executed once per function. */ |
| void |
| emit_insn_at_entry (rtx insn) |
| { |
| edge_iterator ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs); |
| edge e = ei_safe_edge (ei); |
| gcc_assert (e->flags & EDGE_FALLTHRU); |
| |
| insert_insn_on_edge (insn, e); |
| commit_edge_insertions (); |
| } |
| |
| /* Update BLOCK_FOR_INSN of insns between BEGIN and END |
| (or BARRIER if found) and notify df of the bb change. |
| The insn chain range is inclusive |
| (i.e. both BEGIN and END will be updated. */ |
| |
| static void |
| update_bb_for_insn_chain (rtx_insn *begin, rtx_insn *end, basic_block bb) |
| { |
| rtx_insn *insn; |
| |
| end = NEXT_INSN (end); |
| for (insn = begin; insn != end; insn = NEXT_INSN (insn)) |
| if (!BARRIER_P (insn)) |
| df_insn_change_bb (insn, bb); |
| } |
| |
| /* Update BLOCK_FOR_INSN of insns in BB to BB, |
| and notify df of the change. */ |
| |
| void |
| update_bb_for_insn (basic_block bb) |
| { |
| update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb); |
| } |
| |
| |
| /* Like active_insn_p, except keep the return value clobber around |
| even after reload. */ |
| |
| static bool |
| flow_active_insn_p (const rtx_insn *insn) |
| { |
| if (active_insn_p (insn)) |
| return true; |
| |
| /* A clobber of the function return value exists for buggy |
| programs that fail to return a value. Its effect is to |
| keep the return value from being live across the entire |
| function. If we allow it to be skipped, we introduce the |
| possibility for register lifetime confusion. */ |
| if (GET_CODE (PATTERN (insn)) == CLOBBER |
| && REG_P (XEXP (PATTERN (insn), 0)) |
| && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0))) |
| return true; |
| |
| return false; |
| } |
| |
| /* Return true if the block has no effect and only forwards control flow to |
| its single destination. */ |
| |
| bool |
| contains_no_active_insn_p (const_basic_block bb) |
| { |
| rtx_insn *insn; |
| |
| if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) |
| || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) |
| || !single_succ_p (bb) |
| || (single_succ_edge (bb)->flags & EDGE_FAKE) != 0) |
| return false; |
| |
| for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn)) |
| if (INSN_P (insn) && flow_active_insn_p (insn)) |
| return false; |
| |
| return (!INSN_P (insn) |
| || (JUMP_P (insn) && simplejump_p (insn)) |
| || !flow_active_insn_p (insn)); |
| } |
| |
| /* Likewise, but protect loop latches, headers and preheaders. */ |
| /* FIXME: Make this a cfg hook. */ |
| |
| bool |
| forwarder_block_p (const_basic_block bb) |
| { |
| if (!contains_no_active_insn_p (bb)) |
| return false; |
| |
| /* Protect loop latches, headers and preheaders. */ |
| if (current_loops) |
| { |
| basic_block dest; |
| if (bb->loop_father->header == bb) |
| return false; |
| dest = EDGE_SUCC (bb, 0)->dest; |
| if (dest->loop_father->header == dest) |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /* Return nonzero if we can reach target from src by falling through. */ |
| /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */ |
| |
| bool |
| can_fallthru (basic_block src, basic_block target) |
| { |
| rtx_insn *insn = BB_END (src); |
| rtx_insn *insn2; |
| edge e; |
| edge_iterator ei; |
| |
| if (target == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| return true; |
| if (src->next_bb != target) |
| return false; |
| |
| /* ??? Later we may add code to move jump tables offline. */ |
| if (tablejump_p (insn, NULL, NULL)) |
| return false; |
| |
| FOR_EACH_EDGE (e, ei, src->succs) |
| if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) |
| && e->flags & EDGE_FALLTHRU) |
| return false; |
| |
| insn2 = BB_HEAD (target); |
| if (!active_insn_p (insn2)) |
| insn2 = next_active_insn (insn2); |
| |
| return next_active_insn (insn) == insn2; |
| } |
| |
| /* Return nonzero if we could reach target from src by falling through, |
| if the target was made adjacent. If we already have a fall-through |
| edge to the exit block, we can't do that. */ |
| static bool |
| could_fall_through (basic_block src, basic_block target) |
| { |
| edge e; |
| edge_iterator ei; |
| |
| if (target == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| return true; |
| FOR_EACH_EDGE (e, ei, src->succs) |
| if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) |
| && e->flags & EDGE_FALLTHRU) |
| return 0; |
| return true; |
| } |
| |
| /* Return the NOTE_INSN_BASIC_BLOCK of BB. */ |
| rtx_note * |
| bb_note (basic_block bb) |
| { |
| rtx_insn *note; |
| |
| note = BB_HEAD (bb); |
| if (LABEL_P (note)) |
| note = NEXT_INSN (note); |
| |
| gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); |
| return as_a <rtx_note *> (note); |
| } |
| |
| /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK |
| note associated with the BLOCK. */ |
| |
| static rtx_insn * |
| first_insn_after_basic_block_note (basic_block block) |
| { |
| rtx_insn *insn; |
| |
| /* Get the first instruction in the block. */ |
| insn = BB_HEAD (block); |
| |
| if (insn == NULL_RTX) |
| return NULL; |
| if (LABEL_P (insn)) |
| insn = NEXT_INSN (insn); |
| gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn)); |
| |
| return NEXT_INSN (insn); |
| } |
| |
| /* Creates a new basic block just after basic block BB by splitting |
| everything after specified instruction INSNP. */ |
| |
| static basic_block |
| rtl_split_block (basic_block bb, void *insnp) |
| { |
| basic_block new_bb; |
| rtx_insn *insn = (rtx_insn *) insnp; |
| edge e; |
| edge_iterator ei; |
| |
| if (!insn) |
| { |
| insn = first_insn_after_basic_block_note (bb); |
| |
| if (insn) |
| { |
| rtx_insn *next = insn; |
| |
| insn = PREV_INSN (insn); |
| |
| /* If the block contains only debug insns, insn would have |
| been NULL in a non-debug compilation, and then we'd end |
| up emitting a DELETED note. For -fcompare-debug |
| stability, emit the note too. */ |
| if (insn != BB_END (bb) |
| && DEBUG_INSN_P (next) |
| && DEBUG_INSN_P (BB_END (bb))) |
| { |
| while (next != BB_END (bb) && DEBUG_INSN_P (next)) |
| next = NEXT_INSN (next); |
| |
| if (next == BB_END (bb)) |
| emit_note_after (NOTE_INSN_DELETED, next); |
| } |
| } |
| 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), bb); |
| BB_COPY_PARTITION (new_bb, bb); |
| BB_END (bb) = insn; |
| |
| /* Redirect the outgoing edges. */ |
| new_bb->succs = bb->succs; |
| bb->succs = NULL; |
| FOR_EACH_EDGE (e, ei, new_bb->succs) |
| e->src = new_bb; |
| |
| /* The new block starts off being dirty. */ |
| df_set_bb_dirty (bb); |
| return new_bb; |
| } |
| |
| /* Return true if the single edge between blocks A and B is the only place |
| in RTL which holds some unique locus. */ |
| |
| static bool |
| unique_locus_on_edge_between_p (basic_block a, basic_block b) |
| { |
| const location_t goto_locus = EDGE_SUCC (a, 0)->goto_locus; |
| rtx_insn *insn, *end; |
| |
| if (LOCATION_LOCUS (goto_locus) == UNKNOWN_LOCATION) |
| return false; |
| |
| /* First scan block A backward. */ |
| insn = BB_END (a); |
| end = PREV_INSN (BB_HEAD (a)); |
| while (insn != end && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn))) |
| insn = PREV_INSN (insn); |
| |
| if (insn != end && INSN_LOCATION (insn) == goto_locus) |
| return false; |
| |
| /* Then scan block B forward. */ |
| insn = BB_HEAD (b); |
| if (insn) |
| { |
| end = NEXT_INSN (BB_END (b)); |
| while (insn != end && !NONDEBUG_INSN_P (insn)) |
| insn = NEXT_INSN (insn); |
| |
| if (insn != end && INSN_HAS_LOCATION (insn) |
| && INSN_LOCATION (insn) == goto_locus) |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /* If the single edge between blocks A and B is the only place in RTL which |
| holds some unique locus, emit a nop with that locus between the blocks. */ |
| |
| static void |
| emit_nop_for_unique_locus_between (basic_block a, basic_block b) |
| { |
| if (!unique_locus_on_edge_between_p (a, b)) |
| return; |
| |
| BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a); |
| INSN_LOCATION (BB_END (a)) = EDGE_SUCC (a, 0)->goto_locus; |
| } |
| |
| /* Blocks A and B are to be merged into a single block A. The insns |
| are already contiguous. */ |
| |
| static void |
| rtl_merge_blocks (basic_block a, basic_block b) |
| { |
| rtx_insn *b_head = BB_HEAD (b), *b_end = BB_END (b), *a_end = BB_END (a); |
| rtx_insn *del_first = NULL, *del_last = NULL; |
| rtx_insn *b_debug_start = b_end, *b_debug_end = b_end; |
| bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0; |
| int b_empty = 0; |
| |
| if (dump_file) |
| fprintf (dump_file, "Merging block %d into block %d...\n", b->index, |
| a->index); |
| |
| while (DEBUG_INSN_P (b_end)) |
| b_end = PREV_INSN (b_debug_start = b_end); |
| |
| /* If there was a CODE_LABEL beginning B, delete it. */ |
| if (LABEL_P (b_head)) |
| { |
| /* Detect basic blocks with nothing but a label. This can happen |
| in particular at the end of a function. */ |
| if (b_head == b_end) |
| b_empty = 1; |
| |
| del_first = del_last = b_head; |
| b_head = NEXT_INSN (b_head); |
| } |
| |
| /* Delete the basic block note and handle blocks containing just that |
| note. */ |
| if (NOTE_INSN_BASIC_BLOCK_P (b_head)) |
| { |
| if (b_head == b_end) |
| b_empty = 1; |
| if (! del_last) |
| del_first = b_head; |
| |
| del_last = b_head; |
| b_head = NEXT_INSN (b_head); |
| } |
| |
| /* If there was a jump out of A, delete it. */ |
| if (JUMP_P (a_end)) |
| { |
| rtx_insn *prev; |
| |
| for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev)) |
| if (!NOTE_P (prev) |
| || NOTE_INSN_BASIC_BLOCK_P (prev) |
| || prev == BB_HEAD (a)) |
| break; |
| |
| del_first = a_end; |
| |
| /* If this was a conditional jump, we need to also delete |
| the insn that set cc0. */ |
| if (HAVE_cc0 && only_sets_cc0_p (prev)) |
| { |
| rtx_insn *tmp = prev; |
| |
| prev = prev_nonnote_insn (prev); |
| if (!prev) |
| prev = BB_HEAD (a); |
| del_first = tmp; |
| } |
| |
| a_end = PREV_INSN (del_first); |
| } |
| else if (BARRIER_P (NEXT_INSN (a_end))) |
| del_first = NEXT_INSN (a_end); |
| |
| /* Delete everything marked above as well as crap that might be |
| hanging out between the two blocks. */ |
| BB_END (a) = a_end; |
| BB_HEAD (b) = b_empty ? NULL : b_head; |
| delete_insn_chain (del_first, del_last, true); |
| |
| /* When not optimizing and the edge is the only place in RTL which holds |
| some unique locus, emit a nop with that locus in between. */ |
| if (!optimize) |
| { |
| emit_nop_for_unique_locus_between (a, b); |
| a_end = BB_END (a); |
| } |
| |
| /* Reassociate the insns of B with A. */ |
| if (!b_empty) |
| { |
| update_bb_for_insn_chain (a_end, b_debug_end, a); |
| |
| BB_END (a) = b_debug_end; |
| BB_HEAD (b) = NULL; |
| } |
| else if (b_end != b_debug_end) |
| { |
| /* Move any deleted labels and other notes between the end of A |
| and the debug insns that make up B after the debug insns, |
| bringing the debug insns into A while keeping the notes after |
| the end of A. */ |
| if (NEXT_INSN (a_end) != b_debug_start) |
| reorder_insns_nobb (NEXT_INSN (a_end), PREV_INSN (b_debug_start), |
| b_debug_end); |
| update_bb_for_insn_chain (b_debug_start, b_debug_end, a); |
| BB_END (a) = b_debug_end; |
| } |
| |
| df_bb_delete (b->index); |
| |
| /* If B was a forwarder block, propagate the locus on the edge. */ |
| if (forwarder_p |
| && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION) |
| EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus; |
| |
| if (dump_file) |
| fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index); |
| } |
| |
| |
| /* 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 (BB_PARTITION (a) != BB_PARTITION (b)) |
| return false; |
| |
| /* Protect the loop latches. */ |
| if (current_loops && b->loop_father->latch == b) |
| return false; |
| |
| /* There must be exactly one edge in between the blocks. */ |
| return (single_succ_p (a) |
| && single_succ (a) == b |
| && single_pred_p (b) |
| && a != b |
| /* Must be simple edge. */ |
| && !(single_succ_edge (a)->flags & EDGE_COMPLEX) |
| && a->next_bb == b |
| && a != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
| && b != EXIT_BLOCK_PTR_FOR_FN (cfun) |
| /* 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_code_label * |
| block_label (basic_block block) |
| { |
| if (block == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| return NULL; |
| |
| if (!LABEL_P (BB_HEAD (block))) |
| { |
| BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block)); |
| } |
| |
| return as_a <rtx_code_label *> (BB_HEAD (block)); |
| } |
| |
| /* Attempt to perform edge redirection by replacing possibly complex jump |
| instruction by unconditional jump or removing jump completely. This can |
| apply only if all edges now point to the same block. The parameters and |
| return values are equivalent to redirect_edge_and_branch. */ |
| |
| edge |
| try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout) |
| { |
| basic_block src = e->src; |
| rtx_insn *insn = BB_END (src), *kill_from; |
| rtx set; |
| int fallthru = 0; |
| |
| /* 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 (BB_PARTITION (src) != BB_PARTITION (target)) |
| return NULL; |
| |
| /* We can replace or remove a complex jump only when we have exactly |
| two edges. Also, if we have exactly one outgoing edge, we can |
| redirect that. */ |
| if (EDGE_COUNT (src->succs) >= 3 |
| /* Verify that all targets will be TARGET. Specifically, the |
| edge that is not E must also go to TARGET. */ |
| || (EDGE_COUNT (src->succs) == 2 |
| && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)) |
| return NULL; |
| |
| if (!onlyjump_p (insn)) |
| 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 NULL; |
| |
| /* In case we zap a conditional jump, we'll need to kill |
| the cc0 setter too. */ |
| kill_from = insn; |
| if (HAVE_cc0 && reg_mentioned_p (cc0_rtx, PATTERN (insn)) |
| && only_sets_cc0_p (PREV_INSN (insn))) |
| kill_from = PREV_INSN (insn); |
| |
| /* See if we can create the fallthru edge. */ |
| if (in_cfglayout || can_fallthru (src, target)) |
| { |
| if (dump_file) |
| fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn)); |
| fallthru = 1; |
| |
| /* Selectively unlink whole insn chain. */ |
| if (in_cfglayout) |
| { |
| rtx_insn *insn = BB_FOOTER (src); |
| |
| delete_insn_chain (kill_from, BB_END (src), false); |
| |
| /* Remove barriers but keep jumptables. */ |
| while (insn) |
| { |
| if (BARRIER_P (insn)) |
| { |
| if (PREV_INSN (insn)) |
| SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn); |
| else |
| BB_FOOTER (src) = NEXT_INSN (insn); |
| if (NEXT_INSN (insn)) |
| SET_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)), |
| false); |
| } |
| |
| /* If this already is simplejump, redirect it. */ |
| else if (simplejump_p (insn)) |
| { |
| if (e->dest == target) |
| 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 (as_a <rtx_jump_insn *> (insn), |
| block_label (target), 0)) |
| { |
| gcc_assert (target == EXIT_BLOCK_PTR_FOR_FN (cfun)); |
| return NULL; |
| } |
| } |
| |
| /* Cannot do anything for target exit block. */ |
| else if (target == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| return NULL; |
| |
| /* Or replace possibly complicated jump insn by simple jump insn. */ |
| else |
| { |
| rtx_code_label *target_label = block_label (target); |
| rtx_insn *barrier; |
| rtx_insn *label; |
| rtx_jump_table_data *table; |
| |
| emit_jump_insn_after_noloc (targetm.gen_jump (target_label), insn); |
| JUMP_LABEL (BB_END (src)) = target_label; |
| LABEL_NUSES (target_label)++; |
| 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, false); |
| |
| /* 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 (tablejump_p (insn, &label, &table)) |
| delete_insn_chain (label, table, false); |
| |
| barrier = next_nonnote_insn (BB_END (src)); |
| if (!barrier || !BARRIER_P (barrier)) |
| emit_barrier_after (BB_END (src)); |
| else |
| { |
| 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_insn *new_insn = BB_END (src); |
| |
| update_bb_for_insn_chain (NEXT_INSN (BB_END (src)), |
| PREV_INSN (barrier), src); |
| |
| SET_NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn); |
| SET_PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn); |
| |
| SET_NEXT_INSN (new_insn) = barrier; |
| SET_NEXT_INSN (PREV_INSN (barrier)) = new_insn; |
| |
| SET_PREV_INSN (new_insn) = PREV_INSN (barrier); |
| SET_PREV_INSN (barrier) = new_insn; |
| } |
| } |
| } |
| |
| /* Keep only one edge out and set proper flags. */ |
| if (!single_succ_p (src)) |
| remove_edge (e); |
| gcc_assert (single_succ_p (src)); |
| |
| e = single_succ_edge (src); |
| if (fallthru) |
| e->flags = EDGE_FALLTHRU; |
| else |
| e->flags = 0; |
| |
| e->probability = REG_BR_PROB_BASE; |
| e->count = src->count; |
| |
| if (e->dest != target) |
| redirect_edge_succ (e, target); |
| return e; |
| } |
| |
| /* Subroutine of redirect_branch_edge that tries to patch the jump |
| instruction INSN so that it reaches block NEW. Do this |
| only when it originally reached block OLD. Return true if this |
| worked or the original target wasn't OLD, return false if redirection |
| doesn't work. */ |
| |
| static bool |
| patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb) |
| { |
| rtx_jump_table_data *table; |
| rtx tmp; |
| /* Recognize a tablejump and adjust all matching cases. */ |
| if (tablejump_p (insn, NULL, &table)) |
| { |
| rtvec vec; |
| int j; |
| rtx_code_label *new_label = block_label (new_bb); |
| |
| if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| return false; |
| vec = table->get_labels (); |
| |
| for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j) |
| if (XEXP (RTVEC_ELT (vec, j), 0) == old_label) |
| { |
| RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label); |
| --LABEL_NUSES (old_label); |
| ++LABEL_NUSES (new_label); |
| } |
| |
| /* Handle casesi dispatch insns. */ |
| if ((tmp = single_set (insn)) != NULL |
| && SET_DEST (tmp) == pc_rtx |
| && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE |
| && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF |
| && label_ref_label (XEXP (SET_SRC (tmp), 2)) == old_label) |
| { |
| XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode, |
| new_label); |
| --LABEL_NUSES (old_label); |
| ++LABEL_NUSES (new_label); |
| } |
| } |
| else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL) |
| { |
| int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp); |
| rtx note; |
| |
| if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| return false; |
| rtx_code_label *new_label = block_label (new_bb); |
| |
| for (i = 0; i < n; ++i) |
| { |
| rtx old_ref = ASM_OPERANDS_LABEL (tmp, i); |
| gcc_assert (GET_CODE (old_ref) == LABEL_REF); |
| if (XEXP (old_ref, 0) == old_label) |
| { |
| ASM_OPERANDS_LABEL (tmp, i) |
| = gen_rtx_LABEL_REF (Pmode, new_label); |
| --LABEL_NUSES (old_label); |
| ++LABEL_NUSES (new_label); |
| } |
| } |
| |
| if (JUMP_LABEL (insn) == old_label) |
| { |
| JUMP_LABEL (insn) = new_label; |
| note = find_reg_note (insn, REG_LABEL_TARGET, new_label); |
| if (note) |
| remove_note (insn, note); |
| } |
| else |
| { |
| note = find_reg_note (insn, REG_LABEL_TARGET, old_label); |
| if (note) |
| remove_note (insn, note); |
| if (JUMP_LABEL (insn) != new_label |
| && !find_reg_note (insn, REG_LABEL_TARGET, new_label)) |
| add_reg_note (insn, REG_LABEL_TARGET, new_label); |
| } |
| while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label)) |
| != NULL_RTX) |
| XEXP (note, 0) = new_label; |
| } |
| else |
| { |
| /* ?? We may play the games with moving the named labels from |
| one basic block to the other in case only one computed_jump is |
| available. */ |
| if (computed_jump_p (insn) |
| /* A return instruction can't be redirected. */ |
| || returnjump_p (insn)) |
| return false; |
| |
| if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label) |
| { |
| /* If the insn doesn't go where we think, we're confused. */ |
| 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 (as_a <rtx_jump_insn *> (insn), |
| block_label (new_bb), 0)) |
| { |
| gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)); |
| return false; |
| } |
| } |
| } |
| return true; |
| } |
| |
| |
| /* Redirect edge representing branch of (un)conditional jump or tablejump, |
| NULL on failure */ |
| static edge |
| redirect_branch_edge (edge e, basic_block target) |
| { |
| rtx_insn *old_label = BB_HEAD (e->dest); |
| basic_block src = e->src; |
| rtx_insn *insn = BB_END (src); |
| |
| /* We can only redirect non-fallthru edges of jump insn. */ |
| if (e->flags & EDGE_FALLTHRU) |
| return NULL; |
| else if (!JUMP_P (insn) && !currently_expanding_to_rtl) |
| return NULL; |
| |
| if (!currently_expanding_to_rtl) |
| { |
| if (!patch_jump_insn (as_a <rtx_jump_insn *> (insn), old_label, target)) |
| return NULL; |
| } |
| else |
| /* When expanding this BB might actually contain multiple |
| jumps (i.e. not yet split by find_many_sub_basic_blocks). |
| Redirect all of those that match our label. */ |
| FOR_BB_INSNS (src, insn) |
| if (JUMP_P (insn) && !patch_jump_insn (as_a <rtx_jump_insn *> (insn), |
| old_label, target)) |
| return NULL; |
| |
| 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) |
| e = redirect_edge_succ_nodup (e, target); |
| |
| return e; |
| } |
| |
| /* Called when edge E has been redirected to a new destination, |
| in order to update the region crossing flag on the edge and |
| jump. */ |
| |
| static void |
| fixup_partition_crossing (edge e) |
| { |
| if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest |
| == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| return; |
| /* If we redirected an existing edge, it may already be marked |
| crossing, even though the new src is missing a reg crossing note. |
| But make sure reg crossing note doesn't already exist before |
| inserting. */ |
| if (BB_PARTITION (e->src) != BB_PARTITION (e->dest)) |
| { |
| e->flags |= EDGE_CROSSING; |
| if (JUMP_P (BB_END (e->src)) |
| && !CROSSING_JUMP_P (BB_END (e->src))) |
| CROSSING_JUMP_P (BB_END (e->src)) = 1; |
| } |
| else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest)) |
| { |
| e->flags &= ~EDGE_CROSSING; |
| /* Remove the section crossing note from jump at end of |
| src if it exists, and if no other successors are |
| still crossing. */ |
| if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src))) |
| { |
| bool has_crossing_succ = false; |
| edge e2; |
| edge_iterator ei; |
| FOR_EACH_EDGE (e2, ei, e->src->succs) |
| { |
| has_crossing_succ |= (e2->flags & EDGE_CROSSING); |
| if (has_crossing_succ) |
| break; |
| } |
| if (!has_crossing_succ) |
| CROSSING_JUMP_P (BB_END (e->src)) = 0; |
| } |
| } |
| } |
| |
| /* Called when block BB has been reassigned to the cold partition, |
| because it is now dominated by another cold block, |
| to ensure that the region crossing attributes are updated. */ |
| |
| static void |
| fixup_new_cold_bb (basic_block bb) |
| { |
| edge e; |
| edge_iterator ei; |
| |
| /* This is called when a hot bb is found to now be dominated |
| by a cold bb and therefore needs to become cold. Therefore, |
| its preds will no longer be region crossing. Any non-dominating |
| preds that were previously hot would also have become cold |
| in the caller for the same region. Any preds that were previously |
| region-crossing will be adjusted in fixup_partition_crossing. */ |
| FOR_EACH_EDGE (e, ei, bb->preds) |
| { |
| fixup_partition_crossing (e); |
| } |
| |
| /* Possibly need to make bb's successor edges region crossing, |
| or remove stale region crossing. */ |
| FOR_EACH_EDGE (e, ei, bb->succs) |
| { |
| /* We can't have fall-through edges across partition boundaries. |
| Note that force_nonfallthru will do any necessary partition |
| boundary fixup by calling fixup_partition_crossing itself. */ |
| if ((e->flags & EDGE_FALLTHRU) |
| && BB_PARTITION (bb) != BB_PARTITION (e->dest) |
| && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| force_nonfallthru (e); |
| else |
| fixup_partition_crossing (e); |
| } |
| } |
| |
| /* 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; |
| basic_block dest = e->dest; |
| |
| if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) |
| return NULL; |
| |
| if (dest == target) |
| return e; |
| |
| if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL) |
| { |
| df_set_bb_dirty (src); |
| fixup_partition_crossing (ret); |
| return ret; |
| } |
| |
| ret = redirect_branch_edge (e, target); |
| if (!ret) |
| return NULL; |
| |
| df_set_bb_dirty (src); |
| fixup_partition_crossing (ret); |
| return ret; |
| } |
| |
| /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */ |
| |
| void |
| emit_barrier_after_bb (basic_block bb) |
| { |
| rtx_barrier *barrier = emit_barrier_after (BB_END (bb)); |
| gcc_assert (current_ir_type () == IR_RTL_CFGRTL |
| || current_ir_type () == IR_RTL_CFGLAYOUT); |
| if (current_ir_type () == IR_RTL_CFGLAYOUT) |
| { |
| rtx_insn *insn = unlink_insn_chain (barrier, barrier); |
| |
| if (BB_FOOTER (bb)) |
| { |
| rtx_insn *footer_tail = BB_FOOTER (bb); |
| |
| while (NEXT_INSN (footer_tail)) |
| footer_tail = NEXT_INSN (footer_tail); |
| if (!BARRIER_P (footer_tail)) |
| { |
| SET_NEXT_INSN (footer_tail) = insn; |
| SET_PREV_INSN (insn) = footer_tail; |
| } |
| } |
| else |
| BB_FOOTER (bb) = insn; |
| } |
| } |
| |
| /* Like force_nonfallthru below, but additionally performs redirection |
| Used by redirect_edge_and_branch_force. JUMP_LABEL is used only |
| when redirecting to the EXIT_BLOCK, it is either ret_rtx or |
| simple_return_rtx, indicating which kind of returnjump to create. |
| It should be NULL otherwise. */ |
| |
| basic_block |
| force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label) |
| { |
| basic_block jump_block, new_bb = NULL, src = e->src; |
| rtx note; |
| edge new_edge; |
| int abnormal_edge_flags = 0; |
| bool asm_goto_edge = false; |
| int loc; |
| |
| /* 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_FOR_FN (cfun) |
| && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) |
| && any_condjump_p (BB_END (e->src)) |
| && 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 (as_a <rtx_jump_insn *> (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 = XINT (note, 0); |
| |
| b->probability = prob; |
| /* Update this to use GCOV_COMPUTE_SCALE. */ |
| 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. |
| This allows bb-reorder to make such edge non-fallthru. */ |
| gcc_assert (e->dest == target); |
| abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU; |
| e->flags &= EDGE_FALLTHRU; |
| } |
| else |
| { |
| gcc_assert (e->flags & EDGE_FALLTHRU); |
| if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
| { |
| /* 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_FOR_FN (cfun)); |
| |
| /* Make sure new block ends up in correct hot/cold section. */ |
| BB_COPY_PARTITION (bb, e->dest); |
| |
| /* 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_FOR_FN (cfun)->succs); |
| (tmp = ei_safe_edge (ei)); ) |
| { |
| if (tmp == e) |
| { |
| ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index); |
| found = true; |
| break; |
| } |
| else |
| ei_next (&ei); |
| } |
| |
| gcc_assert (found); |
| |
| vec_safe_push (bb->succs, e); |
| make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb, |
| EDGE_FALLTHRU); |
| } |
| } |
| |
| /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs |
| don't point to the target or fallthru label. */ |
| if (JUMP_P (BB_END (e->src)) |
| && target != EXIT_BLOCK_PTR_FOR_FN (cfun) |
| && (e->flags & EDGE_FALLTHRU) |
| && (note = extract_asm_operands (PATTERN (BB_END (e->src))))) |
| { |
| int i, n = ASM_OPERANDS_LABEL_LENGTH (note); |
| bool adjust_jump_target = false; |
| |
| for (i = 0; i < n; ++i) |
| { |
| if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest)) |
| { |
| LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))--; |
| XEXP (ASM_OPERANDS_LABEL (note, i), 0) = block_label (target); |
| LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))++; |
| adjust_jump_target = true; |
| } |
| if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (target)) |
| asm_goto_edge = true; |
| } |
| if (adjust_jump_target) |
| { |
| rtx_insn *insn = BB_END (e->src); |
| rtx note; |
| rtx_insn *old_label = BB_HEAD (e->dest); |
| rtx_insn *new_label = BB_HEAD (target); |
| |
| if (JUMP_LABEL (insn) == old_label) |
| { |
| JUMP_LABEL (insn) = new_label; |
| note = find_reg_note (insn, REG_LABEL_TARGET, new_label); |
| if (note) |
| remove_note (insn, note); |
| } |
| else |
| { |
| note = find_reg_note (insn, REG_LABEL_TARGET, old_label); |
| if (note) |
| remove_note (insn, note); |
| if (JUMP_LABEL (insn) != new_label |
| && !find_reg_note (insn, REG_LABEL_TARGET, new_label)) |
| add_reg_note (insn, REG_LABEL_TARGET, new_label); |
| } |
| while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label)) |
| != NULL_RTX) |
| XEXP (note, 0) = new_label; |
| } |
| } |
| |
| if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge) |
| { |
| rtx_insn *new_head; |
| gcov_type count = e->count; |
| int probability = e->probability; |
| /* 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. */ |
| rtx_jump_table_data *table; |
| if (tablejump_p (BB_END (e->src), NULL, &table)) |
| new_head = table; |
| else |
| new_head = BB_END (e->src); |
| new_head = NEXT_INSN (new_head); |
| |
| jump_block = create_basic_block (new_head, NULL, e->src); |
| jump_block->count = count; |
| jump_block->frequency = EDGE_FREQUENCY (e); |
| |
| /* Make sure new block ends up in correct hot/cold section. */ |
| |
| BB_COPY_PARTITION (jump_block, e->src); |
| |
| /* Wire edge in. */ |
| new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU); |
| new_edge->probability = probability; |
| new_edge->count = count; |
| |
| /* Redirect old edge. */ |
| redirect_edge_pred (e, jump_block); |
| e->probability = REG_BR_PROB_BASE; |
| |
| /* If e->src was previously region crossing, it no longer is |
| and the reg crossing note should be removed. */ |
| fixup_partition_crossing (new_edge); |
| |
| /* If asm goto has any label refs to target's label, |
| add also edge from asm goto bb to target. */ |
| if (asm_goto_edge) |
| { |
| new_edge->probability /= 2; |
| new_edge->count /= 2; |
| jump_block->count /= 2; |
| jump_block->frequency /= 2; |
| new_edge = make_edge (new_edge->src, target, |
| e->flags & ~EDGE_FALLTHRU); |
| new_edge->probability = probability - probability / 2; |
| new_edge->count = count - count / 2; |
| } |
| |
| new_bb = jump_block; |
| } |
| else |
| jump_block = e->src; |
| |
| loc = e->goto_locus; |
| e->flags &= ~EDGE_FALLTHRU; |
| if (target == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| { |
| if (jump_label == ret_rtx) |
| emit_jump_insn_after_setloc (targetm.gen_return (), |
| BB_END (jump_block), loc); |
| else |
| { |
| gcc_assert (jump_label == simple_return_rtx); |
| emit_jump_insn_after_setloc (targetm.gen_simple_return (), |
| BB_END (jump_block), loc); |
| } |
| set_return_jump_label (BB_END (jump_block)); |
| } |
| else |
| { |
| rtx_code_label *label = block_label (target); |
| emit_jump_insn_after_setloc (targetm.gen_jump (label), |
| BB_END (jump_block), loc); |
| JUMP_LABEL (BB_END (jump_block)) = label; |
| LABEL_NUSES (label)++; |
| } |
| |
| /* We might be in cfg layout mode, and if so, the following routine will |
| insert the barrier correctly. */ |
| emit_barrier_after_bb (jump_block); |
| redirect_edge_succ_nodup (e, target); |
| |
| if (abnormal_edge_flags) |
| make_edge (src, target, abnormal_edge_flags); |
| |
| df_mark_solutions_dirty (); |
| fixup_partition_crossing (e); |
| return new_bb; |
| } |
| |
| /* Edge E is assumed to be fallthru edge. Emit needed jump instruction |
| (and possibly create new basic block) to make edge non-fallthru. |
| Return newly created BB or NULL if none. */ |
| |
| static basic_block |
| rtl_force_nonfallthru (edge e) |
| { |
| return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX); |
| } |
| |
| /* Redirect edge even at the expense of creating new jump insn or |
| basic block. Return new basic block if created, NULL otherwise. |
| Conversion must be possible. */ |
| |
| static basic_block |
| rtl_redirect_edge_and_branch_force (edge e, basic_block target) |
| { |
| if (redirect_edge_and_branch (e, target) |
| || e->dest == target) |
| return NULL; |
| |
| /* In case the edge redirection failed, try to force it to be non-fallthru |
| and redirect newly created simplejump. */ |
| df_set_bb_dirty (e->src); |
| return force_nonfallthru_and_redirect (e, target, NULL_RTX); |
| } |
| |
| /* 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. */ |
| |
| static void |
| rtl_tidy_fallthru_edge (edge e) |
| { |
| rtx_insn *q; |
| basic_block b = e->src, c = b->next_bb; |
| |
| /* ??? In a late-running flow pass, other folks may have deleted basic |
| blocks by nopping out blocks, leaving multiple BARRIERs between here |
| and the target label. They ought to be chastised and fixed. |
| |
| We can also wind up with a sequence of undeletable labels between |
| one block and the next. |
| |
| 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 (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 = BB_END (b); |
| if (JUMP_P (q) |
| && onlyjump_p (q) |
| && (any_uncondjump_p (q) |
| || single_succ_p (b))) |
| { |
| rtx_insn *label; |
| rtx_jump_table_data *table; |
| |
| if (tablejump_p (q, &label, &table)) |
| { |
| /* The label is likely mentioned in some instruction before |
| the tablejump and might not be DCEd, so turn it into |
| a note instead and move before the tablejump that is going to |
| be deleted. */ |
| const char *name = LABEL_NAME (label); |
| PUT_CODE (label, NOTE); |
| NOTE_KIND (label) = NOTE_INSN_DELETED_LABEL; |
| NOTE_DELETED_LABEL_NAME (label) = name; |
| reorder_insns (label, label, PREV_INSN (q)); |
| delete_insn (table); |
| } |
| |
| /* If this was a conditional jump, we need to also delete |
| the insn that set cc0. */ |
| if (HAVE_cc0 && any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q))) |
| q = PREV_INSN (q); |
| |
| q = PREV_INSN (q); |
| } |
| /* Unconditional jumps with side-effects (i.e. which we can't just delete |
| together with the barrier) should never have a fallthru edge. */ |
| else if (JUMP_P (q) && any_uncondjump_p (q)) |
| return; |
| |
| /* Selectively unlink the sequence. */ |
| if (q != PREV_INSN (BB_HEAD (c))) |
| delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false); |
| |
| e->flags |= EDGE_FALLTHRU; |
| } |
| |
| /* 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; |
| } |
| |
| /* Locate the last bb in the same partition as START_BB. */ |
| |
| static basic_block |
| last_bb_in_partition (basic_block start_bb) |
| { |
| basic_block bb; |
| FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) |
| { |
| if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb)) |
| return bb; |
| } |
| /* Return bb before the exit block. */ |
| return bb->prev_bb; |
| } |
| |
| /* Split a (typically critical) edge. Return the new block. |
| The edge must not be abnormal. |
| |
| ??? The code generally expects to be called on critical edges. |
| The case of a block ending in an unconditional jump to a |
| block with multiple predecessors is not handled optimally. */ |
| |
| static basic_block |
| rtl_split_edge (edge edge_in) |
| { |
| basic_block bb, new_bb; |
| rtx_insn *before; |
| |
| /* Abnormal edges cannot be split. */ |
| 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 = find_fallthru_edge (edge_in->dest->preds); |
| |
| if (e) |
| force_nonfallthru (e); |
| } |
| |
| /* Create the basic block note. */ |
| if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| before = BB_HEAD (edge_in->dest); |
| else |
| before = NULL; |
| |
| /* If this is a fall through edge to the exit block, the blocks might be |
| not adjacent, and the right place is after the source. */ |
| if ((edge_in->flags & EDGE_FALLTHRU) |
| && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| { |
| before = NEXT_INSN (BB_END (edge_in->src)); |
| bb = create_basic_block (before, NULL, edge_in->src); |
| BB_COPY_PARTITION (bb, edge_in->src); |
| } |
| else |
| { |
| if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
| { |
| bb = create_basic_block (before, NULL, edge_in->dest->prev_bb); |
| BB_COPY_PARTITION (bb, edge_in->dest); |
| } |
| else |
| { |
| basic_block after = edge_in->dest->prev_bb; |
| /* If this is post-bb reordering, and the edge crosses a partition |
| boundary, the new block needs to be inserted in the bb chain |
| at the end of the src partition (since we put the new bb into |
| that partition, see below). Otherwise we may end up creating |
| an extra partition crossing in the chain, which is illegal. |
| It can't go after the src, because src may have a fall-through |
| to a different block. */ |
| if (crtl->bb_reorder_complete |
| && (edge_in->flags & EDGE_CROSSING)) |
| { |
| after = last_bb_in_partition (edge_in->src); |
| before = get_last_bb_insn (after); |
| /* The instruction following the last bb in partition should |
| be a barrier, since it cannot end in a fall-through. */ |
| gcc_checking_assert (BARRIER_P (before)); |
| before = NEXT_INSN (before); |
| } |
| bb = create_basic_block (before, NULL, after); |
| /* Put the split bb into the src partition, to avoid creating |
| a situation where a cold bb dominates a hot bb, in the case |
| where src is cold and dest is hot. The src will dominate |
| the new bb (whereas it might not have dominated dest). */ |
| BB_COPY_PARTITION (bb, edge_in->src); |
| } |
| } |
| |
| make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU); |
| |
| /* Can't allow a region crossing edge to be fallthrough. */ |
| if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest) |
| && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| { |
| new_bb = force_nonfallthru (single_succ_edge (bb)); |
| gcc_assert (!new_bb); |
| } |
| |
| /* For non-fallthru edges, we must adjust the predecessor's |
| jump instruction to target our new block. */ |
| if ((edge_in->flags & EDGE_FALLTHRU) == 0) |
| { |
| edge redirected = redirect_edge_and_branch (edge_in, bb); |
| gcc_assert (redirected); |
| } |
| else |
| { |
| if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
| { |
| /* For asm goto even splitting of fallthru edge might |
| need insn patching, as other labels might point to the |
| old label. */ |
| rtx_insn *last = BB_END (edge_in->src); |
| if (last |
| && JUMP_P (last) |
| && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) |
| && (extract_asm_operands (PATTERN (last)) |
| || JUMP_LABEL (last) == before) |
| && patch_jump_insn (last, before, bb)) |
| df_set_bb_dirty (edge_in->src); |
| } |
| redirect_edge_succ (edge_in, bb); |
| } |
| |
| return bb; |
| } |
| |
| /* Queue instructions for insertion on an edge between two basic blocks. |
| The new instructions and basic blocks (if any) will not appear in the |
| CFG until commit_edge_insertions is called. */ |
| |
| void |
| 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. */ |
| gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))); |
| |
| if (e->insns.r == NULL_RTX) |
| start_sequence (); |
| else |
| push_to_sequence (e->insns.r); |
| |
| emit_insn (pattern); |
| |
| e->insns.r = get_insns (); |
| end_sequence (); |
| } |
| |
| /* Update the CFG for the instructions queued on edge E. */ |
| |
| void |
| commit_one_edge_insertion (edge e) |
| { |
| rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last; |
| basic_block bb; |
| |
| /* Pull the insns off the edge now since the edge might go away. */ |
| insns = e->insns.r; |
| e->insns.r = NULL; |
| |
| /* Figure out where to put these insns. If the destination has |
| one predecessor, insert there. Except for the exit block. */ |
| if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| { |
| 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 (bb); |
| if (LABEL_P (tmp)) |
| tmp = NEXT_INSN (tmp); |
| if (NOTE_INSN_BASIC_BLOCK_P (tmp)) |
| tmp = NEXT_INSN (tmp); |
| if (tmp == BB_HEAD (bb)) |
| before = tmp; |
| else if (tmp) |
| after = PREV_INSN (tmp); |
| else |
| after = get_last_insn (); |
| } |
| |
| /* If the source has one successor and the edge is not abnormal, |
| insert there. Except for the entry block. |
| Don't do this if the predecessor ends in a jump other than |
| unconditional simple jump. E.g. for asm goto that points all |
| its labels at the fallthru basic block, we can't insert instructions |
| before the asm goto, as the asm goto can have various of side effects, |
| and can't emit instructions after the asm goto, as it must end |
| the basic block. */ |
| else if ((e->flags & EDGE_ABNORMAL) == 0 |
| && single_succ_p (e->src) |
| && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
| && (!JUMP_P (BB_END (e->src)) |
| || simplejump_p (BB_END (e->src)))) |
| { |
| bb = e->src; |
| |
| /* It is possible to have a non-simple jump here. Consider a target |
| where some forms of unconditional jumps clobber a register. This |
| happens on the fr30 for example. |
| |
| We know this block has a single successor, so we can just emit |
| the queued insns before the jump. */ |
| if (JUMP_P (BB_END (bb))) |
| before = BB_END (bb); |
| else |
| { |
| /* We'd better be fallthru, or we've lost track of what's what. */ |
| gcc_assert (e->flags & EDGE_FALLTHRU); |
| |
| after = BB_END (bb); |
| } |
| } |
| |
| /* Otherwise we must split the edge. */ |
| else |
| { |
| bb = split_edge (e); |
| |
| /* If E crossed a partition boundary, we needed to make bb end in |
| a region-crossing jump, even though it was originally fallthru. */ |
| if (JUMP_P (BB_END (bb))) |
| before = BB_END (bb); |
| else |
| after = BB_END (bb); |
| } |
| |
| /* Now that we've found the spot, do the insertion. */ |
| if (before) |
| { |
| emit_insn_before_noloc (insns, before, bb); |
| last = prev_nonnote_insn (before); |
| } |
| else |
| last = emit_insn_after_noloc (insns, after, bb); |
| |
| if (returnjump_p (last)) |
| { |
| /* ??? Remove all outgoing edges from BB and add one for EXIT. |
| This is not currently a problem because this only happens |
| for the (single) epilogue, which already has a fallthru edge |
| to EXIT. */ |
| |
| e = single_succ_edge (bb); |
| gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) |
| && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU)); |
| |
| e->flags &= ~EDGE_FALLTHRU; |
| emit_barrier_after (last); |
| |
| if (before) |
| delete_insn (before); |
| } |
| else |
| gcc_assert (!JUMP_P (last)); |
| } |
| |
| /* Update the CFG for all queued instructions. */ |
| |
| void |
| commit_edge_insertions (void) |
| { |
| basic_block bb; |
| |
| /* Optimization passes that invoke this routine can cause hot blocks |
| previously reached by both hot and cold blocks to become dominated only |
| by cold blocks. This will cause the verification below to fail, |
| and lead to now cold code in the hot section. In some cases this |
| may only be visible after newly unreachable blocks are deleted, |
| which will be done by fixup_partitions. */ |
| fixup_partitions (); |
| |
| checking_verify_flow_info (); |
| |
| FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), |
| EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) |
| { |
| edge e; |
| edge_iterator ei; |
| |
| FOR_EACH_EDGE (e, ei, bb->succs) |
| if (e->insns.r) |
| commit_one_edge_insertion (e); |
| } |
| } |
| |
| |
| /* Print out RTL-specific basic block information (live information |
| at start and end with TDF_DETAILS). FLAGS are the TDF_* masks |
| documented in dumpfile.h. */ |
| |
| static void |
| rtl_dump_bb (FILE *outf, basic_block bb, int indent, int flags) |
| { |
| rtx_insn *insn; |
| rtx_insn *last; |
| char *s_indent; |
| |
| s_indent = (char *) alloca ((size_t) indent + 1); |
| memset (s_indent, ' ', (size_t) indent); |
| s_indent[indent] = '\0'; |
| |
| if (df && (flags & TDF_DETAILS)) |
| { |
| df_dump_top (bb, outf); |
| putc ('\n', outf); |
| } |
| |
| if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK) |
| for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last; |
| insn = NEXT_INSN (insn)) |
| { |
| if (flags & TDF_DETAILS) |
| df_dump_insn_top (insn, outf); |
| if (! (flags & TDF_SLIM)) |
| print_rtl_single (outf, insn); |
| else |
| dump_insn_slim (outf, insn); |
| if (flags & TDF_DETAILS) |
| df_dump_insn_bottom (insn, outf); |
| } |
| |
| if (df && (flags & TDF_DETAILS)) |
| { |
| df_dump_bottom (bb, outf); |
| putc ('\n', outf); |
| } |
| |
| } |
| |
| /* Like dump_function_to_file, but for RTL. Print out dataflow information |
| for the start of each basic block. FLAGS are the TDF_* masks documented |
| in dumpfile.h. */ |
| |
| void |
| print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, int flags) |
| { |
| const rtx_insn *tmp_rtx; |
| if (rtx_first == 0) |
| fprintf (outf, "(nil)\n"); |
| else |
| { |
| enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB }; |
| int max_uid = get_max_uid (); |
| basic_block *start = XCNEWVEC (basic_block, max_uid); |
| basic_block *end = XCNEWVEC (basic_block, max_uid); |
| enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid); |
| basic_block bb; |
| |
| /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most |
| insns, but the CFG is not maintained so the basic block info |
| is not reliable. Therefore it's omitted from the dumps. */ |
| if (! (cfun->curr_properties & PROP_cfg)) |
| flags &= ~TDF_BLOCKS; |
| |
| if (df) |
| df_dump_start (outf); |
| |
| if (flags & TDF_BLOCKS) |
| { |
| FOR_EACH_BB_REVERSE_FN (bb, cfun) |
| { |
| rtx_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; |
| |
| if (in_bb_p[INSN_UID (x)] == NOT_IN_BB) |
| state = IN_ONE_BB; |
| in_bb_p[INSN_UID (x)] = state; |
| |
| if (x == BB_END (bb)) |
| break; |
| } |
| } |
| } |
| |
| for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx)) |
| { |
| if (flags & TDF_BLOCKS) |
| { |
| bb = start[INSN_UID (tmp_rtx)]; |
| if (bb != NULL) |
| { |
| dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, true, false); |
| if (df && (flags & TDF_DETAILS)) |
| df_dump_top (bb, outf); |
| } |
| |
| if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB |
| && !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"); |
| } |
| |
| if (flags & TDF_DETAILS) |
| df_dump_insn_top (tmp_rtx, outf); |
| if (! (flags & TDF_SLIM)) |
| print_rtl_single (outf, tmp_rtx); |
| else |
| dump_insn_slim (outf, tmp_rtx); |
| if (flags & TDF_DETAILS) |
| df_dump_insn_bottom (tmp_rtx, outf); |
| |
| if (flags & TDF_BLOCKS) |
| { |
| bb = end[INSN_UID (tmp_rtx)]; |
| if (bb != NULL) |
| { |
| dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, false, true); |
| if (df && (flags & TDF_DETAILS)) |
| df_dump_bottom (bb, outf); |
| putc ('\n', outf); |
| } |
| } |
| } |
| |
| free (start); |
| free (end); |
| free (in_bb_p); |
| } |
| } |
| |
| /* Update the branch probability of BB if a REG_BR_PROB is present. */ |
| |
| void |
| update_br_prob_note (basic_block bb) |
| { |
| rtx note; |
| if (!JUMP_P (BB_END (bb))) |
| return; |
| note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX); |
| if (!note || XINT (note, 0) == BRANCH_EDGE (bb)->probability) |
| return; |
| XINT (note, 0) = BRANCH_EDGE (bb)->probability; |
| } |
| |
| /* Get the last insn associated with block BB (that includes barriers and |
| tablejumps after BB). */ |
| rtx_insn * |
| get_last_bb_insn (basic_block bb) |
| { |
| rtx_jump_table_data *table; |
| rtx_insn *tmp; |
| rtx_insn *end = BB_END (bb); |
| |
| /* Include any jump table following the basic block. */ |
| if (tablejump_p (end, NULL, &table)) |
| end = table; |
| |
| /* Include any barriers that may follow the basic block. */ |
| tmp = next_nonnote_insn_bb (end); |
| while (tmp && BARRIER_P (tmp)) |
| { |
| end = tmp; |
| tmp = next_nonnote_insn_bb (end); |
| } |
| |
| return end; |
| } |
| |
| /* Sanity check partition hotness to ensure that basic blocks in |
| Â the cold partition don't dominate basic blocks in the hot partition. |
| If FLAG_ONLY is true, report violations as errors. Otherwise |
| re-mark the dominated blocks as cold, since this is run after |
| cfg optimizations that may make hot blocks previously reached |
| by both hot and cold blocks now only reachable along cold paths. */ |
| |
| static vec<basic_block> |
| find_partition_fixes (bool flag_only) |
| { |
| basic_block bb; |
| vec<basic_block> bbs_in_cold_partition = vNULL; |
| vec<basic_block> bbs_to_fix = vNULL; |
| |
| /* Callers check this. */ |
| gcc_checking_assert (crtl->has_bb_partition); |
| |
| FOR_EACH_BB_FN (bb, cfun) |
| if ((BB_PARTITION (bb) == BB_COLD_PARTITION)) |
| bbs_in_cold_partition.safe_push (bb); |
| |
| if (bbs_in_cold_partition.is_empty ()) |
| return vNULL; |
| |
| bool dom_calculated_here = !dom_info_available_p (CDI_DOMINATORS); |
| |
| if (dom_calculated_here) |
| calculate_dominance_info (CDI_DOMINATORS); |
| |
| while (! bbs_in_cold_partition.is_empty ()) |
| { |
| bb = bbs_in_cold_partition.pop (); |
| /* Any blocks dominated by a block in the cold section |
| must also be cold. */ |
| basic_block son; |
| for (son = first_dom_son (CDI_DOMINATORS, bb); |
| son; |
| son = next_dom_son (CDI_DOMINATORS, son)) |
| { |
| /* If son is not yet cold, then mark it cold here and |
| enqueue it for further processing. */ |
| if ((BB_PARTITION (son) != BB_COLD_PARTITION)) |
| { |
| if (flag_only) |
| error ("non-cold basic block %d dominated " |
| "by a block in the cold partition (%d)", son->index, bb->index); |
| else |
| BB_SET_PARTITION (son, BB_COLD_PARTITION); |
| bbs_to_fix.safe_push (son); |
| bbs_in_cold_partition.safe_push (son); |
| } |
| } |
| } |
| |
| if (dom_calculated_here) |
| free_dominance_info (CDI_DOMINATORS); |
| |
| return bbs_to_fix; |
| } |
| |
| /* Perform cleanup on the hot/cold bb partitioning after optimization |
| passes that modify the cfg. */ |
| |
| void |
| fixup_partitions (void) |
| { |
| basic_block bb; |
| |
| if (!crtl->has_bb_partition) |
| return; |
| |
| /* Delete any blocks that became unreachable and weren't |
| already cleaned up, for example during edge forwarding |
| and convert_jumps_to_returns. This will expose more |
| opportunities for fixing the partition boundaries here. |
| Also, the calculation of the dominance graph during verification |
| will assert if there are unreachable nodes. */ |
| delete_unreachable_blocks (); |
| |
| /* If there are partitions, do a sanity check on them: A basic block in |
| Â a cold partition cannot dominate a basic block in a hot partition. |
| Fixup any that now violate this requirement, as a result of edge |
| forwarding and unreachable block deletion. Â */ |
| vec<basic_block> bbs_to_fix = find_partition_fixes (false); |
| |
| /* Do the partition fixup after all necessary blocks have been converted to |
| cold, so that we only update the region crossings the minimum number of |
| places, which can require forcing edges to be non fallthru. */ |
| while (! bbs_to_fix.is_empty ()) |
| { |
| bb = bbs_to_fix.pop (); |
| fixup_new_cold_bb (bb); |
| } |
| } |
| |
| /* Verify, in the basic block chain, that there is at most one switch |
| between hot/cold partitions. This condition will not be true until |
| after reorder_basic_blocks is called. */ |
| |
| static int |
| verify_hot_cold_block_grouping (void) |
| { |
| basic_block bb; |
| int err = 0; |
| bool switched_sections = false; |
| int current_partition = BB_UNPARTITIONED; |
| |
| /* Even after bb reordering is complete, we go into cfglayout mode |
| again (in compgoto). Ensure we don't call this before going back |
| into linearized RTL when any layout fixes would have been committed. */ |
| if (!crtl->bb_reorder_complete |
| || current_ir_type () != IR_RTL_CFGRTL) |
| return err; |
| |
| FOR_EACH_BB_FN (bb, cfun) |
| { |
| if (current_partition != BB_UNPARTITIONED |
| && BB_PARTITION (bb) != current_partition) |
| { |
| if (switched_sections) |
| { |
| error ("multiple hot/cold transitions found (bb %i)", |
| bb->index); |
| err = 1; |
| } |
| else |
| switched_sections = true; |
| |
| if (!crtl->has_bb_partition) |
| error ("partition found but function partition flag not set"); |
| } |
| current_partition = BB_PARTITION (bb); |
| } |
| |
| return err; |
| } |
| |
| |
| /* Perform several checks on the edges out of each block, such as |
| the consistency of the branch probabilities, the correctness |
| of hot/cold partition crossing edges, and the number of expected |
| successor edges. Also verify that the dominance relationship |
| between hot/cold blocks is sane. */ |
| |
| static int |
| rtl_verify_edges (void) |
| { |
| int err = 0; |
| basic_block bb; |
| |
| FOR_EACH_BB_REVERSE_FN (bb, cfun) |
| { |
| int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0; |
| int n_eh = 0, n_abnormal = 0; |
| edge e, fallthru = NULL; |
| edge_iterator ei; |
| rtx note; |
| bool has_crossing_edge = false; |
| |
| if (JUMP_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 (XINT (note, 0) != BRANCH_EDGE (bb)->probability |
| && profile_status_for_fn (cfun) != PROFILE_ABSENT) |
| { |
| error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i", |
| XINT (note, 0), BRANCH_EDGE (bb)->probability); |
| err = 1; |
| } |
| } |
| |
| FOR_EACH_EDGE (e, ei, bb->succs) |
| { |
| bool is_crossing; |
| |
| if (e->flags & EDGE_FALLTHRU) |
| n_fallthru++, fallthru = e; |
| |
| is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest) |
| && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
| && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)); |
| has_crossing_edge |= is_crossing; |
| if (e->flags & EDGE_CROSSING) |
| { |
| if (!is_crossing) |
| { |
| error ("EDGE_CROSSING incorrectly set across same section"); |
| err = 1; |
| } |
| if (e->flags & EDGE_FALLTHRU) |
| { |
| error ("fallthru edge crosses section boundary in bb %i", |
| e->src->index); |
| err = 1; |
| } |
| if (e->flags & EDGE_EH) |
| { |
| error ("EH edge crosses section boundary in bb %i", |
| e->src->index); |
| err = 1; |
| } |
| if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb))) |
| { |
| error ("No region crossing jump at section boundary in bb %i", |
| bb->index); |
| err = 1; |
| } |
| } |
| else if (is_crossing) |
| { |
| error ("EDGE_CROSSING missing across section boundary"); |
| err = 1; |
| } |
| |
| if ((e->flags & ~(EDGE_DFS_BACK |
| | EDGE_CAN_FALLTHRU |
| | EDGE_IRREDUCIBLE_LOOP |
| | EDGE_LOOP_EXIT |
| | EDGE_CROSSING |
| | EDGE_PRESERVE)) == 0) |
| n_branch++; |
| |
| if (e->flags & EDGE_ABNORMAL_CALL) |
| n_abnormal_call++; |
| |
| if (e->flags & EDGE_SIBCALL) |
| n_sibcall++; |
| |
| if (e->flags & EDGE_EH) |
| n_eh++; |
| |
| if (e->flags & EDGE_ABNORMAL) |
| n_abnormal++; |
| } |
| |
| if (!has_crossing_edge |
| && JUMP_P (BB_END (bb)) |
| && CROSSING_JUMP_P (BB_END (bb))) |
| { |
| print_rtl_with_bb (stderr, get_insns (), TDF_RTL | TDF_BLOCKS | TDF_DETAILS); |
| error ("Region crossing jump across same section in bb %i", |
| bb->index); |
| err = 1; |
| } |
| |
| if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX)) |
| { |
| error ("missing REG_EH_REGION note at the end of bb %i", bb->index); |
| err = 1; |
| } |
| if (n_eh > 1) |
| { |
| error ("too many exception handling edges in bb %i", bb->index); |
| err = 1; |
| } |
| if (n_branch |
| && (!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 (bb))) |
| { |
| error ("fallthru edge after unconditional jump in bb %i", bb->index); |
| err = 1; |
| } |
| if (n_branch != 1 && any_uncondjump_p (BB_END (bb))) |
| { |
| error ("wrong number of branch edges after unconditional jump" |
| " in bb %i", bb->index); |
| err = 1; |
| } |
| 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" |
| " in bb %i", bb->index); |
| err = 1; |
| } |
| if (n_abnormal_call && !CALL_P (BB_END (bb))) |
| { |
| error ("abnormal call edges for non-call insn in bb %i", bb->index); |
| err = 1; |
| } |
| if (n_sibcall && !CALL_P (BB_END (bb))) |
| { |
| error ("sibcall edges for non-call insn in bb %i", bb->index); |
| err = 1; |
| } |
| if (n_abnormal > n_eh |
| && !(CALL_P (BB_END (bb)) |
| && n_abnormal == n_abnormal_call + n_sibcall) |
| && (!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 there are partitions, do a sanity check on them: A basic block in |
| Â a cold partition cannot dominate a basic block in a hot partition. Â */ |
| if (crtl->has_bb_partition && !err) |
| { |
| vec<basic_block> bbs_to_fix = find_partition_fixes (true); |
| err = !bbs_to_fix.is_empty (); |
| } |
| |
| /* Clean up. */ |
| return err; |
| } |
| |
| /* Checks on the instructions within blocks. Currently checks that each |
| block starts with a basic block note, and that basic block notes and |
| control flow jumps are not found in the middle of the block. */ |
| |
| static int |
| rtl_verify_bb_insns (void) |
| { |
| rtx_insn *x; |
| int err = 0; |
| basic_block bb; |
| |
| FOR_EACH_BB_REVERSE_FN (bb, cfun) |
| { |
| /* Now check the header of basic |
| block. It ought to contain optional CODE_LABEL followed |
| by NOTE_BASIC_BLOCK. */ |
| x = BB_HEAD (bb); |
| if (LABEL_P (x)) |
| { |
| if (BB_END (bb) == x) |
| { |
| error ("NOTE_INSN_BASIC_BLOCK is missing for block %d", |
| bb->index); |
| err = 1; |
| } |
| |
| x = NEXT_INSN (x); |
| } |
| |
| if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb) |
| { |
| error ("NOTE_INSN_BASIC_BLOCK is missing for block %d", |
| bb->index); |
| err = 1; |
| } |
| |
| if (BB_END (bb) == x) |
| /* Do checks for empty blocks here. */ |
| ; |
| else |
| for (x = NEXT_INSN (x); x; x = NEXT_INSN (x)) |
| { |
| if (NOTE_INSN_BASIC_BLOCK_P (x)) |
| { |
| error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d", |
| INSN_UID (x), bb->index); |
| err = 1; |
| } |
| |
| if (x == BB_END (bb)) |
| break; |
| |
| if (control_flow_insn_p (x)) |
| { |
| error ("in basic block %d:", bb->index); |
| fatal_insn ("flow control insn inside a basic block", x); |
| } |
| } |
| } |
| |
| /* Clean up. */ |
| return err; |
| } |
| |
| /* Verify that block pointers for instructions in basic blocks, headers and |
| footers are set appropriately. */ |
| |
| static int |
| rtl_verify_bb_pointers (void) |
| { |
| int err = 0; |
| basic_block bb; |
| |
| /* Check the general integrity of the basic blocks. */ |
| FOR_EACH_BB_REVERSE_FN (bb, cfun) |
| { |
| rtx_insn *insn; |
| |
| if (!(bb->flags & BB_RTL)) |
| { |
| error ("BB_RTL flag not set for block %d", bb->index); |
| err = 1; |
| } |
| |
| FOR_BB_INSNS (bb, insn) |
| if (BLOCK_FOR_INSN (insn) != bb) |
| { |
| error ("insn %d basic block pointer is %d, should be %d", |
| INSN_UID (insn), |
| BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0, |
| bb->index); |
| err = 1; |
| } |
| |
| for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn)) |
| if (!BARRIER_P (insn) |
| && BLOCK_FOR_INSN (insn) != NULL) |
| { |
| error ("insn %d in header of bb %d has non-NULL basic block", |
| INSN_UID (insn), bb->index); |
| err = 1; |
| } |
| for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn)) |
| if (!BARRIER_P (insn) |
| && BLOCK_FOR_INSN (insn) != NULL) |
| { |
| error ("insn %d in footer of bb %d has non-NULL basic block", |
| INSN_UID (insn), bb->index); |
| err = 1; |
| } |
| } |
| |
| /* Clean up. */ |
| return err; |
| } |
| |
| /* Verify the CFG and RTL consistency common for both underlying RTL and |
| cfglayout RTL. |
| |
| Currently it does following checks: |
| |
| - overlapping of basic blocks |
| - insns with wrong BLOCK_FOR_INSN pointers |
| - 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 |
| - verify that no fall_thru edge crosses hot/cold partition boundaries |
| - verify that there are no pending RTL branch predictions |
| - verify that hot blocks are not dominated by cold blocks |
| |
| In future it can be extended check a lot of other stuff as well |
| (reachability of basic blocks, life information, etc. etc.). */ |
| |
| static int |
| rtl_verify_flow_info_1 (void) |
| { |
| int err = 0; |
| |
| err |= rtl_verify_bb_pointers (); |
| |
| err |= rtl_verify_bb_insns (); |
| |
| err |= rtl_verify_edges (); |
| |
| return err; |
| } |
| |
| /* Walk the instruction chain and verify that bb head/end pointers |
| are correct, and that instructions are in exactly one bb and have |
| correct block pointers. */ |
| |
| static int |
| rtl_verify_bb_insn_chain (void) |
| { |
| basic_block bb; |
| int err = 0; |
| rtx_insn *x; |
| rtx_insn *last_head = get_last_insn (); |
| basic_block *bb_info; |
| const int max_uid = get_max_uid (); |
| |
| bb_info = XCNEWVEC (basic_block, max_uid); |
| |
| FOR_EACH_BB_REVERSE_FN (bb, cfun) |
| { |
| rtx_insn *head = BB_HEAD (bb); |
| rtx_insn *end = BB_END (bb); |
| |
| for (x = last_head; x != NULL_RTX; x = PREV_INSN (x)) |
| { |
| /* Verify the end of the basic block is in the INSN chain. */ |
| if (x == end) |
| break; |
| |
| /* And that the code outside of basic blocks has NULL bb field. */ |
| if (!BARRIER_P (x) |
| && BLOCK_FOR_INSN (x) != NULL) |
| { |
| error ("insn %d outside of basic blocks has non-NULL bb field", |
| INSN_UID (x)); |
| err = 1; |
| } |
| } |
| |
| if (!x) |
| { |
| error ("end insn %d for block %d not found in the insn stream", |
| INSN_UID (end), bb->index); |
| err = 1; |
| } |
| |
| /* Work backwards from the end to the head of the basic block |
| to verify the head is in the RTL chain. */ |
| for (; x != NULL_RTX; x = PREV_INSN (x)) |
| { |
| /* While walking over the insn chain, verify insns appear |
| in only one basic block. */ |
| if (bb_info[INSN_UID (x)] != NULL) |
| { |
| error ("insn %d is in multiple basic blocks (%d and %d)", |
| INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index); |
| err = 1; |
| } |
| |
| bb_info[INSN_UID (x)] = bb; |
| |
| if (x == head) |
| break; |
| } |
| if (!x) |
| { |
| error ("head insn %d for block %d not found in the insn stream", |
| INSN_UID (head), bb->index); |
| err = 1; |
| } |
| |
| last_head = PREV_INSN (x); |
| } |
| |
| for (x = last_head; x != NULL_RTX; x = PREV_INSN (x)) |
| { |
| /* Check that the code before the first basic block has NULL |
| bb field. */ |
| if (!BARRIER_P (x) |
| && BLOCK_FOR_INSN (x) != NULL) |
| { |
| error ("insn %d outside of basic blocks has non-NULL bb field", |
| INSN_UID (x)); |
| err = 1; |
| } |
| } |
| free (bb_info); |
| |
| return err; |
| } |
| |
| /* Verify that fallthru edges point to adjacent blocks in layout order and |
| that barriers exist after non-fallthru blocks. */ |
| |
| static int |
| rtl_verify_fallthru (void) |
| { |
| basic_block bb; |
| int err = 0; |
| |
| FOR_EACH_BB_REVERSE_FN (bb, cfun) |
| { |
| edge e; |
| |
| e = find_fallthru_edge (bb->succs); |
| if (!e) |
| { |
| rtx_insn *insn; |
| |
| /* Ensure existence of barrier in BB with no fallthru edges. */ |
| for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn)) |
| { |
| if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn)) |
| { |
| error ("missing barrier after block %i", bb->index); |
| err = 1; |
| break; |
| } |
| if (BARRIER_P (insn)) |
| break; |
| } |
| } |
| else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
| && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) |
| { |
| rtx_insn *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) || INSN_P (insn)) |
| { |
| 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; |
| } |
| } |
| } |
| |
| return err; |
| } |
| |
| /* Verify that blocks are laid out in consecutive order. While walking the |
| instructions, verify that all expected instructions are inside the basic |
| blocks, and that all returns are followed by barriers. */ |
| |
| static int |
| rtl_verify_bb_layout (void) |
| { |
| basic_block bb; |
| int err = 0; |
| rtx_insn *x; |
| int num_bb_notes; |
| rtx_insn * const rtx_first = get_insns (); |
| basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL; |
| |
| num_bb_notes = 0; |
| last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun); |
| |
| for (x = rtx_first; x; x = NEXT_INSN (x)) |
| { |
| if (NOTE_INSN_BASIC_BLOCK_P (x)) |
| { |
| bb = NOTE_BASIC_BLOCK (x); |
| |
| num_bb_notes++; |
| if (bb != last_bb_seen->next_bb) |
| internal_error ("basic blocks not laid down consecutively"); |
| |
| curr_bb = last_bb_seen = bb; |
| } |
| |
| if (!curr_bb) |
| { |
| switch (GET_CODE (x)) |
| { |
| case BARRIER: |
| case NOTE: |
| break; |
| |
| case CODE_LABEL: |
| /* An ADDR_VEC is placed outside any basic block. */ |
| if (NEXT_INSN (x) |
| && JUMP_TABLE_DATA_P (NEXT_INSN (x))) |
| x = NEXT_INSN (x); |
| |
| /* But in any case, non-deletable labels can appear anywhere. */ |
| break; |
| |
| default: |
| fatal_insn ("insn outside basic block", x); |
| } |
| } |
| |
| if (JUMP_P (x) |
| && returnjump_p (x) && ! condjump_p (x) |
| && ! (next_nonnote_insn (x) && BARRIER_P (next_nonnote_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_for_fn (cfun) - NUM_FIXED_BLOCKS) |
| internal_error |
| ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)", |
| num_bb_notes, n_basic_blocks_for_fn (cfun)); |
| |
| return err; |
| } |
| |
| /* Verify the CFG and RTL consistency common for both underlying RTL and |
| cfglayout RTL, plus consistency checks specific to linearized RTL mode. |
| |
| Currently it does following checks: |
| - all checks of rtl_verify_flow_info_1 |
| - test head/end pointers |
| - check that blocks are laid out in consecutive order |
| - 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 |
| - verify that there is a single hot/cold partition boundary after bbro */ |
| |
| static int |
| rtl_verify_flow_info (void) |
| { |
| int err = 0; |
| |
| err |= rtl_verify_flow_info_1 (); |
| |
| err |= rtl_verify_bb_insn_chain (); |
| |
| err |= rtl_verify_fallthru (); |
| |
| err |= rtl_verify_bb_layout (); |
| |
| err |= verify_hot_cold_block_grouping (); |
| |
| return err; |
| } |
| |
| /* Assume that the preceding pass has possibly eliminated jump instructions |
| or converted the unconditional jumps. Eliminate the edges from CFG. |
| Return true if any edges are eliminated. */ |
| |
| bool |
| purge_dead_edges (basic_block bb) |
| { |
| edge e; |
| rtx_insn *insn = BB_END (bb); |
| rtx note; |
| bool purged = false; |
| bool found; |
| edge_iterator ei; |
| |
| if (DEBUG_INSN_P (insn) && insn != BB_HEAD (bb)) |
| do |
| insn = PREV_INSN (insn); |
| while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb)); |
| |
| /* If this instruction cannot trap, remove REG_EH_REGION notes. */ |
| if (NONJUMP_INSN_P (insn) |
| && (note = find_reg_note (insn, REG_EH_REGION, NULL))) |
| { |
| rtx eqnote; |
| |
| if (! may_trap_p (PATTERN (insn)) |
| || ((eqnote = find_reg_equal_equiv_note (insn)) |
| && ! may_trap_p (XEXP (eqnote, 0)))) |
| remove_note (insn, note); |
| } |
| |
| /* Cleanup abnormal edges caused by exceptions or non-local gotos. */ |
| for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) |
| { |
| bool remove = false; |
| |
| /* There are three types of edges we need to handle correctly here: EH |
| edges, abnormal call EH edges, and abnormal call non-EH edges. The |
| latter can appear when nonlocal gotos are used. */ |
| if (e->flags & EDGE_ABNORMAL_CALL) |
| { |
| if (!CALL_P (insn)) |
| remove = true; |
| else if (can_nonlocal_goto (insn)) |
| ; |
| else if ((e->flags & EDGE_EH) && can_throw_internal (insn)) |
| ; |
| else if (flag_tm && find_reg_note (insn, REG_TM, NULL)) |
| ; |
| else |
| remove = true; |
| } |
| else if (e->flags & EDGE_EH) |
| remove = !can_throw_internal (insn); |
| |
| if (remove) |
| { |
| remove_edge (e); |
| df_set_bb_dirty (bb); |
| purged = true; |
| } |
| else |
| ei_next (&ei); |
| } |
| |
| 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) |
| && !returnjump_p (insn) |
| && !simplejump_p (insn)) |
| return purged; |
| |
| /* Branch probability/prediction notes are defined only for |
| condjumps. We've possibly turned condjump into simplejump. */ |
| if (simplejump_p (insn)) |
| { |
| note = find_reg_note (insn, REG_BR_PROB, NULL); |
| if (note) |
| remove_note (insn, note); |
| while ((note = find_reg_note (insn, REG_BR_PRED, NULL))) |
| remove_note (insn, note); |
| } |
| |
| for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) |
| { |
| /* Avoid abnormal flags to leak from computed jumps turned |
| into simplejumps. */ |
| |
| e->flags &= ~EDGE_ABNORMAL; |
| |
| /* See if this edge is one we should keep. */ |
| 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. */ |
| { |
| ei_next (&ei); |
| continue; |
| } |
| else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) |
| && BB_HEAD (e->dest) == JUMP_LABEL (insn)) |
| /* If the destination block is the target of the jump, |
| keep the edge. */ |
| { |
| ei_next (&ei); |
| continue; |
| } |
| else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) |
| && returnjump_p (insn)) |
| /* If the destination block is the exit block, and this |
| instruction is a return, then keep the edge. */ |
| { |
| 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 and rematerialize the EDGE_ABNORMAL |
| flag we just cleared above. */ |
| { |
| e->flags |= EDGE_ABNORMAL; |
| ei_next (&ei); |
| continue; |
| } |
| |
| /* We do not need this edge. */ |
| df_set_bb_dirty (bb); |
| purged = true; |
| remove_edge (e); |
| } |
| |
| if (EDGE_COUNT (bb->succs) == 0 || !purged) |
| return purged; |
| |
| if (dump_file) |
| fprintf (dump_file, "Purged edges from bb %i\n", bb->index); |
| |
| if (!optimize) |
| return purged; |
| |
| /* Redistribute probabilities. */ |
| if (single_succ_p (bb)) |
| { |
| single_succ_edge (bb)->probability = REG_BR_PROB_BASE; |
| single_succ_edge (bb)->count = bb->count; |
| } |
| else |
| { |
| note = find_reg_note (insn, REG_BR_PROB, NULL); |
| if (!note) |
| return purged; |
| |
| b = BRANCH_EDGE (bb); |
| f = FALLTHRU_EDGE (bb); |
| b->probability = XINT (note, 0); |
| f->probability = REG_BR_PROB_BASE - b->probability; |
| /* Update these to use GCOV_COMPUTE_SCALE. */ |
| b->count = bb->count * b->probability / REG_BR_PROB_BASE; |
| f->count = bb->count * f->probability / REG_BR_PROB_BASE; |
| } |
| |
| 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 (single_succ_p (bb)); |
| gcc_assert (single_succ_edge (bb)->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. */ |
| found = false; |
| FOR_EACH_EDGE (e, ei, bb->succs) |
| if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))) |
| { |
| found = true; |
| break; |
| } |
| |
| if (!found) |
| return purged; |
| |
| /* Remove all but the fake and fallthru edges. The fake edge may be |
| the only successor for this block in the case of noreturn |
| calls. */ |
| for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) |
| { |
| if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE))) |
| { |
| df_set_bb_dirty (bb); |
| remove_edge (e); |
| purged = true; |
| } |
| else |
| ei_next (&ei); |
| } |
| |
| gcc_assert (single_succ_p (bb)); |
| |
| single_succ_edge (bb)->probability = REG_BR_PROB_BASE; |
| single_succ_edge (bb)->count = bb->count; |
| |
| if (dump_file) |
| fprintf (dump_file, "Purged non-fallthru edges from bb %i\n", |
| bb->index); |
| return purged; |
| } |
| |
| /* Search all basic blocks for potentially dead edges and purge them. Return |
| true if some edge has been eliminated. */ |
| |
| bool |
| purge_all_dead_edges (void) |
| { |
| int purged |