/* RTL dead store elimination.
- Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2006, 2007, 2008, 2009 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"
#include "dse.h"
#include "optabs.h"
#include "dbgcnt.h"
+#include "target.h"
/* This file contains three techniques for performing Dead Store
- Elimination (dse).
+ Elimination (dse).
* The first technique performs dse locally on any base address. It
is based on the cselib which is a local value numbering technique.
This technique is local to a basic block but deals with a fairly
general addresses.
-
+
* The second technique performs dse globally but is restricted to
base addresses that are either constant or are relative to the
frame_pointer.
stores, only one store to an address is necessary because those
stores die at the end of the function.
- 3) Set up the global dataflow equations based on processing the
+ 3) Set up the global dataflow equations based on processing the
info parsed in the first step.
4) Solve the dataflow equations.
5) Delete the insns that the global analysis has indicated are
unnecessary.
- 6) Cleanup.
+ 6) Delete insns that store the same value as preceeding store
+ where the earlier store couldn't be eliminated.
+
+ 7) Cleanup.
This step uses cselib and canon_rtx to build the largest expression
possible for each address. This pass is a forwards pass through
These are expensive and cumbersome in our bitmap formulation so
care has been taken to avoid large vectors filled with 1s. See
the comments in bb_info and in the dataflow confluence functions
- for details.
+ for details.
There are two places for further enhancements to this algorithm:
-
+
1) The original dse which was embedded in a pass called flow also
did local address forwarding. For example in
with the same mode and alias set. The backout in this case is a
little more graceful than (a). In this case the slot is unmarked
as being a spill slot and if final address comes out to be based
- off the frame pointer, the global algorithm handles this slot.
+ off the frame pointer, the global algorithm handles this slot.
c) For any pass that may prespill, there is currently no
mechanism to tell the dse pass that the slot being used has the
struct insn_info;
/* This structure holds information about a candidate store. */
-struct store_info
+struct store_info
{
/* False means this is a clobber. */
bool is_set;
+ /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */
+ bool is_large;
+
/* The id of the mem group of the base address. If rtx_varies_p is
true, this is -1. Otherwise, it is the index into the group
table. */
int group_id;
-
+
/* This is the cselib value. */
cselib_val *cse_base;
/* This canonized mem. */
rtx mem;
- /* The result of get_addr on mem. */
+ /* Canonized MEM address for use by canon_true_dependence. */
rtx mem_addr;
/* If this is non-zero, it is the alias set of a spill location. */
/* The offset of the first and byte before the last byte associated
with the operation. */
- int begin, end;
+ HOST_WIDE_INT begin, end;
+
+ union
+ {
+ /* A 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. This is used if IS_LARGE is false. */
+ unsigned HOST_WIDE_INT small_bitmask;
- /* 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;
+ struct
+ {
+ /* A bitmap with one bit per byte. Cleared bit means the position
+ is needed. Used if IS_LARGE is false. */
+ bitmap bmap;
+
+ /* Number of set bits (i.e. unneeded bytes) in BITMAP. If it is
+ equal to END - BEGIN, the whole store is unused. */
+ int count;
+ } large;
+ } positions_needed;
/* The next store info for this insn. */
struct store_info *next;
/* The right hand side of the store. This is used if there is a
subsequent reload of the mems address somewhere later in the
basic block. */
- rtx rhs;
+ rtx rhs;
+
+ /* If rhs is or holds a constant, this contains that constant,
+ otherwise NULL. */
+ rtx const_rhs;
+
+ /* Set if this store stores the same constant value as REDUNDANT_REASON
+ insn stored. These aren't eliminated early, because doing that
+ might prevent the earlier larger store to be eliminated. */
+ struct insn_info *redundant_reason;
};
+/* 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;
/* This structure holds information about a load. These are only
built for rtx bases. */
-struct read_info
+struct read_info
{
/* The id of the mem group of the base address. */
int group_id;
/* One of these records is created for each insn. */
-struct insn_info
+struct insn_info
{
/* Set true if the insn contains a store but the insn itself cannot
be deleted. This is set if the insn is a parallel and there is
/* This field is only used for the processing of const functions.
These functions cannot read memory, but they can read the stack
- because that is where they may get their parms. It is set to
- true if the insn may contain a stack pointer based store. */
+ because that is where they may get their parms. We need to be
+ this conservative because, like the store motion pass, we don't
+ consider CALL_INSN_FUNCTION_USAGE when processing call insns.
+ Moreover, we need to distinguish two cases:
+ 1. Before reload (register elimination), the stores related to
+ outgoing arguments are stack pointer based and thus deemed
+ of non-constant base in this pass. This requires special
+ handling but also means that the frame pointer based stores
+ need not be killed upon encountering a const function call.
+ 2. After reload, the stores related to outgoing arguments can be
+ either stack pointer or hard frame pointer based. This means
+ that we have no other choice than also killing all the frame
+ pointer based stores upon encountering a const function call.
+ This field is set after reload for const function calls. Having
+ this set is less severe than a wild read, it just means that all
+ the frame related stores are killed rather than all the stores. */
+ bool frame_read;
+
+ /* This field is only used for the processing of const functions.
+ It is set if the insn may contain a stack pointer based store. */
bool stack_pointer_based;
/* This is true if any of the sets within the store contains a
/* 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 insn_info_pool;
/* The linked list of stores that are under consideration in this
- basic block. */
+ basic block. */
static insn_info_t active_local_stores;
-struct bb_info
+struct bb_info
{
/* Pointer to the insn info for the last insn in the block. These
operations. */
bool apply_wild_read;
+ /* The following 4 bitvectors hold information about which positions
+ of which stores are live or dead. They are indexed by
+ get_bitmap_index. */
+
/* The set of store positions that exist in this block before a wild read. */
bitmap gen;
-
+
/* The set of load positions that exist in this block above the
same position of a store. */
bitmap kill;
just initializes the vector from one of the out sets of the
successors of the block. */
bitmap out;
+
+ /* The following bitvector is indexed by the reg number. It
+ contains the set of regs that are live at the current instruction
+ being processed. While it contains info for all of the
+ registers, only the pseudos are actually examined. It is used to
+ assure that shift sequences that are inserted do not accidently
+ clobber live hard regs. */
+ bitmap regs_live;
};
typedef struct bb_info *bb_info_t;
memory. There are also not many of the rtx bases because they are
very limited in scope. */
-struct group_info
+struct group_info
{
/* The actual base of the address. */
rtx rtx_base;
canonical ordering of these that is not based on addresses. */
int id;
+ /* True if there are any positions that are to be processed
+ globally. */
+ bool process_globally;
+
+ /* True if the base of this group is either the frame_pointer or
+ hard_frame_pointer. */
+ bool frame_related;
+
/* A mem wrapped around the base pointer for the group in order to
do read dependency. */
rtx base_mem;
-
- /* Canonized version of base_mem, most likely the same thing. */
- rtx canon_base_mem;
+
+ /* Canonized version of base_mem's address. */
+ rtx canon_base_addr;
/* These two sets of two bitmaps are used to keep track of how many
stores are actually referencing that position from this base. We
the positions that are occupied by stores for this group. */
bitmap group_kill;
- /* True if there are any positions that are to be processed
- globally. */
- bool process_globally;
-
- /* True if the base of this group is either the frame_pointer or
- hard_frame_pointer. */
- bool frame_related;
-
/* The offset_map is used to map the offsets from this base into
positions in the global bitmaps. It is only created after all of
the all of stores have been scanned and we know which ones we
care about. */
- int *offset_map_n, *offset_map_p;
- int offset_map_size_n, offset_map_size_p;
+ int *offset_map_n, *offset_map_p;
+ int offset_map_size_n, offset_map_size_p;
};
typedef struct group_info *group_info_t;
typedef const struct group_info *const_group_info_t;
/* This structure holds the set of changes that are being deferred
when removing read operation. See replace_read. */
-struct deferred_change
+struct deferred_change
{
/* The mem that is being replaced. */
/* The set of clear_alias_sets that have been disqualified because
there are loads or stores using a different mode than the alias set
- was registered with. */
+ was registered with. */
static bitmap disqualified_clear_alias_sets = NULL;
/* The group that holds all of the clear_alias_sets. */
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 int globally_deleted;
-static int locally_deleted;
-static int spill_deleted;
-
+static int globally_deleted;
+static int locally_deleted;
+static int spill_deleted;
+
static bitmap all_blocks;
/* The number of bits used in the global bitmaps. */
static bool gate_dse (void);
+static bool gate_dse1 (void);
+static bool gate_dse2 (void);
\f
/*----------------------------------------------------------------------------
Zeroth step.
- Initialization.
+ Initialization.
----------------------------------------------------------------------------*/
/* Hashtable callbacks for maintaining the "bases" field of
static int
clear_alias_mode_eq (const void *p1, const void *p2)
{
- const struct clear_alias_mode_holder * h1
+ const struct clear_alias_mode_holder * h1
= (const struct clear_alias_mode_holder *) p1;
- const struct clear_alias_mode_holder * h2
+ const struct clear_alias_mode_holder * h2
= (const struct clear_alias_mode_holder *) p2;
return h1->alias_set == h2->alias_set;
}
static hashval_t
clear_alias_mode_hash (const void *p)
{
- const struct clear_alias_mode_holder *holder
+ const struct clear_alias_mode_holder *holder
= (const struct clear_alias_mode_holder *) p;
return holder->alias_set;
}
{
struct clear_alias_mode_holder tmp_holder;
void **slot;
-
+
tmp_holder.alias_set = alias_set;
slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT);
gcc_assert (*slot);
-
- return *slot;
+
+ return (struct clear_alias_mode_holder *) *slot;
}
static group_info_t
get_group_info (rtx base)
{
- struct group_info tmp_gi;
- group_info_t gi;
+ struct group_info tmp_gi;
+ group_info_t gi;
void **slot;
if (base)
{
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);
- gi->canon_base_mem = canon_rtx (gi->base_mem);
+ gi->canon_base_addr = canon_rtx (base);
gi->store1_n = BITMAP_ALLOC (NULL);
gi->store1_p = BITMAP_ALLOC (NULL);
gi->store2_n = BITMAP_ALLOC (NULL);
gi->store2_p = BITMAP_ALLOC (NULL);
gi->group_kill = BITMAP_ALLOC (NULL);
gi->process_globally = false;
- gi->frame_related =
+ gi->frame_related =
(base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);
gi->offset_map_size_n = 0;
gi->offset_map_size_p = 0;
scratch = BITMAP_ALLOC (NULL);
rtx_store_info_pool
- = create_alloc_pool ("rtx_store_info_pool",
+ = create_alloc_pool ("rtx_store_info_pool",
sizeof (struct store_info), 100);
read_info_pool
- = create_alloc_pool ("read_info_pool",
+ = create_alloc_pool ("read_info_pool",
sizeof (struct read_info), 100);
insn_info_pool
- = create_alloc_pool ("insn_info_pool",
+ = create_alloc_pool ("insn_info_pool",
sizeof (struct insn_info), 100);
bb_info_pool
- = create_alloc_pool ("bb_info_pool",
+ = create_alloc_pool ("bb_info_pool",
sizeof (struct bb_info), 100);
rtx_group_info_pool
- = create_alloc_pool ("rtx_group_info_pool",
+ = create_alloc_pool ("rtx_group_info_pool",
sizeof (struct group_info), 100);
deferred_change_pool
- = create_alloc_pool ("deferred_change_pool",
+ = create_alloc_pool ("deferred_change_pool",
sizeof (struct deferred_change), 10);
rtx_group_table = htab_create (11, invariant_group_base_hash,
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 ();
-
+
if (clear_alias_sets)
clear_alias_group = get_group_info (NULL);
else
/* Delete all of the store_info recs from INSN_INFO. */
-static void
+static void
free_store_info (insn_info_t insn_info)
{
store_info_t store_info = insn_info->store_rec;
while (store_info)
{
store_info_t next = store_info->next;
+ if (store_info->is_large)
+ BITMAP_FREE (store_info->positions_needed.large.bmap);
if (store_info->cse_base)
pool_free (cse_store_info_pool, store_info);
else
case POST_INC:
{
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);
+ rtx c = gen_int_mode (data->size, GET_MODE (r1));
+ emit_insn_before (gen_rtx_SET (VOIDmode, r1,
+ gen_rtx_PLUS (GET_MODE (r1), r1, c)),
+ data->insn);
return -1;
}
-
+
case PRE_DEC:
case POST_DEC:
{
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);
+ rtx c = gen_int_mode (-data->size, GET_MODE (r1));
+ emit_insn_before (gen_rtx_SET (VOIDmode, r1,
+ gen_rtx_PLUS (GET_MODE (r1), r1, c)),
+ data->insn);
return -1;
}
-
+
case PRE_MODIFY:
case POST_MODIFY:
{
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 (VOIDmode, r1, add), data->insn);
return -1;
}
return 0;
}
}
-
+
/* If X is a MEM, check the address to see if it is PRE/POST-INC/DEC/MODIFY
and generate an add to replace that. */
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);
-
+
return -1;
}
return 0;
}
-/* Delete the insn and free all of the fields inside INSN_INFO. */
+/* Delete the insn and free all of the fields inside INSN_INFO. */
static void
delete_dead_store_insn (insn_info_t insn_info)
check_for_inc_dec (insn_info->insn);
if (dump_file)
{
- fprintf (dump_file, "Locally deleting insn %d ",
+ fprintf (dump_file, "Locally deleting insn %d ",
INSN_UID (insn_info->insn));
if (insn_info->store_rec->alias_set)
- fprintf (dump_file, "alias set %d\n",
+ fprintf (dump_file, "alias set %d\n",
(int) insn_info->store_rec->alias_set);
else
fprintf (dump_file, "\n");
free_store_info (insn_info);
read_info = insn_info->read_rec;
-
+
while (read_info)
{
read_info_t next = read_info->next;
{
HOST_WIDE_INT i;
- if ((offset > -MAX_OFFSET) && (offset < MAX_OFFSET))
+ if (offset > -MAX_OFFSET && offset + width < MAX_OFFSET)
for (i=offset; i<offset+width; i++)
{
bitmap store1;
store2 = group->store2_p;
ai = i;
}
-
+
if (bitmap_bit_p (store1, ai))
bitmap_set_bit (store2, ai);
- else
+ else
{
bitmap_set_bit (store1, ai);
if (i < 0)
pool_free (read_info_pool, *ptr);
*ptr = next;
}
- else
+ else
ptr = &(*ptr)->next;
}
insn_info->wild_read = true;
}
}
-/* Take all reasonable action to put the address of MEM into the form
- that we can do analysis on.
+/* Take all reasonable action to put the address of MEM into the form
+ that we can do analysis on.
The gold standard is to get the address into the form: address +
OFFSET where address is something that rtx_varies_p considers a
obtained from that.
If that fails, we try cselib to get a value we can at least use
- locally. If that fails we return false.
-
+ locally. If that fails we return false.
+
The GROUP_ID is set to -1 for cselib bases and the index of the
group for non_varying bases.
canon_address (rtx mem,
alias_set_type *alias_set_out,
int *group_id,
- HOST_WIDE_INT *offset,
+ HOST_WIDE_INT *offset,
cselib_val **base)
{
+ enum machine_mode address_mode
+ = targetm.addr_space.address_mode (MEM_ADDR_SPACE (mem));
rtx mem_address = XEXP (mem, 0);
rtx expanded_address, address;
+ int expanded;
+
/* Make sure that cselib is has initialized all of the operands of
the address before asking it to do the subst. */
fprintf (dump_file, "found alias set %d\n", (int) alias_set);
if (bitmap_bit_p (clear_alias_sets, alias_set))
{
- struct clear_alias_mode_holder *entry
+ struct clear_alias_mode_holder *entry
= clear_alias_set_lookup (alias_set);
/* If the modes do not match, we cannot process this set. */
if (entry->mode != GET_MODE (mem))
{
if (dump_file)
- fprintf (dump_file,
- "disqualifying alias set %d, (%s) != (%s)\n",
- (int) alias_set, GET_MODE_NAME (entry->mode),
+ fprintf (dump_file,
+ "disqualifying alias set %d, (%s) != (%s)\n",
+ (int) alias_set, GET_MODE_NAME (entry->mode),
GET_MODE_NAME (GET_MODE (mem)));
-
+
bitmap_set_bit (disqualified_clear_alias_sets, alias_set);
return false;
}
*alias_set_out = 0;
- cselib_lookup (mem_address, Pmode, 1);
+ cselib_lookup (mem_address, address_mode, 1);
if (dump_file)
{
fprintf (dump_file, "\n");
}
- /* Use cselib to replace all of the reg references with the full
- expression. This will take care of the case where we have
+ /* First see if just canon_rtx (mem_address) is const or frame,
+ if not, try cselib_expand_value_rtx and call canon_rtx on that. */
+ address = NULL_RTX;
+ for (expanded = 0; expanded < 2; expanded++)
+ {
+ if (expanded)
+ {
+ /* Use cselib to replace all of the reg references with the full
+ expression. This will take care of the case where we have
- r_x = base + offset;
- val = *r_x;
-
- by making it into
+ r_x = base + offset;
+ val = *r_x;
- val = *(base + offset);
- */
+ by making it into
- expanded_address = cselib_expand_value_rtx (mem_address, scratch, 5);
+ val = *(base + offset); */
- /* If this fails, just go with the mem_address. */
- if (!expanded_address)
- expanded_address = mem_address;
+ expanded_address = cselib_expand_value_rtx (mem_address,
+ scratch, 5);
- /* Split the address into canonical BASE + OFFSET terms. */
- address = canon_rtx (expanded_address);
+ /* If this fails, just go with the address from first
+ iteration. */
+ if (!expanded_address)
+ break;
+ }
+ else
+ expanded_address = mem_address;
- *offset = 0;
+ /* Split the address into canonical BASE + OFFSET terms. */
+ address = canon_rtx (expanded_address);
- if (dump_file)
- {
- fprintf (dump_file, "\n after cselib_expand address: ");
- print_inline_rtx (dump_file, expanded_address, 0);
- fprintf (dump_file, "\n");
+ *offset = 0;
- fprintf (dump_file, "\n after canon_rtx address: ");
- print_inline_rtx (dump_file, address, 0);
- fprintf (dump_file, "\n");
- }
-
- if (GET_CODE (address) == CONST)
- address = XEXP (address, 0);
+ if (dump_file)
+ {
+ if (expanded)
+ {
+ fprintf (dump_file, "\n after cselib_expand address: ");
+ print_inline_rtx (dump_file, expanded_address, 0);
+ fprintf (dump_file, "\n");
+ }
- if (GET_CODE (address) == PLUS && GET_CODE (XEXP (address, 1)) == CONST_INT)
- {
- *offset = INTVAL (XEXP (address, 1));
- address = XEXP (address, 0);
- }
+ fprintf (dump_file, "\n after canon_rtx address: ");
+ print_inline_rtx (dump_file, address, 0);
+ fprintf (dump_file, "\n");
+ }
- if (const_or_frame_p (address))
- {
- group_info_t group = get_group_info (address);
+ if (GET_CODE (address) == CONST)
+ address = XEXP (address, 0);
- if (dump_file)
- fprintf (dump_file, " gid=%d offset=%d \n", group->id, (int)*offset);
- *base = NULL;
- *group_id = group->id;
- }
- else
- {
- *base = cselib_lookup (address, Pmode, true);
- *group_id = -1;
+ if (GET_CODE (address) == PLUS
+ && CONST_INT_P (XEXP (address, 1)))
+ {
+ *offset = INTVAL (XEXP (address, 1));
+ address = XEXP (address, 0);
+ }
- if (*base == NULL)
+ if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem))
+ && const_or_frame_p (address))
{
+ group_info_t group = get_group_info (address);
+
if (dump_file)
- fprintf (dump_file, " no cselib val - should be a wild read.\n");
- return false;
+ fprintf (dump_file, " gid=%d offset=%d \n",
+ group->id, (int)*offset);
+ *base = NULL;
+ *group_id = group->id;
+ return true;
}
+ }
+
+ *base = cselib_lookup (address, address_mode, true);
+ *group_id = -1;
+
+ if (*base == NULL)
+ {
if (dump_file)
- fprintf (dump_file, " varying cselib base=%d offset = %d\n",
- (*base)->value, (int)*offset);
+ fprintf (dump_file, " no cselib val - should be a wild read.\n");
+ return false;
}
+ if (dump_file)
+ fprintf (dump_file, " varying cselib base=%d offset = %d\n",
+ (*base)->value, (int)*offset);
return true;
}
store_info = store_info->next;
store_info->rhs = NULL;
+ store_info->const_rhs = NULL;
ptr = ptr->next_local_store;
}
}
+/* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
+
+static inline void
+set_position_unneeded (store_info_t s_info, int pos)
+{
+ if (__builtin_expect (s_info->is_large, false))
+ {
+ if (!bitmap_bit_p (s_info->positions_needed.large.bmap, pos))
+ {
+ s_info->positions_needed.large.count++;
+ bitmap_set_bit (s_info->positions_needed.large.bmap, pos);
+ }
+ }
+ else
+ s_info->positions_needed.small_bitmask
+ &= ~(((unsigned HOST_WIDE_INT) 1) << pos);
+}
+
+/* Mark the whole store S_INFO as unneeded. */
+
+static inline void
+set_all_positions_unneeded (store_info_t s_info)
+{
+ if (__builtin_expect (s_info->is_large, false))
+ {
+ int pos, end = s_info->end - s_info->begin;
+ for (pos = 0; pos < end; pos++)
+ bitmap_set_bit (s_info->positions_needed.large.bmap, pos);
+ s_info->positions_needed.large.count = end;
+ }
+ else
+ s_info->positions_needed.small_bitmask = (unsigned HOST_WIDE_INT) 0;
+}
+
+/* Return TRUE if any bytes from S_INFO store are needed. */
+
+static inline bool
+any_positions_needed_p (store_info_t s_info)
+{
+ if (__builtin_expect (s_info->is_large, false))
+ return (s_info->positions_needed.large.count
+ < s_info->end - s_info->begin);
+ else
+ return (s_info->positions_needed.small_bitmask
+ != (unsigned HOST_WIDE_INT) 0);
+}
+
+/* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
+ store are needed. */
+
+static inline bool
+all_positions_needed_p (store_info_t s_info, int start, int width)
+{
+ if (__builtin_expect (s_info->is_large, false))
+ {
+ int end = start + width;
+ while (start < end)
+ if (bitmap_bit_p (s_info->positions_needed.large.bmap, start++))
+ return false;
+ return true;
+ }
+ else
+ {
+ unsigned HOST_WIDE_INT mask = lowpart_bitmask (width) << start;
+ return (s_info->positions_needed.small_bitmask & mask) == mask;
+ }
+}
+
+
+static rtx get_stored_val (store_info_t, enum machine_mode, HOST_WIDE_INT,
+ HOST_WIDE_INT, basic_block, bool);
+
+
/* BODY is an instruction pattern that belongs to INSN. Return 1 if
there is a candidate store, after adding it to the appropriate
local store group if so. */
static int
record_store (rtx body, bb_info_t bb_info)
{
- rtx mem;
+ rtx mem, rhs, const_rhs, mem_addr;
HOST_WIDE_INT offset = 0;
HOST_WIDE_INT width = 0;
alias_set_type spill_alias_set;
store_info_t store_info = NULL;
int group_id;
cselib_val *base = NULL;
- insn_info_t ptr, last;
+ insn_info_t ptr, last, redundant_reason;
bool store_is_unused;
if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER)
return 0;
+ mem = SET_DEST (body);
+
/* If this is not used, then this cannot be used to keep the insn
from being deleted. On the other hand, it does provide something
that can be used to prove that another store is dead. */
store_is_unused
- = (find_reg_note (insn_info->insn, REG_UNUSED, body) != NULL);
+ = (find_reg_note (insn_info->insn, REG_UNUSED, mem) != NULL);
/* Check whether that value is a suitable memory location. */
- mem = SET_DEST (body);
if (!MEM_P (mem))
{
/* If the set or clobber is unused, then it does not effect our
{
if (GET_CODE (XEXP (mem, 0)) == SCRATCH)
{
- if (dump_file)
+ if (dump_file)
fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n");
add_wild_read (bb_info);
insn_info->cannot_delete = true;
+ return 0;
}
- else if (!store_is_unused)
+ /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
+ as memset (addr, 0, 36); */
+ else if (!MEM_SIZE (mem)
+ || !CONST_INT_P (MEM_SIZE (mem))
+ || GET_CODE (body) != SET
+ || INTVAL (MEM_SIZE (mem)) <= 0
+ || INTVAL (MEM_SIZE (mem)) > MAX_OFFSET
+ || !CONST_INT_P (SET_SRC (body)))
{
- /* If the set or clobber is unused, then it does not effect our
- ability to get rid of the entire insn. */
- insn_info->cannot_delete = true;
- clear_rhs_from_active_local_stores ();
+ if (!store_is_unused)
+ {
+ /* If the set or clobber is unused, then it does not effect our
+ ability to get rid of the entire insn. */
+ insn_info->cannot_delete = true;
+ clear_rhs_from_active_local_stores ();
+ }
+ return 0;
}
- return 0;
}
/* We can still process a volatile mem, we just cannot delete it. */
if (MEM_VOLATILE_P (mem))
- insn_info->cannot_delete = true;
+ insn_info->cannot_delete = true;
if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
{
return 0;
}
- width = GET_MODE_SIZE (GET_MODE (mem));
+ if (GET_MODE (mem) == BLKmode)
+ width = INTVAL (MEM_SIZE (mem));
+ else
+ {
+ width = GET_MODE_SIZE (GET_MODE (mem));
+ gcc_assert ((unsigned) width <= HOST_BITS_PER_WIDE_INT);
+ }
if (spill_alias_set)
{
bitmap store1 = clear_alias_group->store1_p;
bitmap store2 = clear_alias_group->store2_p;
-
+
+ gcc_assert (GET_MODE (mem) != BLKmode);
+
if (bitmap_bit_p (store1, spill_alias_set))
bitmap_set_bit (store2, spill_alias_set);
- else
+ else
bitmap_set_bit (store1, spill_alias_set);
-
+
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",
{
/* In the restrictive case where the base is a constant or the
frame pointer we can do global analysis. */
-
- group_info_t group
+
+ 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)
(int)offset, (int)(offset+width));
}
+ const_rhs = rhs = NULL_RTX;
+ if (GET_CODE (body) == SET
+ /* No place to keep the value after ra. */
+ && !reload_completed
+ && (REG_P (SET_SRC (body))
+ || GET_CODE (SET_SRC (body)) == SUBREG
+ || CONSTANT_P (SET_SRC (body)))
+ && !MEM_VOLATILE_P (mem)
+ /* Sometimes the store and reload is used for truncation and
+ rounding. */
+ && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
+ {
+ rhs = SET_SRC (body);
+ if (CONSTANT_P (rhs))
+ const_rhs = rhs;
+ else if (body == PATTERN (insn_info->insn))
+ {
+ rtx tem = find_reg_note (insn_info->insn, REG_EQUAL, NULL_RTX);
+ if (tem && CONSTANT_P (XEXP (tem, 0)))
+ const_rhs = XEXP (tem, 0);
+ }
+ if (const_rhs == NULL_RTX && REG_P (rhs))
+ {
+ rtx tem = cselib_expand_value_rtx (rhs, scratch, 5);
+
+ if (tem && CONSTANT_P (tem))
+ const_rhs = tem;
+ }
+ }
+
/* Check to see if this stores causes some other stores to be
dead. */
ptr = active_local_stores;
last = NULL;
+ redundant_reason = NULL;
+ mem = canon_rtx (mem);
+ /* For alias_set != 0 canon_true_dependence should be never called. */
+ if (spill_alias_set)
+ mem_addr = NULL_RTX;
+ else
+ {
+ if (group_id < 0)
+ mem_addr = base->val_rtx;
+ else
+ {
+ group_info_t group
+ = VEC_index (group_info_t, rtx_group_vec, group_id);
+ mem_addr = group->canon_base_addr;
+ }
+ if (offset)
+ mem_addr = plus_constant (mem_addr, offset);
+ }
while (ptr)
{
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
+ struct clear_alias_mode_holder *entry
= clear_alias_set_lookup (s_info->alias_set);
/* Generally, spills cannot be processed if and of the
references to the slot have a different mode. But if
if ((GET_MODE (mem) == GET_MODE (s_info->mem))
&& (GET_MODE (mem) == entry->mode))
{
- delete = true;
- s_info->positions_needed = 0;
+ del = true;
+ set_all_positions_unneeded (s_info);
}
if (dump_file)
fprintf (dump_file, " trying spill store in insn=%d alias_set=%d\n",
INSN_UID (ptr->insn), (int) s_info->alias_set);
}
- else if ((s_info->group_id == group_id)
+ else if ((s_info->group_id == group_id)
&& (s_info->cse_base == base))
{
HOST_WIDE_INT i;
if (dump_file)
fprintf (dump_file, " trying store in insn=%d gid=%d[%d..%d)\n",
- INSN_UID (ptr->insn), s_info->group_id,
+ INSN_UID (ptr->insn), s_info->group_id,
(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));
+
+ /* Even if PTR won't be eliminated as unneeded, if both
+ PTR and this insn store the same constant value, we might
+ eliminate this insn instead. */
+ if (s_info->const_rhs
+ && const_rhs
+ && offset >= s_info->begin
+ && offset + width <= s_info->end
+ && all_positions_needed_p (s_info, offset - s_info->begin,
+ width))
+ {
+ if (GET_MODE (mem) == BLKmode)
+ {
+ if (GET_MODE (s_info->mem) == BLKmode
+ && s_info->const_rhs == const_rhs)
+ redundant_reason = ptr;
+ }
+ else if (s_info->const_rhs == const0_rtx
+ && const_rhs == const0_rtx)
+ redundant_reason = ptr;
+ else
+ {
+ rtx val;
+ start_sequence ();
+ val = get_stored_val (s_info, GET_MODE (mem),
+ offset, offset + width,
+ BLOCK_FOR_INSN (insn_info->insn),
+ true);
+ if (get_insns () != NULL)
+ val = NULL_RTX;
+ end_sequence ();
+ if (val && rtx_equal_p (val, const_rhs))
+ redundant_reason = ptr;
+ }
+ }
+
+ for (i = MAX (offset, s_info->begin);
+ i < offset + width && i < s_info->end;
+ i++)
+ set_position_unneeded (s_info, i - s_info->begin);
}
else if (s_info->rhs)
/* Need to see if it is possible for this store to overwrite
the value of store_info. If it is, set the rhs to NULL to
keep it from being used to remove a load. */
{
- if (canon_true_dependence (s_info->mem,
+ if (canon_true_dependence (s_info->mem,
GET_MODE (s_info->mem),
s_info->mem_addr,
- mem, rtx_varies_p))
- s_info->rhs = NULL;
+ mem, mem_addr, rtx_varies_p))
+ {
+ s_info->rhs = NULL;
+ s_info->const_rhs = NULL;
+ }
}
-
+
/* 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 (delete)
+ if (any_positions_needed_p (s_info)
+ || ptr->cannot_delete)
+ del = false;
+
+ if (del)
{
insn_info_t insn_to_delete = ptr;
-
+
if (last)
last->next_local_store = ptr->next_local_store;
else
active_local_stores = ptr->next_local_store;
-
+
delete_dead_store_insn (insn_to_delete);
}
else
last = ptr;
-
+
ptr = next;
}
-
- gcc_assert ((unsigned) width < sizeof (store_info->positions_needed) * CHAR_BIT);
-
+
/* Finish filling in the store_info. */
store_info->next = insn_info->store_rec;
insn_info->store_rec = store_info;
- store_info->mem = canon_rtx (mem);
+ store_info->mem = mem;
store_info->alias_set = spill_alias_set;
- store_info->mem_addr = get_addr (XEXP (mem, 0));
+ store_info->mem_addr = mem_addr;
store_info->cse_base = base;
- store_info->positions_needed = (1L << width) - 1;
+ if (width > HOST_BITS_PER_WIDE_INT)
+ {
+ store_info->is_large = true;
+ store_info->positions_needed.large.count = 0;
+ store_info->positions_needed.large.bmap = BITMAP_ALLOC (NULL);
+ }
+ else
+ {
+ store_info->is_large = false;
+ store_info->positions_needed.small_bitmask = lowpart_bitmask (width);
+ }
store_info->group_id = group_id;
store_info->begin = offset;
store_info->end = offset + width;
store_info->is_set = GET_CODE (body) == SET;
+ store_info->rhs = rhs;
+ store_info->const_rhs = const_rhs;
+ store_info->redundant_reason = redundant_reason;
- 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))
- /* Sometimes the store and reload is used for truncation and
- rounding. */
- && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
- store_info->rhs = SET_SRC (body);
- else
- store_info->rhs = NULL;
-
/* If this is a clobber, we return 0. We will only be able to
delete this insn if there is only one store USED store, but we
can use the clobber to delete other stores earlier. */
static void
dump_insn_info (const char * start, insn_info_t insn_info)
{
- fprintf (dump_file, "%s insn=%d %s\n", start,
+ fprintf (dump_file, "%s insn=%d %s\n", start,
INSN_UID (insn_info->insn),
insn_info->store_rec ? "has store" : "naked");
}
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)
+ enum machine_mode read_mode,
+ int shift, bool speed, bool require_cst)
{
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,
+ /* If a constant was stored into memory, try to simplify it here,
+ otherwise the cost of the shift might preclude this optimization
+ e.g. at -Os, even when no actual shift will be needed. */
+ if (store_info->const_rhs)
+ {
+ unsigned int byte = subreg_lowpart_offset (new_mode, store_mode);
+ rtx ret = simplify_subreg (new_mode, store_info->const_rhs,
+ store_mode, byte);
+ if (ret && CONSTANT_P (ret))
+ {
+ ret = simplify_const_binary_operation (LSHIFTRT, new_mode,
+ ret, GEN_INT (shift));
+ if (ret && CONSTANT_P (ret))
+ {
+ byte = subreg_lowpart_offset (read_mode, new_mode);
+ ret = simplify_subreg (read_mode, ret, new_mode, byte);
+ if (ret && CONSTANT_P (ret)
+ && rtx_cost (ret, SET, speed) <= COSTS_N_INSNS (1))
+ return ret;
+ }
+ }
+ }
+
+ if (require_cst)
+ return NULL_RTX;
+
+ /* 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;
}
+/* Call back for note_stores to find the hard regs set or clobbered by
+ insn. Data is a bitmap of the hardregs set so far. */
+
+static void
+look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
+{
+ bitmap regs_set = (bitmap) data;
+
+ if (REG_P (x)
+ && REGNO (x) < FIRST_PSEUDO_REGISTER)
+ {
+ int regno = REGNO (x);
+ int n = hard_regno_nregs[regno][GET_MODE (x)];
+ while (--n >= 0)
+ bitmap_set_bit (regs_set, regno + n);
+ }
+}
+
+/* Helper function for replace_read and record_store.
+ Attempt to return a value stored in STORE_INFO, from READ_BEGIN
+ to one before READ_END bytes read in READ_MODE. Return NULL
+ if not successful. If REQUIRE_CST is true, return always constant. */
+
+static rtx
+get_stored_val (store_info_t store_info, enum machine_mode read_mode,
+ HOST_WIDE_INT read_begin, HOST_WIDE_INT read_end,
+ basic_block bb, bool require_cst)
+{
+ enum machine_mode store_mode = GET_MODE (store_info->mem);
+ int shift;
+ int access_size; /* In bytes. */
+ rtx read_reg;
+
+ /* 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. */
+ if (store_mode == BLKmode)
+ shift = 0;
+ else if (BYTES_BIG_ENDIAN)
+ shift = store_info->end - read_end;
+ else
+ shift = read_begin - store_info->begin;
+
+ access_size = shift + GET_MODE_SIZE (read_mode);
+
+ /* From now on it is bits. */
+ shift *= BITS_PER_UNIT;
+
+ if (shift)
+ read_reg = find_shift_sequence (access_size, store_info, read_mode, shift,
+ optimize_bb_for_speed_p (bb),
+ require_cst);
+ else if (store_mode == BLKmode)
+ {
+ /* The store is a memset (addr, const_val, const_size). */
+ gcc_assert (CONST_INT_P (store_info->rhs));
+ store_mode = int_mode_for_mode (read_mode);
+ if (store_mode == BLKmode)
+ read_reg = NULL_RTX;
+ else if (store_info->rhs == const0_rtx)
+ read_reg = extract_low_bits (read_mode, store_mode, const0_rtx);
+ else if (GET_MODE_BITSIZE (store_mode) > HOST_BITS_PER_WIDE_INT
+ || BITS_PER_UNIT >= HOST_BITS_PER_WIDE_INT)
+ read_reg = NULL_RTX;
+ else
+ {
+ unsigned HOST_WIDE_INT c
+ = INTVAL (store_info->rhs)
+ & (((HOST_WIDE_INT) 1 << BITS_PER_UNIT) - 1);
+ int shift = BITS_PER_UNIT;
+ while (shift < HOST_BITS_PER_WIDE_INT)
+ {
+ c |= (c << shift);
+ shift <<= 1;
+ }
+ read_reg = GEN_INT (trunc_int_for_mode (c, store_mode));
+ read_reg = extract_low_bits (read_mode, store_mode, read_reg);
+ }
+ }
+ else if (store_info->const_rhs
+ && (require_cst
+ || GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode)))
+ read_reg = extract_low_bits (read_mode, store_mode,
+ copy_rtx (store_info->const_rhs));
+ else
+ read_reg = extract_low_bits (read_mode, store_mode,
+ copy_rtx (store_info->rhs));
+ if (require_cst && read_reg && !CONSTANT_P (read_reg))
+ read_reg = NULL_RTX;
+ return read_reg;
+}
+
/* Take a sequence of:
A <- r1
...
... <- A
- and change it into
+ and change it into
r2 <- r1
A <- r1
...
went ok. */
static bool
-replace_read (store_info_t store_info, insn_info_t store_insn,
- read_info_t read_info, insn_info_t read_insn, rtx *loc)
+replace_read (store_info_t store_info, insn_info_t store_insn,
+ read_info_t read_info, insn_info_t read_insn, rtx *loc,
+ bitmap regs_live)
{
enum machine_mode store_mode = GET_MODE (store_info->mem);
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, this_insn, read_reg;
+ basic_block bb;
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. */
- if (BYTES_BIG_ENDIAN)
- shift = store_info->end - read_info->end;
- else
- shift = read_info->begin - store_info->begin;
-
- access_size = shift + GET_MODE_SIZE (read_mode);
-
- /* From now on it is bits. */
- shift *= BITS_PER_UNIT;
+ /* 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
+ 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 (shift)
+ 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 ();
+ bb = BLOCK_FOR_INSN (read_insn->insn);
+ read_reg = get_stored_val (store_info,
+ read_mode, read_info->begin, read_info->end,
+ bb, false);
+ 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;
}
+ /* 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 (dump_file)
- fprintf (dump_file, "replacing load at %d from store at %d\n",
- INSN_UID (read_insn->insn), INSN_UID (store_insn->insn));
-
- if (validate_change (read_insn->insn, loc, read_reg, 0))
+ if (insns != NULL_RTX)
{
- rtx insns;
- deferred_change_t deferred_change = 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
+ /* Now we have to scan the set of new instructions to see if the
+ sequence contains and sets of hardregs that happened to be
+ live at this point. For instance, this can happen if one of
+ the insns sets the CC and the CC happened to be live at that
+ point. This does occasionally happen, see PR 37922. */
+ bitmap regs_set = BITMAP_ALLOC (NULL);
+
+ for (this_insn = insns; this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn))
+ note_stores (PATTERN (this_insn), look_for_hardregs, regs_set);
+
+ bitmap_and_into (regs_set, regs_live);
+ if (!bitmap_empty_p (regs_set))
{
- /* 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 ();
+ {
+ fprintf (dump_file,
+ "abandoning replacement because sequence clobbers live hardregs:");
+ df_print_regset (dump_file, regs_set);
+ }
+
+ BITMAP_FREE (regs_set);
+ return false;
}
+ BITMAP_FREE (regs_set);
+ }
+
+ if (validate_change (read_insn->insn, loc, read_reg, 0))
+ {
+ deferred_change_t deferred_change =
+ (deferred_change_t) pool_alloc (deferred_change_pool);
/* 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);
-
+
/* And now for the kludge part: cselib croaks if you just
return at this point. There are two reasons for this:
-
+
1) Cselib has an idea of how many pseudos there are and
that does not include the new ones we just added.
-
+
2) Cselib does not know about the move insn we added
above the store_info, and there is no way to tell it
about it, because it has "moved on".
-
+
Problem (1) is fixable with a certain amount of engineering.
Problem (2) is requires starting the bb from scratch. This
could be expensive.
-
+
So we are just going to have to lie. The move/extraction
insns are not really an issue, cselib did not see them. But
the use of the new pseudo read_insn is a real problem because
and when we are finished with the block, we undo this. We
keep a table of mems to get rid of. At the end of the basic
block we can put them back. */
-
+
*loc = read_info->mem;
deferred_change->next = deferred_change_list;
deferred_change_list = deferred_change;
deferred_change->loc = loc;
deferred_change->reg = read_reg;
-
+
/* Get rid of the read_info, from the point of view of the
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
+ 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;
}
}
static int
check_mem_read_rtx (rtx *loc, void *data)
{
- rtx mem = *loc;
+ rtx mem = *loc, mem_addr;
bb_info_t bb_info;
insn_info_t insn_info;
HOST_WIDE_INT offset = 0;
HOST_WIDE_INT width = 0;
alias_set_type spill_alias_set = 0;
- cselib_val *base = NULL;
+ cselib_val *base = NULL;
int group_id;
read_info_t read_info;
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;
read_info->end = offset + width;
read_info->next = insn_info->read_rec;
insn_info->read_rec = read_info;
+ /* For alias_set != 0 canon_true_dependence should be never called. */
+ if (spill_alias_set)
+ mem_addr = NULL_RTX;
+ else
+ {
+ if (group_id < 0)
+ mem_addr = base->val_rtx;
+ else
+ {
+ group_info_t group
+ = VEC_index (group_info_t, rtx_group_vec, group_id);
+ mem_addr = group->canon_base_addr;
+ }
+ if (offset)
+ mem_addr = plus_constant (mem_addr, offset);
+ }
/* We ignore the clobbers in store_info. The is mildly aggressive,
but there really should not be a clobber followed by a read. */
/* Skip the clobbers. */
while (!store_info->is_set)
store_info = store_info->next;
-
+
if (store_info->alias_set == spill_alias_set)
{
if (dump_file)
the frame pointer and offset is a constant. */
insn_info_t i_ptr = active_local_stores;
insn_info_t last = NULL;
-
+
if (dump_file)
{
if (width == -1)
{
bool remove = false;
store_info_t store_info = i_ptr->store_rec;
-
+
/* Skip the clobbers. */
while (!store_info->is_set)
store_info = store_info->next;
-
+
/* There are three cases here. */
if (store_info->group_id < 0)
/* We have a cselib store followed by a read from a
const base. */
- remove
- = canon_true_dependence (store_info->mem,
+ remove
+ = canon_true_dependence (store_info->mem,
GET_MODE (store_info->mem),
store_info->mem_addr,
- mem, rtx_varies_p);
-
+ mem, mem_addr, rtx_varies_p);
+
else if (group_id == store_info->group_id)
{
/* This is a block mode load. We may get lucky and
canon_true_dependence may save the day. */
if (width == -1)
- remove
- = canon_true_dependence (store_info->mem,
+ remove
+ = canon_true_dependence (store_info->mem,
GET_MODE (store_info->mem),
store_info->mem_addr,
- mem, rtx_varies_p);
-
+ mem, mem_addr, rtx_varies_p);
+
/* If this read is just reading back something that we just
stored, rewrite the read. */
- else
+ else
{
if (store_info->rhs
- && (offset >= store_info->begin)
- && (offset + width <= store_info->end))
- {
- int mask = ((1L << width) - 1) << (offset - store_info->begin);
-
- if ((store_info->positions_needed & mask) == mask
- && replace_read (store_info, i_ptr,
- read_info, insn_info, loc))
- return 0;
- }
+ && offset >= store_info->begin
+ && offset + width <= store_info->end
+ && all_positions_needed_p (store_info,
+ offset - store_info->begin,
+ width)
+ && replace_read (store_info, i_ptr, read_info,
+ insn_info, loc, bb_info->regs_live))
+ return 0;
+
/* The bases are the same, just see if the offsets
overlap. */
- if ((offset < store_info->end)
+ if ((offset < store_info->end)
&& (offset + width > store_info->begin))
remove = true;
}
}
-
- /* else
+
+ /* else
The else case that is missing here is that the
bases are constant but different. There is nothing
to do here because there is no overlap. */
-
+
if (remove)
{
if (dump_file)
i_ptr = i_ptr->next_local_store;
}
}
- else
+ else
{
insn_info_t i_ptr = active_local_stores;
insn_info_t last = NULL;
{
bool remove = false;
store_info_t store_info = i_ptr->store_rec;
-
+
if (dump_file)
fprintf (dump_file, " processing cselib load against insn %d\n",
INSN_UID (i_ptr->insn));
if (store_info->rhs
&& store_info->group_id == -1
&& store_info->cse_base == base
- && (offset >= store_info->begin)
- && (offset + width <= store_info->end))
- {
- int mask = ((1L << width) - 1) << (offset - store_info->begin);
-
- if ((store_info->positions_needed & mask) == mask
- && replace_read (store_info, i_ptr,
- read_info, insn_info, loc))
- return 0;
- }
+ && width != -1
+ && offset >= store_info->begin
+ && offset + width <= store_info->end
+ && all_positions_needed_p (store_info,
+ offset - store_info->begin, width)
+ && replace_read (store_info, i_ptr, read_info, insn_info, loc,
+ bb_info->regs_live))
+ return 0;
if (!store_info->alias_set)
- remove = canon_true_dependence (store_info->mem,
+ remove = canon_true_dependence (store_info->mem,
GET_MODE (store_info->mem),
store_info->mem_addr,
- mem, rtx_varies_p);
-
+ mem, mem_addr, rtx_varies_p);
+
if (remove)
{
if (dump_file)
dump_insn_info ("removing from active", i_ptr);
-
+
if (last)
last->next_local_store = i_ptr->next_local_store;
else
return 0;
}
-/* A for_each_rtx callback in which DATA points the INSN_INFO for
+/* A for_each_rtx callback in which DATA points the INSN_INFO for
as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
true for any part of *LOC. */
for_each_rtx (loc, check_mem_read_rtx, data);
}
+
+/* Get arguments passed to CALL_INSN. Return TRUE if successful.
+ So far it only handles arguments passed in registers. */
+
+static bool
+get_call_args (rtx call_insn, tree fn, rtx *args, int nargs)
+{
+ CUMULATIVE_ARGS args_so_far;
+ tree arg;
+ int idx;
+
+ INIT_CUMULATIVE_ARGS (args_so_far, TREE_TYPE (fn), NULL_RTX, 0, 3);
+
+ arg = TYPE_ARG_TYPES (TREE_TYPE (fn));
+ for (idx = 0;
+ arg != void_list_node && idx < nargs;
+ arg = TREE_CHAIN (arg), idx++)
+ {
+ enum machine_mode mode = TYPE_MODE (TREE_VALUE (arg));
+ rtx reg = FUNCTION_ARG (args_so_far, mode, NULL_TREE, 1), link, tmp;
+ if (!reg || !REG_P (reg) || GET_MODE (reg) != mode
+ || GET_MODE_CLASS (mode) != MODE_INT)
+ return false;
+
+ for (link = CALL_INSN_FUNCTION_USAGE (call_insn);
+ link;
+ link = XEXP (link, 1))
+ if (GET_CODE (XEXP (link, 0)) == USE)
+ {
+ args[idx] = XEXP (XEXP (link, 0), 0);
+ if (REG_P (args[idx])
+ && REGNO (args[idx]) == REGNO (reg)
+ && (GET_MODE (args[idx]) == mode
+ || (GET_MODE_CLASS (GET_MODE (args[idx])) == MODE_INT
+ && (GET_MODE_SIZE (GET_MODE (args[idx]))
+ <= UNITS_PER_WORD)
+ && (GET_MODE_SIZE (GET_MODE (args[idx]))
+ > GET_MODE_SIZE (mode)))))
+ break;
+ }
+ if (!link)
+ return false;
+
+ tmp = cselib_expand_value_rtx (args[idx], scratch, 5);
+ if (GET_MODE (args[idx]) != mode)
+ {
+ if (!tmp || !CONST_INT_P (tmp))
+ return false;
+ tmp = GEN_INT (trunc_int_for_mode (INTVAL (tmp), mode));
+ }
+ if (tmp)
+ args[idx] = tmp;
+
+ FUNCTION_ARG_ADVANCE (args_so_far, mode, NULL_TREE, 1);
+ }
+ if (arg != void_list_node || idx != nargs)
+ return false;
+ return true;
+}
+
+
/* Apply record_store to all candidate stores in INSN. Mark INSN
if some part of it is not a candidate store and assigns to a
non-register target. */
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));
insn_info->prev_insn = bb_info->last_insn;
insn_info->insn = insn;
bb_info->last_insn = insn_info;
-
+
+ if (DEBUG_INSN_P (insn))
+ {
+ insn_info->cannot_delete = true;
+ return;
+ }
/* Cselib clears the table for this case, so we have to essentially
do the same. */
if (CALL_P (insn))
{
+ bool const_call;
+ tree memset_call = NULL_TREE;
+
insn_info->cannot_delete = true;
/* 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))
+ been pushed onto the stack.
+ memset and bzero don't read memory either. */
+ const_call = RTL_CONST_CALL_P (insn);
+ if (!const_call)
+ {
+ rtx call = PATTERN (insn);
+ if (GET_CODE (call) == PARALLEL)
+ call = XVECEXP (call, 0, 0);
+ if (GET_CODE (call) == SET)
+ call = SET_SRC (call);
+ if (GET_CODE (call) == CALL
+ && MEM_P (XEXP (call, 0))
+ && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
+ {
+ rtx symbol = XEXP (XEXP (call, 0), 0);
+ if (SYMBOL_REF_DECL (symbol)
+ && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
+ {
+ if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
+ == BUILT_IN_NORMAL
+ && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
+ == BUILT_IN_MEMSET))
+ || SYMBOL_REF_DECL (symbol) == block_clear_fn)
+ memset_call = SYMBOL_REF_DECL (symbol);
+ }
+ }
+ }
+ if (const_call || memset_call)
{
insn_info_t i_ptr = active_local_stores;
insn_info_t last = NULL;
if (dump_file)
- fprintf (dump_file, "const call %d\n", INSN_UID (insn));
+ fprintf (dump_file, "%s call %d\n",
+ const_call ? "const" : "memset", INSN_UID (insn));
+ /* See the head comment of the frame_read field. */
+ if (reload_completed)
+ insn_info->frame_read = true;
+
+ /* Loop over the active stores and remove those which are
+ killed by the const function call. */
while (i_ptr)
{
- /* Remove the stack pointer based stores. */
+ bool remove_store = false;
+
+ /* The stack pointer based stores are always killed. */
if (i_ptr->stack_pointer_based)
+ remove_store = true;
+
+ /* If the frame is read, the frame related stores are killed. */
+ else if (insn_info->frame_read)
+ {
+ store_info_t store_info = i_ptr->store_rec;
+
+ /* Skip the clobbers. */
+ while (!store_info->is_set)
+ store_info = store_info->next;
+
+ if (store_info->group_id >= 0
+ && VEC_index (group_info_t, rtx_group_vec,
+ store_info->group_id)->frame_related)
+ remove_store = true;
+ }
+
+ if (remove_store)
{
if (dump_file)
dump_insn_info ("removing from active", i_ptr);
-
+
if (last)
last->next_local_store = i_ptr->next_local_store;
else
}
else
last = i_ptr;
+
i_ptr = i_ptr->next_local_store;
}
+
+ if (memset_call)
+ {
+ rtx args[3];
+ if (get_call_args (insn, memset_call, args, 3)
+ && CONST_INT_P (args[1])
+ && CONST_INT_P (args[2])
+ && INTVAL (args[2]) > 0)
+ {
+ rtx mem = gen_rtx_MEM (BLKmode, args[0]);
+ set_mem_size (mem, args[2]);
+ body = gen_rtx_SET (VOIDmode, mem, args[1]);
+ mems_found += record_store (body, bb_info);
+ if (dump_file)
+ fprintf (dump_file, "handling memset as BLKmode store\n");
+ if (mems_found == 1)
+ {
+ insn_info->next_local_store = active_local_stores;
+ active_local_stores = insn_info;
+ }
+ }
+ }
}
else
them. */
if ((GET_CODE (PATTERN (insn)) == CLOBBER)
|| volatile_refs_p (PATTERN (insn))
- || (flag_non_call_exceptions && may_trap_p (PATTERN (insn)))
+ || insn_could_throw_p (insn)
|| (RTX_FRAME_RELATED_P (insn))
|| find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX))
insn_info->cannot_delete = true;
-
+
body = PATTERN (insn);
if (GET_CODE (body) == PARALLEL)
{
mems_found += record_store (body, bb_info);
if (dump_file)
- fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
+ fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
mems_found, insn_info->cannot_delete ? "true" : "false");
- /* If we found some sets of mems, and the insn has not been marked
- cannot delete, add it into the active_local_stores so that it can
- be locally deleted if found dead. Otherwise mark it as cannot
- delete. This simplifies the processing later. */
- if (mems_found == 1 && !insn_info->cannot_delete)
+ /* If we found some sets of mems, add it into the active_local_stores so
+ that it can be locally deleted if found dead or used for
+ replace_read and redundant constant store elimination. Otherwise mark
+ it as cannot delete. This simplifies the processing later. */
+ if (mems_found == 1)
{
insn_info->next_local_store = active_local_stores;
active_local_stores = insn_info;
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. */
while (store_info)
{
- if ((store_info->group_id == -1)
+ 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;
}
else
last = insn_info;
-
+
insn_info = insn_info->next_local_store;
}
}
dse_step1 (void)
{
basic_block bb;
+ bitmap regs_live = BITMAP_ALLOC (NULL);
cselib_init (false);
all_blocks = BITMAP_ALLOC (NULL);
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);
+ bb_info->regs_live = regs_live;
+
+ bitmap_copy (regs_live, DF_LR_IN (bb));
+ df_simulate_initialize_forwards (bb, regs_live);
bb_table[bb->index] = bb_info;
cselib_discard_hook = remove_useless_values;
rtx insn;
cse_store_info_pool
- = create_alloc_pool ("cse_store_info_pool",
+ = create_alloc_pool ("cse_store_info_pool",
sizeof (struct store_info), 100);
active_local_stores = NULL;
cselib_clear_table ();
-
+
/* Scan the insns. */
FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
scan_insn (bb_info, insn);
cselib_process_insn (insn);
+ if (INSN_P (insn))
+ df_simulate_one_insn_forwards (bb, insn, regs_live);
}
-
+
/* This is something of a hack, because the global algorithm
is supposed to take care of the case where stores go dead
at the end of the function. However, the global
&& (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)
/* Skip the clobbers. */
while (!store_info->is_set)
store_info = store_info->next;
- if (store_info->alias_set)
+ if (store_info->alias_set && !i_ptr->cannot_delete)
delete_dead_store_insn (i_ptr);
- else
+ else
if (store_info->group_id >= 0)
{
- group_info_t group
+ group_info_t group
= VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
- if (group->frame_related)
+ if (group->frame_related && !i_ptr->cannot_delete)
delete_dead_store_insn (i_ptr);
}
while (ptr)
{
if (ptr->contains_cselib_groups)
- free_store_info (ptr);
+ {
+ store_info_t s_info = ptr->store_rec;
+ while (s_info && !s_info->is_set)
+ s_info = s_info->next;
+ if (s_info
+ && s_info->redundant_reason
+ && s_info->redundant_reason->insn
+ && !ptr->cannot_delete)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Locally deleting insn %d "
+ "because insn %d stores the "
+ "same value and couldn't be "
+ "eliminated\n",
+ INSN_UID (ptr->insn),
+ INSN_UID (s_info->redundant_reason->insn));
+ delete_dead_store_insn (ptr);
+ }
+ if (s_info)
+ s_info->redundant_reason = NULL;
+ free_store_info (ptr);
+ }
+ else
+ {
+ store_info_t s_info;
+
+ /* Free at least positions_needed bitmaps. */
+ for (s_info = ptr->store_rec; s_info; s_info = s_info->next)
+ if (s_info->is_large)
+ {
+ BITMAP_FREE (s_info->positions_needed.large.bmap);
+ s_info->is_large = false;
+ }
+ }
ptr = ptr->prev_insn;
}
free_alloc_pool (cse_store_info_pool);
}
+ bb_info->regs_live = NULL;
}
+ BITMAP_FREE (regs_live);
cselib_finish ();
htab_empty (rtx_group_table);
}
for the position. We do this because the stack related
stores can be deleted if their is no read between them and
the end of the function.
-
+
To make this work in the current framework, we take the stack
related bases add all of the bits from store1 into store2.
This has the effect of making the eligible even if there is
bitmap_ior_into (group->store2_n, group->store1_n);
bitmap_ior_into (group->store2_p, group->store1_p);
if (dump_file)
- fprintf (dump_file, "group %d is frame related ", i);
+ fprintf (dump_file, "group %d is frame related ", i);
}
group->offset_map_size_n++;
group->process_globally = false;
if (dump_file)
{
- fprintf (dump_file, "group %d(%d+%d): ", i,
+ fprintf (dump_file, "group %d(%d+%d): ", i,
(int)bitmap_count_bits (group->store2_n),
(int)bitmap_count_bits (group->store2_p));
bitmap_print (dump_file, group->store2_n, "n ", " ");
}
EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
{
- bitmap_set_bit (group->group_kill, current_position);
+ bitmap_set_bit (group->group_kill, current_position);
group->offset_map_p[j] = current_position++;
group->process_globally = true;
}
if (dump_file)
{
- bitmap_print (dump_file, clear_alias_sets,
+ bitmap_print (dump_file, clear_alias_sets,
"clear alias sets ", "\n");
- bitmap_print (dump_file, disqualified_clear_alias_sets,
+ bitmap_print (dump_file, disqualified_clear_alias_sets,
"disqualified clear alias sets ", "\n");
}
memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
bitmap_clear (group->group_kill);
-
+
/* Remove the disqualified positions from the store2_p set. */
bitmap_and_compl_into (group->store2_p, disqualified_clear_alias_sets);
-
+
/* We do not need to process the store2_n set because
alias_sets are always positive. */
EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
{
- bitmap_set_bit (group->group_kill, current_position);
+ bitmap_set_bit (group->group_kill, current_position);
group->offset_map_p[j] = current_position++;
group->process_globally = true;
}
\f
/*----------------------------------------------------------------------------
Third step.
-
+
Build the bit vectors for the transfer functions.
----------------------------------------------------------------------------*/
/* Note that this is NOT a general purpose function. Any mem that has
an alias set registered here expected to be COMPLETELY unaliased:
- i.e it's addresses are not and need not be examined.
+ i.e it's addresses are not and need not be examined.
It is known that all references to this address will have this
alias set and there are NO other references to this address in the
- function.
+ function.
Currently the only place that is known to be clean enough to use
- this interface is the code that assigns the spill locations.
+ this interface is the code that assigns the spill locations.
All of the mems that have alias_sets registered are subjected to a
very powerful form of dse where function calls, volatile reads and
- writes, and reads from random location are not taken into account.
+ writes, and reads from random location are not taken into account.
It is also assumed that these locations go dead when the function
returns. This assumption could be relaxed if there were found to
elements. So when we see a mode mismatch, we just bail. */
-void
-dse_record_singleton_alias_set (alias_set_type alias_set,
+void
+dse_record_singleton_alias_set (alias_set_type alias_set,
enum machine_mode mode)
{
struct clear_alias_mode_holder tmp_holder;
disqualified_clear_alias_sets = BITMAP_ALLOC (NULL);
clear_alias_mode_table = htab_create (11, clear_alias_mode_hash,
clear_alias_mode_eq, NULL);
- clear_alias_mode_pool = create_alloc_pool ("clear_alias_mode_pool",
+ clear_alias_mode_pool = create_alloc_pool ("clear_alias_mode_pool",
sizeof (struct clear_alias_mode_holder), 100);
}
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;
}
/* Remove ALIAS_SET from the sets of stack slots being considered. */
-void
+void
dse_invalidate_singleton_alias_set (alias_set_type alias_set)
{
if ((!gate_dse()) || !alias_set)
/* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
may be NULL. */
-static void
+static void
scan_stores_nospill (store_info_t store_info, bitmap gen, bitmap kill)
{
while (store_info)
{
HOST_WIDE_INT i;
- group_info_t group_info
+ group_info_t group_info
= VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
if (group_info->process_globally)
for (i = store_info->begin; i < store_info->end; i++)
/* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
may be NULL. */
-static void
+static void
scan_stores_spill (store_info_t store_info, bitmap gen, bitmap kill)
{
while (store_info)
{
if (store_info->alias_set)
{
- int index = get_bitmap_index (clear_alias_group,
+ int index = get_bitmap_index (clear_alias_group,
store_info->alias_set);
if (index != 0)
{
int i;
group_info_t group;
+ /* If this insn reads the frame, kill all the frame related stores. */
+ if (insn_info->frame_read)
+ {
+ for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
+ if (group->process_globally && group->frame_related)
+ {
+ if (kill)
+ bitmap_ior_into (kill, group->group_kill);
+ bitmap_and_compl_into (gen, group->group_kill);
+ }
+ }
+
while (read_info)
{
for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
something else with a different constant
base. */
if ((read_info->group_id < 0)
- && canon_true_dependence (group->base_mem,
+ && canon_true_dependence (group->base_mem,
QImode,
- group->canon_base_mem,
- read_info->mem, rtx_varies_p))
+ group->canon_base_addr,
+ read_info->mem, NULL_RTX,
+ rtx_varies_p))
{
if (kill)
bitmap_ior_into (kill, group->group_kill);
}
}
}
-
+
read_info = read_info->next;
}
}
{
if (read_info->alias_set)
{
- int index = get_bitmap_index (clear_alias_group,
+ int index = get_bitmap_index (clear_alias_group,
read_info->alias_set);
if (index != 0)
{
bitmap_clear_bit (gen, index);
}
}
-
+
read_info = read_info->next;
}
}
insn_info = bb_info->last_insn;
else
insn_info = find_insn_before_first_wild_read (bb_info);
-
+
/* In the spill case or in the no_spill case if there is no wild
read in the block, we will need a kill set. */
if (insn_info == bb_info->last_insn)
else
bb_info->kill = BITMAP_ALLOC (NULL);
}
- else
+ else
if (bb_info->kill)
BITMAP_FREE (bb_info->kill);
this phase. */
if (insn_info->insn && INSN_P (insn_info->insn))
{
- /* Process the read(s) last. */
+ /* Process the read(s) last. */
if (for_spills)
{
scan_stores_spill (insn_info->store_rec, bb_info->gen, bb_info->kill);
scan_stores_nospill (insn_info->store_rec, bb_info->gen, bb_info->kill);
scan_reads_nospill (insn_info, bb_info->gen, bb_info->kill);
}
- }
+ }
insn_info = insn_info->prev_insn;
}
{
/* The gen set is all 0's for the exit block except for the
frame_pointer_group. */
-
+
if (stores_off_frame_dead_at_return)
{
unsigned int i;
group_info_t group;
-
+
for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
{
if (group->process_globally && group->frame_related)
{
RESET_BIT (unreachable_blocks, bb->index);
FOR_EACH_EDGE (e, ei, bb->preds)
- {
+ {
mark_reachable_blocks (unreachable_blocks, e->src);
- }
+ }
}
}
sbitmap_iterator sbi;
bitmap all_ones = NULL;
unsigned int i;
-
+
sbitmap_ones (unreachable_blocks);
FOR_ALL_BB (bb)
/* Propagate the info from the out to the in set of BB_INDEX's basic
- block. There are three cases:
+ block. There are three cases:
1) The block has no kill set. In this case the kill set is all
ones. It does not matter what the out set of the block is, none of
{
/* Case 3 above. */
if (bb_info->in)
- return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
+ return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
bb_info->out, bb_info->kill);
else
{
bb_info->in = BITMAP_ALLOC (NULL);
- bitmap_ior_and_compl (bb_info->in, bb_info->gen,
+ bitmap_ior_and_compl (bb_info->in, bb_info->gen,
bb_info->out, bb_info->kill);
return true;
}
static void
dse_step4 (void)
{
- df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
- dse_confluence_n, dse_transfer_function,
- all_blocks, df_get_postorder (DF_BACKWARD),
+ df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
+ dse_confluence_n, dse_transfer_function,
+ all_blocks, df_get_postorder (DF_BACKWARD),
df_get_n_blocks (DF_BACKWARD));
if (dump_file)
{
/* There may have been code deleted by the dce pass run before
this phase. */
- if (insn_info->insn
+ if (insn_info->insn
&& INSN_P (insn_info->insn)
&& (!insn_info->cannot_delete)
&& (!bitmap_empty_p (v)))
/* Try to delete the current insn. */
deleted = true;
-
+
/* Skip the clobbers. */
while (!store_info->is_set)
store_info = store_info->next;
else
{
HOST_WIDE_INT i;
- group_info_t group_info
+ group_info_t group_info
= VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
-
+
for (i = store_info->begin; i < store_info->end; i++)
{
int index = get_bitmap_index (group_info, i);
-
+
if (dump_file)
- fprintf (dump_file, "i = %d, index = %d\n", (int)i, index);
+ fprintf (dump_file, "i = %d, index = %d\n", (int)i, index);
if (index == 0 || !bitmap_bit_p (v, index))
{
if (dump_file)
- fprintf (dump_file, "failing at i = %d\n", (int)i);
+ fprintf (dump_file, "failing at i = %d\n", (int)i);
deleted = false;
break;
}
/* We do want to process the local info if the insn was
deleted. For instance, if the insn did a wild read, we
no longer need to trash the info. */
- if (insn_info->insn
+ if (insn_info->insn
&& INSN_P (insn_info->insn)
&& (!deleted))
{
scan_reads_nospill (insn_info, v, NULL);
}
}
-
+
insn_info = insn_info->prev_insn;
}
}
bool deleted = false;
/* There may have been code deleted by the dce pass run before
this phase. */
- if (insn_info->insn
+ if (insn_info->insn
&& INSN_P (insn_info->insn)
&& (!insn_info->cannot_delete)
&& (!bitmap_empty_p (v)))
/* Try to delete the current insn. */
store_info_t store_info = insn_info->store_rec;
deleted = true;
-
+
while (store_info)
{
if (store_info->alias_set)
{
- int index = get_bitmap_index (clear_alias_group,
+ int index = get_bitmap_index (clear_alias_group,
store_info->alias_set);
if (index == 0 || !bitmap_bit_p (v, index))
{
break;
}
}
- else
+ else
deleted = false;
store_info = store_info->next;
}
if (deleted && dbg_cnt (dse))
{
if (dump_file)
- fprintf (dump_file, "Spill deleting insn %d\n",
+ fprintf (dump_file, "Spill deleting insn %d\n",
INSN_UID (insn_info->insn));
check_for_inc_dec (insn_info->insn);
delete_insn (insn_info->insn);
insn_info->insn = NULL;
}
}
-
- if (insn_info->insn
+
+ if (insn_info->insn
&& INSN_P (insn_info->insn)
&& (!deleted))
{
scan_stores_spill (insn_info->store_rec, v, NULL);
scan_reads_spill (insn_info->read_rec, v, NULL);
}
-
+
insn_info = insn_info->prev_insn;
}
}
/*----------------------------------------------------------------------------
Sixth step.
- Destroy everything left standing.
+ Delete stores made redundant by earlier stores (which store the same
+ value) that couldn't be eliminated.
----------------------------------------------------------------------------*/
-static void
-dse_step6 (bool global_done)
+static void
+dse_step6 (void)
{
- unsigned int i;
- group_info_t group;
basic_block bb;
-
- if (global_done)
+
+ FOR_ALL_BB (bb)
{
- 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);
- }
+ bb_info_t bb_info = bb_table[bb->index];
+ insn_info_t insn_info = bb_info->last_insn;
- FOR_ALL_BB (bb)
+ while (insn_info)
{
- 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);
+ /* There may have been code deleted by the dce pass run before
+ this phase. */
+ if (insn_info->insn
+ && INSN_P (insn_info->insn)
+ && !insn_info->cannot_delete)
+ {
+ store_info_t s_info = insn_info->store_rec;
+
+ while (s_info && !s_info->is_set)
+ s_info = s_info->next;
+ if (s_info
+ && s_info->redundant_reason
+ && s_info->redundant_reason->insn
+ && INSN_P (s_info->redundant_reason->insn))
+ {
+ rtx rinsn = s_info->redundant_reason->insn;
+ if (dump_file)
+ fprintf (dump_file, "Locally deleting insn %d "
+ "because insn %d stores the "
+ "same value and couldn't be "
+ "eliminated\n",
+ INSN_UID (insn_info->insn),
+ INSN_UID (rinsn));
+ delete_dead_store_insn (insn_info);
+ }
+ }
+ insn_info = insn_info->prev_insn;
}
}
- else
+}
+\f
+/*----------------------------------------------------------------------------
+ Seventh step.
+
+ Destroy everything left standing.
+----------------------------------------------------------------------------*/
+
+static void
+dse_step7 (bool global_done)
+{
+ unsigned int i;
+ group_info_t group;
+ basic_block bb;
+
+ 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
------------------------------------------------------------------------- */
df_set_flags (DF_DEFER_INSN_RESCAN);
+ /* Need the notes since we must track live hardregs in the forwards
+ direction. */
+ df_note_add_problem ();
+ df_analyze ();
+
dse_step0 ();
dse_step1 ();
dse_step2_init ();
pass to process the spills. These are special in that they are
totally transparent, i.e, there is no aliasing issues that need
to be considered. This means that the wild reads that kill
- everything else do not apply here. */
+ everything else do not apply here. */
if (clear_alias_sets && dse_step2_spill ())
{
if (!did_global)
dse_step4 ();
dse_step5_spill ();
}
-
- dse_step6 (did_global);
+
+ dse_step6 ();
+ dse_step7 (did_global);
if (dump_file)
fprintf (dump_file, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
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 */
+ }
};
OSDN Git Service
