This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[new-regalloc-branch] Perform store motion after we are done allocating
- To: gcc-patches at gcc dot gnu dot org
- Subject: [new-regalloc-branch] Perform store motion after we are done allocating
- From: Daniel Berlin <dan at cgsoftware dot com>
- Date: Wed, 25 Jul 2001 15:43:06 -0400
This helps us quite a bit when we spill.
Its the equivalent of shrink wrapping for memory, basically.
Index: ChangeLog.RA
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.RA,v
retrieving revision 1.1.2.35
diff -c -3 -p -w -B -b -r1.1.2.35 ChangeLog.RA
*** ChangeLog.RA 2001/07/20 19:31:31 1.1.2.35
--- ChangeLog.RA 2001/07/25 19:40:53
***************
*** 1,3 ****
--- 1,11 ----
+ 2001-07-25 Daniel Berlin <dan@cgsoftware.com>
+
+ * gcse.c: Store motion stuff from patch submitted to mainline.
+
+ * ra.c (reg_alloc): Call store motion when we are done allocating.
+
+ * rtl.h: Add store_motion prototype.
+
2001-07-20 Daniel Berlin <dan@cgsoftware.com>
* params.def: Turn the C++ inlining default down like it is on the
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gcse.c,v
retrieving revision 1.113.2.2
diff -c -3 -p -w -B -b -r1.113.2.2 gcse.c
*** gcse.c 2001/07/17 21:41:01 1.113.2.2
--- gcse.c 2001/07/25 19:40:59
*************** Boston, MA 02111-1307, USA. */
*** 160,167 ****
#include "expr.h"
#include "ggc.h"
#include "params.h"
-
#include "obstack.h"
#define obstack_chunk_alloc gmalloc
#define obstack_chunk_free free
--- 160,167 ----
#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
*************** struct ls_expr
*** 466,473 ****
{
struct expr * expr; /* Gcse expression reference for LM. */
rtx pattern; /* Pattern of this mem. */
! 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. */
--- 466,473 ----
{
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 */
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 invalidate_any_buried_refs P
*** 676,689 ****
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 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));
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));
--- 676,688 ----
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 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_before PARAMS ((rtx, rtx, basic_block));
static void build_store_vectors PARAMS ((void));
static void insert_insn_start_bb PARAMS ((rtx, basic_block));
*************** static void replace_store_insn PARAMS (
*** 692,698 ****
static void delete_store PARAMS ((struct ls_expr *,
basic_block));
static void free_store_memory PARAMS ((void));
- static void store_motion PARAMS ((void));
/* Entry point for global common subexpression elimination.
F is the first instruction in the function. */
--- 691,696 ----
*************** static void
*** 5925,5933 ****
free_ldst_entry (ptr)
struct ls_expr * ptr;
{
- free_INSN_LIST_list (& ptr->loads);
- free_INSN_LIST_list (& ptr->stores);
free (ptr);
}
--- 5923,5931 ----
free_ldst_entry (ptr)
struct ls_expr * ptr;
{
+ free_INSN_LIST_list (&ptr->stores);
+ free_INSN_LIST_list (&ptr->loads);
free (ptr);
}
*************** simple_mem (x)
*** 6048,6057 ****
if (GET_MODE (x) == BLKmode)
return 0;
!
! if (!rtx_varies_p (XEXP (x, 0), 0))
return 1;
!
return 0;
}
--- 6046,6056 ----
if (GET_MODE (x) == BLKmode)
return 0;
! #if 0
! /* See comment in find_moveable_store */
! if (!rtx_addr_varies_p (XEXP (x, 0), 0))
return 1;
! #endif
return 0;
}
*************** update_ld_motion_stores (expr)
*** 6280,6316 ****
/* 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. */
! static void
! reg_set_info (dest, setter, data)
! rtx dest, setter ATTRIBUTE_UNUSED;
! void * data ATTRIBUTE_UNUSED;
{
! if (GET_CODE (dest) == SUBREG)
! dest = SUBREG_REG (dest);
! if (GET_CODE (dest) == REG)
! SET_BIT (*regvec, REGNO (dest));
}
/* Return non-zero if the register operands of expression X are killed
! anywhere in basic block BB. */
static int
! store_ops_ok (x, bb)
rtx x;
basic_block bb;
{
int i;
enum rtx_code code;
--- 6279,6339 ----
/* Store motion code. */
/* 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;
! /* Dataflow analyzer to figure out reg-def chains */
! struct df *df_analyzer;
! /* Mark which registers are used by the mem, in the sbitmap used. */
! static int
! mark_mem_regs (x, used)
! rtx x;
! sbitmap used;
{
! 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;
+ }
+
+ return 0;
+ }
+
+
/* Return non-zero if the register operands of expression X are killed
! before/after insn in basic block BB. */
static int
! store_ops_ok (x, bb,insn, before)
rtx x;
basic_block bb;
+ rtx insn;
+ int before;
{
int i;
enum rtx_code code;
*************** store_ops_ok (x, bb)
*** 6326,6334 ****
switch (code)
{
case REG:
! /* 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);
--- 6349,6393 ----
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;
! }
!
case MEM:
x = XEXP (x, 0);
*************** store_ops_ok (x, bb)
*** 6373,6379 ****
goto repeat;
}
! if (! store_ops_ok (tem, bb))
return 0;
}
else if (fmt[i] == 'E')
--- 6432,6438 ----
goto repeat;
}
! if (! store_ops_ok (tem, bb, insn, before))
return 0;
}
else if (fmt[i] == 'E')
*************** store_ops_ok (x, bb)
*** 6382,6388 ****
for (j = 0; j < XVECLEN (x, i); j++)
{
! if (! store_ops_ok (XVECEXP (x, i, j), bb))
return 0;
}
}
--- 6441,6447 ----
for (j = 0; j < XVECLEN (x, i); j++)
{
! if (! store_ops_ok (XVECEXP (x, i, j), bb, insn, before))
return 0;
}
}
*************** store_ops_ok (x, bb)
*** 6391,6397 ****
return 1;
}
! /* Determine whether insn is MEM store pattern that we will consider moving. */
static void
find_moveable_store (insn)
--- 6450,6458 ----
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. */
static void
find_moveable_store (insn)
*************** find_moveable_store (insn)
*** 6400,6405 ****
--- 6461,6469 ----
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;
*************** find_moveable_store (insn)
*** 6409,6442 ****
if (GET_CODE (dest) != MEM || MEM_VOLATILE_P (dest)
|| GET_MODE (dest) == BLKmode)
return;
!
! if (GET_CODE (XEXP (dest, 0)) != SYMBOL_REF)
! return;
!
! if (rtx_varies_p (XEXP (dest, 0), 0))
return;
!
ptr = ldst_entry (dest);
ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
}
! /* 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++)
{
--- 6473,6502 ----
if (GET_CODE (dest) != MEM || MEM_VOLATILE_P (dest)
|| GET_MODE (dest) == BLKmode)
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))
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. */
static int
compute_store_table ()
{
int bb, ret;
rtx insn, pat;
max_gcse_regno = max_reg_num ();
pre_ldst_mems = 0;
/* Find all the stores we care about. */
for (bb = 0; bb < n_basic_blocks; bb++)
{
*************** compute_store_table ()
*** 6440,6473 ****
/* 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))
{
- #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++)
- SET_BIT (reg_set_in_block[bb], regno);
- continue;
- }
- #endif
/* Ignore anything that is not a normal insn. */
! if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
continue;
- if (GET_CODE (insn) == CALL_INSN)
- {
- for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- if (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);
--- 6500,6514 ----
/* Find all the stores we care about. */
for (bb = 0; bb < n_basic_blocks; 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))
continue;
pat = PATTERN (insn);
/* Now that we've marked regs, look for stores. */
if (GET_CODE (pat) == SET)
find_moveable_store (insn);
*************** compute_store_table ()
*** 6476,6491 ****
ret = enumerate_ldsts ();
! if (gcse_file)
{
! fprintf (gcse_file, "Store Motion Expressions.\n");
! print_ldst_list (gcse_file);
}
return ret;
}
! /* Check to see if the load X is aliased with STORE_PATTERN. */
static int
load_kills_store (x, store_pattern)
--- 6517,6533 ----
ret = enumerate_ldsts ();
! if (rtl_dump_file)
{
! fprintf (rtl_dump_file, "Store Motion Expressions.\n");
! print_ldst_list (rtl_dump_file);
}
return ret;
}
! /* Check to see if the load X is aliased with STORE_PATTERN.
! If it is, it means that load kills the store.*/
static int
load_kills_store (x, store_pattern)
*************** load_kills_store (x, store_pattern)
*** 6496,6503 ****
return 0;
}
! /* 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)
--- 6538,6545 ----
return 0;
}
! /* Go through the entire insn X, looking for any loads which might
! alias, and therefore, kill, STORE_PATTERN. Return 1 if found. */
static int
find_loads (x, store_pattern)
*************** store_killed_in_insn (x, insn)
*** 6553,6561 ****
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
--- 6595,6604 ----
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))
! {
if (find_loads (SET_DEST (pat), x))
return 1;
+ }
return find_loads (SET_SRC (pat), x);
}
else
*************** store_killed_in_insn (x, insn)
*** 6566,6596 ****
within basic block BB. */
static int
! store_killed_after (x, insn, bb)
rtx x, insn;
basic_block bb;
{
rtx last = bb->end;
if (insn == last)
return 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))
if (store_killed_in_insn (x, insn))
return 1;
return 0;
}
! /* 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)
--- 6609,6639 ----
within basic block BB. */
static int
! store_killed_after (x, insn, bb, testops)
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))
return 1;
! 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
within basic block BB. */
static int
store_killed_before (x, insn, bb)
*************** store_killed_before (x, insn, bb)
*** 6601,6616 ****
if (insn == first)
return store_killed_in_insn (x, insn);
!
! /* 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 != PREV_INSN (first); insn = PREV_INSN (insn))
if (store_killed_in_insn (x, insn))
return 1;
--- 6644,6657 ----
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))
return 1;
+
+ for (insn = PREV_INSN (insn) ;
+ insn && insn != PREV_INSN (first);
+ insn = PREV_INSN (insn))
if (store_killed_in_insn (x, insn))
return 1;
*************** static void
*** 6627,6635 ****
build_store_vectors ()
{
basic_block bb;
! int b;
rtx insn, st;
struct ls_expr * ptr;
/* Build the gen_vector. This is any store in the table which is not killed
by aliasing later in its block. */
--- 6668,6678 ----
build_store_vectors ()
{
basic_block bb;
! int b,i,j;
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. */
*************** build_store_vectors ()
*** 6639,6644 ****
--- 6682,6696 ----
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,
*************** build_store_vectors ()
*** 6650,6657 ****
{
insn = XEXP (st, 0);
bb = BLOCK_FOR_INSN (insn);
!
! 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
--- 6702,6708 ----
{
insn = XEXP (st, 0);
bb = BLOCK_FOR_INSN (insn);
! if (!store_killed_after (ptr->pattern, insn, bb, 1))
{
/* If we've already seen an availale expression in this block,
we can delete the one we saw already (It occurs earlier in
*************** build_store_vectors ()
*** 6668,6675 ****
if (st)
{
rtx r = gen_reg_rtx (GET_MODE (ptr->pattern));
! if (gcse_file)
! fprintf(gcse_file, "Removing redundant store:\n");
replace_store_insn (r, XEXP (st, 0), bb);
XEXP (st, 0) = insn;
continue;
--- 6719,6726 ----
if (st)
{
rtx r = gen_reg_rtx (GET_MODE (ptr->pattern));
! if (rtl_dump_file)
! fprintf(rtl_dump_file, "Removing redundant store:\n");
replace_store_insn (r, XEXP (st, 0), bb);
XEXP (st, 0) = insn;
continue;
*************** build_store_vectors ()
*** 6695,6744 ****
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_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++)
{
! if (store_killed_after (ptr->pattern, BLOCK_HEAD (b), BASIC_BLOCK (b)))
{
! /* 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);
}
}
/* Insert an instruction at the begining of a basic block, and update
the BLOCK_HEAD if needed. */
--- 6746,6887 ----
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).
!
! ??? I'm not sure !TEST_BIT (ae_gen[j], ptr->index) is really the right
! test. I have a gut feeling it should be !TEST_BIT (ae_gen[j],
! ptr->index) && !TEST_BIT (st_antloc[j], ptr->index). I.E. If we know
! it's somehow not killed before, or after, it's transparent.
! */
for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
{
! /* 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)
{
! /* 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))
! 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))
! {
! 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))
! {
! 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))
! {
! RESET_BIT (transp[j], ptr->index);
! }
! }
}
}
+ }
+ }
+ 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. */
*************** insert_insn_start_bb (insn, bb)
*** 6770,6781 ****
set_block_for_new_insns (insn, bb);
! if (gcse_file)
{
! fprintf (gcse_file, "STORE_MOTION insert store at start of BB %d:\n",
bb->index);
! print_inline_rtx (gcse_file, insn, 6);
! fprintf (gcse_file, "\n");
}
}
--- 6913,6924 ----
set_block_for_new_insns (insn, bb);
! if (rtl_dump_file)
{
! fprintf (rtl_dump_file, "STORE_MOTION insert store at start of BB %d:\n",
bb->index);
! print_inline_rtx (rtl_dump_file, insn, 6);
! fprintf (rtl_dump_file, "\n");
}
}
*************** insert_store (expr, e)
*** 6836,6847 ****
insert_insn_on_edge (insn, e);
! if (gcse_file)
{
! fprintf (gcse_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
e->src->index, e->dest->index);
! print_inline_rtx (gcse_file, insn, 6);
! fprintf (gcse_file, "\n");
}
return 1;
--- 6979,6990 ----
insert_insn_on_edge (insn, e);
! if (rtl_dump_file)
{
! fprintf (rtl_dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
e->src->index, e->dest->index);
! print_inline_rtx (rtl_dump_file, insn, 6);
! fprintf (rtl_dump_file, "\n");
}
return 1;
*************** replace_store_insn (reg, del, bb)
*** 6860,6873 ****
insn = emit_insn_after (insn, del);
set_block_for_new_insns (insn, bb);
! if (gcse_file)
{
! fprintf (gcse_file,
"STORE_MOTION delete insn in BB %d:\n ", bb->index);
! print_inline_rtx (gcse_file, del, 6);
! fprintf(gcse_file, "\nSTORE MOTION replaced with insn:\n ");
! print_inline_rtx (gcse_file, insn, 6);
! fprintf(gcse_file, "\n");
}
if (bb->end == del)
--- 7003,7016 ----
insn = emit_insn_after (insn, del);
set_block_for_new_insns (insn, bb);
! if (rtl_dump_file)
{
! fprintf (rtl_dump_file,
"STORE_MOTION delete insn in BB %d:\n ", bb->index);
! print_inline_rtx (rtl_dump_file, del, 6);
! fprintf(rtl_dump_file, "\nSTORE MOTION replaced with insn:\n ");
! print_inline_rtx (rtl_dump_file, insn, 6);
! fprintf(rtl_dump_file, "\n");
}
if (bb->end == del)
*************** static void
*** 6917,6923 ****
free_store_memory ()
{
free_ldst_mems ();
-
if (ae_gen)
sbitmap_vector_free (ae_gen);
if (ae_kill)
--- 7060,7065 ----
*************** free_store_memory ()
*** 6930,6937 ****
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;
--- 7072,7077 ----
*************** free_store_memory ()
*** 6940,6975 ****
/* Perform store motion. Much like gcse, except we move expressions the
other way by looking at the flowgraph in reverse. */
! static void
store_motion ()
{
int x;
struct ls_expr * ptr;
! int update_flow = 0;
! if (gcse_file)
{
! fprintf (gcse_file, "before store motion\n");
! print_rtl (gcse_file, get_insns ());
}
init_alias_analysis ();
!
/* Find all the stores that are live to the end of their block. */
num_stores = compute_store_table ();
if (num_stores == 0)
{
! sbitmap_vector_free (reg_set_in_block);
end_alias_analysis ();
! return;
}
/* Now compute whats actually available to move. */
add_noreturn_fake_exit_edges ();
build_store_vectors ();
! edge_list = pre_edge_rev_lcm (gcse_file, num_stores, transp, ae_gen,
st_antloc, ae_kill, &pre_insert_map,
&pre_delete_map);
--- 7080,7143 ----
/* Perform store motion. Much like gcse, except we move expressions the
other way by looking at the flowgraph in reverse. */
! int
store_motion ()
{
int x;
struct ls_expr * ptr;
! sbitmap trapping_expr;
! int i;
! int update_flow = 0;
! if (rtl_dump_file)
{
! fprintf (rtl_dump_file, "before store motion\n");
! print_rtl (rtl_dump_file, get_insns ());
}
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);
end_alias_analysis ();
! return 0;
}
/* Now compute whats actually available to move. */
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 (rtl_dump_file, num_stores, transp, ae_gen,
st_antloc, ae_kill, &pre_insert_map,
&pre_delete_map);
*************** store_motion ()
*** 6987,6995 ****
if (update_flow)
commit_edge_insertions ();
!
free_store_memory ();
free_edge_list (edge_list);
remove_fake_edges ();
end_alias_analysis ();
}
--- 7155,7165 ----
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);
+ return 1;
}
Index: ra.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ra.c,v
retrieving revision 1.1.2.21
diff -c -3 -p -w -B -b -r1.1.2.21 ra.c
*** ra.c 2001/07/20 16:38:13 1.1.2.21
--- ra.c 2001/07/25 19:41:04
*************** reg_alloc (void)
*** 4079,4086 ****
/*if (rtl_dump_file)
print_rtl_with_bb (rtl_dump_file, get_insns ());*/
! no_new_pseudos = 1;
compute_bb_for_insn (get_max_uid ());
/*recompute_reg_usage (get_insns (), TRUE);
regclass (get_insns (), max_reg_num (), rtl_dump_file);*/
/*count_or_remove_death_notes (NULL, 1);
--- 4079,4089 ----
/*if (rtl_dump_file)
print_rtl_with_bb (rtl_dump_file, get_insns ());*/
! no_new_pseudos = 0;
compute_bb_for_insn (get_max_uid ());
+ store_motion();
+ allocate_reg_info (max_reg_num (), 0, 1);
+ no_new_pseudos = 1;
/*recompute_reg_usage (get_insns (), TRUE);
regclass (get_insns (), max_reg_num (), rtl_dump_file);*/
/*count_or_remove_death_notes (NULL, 1);
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.240.2.4
diff -c -3 -p -w -B -b -r1.240.2.4 rtl.h
*** rtl.h 2001/07/19 23:07:56 1.240.2.4
--- rtl.h 2001/07/25 19:41:06
*************** extern rtx expand_mult_highpart PARAMS
*** 1851,1856 ****
--- 1851,1857 ----
/* In gcse.c */
#ifdef BUFSIZ
extern int gcse_main PARAMS ((rtx, FILE *));
+ extern int store_motion PARAMS ((void));
#endif
/* In global.c */
--
"If you were going to shoot a mime, would you use a silencer?
"-Steven Wright