- if (new == pc_rtx)
- {
- edest = FALLTHRU_EDGE (bb);
- dest = edest->insns.r ? NULL : edest->dest;
- }
- else if (GET_CODE (new) == LABEL_REF)
- {
- dest = BLOCK_FOR_INSN (XEXP (new, 0));
- /* Don't bypass edges containing instructions. */
- edest = find_edge (bb, dest);
- if (edest && edest->insns.r)
- dest = NULL;
- }
- else
- dest = NULL;
-
- /* Avoid unification of the edge with other edges from original
- branch. We would end up emitting the instruction on "both"
- edges. */
-
- if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))
- && find_edge (e->src, dest))
- dest = NULL;
-
- old_dest = e->dest;
- if (dest != NULL
- && dest != old_dest
- && dest != EXIT_BLOCK_PTR)
- {
- redirect_edge_and_branch_force (e, dest);
-
- /* Copy the register setter to the redirected edge.
- Don't copy CC0 setters, as CC0 is dead after jump. */
- if (setcc)
- {
- rtx pat = PATTERN (setcc);
- if (!CC0_P (SET_DEST (pat)))
- insert_insn_on_edge (copy_insn (pat), e);
- }
-
- if (dump_file != NULL)
- {
- fprintf (dump_file, "JUMP-BYPASS: Proved reg %d "
- "in jump_insn %d equals constant ",
- regno, INSN_UID (jump));
- print_rtl (dump_file, SET_SRC (set->expr));
- fprintf (dump_file, "\nBypass edge from %d->%d to %d\n",
- e->src->index, old_dest->index, dest->index);
- }
- change = 1;
- removed_p = 1;
- break;
- }
- }
- if (!removed_p)
- ei_next (&ei);
- }
- return change;
-}
-
-/* Find basic blocks with more than one predecessor that only contain a
- single conditional jump. If the result of the comparison is known at
- compile-time from any incoming edge, redirect that edge to the
- appropriate target. Returns nonzero if a change was made.
-
- This function is now mis-named, because we also handle indirect jumps. */
-
-static int
-bypass_conditional_jumps (void)
-{
- basic_block bb;
- int changed;
- rtx setcc;
- rtx insn;
- rtx dest;
-
- /* Note we start at block 1. */
- if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
- return 0;
-
- bypass_last_basic_block = last_basic_block;
- mark_dfs_back_edges ();
-
- changed = 0;
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb,
- EXIT_BLOCK_PTR, next_bb)
- {
- /* Check for more than one predecessor. */
- if (!single_pred_p (bb))
- {
- setcc = NULL_RTX;
- FOR_BB_INSNS (bb, insn)
- if (NONJUMP_INSN_P (insn))
- {
- if (setcc)
- break;
- if (GET_CODE (PATTERN (insn)) != SET)
- break;
-
- dest = SET_DEST (PATTERN (insn));
- if (REG_P (dest) || CC0_P (dest))
- setcc = insn;
- else
- break;
- }
- else if (JUMP_P (insn))
- {
- if ((any_condjump_p (insn) || computed_jump_p (insn))
- && onlyjump_p (insn))
- changed |= bypass_block (bb, setcc, insn);
- break;
- }
- else if (INSN_P (insn))
- break;
- }
- }
-
- /* If we bypassed any register setting insns, we inserted a
- copy on the redirected edge. These need to be committed. */
- if (changed)
- commit_edge_insertions ();
-
- return changed;
-}
-\f
-/* Compute PRE+LCM working variables. */
-
-/* Local properties of expressions. */
-/* Nonzero for expressions that are transparent in the block. */
-static sbitmap *transp;
-
-/* Nonzero for expressions that are transparent at the end of the block.
- This is only zero for expressions killed by abnormal critical edge
- created by a calls. */
-static sbitmap *transpout;
-
-/* Nonzero for expressions that are computed (available) in the block. */
-static sbitmap *comp;
-
-/* Nonzero for expressions that are locally anticipatable in the block. */
-static sbitmap *antloc;
-
-/* Nonzero for expressions where this block is an optimal computation
- point. */
-static sbitmap *pre_optimal;
-
-/* Nonzero for expressions which are redundant in a particular block. */
-static sbitmap *pre_redundant;
-
-/* 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;
-
-/* Redundant insns. */
-static sbitmap pre_redundant_insns;
-
-/* Allocate vars used for PRE analysis. */
-
-static void
-alloc_pre_mem (int n_blocks, int n_exprs)
-{
- transp = sbitmap_vector_alloc (n_blocks, n_exprs);
- comp = sbitmap_vector_alloc (n_blocks, n_exprs);
- antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
-
- pre_optimal = NULL;
- pre_redundant = NULL;
- pre_insert_map = NULL;
- pre_delete_map = NULL;
- ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs);
-
- /* pre_insert and pre_delete are allocated later. */
-}
-
-/* Free vars used for PRE analysis. */
-
-static void
-free_pre_mem (void)
-{
- sbitmap_vector_free (transp);
- sbitmap_vector_free (comp);
-
- /* ANTLOC and AE_KILL are freed just after pre_lcm finishes. */
-
- if (pre_optimal)
- sbitmap_vector_free (pre_optimal);
- if (pre_redundant)
- sbitmap_vector_free (pre_redundant);
- if (pre_insert_map)
- sbitmap_vector_free (pre_insert_map);
- if (pre_delete_map)
- sbitmap_vector_free (pre_delete_map);
-
- transp = comp = NULL;
- pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL;
-}
-
-/* Top level routine to do the dataflow analysis needed by PRE. */
-
-static void
-compute_pre_data (void)
-{
- sbitmap trapping_expr;
- basic_block bb;
- unsigned int ui;
-
- compute_local_properties (transp, comp, antloc, &expr_hash_table);
- sbitmap_vector_zero (ae_kill, last_basic_block);
-
- /* Collect expressions which might trap. */
- trapping_expr = sbitmap_alloc (expr_hash_table.n_elems);
- sbitmap_zero (trapping_expr);
- for (ui = 0; ui < expr_hash_table.size; ui++)
- {
- struct expr *e;
- for (e = expr_hash_table.table[ui]; e != NULL; e = e->next_same_hash)
- if (may_trap_p (e->expr))
- SET_BIT (trapping_expr, e->bitmap_index);
- }
-
- /* Compute ae_kill for each basic block using:
-
- ~(TRANSP | COMP)
- */
-
- FOR_EACH_BB (bb)
- {
- edge e;
- edge_iterator ei;
-
- /* If the current block is the destination of an abnormal edge, we
- kill all trapping expressions because we won't be able to properly
- place the instruction on the edge. So make them neither
- anticipatable nor transparent. This is fairly conservative. */
- FOR_EACH_EDGE (e, ei, bb->preds)
- if (e->flags & EDGE_ABNORMAL)
- {
- sbitmap_difference (antloc[bb->index], antloc[bb->index], trapping_expr);
- sbitmap_difference (transp[bb->index], transp[bb->index], trapping_expr);
- break;
- }
-
- sbitmap_a_or_b (ae_kill[bb->index], transp[bb->index], comp[bb->index]);
- sbitmap_not (ae_kill[bb->index], ae_kill[bb->index]);
- }
-
- edge_list = pre_edge_lcm (expr_hash_table.n_elems, transp, comp, antloc,
- ae_kill, &pre_insert_map, &pre_delete_map);
- sbitmap_vector_free (antloc);
- antloc = NULL;
- sbitmap_vector_free (ae_kill);
- ae_kill = NULL;
- sbitmap_free (trapping_expr);
-}
-\f
-/* PRE utilities */
-
-/* Return nonzero if an occurrence of expression EXPR in OCCR_BB would reach
- block BB.
-
- VISITED is a pointer to a working buffer for tracking which BB's have
- been visited. It is NULL for the top-level call.
-
- We treat reaching expressions that go through blocks containing the same
- reaching expression as "not reaching". E.g. if EXPR is generated in blocks
- 2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
- 2 as not reaching. The intent is to improve the probability of finding
- only one reaching expression and to reduce register lifetimes by picking
- the closest such expression. */
-
-static int
-pre_expr_reaches_here_p_work (basic_block occr_bb, struct expr *expr, basic_block bb, char *visited)
-{
- edge pred;
- edge_iterator ei;
-
- FOR_EACH_EDGE (pred, ei, bb->preds)
- {
- basic_block pred_bb = pred->src;
-
- if (pred->src == ENTRY_BLOCK_PTR
- /* Has predecessor has already been visited? */
- || visited[pred_bb->index])
- ;/* Nothing to do. */
-
- /* Does this predecessor generate this expression? */
- else if (TEST_BIT (comp[pred_bb->index], expr->bitmap_index))
- {
- /* Is this the occurrence we're looking for?
- Note that there's only one generating occurrence per block
- so we just need to check the block number. */
- if (occr_bb == pred_bb)
- return 1;
-
- visited[pred_bb->index] = 1;
- }
- /* Ignore this predecessor if it kills the expression. */
- else if (! TEST_BIT (transp[pred_bb->index], expr->bitmap_index))
- visited[pred_bb->index] = 1;
-
- /* Neither gen nor kill. */
- else
- {
- visited[pred_bb->index] = 1;
- if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb, visited))
- return 1;
- }
- }
-
- /* All paths have been checked. */
- return 0;
-}
-
-/* The wrapper for pre_expr_reaches_here_work that ensures that any
- memory allocated for that function is returned. */
-
-static int
-pre_expr_reaches_here_p (basic_block occr_bb, struct expr *expr, basic_block bb)
-{
- int rval;
- char *visited = XCNEWVEC (char, last_basic_block);
-
- rval = pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited);
-
- free (visited);
- return rval;
-}
-\f
-
-/* Given an expr, generate RTL which we can insert at the end of a BB,
- or on an edge. Set the block number of any insns generated to
- the value of BB. */
-
-static rtx
-process_insert_insn (struct expr *expr)
-{
- rtx reg = expr->reaching_reg;
- rtx exp = copy_rtx (expr->expr);
- rtx pat;
-
- start_sequence ();
-
- /* If the expression is something that's an operand, like a constant,
- just copy it to a register. */
- if (general_operand (exp, GET_MODE (reg)))
- emit_move_insn (reg, exp);
-
- /* Otherwise, make a new insn to compute this expression and make sure the
- insn will be recognized (this also adds any needed CLOBBERs). Copy the
- expression to make sure we don't have any sharing issues. */
- else
- {
- rtx insn = emit_insn (gen_rtx_SET (VOIDmode, reg, exp));
-
- if (insn_invalid_p (insn))
- gcc_unreachable ();
- }
-
-
- pat = get_insns ();
- end_sequence ();
-
- return pat;
-}
-
-/* Add EXPR to the end of basic block BB.
-
- This is used by both the PRE and code hoisting.
-
- For PRE, we want to verify that the expr is either transparent
- or locally anticipatable in the target block. This check makes
- no sense for code hoisting. */
-
-static void
-insert_insn_end_basic_block (struct expr *expr, basic_block bb, int pre)
-{
- rtx insn = BB_END (bb);
- rtx new_insn;
- rtx reg = expr->reaching_reg;
- int regno = REGNO (reg);
- rtx pat, pat_end;
-
- pat = process_insert_insn (expr);
- gcc_assert (pat && INSN_P (pat));
-
- pat_end = pat;
- while (NEXT_INSN (pat_end) != NULL_RTX)
- pat_end = NEXT_INSN (pat_end);
-
- /* If the last insn is a jump, insert EXPR in front [taking care to
- handle cc0, etc. properly]. Similarly we need to care trapping
- instructions in presence of non-call exceptions. */
-
- if (JUMP_P (insn)
- || (NONJUMP_INSN_P (insn)
- && (!single_succ_p (bb)
- || single_succ_edge (bb)->flags & EDGE_ABNORMAL)))
- {
-#ifdef HAVE_cc0
- rtx note;
-#endif
- /* It should always be the case that we can put these instructions
- anywhere in the basic block with performing PRE optimizations.
- Check this. */
- gcc_assert (!NONJUMP_INSN_P (insn) || !pre
- || TEST_BIT (antloc[bb->index], expr->bitmap_index)
- || TEST_BIT (transp[bb->index], expr->bitmap_index));
-
- /* If this is a jump table, then we can't insert stuff here. Since
- we know the previous real insn must be the tablejump, we insert
- the new instruction just before the tablejump. */
- if (GET_CODE (PATTERN (insn)) == ADDR_VEC
- || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
- insn = prev_real_insn (insn);
-
-#ifdef HAVE_cc0
- /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
- if cc0 isn't set. */
- note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
- if (note)
- insn = XEXP (note, 0);
- else
- {
- rtx maybe_cc0_setter = prev_nonnote_insn (insn);
- if (maybe_cc0_setter
- && INSN_P (maybe_cc0_setter)
- && sets_cc0_p (PATTERN (maybe_cc0_setter)))
- insn = maybe_cc0_setter;
- }
-#endif
- /* FIXME: What if something in cc0/jump uses value set in new insn? */
- new_insn = emit_insn_before_noloc (pat, insn, bb);
- }
-
- /* Likewise if the last insn is a call, as will happen in the presence
- of exception handling. */
- else if (CALL_P (insn)
- && (!single_succ_p (bb)
- || single_succ_edge (bb)->flags & EDGE_ABNORMAL))
- {
- /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
- we search backward and place the instructions before the first
- parameter is loaded. Do this for everyone for consistency and a
- presumption that we'll get better code elsewhere as well.
-
- It should always be the case that we can put these instructions
- anywhere in the basic block with performing PRE optimizations.
- Check this. */
-
- gcc_assert (!pre
- || TEST_BIT (antloc[bb->index], expr->bitmap_index)
- || TEST_BIT (transp[bb->index], expr->bitmap_index));
-
- /* Since different machines initialize their parameter registers
- in different orders, assume nothing. Collect the set of all
- parameter registers. */
- insn = find_first_parameter_load (insn, BB_HEAD (bb));
-
- /* If we found all the parameter loads, then we want to insert
- before the first parameter load.
-
- If we did not find all the parameter loads, then we might have
- stopped on the head of the block, which could be a CODE_LABEL.
- If we inserted before the CODE_LABEL, then we would be putting
- the insn in the wrong basic block. In that case, put the insn
- after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
- while (LABEL_P (insn)
- || NOTE_INSN_BASIC_BLOCK_P (insn))
- insn = NEXT_INSN (insn);
-
- new_insn = emit_insn_before_noloc (pat, insn, bb);
- }
- else
- new_insn = emit_insn_after_noloc (pat, insn, bb);
-
- while (1)
- {
- if (INSN_P (pat))
- {
- add_label_notes (PATTERN (pat), new_insn);
- note_stores (PATTERN (pat), record_set_info, pat);
- }
- if (pat == pat_end)
- break;
- pat = NEXT_INSN (pat);
- }
-
- gcse_create_count++;
-
- if (dump_file)
- {
- fprintf (dump_file, "PRE/HOIST: end of bb %d, insn %d, ",
- bb->index, INSN_UID (new_insn));
- fprintf (dump_file, "copying expression %d to reg %d\n",
- expr->bitmap_index, regno);
- }
-}
-
-/* Insert partially redundant expressions on edges in the CFG to make
- the expressions fully redundant. */
-
-static int
-pre_edge_insert (struct edge_list *edge_list, struct expr **index_map)
-{
- int e, i, j, num_edges, set_size, did_insert = 0;
- sbitmap *inserted;
-
- /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge
- if it reaches any of the deleted expressions. */
-
- set_size = pre_insert_map[0]->size;
- num_edges = NUM_EDGES (edge_list);
- inserted = sbitmap_vector_alloc (num_edges, expr_hash_table.n_elems);
- sbitmap_vector_zero (inserted, num_edges);
-
- for (e = 0; e < num_edges; e++)
- {
- int indx;
- basic_block bb = INDEX_EDGE_PRED_BB (edge_list, e);
-
- for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
- {
- SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i];
-
- for (j = indx; insert && j < (int) expr_hash_table.n_elems; j++, insert >>= 1)
- if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX)
- {
- struct expr *expr = index_map[j];
- struct occr *occr;
-
- /* Now look at each deleted occurrence of this expression. */
- for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
- {
- if (! occr->deleted_p)
- continue;
-
- /* Insert this expression on this edge if it would
- reach the deleted occurrence in BB. */
- if (!TEST_BIT (inserted[e], j))
- {
- rtx insn;
- edge eg = INDEX_EDGE (edge_list, e);
-
- /* We can't insert anything on an abnormal and
- critical edge, so we insert the insn at the end of
- the previous block. There are several alternatives
- detailed in Morgans book P277 (sec 10.5) for
- handling this situation. This one is easiest for
- now. */
-
- if (eg->flags & EDGE_ABNORMAL)
- insert_insn_end_basic_block (index_map[j], bb, 0);
- else
- {
- insn = process_insert_insn (index_map[j]);
- insert_insn_on_edge (insn, eg);
- }
-
- if (dump_file)
- {
- fprintf (dump_file, "PRE/HOIST: edge (%d,%d), ",
- bb->index,
- INDEX_EDGE_SUCC_BB (edge_list, e)->index);
- fprintf (dump_file, "copy expression %d\n",
- expr->bitmap_index);
- }
-
- update_ld_motion_stores (expr);
- SET_BIT (inserted[e], j);
- did_insert = 1;
- gcse_create_count++;
- }
- }
- }
- }
- }
-
- sbitmap_vector_free (inserted);
- return did_insert;
-}
-
-/* Copy the result of EXPR->EXPR generated by INSN to EXPR->REACHING_REG.
- Given "old_reg <- expr" (INSN), instead of adding after it
- reaching_reg <- old_reg
- it's better to do the following:
- reaching_reg <- expr
- old_reg <- reaching_reg
- because this way copy propagation can discover additional PRE
- opportunities. But if this fails, we try the old way.
- When "expr" is a store, i.e.
- given "MEM <- old_reg", instead of adding after it
- reaching_reg <- old_reg
- it's better to add it before as follows:
- reaching_reg <- old_reg
- MEM <- reaching_reg. */
-
-static void
-pre_insert_copy_insn (struct expr *expr, rtx insn)
-{
- rtx reg = expr->reaching_reg;
- int regno = REGNO (reg);
- int indx = expr->bitmap_index;
- rtx pat = PATTERN (insn);
- rtx set, first_set, new_insn;
- rtx old_reg;
- int i;
-
- /* This block matches the logic in hash_scan_insn. */
- switch (GET_CODE (pat))
- {
- case SET:
- set = pat;
- break;
-
- case PARALLEL:
- /* Search through the parallel looking for the set whose
- source was the expression that we're interested in. */
- first_set = NULL_RTX;
- set = NULL_RTX;
- for (i = 0; i < XVECLEN (pat, 0); i++)
- {
- rtx x = XVECEXP (pat, 0, i);
- if (GET_CODE (x) == SET)
- {
- /* If the source was a REG_EQUAL or REG_EQUIV note, we
- may not find an equivalent expression, but in this
- case the PARALLEL will have a single set. */
- if (first_set == NULL_RTX)
- first_set = x;
- if (expr_equiv_p (SET_SRC (x), expr->expr))
- {
- set = x;
- break;
- }
- }
- }
-
- gcc_assert (first_set);
- if (set == NULL_RTX)
- set = first_set;
- break;
-
- default:
- gcc_unreachable ();
- }
-
- if (REG_P (SET_DEST (set)))
- {
- old_reg = SET_DEST (set);
- /* Check if we can modify the set destination in the original insn. */
- if (validate_change (insn, &SET_DEST (set), reg, 0))
- {
- new_insn = gen_move_insn (old_reg, reg);
- new_insn = emit_insn_after (new_insn, insn);
-
- /* Keep register set table up to date. */
- record_one_set (regno, insn);
- }
- else
- {
- new_insn = gen_move_insn (reg, old_reg);
- new_insn = emit_insn_after (new_insn, insn);
-
- /* Keep register set table up to date. */
- record_one_set (regno, new_insn);
- }
- }
- else /* This is possible only in case of a store to memory. */
- {
- old_reg = SET_SRC (set);
- new_insn = gen_move_insn (reg, old_reg);
-
- /* Check if we can modify the set source in the original insn. */
- if (validate_change (insn, &SET_SRC (set), reg, 0))
- new_insn = emit_insn_before (new_insn, insn);
- else
- new_insn = emit_insn_after (new_insn, insn);
-
- /* Keep register set table up to date. */
- record_one_set (regno, new_insn);
- }
-
- gcse_create_count++;
-
- if (dump_file)
- fprintf (dump_file,
- "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n",
- BLOCK_NUM (insn), INSN_UID (new_insn), indx,
- INSN_UID (insn), regno);
-}
-
-/* Copy available expressions that reach the redundant expression
- to `reaching_reg'. */
-
-static void
-pre_insert_copies (void)
-{
- unsigned int i, added_copy;
- struct expr *expr;
- struct occr *occr;
- struct occr *avail;
-
- /* For each available expression in the table, copy the result to
- `reaching_reg' if the expression reaches a deleted one.
-
- ??? The current algorithm is rather brute force.
- Need to do some profiling. */
-
- for (i = 0; i < expr_hash_table.size; i++)
- for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
- {
- /* If the basic block isn't reachable, PPOUT will be TRUE. However,
- we don't want to insert a copy here because the expression may not
- really be redundant. So only insert an insn if the expression was
- deleted. This test also avoids further processing if the
- expression wasn't deleted anywhere. */
- if (expr->reaching_reg == NULL)
- continue;
-
- /* Set when we add a copy for that expression. */
- added_copy = 0;
-
- for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
- {
- if (! occr->deleted_p)
- continue;
-
- for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
- {
- rtx insn = avail->insn;
-
- /* No need to handle this one if handled already. */
- if (avail->copied_p)
- continue;
-
- /* Don't handle this one if it's a redundant one. */
- if (TEST_BIT (pre_redundant_insns, INSN_CUID (insn)))
- continue;
-
- /* Or if the expression doesn't reach the deleted one. */
- if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail->insn),
- expr,
- BLOCK_FOR_INSN (occr->insn)))
- continue;
-
- added_copy = 1;
-
- /* Copy the result of avail to reaching_reg. */
- pre_insert_copy_insn (expr, insn);
- avail->copied_p = 1;
- }
- }
-
- if (added_copy)
- update_ld_motion_stores (expr);
- }
-}
-
-/* Emit move from SRC to DEST noting the equivalence with expression computed
- in INSN. */
-static rtx
-gcse_emit_move_after (rtx src, rtx dest, rtx insn)
-{
- rtx new;
- rtx set = single_set (insn), set2;
- rtx note;
- rtx eqv;
-
- /* This should never fail since we're creating a reg->reg copy
- we've verified to be valid. */
-
- new = emit_insn_after (gen_move_insn (dest, src), insn);
-
- /* Note the equivalence for local CSE pass. */
- set2 = single_set (new);
- if (!set2 || !rtx_equal_p (SET_DEST (set2), dest))
- return new;
- if ((note = find_reg_equal_equiv_note (insn)))
- eqv = XEXP (note, 0);
- else
- eqv = SET_SRC (set);
-
- set_unique_reg_note (new, REG_EQUAL, copy_insn_1 (eqv));
-
- return new;
-}
-
-/* Delete redundant computations.
- Deletion is done by changing the insn to copy the `reaching_reg' of
- the expression into the result of the SET. It is left to later passes
- (cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it.
-
- Returns nonzero if a change is made. */
-
-static int
-pre_delete (void)
-{
- unsigned int i;
- int changed;
- struct expr *expr;
- struct occr *occr;
-
- changed = 0;
- for (i = 0; i < expr_hash_table.size; i++)
- for (expr = expr_hash_table.table[i];
- expr != NULL;
- expr = expr->next_same_hash)
- {
- int indx = expr->bitmap_index;
-
- /* We only need to search antic_occr since we require
- ANTLOC != 0. */
-
- for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
- {
- rtx insn = occr->insn;
- rtx set;
- basic_block bb = BLOCK_FOR_INSN (insn);
-
- /* We only delete insns that have a single_set. */
- if (TEST_BIT (pre_delete_map[bb->index], indx)
- && (set = single_set (insn)) != 0
- && dbg_cnt (pre_insn))
- {
- /* 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;
- SET_BIT (pre_redundant_insns, INSN_CUID (insn));
- changed = 1;
- gcse_subst_count++;
-
- if (dump_file)
- {
- fprintf (dump_file,
- "PRE: redundant insn %d (expression %d) in ",
- INSN_UID (insn), indx);
- fprintf (dump_file, "bb %d, reaching reg is %d\n",
- bb->index, REGNO (expr->reaching_reg));
- }
- }
- }
- }
-
- return changed;
-}
-
-/* Perform GCSE optimizations using PRE.
- This is called by one_pre_gcse_pass after all the dataflow analysis
- has been done.
-
- This is based on the original Morel-Renvoise paper Fred Chow's thesis, and
- lazy code motion from Knoop, Ruthing and Steffen as described in Advanced
- Compiler Design and Implementation.
-
- ??? A new pseudo reg is created to hold the reaching expression. The nice
- thing about the classical approach is that it would try to use an existing
- reg. If the register can't be adequately optimized [i.e. we introduce
- reload problems], one could add a pass here to propagate the new register
- through the block.
-
- ??? We don't handle single sets in PARALLELs because we're [currently] not
- able to copy the rest of the parallel when we insert copies to create full
- redundancies from partial redundancies. However, there's no reason why we
- can't handle PARALLELs in the cases where there are no partial
- redundancies. */
-
-static int
-pre_gcse (void)
-{
- unsigned int i;
- int did_insert, changed;
- struct expr **index_map;
- struct expr *expr;
-
- /* Compute a mapping from expression number (`bitmap_index') to
- hash table entry. */
-
- index_map = XCNEWVEC (struct expr *, expr_hash_table.n_elems);
- 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;
-
- /* Reset bitmap used to track which insns are redundant. */
- pre_redundant_insns = sbitmap_alloc (max_cuid);
- sbitmap_zero (pre_redundant_insns);
-
- /* Delete the redundant insns first so that
- - we know what register to use for the new insns and for the other
- ones with reaching expressions
- - we know which insns are redundant when we go to create copies */
-
- changed = pre_delete ();
- did_insert = pre_edge_insert (edge_list, index_map);
-
- /* In other places with reaching expressions, copy the expression to the
- specially allocated pseudo-reg that reaches the redundant expr. */
- pre_insert_copies ();
- if (did_insert)
- {
- commit_edge_insertions ();
- changed = 1;
- }
-
- free (index_map);
- sbitmap_free (pre_redundant_insns);
- return changed;
-}
-
-/* Top level routine to perform one PRE GCSE pass.
-
- Return nonzero if a change was made. */
-
-static int
-one_pre_gcse_pass (int pass)
-{
- int changed = 0;
-
- gcse_subst_count = 0;
- gcse_create_count = 0;
-
- alloc_hash_table (max_cuid, &expr_hash_table, 0);
- add_noreturn_fake_exit_edges ();
- if (flag_gcse_lm)
- compute_ld_motion_mems ();
-
- compute_hash_table (&expr_hash_table);
- trim_ld_motion_mems ();
- if (dump_file)
- dump_hash_table (dump_file, "Expression", &expr_hash_table);
-
- if (expr_hash_table.n_elems > 0)
- {
- alloc_pre_mem (last_basic_block, expr_hash_table.n_elems);
- compute_pre_data ();
- changed |= pre_gcse ();
- free_edge_list (edge_list);
- free_pre_mem ();
- }
-
- free_ldst_mems ();
- remove_fake_exit_edges ();
- free_hash_table (&expr_hash_table);
-
- if (dump_file)
- {
- fprintf (dump_file, "\nPRE GCSE of %s, pass %d: %d bytes needed, ",
- current_function_name (), pass, bytes_used);
- fprintf (dump_file, "%d substs, %d insns created\n",
- gcse_subst_count, gcse_create_count);
- }
-
- return changed;
-}
-\f
-/* If X contains any LABEL_REF's, add REG_LABEL_OPERAND notes for them
- to INSN. If such notes are added to an insn which references a
- CODE_LABEL, the LABEL_NUSES count is incremented. We have to add
- that note, because the following loop optimization pass requires
- them. */
-
-/* ??? If there was a jump optimization pass after gcse and before loop,
- then we would not need to do this here, because jump would add the
- necessary REG_LABEL_OPERAND and REG_LABEL_TARGET notes. */
-
-static void
-add_label_notes (rtx x, rtx insn)
-{
- enum rtx_code code = GET_CODE (x);
- int i, j;
- const char *fmt;
-
- if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
- {
- /* This code used to ignore labels that referred to dispatch tables to
- avoid flow generating (slightly) worse code.
-
- We no longer ignore such label references (see LABEL_REF handling in
- mark_jump_label for additional information). */
-
- if (reg_mentioned_p (XEXP (x, 0), insn))
- {
- /* There's no reason for current users to emit jump-insns
- with such a LABEL_REF, so we don't have to handle
- REG_LABEL_TARGET notes. */
- gcc_assert (!JUMP_P (insn));
- REG_NOTES (insn)
- = gen_rtx_INSN_LIST (REG_LABEL_OPERAND, XEXP (x, 0),
- REG_NOTES (insn));
- if (LABEL_P (XEXP (x, 0)))
- LABEL_NUSES (XEXP (x, 0))++;
- }
- return;
- }
-
- for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
- {
- if (fmt[i] == 'e')
- add_label_notes (XEXP (x, i), insn);
- else if (fmt[i] == 'E')
- for (j = XVECLEN (x, i) - 1; j >= 0; j--)
- add_label_notes (XVECEXP (x, i, j), insn);
- }
-}
-
-/* Compute transparent outgoing information for each block.
-
- An expression is transparent to an edge unless it is killed by
- the edge itself. This can only happen with abnormal control flow,
- when the edge is traversed through a call. This happens with
- non-local labels and exceptions.
-
- This would not be necessary if we split the edge. While this is
- normally impossible for abnormal critical edges, with some effort
- it should be possible with exception handling, since we still have
- control over which handler should be invoked. But due to increased
- EH table sizes, this may not be worthwhile. */
-
-static void
-compute_transpout (void)
-{
- basic_block bb;
- unsigned int i;
- struct expr *expr;
-
- sbitmap_vector_ones (transpout, last_basic_block);
-
- FOR_EACH_BB (bb)
- {
- /* Note that flow inserted a nop a the end of basic blocks that
- end in call instructions for reasons other than abnormal
- control flow. */
- if (! CALL_P (BB_END (bb)))
- continue;
-
- for (i = 0; i < expr_hash_table.size; i++)
- for (expr = expr_hash_table.table[i]; expr ; expr = expr->next_same_hash)
- if (MEM_P (expr->expr))
- {
- if (GET_CODE (XEXP (expr->expr, 0)) == SYMBOL_REF
- && CONSTANT_POOL_ADDRESS_P (XEXP (expr->expr, 0)))
- continue;
-
- /* ??? Optimally, we would use interprocedural alias
- analysis to determine if this mem is actually killed
- by this call. */
- RESET_BIT (transpout[bb->index], expr->bitmap_index);
- }
- }
-}
-
-/* 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 (dump_file)
- fprintf (dump_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 (dump_file)
- fprintf (dump_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;
- edge_iterator ei;
- int visited_allocated_locally = 0;
-
-
- if (visited == NULL)
- {
- visited_allocated_locally = 1;
- visited = XCNEWVEC (char, last_basic_block);
- }
-
- FOR_EACH_EDGE (pred, ei, bb->preds)
- {
- 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;
- VEC (basic_block, heap) *domby;
- 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 = XCNEWVEC (struct expr *, expr_hash_table.n_elems);
- 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 = get_dominated_by (CDI_DOMINATORS, bb);
- /* 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; VEC_iterate (basic_block, domby, j, dominated); 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)
- {
- VEC_free (basic_block, heap, 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_exprs[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; VEC_iterate (basic_block, domby, j, dominated); 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;
-
- gcc_assert (occr);
- insn = occr->insn;
- set = single_set (insn);
- gcc_assert (set);
-
- /* 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_basic_block (index_map[i], bb, 0);
- insn_inserted_p = 1;
- }
- }
- }
- }
- }
- VEC_free (basic_block, heap, 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 (dump_file)
- dump_hash_table (dump_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. */
-
-static hashval_t
-pre_ldst_expr_hash (const void *p)
-{
- int do_not_record_p = 0;
- const struct ls_expr *x = 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 *ptr1 = p1, *ptr2 = p2;
- return expr_equiv_p (ptr1->pattern, ptr2->pattern);
-}
-
-/* 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->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;
- *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;
-}
-
-/* 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 e;
- void **slot;
- if (!pre_ldst_table)
- return NULL;
- e.pattern = x;
- slot = htab_find_slot (pre_ldst_table, &e, NO_INSERT);
- if (!slot || ((struct ls_expr *)*slot)->invalid)
- return NULL;
- return *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 *
-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 (const_rtx x)
-{
- if (! MEM_P (x))
- 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 (MEM_P (x) && 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;
- pre_ldst_table = htab_create (13, pre_ldst_expr_hash,
- pre_ldst_expr_eq, NULL);
-
- FOR_EACH_BB (bb)
- {
- FOR_BB_INSNS (bb, 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 (MEM_P (src) && simple_mem (src))
- {
- ptr = ldst_entry (src);
- if (REG_P (dest))
- 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 (MEM_P (dest) && simple_mem (dest))
- {
- ptr = ldst_entry (dest);
-
- if (! MEM_P (src)
- && 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))
- 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;