/* 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.
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 2, or (at your option) any later
+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
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#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. */
/* -------------------------------------------------------------------------
Core mark/delete routines
------------------------------------------------------------------------- */
-/* The data-flow information needed by this pass. */
+/* True if we are invoked while the df engine is running; in this case,
+ 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;
+/* Bitmap of instructions marked as needed indexed by INSN_UID. */
+static sbitmap marked;
+
+/* Bitmap obstacks used for block processing by the fast algorithm. */
static bitmap_obstack dce_blocks_bitmap_obstack;
static bitmap_obstack dce_tmp_bitmap_obstack;
-static sbitmap marked = NULL;
+static bool find_call_stack_args (rtx, bool, bool, bitmap);
-/* Return true if INSN a normal instruction that can be deleted by the
- DCE pass. */
+/* A subroutine for which BODY is part of the instruction being tested;
+ either the top-level pattern, or an element of a PARALLEL. The
+ instruction is known not to be a bare USE or CLOBBER. */
static bool
-deletable_insn_p (rtx insn, bool fast)
+deletable_insn_p_1 (rtx body)
{
- rtx x;
-
- switch (GET_CODE (PATTERN (insn)))
+ switch (GET_CODE (body))
{
- case USE:
case PREFETCH:
case TRAP_IF:
/* The UNSPEC case was added here because the ia-64 claims that
case UNSPEC:
return false;
+ default:
+ return !volatile_refs_p (body);
+ }
+}
+
+
+/* Return true if INSN is a normal instruction that can be deleted by
+ the DCE pass. */
+
+static bool
+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:
if (fast)
{
/* A CLOBBER of a dead pseudo register serves no purpose.
That is not necessarily true for hard registers until
after reload. */
- x = XEXP (PATTERN (insn), 0);
+ x = XEXP (body, 0);
return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed);
}
- else
+ else
/* Because of the way that use-def chains are built, it is not
possible to tell if the clobber is dead because it can
never be the target of a use-def chain. */
return false;
- default:
- if (!NONJUMP_INSN_P (insn))
- return false;
-
- if (volatile_insn_p (PATTERN (insn)))
- return false;
-
- if (flag_non_call_exceptions && may_trap_p (PATTERN (insn)))
- return false;
-
+ case PARALLEL:
+ for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
+ if (!deletable_insn_p_1 (XVECEXP (body, 0, i)))
+ return false;
return true;
+
+ default:
+ return deletable_insn_p_1 (body);
}
}
-/* Return true if INSN has not been marked as needed. */
+/* Return true if INSN has been marked as needed. */
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));
}
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);
}
}
instruction containing DEST. */
static void
-mark_nonreg_stores_1 (rtx dest, rtx pattern, void *data)
+mark_nonreg_stores_1 (rtx dest, const_rtx pattern, void *data)
{
if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
mark_insn ((rtx) data, true);
instruction containing DEST. */
static void
-mark_nonreg_stores_2 (rtx dest, rtx pattern, void *data)
+mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data)
{
if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
mark_insn ((rtx) data, false);
}
-/* Initialize global variables for a new DCE pass. */
+/* 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
-init_dce (bool fast)
+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)
{
- if (!df_in_progress)
+ HOST_WIDE_INT byte;
+ for (byte = off; byte < off + GET_MODE_SIZE (GET_MODE (mem)); byte++)
{
- if (!fast)
- df_chain_add_problem (DF_UD_CHAIN);
- df_analyze ();
+ if (byte < min_sp_off
+ || byte >= max_sp_off
+ || !bitmap_clear_bit (sp_bytes, byte - min_sp_off))
+ return false;
}
-
- if (dump_file)
- df_dump (dump_file);
-
- bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
- bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
- marked = sbitmap_alloc (get_max_uid () + 1);
- sbitmap_zero (marked);
+ return true;
}
-/* Delete all REG_EQUAL notes of the registers INSN writes, to prevent
- bad dangling REG_EQUAL notes. */
+/* 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_corresponding_reg_eq_notes (rtx insn)
+static bool
+find_call_stack_args (rtx call_insn, bool do_mark, bool fast,
+ bitmap arg_stores)
{
- struct df_ref **def_rec;
- for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
+ 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;
+ 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)
{
- 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))
+ 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)))
{
- 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);
+ 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
+ || !check_argument_store (mem, off, min_sp_off,
+ max_sp_off, sp_bytes))
+ 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 every instruction that hasn't been marked. Clear the insn
- from DCE_DF if DF_DELETE is true. */
+/* Remove all REG_EQUAL and REG_EQUIV notes referring to the registers INSN
+ writes to. */
static void
-delete_unmarked_insns (void)
+remove_reg_equal_equiv_notes_for_defs (rtx insn)
+{
+ df_ref *def_rec;
+
+ for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
+ remove_reg_equal_equiv_notes_for_regno (DF_REF_REGNO (*def_rec));
+}
+
+/* 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;
- something_changed = false;
- FOR_EACH_BB (bb)
- FOR_BB_INSNS_SAFE (bb, insn, next)
- if (INSN_P (insn))
+ FOR_EACH_BB_REVERSE (bb)
+ FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
+ if (DEBUG_INSN_P (insn))
{
- if (noop_move_p (insn))
+ df_ref *use_rec;
+
+ for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
{
- /* 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))
+ df_ref use = *use_rec;
+ struct df_link *defs;
+ for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
{
- 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;
+ 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;
}
+ }
+}
+
+/* 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))
+ {
+ /* Always delete no-op moves. */
+ if (noop_move_p (insn))
+ ;
+
+ /* Otherwise rely only on the DCE algorithm. */
else if (marked_insn_p (insn))
continue;
- /* 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. */
+ /* 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 delete
- REG_EQUAL of the destination regs of the deleted insn
- to prevent dangling REG_EQUAL. */
- delete_corresponding_reg_eq_notes (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);
- something_changed = true;
}
-}
-
-/* Mark all insns using DELETE_PARM in the libcall that contains
- START_INSN. */
-static void
-mark_libcall (rtx start_insn, bool delete_parm)
-{
- rtx note = find_reg_note (start_insn, REG_LIBCALL_ID, NULL_RTX);
- int id = INTVAL (XEXP (note, 0));
- rtx insn;
-
- mark_insn (start_insn, delete_parm);
- insn = NEXT_INSN (start_insn);
-
- /* 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))
- {
- /* 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 forward libcall %d[%d]\n",
- INSN_UID (insn), id);
- }
- }
- else
- break;
- }
- }
-
- for (insn = PREV_INSN (start_insn); insn; insn = PREV_INSN (insn))
- {
- if (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;
- }
- }
+ /* Deleted a pure or const call. */
+ if (must_clean)
+ delete_unreachable_blocks ();
}
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");
/* UD-based DSE routines. */
-/* Mark instructions that define artifically-used registers, such as
+/* Mark instructions that define artificially-used registers, such as
the frame pointer and the stack pointer. */
static 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);
}
}
+
/* Mark every instruction that defines a register value that INSN uses. */
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 ");
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);
+ }
+}
+
+
+/* Initialize global variables for a new DCE pass. */
+
+static void
+init_dce (bool fast)
+{
+ if (!df_in_progress)
+ {
+ if (!fast)
+ df_chain_add_problem (DF_UD_CHAIN);
+ df_analyze ();
+ }
+
+ if (dump_file)
+ df_dump (dump_file);
+
+ if (fast)
+ {
+ bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
+ bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
}
+
+ marked = sbitmap_alloc (get_max_uid () + 1);
+ sbitmap_zero (marked);
}
+/* Free the data allocated by init_dce. */
+
static void
-end_ud_dce (void)
+fini_dce (bool fast)
{
sbitmap_free (marked);
- gcc_assert (VEC_empty (rtx, worklist));
+
+ if (fast)
+ {
+ bitmap_obstack_release (&dce_blocks_bitmap_obstack);
+ bitmap_obstack_release (&dce_tmp_bitmap_obstack);
+ }
}
{
rtx insn;
- df_in_progress = false;
init_dce (false);
prescan_insns_for_dce (false);
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. */
df_remove_problem (df_chain);
delete_unmarked_insns ();
- end_ud_dce ();
+ fini_dce (false);
return 0;
}
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 */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func |
- TODO_df_finish |
- TODO_ggc_collect, /* todo_flags_finish */
- 'w' /* letter */
+ TODO_df_finish | TODO_verify_rtl_sharing |
+ TODO_ggc_collect /* todo_flags_finish */
+ }
};
+
/* -------------------------------------------------------------------------
Fast DCE functions
------------------------------------------------------------------------- */
+/* 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. */
-/* Free the data allocated by init_dce. */
-
-static void
-fini_dce (void)
+static bool
+word_dce_process_block (basic_block bb, bool redo_out)
{
- sbitmap_free (marked);
- bitmap_obstack_release (&dce_blocks_bitmap_obstack);
- bitmap_obstack_release (&dce_tmp_bitmap_obstack);
- df_in_progress = false;
+ bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
+ rtx insn;
+ bool block_changed;
+
+ if (redo_out)
+ {
+ /* 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_word_lr->problem->con_fun_n;
+ bitmap_clear (DF_WORD_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_word_regset (dump_file, DF_WORD_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);
+
+ /* 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. */
+ 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)
+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, **use_rec;
- unsigned int bb_index = bb->index;
+ df_ref *def_rec;
if (redo_out)
{
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));
- /* 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++)
- {
- 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));
- }
-
- for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
- {
- 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));
- }
+ 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)))
- {
- 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)
return block_changed;
}
+
+/* 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);
- int i;
/* The set of blocks that have been seen on this iteration. */
bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
/* The set of blocks that need to have the out vectors reset because
bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
bool global_changed = true;
- int 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);
while (global_changed)
{
global_changed = false;
+
for (i = 0; i < n_blocks; i++)
{
int index = postorder[i];
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;
bitmap_set_bit (redo_out, e->src->index);
}
}
-
+
if (global_changed)
{
/* Turn off the RUN_DCE flag to prevent recursive calls to
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 ();
}
-/* Callback for running pass_rtl_dce. */
+/* Fast register level DCE. */
static unsigned int
rest_of_handle_fast_dce (void)
{
init_dce (true);
- fast_dce ();
- fini_dce ();
- df_in_progress = false;
+ 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,
info, and then returns to allow the rest of the problems to be run.
This can be called by elsewhere but it will not update the bit
- vectors for any other problems than LR.
-*/
+ vectors for any other problems than LR. */
void
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;
+
df_set_flags (old_flags);
}
}
-static bool
-gate_fast_dce (void)
-{
- return optimize > 0 && flag_dce;
-}
-
-/* Run a fast DCE pass and return true if any instructions were
- deleted. */
+/* Run a fast DCE pass. */
-bool
+void
run_fast_dce (void)
{
- return gate_fast_dce () && (rest_of_handle_fast_dce (), something_changed);
+ if (flag_dce)
+ rest_of_handle_fast_dce ();
}
-struct tree_opt_pass pass_fast_rtl_dce =
+static bool
+gate_fast_dce (void)
{
- "dce", /* name */
+ return optimize > 0 && flag_dce
+ && dbg_cnt (dce_fast);
+}
+
+struct rtl_opt_pass pass_fast_rtl_dce =
+{
+ {
+ RTL_PASS,
+ "rtl_dce", /* name */
gate_fast_dce, /* gate */
rest_of_handle_fast_dce, /* execute */
NULL, /* sub */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func |
- TODO_df_finish |
- TODO_ggc_collect, /* todo_flags_finish */
- 'w' /* letter */
+ TODO_df_finish | TODO_verify_rtl_sharing |
+ TODO_ggc_collect /* todo_flags_finish */
+ }
};
-
OSDN Git Service
