X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=gcc%2Fdce.c;h=a36ac61dea8c772123eb08750c208d0bc403e860;hb=6c1e7aa99cf4d918535ebfe59f19e48672a3c9a4;hp=e38e79732daf8fb42a3a04d8e134c2a23c963f9d;hpb=2e6be65ec6ee3a39c125cd71c348e0ec3b715fc0;p=platform%2Fupstream%2Fgcc.git diff --git a/gcc/dce.c b/gcc/dce.c index e38e797..a36ac61 100644 --- a/gcc/dce.c +++ b/gcc/dce.c @@ -1,5 +1,6 @@ /* RTL dead code elimination. - Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc. + Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 + Free Software Foundation, Inc. This file is part of GCC. @@ -27,15 +28,15 @@ along with GCC; see the file COPYING3. If not see #include "regs.h" #include "hard-reg-set.h" #include "flags.h" +#include "except.h" #include "df.h" #include "cselib.h" #include "dce.h" #include "timevar.h" #include "tree-pass.h" #include "dbgcnt.h" - -DEF_VEC_I(int); -DEF_VEC_ALLOC_I(int,heap); +#include "tm_p.h" +#include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */ /* ------------------------------------------------------------------------- @@ -46,9 +47,6 @@ DEF_VEC_ALLOC_I(int,heap); we don't want to reenter it. */ static bool df_in_progress = false; -/* True if we deleted at least one instruction. */ -static bool something_changed; - /* Instructions that have been marked but whose dependencies have not yet been processed. */ static VEC(rtx,heap) *worklist; @@ -60,6 +58,7 @@ static sbitmap marked; static bitmap_obstack dce_blocks_bitmap_obstack; static bitmap_obstack dce_tmp_bitmap_obstack; +static bool find_call_stack_args (rtx, bool, bool, bitmap); /* A subroutine for which BODY is part of the instruction being tested; either the top-level pattern, or an element of a PARALLEL. The @@ -82,13 +81,7 @@ deletable_insn_p_1 (rtx body) return false; default: - if (volatile_refs_p (body)) - return false; - - if (flag_non_call_exceptions && may_trap_p (body)) - return false; - - return true; + return !volatile_refs_p (body); } } @@ -97,18 +90,38 @@ deletable_insn_p_1 (rtx body) the DCE pass. */ static bool -deletable_insn_p (rtx insn, bool fast) +deletable_insn_p (rtx insn, bool fast, bitmap arg_stores) { 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 find_call_stack_args (insn, false, fast, arg_stores); + + /* Don't delete jumps, notes and the like. */ if (!NONJUMP_INSN_P (insn)) return false; + /* Don't delete insns that can throw. */ + if (!insn_nothrow_p (insn)) + return false; + body = PATTERN (insn); switch (GET_CODE (body)) { case USE: + case VAR_LOCATION: return false; case CLOBBER: @@ -143,12 +156,10 @@ deletable_insn_p (rtx insn, bool fast) 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)); } @@ -165,6 +176,12 @@ mark_insn (rtx insn, bool fast) SET_BIT (marked, INSN_UID (insn)); if (dump_file) fprintf (dump_file, " Adding insn %d to worklist\n", INSN_UID (insn)); + if (CALL_P (insn) + && !df_in_progress + && !SIBLING_CALL_P (insn) + && (RTL_CONST_OR_PURE_CALL_P (insn) + && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))) + find_call_stack_args (insn, true, fast, NULL); } } @@ -203,149 +220,380 @@ mark_nonreg_stores (rtx body, rtx insn, bool fast) } -/* Delete all REG_EQUAL notes of the registers INSN writes, to prevent - bad dangling REG_EQUAL notes. */ +/* Return true if store to MEM, starting OFF bytes from stack pointer, + is a call argument store, and clear corresponding bits from SP_BYTES + bitmap if it is. */ -static void -delete_corresponding_reg_eq_notes (rtx insn) +static bool +check_argument_store (rtx mem, HOST_WIDE_INT off, HOST_WIDE_INT min_sp_off, + HOST_WIDE_INT max_sp_off, bitmap sp_bytes) { - struct df_ref **def_rec; - for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++) + HOST_WIDE_INT byte; + for (byte = off; byte < off + GET_MODE_SIZE (GET_MODE (mem)); byte++) { - struct df_ref *def = *def_rec; - unsigned int regno = DF_REF_REGNO (def); - /* This loop is a little tricky. We cannot just go down the - chain because it is being modified by the actions in the - loop. So we just get the head. We plan to drain the list - anyway. */ - while (DF_REG_EQ_USE_CHAIN (regno)) - { - struct df_ref *eq_use = DF_REG_EQ_USE_CHAIN (regno); - rtx noted_insn = DF_REF_INSN (eq_use); - rtx note = find_reg_note (noted_insn, REG_EQUAL, NULL_RTX); - if (!note) - note = find_reg_note (noted_insn, REG_EQUIV, NULL_RTX); - - /* This assert is generally triggered when someone deletes a - REG_EQUAL or REG_EQUIV note by hacking the list manually - rather than calling remove_note. */ - gcc_assert (note); - remove_note (noted_insn, note); - } + if (byte < min_sp_off + || byte >= max_sp_off + || !bitmap_clear_bit (sp_bytes, byte - min_sp_off)) + return false; } + return true; } -/* Delete every instruction that hasn't been marked. Clear the insn - from DCE_DF if DF_DELETE is true. */ +/* Try to find all stack stores of CALL_INSN arguments if + ACCUMULATE_OUTGOING_ARGS. If all stack stores have been found + and it is therefore safe to eliminate the call, return true, + otherwise return false. This function should be first called + with DO_MARK false, and only when the CALL_INSN is actually + going to be marked called again with DO_MARK true. */ -static void -delete_unmarked_insns (void) +static bool +find_call_stack_args (rtx call_insn, bool do_mark, bool fast, + bitmap arg_stores) { - basic_block bb; - rtx insn, next; + rtx p, insn, prev_insn; + bool ret; + HOST_WIDE_INT min_sp_off, max_sp_off; + bitmap sp_bytes; - something_changed = false; + gcc_assert (CALL_P (call_insn)); + if (!ACCUMULATE_OUTGOING_ARGS) + return true; - FOR_EACH_BB (bb) - FOR_BB_INSNS_SAFE (bb, insn, next) - if (INSN_P (insn)) + if (!do_mark) + { + gcc_assert (arg_stores); + bitmap_clear (arg_stores); + } + + min_sp_off = INTTYPE_MAXIMUM (HOST_WIDE_INT); + max_sp_off = 0; + + /* First determine the minimum and maximum offset from sp for + stored arguments. */ + for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1)) + if (GET_CODE (XEXP (p, 0)) == USE + && MEM_P (XEXP (XEXP (p, 0), 0))) + { + rtx mem = XEXP (XEXP (p, 0), 0), addr; + HOST_WIDE_INT off = 0, size; + if (!MEM_SIZE_KNOWN_P (mem)) + return false; + size = MEM_SIZE (mem); + addr = XEXP (mem, 0); + if (GET_CODE (addr) == PLUS + && REG_P (XEXP (addr, 0)) + && CONST_INT_P (XEXP (addr, 1))) + { + off = INTVAL (XEXP (addr, 1)); + addr = XEXP (addr, 0); + } + if (addr != stack_pointer_rtx) + { + if (!REG_P (addr)) + return false; + /* If not fast, use chains to see if addr wasn't set to + sp + offset. */ + if (!fast) + { + df_ref *use_rec; + struct df_link *defs; + rtx set; + + for (use_rec = DF_INSN_USES (call_insn); *use_rec; use_rec++) + if (rtx_equal_p (addr, DF_REF_REG (*use_rec))) + break; + + if (*use_rec == NULL) + return false; + + for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next) + if (! DF_REF_IS_ARTIFICIAL (defs->ref)) + break; + + if (defs == NULL) + return false; + + set = single_set (DF_REF_INSN (defs->ref)); + if (!set) + return false; + + if (GET_CODE (SET_SRC (set)) != PLUS + || XEXP (SET_SRC (set), 0) != stack_pointer_rtx + || !CONST_INT_P (XEXP (SET_SRC (set), 1))) + return false; + + off += INTVAL (XEXP (SET_SRC (set), 1)); + } + else + return false; + } + min_sp_off = MIN (min_sp_off, off); + max_sp_off = MAX (max_sp_off, off + size); + } + + if (min_sp_off >= max_sp_off) + return true; + sp_bytes = BITMAP_ALLOC (NULL); + + /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off + which contain arguments. Checking has been done in the previous + loop. */ + for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1)) + if (GET_CODE (XEXP (p, 0)) == USE + && MEM_P (XEXP (XEXP (p, 0), 0))) + { + rtx mem = XEXP (XEXP (p, 0), 0), addr; + HOST_WIDE_INT off = 0, byte; + addr = XEXP (mem, 0); + if (GET_CODE (addr) == PLUS + && REG_P (XEXP (addr, 0)) + && CONST_INT_P (XEXP (addr, 1))) + { + off = INTVAL (XEXP (addr, 1)); + addr = XEXP (addr, 0); + } + if (addr != stack_pointer_rtx) + { + df_ref *use_rec; + struct df_link *defs; + rtx set; + + for (use_rec = DF_INSN_USES (call_insn); *use_rec; use_rec++) + if (rtx_equal_p (addr, DF_REF_REG (*use_rec))) + break; + + for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next) + if (! DF_REF_IS_ARTIFICIAL (defs->ref)) + break; + + set = single_set (DF_REF_INSN (defs->ref)); + off += INTVAL (XEXP (SET_SRC (set), 1)); + } + for (byte = off; byte < off + MEM_SIZE (mem); byte++) + { + if (!bitmap_set_bit (sp_bytes, byte - min_sp_off)) + gcc_unreachable (); + } + } + + /* Walk backwards, looking for argument stores. The search stops + when seeing another call, sp adjustment or memory store other than + argument store. */ + ret = false; + for (insn = PREV_INSN (call_insn); insn; insn = prev_insn) + { + rtx set, mem, addr; + HOST_WIDE_INT off; + + if (insn == BB_HEAD (BLOCK_FOR_INSN (call_insn))) + prev_insn = NULL_RTX; + else + prev_insn = PREV_INSN (insn); + + if (CALL_P (insn)) + break; + + if (!NONDEBUG_INSN_P (insn)) + continue; + + set = single_set (insn); + if (!set || SET_DEST (set) == stack_pointer_rtx) + break; + + if (!MEM_P (SET_DEST (set))) + continue; + + mem = SET_DEST (set); + addr = XEXP (mem, 0); + off = 0; + if (GET_CODE (addr) == PLUS + && REG_P (XEXP (addr, 0)) + && CONST_INT_P (XEXP (addr, 1))) { - if (noop_move_p (insn)) + off = INTVAL (XEXP (addr, 1)); + addr = XEXP (addr, 0); + } + if (addr != stack_pointer_rtx) + { + if (!REG_P (addr)) + break; + if (!fast) { - /* Note that this code does not handle the case where - the last insn of libcall is deleted. As it turns out - this case is excluded in the call to noop_move_p. */ - rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX); - 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); - 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; - } + df_ref *use_rec; + struct df_link *defs; + rtx set; + + for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++) + if (rtx_equal_p (addr, DF_REF_REG (*use_rec))) + break; + + if (*use_rec == NULL) + break; + + for (defs = DF_REF_CHAIN (*use_rec); defs; defs = defs->next) + if (! DF_REF_IS_ARTIFICIAL (defs->ref)) + break; + + if (defs == NULL) + break; + + set = single_set (DF_REF_INSN (defs->ref)); + if (!set) + break; + + if (GET_CODE (SET_SRC (set)) != PLUS + || XEXP (SET_SRC (set), 0) != stack_pointer_rtx + || !CONST_INT_P (XEXP (SET_SRC (set), 1))) + break; + + off += INTVAL (XEXP (SET_SRC (set), 1)); } - else if (marked_insn_p (insn)) - continue; + else + break; + } - /* WARNING, this debugging can itself cause problems if the - edge of the counter causes part of a libcall to be - deleted but not all of it. */ - if (!dbg_cnt (dce)) - continue; + if (GET_MODE_SIZE (GET_MODE (mem)) == 0 + || !check_argument_store (mem, off, min_sp_off, + max_sp_off, sp_bytes)) + break; - if (dump_file) - fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn)); + if (!deletable_insn_p (insn, fast, NULL)) + break; - /* Before we delete the insn, we have to delete - REG_EQUAL of the destination regs of the deleted insn - to prevent dangling REG_EQUAL. */ - delete_corresponding_reg_eq_notes (insn); + if (do_mark) + mark_insn (insn, fast); + else + bitmap_set_bit (arg_stores, INSN_UID (insn)); - delete_insn_and_edges (insn); - something_changed = true; + if (bitmap_empty_p (sp_bytes)) + { + ret = true; + break; } + } + + BITMAP_FREE (sp_bytes); + if (!ret && arg_stores) + bitmap_clear (arg_stores); + + return ret; } -/* Mark all insns using DELETE_PARM in the libcall that contains - START_INSN. */ +/* Remove all REG_EQUAL and REG_EQUIV notes referring to the registers INSN + writes to. */ -static void -mark_libcall (rtx start_insn, bool delete_parm) +static void +remove_reg_equal_equiv_notes_for_defs (rtx insn) { - rtx note = find_reg_note (start_insn, REG_LIBCALL_ID, NULL_RTX); - int id = INTVAL (XEXP (note, 0)); - rtx insn; + df_ref *def_rec; - mark_insn (start_insn, delete_parm); - insn = NEXT_INSN (start_insn); + for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++) + remove_reg_equal_equiv_notes_for_regno (DF_REF_REGNO (*def_rec)); +} - /* There are tales, long ago and far away, of the mystical nested - libcall. No one alive has actually seen one, but other parts of - the compiler support them so we will here. */ - for (insn = NEXT_INSN (start_insn); insn; insn = NEXT_INSN (insn)) - { - if (INSN_P (insn)) +/* Scan all BBs for debug insns and reset those that reference values + defined in unmarked insns. */ + +static void +reset_unmarked_insns_debug_uses (void) +{ + basic_block bb; + rtx insn, next; + + FOR_EACH_BB_REVERSE (bb) + FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next) + if (DEBUG_INSN_P (insn)) { - /* Stay in the loop as long as we are in any libcall. */ - if ((note = find_reg_note (insn, REG_LIBCALL_ID, NULL_RTX))) + df_ref *use_rec; + + for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++) { - if (id == INTVAL (XEXP (note, 0))) + df_ref use = *use_rec; + struct df_link *defs; + for (defs = DF_REF_CHAIN (use); defs; defs = defs->next) { - mark_insn (insn, delete_parm); - if (dump_file) - fprintf (dump_file, "matching forward libcall %d[%d]\n", - INSN_UID (insn), id); + rtx ref_insn; + if (DF_REF_IS_ARTIFICIAL (defs->ref)) + continue; + ref_insn = DF_REF_INSN (defs->ref); + if (!marked_insn_p (ref_insn)) + break; } + if (!defs) + continue; + /* ??? FIXME could we propagate the values assigned to + each of the DEFs? */ + INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC (); + df_insn_rescan_debug_internal (insn); + break; } - else - break; } - } - - for (insn = PREV_INSN (start_insn); insn; insn = PREV_INSN (insn)) - { - if (INSN_P (insn)) +} + +/* Delete every instruction that hasn't been marked. */ + +static void +delete_unmarked_insns (void) +{ + basic_block bb; + rtx insn, next; + bool must_clean = false; + + FOR_EACH_BB_REVERSE (bb) + FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next) + if (NONDEBUG_INSN_P (insn)) { - /* Stay in the loop as long as we are in any libcall. */ - if ((note = find_reg_note (insn, REG_LIBCALL_ID, NULL_RTX))) - { - if (id == INTVAL (XEXP (note, 0))) - { - mark_insn (insn, delete_parm); - if (dump_file) - fprintf (dump_file, "matching backward libcall %d[%d]\n", - INSN_UID (insn), id); - } - } - else - break; + /* Always delete no-op moves. */ + if (noop_move_p (insn)) + ; + + /* Otherwise rely only on the DCE algorithm. */ + else if (marked_insn_p (insn)) + continue; + + /* Beware that reaching a dbg counter limit here can result + in miscompiled file. This occurs when a group of insns + must be deleted together, typically because the kept insn + depends on the output from the deleted insn. Deleting + this insns in reverse order (both at the bb level and + when looking at the blocks) minimizes this, but does not + eliminate it, since it is possible for the using insn to + be top of a block and the producer to be at the bottom of + the block. However, in most cases this will only result + in an uninitialized use of an insn that is dead anyway. + + However, there is one rare case that will cause a + miscompile: deletion of non-looping pure and constant + calls on a machine where ACCUMULATE_OUTGOING_ARGS is true. + In this case it is possible to remove the call, but leave + the argument pushes to the stack. Because of the changes + to the stack pointer, this will almost always lead to a + miscompile. */ + if (!dbg_cnt (dce)) + continue; + + if (dump_file) + fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn)); + + /* Before we delete the insn we have to remove the REG_EQUAL notes + for the destination regs in order to avoid dangling notes. */ + remove_reg_equal_equiv_notes_for_defs (insn); + + /* 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); } - } + + /* Deleted a pure or const call. */ + if (must_clean) + delete_unreachable_blocks (); } @@ -357,23 +605,37 @@ static void prescan_insns_for_dce (bool fast) { basic_block bb; - rtx insn; - + rtx insn, prev; + bitmap arg_stores = NULL; + if (dump_file) fprintf (dump_file, "Finding needed instructions:\n"); - + + if (!df_in_progress && ACCUMULATE_OUTGOING_ARGS) + arg_stores = BITMAP_ALLOC (NULL); + FOR_EACH_BB (bb) - FOR_BB_INSNS (bb, insn) - if (INSN_P (insn)) - { - rtx note = find_reg_note (insn, REG_LIBCALL_ID, NULL_RTX); - if (note) - mark_libcall (insn, fast); - else if (deletable_insn_p (insn, fast)) - mark_nonreg_stores (PATTERN (insn), insn, fast); - else - mark_insn (insn, fast); - } + { + FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev) + if (NONDEBUG_INSN_P (insn)) + { + /* Don't mark argument stores now. They will be marked + if needed when the associated CALL is marked. */ + if (arg_stores && bitmap_bit_p (arg_stores, INSN_UID (insn))) + continue; + if (deletable_insn_p (insn, fast, arg_stores)) + mark_nonreg_stores (PATTERN (insn), insn, fast); + else + mark_insn (insn, fast); + } + /* find_call_stack_args only looks at argument stores in the + same bb. */ + if (arg_stores) + bitmap_clear (arg_stores); + } + + if (arg_stores) + BITMAP_FREE (arg_stores); if (dump_file) fprintf (dump_file, "Finished finding needed instructions:\n"); @@ -390,14 +652,15 @@ mark_artificial_uses (void) { basic_block bb; struct df_link *defs; - struct df_ref **use_rec; + df_ref *use_rec; FOR_ALL_BB (bb) { - for (use_rec = df_get_artificial_uses (bb->index); + 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); } } @@ -408,15 +671,14 @@ static void mark_reg_dependencies (rtx insn) { struct df_link *defs; - struct df_ref **use_rec; + df_ref *use_rec; - /* If this is part of a libcall, mark the entire libcall. */ - if (find_reg_note (insn, REG_LIBCALL_ID, NULL_RTX)) - mark_libcall (insn, false); + if (DEBUG_INSN_P (insn)) + return; for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++) { - struct df_ref *use = *use_rec; + df_ref use = *use_rec; if (dump_file) { fprintf (dump_file, "Processing use of "); @@ -424,7 +686,8 @@ mark_reg_dependencies (rtx insn) 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); } } @@ -486,6 +749,10 @@ rest_of_handle_ud_dce (void) insn = VEC_pop (rtx, worklist); mark_reg_dependencies (insn); } + VEC_free (rtx, heap, worklist); + + if (MAY_HAVE_DEBUG_INSNS) + reset_unmarked_insns_debug_uses (); /* Before any insns are deleted, we must remove the chains since they are not bidirectional. */ @@ -500,14 +767,17 @@ rest_of_handle_ud_dce (void) static bool gate_ud_dce (void) { - return optimize > 1 && flag_dce; + return optimize > 1 && flag_dce + && dbg_cnt (dce_ud); } -struct tree_opt_pass pass_ud_rtl_dce = +struct rtl_opt_pass pass_ud_rtl_dce = { - "dce", /* name */ - gate_ud_dce, /* gate */ - rest_of_handle_ud_dce, /* execute */ + { + RTL_PASS, + "ud_dce", /* name */ + gate_ud_dce, /* gate */ + rest_of_handle_ud_dce, /* execute */ NULL, /* sub */ NULL, /* next */ 0, /* static_pass_number */ @@ -516,10 +786,9 @@ struct tree_opt_pass pass_ud_rtl_dce = 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 */ - 'w' /* letter */ + TODO_ggc_collect /* todo_flags_finish */ + } }; @@ -527,17 +796,17 @@ struct tree_opt_pass pass_ud_rtl_dce = 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) +word_dce_process_block (basic_block bb, bool redo_out) { 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; if (redo_out) { @@ -546,8 +815,8 @@ dce_process_block (basic_block bb, bool 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_word_lr->problem->con_fun_n; + bitmap_clear (DF_WORD_LR_OUT (bb)); FOR_EACH_EDGE (e, ei, bb->succs) (*con_fun_n) (e); } @@ -555,103 +824,106 @@ dce_process_block (basic_block bb, bool redo_out) if (dump_file) { fprintf (dump_file, "processing block %d live out = ", bb->index); - df_print_regset (dump_file, DF_LR_OUT (bb)); + df_print_word_regset (dump_file, DF_WORD_LR_OUT (bb)); } - bitmap_copy (local_live, DF_LR_OUT (bb)); + bitmap_copy (local_live, DF_WORD_LR_OUT (bb)); + + FOR_BB_INSNS_REVERSE (bb, insn) + if (NONDEBUG_INSN_P (insn)) + { + bool any_changed; + /* No matter if the instruction is needed or not, we remove + any regno in the defs from the live set. */ + any_changed = df_word_lr_simulate_defs (insn, local_live); + if (any_changed) + mark_insn (insn, true); - /* 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++) + /* On the other hand, we do not allow the dead uses to set + anything in local_live. */ + if (marked_insn_p (insn)) + df_word_lr_simulate_uses (insn, local_live); + + if (dump_file) + { + fprintf (dump_file, "finished processing insn %d live out = ", + INSN_UID (insn)); + df_print_word_regset (dump_file, local_live); + } + } + + block_changed = !bitmap_equal_p (local_live, DF_WORD_LR_IN (bb)); + if (block_changed) + bitmap_copy (DF_WORD_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; + 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 lr 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_initialize_backwards (bb, local_live); FOR_BB_INSNS_REVERSE (bb, insn) if (INSN_P (insn)) { - /* If this is a recursive call, the libcall will have already - been marked. */ - if (!marked_insn_p (insn)) - { - bool needed = false; - - /* The insn is needed if there is someone who uses the output. */ - for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++) - if (bitmap_bit_p (local_live, DF_REF_REGNO (*def_rec)) - || bitmap_bit_p (au, DF_REF_REGNO (*def_rec))) - { - needed = true; - break; - } - - if (needed) + bool needed = marked_insn_p (insn); + + /* The insn is needed if there is someone who uses the output. */ + if (!needed) + for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++) + if (bitmap_bit_p (local_live, DF_REF_REGNO (*def_rec)) + || bitmap_bit_p (au, DF_REF_REGNO (*def_rec))) { - rtx note = find_reg_note (insn, REG_LIBCALL_ID, NULL_RTX); - - /* If we need to mark an insn in the middle of a - libcall, we need to back up to mark the entire - libcall. Given that libcalls are rare, rescanning - the block should be a reasonable solution to trying - to figure out how to back up. */ - if (note) - { - if (dump_file) - fprintf (dump_file, "needed libcall %d\n", INSN_UID (insn)); - mark_libcall (insn, true); - BITMAP_FREE (local_live); - return dce_process_block (bb, false); - } - else - mark_insn (insn, true); + needed = true; + mark_insn (insn, true); + break; } - } - + /* No matter if the instruction is needed or not, we remove any regno in the defs from the live set. */ df_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)) + if (needed) 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_finalize_backwards (bb, local_live); block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb)); if (block_changed) @@ -662,10 +934,12 @@ dce_process_block (basic_block bb, bool redo_out) } -/* Perform fast DCE once initialization is done. */ +/* Perform fast DCE once initialization is done. If WORD_LEVEL is + true, use the word level dce, otherwise do it at the pseudo + level. */ static void -fast_dce (void) +fast_dce (bool word_level) { int *postorder = df_get_postorder (DF_BACKWARD); int n_blocks = df_get_n_blocks (DF_BACKWARD); @@ -676,7 +950,15 @@ fast_dce (void) bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack); bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack); bool global_changed = true; - int i, loop_count = 0; + + /* 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); @@ -686,6 +968,7 @@ fast_dce (void) while (global_changed) { global_changed = false; + for (i = 0; i < n_blocks; i++) { int index = postorder[i]; @@ -698,10 +981,15 @@ fast_dce (void) continue; } - local_changed - = dce_process_block (bb, bitmap_bit_p (redo_out, index)); + if (word_level) + local_changed + = word_dce_process_block (bb, bitmap_bit_p (redo_out, index)); + 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) { edge e; @@ -717,7 +1005,7 @@ fast_dce (void) bitmap_set_bit (redo_out, e->src->index); } } - + if (global_changed) { /* Turn off the RUN_DCE flag to prevent recursive calls to @@ -730,18 +1018,21 @@ fast_dce (void) sbitmap_zero (marked); bitmap_clear (processed); bitmap_clear (redo_out); - + /* We do not need to rescan any instructions. We only need 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); + iteration. */ + if (word_level) + df_analyze_problem (df_word_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); + prescan_insns_for_dce (true); } - loop_count++; } delete_unmarked_insns (); @@ -752,18 +1043,39 @@ fast_dce (void) } -/* 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. */ + +void +run_word_dce (void) +{ + int old_flags; + + if (!flag_dce) + return; + + timevar_push (TV_DCE); + old_flags = df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN); + df_word_lr_add_problem (); + init_dce (true); + fast_dce (true); + fini_dce (true); + df_set_flags (old_flags); + timevar_pop (TV_DCE); +} + + /* This is an internal call that is used by the df live register problem to run fast dce as a side effect of creating the live information. The stack is organized so that the lr problem is run, @@ -781,9 +1093,9 @@ run_fast_df_dce (void) /* If dce is able to delete something, it has to happen immediately. Otherwise there will be problems handling the eq_notes. */ - enum df_changeable_flags old_flags - = df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN); - + int old_flags = + df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN); + df_in_progress = true; rest_of_handle_fast_dce (); df_in_progress = false; @@ -793,25 +1105,28 @@ run_fast_df_dce (void) } -static bool -gate_fast_dce (void) +/* Run a fast DCE pass. */ + +void +run_fast_dce (void) { - return optimize > 0 && flag_dce; + if (flag_dce) + rest_of_handle_fast_dce (); } -/* Run a fast DCE pass and return true if any instructions were deleted. */ - -bool -run_fast_dce (void) +static bool +gate_fast_dce (void) { - return gate_fast_dce () && (rest_of_handle_fast_dce (), something_changed); + return optimize > 0 && flag_dce + && dbg_cnt (dce_fast); } - -struct tree_opt_pass pass_fast_rtl_dce = +struct rtl_opt_pass pass_fast_rtl_dce = { - "dce", /* name */ + { + RTL_PASS, + "rtl_dce", /* name */ gate_fast_dce, /* gate */ rest_of_handle_fast_dce, /* execute */ NULL, /* sub */ @@ -822,8 +1137,7 @@ struct tree_opt_pass pass_fast_rtl_dce = 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 */ - 'w' /* letter */ + TODO_ggc_collect /* todo_flags_finish */ + } };