+\f
+/* Here we provide the things required to do store motion towards
+ the exit. In order for this to be effective, gcse also needed to
+ be taught how to move a load when it is kill only by a store to itself.
+
+ int i;
+ float a[10];
+
+ void foo(float scale)
+ {
+ for (i=0; i<10; i++)
+ a[i] *= scale;
+ }
+
+ 'i' is both loaded and stored to in the loop. Normally, gcse cannot move
+ the load out since its live around the loop, and stored at the bottom
+ of the loop.
+
+ The 'Load Motion' referred to and implemented in this file is
+ an enhancement to gcse which when using edge based lcm, recognizes
+ this situation and allows gcse to move the load out of the loop.
+
+ Once gcse has hoisted the load, store motion can then push this
+ load towards the exit, and we end up with no loads or stores of 'i'
+ in the loop. */
+
+/* This will search the ldst list for a matching expression. If it
+ doesn't find one, we create one and initialize it. */
+
+static struct ls_expr *
+ldst_entry (x)
+ rtx x;
+{
+ struct ls_expr * ptr;
+
+ for (ptr = first_ls_expr(); ptr != NULL; ptr = next_ls_expr (ptr))
+ if (expr_equiv_p (ptr->pattern, x))
+ break;
+
+ if (!ptr)
+ {
+ ptr = (struct ls_expr *) xmalloc (sizeof (struct ls_expr));
+
+ ptr->next = pre_ldst_mems;
+ ptr->expr = NULL;
+ ptr->pattern = x;
+ ptr->loads = NULL_RTX;
+ ptr->stores = NULL_RTX;
+ ptr->reaching_reg = NULL_RTX;
+ ptr->invalid = 0;
+ ptr->index = 0;
+ ptr->hash_index = 0;
+ pre_ldst_mems = ptr;
+ }
+
+ return ptr;
+}
+
+/* Free up an individual ldst entry. */
+
+static void
+free_ldst_entry (ptr)
+ struct ls_expr * ptr;
+{
+ free_INSN_LIST_list (& ptr->loads);
+ free_INSN_LIST_list (& ptr->stores);
+
+ free (ptr);
+}
+
+/* Free up all memory associated with the ldst list. */
+
+static void
+free_ldst_mems ()
+{
+ while (pre_ldst_mems)
+ {
+ struct ls_expr * tmp = pre_ldst_mems;
+
+ pre_ldst_mems = pre_ldst_mems->next;
+
+ free_ldst_entry (tmp);
+ }
+
+ pre_ldst_mems = NULL;
+}
+
+/* Dump debugging info about the ldst list. */
+
+static void
+print_ldst_list (file)
+ FILE * file;
+{
+ struct ls_expr * ptr;
+
+ fprintf (file, "LDST list: \n");
+
+ for (ptr = first_ls_expr(); ptr != NULL; ptr = next_ls_expr (ptr))
+ {
+ fprintf (file, " Pattern (%3d): ", ptr->index);
+
+ print_rtl (file, ptr->pattern);
+
+ fprintf (file, "\n Loads : ");
+
+ if (ptr->loads)
+ print_rtl (file, ptr->loads);
+ else
+ fprintf (file, "(nil)");
+
+ fprintf (file, "\n Stores : ");
+
+ if (ptr->stores)
+ print_rtl (file, ptr->stores);
+ else
+ fprintf (file, "(nil)");
+
+ fprintf (file, "\n\n");
+ }
+
+ fprintf (file, "\n");
+}
+
+/* Returns 1 if X is in the list of ldst only expressions. */
+
+static struct ls_expr *
+find_rtx_in_ldst (x)
+ rtx x;
+{
+ struct ls_expr * ptr;
+
+ for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
+ if (expr_equiv_p (ptr->pattern, x) && ! ptr->invalid)
+ return ptr;
+
+ return NULL;
+}
+
+/* Assign each element of the list of mems a monotonically increasing value. */
+
+static int
+enumerate_ldsts ()
+{
+ struct ls_expr * ptr;
+ int n = 0;
+
+ for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
+ ptr->index = n++;
+
+ return n;
+}
+
+/* Return first item in the list. */
+
+static inline struct ls_expr *
+first_ls_expr ()
+{
+ return pre_ldst_mems;
+}
+
+/* Return the next item in ther list after the specified one. */
+
+static inline struct ls_expr *
+next_ls_expr (ptr)
+ struct ls_expr * ptr;
+{
+ return ptr->next;
+}
+\f
+/* Load Motion for loads which only kill themselves. */
+
+/* Return true if x is a simple MEM operation, with no registers or
+ side effects. These are the types of loads we consider for the
+ ld_motion list, otherwise we let the usual aliasing take care of it. */
+
+static int
+simple_mem (x)
+ rtx x;
+{
+ if (GET_CODE (x) != MEM)
+ return 0;
+
+ if (MEM_VOLATILE_P (x))
+ return 0;
+
+ if (GET_MODE (x) == BLKmode)
+ return 0;
+
+ if (!rtx_varies_p (XEXP (x, 0), 0))
+ return 1;
+
+ return 0;
+}
+
+/* Make sure there isn't a buried reference in this pattern anywhere.
+ If there is, invalidate the entry for it since we're not capable
+ of fixing it up just yet.. We have to be sure we know about ALL
+ loads since the aliasing code will allow all entries in the
+ ld_motion list to not-alias itself. If we miss a load, we will get
+ the wrong value since gcse might common it and we won't know to
+ fix it up. */
+
+static void
+invalidate_any_buried_refs (x)
+ rtx x;
+{
+ const char * fmt;
+ int i,j;
+ struct ls_expr * ptr;
+
+ /* Invalidate it in the list. */
+ if (GET_CODE (x) == MEM && simple_mem (x))
+ {
+ ptr = ldst_entry (x);
+ ptr->invalid = 1;
+ }
+
+ /* Recursively process the insn. */
+ fmt = GET_RTX_FORMAT (GET_CODE (x));
+
+ for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ invalidate_any_buried_refs (XEXP (x, i));
+ else if (fmt[i] == 'E')
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ invalidate_any_buried_refs (XVECEXP (x, i, j));
+ }
+}
+
+/* Find all the 'simple' MEMs which are used in LOADs and STORES. Simple
+ being defined as MEM loads and stores to symbols, with no
+ side effects and no registers in the expression. If there are any
+ uses/defs which don't match this criteria, it is invalidated and
+ trimmed out later. */
+
+static void
+compute_ld_motion_mems ()
+{
+ struct ls_expr * ptr;
+ int bb;
+ rtx insn;
+
+ pre_ldst_mems = NULL;
+
+ for (bb = 0; bb < n_basic_blocks; bb++)
+ {
+ for (insn = BLOCK_HEAD (bb);
+ insn && insn != NEXT_INSN (BLOCK_END (bb));
+ insn = NEXT_INSN (insn))
+ {
+ if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ {
+ if (GET_CODE (PATTERN (insn)) == SET)
+ {
+ rtx src = SET_SRC (PATTERN (insn));
+ rtx dest = SET_DEST (PATTERN (insn));
+
+ /* Check for a simple LOAD... */
+ if (GET_CODE (src) == MEM && simple_mem (src))
+ {
+ ptr = ldst_entry (src);
+ if (GET_CODE (dest) == REG)
+ ptr->loads = alloc_INSN_LIST (insn, ptr->loads);
+ else
+ ptr->invalid = 1;
+ }
+ else
+ {
+ /* 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
+ circumstance that we will ignore the aliasing info. */
+ if (GET_CODE (dest) == MEM && simple_mem (dest))
+ {
+ ptr = ldst_entry (dest);
+
+ if (GET_CODE (src) != MEM
+ && GET_CODE (src) != ASM_OPERANDS)
+ ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
+ else
+ ptr->invalid = 1;
+ }
+ }
+ else
+ invalidate_any_buried_refs (PATTERN (insn));
+ }
+ }
+ }
+}
+
+/* Remove any references that have been either invalidated or are not in the
+ expression list for pre gcse. */
+
+static void
+trim_ld_motion_mems ()
+{
+ struct ls_expr * last = NULL;
+ struct ls_expr * ptr = first_ls_expr ();
+
+ while (ptr != NULL)
+ {
+ int del = ptr->invalid;
+ struct expr * expr = NULL;
+
+ /* Delete if entry has been made invalid. */
+ if (!del)
+ {
+ unsigned int i;
+
+ del = 1;
+ /* Delete if we cannot find this mem in the expression list. */
+ for (i = 0; i < expr_hash_table_size && del; i++)
+ {
+ for (expr = expr_hash_table[i];
+ expr != NULL;
+ expr = expr->next_same_hash)
+ if (expr_equiv_p (expr->expr, ptr->pattern))
+ {
+ del = 0;
+ break;
+ }
+ }
+ }
+
+ if (del)
+ {
+ if (last != NULL)
+ {
+ last->next = ptr->next;
+ free_ldst_entry (ptr);
+ ptr = last->next;
+ }
+ else
+ {
+ pre_ldst_mems = pre_ldst_mems->next;
+ free_ldst_entry (ptr);
+ ptr = pre_ldst_mems;
+ }
+ }
+ else
+ {
+ /* Set the expression field if we are keeping it. */
+ last = ptr;
+ ptr->expr = expr;
+ ptr = ptr->next;
+ }
+ }
+
+ /* Show the world what we've found. */
+ if (gcse_file && pre_ldst_mems != NULL)
+ print_ldst_list (gcse_file);
+}
+
+/* This routine will take an expression which we are replacing with
+ a reaching register, and update any stores that are needed if
+ that expression is in the ld_motion list. Stores are updated by
+ copying their SRC to the reaching register, and then storeing
+ the reaching register into the store location. These keeps the
+ correct value in the reaching register for the loads. */
+
+static void
+update_ld_motion_stores (expr)
+ struct expr * expr;
+{
+ struct ls_expr * mem_ptr;
+
+ if ((mem_ptr = find_rtx_in_ldst (expr->expr)))
+ {
+ /* We can try to find just the REACHED stores, but is shouldn't
+ matter to set the reaching reg everywhere... some might be
+ dead and should be eliminated later. */
+
+ /* We replace SET mem = expr with
+ SET reg = expr
+ SET mem = reg , where reg is the
+ reaching reg used in the load. */
+ rtx list = mem_ptr->stores;
+
+ for ( ; list != NULL_RTX; list = XEXP (list, 1))
+ {
+ rtx insn = XEXP (list, 0);
+ rtx pat = PATTERN (insn);
+ rtx src = SET_SRC (pat);
+ rtx reg = expr->reaching_reg;
+ rtx copy, new;
+
+ /* If we've already copied it, continue. */
+ if (expr->reaching_reg == src)
+ continue;
+
+ if (gcse_file)
+ {
+ fprintf (gcse_file, "PRE: store updated with reaching reg ");
+ print_rtl (gcse_file, expr->reaching_reg);
+ fprintf (gcse_file, ":\n ");
+ print_inline_rtx (gcse_file, insn, 8);
+ fprintf (gcse_file, "\n");
+ }
+
+ copy = gen_move_insn ( reg, SET_SRC (pat));
+ new = emit_insn_before (copy, insn);
+ record_one_set (REGNO (reg), new);
+ SET_SRC (pat) = reg;
+
+ /* un-recognize this pattern since it's probably different now. */
+ INSN_CODE (insn) = -1;
+ gcse_create_count++;
+ }
+ }
+}
+\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. */
+
+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;
+ const char * fmt;
+
+ /* Repeat is used to turn tail-recursion into iteration. */
+ repeat:
+
+ if (x == 0)
+ return 1;
+
+ code = GET_CODE (x);
+ 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);
+ goto repeat;
+
+ case PRE_DEC:
+ case PRE_INC:
+ case POST_DEC:
+ case POST_INC:
+ return 0;
+
+ case PC:
+ case CC0: /*FIXME*/
+ case CONST:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case SYMBOL_REF:
+ case LABEL_REF:
+ case ADDR_VEC:
+ case ADDR_DIFF_VEC:
+ return 1;
+
+ default:
+ break;
+ }
+
+ i = GET_RTX_LENGTH (code) - 1;
+ fmt = GET_RTX_FORMAT (code);
+
+ for (; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ {
+ rtx tem = XEXP (x, i);
+
+ /* If we are about to do the last recursive call
+ needed at this level, change it into iteration.
+ This function is called enough to be worth it. */
+ if (i == 0)
+ {
+ x = tem;
+ goto repeat;
+ }
+
+ if (! store_ops_ok (tem, bb))
+ return 0;
+ }
+ else if (fmt[i] == 'E')
+ {
+ int j;
+
+ for (j = 0; j < XVECLEN (x, i); j++)
+ {
+ 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. */
+
+static void
+find_moveable_store (insn)
+ rtx insn;
+{
+ struct ls_expr * ptr;
+ rtx dest = PATTERN (insn);
+
+ if (GET_CODE (dest) != SET
+ || GET_CODE (SET_SRC (dest)) == ASM_OPERANDS)
+ return;
+
+ dest = SET_DEST (dest);
+
+ 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++)
+ {
+ 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))
+ 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);
+ }
+ }
+
+ 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)
+ rtx x, store_pattern;
+{
+ if (true_dependence (x, GET_MODE (x), store_pattern, rtx_addr_varies_p))
+ return 1;
+ 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)
+ rtx x, store_pattern;
+{
+ const char * fmt;
+ int i,j;
+ int ret = 0;
+
+ if (!x)
+ return 0;
+
+ if (GET_CODE (x) == SET)
+ x = SET_SRC (x);
+
+ if (GET_CODE (x) == MEM)
+ {
+ if (load_kills_store (x, store_pattern))
+ return 1;
+ }
+
+ /* Recursively process the insn. */
+ fmt = GET_RTX_FORMAT (GET_CODE (x));
+
+ for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
+ {
+ if (fmt[i] == 'e')
+ ret |= find_loads (XEXP (x, i), store_pattern);
+ else if (fmt[i] == 'E')
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ ret |= find_loads (XVECEXP (x, i, j), store_pattern);
+ }
+ return ret;
+}
+
+/* Check if INSN kills the store pattern X (is aliased with it).
+ Return 1 if it it does. */
+
+static int
+store_killed_in_insn (x, insn)
+ rtx x, insn;
+{
+ if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
+ return 0;
+
+ if (GET_CODE (insn) == CALL_INSN)
+ {
+ if (CONST_OR_PURE_CALL_P (insn))
+ return 0;
+ else
+ return 1;
+ }
+
+ if (GET_CODE (PATTERN (insn)) == SET)
+ {
+ 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
+ return find_loads (PATTERN (insn), x);
+}
+
+/* Returns 1 if the expression X is loaded or clobbered on or after INSN
+ 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)
+ rtx x, insn;
+ basic_block bb;
+{
+ rtx first = bb->head;
+
+ 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;
+
+ return 0;
+}
+
+#define ANTIC_STORE_LIST(x) ((x)->loads)
+#define AVAIL_STORE_LIST(x) ((x)->stores)
+
+/* Given the table of available store insns at the end of blocks,
+ determine which ones are not killed by aliasing, and generate
+ the appropriate vectors for gen and killed. */
+static void
+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. */
+ ae_gen = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, num_stores);
+ sbitmap_vector_zero (ae_gen, n_basic_blocks);
+
+ st_antloc = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, num_stores);
+ sbitmap_vector_zero (st_antloc, n_basic_blocks);
+
+ 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,
+ or both. */
+ rtx store_list = ptr->stores;
+ ptr->stores = NULL_RTX;
+
+ for (st = store_list; st != NULL; st = XEXP (st, 1))
+ {
+ 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
+ the block), and replace it with this one). We'll copy the
+ old SRC expression to an unused register in case there
+ are any side effects. */
+ if (TEST_BIT (ae_gen[bb->index], ptr->index))
+ {
+ /* Find previous store. */
+ rtx st;
+ for (st = AVAIL_STORE_LIST (ptr); st ; st = XEXP (st, 1))
+ if (BLOCK_FOR_INSN (XEXP (st, 0)) == bb)
+ break;
+ 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;
+ }
+ }
+ SET_BIT (ae_gen[bb->index], ptr->index);
+ AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn,
+ AVAIL_STORE_LIST (ptr));
+ }
+
+ if (!store_killed_before (ptr->pattern, insn, bb))
+ {
+ SET_BIT (st_antloc[BLOCK_NUM (insn)], ptr->index);
+ ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (insn,
+ ANTIC_STORE_LIST (ptr));
+ }
+ }
+
+ /* Free the original list of store insns. */
+ free_INSN_LIST_list (&store_list);
+ }
+
+ 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. */
+
+static void
+insert_insn_start_bb (insn, bb)
+ rtx insn;
+ basic_block bb;
+{
+ /* Insert at start of successor block. */
+ rtx prev = PREV_INSN (bb->head);
+ rtx before = bb->head;
+ while (before != 0)
+ {
+ if (GET_CODE (before) != CODE_LABEL
+ && (GET_CODE (before) != NOTE
+ || NOTE_LINE_NUMBER (before) != NOTE_INSN_BASIC_BLOCK))
+ break;
+ prev = before;
+ if (prev == bb->end)
+ break;
+ before = NEXT_INSN (before);
+ }
+
+ insn = emit_insn_after (insn, prev);
+
+ 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");
+ }
+}
+
+/* This routine will insert a store on an edge. EXPR is the ldst entry for
+ the memory reference, and E is the edge to insert it on. Returns non-zero
+ if an edge insertion was performed. */
+
+static int
+insert_store (expr, e)
+ struct ls_expr * expr;
+ edge e;
+{
+ rtx reg, insn;
+ basic_block bb;
+ edge tmp;
+
+ /* We did all the deleted before this insert, so if we didn't delete a
+ store, then we haven't set the reaching reg yet either. */
+ if (expr->reaching_reg == NULL_RTX)
+ return 0;
+
+ reg = expr->reaching_reg;
+ insn = gen_move_insn (expr->pattern, reg);
+
+ /* If we are inserting this expression on ALL predecessor edges of a BB,
+ insert it at the start of the BB, and reset the insert bits on the other
+ edges so we don't try to insert it on the other edges. */
+ bb = e->dest;
+ for (tmp = e->dest->pred; tmp ; tmp = tmp->pred_next)
+ {
+ int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
+ if (index == EDGE_INDEX_NO_EDGE)
+ abort ();
+ if (! TEST_BIT (pre_insert_map[index], expr->index))
+ break;
+ }
+
+ /* If tmp is NULL, we found an insertion on every edge, blank the
+ insertion vector for these edges, and insert at the start of the BB. */
+ if (!tmp && bb != EXIT_BLOCK_PTR)
+ {
+ for (tmp = e->dest->pred; tmp ; tmp = tmp->pred_next)
+ {
+ int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
+ RESET_BIT (pre_insert_map[index], expr->index);
+ }
+ insert_insn_start_bb (insn, bb);
+ return 0;
+ }
+
+ /* We can't insert on this edge, so we'll insert at the head of the
+ successors block. See Morgan, sec 10.5. */
+ if ((e->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL)
+ {
+ insert_insn_start_bb (insn, bb);
+ return 0;
+ }
+
+ 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;
+}
+
+/* This routine will replace a store with a SET to a specified register. */
+
+static void
+replace_store_insn (reg, del, bb)
+ rtx reg, del;
+ basic_block bb;
+{
+ rtx insn;
+
+ insn = gen_move_insn (reg, SET_SRC (PATTERN (del)));
+ insn = emit_insn_after (insn, del);
+
+ 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");
+ }
+
+ delete_insn (del);
+}
+
+
+/* Delete a store, but copy the value that would have been stored into
+ the reaching_reg for later storing. */
+
+static void
+delete_store (expr, bb)
+ struct ls_expr * expr;
+ basic_block bb;
+{
+ rtx reg, i, del;
+
+ if (expr->reaching_reg == NULL_RTX)
+ expr->reaching_reg = gen_reg_rtx (GET_MODE (expr->pattern));
+
+
+ /* If there is more than 1 store, the earlier ones will be dead,
+ but it doesn't hurt to replace them here. */
+ reg = expr->reaching_reg;
+
+ for (i = AVAIL_STORE_LIST (expr); i; i = XEXP (i, 1))
+ {
+ del = XEXP (i, 0);
+ if (BLOCK_FOR_INSN (del) == bb)
+ {
+ /* We know there is only one since we deleted redundant
+ ones during the available computation. */
+ replace_store_insn (reg, del, bb);
+ break;
+ }
+ }
+}
+
+/* Free memory used by store motion. */
+
+static void
+free_store_memory ()
+{
+ free_ldst_mems ();
+
+ if (ae_gen)
+ sbitmap_vector_free (ae_gen);
+ if (ae_kill)
+ sbitmap_vector_free (ae_kill);
+ if (transp)
+ sbitmap_vector_free (transp);
+ if (st_antloc)
+ sbitmap_vector_free (st_antloc);
+ if (pre_insert_map)
+ 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;
+}
+
+/* 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);
+
+ /* Now we want to insert the new stores which are going to be needed. */
+ for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
+ {
+ for (x = 0; x < n_basic_blocks; x++)
+ if (TEST_BIT (pre_delete_map[x], ptr->index))
+ delete_store (ptr, BASIC_BLOCK (x));
+
+ for (x = 0; x < NUM_EDGES (edge_list); x++)
+ if (TEST_BIT (pre_insert_map[x], ptr->index))
+ update_flow |= insert_store (ptr, INDEX_EDGE (edge_list, x));
+ }
+
+ if (update_flow)
+ commit_edge_insertions ();
+
+ free_store_memory ();
+ free_edge_list (edge_list);
+ remove_fake_edges ();
+ end_alias_analysis ();
+}