X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fdce.c;h=855bef32237bc7511c9214297b9aa583c80b9cdd;hb=4ce12f0156e9df62da3049b9c4aa7ec7fb7af153;hp=63ea3806606aede778a8ee6ccb5ae262cfc86997;hpb=ed6e85ae3c0cfeeab54eb3e7090170ea36bf949d;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/dce.c b/gcc/dce.c index 63ea3806606..855bef32237 100644 --- a/gcc/dce.c +++ b/gcc/dce.c @@ -1,5 +1,5 @@ /* RTL dead code elimination. - Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc. + Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc. This file is part of GCC. @@ -27,15 +27,14 @@ 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" /* ------------------------------------------------------------------------- @@ -57,6 +56,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 @@ -79,13 +79,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); } } @@ -94,11 +88,19 @@ 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; + /* 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; + 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 @@ -111,15 +113,13 @@ deletable_insn_p (rtx insn, bool fast) 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; + return find_call_stack_args (insn, false, fast, arg_stores); body = PATTERN (insn); switch (GET_CODE (body)) { case USE: + case VAR_LOCATION: return false; case CLOBBER: @@ -174,6 +174,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); } } @@ -212,6 +218,253 @@ mark_nonreg_stores (rtx body, rtx insn, bool fast) } +/* 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 bool +find_call_stack_args (rtx call_insn, bool do_mark, bool fast, + bitmap arg_stores) +{ + rtx p, insn, prev_insn; + bool ret; + HOST_WIDE_INT min_sp_off, max_sp_off; + bitmap sp_bytes; + + gcc_assert (CALL_P (call_insn)); + if (!ACCUMULATE_OUTGOING_ARGS) + return true; + + 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, size; + HOST_WIDE_INT off = 0; + size = MEM_SIZE (mem); + if (size == NULL_RTX) + return false; + 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 + INTVAL (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 + INTVAL (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, byte; + + 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 (!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))) + { + off = INTVAL (XEXP (addr, 1)); + addr = XEXP (addr, 0); + } + if (addr != stack_pointer_rtx) + { + if (!REG_P (addr)) + break; + if (!fast) + { + 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 + break; + } + + if (GET_MODE_SIZE (GET_MODE (mem)) == 0) + break; + + for (byte = off; byte < off + GET_MODE_SIZE (GET_MODE (mem)); byte++) + { + if (byte < min_sp_off + || byte >= max_sp_off + || !bitmap_clear_bit (sp_bytes, byte - min_sp_off)) + break; + } + + if (!deletable_insn_p (insn, fast, NULL)) + break; + + if (do_mark) + mark_insn (insn, fast); + else + bitmap_set_bit (arg_stores, INSN_UID (insn)); + + if (bitmap_empty_p (sp_bytes)) + { + ret = true; + break; + } + } + + BITMAP_FREE (sp_bytes); + if (!ret && arg_stores) + bitmap_clear (arg_stores); + + return ret; +} + + /* Delete all REG_EQUAL notes of the registers INSN writes, to prevent bad dangling REG_EQUAL notes. */ @@ -254,8 +507,8 @@ delete_unmarked_insns (void) rtx insn, next; bool must_clean = false; - FOR_EACH_BB (bb) - FOR_BB_INSNS_SAFE (bb, insn, next) + FOR_EACH_BB_REVERSE (bb) + FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next) if (INSN_P (insn)) { /* Always delete no-op moves. */ @@ -266,6 +519,24 @@ delete_unmarked_insns (void) 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; @@ -300,20 +571,37 @@ static void prescan_insns_for_dce (bool fast) { basic_block bb; - rtx insn, next; - + 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_SAFE (bb, insn, next) - if (INSN_P (insn)) - { - 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 (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"); @@ -334,7 +622,7 @@ mark_artificial_uses (void) 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) if (! DF_REF_IS_ARTIFICIAL (defs->ref)) @@ -351,6 +639,9 @@ mark_reg_dependencies (rtx insn) struct df_link *defs; df_ref *use_rec; + if (DEBUG_INSN_P (insn)) + return; + for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++) { df_ref use = *use_rec; @@ -447,9 +738,9 @@ struct rtl_opt_pass pass_ud_rtl_dce = { { RTL_PASS, - "dce", /* name */ - gate_ud_dce, /* gate */ - rest_of_handle_ud_dce, /* execute */ + "ud dce", /* name */ + gate_ud_dce, /* gate */ + rest_of_handle_ud_dce, /* execute */ NULL, /* sub */ NULL, /* next */ 0, /* static_pass_number */ @@ -534,7 +825,7 @@ byte_dce_process_block (basic_block bb, bool redo_out, bitmap au) mark_insn (insn, true); goto quickexit; } - + last = start + len; while (start < last) if (bitmap_bit_p (local_live, start++)) @@ -543,9 +834,9 @@ byte_dce_process_block (basic_block bb, bool redo_out, bitmap au) goto quickexit; } } - - 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); @@ -557,12 +848,12 @@ byte_dce_process_block (basic_block bb, bool redo_out, bitmap au) if (dump_file) { - fprintf (dump_file, "finished processing insn %d live out = ", + 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)); @@ -601,13 +892,13 @@ dce_process_block (basic_block bb, bool redo_out, bitmap au) if (dump_file) { - fprintf (dump_file, "processing block %d live out = ", bb->index); + fprintf (dump_file, "processing block %d lr out = ", bb->index); df_print_regset (dump_file, DF_LR_OUT (bb)); } bitmap_copy (local_live, DF_LR_OUT (bb)); - df_simulate_artificial_refs_at_end (bb, local_live); + df_simulate_initialize_backwards (bb, local_live); FOR_BB_INSNS_REVERSE (bb, insn) if (INSN_P (insn)) @@ -622,10 +913,10 @@ dce_process_block (basic_block bb, bool redo_out, bitmap au) needed = true; break; } - + if (needed) mark_insn (insn, true); - + /* 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); @@ -635,8 +926,8 @@ dce_process_block (basic_block bb, bool redo_out, bitmap au) if (marked_insn_p (insn)) df_simulate_uses (insn, local_live); } - - df_simulate_artificial_refs_at_top (bb, local_live); + + df_simulate_finalize_backwards (bb, local_live); block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb)); if (block_changed) @@ -695,15 +986,15 @@ fast_dce (bool byte_level) } if (byte_level) - local_changed + local_changed = byte_dce_process_block (bb, bitmap_bit_p (redo_out, index), bb_has_eh_pred (bb) ? au_eh : au); else - local_changed + 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; @@ -719,7 +1010,7 @@ fast_dce (bool byte_level) bitmap_set_bit (redo_out, e->src->index); } } - + if (global_changed) { /* Turn off the RUN_DCE flag to prevent recursive calls to @@ -732,11 +1023,11 @@ fast_dce (bool byte_level) 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. */ + iteration. */ if (byte_level) df_analyze_problem (df_byte_lr, all_blocks, postorder, n_blocks); else @@ -799,9 +1090,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; @@ -832,7 +1123,7 @@ struct rtl_opt_pass pass_fast_rtl_dce = { { RTL_PASS, - "dce", /* name */ + "rtl dce", /* name */ gate_fast_dce, /* gate */ rest_of_handle_fast_dce, /* execute */ NULL, /* sub */