[PATCH][RFA] Split store_motion pass from gcse.c into new file store-motion.c
Richard Guenther
richard.guenther@gmail.com
Thu Apr 30 09:00:00 GMT 2009
On Thu, Apr 30, 2009 at 12:46 AM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> Hi,
>
> $SUBJECT says all, really. The store motion pass in gcse.c is pretty
> much independent of all the other passes, so this patch is basically
> ~1500 lines of copy-and-paste, to split the (huge) gcse.c into more
> manageable bits.
>
> Bootstrapped&tested on {ia64,x86_64}-unknown-linux-gnu.
> OK for trunk?
This is ok.
Thanks,
Richard.
> Ciao!
> Steven
>
>
>
> * gcse.c (ae_gen): Remove.
> (can_assign_to_reg_p): Rename to can_assign_to_reg_without_clobbers_p
> and make non-static function to make it available in store-motion.c.
> Update call sites with search-and-replace.
> (enumerate_ldsts, reg_set_info, reg_clear_last_set, store_ops_ok,
> extract_mentioned_regs, extract_mentioned_regs_helper,
> find_moveable_store, compute_store_table, load_kills_store, find_loads,
> store_killed_in_insn, store_killed_after, store_killed_before,
> build_store_vectors, insert_insn_start_basic_block, insert-store,
> remove_reachable_equiv_notes, replace_store_insn, delete_store,
> free_store_memory, one_store_motion_pass, gate_rtl_store_motion,
> execute_rtl_store_motion, pass_rtl_store_motion): Move to...
> * store-motion.c: ...new file. Also copy data structures from gcse.c
> and clean up to remove parts not used by store motion.
> * rtl.h (can_assign_to_reg_without_clobbers_p): Add prototype.
> * Makefile.in (store-motion.o): New rule. Add to OBJS-common.
>
> Index: gcse.c
> ===================================================================
> --- gcse.c (revision 146989)
> +++ gcse.c (working copy)
> @@ -437,7 +437,7 @@ static int global_const_prop_count;
> static int global_copy_prop_count;
>
> /* For available exprs */
> -static sbitmap *ae_kill, *ae_gen;
> +static sbitmap *ae_kill;
>
> static void compute_can_copy (void);
> static void *gmalloc (size_t) ATTRIBUTE_MALLOC;
> @@ -450,7 +450,6 @@ static void hash_scan_set (rtx, rtx, str
> static void hash_scan_clobber (rtx, rtx, struct hash_table *);
> static void hash_scan_call (rtx, rtx, struct hash_table *);
> static int want_to_gcse_p (rtx);
> -static bool can_assign_to_reg_p (rtx);
> static bool gcse_constant_p (const_rtx);
> static int oprs_unchanged_p (const_rtx, const_rtx, int);
> static int oprs_anticipatable_p (const_rtx, const_rtx);
> @@ -527,7 +526,6 @@ static void free_ldst_entry (struct ls_e
> static void free_ldst_mems (void);
> static void print_ldst_list (FILE *);
> static struct ls_expr * find_rtx_in_ldst (rtx);
> -static int enumerate_ldsts (void);
> static inline struct ls_expr * first_ls_expr (void);
> static inline struct ls_expr * next_ls_expr (struct ls_expr *);
> static int simple_mem (const_rtx);
> @@ -535,26 +533,6 @@ static void invalidate_any_buried_refs (
> static void compute_ld_motion_mems (void);
> static void trim_ld_motion_mems (void);
> static void update_ld_motion_stores (struct expr *);
> -static void reg_set_info (rtx, const_rtx, void *);
> -static void reg_clear_last_set (rtx, const_rtx, void *);
> -static bool store_ops_ok (const_rtx, int *);
> -static rtx extract_mentioned_regs (rtx);
> -static rtx extract_mentioned_regs_helper (rtx, rtx);
> -static void find_moveable_store (rtx, int *, int *);
> -static int compute_store_table (void);
> -static bool load_kills_store (const_rtx, const_rtx, int);
> -static bool find_loads (const_rtx, const_rtx, int);
> -static bool store_killed_in_insn (const_rtx, const_rtx, const_rtx, int);
> -static bool store_killed_after (const_rtx, const_rtx, const_rtx,
> const_basic_block, int *, rtx *);
> -static bool store_killed_before (const_rtx, const_rtx, const_rtx,
> const_basic_block, int *);
> -static void build_store_vectors (void);
> -static void insert_insn_start_basic_block (rtx, basic_block);
> -static int insert_store (struct ls_expr *, edge);
> -static void remove_reachable_equiv_notes (basic_block, struct ls_expr *);
> -static void replace_store_insn (rtx, rtx, basic_block, struct ls_expr *);
> -static void delete_store (struct ls_expr *, basic_block);
> -static void free_store_memory (void);
> -static int one_store_motion_pass (void);
> static void free_insn_expr_list_list (rtx *);
> static void clear_modify_mem_tables (void);
> static void free_modify_mem_tables (void);
> @@ -816,18 +794,23 @@ want_to_gcse_p (rtx x)
> return 0;
>
> default:
> - return can_assign_to_reg_p (x);
> + return can_assign_to_reg_without_clobbers_p (x);
> }
> }
>
> -/* Used internally by can_assign_to_reg_p. */
> +/* Used internally by can_assign_to_reg_without_clobbers_p. */
>
> static GTY(()) rtx test_insn;
>
> -/* Return true if we can assign X to a pseudo register. */
> +/* Return true if we can assign X to a pseudo register such that the
> + resulting insn does not result in clobbering a hard register as a
> + side-effect.
> + This function is typically used by code motion passes, to verify
> + that it is safe to insert an insn without worrying about clobbering
> + maybe live hard regs. */
>
> -static bool
> -can_assign_to_reg_p (rtx x)
> +bool
> +can_assign_to_reg_without_clobbers_p (rtx x)
> {
> int num_clobbers = 0;
> int icode;
> @@ -4640,20 +4623,6 @@ find_rtx_in_ldst (rtx x)
> return (struct ls_expr *) *slot;
> }
>
> -/* Assign each element of the list of mems a monotonically increasing
> value. */
> -
> -static int
> -enumerate_ldsts (void)
> -{
> - 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 *
> @@ -4799,7 +4768,7 @@ compute_ld_motion_mems (void)
> && GET_CODE (src) != ASM_OPERANDS
> /* Check for REG manually since want_to_gcse_p
> returns 0 for all REGs. */
> - && can_assign_to_reg_p (src))
> + && can_assign_to_reg_without_clobbers_p (src))
> ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
> else
> ptr->invalid = 1;
> @@ -4918,1318 +4887,216 @@ update_ld_motion_stores (struct expr * e
> }
> }
>
> -/* Store motion code. */
> -
> -#define ANTIC_STORE_LIST(x) ((x)->loads)
> -#define AVAIL_STORE_LIST(x) ((x)->stores)
> -#define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
> -
> -/* 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 int * regvec;
> +/* Return true if the graph is too expensive to optimize. PASS is the
> + optimization about to be performed. */
>
> -/* And current insn, for the same routine. */
> -static rtx compute_store_table_current_insn;
> +static bool
> +is_too_expensive (const char *pass)
> +{
> + /* Trying to perform global optimizations on flow graphs which have
> + a high connectivity will take a long time and is unlikely to be
> + particularly useful.
>
> -/* Used in computing the reverse edge graph bit vectors. */
> -static sbitmap * st_antloc;
> + In normal circumstances a cfg should have about twice as many
> + edges as blocks. But we do not want to punish small functions
> + which have a couple switch statements. Rather than simply
> + threshold the number of blocks, uses something with a more
> + graceful degradation. */
> + if (n_edges > 20000 + n_basic_blocks * 4)
> + {
> + warning (OPT_Wdisabled_optimization,
> + "%s: %d basic blocks and %d edges/basic block",
> + pass, n_basic_blocks, n_edges / n_basic_blocks);
>
> -/* Global holding the number of store expressions we are dealing with. */
> -static int num_stores;
> + return true;
> + }
>
> -/* Checks to set if we need to mark a register set. Called from
> - note_stores. */
> + /* If allocating memory for the cprop bitmap would take up too much
> + storage it's better just to disable the optimization. */
> + if ((n_basic_blocks
> + * SBITMAP_SET_SIZE (max_reg_num ())
> + * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
> + {
> + warning (OPT_Wdisabled_optimization,
> + "%s: %d basic blocks and %d registers",
> + pass, n_basic_blocks, max_reg_num ());
>
> -static void
> -reg_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
> - void *data ATTRIBUTE_UNUSED)
> -{
> - if (GET_CODE (dest) == SUBREG)
> - dest = SUBREG_REG (dest);
> + return true;
> + }
>
> - if (REG_P (dest))
> - regvec[REGNO (dest)] = INSN_UID (compute_store_table_current_insn);
> + return false;
> }
>
> -/* Clear any mark that says that this insn sets dest. Called from
> - note_stores. */
> +
> +/* Main function for the CPROP pass. */
>
> -static void
> -reg_clear_last_set (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
> - void *data)
> +static int
> +one_cprop_pass (void)
> {
> - int *dead_vec = (int *) data;
> + int changed = 0;
>
> - if (GET_CODE (dest) == SUBREG)
> - dest = SUBREG_REG (dest);
> + /* Return if there's nothing to do, or it is too expensive. */
> + if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
> + || is_too_expensive (_ ("const/copy propagation disabled")))
> + return 0;
>
> - if (REG_P (dest) &&
> - dead_vec[REGNO (dest)] == INSN_UID (compute_store_table_current_insn))
> - dead_vec[REGNO (dest)] = 0;
> -}
> + global_const_prop_count = local_const_prop_count = 0;
> + global_copy_prop_count = local_copy_prop_count = 0;
>
> -/* Return zero if some of the registers in list X are killed
> - due to set of registers in bitmap REGS_SET. */
> + bytes_used = 0;
> + gcc_obstack_init (&gcse_obstack);
> + alloc_gcse_mem ();
>
> -static bool
> -store_ops_ok (const_rtx x, int *regs_set)
> -{
> - const_rtx reg;
> + /* Do a local const/copy propagation pass first. The global pass
> + only handles global opportunities.
> + If the local pass changes something, remove any unreachable blocks
> + because the CPROP global dataflow analysis may get into infinite
> + loops for CFGs with unreachable blocks.
>
> - for (; x; x = XEXP (x, 1))
> + FIXME: This local pass should not be necessary after CSE (but for
> + some reason it still is). It is also (proven) not necessary
> + to run the local pass right after FWPWOP.
> +
> + FIXME: The global analysis would not get into infinite loops if it
> + would use the DF solver (via df_simple_dataflow) instead of
> + the solver implemented in this file. */
> + if (local_cprop_pass ())
> {
> - reg = XEXP (x, 0);
> - if (regs_set[REGNO(reg)])
> - return false;
> + delete_unreachable_blocks ();
> + df_analyze ();
> }
>
> - return true;
> -}
> -
> -/* Returns a list of registers mentioned in X. */
> -static rtx
> -extract_mentioned_regs (rtx x)
> -{
> - return extract_mentioned_regs_helper (x, NULL_RTX);
> -}
> -
> -/* Helper for extract_mentioned_regs; ACCUM is used to accumulate used
> - registers. */
> -static rtx
> -extract_mentioned_regs_helper (rtx x, rtx accum)
> -{
> - int i;
> - enum rtx_code code;
> - const char * fmt;
> + /* Determine implicit sets. */
> + implicit_sets = XCNEWVEC (rtx, last_basic_block);
> + find_implicit_sets ();
>
> - /* Repeat is used to turn tail-recursion into iteration. */
> - repeat:
> + alloc_hash_table (get_max_uid (), &set_hash_table, 1);
> + compute_hash_table (&set_hash_table);
>
> - if (x == 0)
> - return accum;
> + /* Free implicit_sets before peak usage. */
> + free (implicit_sets);
> + implicit_sets = NULL;
>
> - code = GET_CODE (x);
> - switch (code)
> + if (dump_file)
> + dump_hash_table (dump_file, "SET", &set_hash_table);
> + if (set_hash_table.n_elems > 0)
> {
> - case REG:
> - return alloc_EXPR_LIST (0, x, accum);
> -
> - case MEM:
> - x = XEXP (x, 0);
> - goto repeat;
> -
> - case PRE_DEC:
> - case PRE_INC:
> - case PRE_MODIFY:
> - case POST_DEC:
> - case POST_INC:
> - case POST_MODIFY:
> - /* We do not run this function with arguments having side effects. */
> - gcc_unreachable ();
> -
> - case PC:
> - case CC0: /*FIXME*/
> - case CONST:
> - case CONST_INT:
> - case CONST_DOUBLE:
> - case CONST_FIXED:
> - case CONST_VECTOR:
> - case SYMBOL_REF:
> - case LABEL_REF:
> - case ADDR_VEC:
> - case ADDR_DIFF_VEC:
> - return accum;
> -
> - default:
> - break;
> - }
> + basic_block bb;
> + rtx insn;
>
> - i = GET_RTX_LENGTH (code) - 1;
> - fmt = GET_RTX_FORMAT (code);
> + alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
> + compute_cprop_data ();
>
> - for (; i >= 0; i--)
> - {
> - if (fmt[i] == 'e')
> + FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb,
> EXIT_BLOCK_PTR, next_bb)
> {
> - rtx tem = XEXP (x, i);
> + /* Reset tables used to keep track of what's still valid [since
> + the start of the block]. */
> + reset_opr_set_tables ();
>
> - /* If we are about to do the last recursive call
> - needed at this level, change it into iteration. */
> - if (i == 0)
> - {
> - x = tem;
> - goto repeat;
> - }
> + FOR_BB_INSNS (bb, insn)
> + if (INSN_P (insn))
> + {
> + changed |= cprop_insn (insn);
>
> - accum = extract_mentioned_regs_helper (tem, accum);
> + /* Keep track of everything modified by this insn. */
> + /* ??? Need to be careful w.r.t. mods done to INSN.
> + Don't call mark_oprs_set if we turned the
> + insn into a NOTE. */
> + if (! NOTE_P (insn))
> + mark_oprs_set (insn);
> + }
> }
> - else if (fmt[i] == 'E')
> - {
> - int j;
>
> - for (j = 0; j < XVECLEN (x, i); j++)
> - accum = extract_mentioned_regs_helper (XVECEXP (x, i, j), accum);
> - }
> + changed |= bypass_conditional_jumps ();
> + free_cprop_mem ();
> }
>
> - return accum;
> -}
> + free_hash_table (&set_hash_table);
> + free_gcse_mem ();
> + obstack_free (&gcse_obstack, NULL);
>
> -/* Determine whether INSN is MEM store pattern that we will consider moving.
> - REGS_SET_BEFORE is bitmap of registers set before (and including) the
> - current insn, REGS_SET_AFTER is bitmap of registers set after (and
> - including) the insn in this basic block. We must be passing through BB from
> - head to end, as we are using this fact to speed things up.
> + if (dump_file)
> + {
> + fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ",
> + current_function_name (), n_basic_blocks, bytes_used);
> + fprintf (dump_file, "%d local const props, %d local copy props, ",
> + local_const_prop_count, local_copy_prop_count);
> + fprintf (dump_file, "%d global const props, %d global copy props\n\n",
> + global_const_prop_count, global_copy_prop_count);
> + }
>
> - The results are stored this way:
> + return changed;
> +}
>
> - -- the first anticipatable expression is added into ANTIC_STORE_LIST
> - -- if the processed expression is not anticipatable, NULL_RTX is added
> - there instead, so that we can use it as indicator that no further
> - expression of this type may be anticipatable
> - -- if the expression is available, it is added as head of AVAIL_STORE_LIST;
> - consequently, all of them but this head are dead and may be deleted.
> - -- if the expression is not available, the insn due to that it fails to be
> - available is stored in reaching_reg.
> +
> +/* All the passes implemented in this file. Each pass has its
> + own gate and execute function, and at the end of the file a
> + pass definition for passes.c.
>
> - The things are complicated a bit by fact that there already may be stores
> - to the same MEM from other blocks; also caller must take care of the
> - necessary cleanup of the temporary markers after end of the basic block.
> - */
> + We do not construct an accurate cfg in functions which call
> + setjmp, so none of these passes runs if the function calls
> + setjmp.
> + FIXME: Should just handle setjmp via REG_SETJMP notes. */
>
> -static void
> -find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after)
> +static bool
> +gate_rtl_cprop (void)
> {
> - struct ls_expr * ptr;
> - rtx dest, set, tmp;
> - int check_anticipatable, check_available;
> - basic_block bb = BLOCK_FOR_INSN (insn);
> + return optimize > 0 && flag_gcse
> + && !cfun->calls_setjmp
> + && dbg_cnt (cprop);
> +}
>
> - set = single_set (insn);
> - if (!set)
> - return;
> +static unsigned int
> +execute_rtl_cprop (void)
> +{
> + delete_unreachable_blocks ();
> + df_note_add_problem ();
> + df_set_flags (DF_LR_RUN_DCE);
> + df_analyze ();
> + flag_rerun_cse_after_global_opts |= one_cprop_pass ();
> + return 0;
> +}
>
> - dest = SET_DEST (set);
> +static bool
> +gate_rtl_pre (void)
> +{
> + return optimize > 0 && flag_gcse
> + && !cfun->calls_setjmp
> + && optimize_function_for_speed_p (cfun)
> + && dbg_cnt (pre);
> +}
>
> - if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
> - || GET_MODE (dest) == BLKmode)
> - return;
> +static unsigned int
> +execute_rtl_pre (void)
> +{
> + delete_unreachable_blocks ();
> + df_note_add_problem ();
> + df_analyze ();
> + flag_rerun_cse_after_global_opts |= one_pre_gcse_pass ();
> + return 0;
> +}
>
> - if (side_effects_p (dest))
> - return;
> +static bool
> +gate_rtl_hoist (void)
> +{
> + return optimize > 0 && flag_gcse
> + && !cfun->calls_setjmp
> + /* It does not make sense to run code hoisting unless we are optimizing
> + for code size -- it rarely makes programs faster, and can make then
> + bigger if we did PRE (when optimizing for space, we don't run PRE). */
> + && optimize_function_for_size_p (cfun)
> + && dbg_cnt (hoist);
> +}
>
> - /* If we are handling exceptions, we must be careful with memory references
> - that may trap. If we are not, the behavior is undefined, so we may just
> - continue. */
> - if (flag_non_call_exceptions && may_trap_p (dest))
> - return;
> -
> - /* Even if the destination cannot trap, the source may. In this case we'd
> - need to handle updating the REG_EH_REGION note. */
> - if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
> - return;
> -
> - /* Make sure that the SET_SRC of this store insns can be assigned to
> - a register, or we will fail later on in replace_store_insn, which
> - assumes that we can do this. But sometimes the target machine has
> - oddities like MEM read-modify-write instruction. See for example
> - PR24257. */
> - if (!can_assign_to_reg_p (SET_SRC (set)))
> - return;
> -
> - ptr = ldst_entry (dest);
> - if (!ptr->pattern_regs)
> - ptr->pattern_regs = extract_mentioned_regs (dest);
> -
> - /* Do not check for anticipatability if we either found one anticipatable
> - store already, or tested for one and found out that it was killed. */
> - check_anticipatable = 0;
> - if (!ANTIC_STORE_LIST (ptr))
> - check_anticipatable = 1;
> - else
> - {
> - tmp = XEXP (ANTIC_STORE_LIST (ptr), 0);
> - if (tmp != NULL_RTX
> - && BLOCK_FOR_INSN (tmp) != bb)
> - check_anticipatable = 1;
> - }
> - if (check_anticipatable)
> - {
> - if (store_killed_before (dest, ptr->pattern_regs, insn, bb,
> regs_set_before))
> - tmp = NULL_RTX;
> - else
> - tmp = insn;
> - ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (tmp,
> - ANTIC_STORE_LIST (ptr));
> - }
> -
> - /* It is not necessary to check whether store is available if we did
> - it successfully before; if we failed before, do not bother to check
> - until we reach the insn that caused us to fail. */
> - check_available = 0;
> - if (!AVAIL_STORE_LIST (ptr))
> - check_available = 1;
> - else
> - {
> - tmp = XEXP (AVAIL_STORE_LIST (ptr), 0);
> - if (BLOCK_FOR_INSN (tmp) != bb)
> - check_available = 1;
> - }
> - if (check_available)
> - {
> - /* Check that we have already reached the insn at that the check
> - failed last time. */
> - if (LAST_AVAIL_CHECK_FAILURE (ptr))
> - {
> - for (tmp = BB_END (bb);
> - tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
> - tmp = PREV_INSN (tmp))
> - continue;
> - if (tmp == insn)
> - check_available = 0;
> - }
> - else
> - check_available = store_killed_after (dest, ptr->pattern_regs, insn,
> - bb, regs_set_after,
> - &LAST_AVAIL_CHECK_FAILURE (ptr));
> - }
> - if (!check_available)
> - AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn, AVAIL_STORE_LIST (ptr));
> -}
> -
> -/* Find available and anticipatable stores. */
> -
> -static int
> -compute_store_table (void)
> -{
> - int ret;
> - basic_block bb;
> - unsigned regno;
> - rtx insn, pat, tmp;
> - int *last_set_in, *already_set;
> - struct ls_expr * ptr, **prev_next_ptr_ptr;
> - unsigned int max_gcse_regno = max_reg_num ();
> -
> - pre_ldst_mems = 0;
> - pre_ldst_table = htab_create (13, pre_ldst_expr_hash,
> - pre_ldst_expr_eq, NULL);
> - last_set_in = XCNEWVEC (int, max_gcse_regno);
> - already_set = XNEWVEC (int, max_gcse_regno);
> -
> - /* Find all the stores we care about. */
> - FOR_EACH_BB (bb)
> - {
> - /* First compute the registers set in this block. */
> - regvec = last_set_in;
> -
> - FOR_BB_INSNS (bb, insn)
> - {
> - if (! INSN_P (insn))
> - continue;
> -
> - if (CALL_P (insn))
> - {
> - for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
> - if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
> - last_set_in[regno] = INSN_UID (insn);
> - }
> -
> - pat = PATTERN (insn);
> - compute_store_table_current_insn = insn;
> - note_stores (pat, reg_set_info, NULL);
> - }
> -
> - /* Now find the stores. */
> - memset (already_set, 0, sizeof (int) * max_gcse_regno);
> - regvec = already_set;
> - FOR_BB_INSNS (bb, insn)
> - {
> - if (! INSN_P (insn))
> - continue;
> -
> - if (CALL_P (insn))
> - {
> - for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
> - if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
> - already_set[regno] = 1;
> - }
> -
> - pat = PATTERN (insn);
> - note_stores (pat, reg_set_info, NULL);
> -
> - /* Now that we've marked regs, look for stores. */
> - find_moveable_store (insn, already_set, last_set_in);
> -
> - /* Unmark regs that are no longer set. */
> - compute_store_table_current_insn = insn;
> - note_stores (pat, reg_clear_last_set, last_set_in);
> - if (CALL_P (insn))
> - {
> - for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
> - if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)
> - && last_set_in[regno] == INSN_UID (insn))
> - last_set_in[regno] = 0;
> - }
> - }
> -
> -#ifdef ENABLE_CHECKING
> - /* last_set_in should now be all-zero. */
> - for (regno = 0; regno < max_gcse_regno; regno++)
> - gcc_assert (!last_set_in[regno]);
> -#endif
> -
> - /* Clear temporary marks. */
> - for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
> - {
> - LAST_AVAIL_CHECK_FAILURE(ptr) = NULL_RTX;
> - if (ANTIC_STORE_LIST (ptr)
> - && (tmp = XEXP (ANTIC_STORE_LIST (ptr), 0)) == NULL_RTX)
> - ANTIC_STORE_LIST (ptr) = XEXP (ANTIC_STORE_LIST (ptr), 1);
> - }
> - }
> -
> - /* Remove the stores that are not available anywhere, as there will
> - be no opportunity to optimize them. */
> - for (ptr = pre_ldst_mems, prev_next_ptr_ptr = &pre_ldst_mems;
> - ptr != NULL;
> - ptr = *prev_next_ptr_ptr)
> - {
> - if (!AVAIL_STORE_LIST (ptr))
> - {
> - *prev_next_ptr_ptr = ptr->next;
> - htab_remove_elt_with_hash (pre_ldst_table, ptr, ptr->hash_index);
> - free_ldst_entry (ptr);
> - }
> - else
> - prev_next_ptr_ptr = &ptr->next;
> - }
> -
> - ret = enumerate_ldsts ();
> -
> - if (dump_file)
> - {
> - fprintf (dump_file, "ST_avail and ST_antic (shown under loads..)\n");
> - print_ldst_list (dump_file);
> - }
> -
> - free (last_set_in);
> - free (already_set);
> - return ret;
> -}
> -
> -/* Check to see if the load X is aliased with STORE_PATTERN.
> - AFTER is true if we are checking the case when STORE_PATTERN occurs
> - after the X. */
> -
> -static bool
> -load_kills_store (const_rtx x, const_rtx store_pattern, int after)
> -{
> - if (after)
> - return anti_dependence (x, store_pattern);
> - else
> - return true_dependence (store_pattern, GET_MODE (store_pattern), x,
> - rtx_addr_varies_p);
> -}
> -
> -/* Go through the entire insn X, looking for any loads which might alias
> - STORE_PATTERN. Return true if found.
> - AFTER is true if we are checking the case when STORE_PATTERN occurs
> - after the insn X. */
> -
> -static bool
> -find_loads (const_rtx x, const_rtx store_pattern, int after)
> -{
> - const char * fmt;
> - int i, j;
> - int ret = false;
> -
> - if (!x)
> - return false;
> -
> - if (GET_CODE (x) == SET)
> - x = SET_SRC (x);
> -
> - if (MEM_P (x))
> - {
> - if (load_kills_store (x, store_pattern, after))
> - return true;
> - }
> -
> - /* 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, after);
> - else if (fmt[i] == 'E')
> - for (j = XVECLEN (x, i) - 1; j >= 0; j--)
> - ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
> - }
> - return ret;
> -}
> -
> -static inline bool
> -store_killed_in_pat (const_rtx x, const_rtx pat, int after)
> -{
> - if (GET_CODE (pat) == SET)
> - {
> - rtx dest = SET_DEST (pat);
> -
> - if (GET_CODE (dest) == ZERO_EXTRACT)
> - dest = XEXP (dest, 0);
> -
> - /* Check for memory stores to aliased objects. */
> - if (MEM_P (dest)
> - && !expr_equiv_p (dest, x))
> - {
> - if (after)
> - {
> - if (output_dependence (dest, x))
> - return true;
> - }
> - else
> - {
> - if (output_dependence (x, dest))
> - return true;
> - }
> - }
> - }
> -
> - if (find_loads (pat, x, after))
> - return true;
> -
> - return false;
> -}
> -
> -/* Check if INSN kills the store pattern X (is aliased with it).
> - AFTER is true if we are checking the case when store X occurs
> - after the insn. Return true if it does. */
> -
> -static bool
> -store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after)
> -{
> - const_rtx reg, base, note, pat;
> -
> - if (!INSN_P (insn))
> - return false;
> -
> - if (CALL_P (insn))
> - {
> - /* A normal or pure call might read from pattern,
> - but a const call will not. */
> - if (!RTL_CONST_CALL_P (insn))
> - return true;
> -
> - /* But even a const call reads its parameters. Check whether the
> - base of some of registers used in mem is stack pointer. */
> - for (reg = x_regs; reg; reg = XEXP (reg, 1))
> - {
> - base = find_base_term (XEXP (reg, 0));
> - if (!base
> - || (GET_CODE (base) == ADDRESS
> - && GET_MODE (base) == Pmode
> - && XEXP (base, 0) == stack_pointer_rtx))
> - return true;
> - }
> -
> - return false;
> - }
> -
> - pat = PATTERN (insn);
> - if (GET_CODE (pat) == SET)
> - {
> - if (store_killed_in_pat (x, pat, after))
> - return true;
> - }
> - else if (GET_CODE (pat) == PARALLEL)
> - {
> - int i;
> -
> - for (i = 0; i < XVECLEN (pat, 0); i++)
> - if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
> - return true;
> - }
> - else if (find_loads (PATTERN (insn), x, after))
> - return true;
> -
> - /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
> - location aliased with X, then this insn kills X. */
> - note = find_reg_equal_equiv_note (insn);
> - if (! note)
> - return false;
> - note = XEXP (note, 0);
> -
> - /* However, if the note represents a must alias rather than a may
> - alias relationship, then it does not kill X. */
> - if (expr_equiv_p (note, x))
> - return false;
> -
> - /* See if there are any aliased loads in the note. */
> - return find_loads (note, x, after);
> -}
> -
> -/* Returns true if the expression X is loaded or clobbered on or after INSN
> - within basic block BB. REGS_SET_AFTER is bitmap of registers set in
> - or after the insn. X_REGS is list of registers mentioned in X. If the store
> - is killed, return the last insn in that it occurs in FAIL_INSN. */
> -
> -static bool
> -store_killed_after (const_rtx x, const_rtx x_regs, const_rtx insn,
> const_basic_block bb,
> - int *regs_set_after, rtx *fail_insn)
> -{
> - rtx last = BB_END (bb), act;
> -
> - if (!store_ops_ok (x_regs, regs_set_after))
> - {
> - /* We do not know where it will happen. */
> - if (fail_insn)
> - *fail_insn = NULL_RTX;
> - return true;
> - }
> -
> - /* Scan from the end, so that fail_insn is determined correctly. */
> - for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
> - if (store_killed_in_insn (x, x_regs, act, false))
> - {
> - if (fail_insn)
> - *fail_insn = act;
> - return true;
> - }
> -
> - return false;
> -}
> -
> -/* Returns true if the expression X is loaded or clobbered on or before INSN
> - within basic block BB. X_REGS is list of registers mentioned in X.
> - REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
> -static bool
> -store_killed_before (const_rtx x, const_rtx x_regs, const_rtx insn,
> const_basic_block bb,
> - int *regs_set_before)
> -{
> - rtx first = BB_HEAD (bb);
> -
> - if (!store_ops_ok (x_regs, regs_set_before))
> - return true;
> -
> - for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
> - if (store_killed_in_insn (x, x_regs, insn, true))
> - return true;
> -
> - return false;
> -}
> -
> -/* Fill in available, anticipatable, transparent and kill vectors in
> - STORE_DATA, based on lists of available and anticipatable stores. */
> -static void
> -build_store_vectors (void)
> -{
> - basic_block bb;
> - int *regs_set_in_block;
> - rtx insn, st;
> - struct ls_expr * ptr;
> - unsigned int max_gcse_regno = max_reg_num ();
> -
> - /* Build the gen_vector. This is any store in the table which is not killed
> - by aliasing later in its block. */
> - ae_gen = sbitmap_vector_alloc (last_basic_block, num_stores);
> - sbitmap_vector_zero (ae_gen, last_basic_block);
> -
> - st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores);
> - sbitmap_vector_zero (st_antloc, last_basic_block);
> -
> - for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
> - {
> - for (st = AVAIL_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
> - {
> - insn = XEXP (st, 0);
> - bb = BLOCK_FOR_INSN (insn);
> -
> - /* If we've already seen an available expression in this block,
> - we can delete this one (It occurs earlier in the block). We'll
> - copy the SRC expression to an unused register in case there
> - are any side effects. */
> - if (TEST_BIT (ae_gen[bb->index], ptr->index))
> - {
> - rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
> - if (dump_file)
> - fprintf (dump_file, "Removing redundant store:\n");
> - replace_store_insn (r, XEXP (st, 0), bb, ptr);
> - continue;
> - }
> - SET_BIT (ae_gen[bb->index], ptr->index);
> - }
> -
> - for (st = ANTIC_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
> - {
> - insn = XEXP (st, 0);
> - bb = BLOCK_FOR_INSN (insn);
> - SET_BIT (st_antloc[bb->index], ptr->index);
> - }
> - }
> -
> - ae_kill = sbitmap_vector_alloc (last_basic_block, num_stores);
> - sbitmap_vector_zero (ae_kill, last_basic_block);
> -
> - transp = sbitmap_vector_alloc (last_basic_block, num_stores);
> - sbitmap_vector_zero (transp, last_basic_block);
> - regs_set_in_block = XNEWVEC (int, max_gcse_regno);
> -
> - FOR_EACH_BB (bb)
> - {
> - FOR_BB_INSNS (bb, insn)
> - if (INSN_P (insn))
> - {
> - df_ref *def_rec;
> - for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
> - {
> - unsigned int ref_regno = DF_REF_REGNO (*def_rec);
> - if (ref_regno < max_gcse_regno)
> - regs_set_in_block[DF_REF_REGNO (*def_rec)] = 1;
> - }
> - }
> -
> - for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
> - {
> - if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
> - bb, regs_set_in_block, NULL))
> - {
> - /* It should not be necessary to consider the expression
> - killed if it is both anticipatable and available. */
> - if (!TEST_BIT (st_antloc[bb->index], ptr->index)
> - || !TEST_BIT (ae_gen[bb->index], ptr->index))
> - SET_BIT (ae_kill[bb->index], ptr->index);
> - }
> - else
> - SET_BIT (transp[bb->index], ptr->index);
> - }
> - }
> -
> - free (regs_set_in_block);
> -
> - if (dump_file)
> - {
> - dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc,
> last_basic_block);
> - dump_sbitmap_vector (dump_file, "st_kill", "", ae_kill,
> last_basic_block);
> - dump_sbitmap_vector (dump_file, "Transpt", "", transp, last_basic_block);
> - dump_sbitmap_vector (dump_file, "st_avloc", "", ae_gen,
> last_basic_block);
> - }
> -}
> -
> -/* Insert an instruction at the beginning of a basic block, and update
> - the BB_HEAD if needed. */
> -
> -static void
> -insert_insn_start_basic_block (rtx insn, basic_block bb)
> -{
> - /* Insert at start of successor block. */
> - rtx prev = PREV_INSN (BB_HEAD (bb));
> - rtx before = BB_HEAD (bb);
> - while (before != 0)
> - {
> - if (! LABEL_P (before)
> - && !NOTE_INSN_BASIC_BLOCK_P (before))
> - break;
> - prev = before;
> - if (prev == BB_END (bb))
> - break;
> - before = NEXT_INSN (before);
> - }
> -
> - insn = emit_insn_after_noloc (insn, prev, bb);
> -
> - if (dump_file)
> - {
> - fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n",
> - bb->index);
> - print_inline_rtx (dump_file, insn, 6);
> - fprintf (dump_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 nonzero
> - if an edge insertion was performed. */
> -
> -static int
> -insert_store (struct ls_expr * expr, edge e)
> -{
> - rtx reg, insn;
> - basic_block bb;
> - edge tmp;
> - edge_iterator ei;
> -
> - /* 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;
> -
> - if (e->flags & EDGE_FAKE)
> - return 0;
> -
> - reg = expr->reaching_reg;
> - insn = gen_move_insn (copy_rtx (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_EACH_EDGE (tmp, ei, e->dest->preds)
> - if (!(tmp->flags & EDGE_FAKE))
> - {
> - int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
> -
> - gcc_assert (index != EDGE_INDEX_NO_EDGE);
> - 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_EACH_EDGE (tmp, ei, e->dest->preds)
> - {
> - int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
> - RESET_BIT (pre_insert_map[index], expr->index);
> - }
> - insert_insn_start_basic_block (insn, bb);
> - return 0;
> - }
> -
> - /* We can't put stores in the front of blocks pointed to by abnormal
> - edges since that may put a store where one didn't used to be. */
> - gcc_assert (!(e->flags & EDGE_ABNORMAL));
> -
> - insert_insn_on_edge (insn, e);
> -
> - if (dump_file)
> - {
> - fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
> - e->src->index, e->dest->index);
> - print_inline_rtx (dump_file, insn, 6);
> - fprintf (dump_file, "\n");
> - }
> -
> - return 1;
> -}
> -
> -/* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
> - memory location in SMEXPR set in basic block BB.
> -
> - This could be rather expensive. */
> -
> -static void
> -remove_reachable_equiv_notes (basic_block bb, struct ls_expr *smexpr)
> -{
> - edge_iterator *stack, ei;
> - int sp;
> - edge act;
> - sbitmap visited = sbitmap_alloc (last_basic_block);
> - rtx last, insn, note;
> - rtx mem = smexpr->pattern;
> -
> - stack = XNEWVEC (edge_iterator, n_basic_blocks);
> - sp = 0;
> - ei = ei_start (bb->succs);
> -
> - sbitmap_zero (visited);
> -
> - act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container
> (ei), 0) : NULL);
> - while (1)
> - {
> - if (!act)
> - {
> - if (!sp)
> - {
> - free (stack);
> - sbitmap_free (visited);
> - return;
> - }
> - act = ei_edge (stack[--sp]);
> - }
> - bb = act->dest;
> -
> - if (bb == EXIT_BLOCK_PTR
> - || TEST_BIT (visited, bb->index))
> - {
> - if (!ei_end_p (ei))
> - ei_next (&ei);
> - act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
> - continue;
> - }
> - SET_BIT (visited, bb->index);
> -
> - if (TEST_BIT (st_antloc[bb->index], smexpr->index))
> - {
> - for (last = ANTIC_STORE_LIST (smexpr);
> - BLOCK_FOR_INSN (XEXP (last, 0)) != bb;
> - last = XEXP (last, 1))
> - continue;
> - last = XEXP (last, 0);
> - }
> - else
> - last = NEXT_INSN (BB_END (bb));
> -
> - for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
> - if (INSN_P (insn))
> - {
> - note = find_reg_equal_equiv_note (insn);
> - if (!note || !expr_equiv_p (XEXP (note, 0), mem))
> - continue;
> -
> - if (dump_file)
> - fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
> - INSN_UID (insn));
> - remove_note (insn, note);
> - }
> -
> - if (!ei_end_p (ei))
> - ei_next (&ei);
> - act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
> -
> - if (EDGE_COUNT (bb->succs) > 0)
> - {
> - if (act)
> - stack[sp++] = ei;
> - ei = ei_start (bb->succs);
> - act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container
> (ei), 0) : NULL);
> - }
> - }
> -}
> -
> -/* This routine will replace a store with a SET to a specified register. */
> -
> -static void
> -replace_store_insn (rtx reg, rtx del, basic_block bb, struct ls_expr *smexpr)
> -{
> - rtx insn, mem, note, set, ptr;
> -
> - mem = smexpr->pattern;
> - insn = gen_move_insn (reg, SET_SRC (single_set (del)));
> -
> - for (ptr = ANTIC_STORE_LIST (smexpr); ptr; ptr = XEXP (ptr, 1))
> - if (XEXP (ptr, 0) == del)
> - {
> - XEXP (ptr, 0) = insn;
> - break;
> - }
> -
> - /* Move the notes from the deleted insn to its replacement. */
> - REG_NOTES (insn) = REG_NOTES (del);
> -
> - /* Emit the insn AFTER all the notes are transferred.
> - This is cheaper since we avoid df rescanning for the note change. */
> - insn = emit_insn_after (insn, del);
> -
> - if (dump_file)
> - {
> - fprintf (dump_file,
> - "STORE_MOTION delete insn in BB %d:\n ", bb->index);
> - print_inline_rtx (dump_file, del, 6);
> - fprintf (dump_file, "\nSTORE_MOTION replaced with insn:\n ");
> - print_inline_rtx (dump_file, insn, 6);
> - fprintf (dump_file, "\n");
> - }
> -
> - delete_insn (del);
> -
> - /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
> - they are no longer accurate provided that they are reached by this
> - definition, so drop them. */
> - for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
> - if (INSN_P (insn))
> - {
> - set = single_set (insn);
> - if (!set)
> - continue;
> - if (expr_equiv_p (SET_DEST (set), mem))
> - return;
> - note = find_reg_equal_equiv_note (insn);
> - if (!note || !expr_equiv_p (XEXP (note, 0), mem))
> - continue;
> -
> - if (dump_file)
> - fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
> - INSN_UID (insn));
> - remove_note (insn, note);
> - }
> - remove_reachable_equiv_notes (bb, smexpr);
> -}
> -
> -
> -/* Delete a store, but copy the value that would have been stored into
> - the reaching_reg for later storing. */
> -
> -static void
> -delete_store (struct ls_expr * expr, basic_block bb)
> -{
> - rtx reg, i, del;
> -
> - if (expr->reaching_reg == NULL_RTX)
> - expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
> -
> - 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, expr);
> - break;
> - }
> - }
> -}
> -
> -/* Free memory used by store motion. */
> -
> -static void
> -free_store_memory (void)
> -{
> - 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);
> -
> - ae_gen = ae_kill = transp = st_antloc = NULL;
> - pre_insert_map = pre_delete_map = NULL;
> -}
> -
> -/* Perform store motion. Much like gcse, except we move expressions the
> - other way by looking at the flowgraph in reverse.
> - Return non-zero if transformations are performed by the pass. */
> -
> -static int
> -one_store_motion_pass (void)
> -{
> - basic_block bb;
> - int x;
> - struct ls_expr * ptr;
> - int update_flow = 0;
> -
> - gcse_subst_count = 0;
> - gcse_create_count = 0;
> -
> - init_alias_analysis ();
> -
> - /* Find all the available and anticipatable stores. */
> - num_stores = compute_store_table ();
> - if (num_stores == 0)
> - {
> - htab_delete (pre_ldst_table);
> - pre_ldst_table = NULL;
> - end_alias_analysis ();
> - return 0;
> - }
> -
> - /* Now compute kill & transp vectors. */
> - build_store_vectors ();
> - add_noreturn_fake_exit_edges ();
> - connect_infinite_loops_to_exit ();
> -
> - edge_list = pre_edge_rev_lcm (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))
> - {
> - /* If any of the edges we have above are abnormal, we can't move this
> - store. */
> - for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
> - if (TEST_BIT (pre_insert_map[x], ptr->index)
> - && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
> - break;
> -
> - if (x >= 0)
> - {
> - if (dump_file != NULL)
> - fprintf (dump_file,
> - "Can't replace store %d: abnormal edge from %d to %d\n",
> - ptr->index, INDEX_EDGE (edge_list, x)->src->index,
> - INDEX_EDGE (edge_list, x)->dest->index);
> - continue;
> - }
> -
> - /* Now we want to insert the new stores which are going to be needed. */
> -
> - FOR_EACH_BB (bb)
> - if (TEST_BIT (pre_delete_map[bb->index], ptr->index))
> - {
> - delete_store (ptr, bb);
> - gcse_subst_count++;
> - }
> -
> - 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));
> - gcse_create_count++;
> - }
> - }
> -
> - if (update_flow)
> - commit_edge_insertions ();
> -
> - free_store_memory ();
> - free_edge_list (edge_list);
> - remove_fake_exit_edges ();
> - end_alias_analysis ();
> -
> - if (dump_file)
> - {
> - fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ",
> - current_function_name (), n_basic_blocks);
> - fprintf (dump_file, "%d substs, %d insns created\n",
> - gcse_subst_count, gcse_create_count);
> - }
> -
> - return (gcse_subst_count > 0 || gcse_create_count > 0);
> -}
> -
> -
> -/* Return true if the graph is too expensive to optimize. PASS is the
> - optimization about to be performed. */
> -
> -static bool
> -is_too_expensive (const char *pass)
> -{
> - /* Trying to perform global optimizations on flow graphs which have
> - a high connectivity will take a long time and is unlikely to be
> - particularly useful.
> -
> - In normal circumstances a cfg should have about twice as many
> - edges as blocks. But we do not want to punish small functions
> - which have a couple switch statements. Rather than simply
> - threshold the number of blocks, uses something with a more
> - graceful degradation. */
> - if (n_edges > 20000 + n_basic_blocks * 4)
> - {
> - warning (OPT_Wdisabled_optimization,
> - "%s: %d basic blocks and %d edges/basic block",
> - pass, n_basic_blocks, n_edges / n_basic_blocks);
> -
> - return true;
> - }
> -
> - /* If allocating memory for the cprop bitmap would take up too much
> - storage it's better just to disable the optimization. */
> - if ((n_basic_blocks
> - * SBITMAP_SET_SIZE (max_reg_num ())
> - * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
> - {
> - warning (OPT_Wdisabled_optimization,
> - "%s: %d basic blocks and %d registers",
> - pass, n_basic_blocks, max_reg_num ());
> -
> - return true;
> - }
> -
> - return false;
> -}
> -
> -
> -/* Main function for the CPROP pass. */
> -
> -static int
> -one_cprop_pass (void)
> -{
> - int changed = 0;
> -
> - /* Return if there's nothing to do, or it is too expensive. */
> - if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
> - || is_too_expensive (_ ("const/copy propagation disabled")))
> - return 0;
> -
> - global_const_prop_count = local_const_prop_count = 0;
> - global_copy_prop_count = local_copy_prop_count = 0;
> -
> - bytes_used = 0;
> - gcc_obstack_init (&gcse_obstack);
> - alloc_gcse_mem ();
> -
> - /* Do a local const/copy propagation pass first. The global pass
> - only handles global opportunities.
> - If the local pass changes something, remove any unreachable blocks
> - because the CPROP global dataflow analysis may get into infinite
> - loops for CFGs with unreachable blocks.
> -
> - FIXME: This local pass should not be necessary after CSE (but for
> - some reason it still is). It is also (proven) not necessary
> - to run the local pass right after FWPWOP.
> -
> - FIXME: The global analysis would not get into infinite loops if it
> - would use the DF solver (via df_simple_dataflow) instead of
> - the solver implemented in this file. */
> - if (local_cprop_pass ())
> - {
> - delete_unreachable_blocks ();
> - df_analyze ();
> - }
> -
> - /* Determine implicit sets. */
> - implicit_sets = XCNEWVEC (rtx, last_basic_block);
> - find_implicit_sets ();
> -
> - alloc_hash_table (get_max_uid (), &set_hash_table, 1);
> - compute_hash_table (&set_hash_table);
> -
> - /* Free implicit_sets before peak usage. */
> - free (implicit_sets);
> - implicit_sets = NULL;
> -
> - if (dump_file)
> - dump_hash_table (dump_file, "SET", &set_hash_table);
> - if (set_hash_table.n_elems > 0)
> - {
> - basic_block bb;
> - rtx insn;
> -
> - alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
> - compute_cprop_data ();
> -
> - FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb,
> EXIT_BLOCK_PTR, next_bb)
> - {
> - /* Reset tables used to keep track of what's still valid [since
> - the start of the block]. */
> - reset_opr_set_tables ();
> -
> - FOR_BB_INSNS (bb, insn)
> - if (INSN_P (insn))
> - {
> - changed |= cprop_insn (insn);
> -
> - /* Keep track of everything modified by this insn. */
> - /* ??? Need to be careful w.r.t. mods done to INSN.
> - Don't call mark_oprs_set if we turned the
> - insn into a NOTE. */
> - if (! NOTE_P (insn))
> - mark_oprs_set (insn);
> - }
> - }
> -
> - changed |= bypass_conditional_jumps ();
> - free_cprop_mem ();
> - }
> -
> - free_hash_table (&set_hash_table);
> - free_gcse_mem ();
> - obstack_free (&gcse_obstack, NULL);
> -
> - if (dump_file)
> - {
> - fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ",
> - current_function_name (), n_basic_blocks, bytes_used);
> - fprintf (dump_file, "%d local const props, %d local copy props, ",
> - local_const_prop_count, local_copy_prop_count);
> - fprintf (dump_file, "%d global const props, %d global copy props\n\n",
> - global_const_prop_count, global_copy_prop_count);
> - }
> -
> - return changed;
> -}
> -
> -
> -/* All the passes implemented in this file. Each pass has its
> - own gate and execute function, and at the end of the file a
> - pass definition for passes.c.
> -
> - We do not construct an accurate cfg in functions which call
> - setjmp, so none of these passes runs if the function calls
> - setjmp.
> - FIXME: Should just handle setjmp via REG_SETJMP notes. */
> -
> -static bool
> -gate_rtl_cprop (void)
> -{
> - return optimize > 0 && flag_gcse
> - && !cfun->calls_setjmp
> - && dbg_cnt (cprop);
> -}
> -
> -static unsigned int
> -execute_rtl_cprop (void)
> -{
> - delete_unreachable_blocks ();
> - df_note_add_problem ();
> - df_set_flags (DF_LR_RUN_DCE);
> - df_analyze ();
> - flag_rerun_cse_after_global_opts |= one_cprop_pass ();
> - return 0;
> -}
> -
> -static bool
> -gate_rtl_pre (void)
> -{
> - return optimize > 0 && flag_gcse
> - && !cfun->calls_setjmp
> - && optimize_function_for_speed_p (cfun)
> - && dbg_cnt (pre);
> -}
> -
> -static unsigned int
> -execute_rtl_pre (void)
> -{
> - delete_unreachable_blocks ();
> - df_note_add_problem ();
> - df_analyze ();
> - flag_rerun_cse_after_global_opts |= one_pre_gcse_pass ();
> - return 0;
> -}
> -
> -static bool
> -gate_rtl_hoist (void)
> -{
> - return optimize > 0 && flag_gcse
> - && !cfun->calls_setjmp
> - /* It does not make sense to run code hoisting unless we are optimizing
> - for code size -- it rarely makes programs faster, and can make then
> - bigger if we did PRE (when optimizing for space, we don't run PRE). */
> - && optimize_function_for_size_p (cfun)
> - && dbg_cnt (hoist);
> -}
> -
> -static unsigned int
> -execute_rtl_hoist (void)
> -{
> - delete_unreachable_blocks ();
> - df_note_add_problem ();
> - df_analyze ();
> - flag_rerun_cse_after_global_opts |= one_code_hoisting_pass ();
> - return 0;
> -}
> -
> -static bool
> -gate_rtl_store_motion (void)
> -{
> - return optimize > 0 && flag_gcse_sm
> - && !cfun->calls_setjmp
> - && optimize_function_for_speed_p (cfun)
> - && dbg_cnt (store_motion);
> -}
> -
> -static unsigned int
> -execute_rtl_store_motion (void)
> -{
> - delete_unreachable_blocks ();
> - df_note_add_problem ();
> - df_analyze ();
> - flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
> - return 0;
> -}
> +static unsigned int
> +execute_rtl_hoist (void)
> +{
> + delete_unreachable_blocks ();
> + df_note_add_problem ();
> + df_analyze ();
> + flag_rerun_cse_after_global_opts |= one_code_hoisting_pass ();
> + return 0;
> +}
>
> struct rtl_opt_pass pass_rtl_cprop =
> {
> @@ -6294,25 +5161,4 @@ struct rtl_opt_pass pass_rtl_hoist =
> }
> };
>
> -struct rtl_opt_pass pass_rtl_store_motion =
> -{
> - {
> - RTL_PASS,
> - "store_motion", /* name */
> - gate_rtl_store_motion, /* gate */
> - execute_rtl_store_motion, /* execute */
> - NULL, /* sub */
> - NULL, /* next */
> - 0, /* static_pass_number */
> - TV_LSM, /* tv_id */
> - PROP_cfglayout, /* properties_required */
> - 0, /* properties_provided */
> - 0, /* properties_destroyed */
> - 0, /* todo_flags_start */
> - TODO_df_finish | TODO_verify_rtl_sharing |
> - TODO_dump_func |
> - TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */
> - }
> -};
> -
> #include "gt-gcse.h"
> Index: store-motion.c
> ===================================================================
> --- store-motion.c (revision 0)
> +++ store-motion.c (revision 0)
> @@ -0,0 +1,1405 @@
> +/* Store motion via Lazy Code Motion on the reverse CFG.
> + Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
> + 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
> +
> +This file is part of GCC.
> +
> +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 3, or (at your option) any later
> +version.
> +
> +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 GCC; see the file COPYING3. If not see
> +<http://www.gnu.org/licenses/>. */
> +
> +#include "config.h"
> +#include "system.h"
> +#include "coretypes.h"
> +#include "tm.h"
> +#include "toplev.h"
> +
> +#include "rtl.h"
> +#include "tree.h"
> +#include "tm_p.h"
> +#include "regs.h"
> +#include "hard-reg-set.h"
> +#include "flags.h"
> +#include "real.h"
> +#include "insn-config.h"
> +#include "recog.h"
> +#include "basic-block.h"
> +#include "output.h"
> +#include "function.h"
> +#include "expr.h"
> +#include "except.h"
> +#include "ggc.h"
> +#include "params.h"
> +#include "intl.h"
> +#include "timevar.h"
> +#include "tree-pass.h"
> +#include "hashtab.h"
> +#include "df.h"
> +#include "dbgcnt.h"
> +
> +
> +/* This is a list of expressions which are MEMs and will be used by load
> + or store motion.
> + Load motion tracks MEMs which aren't killed by
> + anything except itself. (i.e., loads and stores to a single location).
> + We can then allow movement of these MEM refs with a little special
> + allowance. (all stores copy the same value to the reaching reg used
> + for the loads). This means all values used to store into memory must have
> + no side effects so we can re-issue the setter value.
> + Store Motion uses this structure as an expression table to track stores
> + which look interesting, and might be moveable towards the exit block. */
> +
> +struct ls_expr
> +{
> + rtx pattern; /* Pattern of this mem. */
> + rtx pattern_regs; /* List of registers mentioned by the 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. */
> + unsigned int hash_index; /* Index when in a hash table. */
> + rtx reaching_reg; /* Register to use when re-writing. */
> +};
> +
> +/* Head of the list of load/store memory refs. */
> +static struct ls_expr * pre_ldst_mems = NULL;
> +
> +/* Hashtable for the load/store memory refs. */
> +static htab_t pre_ldst_table = NULL;
> +
> +/* Various variables for statistics gathering. */
> +
> +/* GCSE substitutions made. */
> +static int gcse_subst_count;
> +/* Number of copy instructions created. */
> +static int gcse_create_count;
> +/* For available exprs */
> +static sbitmap *ae_kill, *ae_gen;
> +
> +/* Nonzero for expressions that are transparent in the block. */
> +static sbitmap *transp;
> +
> +/* Nonzero for expressions which should be inserted on a specific edge. */
> +static sbitmap *pre_insert_map;
> +
> +/* Nonzero for expressions which should be deleted in a specific block. */
> +static sbitmap *pre_delete_map;
> +
> +/* Contains the edge_list returned by pre_edge_lcm. */
> +static struct edge_list *edge_list;
> +
> +/* Here we provide the things required to do store motion towards
> + the exit. In order for this to be effective, PRE load motion 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. */
> +
> +static hashval_t
> +pre_ldst_expr_hash (const void *p)
> +{
> + int do_not_record_p = 0;
> + const struct ls_expr *const x = (const struct ls_expr *) p;
> + return hash_rtx (x->pattern, GET_MODE (x->pattern),
> &do_not_record_p, NULL, false);
> +}
> +
> +static int
> +pre_ldst_expr_eq (const void *p1, const void *p2)
> +{
> + const struct ls_expr *const ptr1 = (const struct ls_expr *) p1,
> + *const ptr2 = (const struct ls_expr *) p2;
> + return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true);
> +}
> +
> +/* 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 (rtx x)
> +{
> + int do_not_record_p = 0;
> + struct ls_expr * ptr;
> + unsigned int hash;
> + void **slot;
> + struct ls_expr e;
> +
> + hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
> + NULL, /*have_reg_qty=*/false);
> +
> + e.pattern = x;
> + slot = htab_find_slot_with_hash (pre_ldst_table, &e, hash, INSERT);
> + if (*slot)
> + return (struct ls_expr *)*slot;
> +
> + ptr = XNEW (struct ls_expr);
> +
> + ptr->next = pre_ldst_mems;
> + ptr->pattern = x;
> + ptr->pattern_regs = NULL_RTX;
> + ptr->loads = NULL_RTX;
> + ptr->stores = NULL_RTX;
> + ptr->reaching_reg = NULL_RTX;
> + ptr->invalid = 0;
> + ptr->index = 0;
> + ptr->hash_index = hash;
> + pre_ldst_mems = ptr;
> + *slot = ptr;
> +
> + return ptr;
> +}
> +
> +/* Free up an individual ldst entry. */
> +
> +static void
> +free_ldst_entry (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 (void)
> +{
> + if (pre_ldst_table)
> + htab_delete (pre_ldst_table);
> + pre_ldst_table = NULL;
> +
> + 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;
> +}
> +
> +/* Assign each element of the list of mems a monotonically increasing
> value. */
> +
> +static int
> +enumerate_ldsts (void)
> +{
> + 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 (void)
> +{
> + return pre_ldst_mems;
> +}
> +
> +/* Return the next item in the list after the specified one. */
> +
> +static inline struct ls_expr *
> +next_ls_expr (struct ls_expr * ptr)
> +{
> + return ptr->next;
> +}
> +
> +/* Dump debugging info about the ldst list. */
> +
> +static void
> +print_ldst_list (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");
> +}
> +
> +/* Store motion code. */
> +
> +#define ANTIC_STORE_LIST(x) ((x)->loads)
> +#define AVAIL_STORE_LIST(x) ((x)->stores)
> +#define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
> +
> +/* 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 int * regvec;
> +
> +/* And current insn, for the same routine. */
> +static rtx compute_store_table_current_insn;
> +
> +/* 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 (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
> + void *data ATTRIBUTE_UNUSED)
> +{
> + if (GET_CODE (dest) == SUBREG)
> + dest = SUBREG_REG (dest);
> +
> + if (REG_P (dest))
> + regvec[REGNO (dest)] = INSN_UID (compute_store_table_current_insn);
> +}
> +
> +/* Clear any mark that says that this insn sets dest. Called from
> + note_stores. */
> +
> +static void
> +reg_clear_last_set (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
> + void *data)
> +{
> + int *dead_vec = (int *) data;
> +
> + if (GET_CODE (dest) == SUBREG)
> + dest = SUBREG_REG (dest);
> +
> + if (REG_P (dest) &&
> + dead_vec[REGNO (dest)] == INSN_UID (compute_store_table_current_insn))
> + dead_vec[REGNO (dest)] = 0;
> +}
> +
> +/* Return zero if some of the registers in list X are killed
> + due to set of registers in bitmap REGS_SET. */
> +
> +static bool
> +store_ops_ok (const_rtx x, int *regs_set)
> +{
> + const_rtx reg;
> +
> + for (; x; x = XEXP (x, 1))
> + {
> + reg = XEXP (x, 0);
> + if (regs_set[REGNO(reg)])
> + return false;
> + }
> +
> + return true;
> +}
> +
> +/* Helper for extract_mentioned_regs; ACCUM is used to accumulate used
> + registers. */
> +static rtx
> +extract_mentioned_regs_helper (rtx x, rtx accum)
> +{
> + int i;
> + enum rtx_code code;
> + const char * fmt;
> +
> + /* Repeat is used to turn tail-recursion into iteration. */
> + repeat:
> +
> + if (x == 0)
> + return accum;
> +
> + code = GET_CODE (x);
> + switch (code)
> + {
> + case REG:
> + return alloc_EXPR_LIST (0, x, accum);
> +
> + case MEM:
> + x = XEXP (x, 0);
> + goto repeat;
> +
> + case PRE_DEC:
> + case PRE_INC:
> + case PRE_MODIFY:
> + case POST_DEC:
> + case POST_INC:
> + case POST_MODIFY:
> + /* We do not run this function with arguments having side effects. */
> + gcc_unreachable ();
> +
> + case PC:
> + case CC0: /*FIXME*/
> + case CONST:
> + case CONST_INT:
> + case CONST_DOUBLE:
> + case CONST_FIXED:
> + case CONST_VECTOR:
> + case SYMBOL_REF:
> + case LABEL_REF:
> + case ADDR_VEC:
> + case ADDR_DIFF_VEC:
> + return accum;
> +
> + 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. */
> + if (i == 0)
> + {
> + x = tem;
> + goto repeat;
> + }
> +
> + accum = extract_mentioned_regs_helper (tem, accum);
> + }
> + else if (fmt[i] == 'E')
> + {
> + int j;
> +
> + for (j = 0; j < XVECLEN (x, i); j++)
> + accum = extract_mentioned_regs_helper (XVECEXP (x, i, j), accum);
> + }
> + }
> +
> + return accum;
> +}
> +
> +/* Returns a list of registers mentioned in X. */
> +/* ??? Reimplement with for_each_rtx? */
> +static rtx
> +extract_mentioned_regs (rtx x)
> +{
> + return extract_mentioned_regs_helper (x, NULL_RTX);
> +}
> +
> +/* Check to see if the load X is aliased with STORE_PATTERN.
> + AFTER is true if we are checking the case when STORE_PATTERN occurs
> + after the X. */
> +
> +static bool
> +load_kills_store (const_rtx x, const_rtx store_pattern, int after)
> +{
> + if (after)
> + return anti_dependence (x, store_pattern);
> + else
> + return true_dependence (store_pattern, GET_MODE (store_pattern), x,
> + rtx_addr_varies_p);
> +}
> +
> +/* Go through the entire insn X, looking for any loads which might alias
> + STORE_PATTERN. Return true if found.
> + AFTER is true if we are checking the case when STORE_PATTERN occurs
> + after the insn X. */
> +
> +static bool
> +find_loads (const_rtx x, const_rtx store_pattern, int after)
> +{
> + const char * fmt;
> + int i, j;
> + int ret = false;
> +
> + if (!x)
> + return false;
> +
> + if (GET_CODE (x) == SET)
> + x = SET_SRC (x);
> +
> + if (MEM_P (x))
> + {
> + if (load_kills_store (x, store_pattern, after))
> + return true;
> + }
> +
> + /* 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, after);
> + else if (fmt[i] == 'E')
> + for (j = XVECLEN (x, i) - 1; j >= 0; j--)
> + ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
> + }
> + return ret;
> +}
> +
> +/* Go through pattern PAT looking for any loads which might kill the
> + store in X. Return true if found.
> + AFTER is true if we are checking the case when loads kill X occurs
> + after the insn for PAT. */
> +
> +static inline bool
> +store_killed_in_pat (const_rtx x, const_rtx pat, int after)
> +{
> + if (GET_CODE (pat) == SET)
> + {
> + rtx dest = SET_DEST (pat);
> +
> + if (GET_CODE (dest) == ZERO_EXTRACT)
> + dest = XEXP (dest, 0);
> +
> + /* Check for memory stores to aliased objects. */
> + if (MEM_P (dest)
> + && !exp_equiv_p (dest, x, 0, true))
> + {
> + if (after)
> + {
> + if (output_dependence (dest, x))
> + return true;
> + }
> + else
> + {
> + if (output_dependence (x, dest))
> + return true;
> + }
> + }
> + }
> +
> + if (find_loads (pat, x, after))
> + return true;
> +
> + return false;
> +}
> +
> +/* Check if INSN kills the store pattern X (is aliased with it).
> + AFTER is true if we are checking the case when store X occurs
> + after the insn. Return true if it does. */
> +
> +static bool
> +store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after)
> +{
> + const_rtx reg, base, note, pat;
> +
> + if (!INSN_P (insn))
> + return false;
> +
> + if (CALL_P (insn))
> + {
> + /* A normal or pure call might read from pattern,
> + but a const call will not. */
> + if (!RTL_CONST_CALL_P (insn))
> + return true;
> +
> + /* But even a const call reads its parameters. Check whether the
> + base of some of registers used in mem is stack pointer. */
> + for (reg = x_regs; reg; reg = XEXP (reg, 1))
> + {
> + base = find_base_term (XEXP (reg, 0));
> + if (!base
> + || (GET_CODE (base) == ADDRESS
> + && GET_MODE (base) == Pmode
> + && XEXP (base, 0) == stack_pointer_rtx))
> + return true;
> + }
> +
> + return false;
> + }
> +
> + pat = PATTERN (insn);
> + if (GET_CODE (pat) == SET)
> + {
> + if (store_killed_in_pat (x, pat, after))
> + return true;
> + }
> + else if (GET_CODE (pat) == PARALLEL)
> + {
> + int i;
> +
> + for (i = 0; i < XVECLEN (pat, 0); i++)
> + if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
> + return true;
> + }
> + else if (find_loads (PATTERN (insn), x, after))
> + return true;
> +
> + /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
> + location aliased with X, then this insn kills X. */
> + note = find_reg_equal_equiv_note (insn);
> + if (! note)
> + return false;
> + note = XEXP (note, 0);
> +
> + /* However, if the note represents a must alias rather than a may
> + alias relationship, then it does not kill X. */
> + if (exp_equiv_p (note, x, 0, true))
> + return false;
> +
> + /* See if there are any aliased loads in the note. */
> + return find_loads (note, x, after);
> +}
> +
> +/* Returns true if the expression X is loaded or clobbered on or after INSN
> + within basic block BB. REGS_SET_AFTER is bitmap of registers set in
> + or after the insn. X_REGS is list of registers mentioned in X. If the store
> + is killed, return the last insn in that it occurs in FAIL_INSN. */
> +
> +static bool
> +store_killed_after (const_rtx x, const_rtx x_regs, const_rtx insn,
> const_basic_block bb,
> + int *regs_set_after, rtx *fail_insn)
> +{
> + rtx last = BB_END (bb), act;
> +
> + if (!store_ops_ok (x_regs, regs_set_after))
> + {
> + /* We do not know where it will happen. */
> + if (fail_insn)
> + *fail_insn = NULL_RTX;
> + return true;
> + }
> +
> + /* Scan from the end, so that fail_insn is determined correctly. */
> + for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
> + if (store_killed_in_insn (x, x_regs, act, false))
> + {
> + if (fail_insn)
> + *fail_insn = act;
> + return true;
> + }
> +
> + return false;
> +}
> +
> +/* Returns true if the expression X is loaded or clobbered on or before INSN
> + within basic block BB. X_REGS is list of registers mentioned in X.
> + REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
> +static bool
> +store_killed_before (const_rtx x, const_rtx x_regs, const_rtx insn,
> const_basic_block bb,
> + int *regs_set_before)
> +{
> + rtx first = BB_HEAD (bb);
> +
> + if (!store_ops_ok (x_regs, regs_set_before))
> + return true;
> +
> + for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
> + if (store_killed_in_insn (x, x_regs, insn, true))
> + return true;
> +
> + return false;
> +}
> +
> +/* Determine whether INSN is MEM store pattern that we will consider moving.
> + REGS_SET_BEFORE is bitmap of registers set before (and including) the
> + current insn, REGS_SET_AFTER is bitmap of registers set after (and
> + including) the insn in this basic block. We must be passing through BB from
> + head to end, as we are using this fact to speed things up.
> +
> + The results are stored this way:
> +
> + -- the first anticipatable expression is added into ANTIC_STORE_LIST
> + -- if the processed expression is not anticipatable, NULL_RTX is added
> + there instead, so that we can use it as indicator that no further
> + expression of this type may be anticipatable
> + -- if the expression is available, it is added as head of AVAIL_STORE_LIST;
> + consequently, all of them but this head are dead and may be deleted.
> + -- if the expression is not available, the insn due to that it fails to be
> + available is stored in reaching_reg.
> +
> + The things are complicated a bit by fact that there already may be stores
> + to the same MEM from other blocks; also caller must take care of the
> + necessary cleanup of the temporary markers after end of the basic block.
> + */
> +
> +static void
> +find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after)
> +{
> + struct ls_expr * ptr;
> + rtx dest, set, tmp;
> + int check_anticipatable, check_available;
> + basic_block bb = BLOCK_FOR_INSN (insn);
> +
> + set = single_set (insn);
> + if (!set)
> + return;
> +
> + dest = SET_DEST (set);
> +
> + if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
> + || GET_MODE (dest) == BLKmode)
> + return;
> +
> + if (side_effects_p (dest))
> + return;
> +
> + /* If we are handling exceptions, we must be careful with memory references
> + that may trap. If we are not, the behavior is undefined, so we may just
> + continue. */
> + if (flag_non_call_exceptions && may_trap_p (dest))
> + return;
> +
> + /* Even if the destination cannot trap, the source may. In this case we'd
> + need to handle updating the REG_EH_REGION note. */
> + if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
> + return;
> +
> + /* Make sure that the SET_SRC of this store insns can be assigned to
> + a register, or we will fail later on in replace_store_insn, which
> + assumes that we can do this. But sometimes the target machine has
> + oddities like MEM read-modify-write instruction. See for example
> + PR24257. */
> + if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set)))
> + return;
> +
> + ptr = ldst_entry (dest);
> + if (!ptr->pattern_regs)
> + ptr->pattern_regs = extract_mentioned_regs (dest);
> +
> + /* Do not check for anticipatability if we either found one anticipatable
> + store already, or tested for one and found out that it was killed. */
> + check_anticipatable = 0;
> + if (!ANTIC_STORE_LIST (ptr))
> + check_anticipatable = 1;
> + else
> + {
> + tmp = XEXP (ANTIC_STORE_LIST (ptr), 0);
> + if (tmp != NULL_RTX
> + && BLOCK_FOR_INSN (tmp) != bb)
> + check_anticipatable = 1;
> + }
> + if (check_anticipatable)
> + {
> + if (store_killed_before (dest, ptr->pattern_regs, insn, bb,
> regs_set_before))
> + tmp = NULL_RTX;
> + else
> + tmp = insn;
> + ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (tmp,
> + ANTIC_STORE_LIST (ptr));
> + }
> +
> + /* It is not necessary to check whether store is available if we did
> + it successfully before; if we failed before, do not bother to check
> + until we reach the insn that caused us to fail. */
> + check_available = 0;
> + if (!AVAIL_STORE_LIST (ptr))
> + check_available = 1;
> + else
> + {
> + tmp = XEXP (AVAIL_STORE_LIST (ptr), 0);
> + if (BLOCK_FOR_INSN (tmp) != bb)
> + check_available = 1;
> + }
> + if (check_available)
> + {
> + /* Check that we have already reached the insn at that the check
> + failed last time. */
> + if (LAST_AVAIL_CHECK_FAILURE (ptr))
> + {
> + for (tmp = BB_END (bb);
> + tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
> + tmp = PREV_INSN (tmp))
> + continue;
> + if (tmp == insn)
> + check_available = 0;
> + }
> + else
> + check_available = store_killed_after (dest, ptr->pattern_regs, insn,
> + bb, regs_set_after,
> + &LAST_AVAIL_CHECK_FAILURE (ptr));
> + }
> + if (!check_available)
> + AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn, AVAIL_STORE_LIST (ptr));
> +}
> +
> +/* Find available and anticipatable stores. */
> +
> +static int
> +compute_store_table (void)
> +{
> + int ret;
> + basic_block bb;
> + unsigned regno;
> + rtx insn, pat, tmp;
> + int *last_set_in, *already_set;
> + struct ls_expr * ptr, **prev_next_ptr_ptr;
> + unsigned int max_gcse_regno = max_reg_num ();
> +
> + pre_ldst_mems = 0;
> + pre_ldst_table = htab_create (13, pre_ldst_expr_hash,
> + pre_ldst_expr_eq, NULL);
> + last_set_in = XCNEWVEC (int, max_gcse_regno);
> + already_set = XNEWVEC (int, max_gcse_regno);
> +
> + /* Find all the stores we care about. */
> + FOR_EACH_BB (bb)
> + {
> + /* First compute the registers set in this block. */
> + regvec = last_set_in;
> +
> + FOR_BB_INSNS (bb, insn)
> + {
> + if (! INSN_P (insn))
> + continue;
> +
> + if (CALL_P (insn))
> + {
> + for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
> + if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
> + last_set_in[regno] = INSN_UID (insn);
> + }
> +
> + pat = PATTERN (insn);
> + compute_store_table_current_insn = insn;
> + note_stores (pat, reg_set_info, NULL);
> + }
> +
> + /* Now find the stores. */
> + memset (already_set, 0, sizeof (int) * max_gcse_regno);
> + regvec = already_set;
> + FOR_BB_INSNS (bb, insn)
> + {
> + if (! INSN_P (insn))
> + continue;
> +
> + if (CALL_P (insn))
> + {
> + for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
> + if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
> + already_set[regno] = 1;
> + }
> +
> + pat = PATTERN (insn);
> + note_stores (pat, reg_set_info, NULL);
> +
> + /* Now that we've marked regs, look for stores. */
> + find_moveable_store (insn, already_set, last_set_in);
> +
> + /* Unmark regs that are no longer set. */
> + compute_store_table_current_insn = insn;
> + note_stores (pat, reg_clear_last_set, last_set_in);
> + if (CALL_P (insn))
> + {
> + for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
> + if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)
> + && last_set_in[regno] == INSN_UID (insn))
> + last_set_in[regno] = 0;
> + }
> + }
> +
> +#ifdef ENABLE_CHECKING
> + /* last_set_in should now be all-zero. */
> + for (regno = 0; regno < max_gcse_regno; regno++)
> + gcc_assert (!last_set_in[regno]);
> +#endif
> +
> + /* Clear temporary marks. */
> + for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
> + {
> + LAST_AVAIL_CHECK_FAILURE(ptr) = NULL_RTX;
> + if (ANTIC_STORE_LIST (ptr)
> + && (tmp = XEXP (ANTIC_STORE_LIST (ptr), 0)) == NULL_RTX)
> + ANTIC_STORE_LIST (ptr) = XEXP (ANTIC_STORE_LIST (ptr), 1);
> + }
> + }
> +
> + /* Remove the stores that are not available anywhere, as there will
> + be no opportunity to optimize them. */
> + for (ptr = pre_ldst_mems, prev_next_ptr_ptr = &pre_ldst_mems;
> + ptr != NULL;
> + ptr = *prev_next_ptr_ptr)
> + {
> + if (!AVAIL_STORE_LIST (ptr))
> + {
> + *prev_next_ptr_ptr = ptr->next;
> + htab_remove_elt_with_hash (pre_ldst_table, ptr, ptr->hash_index);
> + free_ldst_entry (ptr);
> + }
> + else
> + prev_next_ptr_ptr = &ptr->next;
> + }
> +
> + ret = enumerate_ldsts ();
> +
> + if (dump_file)
> + {
> + fprintf (dump_file, "ST_avail and ST_antic (shown under loads..)\n");
> + print_ldst_list (dump_file);
> + }
> +
> + free (last_set_in);
> + free (already_set);
> + return ret;
> +}
> +
> +/* Insert an instruction at the beginning of a basic block, and update
> + the BB_HEAD if needed. */
> +
> +static void
> +insert_insn_start_basic_block (rtx insn, basic_block bb)
> +{
> + /* Insert at start of successor block. */
> + rtx prev = PREV_INSN (BB_HEAD (bb));
> + rtx before = BB_HEAD (bb);
> + while (before != 0)
> + {
> + if (! LABEL_P (before)
> + && !NOTE_INSN_BASIC_BLOCK_P (before))
> + break;
> + prev = before;
> + if (prev == BB_END (bb))
> + break;
> + before = NEXT_INSN (before);
> + }
> +
> + insn = emit_insn_after_noloc (insn, prev, bb);
> +
> + if (dump_file)
> + {
> + fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n",
> + bb->index);
> + print_inline_rtx (dump_file, insn, 6);
> + fprintf (dump_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 nonzero
> + if an edge insertion was performed. */
> +
> +static int
> +insert_store (struct ls_expr * expr, edge e)
> +{
> + rtx reg, insn;
> + basic_block bb;
> + edge tmp;
> + edge_iterator ei;
> +
> + /* 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;
> +
> + if (e->flags & EDGE_FAKE)
> + return 0;
> +
> + reg = expr->reaching_reg;
> + insn = gen_move_insn (copy_rtx (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_EACH_EDGE (tmp, ei, e->dest->preds)
> + if (!(tmp->flags & EDGE_FAKE))
> + {
> + int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
> +
> + gcc_assert (index != EDGE_INDEX_NO_EDGE);
> + 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_EACH_EDGE (tmp, ei, e->dest->preds)
> + {
> + int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
> + RESET_BIT (pre_insert_map[index], expr->index);
> + }
> + insert_insn_start_basic_block (insn, bb);
> + return 0;
> + }
> +
> + /* We can't put stores in the front of blocks pointed to by abnormal
> + edges since that may put a store where one didn't used to be. */
> + gcc_assert (!(e->flags & EDGE_ABNORMAL));
> +
> + insert_insn_on_edge (insn, e);
> +
> + if (dump_file)
> + {
> + fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
> + e->src->index, e->dest->index);
> + print_inline_rtx (dump_file, insn, 6);
> + fprintf (dump_file, "\n");
> + }
> +
> + return 1;
> +}
> +
> +/* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
> + memory location in SMEXPR set in basic block BB.
> +
> + This could be rather expensive. */
> +
> +static void
> +remove_reachable_equiv_notes (basic_block bb, struct ls_expr *smexpr)
> +{
> + edge_iterator *stack, ei;
> + int sp;
> + edge act;
> + sbitmap visited = sbitmap_alloc (last_basic_block);
> + rtx last, insn, note;
> + rtx mem = smexpr->pattern;
> +
> + stack = XNEWVEC (edge_iterator, n_basic_blocks);
> + sp = 0;
> + ei = ei_start (bb->succs);
> +
> + sbitmap_zero (visited);
> +
> + act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container
> (ei), 0) : NULL);
> + while (1)
> + {
> + if (!act)
> + {
> + if (!sp)
> + {
> + free (stack);
> + sbitmap_free (visited);
> + return;
> + }
> + act = ei_edge (stack[--sp]);
> + }
> + bb = act->dest;
> +
> + if (bb == EXIT_BLOCK_PTR
> + || TEST_BIT (visited, bb->index))
> + {
> + if (!ei_end_p (ei))
> + ei_next (&ei);
> + act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
> + continue;
> + }
> + SET_BIT (visited, bb->index);
> +
> + if (TEST_BIT (st_antloc[bb->index], smexpr->index))
> + {
> + for (last = ANTIC_STORE_LIST (smexpr);
> + BLOCK_FOR_INSN (XEXP (last, 0)) != bb;
> + last = XEXP (last, 1))
> + continue;
> + last = XEXP (last, 0);
> + }
> + else
> + last = NEXT_INSN (BB_END (bb));
> +
> + for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
> + if (INSN_P (insn))
> + {
> + note = find_reg_equal_equiv_note (insn);
> + if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
> + continue;
> +
> + if (dump_file)
> + fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
> + INSN_UID (insn));
> + remove_note (insn, note);
> + }
> +
> + if (!ei_end_p (ei))
> + ei_next (&ei);
> + act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
> +
> + if (EDGE_COUNT (bb->succs) > 0)
> + {
> + if (act)
> + stack[sp++] = ei;
> + ei = ei_start (bb->succs);
> + act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container
> (ei), 0) : NULL);
> + }
> + }
> +}
> +
> +/* This routine will replace a store with a SET to a specified register. */
> +
> +static void
> +replace_store_insn (rtx reg, rtx del, basic_block bb, struct ls_expr *smexpr)
> +{
> + rtx insn, mem, note, set, ptr;
> +
> + mem = smexpr->pattern;
> + insn = gen_move_insn (reg, SET_SRC (single_set (del)));
> +
> + for (ptr = ANTIC_STORE_LIST (smexpr); ptr; ptr = XEXP (ptr, 1))
> + if (XEXP (ptr, 0) == del)
> + {
> + XEXP (ptr, 0) = insn;
> + break;
> + }
> +
> + /* Move the notes from the deleted insn to its replacement. */
> + REG_NOTES (insn) = REG_NOTES (del);
> +
> + /* Emit the insn AFTER all the notes are transferred.
> + This is cheaper since we avoid df rescanning for the note change. */
> + insn = emit_insn_after (insn, del);
> +
> + if (dump_file)
> + {
> + fprintf (dump_file,
> + "STORE_MOTION delete insn in BB %d:\n ", bb->index);
> + print_inline_rtx (dump_file, del, 6);
> + fprintf (dump_file, "\nSTORE_MOTION replaced with insn:\n ");
> + print_inline_rtx (dump_file, insn, 6);
> + fprintf (dump_file, "\n");
> + }
> +
> + delete_insn (del);
> +
> + /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
> + they are no longer accurate provided that they are reached by this
> + definition, so drop them. */
> + for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
> + if (INSN_P (insn))
> + {
> + set = single_set (insn);
> + if (!set)
> + continue;
> + if (exp_equiv_p (SET_DEST (set), mem, 0, true))
> + return;
> + note = find_reg_equal_equiv_note (insn);
> + if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
> + continue;
> +
> + if (dump_file)
> + fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
> + INSN_UID (insn));
> + remove_note (insn, note);
> + }
> + remove_reachable_equiv_notes (bb, smexpr);
> +}
> +
> +
> +/* Delete a store, but copy the value that would have been stored into
> + the reaching_reg for later storing. */
> +
> +static void
> +delete_store (struct ls_expr * expr, basic_block bb)
> +{
> + rtx reg, i, del;
> +
> + if (expr->reaching_reg == NULL_RTX)
> + expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
> +
> + 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, expr);
> + break;
> + }
> + }
> +}
> +
> +/* Fill in available, anticipatable, transparent and kill vectors in
> + STORE_DATA, based on lists of available and anticipatable stores. */
> +static void
> +build_store_vectors (void)
> +{
> + basic_block bb;
> + int *regs_set_in_block;
> + rtx insn, st;
> + struct ls_expr * ptr;
> + unsigned int max_gcse_regno = max_reg_num ();
> +
> + /* Build the gen_vector. This is any store in the table which is not killed
> + by aliasing later in its block. */
> + ae_gen = sbitmap_vector_alloc (last_basic_block, num_stores);
> + sbitmap_vector_zero (ae_gen, last_basic_block);
> +
> + st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores);
> + sbitmap_vector_zero (st_antloc, last_basic_block);
> +
> + for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
> + {
> + for (st = AVAIL_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
> + {
> + insn = XEXP (st, 0);
> + bb = BLOCK_FOR_INSN (insn);
> +
> + /* If we've already seen an available expression in this block,
> + we can delete this one (It occurs earlier in the block). We'll
> + copy the SRC expression to an unused register in case there
> + are any side effects. */
> + if (TEST_BIT (ae_gen[bb->index], ptr->index))
> + {
> + rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
> + if (dump_file)
> + fprintf (dump_file, "Removing redundant store:\n");
> + replace_store_insn (r, XEXP (st, 0), bb, ptr);
> + continue;
> + }
> + SET_BIT (ae_gen[bb->index], ptr->index);
> + }
> +
> + for (st = ANTIC_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
> + {
> + insn = XEXP (st, 0);
> + bb = BLOCK_FOR_INSN (insn);
> + SET_BIT (st_antloc[bb->index], ptr->index);
> + }
> + }
> +
> + ae_kill = sbitmap_vector_alloc (last_basic_block, num_stores);
> + sbitmap_vector_zero (ae_kill, last_basic_block);
> +
> + transp = sbitmap_vector_alloc (last_basic_block, num_stores);
> + sbitmap_vector_zero (transp, last_basic_block);
> + regs_set_in_block = XNEWVEC (int, max_gcse_regno);
> +
> + FOR_EACH_BB (bb)
> + {
> + FOR_BB_INSNS (bb, insn)
> + if (INSN_P (insn))
> + {
> + df_ref *def_rec;
> + for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
> + {
> + unsigned int ref_regno = DF_REF_REGNO (*def_rec);
> + if (ref_regno < max_gcse_regno)
> + regs_set_in_block[DF_REF_REGNO (*def_rec)] = 1;
> + }
> + }
> +
> + for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
> + {
> + if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
> + bb, regs_set_in_block, NULL))
> + {
> + /* It should not be necessary to consider the expression
> + killed if it is both anticipatable and available. */
> + if (!TEST_BIT (st_antloc[bb->index], ptr->index)
> + || !TEST_BIT (ae_gen[bb->index], ptr->index))
> + SET_BIT (ae_kill[bb->index], ptr->index);
> + }
> + else
> + SET_BIT (transp[bb->index], ptr->index);
> + }
> + }
> +
> + free (regs_set_in_block);
> +
> + if (dump_file)
> + {
> + dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc,
> last_basic_block);
> + dump_sbitmap_vector (dump_file, "st_kill", "", ae_kill,
> last_basic_block);
> + dump_sbitmap_vector (dump_file, "Transpt", "", transp, last_basic_block);
> + dump_sbitmap_vector (dump_file, "st_avloc", "", ae_gen,
> last_basic_block);
> + }
> +}
> +
> +/* Free memory used by store motion. */
> +
> +static void
> +free_store_memory (void)
> +{
> + 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);
> +
> + ae_gen = ae_kill = transp = st_antloc = NULL;
> + pre_insert_map = pre_delete_map = NULL;
> +}
> +
> +/* Perform store motion. Much like gcse, except we move expressions the
> + other way by looking at the flowgraph in reverse.
> + Return non-zero if transformations are performed by the pass. */
> +
> +static int
> +one_store_motion_pass (void)
> +{
> + basic_block bb;
> + int x;
> + struct ls_expr * ptr;
> + int update_flow = 0;
> +
> + gcse_subst_count = 0;
> + gcse_create_count = 0;
> +
> + init_alias_analysis ();
> +
> + /* Find all the available and anticipatable stores. */
> + num_stores = compute_store_table ();
> + if (num_stores == 0)
> + {
> + htab_delete (pre_ldst_table);
> + pre_ldst_table = NULL;
> + end_alias_analysis ();
> + return 0;
> + }
> +
> + /* Now compute kill & transp vectors. */
> + build_store_vectors ();
> + add_noreturn_fake_exit_edges ();
> + connect_infinite_loops_to_exit ();
> +
> + edge_list = pre_edge_rev_lcm (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))
> + {
> + /* If any of the edges we have above are abnormal, we can't move this
> + store. */
> + for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
> + if (TEST_BIT (pre_insert_map[x], ptr->index)
> + && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
> + break;
> +
> + if (x >= 0)
> + {
> + if (dump_file != NULL)
> + fprintf (dump_file,
> + "Can't replace store %d: abnormal edge from %d to %d\n",
> + ptr->index, INDEX_EDGE (edge_list, x)->src->index,
> + INDEX_EDGE (edge_list, x)->dest->index);
> + continue;
> + }
> +
> + /* Now we want to insert the new stores which are going to be needed. */
> +
> + FOR_EACH_BB (bb)
> + if (TEST_BIT (pre_delete_map[bb->index], ptr->index))
> + {
> + delete_store (ptr, bb);
> + gcse_subst_count++;
> + }
> +
> + 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));
> + gcse_create_count++;
> + }
> + }
> +
> + if (update_flow)
> + commit_edge_insertions ();
> +
> + free_store_memory ();
> + free_edge_list (edge_list);
> + remove_fake_exit_edges ();
> + end_alias_analysis ();
> +
> + if (dump_file)
> + {
> + fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ",
> + current_function_name (), n_basic_blocks);
> + fprintf (dump_file, "%d substs, %d insns created\n",
> + gcse_subst_count, gcse_create_count);
> + }
> +
> + return (gcse_subst_count > 0 || gcse_create_count > 0);
> +}
> +
> +
> +static bool
> +gate_rtl_store_motion (void)
> +{
> + return optimize > 0 && flag_gcse_sm
> + && !cfun->calls_setjmp
> + && optimize_function_for_speed_p (cfun)
> + && dbg_cnt (store_motion);
> +}
> +
> +static unsigned int
> +execute_rtl_store_motion (void)
> +{
> + delete_unreachable_blocks ();
> + df_note_add_problem ();
> + df_analyze ();
> + flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
> + return 0;
> +}
> +
> +struct rtl_opt_pass pass_rtl_store_motion =
> +{
> + {
> + RTL_PASS,
> + "store_motion", /* name */
> + gate_rtl_store_motion, /* gate */
> + execute_rtl_store_motion, /* execute */
> + NULL, /* sub */
> + NULL, /* next */
> + 0, /* static_pass_number */
> + TV_LSM, /* tv_id */
> + PROP_cfglayout, /* properties_required */
> + 0, /* properties_provided */
> + 0, /* properties_destroyed */
> + 0, /* todo_flags_start */
> + TODO_df_finish | TODO_verify_rtl_sharing |
> + TODO_dump_func |
> + TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */
> + }
> +};
> +
> Index: rtl.h
> ===================================================================
> --- rtl.h (revision 146989)
> +++ rtl.h (working copy)
> @@ -2222,6 +2222,7 @@ extern void expand_dec (rtx, rtx);
>
> /* In gcse.c */
> extern bool can_copy_p (enum machine_mode);
> +extern bool can_assign_to_reg_without_clobbers_p (rtx);
> extern rtx fis_get_condition (rtx);
>
> /* In ira.c */
> Index: Makefile.in
> ===================================================================
> --- Makefile.in (revision 146989)
> +++ Makefile.in (working copy)
> @@ -1199,6 +1199,7 @@ OBJS-common = \
> statistics.o \
> stmt.o \
> stor-layout.o \
> + store-motion.o \
> stringpool.o \
> targhooks.o \
> timevar.o \
> @@ -2700,6 +2701,11 @@ see.o : see.c $(CONFIG_H) $(SYSTEM_H) co
> gcse.o : gcse.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
> $(REGS_H) hard-reg-set.h $(FLAGS_H) $(REAL_H) insn-config.h $(GGC_H) \
> $(RECOG_H) $(EXPR_H) $(BASIC_BLOCK_H) $(FUNCTION_H) output.h $(TOPLEV_H) \
> + $(TM_P_H) $(PARAMS_H) $(EXCEPT_H) $(TREE_H) $(TIMEVAR_H) \
> + intl.h $(OBSTACK_H) $(TREE_PASS_H) $(DF_H) $(DBGCNT_H)
> +store-motion.o : store-motion.c $(CONFIG_H) $(SYSTEM_H) coretypes.h
> $(TM_H) $(RTL_H) \
> + $(REGS_H) hard-reg-set.h $(FLAGS_H) $(REAL_H) insn-config.h $(GGC_H) \
> + $(RECOG_H) $(EXPR_H) $(BASIC_BLOCK_H) $(FUNCTION_H) output.h $(TOPLEV_H) \
> $(TM_P_H) $(PARAMS_H) $(EXCEPT_H) gt-gcse.h $(TREE_H) cselib.h
> $(TIMEVAR_H) \
> intl.h $(OBSTACK_H) $(TREE_PASS_H) $(DF_H) $(DBGCNT_H)
> resource.o : resource.c $(CONFIG_H) $(RTL_H) hard-reg-set.h $(SYSTEM_H) \
>
More information about the Gcc-patches
mailing list