and global constant/copy propagation for GNU compiler.
Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
-This file is part of GNU CC.
+This file is part of GCC.
-GNU CC is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
-any later version.
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
-GNU CC is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
You should have received a copy of the GNU General Public License
-along with GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
/* TODO
- reordering of memory allocation and freeing to be more space efficient
#include "expr.h"
#include "ggc.h"
#include "params.h"
+
#include "obstack.h"
-#include "df.h"
#define obstack_chunk_alloc gmalloc
#define obstack_chunk_free free
/* Non-zero if can_copy_p has been initialized. */
static int can_copy_init_p;
-/* Dataflow analyzer */
-struct df *df_analyzer;
-
-
struct reg_use {rtx reg_rtx; };
/* Hash table of expressions. */
{
struct expr * expr; /* Gcse expression reference for LM. */
rtx pattern; /* Pattern of this mem. */
- rtx loads; /* INSN list for where load appears */
- rtx stores; /* INSN list for where store appears */
+ rtx loads; /* INSN list of loads seen. */
+ rtx stores; /* INSN list of stores seen. */
struct ls_expr * next; /* Next in the list. */
int invalid; /* Invalid for some reason. */
int index; /* If it maps to a bitmap index. */
static void compute_ld_motion_mems PARAMS ((void));
static void trim_ld_motion_mems PARAMS ((void));
static void update_ld_motion_stores PARAMS ((struct expr *));
-static int store_ops_ok PARAMS ((rtx, basic_block, rtx, int));
+static void reg_set_info PARAMS ((rtx, rtx, void *));
+static int store_ops_ok PARAMS ((rtx, basic_block));
static void find_moveable_store PARAMS ((rtx));
static int compute_store_table PARAMS ((void));
static int load_kills_store PARAMS ((rtx, rtx));
static int find_loads PARAMS ((rtx, rtx));
static int store_killed_in_insn PARAMS ((rtx, rtx));
-static int store_killed_after PARAMS ((rtx, rtx, basic_block, int));
+static int store_killed_after PARAMS ((rtx, rtx, basic_block));
static int store_killed_before PARAMS ((rtx, rtx, basic_block));
static void build_store_vectors PARAMS ((void));
static void insert_insn_start_bb PARAMS ((rtx, basic_block));
\f
/* Hash table support. */
-/* For each register, the cuid of the first/last insn in the block to set it,
- or -1 if not set. */
+/* For each register, the cuid of the first/last insn in the block
+ that set it, or -1 if not set. */
#define NEVER_SET -1
-static int *reg_first_set;
-static int *reg_last_set;
+
+struct reg_avail_info
+{
+ int last_bb;
+ int first_set;
+ int last_set;
+};
+
+static struct reg_avail_info *reg_avail_info;
+static int current_bb;
/* See whether X, the source of a set, is something we want to consider for
switch (code)
{
case REG:
- if (avail_p)
- return (reg_last_set[REGNO (x)] == NEVER_SET
- || reg_last_set[REGNO (x)] < INSN_CUID (insn));
- else
- return (reg_first_set[REGNO (x)] == NEVER_SET
- || reg_first_set[REGNO (x)] >= INSN_CUID (insn));
+ {
+ struct reg_avail_info *info = ®_avail_info[REGNO (x)];
+
+ if (info->last_bb != current_bb)
+ return 1;
+ if (avail_p)
+ return info->last_set < INSN_CUID (insn);
+ else
+ return info->first_set >= INSN_CUID (insn);
+ }
case MEM:
- if (load_killed_in_block_p (BLOCK_FOR_INSN (insn), INSN_CUID (insn),
+ if (load_killed_in_block_p (BASIC_BLOCK (current_bb), INSN_CUID (insn),
x, avail_p))
return 0;
else
elsewhere. */
if (GET_CODE (dest) != MEM)
return;
+
/* If we are setting a MEM in our list of specially recognized MEMs,
don't mark as killed this time. */
gcse_mems_conflict_p = 1;
return;
}
+
if (true_dependence (dest, GET_MODE (dest), gcse_mem_operand,
rtx_addr_varies_p))
gcse_mems_conflict_p = 1;
hash += hash_string_1 (XSTR (x, i));
else if (fmt[i] == 'i')
hash += (unsigned int) XINT (x, i);
- else if (fmt[i] == 't');
else
abort ();
}
break;
case '0':
- case 't':
break;
-
+
default:
abort ();
}
this insn. */
int antic_p = oprs_anticipatable_p (src, insn) && single_set (insn);
/* An expression is not available if its operands are
- subsequently modified, including this insn. */
- int avail_p = oprs_available_p (src, insn);
+ subsequently modified, including this insn. It's also not
+ available if this is a branch, because we can't insert
+ a set after the branch. */
+ int avail_p = (oprs_available_p (src, insn)
+ && ! JUMP_P (insn));
insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p);
}
/* Record register first/last/block set information for REGNO in INSN.
- reg_first_set records the first place in the block where the register
+ first_set records the first place in the block where the register
is set and is used to compute "anticipatability".
- reg_last_set records the last place in the block where the register
+ last_set records the last place in the block where the register
is set and is used to compute "availability".
+ last_bb records the block for which first_set and last_set are
+ valid, as a quick test to invalidate them.
+
reg_set_in_block records whether the register is set in the block
and is used to compute "transparency". */
rtx insn;
int regno;
{
- if (reg_first_set[regno] == NEVER_SET)
- reg_first_set[regno] = INSN_CUID (insn);
+ struct reg_avail_info *info = ®_avail_info[regno];
+ int cuid = INSN_CUID (insn);
- reg_last_set[regno] = INSN_CUID (insn);
- SET_BIT (reg_set_in_block[BLOCK_NUM (insn)], regno);
+ info->last_set = cuid;
+ if (info->last_bb != current_bb)
+ {
+ info->last_bb = current_bb;
+ info->first_set = cuid;
+ SET_BIT (reg_set_in_block[current_bb], regno);
+ }
}
rtx insn;
{
/* load_killed_in_block_p will handle the case of calls clobbering
- everything. */
+ everything. */
modify_mem_list[BLOCK_NUM (insn)] =
alloc_INSN_LIST (insn, modify_mem_list[BLOCK_NUM (insn)]);
{
/* Note that traversals of this loop (other than for free-ing)
will break after encountering a CALL_INSN. So, there's no
- need to insert a pair of items, as canon_list_insert does. */
+ need to insert a pair of items, as canon_list_insert does. */
canon_modify_mem_list[BLOCK_NUM (insn)] =
alloc_INSN_LIST (insn, canon_modify_mem_list[BLOCK_NUM (insn)]);
}
compute_hash_table (set_p)
int set_p;
{
- int bb;
+ unsigned int i;
/* While we compute the hash table we also compute a bit array of which
registers are set in which blocks.
}
}
/* Some working arrays used to track first and last set in each block. */
- /* ??? One could use alloca here, but at some size a threshold is crossed
- beyond which one should use malloc. Are we at that threshold here? */
- reg_first_set = (int *) gmalloc (max_gcse_regno * sizeof (int));
- reg_last_set = (int *) gmalloc (max_gcse_regno * sizeof (int));
+ reg_avail_info = (struct reg_avail_info*)
+ gmalloc (max_gcse_regno * sizeof (struct reg_avail_info));
- for (bb = 0; bb < n_basic_blocks; bb++)
+ for (i = 0; i < max_gcse_regno; ++i)
+ reg_avail_info[i].last_bb = NEVER_SET;
+
+ for (current_bb = 0; current_bb < n_basic_blocks; current_bb++)
{
rtx insn;
unsigned int regno;
int in_libcall_block;
- unsigned int i;
/* First pass over the instructions records information used to
determine when registers and memory are first and last set.
??? hard-reg reg_set_in_block computation
could be moved to compute_sets since they currently don't change. */
- for (i = 0; i < max_gcse_regno; i++)
- reg_first_set[i] = reg_last_set[i] = NEVER_SET;
-
-
- for (insn = BLOCK_HEAD (bb);
- insn && insn != NEXT_INSN (BLOCK_END (bb));
+ for (insn = BLOCK_HEAD (current_bb);
+ insn && insn != NEXT_INSN (BLOCK_END (current_bb));
insn = NEXT_INSN (insn))
{
-#ifdef NON_SAVING_SETJMP
- if (NON_SAVING_SETJMP && GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
- {
- for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- record_last_reg_set_info (insn, regno);
- continue;
- }
-#endif
-
if (! INSN_P (insn))
continue;
if (GET_CODE (insn) == CALL_INSN)
{
+ bool clobbers_all = false;
+#ifdef NON_SAVING_SETJMP
+ if (NON_SAVING_SETJMP
+ && find_reg_note (insn, REG_SETJMP, NULL_RTX))
+ clobbers_all = true;
+#endif
+
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
+ if (clobbers_all
+ || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
record_last_reg_set_info (insn, regno);
- if (! CONST_CALL_P (insn))
- record_last_mem_set_info (insn);
+ mark_call (insn);
}
note_stores (PATTERN (insn), record_last_set_info, insn);
/* The next pass builds the hash table. */
- for (insn = BLOCK_HEAD (bb), in_libcall_block = 0;
- insn && insn != NEXT_INSN (BLOCK_END (bb));
+ for (insn = BLOCK_HEAD (current_bb), in_libcall_block = 0;
+ insn && insn != NEXT_INSN (BLOCK_END (current_bb));
insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
- in_libcall_block = 1;
- else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
- in_libcall_block = 0;
- hash_scan_insn (insn, set_p, in_libcall_block);
+ in_libcall_block = 1;
+ else if (set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX))
+ in_libcall_block = 0;
+ hash_scan_insn (insn, set_p, in_libcall_block);
+ if (!set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX))
+ in_libcall_block = 0;
}
}
- free (reg_first_set);
- free (reg_last_set);
-
- /* Catch bugs early. */
- reg_first_set = reg_last_set = 0;
+ free (reg_avail_info);
+ reg_avail_info = NULL;
}
/* Allocate space for the set hash table.
mark_call (insn)
rtx insn;
{
- if (! CONST_CALL_P (insn))
+ if (! CONST_OR_PURE_CALL_P (insn))
record_last_mem_set_info (insn);
}
}
/* This wrapper for expr_reaches_here_p_work() is to ensure that any
- memory allocated for that function is returned. */
+ memory allocated for that function is returned. */
static int
expr_reaches_here_p (occr, expr, bb, check_self_loop)
note = find_reg_equal_equiv_note (insn);
- /* We may win even when propagating constants into notes. */
+ /* We may win even when propagating constants into notes. */
if (note)
find_used_regs (&XEXP (note, 0), NULL);
struct expr *set;
/* Ignore registers created by GCSE.
- We do this because ... */
+ We do this because ... */
if (regno >= max_gcse_regno)
continue;
}
/* The wrapper for pre_expr_reaches_here_work that ensures that any
- memory allocated for that function is returned. */
+ memory allocated for that function is returned. */
static int
pre_expr_reaches_here_p (occr_bb, expr, bb)
We no longer ignore such label references (see LABEL_REF handling in
mark_jump_label for additional information). */
- REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
+ REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL, XEXP (x, 0),
REG_NOTES (insn));
if (LABEL_P (XEXP (x, 0)))
LABEL_NUSES (XEXP (x, 0))++;
free_ldst_entry (ptr)
struct ls_expr * ptr;
{
+ free_INSN_LIST_list (& ptr->loads);
+ free_INSN_LIST_list (& ptr->stores);
- free_INSN_LIST_list (&ptr->stores);
- free_INSN_LIST_list (&ptr->loads);
free (ptr);
}
if (GET_MODE (x) == BLKmode)
return 0;
-#if 0
- /* See comment in find_moveable_store */
- if (!rtx_addr_varies_p (XEXP (x, 0), 0))
+
+ if (!rtx_varies_p (XEXP (x, 0), 0))
return 1;
-#endif
+
return 0;
}
/* Make sure there isn't a buried load somewhere. */
invalidate_any_buried_refs (src);
}
+
/* Check for stores. Don't worry about aliased ones, they
will block any movement we might do later. We only care
about this exact pattern since those are the only
\f
/* Store motion code. */
+/* This is used to communicate the target bitvector we want to use in the
+ reg_set_info routine when called via the note_stores mechanism. */
+static sbitmap * regvec;
+
/* Used in computing the reverse edge graph bit vectors. */
static sbitmap * st_antloc;
/* Global holding the number of store expressions we are dealing with. */
static int num_stores;
+/* Checks to set if we need to mark a register set. Called from note_stores. */
-/* Mark which registers are used by the mem, in the sbitmap used. */
-static int
-mark_mem_regs (x, used)
- rtx x;
- sbitmap used;
+static void
+reg_set_info (dest, setter, data)
+ rtx dest, setter ATTRIBUTE_UNUSED;
+ void * data ATTRIBUTE_UNUSED;
{
- register const char *fmt;
- int i, j;
-
- if (GET_CODE (x) == REG)
- {
- if (!TEST_BIT (used, REGNO (x)))
- {
- SET_BIT (used, REGNO (x));
- return 1;
-}
- return 0;
- }
-
- fmt = GET_RTX_FORMAT (GET_CODE (x));
- for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e')
- {
- if (mark_mem_regs (XEXP (x, i),used))
- return 1;
- }
- else if (fmt[i] == 'E')
- for (j = XVECLEN (x, i) - 1; j >= 0; j--)
- if (mark_mem_regs (XVECEXP (x, i, j),used))
- return 1;
- }
+ if (GET_CODE (dest) == SUBREG)
+ dest = SUBREG_REG (dest);
- return 0;
+ if (GET_CODE (dest) == REG)
+ SET_BIT (*regvec, REGNO (dest));
}
-
/* Return non-zero if the register operands of expression X are killed
- before/after insn in basic block BB. */
+ anywhere in basic block BB. */
static int
-store_ops_ok (x, bb,insn, before)
+store_ops_ok (x, bb)
rtx x;
basic_block bb;
- rtx insn;
- int before;
{
int i;
enum rtx_code code;
switch (code)
{
case REG:
- {
- /* Okay, since the reg def chains are ordered by bb/insn
- (since that's how it calculates them, and even if it didn't,
- we could just sort them), we just walk until we find a def
- in our BB, then walk until we find a def after/before our
- insn, and if we find a reg def after/before our insn, in the
- same bb, we return the approriate value. If there is no
- such def, to prevent walking *every* reg def, we stop once
- we are out of our BB again. */
- struct df_link *currref;
- bool thereyet=FALSE;
- for (currref = df_analyzer->regs[REGNO(x)].defs;
- currref;
- currref = currref->next)
- {
- if (! (DF_REF_BB (currref->ref) == bb))
- {
- if (!thereyet)
- continue;
- else
- return 1;
- }
- if (before)
- {
- if (INSN_UID (DF_REF_INSN (currref->ref)) >= INSN_UID (insn))
- continue;
- }
- else
- {
- if (INSN_UID (DF_REF_INSN (currref->ref)) < INSN_UID (insn))
- continue;
- }
- thereyet = TRUE;
- if (DF_REF_TYPE (currref->ref) == DF_REF_REG_DEF)
- return 0;
- }
- return 1;
- }
+ /* If a reg has changed after us in this
+ block, the operand has been killed. */
+ return TEST_BIT (reg_set_in_block[bb->index], REGNO (x));
-
case MEM:
x = XEXP (x, 0);
goto repeat;
goto repeat;
}
- if (! store_ops_ok (tem, bb, insn, before))
+ if (! store_ops_ok (tem, bb))
return 0;
}
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
{
- if (! store_ops_ok (XVECEXP (x, i, j), bb, insn, before))
+ if (! store_ops_ok (XVECEXP (x, i, j), bb))
return 0;
}
}
return 1;
}
-/* Determine whether insn is MEM store pattern that we will consider
- moving. We'll consider moving pretty much anything that we can
- move safely. */
+/* Determine whether insn is MEM store pattern that we will consider moving. */
static void
find_moveable_store (insn)
struct ls_expr * ptr;
rtx dest = PATTERN (insn);
- /* It's it's not a set, it's not a mem store we want to consider.
- Also, if it's an ASM, we certainly don't want to try to touch
- it. */
if (GET_CODE (dest) != SET
|| GET_CODE (SET_SRC (dest)) == ASM_OPERANDS)
return;
if (GET_CODE (dest) != MEM || MEM_VOLATILE_P (dest)
|| GET_MODE (dest) == BLKmode)
+ return;
+
+ if (GET_CODE (XEXP (dest, 0)) != SYMBOL_REF)
return;
-#if 0
- /* ??? Is this conservative, or just correct? We get more
- *candidates* without it, but i don't think we ever remove any
- stores where the address did vary. */
- if (rtx_addr_varies_p (XEXP (dest, 0), 0))
+
+ if (rtx_varies_p (XEXP (dest, 0), 0))
return;
-#endif
+
ptr = ldst_entry (dest);
ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
}
-/* Perform store motion.
- Store motion is modeled as a lazy code motion problem, like PRE is
- above. The main diffence is that we want to move stores down as far
- as possible, so we have LCM work on the reverse flowgraph. */
+/* Perform store motion. Much like gcse, except we move expressions the
+ other way by looking at the flowgraph in reverse. */
static int
compute_store_table ()
{
int bb, ret;
+ unsigned regno;
rtx insn, pat;
+
max_gcse_regno = max_reg_num ();
+ reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks,
+ max_gcse_regno);
+ sbitmap_vector_zero (reg_set_in_block, n_basic_blocks);
pre_ldst_mems = 0;
+
/* Find all the stores we care about. */
for (bb = 0; bb < n_basic_blocks; bb++)
{
+ regvec = & (reg_set_in_block[bb]);
for (insn = BLOCK_END (bb);
insn && insn != PREV_INSN (BLOCK_HEAD (bb));
insn = PREV_INSN (insn))
{
/* Ignore anything that is not a normal insn. */
- if (!INSN_P (insn))
+ if (! INSN_P (insn))
continue;
+ if (GET_CODE (insn) == CALL_INSN)
+ {
+ bool clobbers_all = false;
+#ifdef NON_SAVING_SETJMP
+ if (NON_SAVING_SETJMP
+ && find_reg_note (insn, REG_SETJMP, NULL_RTX))
+ clobbers_all = true;
+#endif
+
+ for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
+ if (clobbers_all
+ || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
+ SET_BIT (reg_set_in_block[bb], regno);
+ }
+
pat = PATTERN (insn);
+ note_stores (pat, reg_set_info, NULL);
+
/* Now that we've marked regs, look for stores. */
if (GET_CODE (pat) == SET)
find_moveable_store (insn);
return ret;
}
-/* Check to see if the load X is aliased with STORE_PATTERN.
- If it is, it means that load kills the store.*/
+/* Check to see if the load X is aliased with STORE_PATTERN. */
static int
load_kills_store (x, store_pattern)
return 0;
}
-/* Go through the entire insn X, looking for any loads which might
- alias, and therefore, kill, STORE_PATTERN. Return 1 if found. */
+/* Go through the entire insn X, looking for any loads which might alias
+ STORE_PATTERN. Return 1 if found. */
static int
find_loads (x, store_pattern)
int i,j;
int ret = 0;
+ if (!x)
+ return 0;
+
if (GET_CODE (x) == SET)
x = SET_SRC (x);
if (GET_CODE (insn) == CALL_INSN)
{
- if (CONST_CALL_P (insn))
+ if (CONST_OR_PURE_CALL_P (insn))
return 0;
else
return 1;
rtx pat = PATTERN (insn);
/* Check for memory stores to aliased objects. */
if (GET_CODE (SET_DEST (pat)) == MEM && !expr_equiv_p (SET_DEST (pat), x))
- {
+ /* pretend its a load and check for aliasing. */
if (find_loads (SET_DEST (pat), x))
return 1;
- }
return find_loads (SET_SRC (pat), x);
}
else
within basic block BB. */
static int
-store_killed_after (x, insn, bb, testops)
+store_killed_after (x, insn, bb)
rtx x, insn;
basic_block bb;
- int testops;
{
rtx last = bb->end;
if (insn == last)
return 0;
-
- if (testops)
- /* Check if the register operands of the store are OK in this block.*/
- if (!store_ops_ok (XEXP (x, 0), bb, insn, 0))
+
+ /* Check if the register operands of the store are OK in this block.
+ Note that if registers are changed ANYWHERE in the block, we'll
+ decide we can't move it, regardless of whether it changed above
+ or below the store. This could be improved by checking the register
+ operands while lookinng for aliasing in each insn. */
+ if (!store_ops_ok (XEXP (x, 0), bb))
return 1;
- for ( ;
- insn && insn != NEXT_INSN (last);
- insn = NEXT_INSN (insn))
+ for ( ; insn && insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
if (store_killed_in_insn (x, insn))
return 1;
return 0;
}
-/* Returns 1 if the expression X is loaded or clobbered before INSN
+/* Returns 1 if the expression X is loaded or clobbered on or before INSN
within basic block BB. */
static int
store_killed_before (x, insn, bb)
if (insn == first)
return store_killed_in_insn (x, insn);
- /* Check if the register operands of the store are OK in this block.*/
- if (!store_ops_ok (XEXP (x, 0), bb, insn, 1))
+
+ /* Check if the register operands of the store are OK in this block.
+ Note that if registers are changed ANYWHERE in the block, we'll
+ decide we can't move it, regardless of whether it changed above
+ or below the store. This could be improved by checking the register
+ operands while lookinng for aliasing in each insn. */
+ if (!store_ops_ok (XEXP (x, 0), bb))
return 1;
- for (insn = PREV_INSN (insn) ;
- insn && insn != PREV_INSN (first);
- insn = PREV_INSN (insn))
-
+ for ( ; insn && insn != PREV_INSN (first); insn = PREV_INSN (insn))
if (store_killed_in_insn (x, insn))
return 1;
build_store_vectors ()
{
basic_block bb;
- int b,i,j;
+ int b;
rtx insn, st;
struct ls_expr * ptr;
- sbitmap tested, *result;
- sbitmap used;
/* Build the gen_vector. This is any store in the table which is not killed
by aliasing later in its block. */
st_antloc = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, num_stores);
sbitmap_vector_zero (st_antloc, n_basic_blocks);
-
- /* Note: In case someone needs something to optimize about store
- motion, here's the next place to look. We currently test one more
- basic block per store than necessary (at least). Since we know, at
- the end of this for loop, whether a store was killed in one of the
- basic blocks (We know both whether it's killed before, and killed
- after, the insn in the bb it resides in. So unless the insn
- consists of multiple store/loads, we know whether it was killed
- in the entire bb), we could avoid testing it for kill and transp in
- the next for loop. */
+
for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
{
/* Put all the stores into either the antic list, or the avail list,
{
insn = XEXP (st, 0);
bb = BLOCK_FOR_INSN (insn);
- if (!store_killed_after (ptr->pattern, insn, bb, 1))
+
+ if (!store_killed_after (ptr->pattern, insn, bb))
{
/* If we've already seen an availale expression in this block,
we can delete the one we saw already (It occurs earlier in
ae_kill = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, num_stores);
sbitmap_vector_zero (ae_kill, n_basic_blocks);
-
transp = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, num_stores);
- sbitmap_vector_ones (transp, n_basic_blocks);
-
- tested = sbitmap_alloc (max_gcse_regno);
- sbitmap_zero (tested);
- result = sbitmap_vector_alloc (n_basic_blocks, max_gcse_regno);
- sbitmap_vector_zero (result, n_basic_blocks);
- used = sbitmap_alloc (max_gcse_regno);
- sbitmap_zero (used);
-
- /* This whole big nasty thing computes kill and transparent.
- It's done in this nasty way because profiling showed store motion
- taking twice as long as GCSE, with the cause being 1 million calls
- to store_ops_ok taking 30% of the entire runtime of the
- compiler.
- Since store most expressions use the same registers, there's no
- point in checking them 8 million times for the same basic blocks. If
- they weren't okay in a BB the last time we checked, they won't be
- okay now. Since we check all the bb's on each iteration, we don't
- need a vector for which registers we've tested, just the results.
- We then proceed to use the results of what store_ops_ok was for a
- given reg and bb, and if the results were a kill, we don't even need
- to check if the store was killed in the basic block, it'll be
- in the kill set because it's regs changed between here and there.
-
-
- If the whole store had no registers, we just skip store_ops_okay
- anyway (since it's checking reg operands), and proceed to see if
- it's okay in each bb, setting the approriate bits.
-
- With this in place, we now take almost no time at all to perform
- store motion. (It's not on the first page of the profile, it
- takes less than a second).
-
- */
+ sbitmap_vector_zero (transp, n_basic_blocks);
for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
+ for (b = 0; b < n_basic_blocks; b++)
{
- /* Make sure we don't have a load-only expr, which we never seem
- to, but i don't think there's actually a guarantee */
- if (ptr->stores != NULL)
+ if (store_killed_after (ptr->pattern, BLOCK_HEAD (b), BASIC_BLOCK (b)))
{
- /* First mark the regs used by the mem */
- mark_mem_regs (ptr->pattern, used);
- /* Now see if it had any regs */
- if (!(sbitmap_first_set_bit (used) == -1))
- {
- /* For each register, see if we've tested it */
- EXECUTE_IF_SET_IN_SBITMAP (used, 0, i,
- {
- if (TEST_BIT (tested, i))
- {
- /* Already tested the register, so check the
- result, and if we had an okay result, check the
- store itself. */
- for (j = 0; j < n_basic_blocks; j++)
- {
- if (!TEST_BIT (result[j], i)
- || store_killed_after (ptr->pattern, BLOCK_HEAD (j),
- BASIC_BLOCK (j), FALSE))
- {
- SET_BIT (ae_kill[j], ptr->index);
- if (!TEST_BIT (ae_gen[j], ptr->index)
- || !TEST_BIT (st_antloc[j], ptr->index))
- RESET_BIT (transp[j], ptr->index);
- }
- }
- }
- else
- {
- /* We haven't tested it yet, so mark it tested,
- and perform the tests */
- SET_BIT (tested, i);
- /* Check if it's okay in each BB */
- for (j = 0; j < n_basic_blocks; j++)
- {
- if (store_ops_ok (XEXP (ptr->pattern, 0),
- BASIC_BLOCK (j), BLOCK_HEAD (j), 0))
- {
- SET_BIT (result[j], ptr->index);
- }
- else
- {
- /* It's not okay, so it's killed and maybe
- not transparent */
- SET_BIT (ae_kill[j], ptr->index);
- if (!TEST_BIT (ae_gen[j], ptr->index)
- || !TEST_BIT (st_antloc[j], ptr->index))
- {
- RESET_BIT (transp[j], ptr->index);
- }
- continue;
- }
- /* The ops were okay, so check the store
- itself */
- if (store_killed_after (ptr->pattern, BLOCK_HEAD (j),
- BASIC_BLOCK (j), FALSE))
- {
- SET_BIT (ae_kill[j], ptr->index);
- if (!TEST_BIT (ae_gen[j], ptr->index)
- || !TEST_BIT (st_antloc[j], ptr->index))
- {
- RESET_BIT (transp[j], ptr->index);
- }
- }
- }
- }
- });
- /* Reset the used list */
- sbitmap_zero (used);
- }
- /* If it had no registers, we come here, and do the
- approriate testing */
- else
- {
- for (j = 0; j < n_basic_blocks; j++)
- {
- if (store_killed_after (ptr->pattern, BLOCK_HEAD (j),
- BASIC_BLOCK (j), FALSE))
- {
- SET_BIT (ae_kill[j], ptr->index);
- if (!TEST_BIT (ae_gen[j], ptr->index)
- || !TEST_BIT (st_antloc[j], ptr->index))
- {
- RESET_BIT (transp[j], ptr->index);
- }
- }
- }
- }
+ /* The anticipatable expression is not killed if it's gen'd. */
+ /*
+ We leave this check out for now. If we have a code sequence
+ in a block which looks like:
+ ST MEMa = x
+ L y = MEMa
+ ST MEMa = z
+ We should flag this as having an ANTIC expression, NOT
+ transparent, NOT killed, and AVAIL.
+ Unfortunately, since we haven't re-written all loads to
+ use the reaching reg, we'll end up doing an incorrect
+ Load in the middle here if we push the store down. It happens in
+ gcc.c-torture/execute/960311-1.c with -O3
+ If we always kill it in this case, we'll sometimes do
+ uneccessary work, but it shouldn't actually hurt anything.
+ if (!TEST_BIT (ae_gen[b], ptr->index)). */
+ SET_BIT (ae_kill[b], ptr->index);
+ }
+ else
+ SET_BIT (transp[b], ptr->index);
+ }
+
+ /* Any block with no exits calls some non-returning function, so
+ we better mark the store killed here, or we might not store to
+ it at all. If we knew it was abort, we wouldn't have to store,
+ but we don't know that for sure. */
+ if (gcse_file)
+ {
+ fprintf (gcse_file, "ST_avail and ST_antic (shown under loads..)\n");
+ print_ldst_list (gcse_file);
+ dump_sbitmap_vector (gcse_file, "st_antloc", "", st_antloc, n_basic_blocks);
+ dump_sbitmap_vector (gcse_file, "st_kill", "", ae_kill, n_basic_blocks);
+ dump_sbitmap_vector (gcse_file, "Transpt", "", transp, n_basic_blocks);
+ dump_sbitmap_vector (gcse_file, "st_avloc", "", ae_gen, n_basic_blocks);
}
}
- sbitmap_free (tested);
- sbitmap_free (used);
- sbitmap_vector_free (result);
-}
/* Insert an instruction at the begining of a basic block, and update
the BLOCK_HEAD if needed. */
free_store_memory ()
{
free_ldst_mems ();
+
if (ae_gen)
sbitmap_vector_free (ae_gen);
if (ae_kill)
sbitmap_vector_free (pre_insert_map);
if (pre_delete_map)
sbitmap_vector_free (pre_delete_map);
+ if (reg_set_in_block)
+ sbitmap_vector_free (reg_set_in_block);
ae_gen = ae_kill = transp = st_antloc = NULL;
pre_insert_map = pre_delete_map = reg_set_in_block = NULL;
{
int x;
struct ls_expr * ptr;
- sbitmap trapping_expr;
- int i;
-
int update_flow = 0;
+
if (gcse_file)
{
fprintf (gcse_file, "before store motion\n");
init_alias_analysis ();
- df_analyzer = df_init();
- df_analyse (df_analyzer, 0, DF_RD_CHAIN | DF_HARD_REGS);
+
/* Find all the stores that are live to the end of their block. */
num_stores = compute_store_table ();
if (num_stores == 0)
{
- df_finish (df_analyzer);
+ sbitmap_vector_free (reg_set_in_block);
end_alias_analysis ();
return;
}
add_noreturn_fake_exit_edges ();
build_store_vectors ();
- /* Collect expressions which might trap. */
- trapping_expr = sbitmap_alloc (num_stores);
- sbitmap_zero (trapping_expr);
- for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr(ptr))
- {
- if (may_trap_p (ptr->pattern))
- SET_BIT (trapping_expr, ptr->index);
- }
- for (i = 0; i < n_basic_blocks; i++)
- {
- edge e;
-
- /* If the current block is the destination of an abnormal edge, we
- kill all trapping expressions because we won't be able to properly
- place the instruction on the edge. So make them neither
- anticipatable nor transparent. This is fairly conservative. */
- for (e = BASIC_BLOCK (i)->pred; e ; e = e->pred_next)
- if (e->flags & EDGE_ABNORMAL)
- {
- sbitmap_difference (st_antloc[i], st_antloc[i], trapping_expr);
- sbitmap_difference (transp[i], transp[i], trapping_expr);
- break;
- }
- }
-
edge_list = pre_edge_rev_lcm (gcse_file, num_stores, transp, ae_gen,
st_antloc, ae_kill, &pre_insert_map,
&pre_delete_map);
if (update_flow)
commit_edge_insertions ();
- sbitmap_free (trapping_expr);
+
free_store_memory ();
free_edge_list (edge_list);
remove_fake_edges ();
end_alias_analysis ();
- df_finish (df_analyzer);
}
OSDN Git Service
