- If a register is used as memory address with the form (mem (reg)), then we
- know that REG can not be zero at that point in the program. Any instruction
- which sets REG "kills" this property.
-
- So, if every path leading to a conditional branch has an available memory
- reference of that form, then we know the register can not have the value
- zero at the conditional branch.
-
- So we merely need to compute the local properties and propagate that data
- around the cfg, then optimize where possible.
-
- We run this pass two times. Once before CSE, then again after CSE. This
- has proven to be the most profitable approach. It is rare for new
- optimization opportunities of this nature to appear after the first CSE
- pass.
-
- This could probably be integrated with global cprop with a little work. */
-
-int
-delete_null_pointer_checks (rtx f ATTRIBUTE_UNUSED)
-{
- sbitmap *nonnull_avin, *nonnull_avout;
- unsigned int *block_reg;
- basic_block bb;
- int reg;
- int regs_per_pass;
- int max_reg = max_reg_num ();
- struct null_pointer_info npi;
- int something_changed = 0;
-
- /* If we have only a single block, or it is too expensive, give up. */
- if (n_basic_blocks <= 1
- || is_too_expensive (_ ("NULL pointer checks disabled")))
- return 0;
-
- /* We need four bitmaps, each with a bit for each register in each
- basic block. */
- regs_per_pass = get_bitmap_width (4, last_basic_block, max_reg);
-
- /* Allocate bitmaps to hold local and global properties. */
- npi.nonnull_local = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
- npi.nonnull_killed = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
- nonnull_avin = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
- nonnull_avout = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
-
- /* Go through the basic blocks, seeing whether or not each block
- ends with a conditional branch whose condition is a comparison
- against zero. Record the register compared in BLOCK_REG. */
- block_reg = xcalloc (last_basic_block, sizeof (int));
- FOR_EACH_BB (bb)
- {
- rtx last_insn = BB_END (bb);
- rtx condition, earliest, reg;
-
- /* We only want conditional branches. */
- if (GET_CODE (last_insn) != JUMP_INSN
- || !any_condjump_p (last_insn)
- || !onlyjump_p (last_insn))
- continue;
-
- /* LAST_INSN is a conditional jump. Get its condition. */
- condition = get_condition (last_insn, &earliest, false);
-
- /* If we were unable to get the condition, or it is not an equality
- comparison against zero then there's nothing we can do. */
- if (!condition
- || (GET_CODE (condition) != NE && GET_CODE (condition) != EQ)
- || GET_CODE (XEXP (condition, 1)) != CONST_INT
- || (XEXP (condition, 1)
- != CONST0_RTX (GET_MODE (XEXP (condition, 0)))))
- continue;
-
- /* We must be checking a register against zero. */
- reg = XEXP (condition, 0);
- if (GET_CODE (reg) != REG)
- continue;
-
- block_reg[bb->index] = REGNO (reg);
- }
-
- /* Go through the algorithm for each block of registers. */
- for (reg = FIRST_PSEUDO_REGISTER; reg < max_reg; reg += regs_per_pass)
- {
- npi.min_reg = reg;
- npi.max_reg = MIN (reg + regs_per_pass, max_reg);
- something_changed |= delete_null_pointer_checks_1 (block_reg,
- nonnull_avin,
- nonnull_avout,
- &npi);
- }
-
- /* Free the table of registers compared at the end of every block. */
- free (block_reg);
-
- /* Free bitmaps. */
- sbitmap_vector_free (npi.nonnull_local);
- sbitmap_vector_free (npi.nonnull_killed);
- sbitmap_vector_free (nonnull_avin);
- sbitmap_vector_free (nonnull_avout);
-
- return something_changed;
-}
-
-/* Code Hoisting variables and subroutines. */
-
-/* Very busy expressions. */
-static sbitmap *hoist_vbein;
-static sbitmap *hoist_vbeout;
-
-/* Hoistable expressions. */
-static sbitmap *hoist_exprs;
-
-/* ??? We could compute post dominators and run this algorithm in
- reverse to perform tail merging, doing so would probably be
- more effective than the tail merging code in jump.c.
-
- It's unclear if tail merging could be run in parallel with
- code hoisting. It would be nice. */
-
-/* Allocate vars used for code hoisting analysis. */
-
-static void
-alloc_code_hoist_mem (int n_blocks, int n_exprs)
-{
- antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
- transp = sbitmap_vector_alloc (n_blocks, n_exprs);
- comp = sbitmap_vector_alloc (n_blocks, n_exprs);
-
- hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs);
- hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs);
- hoist_exprs = sbitmap_vector_alloc (n_blocks, n_exprs);
- transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
-}
-
-/* Free vars used for code hoisting analysis. */
-
-static void
-free_code_hoist_mem (void)
-{
- sbitmap_vector_free (antloc);
- sbitmap_vector_free (transp);
- sbitmap_vector_free (comp);
-
- sbitmap_vector_free (hoist_vbein);
- sbitmap_vector_free (hoist_vbeout);
- sbitmap_vector_free (hoist_exprs);
- sbitmap_vector_free (transpout);
-
- free_dominance_info (CDI_DOMINATORS);
-}
-
-/* Compute the very busy expressions at entry/exit from each block.
-
- An expression is very busy if all paths from a given point
- compute the expression. */
-
-static void
-compute_code_hoist_vbeinout (void)
-{
- int changed, passes;
- basic_block bb;
-
- sbitmap_vector_zero (hoist_vbeout, last_basic_block);
- sbitmap_vector_zero (hoist_vbein, last_basic_block);
-
- passes = 0;
- changed = 1;
-
- while (changed)
- {
- changed = 0;
-
- /* We scan the blocks in the reverse order to speed up
- the convergence. */
- FOR_EACH_BB_REVERSE (bb)
- {
- changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index], antloc[bb->index],
- hoist_vbeout[bb->index], transp[bb->index]);
- if (bb->next_bb != EXIT_BLOCK_PTR)
- sbitmap_intersection_of_succs (hoist_vbeout[bb->index], hoist_vbein, bb->index);
- }
-
- passes++;
- }
-
- if (gcse_file)
- fprintf (gcse_file, "hoisting vbeinout computation: %d passes\n", passes);
-}
-
-/* Top level routine to do the dataflow analysis needed by code hoisting. */
-
-static void
-compute_code_hoist_data (void)
-{
- compute_local_properties (transp, comp, antloc, &expr_hash_table);
- compute_transpout ();
- compute_code_hoist_vbeinout ();
- calculate_dominance_info (CDI_DOMINATORS);
- if (gcse_file)
- fprintf (gcse_file, "\n");
-}
-
-/* Determine if the expression identified by EXPR_INDEX would
- reach BB unimpared if it was placed at the end of EXPR_BB.
-
- It's unclear exactly what Muchnick meant by "unimpared". It seems
- to me that the expression must either be computed or transparent in
- *every* block in the path(s) from EXPR_BB to BB. Any other definition
- would allow the expression to be hoisted out of loops, even if
- the expression wasn't a loop invariant.
-
- Contrast this to reachability for PRE where an expression is
- considered reachable if *any* path reaches instead of *all*
- paths. */
-
-static int
-hoist_expr_reaches_here_p (basic_block expr_bb, int expr_index, basic_block bb, char *visited)
-{
- edge pred;
- int visited_allocated_locally = 0;
-
-
- if (visited == NULL)
- {
- visited_allocated_locally = 1;
- visited = xcalloc (last_basic_block, 1);
- }
-
- for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
- {
- basic_block pred_bb = pred->src;
-
- if (pred->src == ENTRY_BLOCK_PTR)
- break;
- else if (pred_bb == expr_bb)
- continue;
- else if (visited[pred_bb->index])
- continue;
-
- /* Does this predecessor generate this expression? */
- else if (TEST_BIT (comp[pred_bb->index], expr_index))
- break;
- else if (! TEST_BIT (transp[pred_bb->index], expr_index))
- break;
-
- /* Not killed. */
- else
- {
- visited[pred_bb->index] = 1;
- if (! hoist_expr_reaches_here_p (expr_bb, expr_index,
- pred_bb, visited))
- break;
- }
- }
- if (visited_allocated_locally)
- free (visited);
-
- return (pred == NULL);
-}
-\f
-/* Actually perform code hoisting. */
-
-static void
-hoist_code (void)
-{
- basic_block bb, dominated;
- basic_block *domby;
- unsigned int domby_len;
- unsigned int i,j;
- struct expr **index_map;
- struct expr *expr;
-
- sbitmap_vector_zero (hoist_exprs, last_basic_block);
-
- /* Compute a mapping from expression number (`bitmap_index') to
- hash table entry. */
-
- index_map = xcalloc (expr_hash_table.n_elems, sizeof (struct expr *));
- for (i = 0; i < expr_hash_table.size; i++)
- for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
- index_map[expr->bitmap_index] = expr;
-
- /* Walk over each basic block looking for potentially hoistable
- expressions, nothing gets hoisted from the entry block. */
- FOR_EACH_BB (bb)
- {
- int found = 0;
- int insn_inserted_p;
-
- domby_len = get_dominated_by (CDI_DOMINATORS, bb, &domby);
- /* Examine each expression that is very busy at the exit of this
- block. These are the potentially hoistable expressions. */
- for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++)
- {
- int hoistable = 0;
-
- if (TEST_BIT (hoist_vbeout[bb->index], i)
- && TEST_BIT (transpout[bb->index], i))
- {
- /* We've found a potentially hoistable expression, now
- we look at every block BB dominates to see if it
- computes the expression. */
- for (j = 0; j < domby_len; j++)
- {
- dominated = domby[j];
- /* Ignore self dominance. */
- if (bb == dominated)
- continue;
- /* We've found a dominated block, now see if it computes
- the busy expression and whether or not moving that
- expression to the "beginning" of that block is safe. */
- if (!TEST_BIT (antloc[dominated->index], i))
- continue;
-
- /* Note if the expression would reach the dominated block
- unimpared if it was placed at the end of BB.
-
- Keep track of how many times this expression is hoistable
- from a dominated block into BB. */
- if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
- hoistable++;
- }
-
- /* If we found more than one hoistable occurrence of this
- expression, then note it in the bitmap of expressions to
- hoist. It makes no sense to hoist things which are computed
- in only one BB, and doing so tends to pessimize register
- allocation. One could increase this value to try harder
- to avoid any possible code expansion due to register
- allocation issues; however experiments have shown that
- the vast majority of hoistable expressions are only movable
- from two successors, so raising this threshold is likely
- to nullify any benefit we get from code hoisting. */
- if (hoistable > 1)
- {
- SET_BIT (hoist_exprs[bb->index], i);
- found = 1;
- }
- }
- }
- /* If we found nothing to hoist, then quit now. */
- if (! found)
- {
- free (domby);
- continue;
- }
-
- /* Loop over all the hoistable expressions. */
- for (i = 0; i < hoist_exprs[bb->index]->n_bits; i++)
- {
- /* We want to insert the expression into BB only once, so
- note when we've inserted it. */
- insn_inserted_p = 0;
-
- /* These tests should be the same as the tests above. */
- if (TEST_BIT (hoist_vbeout[bb->index], i))
- {
- /* We've found a potentially hoistable expression, now
- we look at every block BB dominates to see if it
- computes the expression. */
- for (j = 0; j < domby_len; j++)
- {
- dominated = domby[j];
- /* Ignore self dominance. */
- if (bb == dominated)
- continue;
-
- /* We've found a dominated block, now see if it computes
- the busy expression and whether or not moving that
- expression to the "beginning" of that block is safe. */
- if (!TEST_BIT (antloc[dominated->index], i))
- continue;
-
- /* The expression is computed in the dominated block and
- it would be safe to compute it at the start of the
- dominated block. Now we have to determine if the
- expression would reach the dominated block if it was
- placed at the end of BB. */
- if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
- {
- struct expr *expr = index_map[i];
- struct occr *occr = expr->antic_occr;
- rtx insn;
- rtx set;
-
- /* Find the right occurrence of this expression. */
- while (BLOCK_FOR_INSN (occr->insn) != dominated && occr)
- occr = occr->next;
-
- /* Should never happen. */
- if (!occr)
- abort ();
-
- insn = occr->insn;
-
- set = single_set (insn);
- if (! set)
- abort ();
-
- /* Create a pseudo-reg to store the result of reaching
- expressions into. Get the mode for the new pseudo
- from the mode of the original destination pseudo. */
- if (expr->reaching_reg == NULL)
- expr->reaching_reg
- = gen_reg_rtx (GET_MODE (SET_DEST (set)));
-
- gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
- delete_insn (insn);
- occr->deleted_p = 1;
- if (!insn_inserted_p)
- {
- insert_insn_end_bb (index_map[i], bb, 0);
- insn_inserted_p = 1;
- }
- }
- }
- }
- }
- free (domby);
- }
-
- free (index_map);
-}
-
-/* Top level routine to perform one code hoisting (aka unification) pass
-
- Return nonzero if a change was made. */
-
-static int
-one_code_hoisting_pass (void)
-{
- int changed = 0;
-
- alloc_hash_table (max_cuid, &expr_hash_table, 0);
- compute_hash_table (&expr_hash_table);
- if (gcse_file)
- dump_hash_table (gcse_file, "Code Hosting Expressions", &expr_hash_table);
-
- if (expr_hash_table.n_elems > 0)
- {
- alloc_code_hoist_mem (last_basic_block, expr_hash_table.n_elems);
- compute_code_hoist_data ();
- hoist_code ();
- free_code_hoist_mem ();
- }
-
- free_hash_table (&expr_hash_table);
-
- return changed;
-}
-\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 (rtx x)
-{
- int do_not_record_p = 0;
- struct ls_expr * ptr;
- unsigned int hash;
-
- hash = hash_expr_1 (x, GET_MODE (x), & do_not_record_p);
-
- for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
- if (ptr->hash_index == hash && expr_equiv_p (ptr->pattern, x))
- return ptr;
-
- ptr = xmalloc (sizeof (struct ls_expr));
-
- ptr->next = pre_ldst_mems;
- ptr->expr = NULL;
- 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;
-
- 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)
-{
- 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)
-{
- 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 (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 (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;
-}
-\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 (rtx x)
-{
- if (GET_CODE (x) != MEM)
- return 0;
-
- if (MEM_VOLATILE_P (x))
- return 0;
-
- if (GET_MODE (x) == BLKmode)
- return 0;
-
- /* 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 (x))
- return 0;
-
- if (side_effects_p (x))
- return 0;
-
- /* Do not consider function arguments passed on stack. */
- if (reg_mentioned_p (stack_pointer_rtx, x))
- return 0;
-
- if (flag_float_store && FLOAT_MODE_P (GET_MODE (x)))
- return 0;
-
- return 1;
-}
-
-/* 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 (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. For a MEM destination, we also
- check that the insn is still valid if we replace the destination with a
- REG, as is done in update_ld_motion_stores. If there are any uses/defs
- which don't match this criteria, they are invalidated and trimmed out
- later. */
-
-static void
-compute_ld_motion_mems (void)
-{
- struct ls_expr * ptr;
- basic_block bb;
- rtx insn;
-
- pre_ldst_mems = NULL;
-
- FOR_EACH_BB (bb)
- {
- for (insn = BB_HEAD (bb);
- insn && insn != NEXT_INSN (BB_END (bb));
- insn = NEXT_INSN (insn))
- {
- if (INSN_P (insn))
- {
- 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
- /* Check for REG manually since want_to_gcse_p
- returns 0 for all REGs. */
- && (REG_P (src) || want_to_gcse_p (src)))
- 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 (void)
-{
- struct ls_expr * * last = & pre_ldst_mems;
- struct ls_expr * ptr = pre_ldst_mems;
-
- while (ptr != NULL)
- {
- struct expr * expr;
-
- /* Delete if entry has been made invalid. */
- if (! ptr->invalid)
- {
- /* Delete if we cannot find this mem in the expression list. */
- unsigned int hash = ptr->hash_index % expr_hash_table.size;
-
- for (expr = expr_hash_table.table[hash];
- expr != NULL;
- expr = expr->next_same_hash)
- if (expr_equiv_p (expr->expr, ptr->pattern))
- break;
- }
- else
- expr = (struct expr *) 0;
-
- if (expr)
- {
- /* Set the expression field if we are keeping it. */
- ptr->expr = expr;
- last = & ptr->next;
- ptr = ptr->next;
- }
- else
- {
- *last = ptr->next;
- free_ldst_entry (ptr);
- ptr = * last;
- }
- }
-
- /* 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 storing
- 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 (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. We checked in
- compute_ld_motion_mems that we can replace (set mem expr) with
- (set reg expr) in that insn. */
- 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, copy_rtx (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. */
-
-#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, rtx setter ATTRIBUTE_UNUSED,
- void *data)
-{
- sbitmap bb_reg = data;
-
- if (GET_CODE (dest) == SUBREG)
- dest = SUBREG_REG (dest);
-
- if (GET_CODE (dest) == REG)
- {
- regvec[REGNO (dest)] = INSN_UID (compute_store_table_current_insn);
- if (bb_reg)
- SET_BIT (bb_reg, REGNO (dest));
- }
-}
-
-/* Clear any mark that says that this insn sets dest. Called from
- note_stores. */
-
-static void
-reg_clear_last_set (rtx dest, rtx setter ATTRIBUTE_UNUSED,
- void *data)
-{
- int *dead_vec = data;
-
- if (GET_CODE (dest) == SUBREG)
- dest = SUBREG_REG (dest);
-
- if (GET_CODE (dest) == REG &&
- 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 (rtx x, int *regs_set)
-{
- rtx reg;
-
- for (; x; x = XEXP (x, 1))
- {
- reg = XEXP (x, 0);
- if (regs_set[REGNO(reg)])
- return false;
- }
-
- 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;
-
- /* 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 POST_DEC:
- case POST_INC:
- /* We do not run this function with arguments having side effects. */
- abort ();
-
- case PC:
- case CC0: /*FIXME*/
- case CONST:
- case CONST_INT:
- case CONST_DOUBLE:
- 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;
-}
-
-/* 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 (GET_CODE (dest) != MEM || 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;
-
- 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;