/* RTL dead code elimination.
- Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
This file is part of GCC.
rtx body, x;
int i;
+ if (CALL_P (insn)
+ /* We cannot delete calls inside of the recursive dce because
+ this may cause basic blocks to be deleted and this messes up
+ the rest of the stack of optimization passes. */
+ && (!df_in_progress)
+ /* We cannot delete pure or const sibling calls because it is
+ hard to see the result. */
+ && (!SIBLING_CALL_P (insn))
+ /* We can delete dead const or pure calls as long as they do not
+ infinite loop. */
+ && (RTL_CONST_OR_PURE_CALL_P (insn)
+ && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)))
+ return true;
+
if (!NONJUMP_INSN_P (insn))
return false;
static inline int
marked_insn_p (rtx insn)
{
- if (insn)
- return TEST_BIT (marked, INSN_UID (insn));
- else
- /* Artificial defs are always needed and they do not have an
- insn. */
- return true;
+ /* Artificial defs are always needed and they do not have an insn.
+ We should never see them here. */
+ gcc_assert (insn);
+ return TEST_BIT (marked, INSN_UID (insn));
}
}
-/* Return true if the entire libcall sequence starting at INSN is dead.
- NOTE is the REG_LIBCALL note attached to INSN.
-
- A libcall sequence is a block of insns with no side-effects, i.e.
- that is only used for its return value. The terminology derives
- from that of a call, but a libcall sequence need not contain one.
- It is only defined by a pair of REG_LIBCALL/REG_RETVAL notes.
-
- From a dataflow viewpoint, a libcall sequence has the property that
- no UD chain can enter it from the outside. As a consequence, if a
- libcall sequence has a dead return value, it is effectively dead.
- This is both enforced by CSE (cse_extended_basic_block) and relied
- upon by delete_trivially_dead_insns.
-
- However, in practice, the return value business is a tricky one and
- only checking the liveness of the last insn is not sufficient to
- decide whether the whole sequence is dead (e.g. PR middle-end/19551)
- so we check the liveness of every insn starting from the call. */
-
-static bool
-libcall_dead_p (rtx insn, rtx note)
-{
- rtx last = XEXP (note, 0);
-
- /* Find the call insn. */
- while (insn != last && !CALL_P (insn))
- insn = NEXT_INSN (insn);
-
- /* If there is none, do nothing special, since ordinary death handling
- can understand these insns. */
- if (!CALL_P (insn))
- return false;
-
- /* If this is a call that returns a value via an invisible pointer, the
- dataflow engine cannot see it so it has been marked unconditionally.
- Skip it unless it has been made the last insn in the libcall, for
- example by the combiner, in which case we're left with no easy way
- of asserting its liveness. */
- if (!single_set (insn))
- {
- if (insn == last)
- return false;
- insn = NEXT_INSN (insn);
- }
-
- while (insn != NEXT_INSN (last))
- {
- if (INSN_P (insn) && marked_insn_p (insn))
- return false;
- insn = NEXT_INSN (insn);
- }
-
- return true;
-}
-
-
/* Delete all REG_EQUAL notes of the registers INSN writes, to prevent
bad dangling REG_EQUAL notes. */
{
basic_block bb;
rtx insn, next;
+ bool must_clean = false;
FOR_EACH_BB (bb)
FOR_BB_INSNS_SAFE (bb, insn, next)
if (INSN_P (insn))
{
- rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
-
/* Always delete no-op moves. */
if (noop_move_p (insn))
;
- /* Try to delete libcall sequences as a whole. */
- else if (note && libcall_dead_p (insn, note))
- {
- rtx last = XEXP (note, 0);
-
- if (!dbg_cnt (dce))
- continue;
-
- if (dump_file)
- fprintf (dump_file, "DCE: Deleting libcall %d-%d\n",
- INSN_UID (insn), INSN_UID (last));
-
- next = NEXT_INSN (last);
- delete_insn_chain_and_edges (insn, last);
- continue;
- }
-
/* Otherwise rely only on the DCE algorithm. */
else if (marked_insn_p (insn))
continue;
for the destination regs in order to avoid dangling notes. */
delete_corresponding_reg_eq_notes (insn);
- /* If we're about to delete the first insn of a libcall, then
- move the REG_LIBCALL note to the next real insn and update
- the REG_RETVAL note. */
- if (note && (XEXP (note, 0) != insn))
- {
- rtx new_libcall_insn = next_real_insn (insn);
- rtx retval_note = find_reg_note (XEXP (note, 0),
- REG_RETVAL, NULL_RTX);
- /* If the RETVAL and LIBCALL notes would land on the same
- insn just remove them. */
- if (XEXP (note, 0) == new_libcall_insn)
- remove_note (new_libcall_insn, retval_note);
- else
- {
- REG_NOTES (new_libcall_insn)
- = gen_rtx_INSN_LIST (REG_LIBCALL, XEXP (note, 0),
- REG_NOTES (new_libcall_insn));
- XEXP (retval_note, 0) = new_libcall_insn;
- }
- }
-
- /* If the insn contains a REG_RETVAL note and is dead, but the
- libcall as a whole is not dead, then we want to remove the
- insn, but not the whole libcall sequence. However, we also
- need to remove the dangling REG_LIBCALL note in order to
- avoid mismatched notes. We could find a new location for
- the REG_RETVAL note, but it hardly seems worth the effort. */
- note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
- if (note && (XEXP (note, 0) != insn))
- {
- rtx libcall_note
- = find_reg_note (XEXP (note, 0), REG_LIBCALL, NULL_RTX);
- remove_note (XEXP (note, 0), libcall_note);
- }
+ /* If a pure or const call is deleted, this may make the cfg
+ have unreachable blocks. We rememeber this and call
+ delete_unreachable_blocks at the end. */
+ if (CALL_P (insn))
+ must_clean = true;
/* Now delete the insn. */
delete_insn_and_edges (insn);
}
-}
-
-
-/* Helper function for prescan_insns_for_dce: prescan the entire libcall
- sequence starting at INSN and return the insn following the libcall.
- NOTE is the REG_LIBCALL note attached to INSN. */
-
-static rtx
-prescan_libcall_for_dce (rtx insn, rtx note, bool fast)
-{
- rtx last = XEXP (note, 0);
- /* A libcall is never necessary on its own but we need to mark the stores
- to a non-register destination. */
- while (insn != last && !CALL_P (insn))
- {
- if (INSN_P (insn))
- mark_nonreg_stores (PATTERN (insn), insn, fast);
- insn = NEXT_INSN (insn);
- }
-
- /* If this is a call that returns a value via an invisible pointer, the
- dataflow engine cannot see it so it has to be marked unconditionally. */
- if (CALL_P (insn) && !single_set (insn))
- {
- mark_insn (insn, fast);
- insn = NEXT_INSN (insn);
- }
-
- while (insn != NEXT_INSN (last))
- {
- if (INSN_P (insn))
- mark_nonreg_stores (PATTERN (insn), insn, fast);
- insn = NEXT_INSN (insn);
- }
-
- return insn;
+ /* Deleted a pure or const call. */
+ if (must_clean)
+ delete_unreachable_blocks ();
}
FOR_BB_INSNS_SAFE (bb, insn, next)
if (INSN_P (insn))
{
- rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
- if (note)
- next = prescan_libcall_for_dce (insn, note, fast);
- else if (deletable_insn_p (insn, fast))
+ if (deletable_insn_p (insn, fast))
mark_nonreg_stores (PATTERN (insn), insn, fast);
else
mark_insn (insn, fast);
for (use_rec = df_get_artificial_uses (bb->index);
*use_rec; use_rec++)
for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next)
- mark_insn (DF_REF_INSN (defs->ref), false);
+ if (! DF_REF_IS_ARTIFICIAL (defs->ref))
+ mark_insn (DF_REF_INSN (defs->ref), false);
}
}
fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));
}
for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
- mark_insn (DF_REF_INSN (defs->ref), false);
+ if (! DF_REF_IS_ARTIFICIAL (defs->ref))
+ mark_insn (DF_REF_INSN (defs->ref), false);
}
}
Fast DCE functions
------------------------------------------------------------------------- */
-/* Process basic block BB. Return true if the live_in set has changed. */
+/* Process basic block BB. Return true if the live_in set has
+ changed. REDO_OUT is true if the info at the bottom of the block
+ needs to be recalculated before starting. AU is the proper set of
+ artificial uses. */
static bool
-dce_process_block (basic_block bb, bool redo_out)
+byte_dce_process_block (basic_block bb, bool redo_out, bitmap au)
{
bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
- bitmap au;
rtx insn;
bool block_changed;
- struct df_ref **def_rec, **use_rec;
- unsigned int bb_index = bb->index;
+ struct df_ref **def_rec;
if (redo_out)
{
set. */
edge e;
edge_iterator ei;
- df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
- bitmap_clear (DF_LR_OUT (bb));
+ df_confluence_function_n con_fun_n = df_byte_lr->problem->con_fun_n;
+ bitmap_clear (DF_BYTE_LR_OUT (bb));
FOR_EACH_EDGE (e, ei, bb->succs)
(*con_fun_n) (e);
}
if (dump_file)
{
fprintf (dump_file, "processing block %d live out = ", bb->index);
- df_print_regset (dump_file, DF_LR_OUT (bb));
+ df_print_byte_regset (dump_file, DF_BYTE_LR_OUT (bb));
}
- bitmap_copy (local_live, DF_LR_OUT (bb));
+ bitmap_copy (local_live, DF_BYTE_LR_OUT (bb));
+
+ df_byte_lr_simulate_artificial_refs_at_end (bb, local_live);
- /* Process the artificial defs and uses at the bottom of the block. */
- for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+ FOR_BB_INSNS_REVERSE (bb, insn)
+ if (INSN_P (insn))
+ {
+ /* The insn is needed if there is someone who uses the output. */
+ for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ unsigned int last;
+ unsigned int dregno = DF_REF_REGNO (def);
+ unsigned int start = df_byte_lr_get_regno_start (dregno);
+ unsigned int len = df_byte_lr_get_regno_len (dregno);
+
+ unsigned int sb;
+ unsigned int lb;
+ /* This is one of the only places where DF_MM_MAY should
+ be used for defs. Need to make sure that we are
+ checking for all of the bits that may be used. */
+
+ if (!df_compute_accessed_bytes (def, DF_MM_MAY, &sb, &lb))
+ {
+ start += sb;
+ len = lb - sb;
+ }
+
+ if (bitmap_bit_p (au, dregno))
+ {
+ mark_insn (insn, true);
+ goto quickexit;
+ }
+
+ last = start + len;
+ while (start < last)
+ if (bitmap_bit_p (local_live, start++))
+ {
+ mark_insn (insn, true);
+ goto quickexit;
+ }
+ }
+
+ quickexit:
+
+ /* No matter if the instruction is needed or not, we remove
+ any regno in the defs from the live set. */
+ df_byte_lr_simulate_defs (insn, local_live);
+
+ /* On the other hand, we do not allow the dead uses to set
+ anything in local_live. */
+ if (marked_insn_p (insn))
+ df_byte_lr_simulate_uses (insn, local_live);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "finished processing insn %d live out = ",
+ INSN_UID (insn));
+ df_print_byte_regset (dump_file, local_live);
+ }
+ }
+
+ df_byte_lr_simulate_artificial_refs_at_top (bb, local_live);
+
+ block_changed = !bitmap_equal_p (local_live, DF_BYTE_LR_IN (bb));
+ if (block_changed)
+ bitmap_copy (DF_BYTE_LR_IN (bb), local_live);
+ BITMAP_FREE (local_live);
+ return block_changed;
+}
+
+
+/* Process basic block BB. Return true if the live_in set has
+ changed. REDO_OUT is true if the info at the bottom of the block
+ needs to be recalculated before starting. AU is the proper set of
+ artificial uses. */
+
+static bool
+dce_process_block (basic_block bb, bool redo_out, bitmap au)
+{
+ bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
+ rtx insn;
+ bool block_changed;
+ struct df_ref **def_rec;
+
+ if (redo_out)
{
- struct df_ref *def = *def_rec;
- if (((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
- && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
- bitmap_clear_bit (local_live, DF_REF_REGNO (def));
+ /* Need to redo the live_out set of this block if when one of
+ the succs of this block has had a change in it live in
+ set. */
+ edge e;
+ edge_iterator ei;
+ df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
+ bitmap_clear (DF_LR_OUT (bb));
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ (*con_fun_n) (e);
}
- for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
+ if (dump_file)
{
- struct df_ref *use = *use_rec;
- if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
- bitmap_set_bit (local_live, DF_REF_REGNO (use));
+ fprintf (dump_file, "processing block %d live out = ", bb->index);
+ df_print_regset (dump_file, DF_LR_OUT (bb));
}
- /* These regs are considered always live so if they end up dying
- because of some def, we need to bring the back again.
- Calling df_simulate_fixup_sets has the disadvantage of calling
- bb_has_eh_pred once per insn, so we cache the information here. */
- if (bb_has_eh_pred (bb))
- au = df->eh_block_artificial_uses;
- else
- au = df->regular_block_artificial_uses;
+ bitmap_copy (local_live, DF_LR_OUT (bb));
+
+ df_simulate_artificial_refs_at_end (bb, local_live);
FOR_BB_INSNS_REVERSE (bb, insn)
if (INSN_P (insn))
df_simulate_uses (insn, local_live);
}
- for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
- {
- struct df_ref *def = *def_rec;
- if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP)
- && (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))))
- bitmap_clear_bit (local_live, DF_REF_REGNO (def));
- }
-
-#ifdef EH_USES
- /* Process the uses that are live into an exception handler. */
- for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
- {
- /* Add use to set of uses in this BB. */
- struct df_ref *use = *use_rec;
- if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
- bitmap_set_bit (local_live, DF_REF_REGNO (use));
- }
-#endif
+ df_simulate_artificial_refs_at_top (bb, local_live);
block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
if (block_changed)
}
-/* Perform fast DCE once initialization is done. */
+/* Perform fast DCE once initialization is done. If BYTE_LEVEL is
+ true, use the byte level dce, otherwise do it at the pseudo
+ level. */
static void
-fast_dce (void)
+fast_dce (bool byte_level)
{
int *postorder = df_get_postorder (DF_BACKWARD);
int n_blocks = df_get_n_blocks (DF_BACKWARD);
bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
bool global_changed = true;
+
+ /* These regs are considered always live so if they end up dying
+ because of some def, we need to bring the back again. Calling
+ df_simulate_fixup_sets has the disadvantage of calling
+ bb_has_eh_pred once per insn, so we cache the information
+ here. */
+ bitmap au = df->regular_block_artificial_uses;
+ bitmap au_eh = df->eh_block_artificial_uses;
int i;
prescan_insns_for_dce (true);
continue;
}
- local_changed
- = dce_process_block (bb, bitmap_bit_p (redo_out, index));
+ if (byte_level)
+ local_changed
+ = byte_dce_process_block (bb, bitmap_bit_p (redo_out, index),
+ bb_has_eh_pred (bb) ? au_eh : au);
+ else
+ local_changed
+ = dce_process_block (bb, bitmap_bit_p (redo_out, index),
+ bb_has_eh_pred (bb) ? au_eh : au);
bitmap_set_bit (processed, index);
if (local_changed)
to redo the dataflow equations for the blocks that had a
change at the top of the block. Then we need to redo the
iteration. */
- df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
+ if (byte_level)
+ df_analyze_problem (df_byte_lr, all_blocks, postorder, n_blocks);
+ else
+ df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
if (old_flag & DF_LR_RUN_DCE)
df_set_flags (DF_LR_RUN_DCE);
}
-/* Fast DCE. */
+/* Fast register level DCE. */
static unsigned int
rest_of_handle_fast_dce (void)
{
init_dce (true);
- fast_dce ();
+ fast_dce (false);
+ fini_dce (true);
+ return 0;
+}
+
+
+/* Fast byte level DCE. */
+
+static unsigned int
+rest_of_handle_fast_byte_dce (void)
+{
+ df_byte_lr_add_problem ();
+ init_dce (true);
+ fast_dce (true);
fini_dce (true);
return 0;
}
TODO_ggc_collect /* todo_flags_finish */
}
};
+
+struct rtl_opt_pass pass_fast_rtl_byte_dce =
+{
+ {
+ RTL_PASS,
+ "byte-dce", /* name */
+ gate_fast_dce, /* gate */
+ rest_of_handle_fast_byte_dce, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_DCE, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func |
+ TODO_df_finish | TODO_verify_rtl_sharing |
+ TODO_ggc_collect /* todo_flags_finish */
+ }
+};
OSDN Git Service
