/* Global common subexpression elimination/Partial redundancy elimination
and global constant/copy propagation for GNU compiler.
- Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
+ Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
Free Software Foundation, Inc.
This file is part of GCC.
\f
/* For available exprs */
static sbitmap *ae_kill, *ae_gen;
-
-/* Objects of this type are passed around by the null-pointer check
- removal routines. */
-struct null_pointer_info
-{
- /* The basic block being processed. */
- basic_block current_block;
- /* The first register to be handled in this pass. */
- unsigned int min_reg;
- /* One greater than the last register to be handled in this pass. */
- unsigned int max_reg;
- sbitmap *nonnull_local;
- sbitmap *nonnull_killed;
-};
\f
static void compute_can_copy (void);
static void *gmalloc (size_t) ATTRIBUTE_MALLOC;
\f
/* Entry point for global common subexpression elimination.
- F is the first instruction in the function. */
+ F is the first instruction in the function. Return nonzero if a
+ change is mode. */
int
gcse_main (rtx f, FILE *file)
{
while (GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT
- || GET_CODE (dest) == SIGN_EXTRACT
|| GET_CODE (dest) == STRICT_LOW_PART)
dest = XEXP (dest, 0);
while (GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT
- || GET_CODE (dest) == SIGN_EXTRACT
|| GET_CODE (dest) == STRICT_LOW_PART)
dest = XEXP (dest, 0);
if (CALL_P (insn))
{
- bool clobbers_all = false;
-#ifdef NON_SAVING_SETJMP
- if (NON_SAVING_SETJMP
- && find_reg_note (insn, REG_SETJMP, NULL_RTX))
- clobbers_all = true;
-#endif
-
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- if (clobbers_all
- || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
+ if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
record_last_reg_set_info (insn, regno);
mark_call (insn);
static void
clear_modify_mem_tables (void)
{
- int i;
+ unsigned i;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi)
while (GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT
- || GET_CODE (dest) == SIGN_EXTRACT
|| GET_CODE (dest) == STRICT_LOW_PART)
dest = XEXP (dest, 0);
have a note, and have no special SET, add a REG_EQUAL note to not
lose information. */
if (!success && note == 0 && set != 0
- && GET_CODE (XEXP (set, 0)) != ZERO_EXTRACT
- && GET_CODE (XEXP (set, 0)) != SIGN_EXTRACT)
+ && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT)
note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
}
rtx this_rtx = l->loc;
rtx note;
- if (l->in_libcall)
+ /* Don't CSE non-constant values out of libcall blocks. */
+ if (l->in_libcall && ! CONSTANT_P (this_rtx))
continue;
if (gcse_constant_p (this_rtx))
return true;
}
}
- XEXP (note, 0) = replace_rtx (XEXP (note, 0), oldreg, newval);
+ XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0), oldreg, newval);
insn = end;
}
return true;
count = 0;
FOR_EACH_BB (bb)
/* Check for more than one successor. */
- if (bb->succ && bb->succ->succ_next)
+ if (EDGE_COUNT (bb->succs) > 1)
{
cond = fis_get_condition (BB_END (bb));
dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest
: FALLTHRU_EDGE (bb)->dest;
- if (dest && ! dest->pred->pred_next
+ if (dest && EDGE_COUNT (dest->preds) == 1
&& dest != EXIT_BLOCK_PTR)
{
new = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
bypass_block (basic_block bb, rtx setcc, rtx jump)
{
rtx insn, note;
- edge e, enext, edest;
+ edge e, edest;
int i, change;
int may_be_loop_header;
+ unsigned removed_p;
+ edge_iterator ei;
insn = (setcc != NULL) ? setcc : jump;
find_used_regs (&XEXP (note, 0), NULL);
may_be_loop_header = false;
- for (e = bb->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, bb->preds)
if (e->flags & EDGE_DFS_BACK)
{
may_be_loop_header = true;
}
change = 0;
- for (e = bb->pred; e; e = enext)
+ for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
{
- enext = e->pred_next;
+ removed_p = 0;
+
if (e->flags & EDGE_COMPLEX)
- continue;
+ {
+ ei_next (&ei);
+ continue;
+ }
/* We can't redirect edges from new basic blocks. */
if (e->src->index >= bypass_last_basic_block)
- continue;
+ {
+ ei_next (&ei);
+ continue;
+ }
/* The irreducible loops created by redirecting of edges entering the
loop from outside would decrease effectiveness of some of the following
optimizations, so prevent this. */
if (may_be_loop_header
&& !(e->flags & EDGE_DFS_BACK))
- continue;
+ {
+ ei_next (&ei);
+ continue;
+ }
for (i = 0; i < reg_use_count; i++)
{
}
else if (GET_CODE (new) == LABEL_REF)
{
+ edge_iterator ei2;
+
dest = BLOCK_FOR_INSN (XEXP (new, 0));
/* Don't bypass edges containing instructions. */
- for (edest = bb->succ; edest; edest = edest->succ_next)
+ FOR_EACH_EDGE (edest, ei2, bb->succs)
if (edest->dest == dest && edest->insns.r)
{
dest = NULL;
if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc))))
{
edge e2;
- for (e2 = e->src->succ; e2; e2 = e2->succ_next)
+ edge_iterator ei2;
+
+ FOR_EACH_EDGE (e2, ei2, e->src->succs)
if (e2->dest == dest)
{
dest = NULL;
e->src->index, old_dest->index, dest->index);
}
change = 1;
+ removed_p = 1;
break;
}
}
+ if (!removed_p)
+ ei_next (&ei);
}
return change;
}
EXIT_BLOCK_PTR, next_bb)
{
/* Check for more than one predecessor. */
- if (bb->pred && bb->pred->pred_next)
+ if (EDGE_COUNT (bb->preds) > 1)
{
setcc = NULL_RTX;
for (insn = BB_HEAD (bb);
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 (e = bb->pred; e ; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, bb->preds)
if (e->flags & EDGE_ABNORMAL)
{
sbitmap_difference (antloc[bb->index], antloc[bb->index], trapping_expr);
pre_expr_reaches_here_p_work (basic_block occr_bb, struct expr *expr, basic_block bb, char *visited)
{
edge pred;
-
- for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (pred, ei, bb->preds)
{
basic_block pred_bb = pred->src;
if (JUMP_P (insn)
|| (NONJUMP_INSN_P (insn)
- && (bb->succ->succ_next || (bb->succ->flags & EDGE_ABNORMAL))))
+ && (EDGE_COUNT (bb->succs) > 1
+ || EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL)))
{
#ifdef HAVE_cc0
rtx note;
}
#endif
/* FIXME: What if something in cc0/jump uses value set in new insn? */
- new_insn = emit_insn_before (pat, insn);
+ new_insn = emit_insn_before_noloc (pat, insn);
}
/* Likewise if the last insn is a call, as will happen in the presence
of exception handling. */
else if (CALL_P (insn)
- && (bb->succ->succ_next || (bb->succ->flags & EDGE_ABNORMAL)))
+ && (EDGE_COUNT (bb->succs) > 1 || EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL))
{
/* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
we search backward and place the instructions before the first
|| NOTE_INSN_BASIC_BLOCK_P (insn))
insn = NEXT_INSN (insn);
- new_insn = emit_insn_before (pat, insn);
+ new_insn = emit_insn_before_noloc (pat, insn);
}
else
- new_insn = emit_insn_after (pat, insn);
+ new_insn = emit_insn_after_noloc (pat, insn);
while (1)
{
handling this situation. This one is easiest for
now. */
- if ((eg->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL)
+ if (eg->flags & EDGE_ABNORMAL)
insert_insn_end_bb (index_map[j], bb, 0);
else
{
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;
visited = xcalloc (last_basic_block, 1);
}
- for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
+ FOR_EACH_EDGE (pred, ei, bb->preds)
{
basic_block pred_bb = pred->src;
if (CALL_P (insn))
{
- bool clobbers_all = false;
-#ifdef NON_SAVING_SETJMP
- if (NON_SAVING_SETJMP
- && find_reg_note (insn, REG_SETJMP, NULL_RTX))
- clobbers_all = true;
-#endif
-
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- if (clobbers_all
- || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
+ if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
{
last_set_in[regno] = INSN_UID (insn);
SET_BIT (reg_set_in_block[bb->index], regno);
if (CALL_P (insn))
{
- bool clobbers_all = false;
-#ifdef NON_SAVING_SETJMP
- if (NON_SAVING_SETJMP
- && find_reg_note (insn, REG_SETJMP, NULL_RTX))
- clobbers_all = true;
-#endif
-
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- if (clobbers_all
- || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
+ if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
already_set[regno] = 1;
}
note_stores (pat, reg_clear_last_set, last_set_in);
if (CALL_P (insn))
{
- bool clobbers_all = false;
-#ifdef NON_SAVING_SETJMP
- if (NON_SAVING_SETJMP
- && find_reg_note (insn, REG_SETJMP, NULL_RTX))
- clobbers_all = true;
-#endif
-
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- if ((clobbers_all
- || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
+ if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)
&& last_set_in[regno] == INSN_UID (insn))
last_set_in[regno] = 0;
}
rtx pat = PATTERN (insn);
rtx dest = SET_DEST (pat);
- if (GET_CODE (dest) == SIGN_EXTRACT
- || GET_CODE (dest) == ZERO_EXTRACT)
+ if (GET_CODE (dest) == ZERO_EXTRACT)
dest = XEXP (dest, 0);
/* Check for memory stores to aliased objects. */
before = NEXT_INSN (before);
}
- insn = emit_insn_after (insn, prev);
+ insn = emit_insn_after_noloc (insn, prev);
if (gcse_file)
{
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. */
insert it at the start of the BB, and reset the insert bits on the other
edges so we don't try to insert it on the other edges. */
bb = e->dest;
- for (tmp = e->dest->pred; tmp ; tmp = tmp->pred_next)
+ FOR_EACH_EDGE (tmp, ei, e->dest->preds)
if (!(tmp->flags & EDGE_FAKE))
{
int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
insertion vector for these edges, and insert at the start of the BB. */
if (!tmp && bb != EXIT_BLOCK_PTR)
{
- for (tmp = e->dest->pred; tmp ; tmp = tmp->pred_next)
+ 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);
return 0;
}
- /* We can't insert on this edge, so we'll insert at the head of the
- successors block. See Morgan, sec 10.5. */
- if ((e->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL)
- {
- insert_insn_start_bb (insn, bb);
- return 0;
- }
+ /* 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);
static void
remove_reachable_equiv_notes (basic_block bb, struct ls_expr *smexpr)
{
- edge *stack = xmalloc (sizeof (edge) * n_basic_blocks), act;
+ edge_iterator *stack, ei;
+ int sp;
+ edge act;
sbitmap visited = sbitmap_alloc (last_basic_block);
- int stack_top = 0;
rtx last, insn, note;
rtx mem = smexpr->pattern;
+ stack = xmalloc (sizeof (edge_iterator) * n_basic_blocks);
+ sp = 0;
+ ei = ei_start (bb->succs);
+
sbitmap_zero (visited);
- act = bb->succ;
+ act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
while (1)
{
if (!act)
{
- if (!stack_top)
+ if (!sp)
{
free (stack);
sbitmap_free (visited);
return;
}
- act = stack[--stack_top];
+ act = ei_edge (stack[--sp]);
}
bb = act->dest;
if (bb == EXIT_BLOCK_PTR
|| TEST_BIT (visited, bb->index))
{
- act = act->succ_next;
+ if (!ei_end_p (ei))
+ ei_next (&ei);
+ act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
continue;
}
SET_BIT (visited, bb->index);
INSN_UID (insn));
remove_note (insn, note);
}
- act = act->succ_next;
- if (bb->succ)
+
+ 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[stack_top++] = act;
- act = bb->succ;
+ stack[sp++] = ei;
+ ei = ei_start (bb->succs);
+ act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
}
}
}
/* 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 (gcse_file != NULL)
+ fprintf (gcse_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);