/* RTL dead store elimination.
- Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
Contributed by Richard Sandiford <rsandifor@codesourcery.com>
and Kenneth Zadeck <zadeck@naturalbridge.com>
#include "tm.h"
#include "rtl.h"
#include "tree.h"
+#include "tm_p.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"
/* An bitmask as wide as the number of bytes in the word that
contains a 1 if the byte may be needed. The store is unused if
all of the bits are 0. */
- long positions_needed;
+ unsigned HOST_WIDE_INT positions_needed;
/* The next store info for this insn. */
struct store_info *next;
rtx rhs;
};
+/* Return a bitmask with the first N low bits set. */
+
+static unsigned HOST_WIDE_INT
+lowpart_bitmask (int n)
+{
+ unsigned HOST_WIDE_INT mask = ~(unsigned HOST_WIDE_INT) 0;
+ return mask >> (HOST_BITS_PER_WIDE_INT - n);
+}
+
typedef struct store_info *store_info_t;
static alloc_pool cse_store_info_pool;
static alloc_pool rtx_store_info_pool;
/* The linked list of insns that are in consideration for removal in
the forwards pass thru the basic block. This pointer may be
trash as it is not cleared when a wild read occurs. The only
- time it is guaranteed to be correct is when the traveral starts
+ time it is guaranteed to be correct is when the traversal starts
at active_local_stores. */
struct insn_info * next_local_store;
};
static alloc_pool clear_alias_mode_pool;
-/* This is true except for two cases:
- (1) current_function_stdarg -- i.e. we cannot do this
- for vararg functions because they play games with the frame.
- (2) In ada, it is sometimes not safe to do assume that any stores
- based off the stack frame go dead at the exit to a function. */
+/* This is true except if cfun->stdarg -- i.e. we cannot do
+ this for vararg functions because they play games with the frame. */
static bool stores_off_frame_dead_at_return;
/* Counter for stats. */
static bool gate_dse (void);
+static bool gate_dse1 (void);
+static bool gate_dse2 (void);
\f
/*----------------------------------------------------------------------------
slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT);
gcc_assert (*slot);
- return *slot;
+ return (struct clear_alias_mode_holder *) *slot;
}
{
if (!clear_alias_group)
{
- clear_alias_group = gi = pool_alloc (rtx_group_info_pool);
+ clear_alias_group = gi =
+ (group_info_t) pool_alloc (rtx_group_info_pool);
memset (gi, 0, sizeof (struct group_info));
gi->id = rtx_group_next_id++;
gi->store1_n = BITMAP_ALLOC (NULL);
if (gi == NULL)
{
- *slot = gi = pool_alloc (rtx_group_info_pool);
+ *slot = gi = (group_info_t) pool_alloc (rtx_group_info_pool);
gi->rtx_base = base;
gi->id = rtx_group_next_id++;
gi->base_mem = gen_rtx_MEM (QImode, base);
bb_table = XCNEWVEC (bb_info_t, last_basic_block);
rtx_group_next_id = 0;
- stores_off_frame_dead_at_return =
- (!(TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE
- && (TYPE_RETURNS_STACK_DEPRESSED (TREE_TYPE (current_function_decl)))))
- && (!current_function_stdarg);
+ stores_off_frame_dead_at_return = !cfun->stdarg;
init_alias_analysis ();
{
rtx r1 = XEXP (x, 0);
rtx c = gen_int_mode (Pmode, data->size);
- add_insn_before (data->insn,
- gen_rtx_SET (Pmode, r1,
- gen_rtx_PLUS (Pmode, r1, c)),
- NULL);
+ emit_insn_before (gen_rtx_SET (Pmode, r1,
+ gen_rtx_PLUS (Pmode, r1, c)),
+ data->insn);
return -1;
}
{
rtx r1 = XEXP (x, 0);
rtx c = gen_int_mode (Pmode, -data->size);
- add_insn_before (data->insn,
- gen_rtx_SET (Pmode, r1,
- gen_rtx_PLUS (Pmode, r1, c)),
- NULL);
+ emit_insn_before (gen_rtx_SET (Pmode, r1,
+ gen_rtx_PLUS (Pmode, r1, c)),
+ data->insn);
return -1;
}
insn that contained it. */
rtx add = XEXP (x, 0);
rtx r1 = XEXP (add, 0);
- add_insn_before (data->insn,
- gen_rtx_SET (Pmode, r1, add), NULL);
+ emit_insn_before (gen_rtx_SET (Pmode, r1, add), data->insn);
return -1;
}
replace_inc_dec_mem (rtx *r, void *d)
{
rtx x = *r;
- if (GET_CODE (x) == MEM)
+ if (x != NULL_RTX && MEM_P (x))
{
struct insn_size data;
data.size = GET_MODE_SIZE (GET_MODE (x));
- data.insn = (rtx)d;
+ data.insn = (rtx) d;
for_each_rtx (&XEXP (x, 0), replace_inc_dec, &data);
if (clear_alias_group->offset_map_size_p < spill_alias_set)
clear_alias_group->offset_map_size_p = spill_alias_set;
- store_info = pool_alloc (rtx_store_info_pool);
+ store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
if (dump_file)
fprintf (dump_file, " processing spill store %d(%s)\n",
group_info_t group
= VEC_index (group_info_t, rtx_group_vec, group_id);
- store_info = pool_alloc (rtx_store_info_pool);
+ store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
set_usage_bits (group, offset, width);
if (dump_file)
insn_info->stack_pointer_based = true;
insn_info->contains_cselib_groups = true;
- store_info = pool_alloc (cse_store_info_pool);
+ store_info = (store_info_t) pool_alloc (cse_store_info_pool);
group_id = -1;
if (dump_file)
{
insn_info_t next = ptr->next_local_store;
store_info_t s_info = ptr->store_rec;
- bool delete = true;
+ bool del = true;
/* Skip the clobbers. We delete the active insn if this insn
shadows the set. To have been put on the active list, it
s_info = s_info->next;
if (s_info->alias_set != spill_alias_set)
- delete = false;
+ del = false;
else if (s_info->alias_set)
{
struct clear_alias_mode_holder *entry
if ((GET_MODE (mem) == GET_MODE (s_info->mem))
&& (GET_MODE (mem) == entry->mode))
{
- delete = true;
- s_info->positions_needed = 0;
+ del = true;
+ s_info->positions_needed = (unsigned HOST_WIDE_INT) 0;
}
if (dump_file)
fprintf (dump_file, " trying spill store in insn=%d alias_set=%d\n",
(int)s_info->begin, (int)s_info->end);
for (i = offset; i < offset+width; i++)
if (i >= s_info->begin && i < s_info->end)
- s_info->positions_needed &= ~(1L << (i - s_info->begin));
+ s_info->positions_needed
+ &= ~(((unsigned HOST_WIDE_INT) 1) << (i - s_info->begin));
}
else if (s_info->rhs)
/* Need to see if it is possible for this store to overwrite
/* An insn can be deleted if every position of every one of
its s_infos is zero. */
- if (s_info->positions_needed != 0)
- delete = false;
+ if (s_info->positions_needed != (unsigned HOST_WIDE_INT) 0)
+ del = false;
- if (delete)
+ if (del)
{
insn_info_t insn_to_delete = ptr;
ptr = next;
}
- gcc_assert ((unsigned) width < sizeof (store_info->positions_needed) * CHAR_BIT);
+ gcc_assert ((unsigned) width <= HOST_BITS_PER_WIDE_INT);
/* Finish filling in the store_info. */
store_info->next = insn_info->store_rec;
store_info->alias_set = spill_alias_set;
store_info->mem_addr = get_addr (XEXP (mem, 0));
store_info->cse_base = base;
- store_info->positions_needed = (1L << width) - 1;
+ store_info->positions_needed = lowpart_bitmask (width);
store_info->group_id = group_id;
store_info->begin = offset;
store_info->end = offset + width;
if (store_info->is_set
/* No place to keep the value after ra. */
&& !reload_completed
- /* The careful reviewer may wish to comment my checking that the
- rhs of a store is always a reg. */
- && REG_P (SET_SRC (body))
+ && (REG_P (SET_SRC (body))
+ || GET_CODE (SET_SRC (body)) == SUBREG
+ || CONSTANT_P (SET_SRC (body)))
/* Sometimes the store and reload is used for truncation and
rounding. */
&& !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
shift. */
static rtx
-find_shift_sequence (rtx read_reg,
- int access_size,
+find_shift_sequence (int access_size,
store_info_t store_info,
read_info_t read_info,
- int shift)
+ int shift,
+ bool speed)
{
enum machine_mode store_mode = GET_MODE (store_info->mem);
enum machine_mode read_mode = GET_MODE (read_info->mem);
- rtx chosen_seq = NULL;
+ enum machine_mode new_mode;
+ rtx read_reg = NULL;
/* Some machines like the x86 have shift insns for each size of
operand. Other machines like the ppc or the ia-64 may only have
justify the value we want to read but is available in one insn on
the machine. */
- for (; access_size <= UNITS_PER_WORD; access_size *= 2)
+ for (new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
+ MODE_INT);
+ GET_MODE_BITSIZE (new_mode) <= BITS_PER_WORD;
+ new_mode = GET_MODE_WIDER_MODE (new_mode))
{
- rtx target, new_reg, shift_seq, insn;
- enum machine_mode new_mode;
+ rtx target, new_reg, shift_seq, insn, new_lhs;
int cost;
- /* Try a wider mode if truncating the store mode to ACCESS_SIZE
- bytes requires a real instruction. */
- if (access_size < GET_MODE_SIZE (store_mode)
- && !TRULY_NOOP_TRUNCATION (access_size * BITS_PER_UNIT,
+ /* Try a wider mode if truncating the store mode to NEW_MODE
+ requires a real instruction. */
+ if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode)
+ && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (new_mode),
GET_MODE_BITSIZE (store_mode)))
continue;
- new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
- GET_MODE_CLASS (read_mode));
+ /* Also try a wider mode if the necessary punning is either not
+ desirable or not possible. */
+ if (!CONSTANT_P (store_info->rhs)
+ && !MODES_TIEABLE_P (new_mode, store_mode))
+ continue;
+
new_reg = gen_reg_rtx (new_mode);
start_sequence ();
cost = 0;
for (insn = shift_seq; insn != NULL_RTX; insn = NEXT_INSN (insn))
if (INSN_P (insn))
- cost += insn_rtx_cost (PATTERN (insn));
+ cost += insn_rtx_cost (PATTERN (insn), speed);
/* The computation up to here is essentially independent
of the arguments and could be precomputed. It may
not be worth doing so. We could precompute if
worthwhile or at least cache the results. The result
- technically depends on SHIFT, ACCESS_SIZE, and
- GET_MODE_CLASS (READ_MODE). But in practice the
- answer will depend only on ACCESS_SIZE. */
+ technically depends on both SHIFT and ACCESS_SIZE,
+ but in practice the answer will depend only on ACCESS_SIZE. */
if (cost > COSTS_N_INSNS (1))
continue;
+ new_lhs = extract_low_bits (new_mode, store_mode,
+ copy_rtx (store_info->rhs));
+ if (new_lhs == NULL_RTX)
+ continue;
+
/* We found an acceptable shift. Generate a move to
take the value from the store and put it into the
shift pseudo, then shift it, then generate another
move to put in into the target of the read. */
- start_sequence ();
- emit_move_insn (new_reg, gen_lowpart (new_mode, store_info->rhs));
+ emit_move_insn (new_reg, new_lhs);
emit_insn (shift_seq);
- convert_move (read_reg, new_reg, 1);
-
- if (dump_file)
- {
- fprintf (dump_file, " -- adding extract insn r%d:%s = r%d:%s\n",
- REGNO (new_reg), GET_MODE_NAME (new_mode),
- REGNO (store_info->rhs), GET_MODE_NAME (store_mode));
-
- fprintf (dump_file, " -- with shift of r%d by %d\n",
- REGNO(new_reg), shift);
- fprintf (dump_file, " -- and second extract insn r%d:%s = r%d:%s\n",
- REGNO (read_reg), GET_MODE_NAME (read_mode),
- REGNO (new_reg), GET_MODE_NAME (new_mode));
- }
-
- /* Get the three insn sequence and return it. */
- chosen_seq = get_insns ();
- end_sequence ();
+ read_reg = extract_low_bits (read_mode, new_mode, new_reg);
break;
}
- return chosen_seq;
+ return read_reg;
}
enum machine_mode read_mode = GET_MODE (read_info->mem);
int shift;
int access_size; /* In bytes. */
- rtx read_reg = gen_reg_rtx (read_mode);
- rtx shift_seq = NULL;
+ rtx insns, read_reg;
if (!dbg_cnt (dse))
return false;
- if (GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode))
- return false;
-
/* To get here the read is within the boundaries of the write so
shift will never be negative. Start out with the shift being in
bytes. */
/* From now on it is bits. */
shift *= BITS_PER_UNIT;
- /* We need to keep this in perspective. We are replacing a read
+ /* Create a sequence of instructions to set up the read register.
+ This sequence goes immediately before the store and its result
+ is read by the load.
+
+ We need to keep this in perspective. We are replacing a read
with a sequence of insns, but the read will almost certainly be
in cache, so it is not going to be an expensive one. Thus, we
are not willing to do a multi insn shift or worse a subroutine
call to get rid of the read. */
+ if (dump_file)
+ fprintf (dump_file, "trying to replace %smode load in insn %d"
+ " from %smode store in insn %d\n",
+ GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
+ GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
+ start_sequence ();
if (shift)
+ read_reg = find_shift_sequence (access_size, store_info, read_info, shift,
+ optimize_bb_for_speed_p (BLOCK_FOR_INSN (read_insn->insn)));
+ else
+ read_reg = extract_low_bits (read_mode, store_mode,
+ copy_rtx (store_info->rhs));
+ if (read_reg == NULL_RTX)
{
- if (access_size > UNITS_PER_WORD || FLOAT_MODE_P (store_mode))
- return false;
-
- shift_seq = find_shift_sequence (read_reg, access_size, store_info,
- read_info, shift);
- if (!shift_seq)
- return false;
+ end_sequence ();
+ if (dump_file)
+ fprintf (dump_file, " -- could not extract bits of stored value\n");
+ return false;
}
-
- if (dump_file)
- fprintf (dump_file, "replacing load at %d from store at %d\n",
- INSN_UID (read_insn->insn), INSN_UID (store_insn->insn));
+ /* Force the value into a new register so that it won't be clobbered
+ between the store and the load. */
+ read_reg = copy_to_mode_reg (read_mode, read_reg);
+ insns = get_insns ();
+ end_sequence ();
if (validate_change (read_insn->insn, loc, read_reg, 0))
{
- rtx insns;
- deferred_change_t deferred_change = pool_alloc (deferred_change_pool);
+ deferred_change_t deferred_change =
+ (deferred_change_t) pool_alloc (deferred_change_pool);
- if (read_mode == store_mode)
- {
- start_sequence ();
-
- /* The modes are the same and everything lines up. Just
- generate a simple move. */
- emit_move_insn (read_reg, store_info->rhs);
- if (dump_file)
- fprintf (dump_file, " -- adding move insn r%d = r%d\n",
- REGNO (read_reg), REGNO (store_info->rhs));
- insns = get_insns ();
- end_sequence ();
- }
- else if (shift)
- insns = shift_seq;
- else
- {
- /* The modes are different but the lsb are in the same
- place, we need to extract the value in the right from the
- rhs of the store. */
- start_sequence ();
- convert_move (read_reg, store_info->rhs, 1);
-
- if (dump_file)
- fprintf (dump_file, " -- adding extract insn r%d:%s = r%d:%s\n",
- REGNO (read_reg), GET_MODE_NAME (read_mode),
- REGNO (store_info->rhs), GET_MODE_NAME (store_mode));
- insns = get_insns ();
- end_sequence ();
- }
-
/* Insert this right before the store insn where it will be safe
from later insns that might change it before the read. */
emit_insn_before (insns, store_insn->insn);
rest of dse, play like this read never happened. */
read_insn->read_rec = read_info->next;
pool_free (read_info_pool, read_info);
+ if (dump_file)
+ {
+ fprintf (dump_file, " -- replaced the loaded MEM with ");
+ print_simple_rtl (dump_file, read_reg);
+ fprintf (dump_file, "\n");
+ }
return true;
}
else
{
if (dump_file)
- fprintf (dump_file, " -- validation failure\n");
+ {
+ fprintf (dump_file, " -- replacing the loaded MEM with ");
+ print_simple_rtl (dump_file, read_reg);
+ fprintf (dump_file, " led to an invalid instruction\n");
+ }
return false;
}
}
else
width = GET_MODE_SIZE (GET_MODE (mem));
- read_info = pool_alloc (read_info_pool);
+ read_info = (read_info_t) pool_alloc (read_info_pool);
read_info->group_id = group_id;
read_info->mem = mem;
read_info->alias_set = spill_alias_set;
&& (offset >= store_info->begin)
&& (offset + width <= store_info->end))
{
- int mask = ((1L << width) - 1) << (offset - store_info->begin);
-
+ unsigned HOST_WIDE_INT mask
+ = (lowpart_bitmask (width)
+ << (offset - store_info->begin));
+
if ((store_info->positions_needed & mask) == mask
&& replace_read (store_info, i_ptr,
read_info, insn_info, loc))
&& (offset >= store_info->begin)
&& (offset + width <= store_info->end))
{
- int mask = ((1L << width) - 1) << (offset - store_info->begin);
-
+ unsigned HOST_WIDE_INT mask
+ = (lowpart_bitmask (width)
+ << (offset - store_info->begin));
+
if ((store_info->positions_needed & mask) == mask
&& replace_read (store_info, i_ptr,
read_info, insn_info, loc))
scan_insn (bb_info_t bb_info, rtx insn)
{
rtx body;
- insn_info_t insn_info = pool_alloc (insn_info_pool);
+ insn_info_t insn_info = (insn_info_t) pool_alloc (insn_info_pool);
int mems_found = 0;
memset (insn_info, 0, sizeof (struct insn_info));
/* Const functions cannot do anything bad i.e. read memory,
however, they can read their parameters which may have
been pushed onto the stack. */
- if (CONST_OR_PURE_CALL_P (insn) && !pure_call_p (insn))
+ if (RTL_CONST_CALL_P (insn))
{
insn_info_t i_ptr = active_local_stores;
insn_info_t last = NULL;
while (insn_info)
{
store_info_t store_info = insn_info->store_rec;
- bool delete = false;
+ bool del = false;
/* If ANY of the store_infos match the cselib group that is
being deleted, then the insn can not be deleted. */
if ((store_info->group_id == -1)
&& (store_info->cse_base == base))
{
- delete = true;
+ del = true;
break;
}
store_info = store_info->next;
}
- if (delete)
+ if (del)
{
if (last)
last->next_local_store = insn_info->next_local_store;
FOR_ALL_BB (bb)
{
insn_info_t ptr;
- bb_info_t bb_info = pool_alloc (bb_info_pool);
+ bb_info_t bb_info = (bb_info_t) pool_alloc (bb_info_pool);
memset (bb_info, 0, sizeof (struct bb_info));
bitmap_set_bit (all_blocks, bb->index);
&& (EDGE_COUNT (bb->succs) == 0
|| (single_succ_p (bb)
&& single_succ (bb) == EXIT_BLOCK_PTR
- && ! current_function_calls_eh_return)))
+ && ! crtl->calls_eh_return)))
{
insn_info_t i_ptr = active_local_stores;
while (i_ptr)
slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, INSERT);
gcc_assert (*slot == NULL);
- *slot = entry = pool_alloc (clear_alias_mode_pool);
+ *slot = entry =
+ (struct clear_alias_mode_holder *) pool_alloc (clear_alias_mode_pool);
entry->alias_set = alias_set;
entry->mode = mode;
}
group_info_t group;
basic_block bb;
- if (global_done)
- {
- for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
- {
- free (group->offset_map_n);
- free (group->offset_map_p);
- BITMAP_FREE (group->store1_n);
- BITMAP_FREE (group->store1_p);
- BITMAP_FREE (group->store2_n);
- BITMAP_FREE (group->store2_p);
- BITMAP_FREE (group->group_kill);
- }
-
- FOR_ALL_BB (bb)
- {
- bb_info_t bb_info = bb_table[bb->index];
- BITMAP_FREE (bb_info->gen);
- if (bb_info->kill)
- BITMAP_FREE (bb_info->kill);
- if (bb_info->in)
- BITMAP_FREE (bb_info->in);
- if (bb_info->out)
- BITMAP_FREE (bb_info->out);
- }
- }
- else
+ for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
{
- for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
- {
- BITMAP_FREE (group->store1_n);
- BITMAP_FREE (group->store1_p);
- BITMAP_FREE (group->store2_n);
- BITMAP_FREE (group->store2_p);
- BITMAP_FREE (group->group_kill);
- }
+ free (group->offset_map_n);
+ free (group->offset_map_p);
+ BITMAP_FREE (group->store1_n);
+ BITMAP_FREE (group->store1_p);
+ BITMAP_FREE (group->store2_n);
+ BITMAP_FREE (group->store2_p);
+ BITMAP_FREE (group->group_kill);
}
+ if (global_done)
+ FOR_ALL_BB (bb)
+ {
+ bb_info_t bb_info = bb_table[bb->index];
+ BITMAP_FREE (bb_info->gen);
+ if (bb_info->kill)
+ BITMAP_FREE (bb_info->kill);
+ if (bb_info->in)
+ BITMAP_FREE (bb_info->in);
+ if (bb_info->out)
+ BITMAP_FREE (bb_info->out);
+ }
+
if (clear_alias_sets)
{
BITMAP_FREE (clear_alias_sets);
}
-
/* -------------------------------------------------------------------------
DSE
------------------------------------------------------------------------- */
static bool
gate_dse (void)
{
- return optimize > 0 && flag_dse;
+ return gate_dse1 () || gate_dse2 ();
+}
+
+static bool
+gate_dse1 (void)
+{
+ return optimize > 0 && flag_dse
+ && dbg_cnt (dse1);
+}
+
+static bool
+gate_dse2 (void)
+{
+ return optimize > 0 && flag_dse
+ && dbg_cnt (dse2);
}
-struct tree_opt_pass pass_rtl_dse1 =
+struct rtl_opt_pass pass_rtl_dse1 =
{
+ {
+ RTL_PASS,
"dse1", /* name */
- gate_dse, /* gate */
+ gate_dse1, /* gate */
rest_of_handle_dse, /* execute */
NULL, /* sub */
NULL, /* next */
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 */
+ }
};
-struct tree_opt_pass pass_rtl_dse2 =
+struct rtl_opt_pass pass_rtl_dse2 =
{
+ {
+ RTL_PASS,
"dse2", /* name */
- gate_dse, /* gate */
+ gate_dse2, /* gate */
rest_of_handle_dse, /* execute */
NULL, /* sub */
NULL, /* next */
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 */
+ }
};