/* Common subexpression elimination for GNU compiler.
Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998
- 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
+ Free Software Foundation, Inc.
This file is part of GCC.
#include "params.h"
#include "rtlhooks-def.h"
#include "tree-pass.h"
+#include "df.h"
+#include "dbgcnt.h"
/* The basic idea of common subexpression elimination is to go
through the code, keeping a record of expressions that would
static HARD_REG_SET hard_regs_in_table;
-/* CUID of insn that starts the basic block currently being cse-processed. */
-
-static int cse_basic_block_start;
-
-/* CUID of insn that ends the basic block currently being cse-processed. */
-
-static int cse_basic_block_end;
-
-/* Vector mapping INSN_UIDs to cuids.
- The cuids are like uids but increase monotonically always.
- We use them to see whether a reg is used outside a given basic block. */
-
-static int *uid_cuid;
-
-/* Highest UID in UID_CUID. */
-static int max_uid;
-
-/* Get the cuid of an insn. */
-
-#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
-
/* Nonzero if cse has altered conditional jump insns
in such a way that jump optimization should be redone. */
struct cse_basic_block_data
{
- /* Lowest CUID value of insns in block. */
- int low_cuid;
- /* Highest CUID value of insns in block. */
- int high_cuid;
/* Total number of SETs in block. */
int nsets;
/* Size of current branch path, if any. */
} *path;
};
+
+/* Pointers to the live in/live out bitmaps for the boundaries of the
+ current EBB. */
+static bitmap cse_ebb_live_in, cse_ebb_live_out;
+
/* A simple bitmap to track which basic blocks have been visited
already as part of an already processed extended basic block. */
static sbitmap cse_visited_basic_blocks;
static void cse_insn (rtx, rtx);
static void cse_prescan_path (struct cse_basic_block_data *);
static void invalidate_from_clobbers (rtx);
-static rtx cse_process_notes (rtx, rtx);
+static rtx cse_process_notes (rtx, rtx, bool *);
static void cse_extended_basic_block (struct cse_basic_block_data *);
static void count_reg_usage (rtx, int *, rtx, int);
static int check_for_label_ref (rtx *, void *);
&& ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new))
|| (new >= FIRST_PSEUDO_REGISTER
&& (firstr < FIRST_PSEUDO_REGISTER
- || ((uid_cuid[REGNO_LAST_UID (new)] > cse_basic_block_end
- || (uid_cuid[REGNO_FIRST_UID (new)]
- < cse_basic_block_start))
- && (uid_cuid[REGNO_LAST_UID (new)]
- > uid_cuid[REGNO_LAST_UID (firstr)]))))))
+ || (bitmap_bit_p (cse_ebb_live_out, new)
+ && !bitmap_bit_p (cse_ebb_live_out, firstr))
+ || (bitmap_bit_p (cse_ebb_live_in, new)
+ && !bitmap_bit_p (cse_ebb_live_in, firstr))))))
{
reg_eqv_table[firstr].prev = new;
reg_eqv_table[new].next = firstr;
if (code == REG)
{
unsigned int regno = REGNO (x);
- unsigned int endregno
- = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
- : hard_regno_nregs[regno][GET_MODE (x)]);
+ unsigned int endregno = END_REGNO (x);
unsigned int i;
for (i = regno; i < endregno; i++)
/* If X is a hard register, show it is being put in the table. */
if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER)
- {
- unsigned int regno = REGNO (x);
- unsigned int endregno = regno + hard_regno_nregs[regno][GET_MODE (x)];
- unsigned int i;
-
- for (i = regno; i < endregno; i++)
- SET_HARD_REG_BIT (hard_regs_in_table, i);
- }
+ add_to_hard_reg_set (&hard_regs_in_table, GET_MODE (x), REGNO (x));
/* Put an element for X into the right hash bucket. */
{
HOST_WIDE_INT in_table
= TEST_HARD_REG_BIT (hard_regs_in_table, regno);
- unsigned int endregno
- = regno + hard_regno_nregs[regno][GET_MODE (x)];
+ unsigned int endregno = END_HARD_REGNO (x);
unsigned int tregno, tendregno, rn;
struct table_elt *p, *next;
continue;
tregno = REGNO (p->exp);
- tendregno
- = tregno + hard_regno_nregs[tregno][GET_MODE (p->exp)];
+ tendregno = END_HARD_REGNO (p->exp);
if (tendregno > regno && tregno < endregno)
remove_from_table (p, hash);
}
continue;
regno = REGNO (p->exp);
- endregno = regno + hard_regno_nregs[regno][GET_MODE (p->exp)];
+ endregno = END_HARD_REGNO (p->exp);
for (i = regno; i < endregno; i++)
if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
{
unsigned int regno = REGNO (y);
unsigned int i;
- unsigned int endregno
- = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
- : hard_regno_nregs[regno][GET_MODE (y)]);
+ unsigned int endregno = END_REGNO (y);
/* If the quantities are not the same, the expressions are not
equivalent. If there are and we are not to validate, they
static void
validate_canon_reg (rtx *xloc, rtx insn)
{
- rtx new = canon_reg (*xloc, insn);
+ if (*xloc)
+ {
+ rtx new = canon_reg (*xloc, insn);
- /* If replacing pseudo with hard reg or vice versa, ensure the
- insn remains valid. Likewise if the insn has MATCH_DUPs. */
- if (insn != 0 && new != 0)
- validate_change (insn, xloc, new, 1);
- else
- *xloc = new;
+ /* If replacing pseudo with hard reg or vice versa, ensure the
+ insn remains valid. Likewise if the insn has MATCH_DUPs. */
+ gcc_assert (insn && new);
+ validate_change (insn, xloc, new, 1);
+ }
}
/* Canonicalize an expression:
{
rtx folded_arg = XEXP (x, i), const_arg;
enum machine_mode mode_arg = GET_MODE (folded_arg);
+
+ switch (GET_CODE (folded_arg))
+ {
+ case MEM:
+ case REG:
+ case SUBREG:
+ const_arg = equiv_constant (folded_arg);
+ break;
+
+ case CONST:
+ case CONST_INT:
+ case SYMBOL_REF:
+ case LABEL_REF:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ const_arg = folded_arg;
+ break;
+
#ifdef HAVE_cc0
- if (CC0_P (folded_arg))
- folded_arg = prev_insn_cc0, mode_arg = prev_insn_cc0_mode;
+ case CC0:
+ folded_arg = prev_insn_cc0;
+ mode_arg = prev_insn_cc0_mode;
+ const_arg = equiv_constant (folded_arg);
+ break;
#endif
- const_arg = equiv_constant (folded_arg);
+
+ default:
+ folded_arg = fold_rtx (folded_arg, insn);
+ const_arg = equiv_constant (folded_arg);
+ break;
+ }
/* For the first three operands, see if the operand
is constant or equivalent to a constant. */
rtx tem;
int n_sets = 0;
-#ifdef HAVE_cc0
- /* Records what this insn does to set CC0. */
- this_insn_cc0 = 0;
- this_insn_cc0_mode = VOIDmode;
-#endif
-
rtx src_eqv = 0;
struct table_elt *src_eqv_elt = 0;
int src_eqv_volatile = 0;
struct set *sets = (struct set *) 0;
this_insn = insn;
+#ifdef HAVE_cc0
+ /* Records what this insn does to set CC0. */
+ this_insn_cc0 = 0;
+ this_insn_cc0_mode = VOIDmode;
+#endif
/* Find all the SETs and CLOBBERs in this instruction.
Record all the SETs in the array `set' and count them.
This does nothing when a register is clobbered
because we have already invalidated the reg. */
if (MEM_P (XEXP (y, 0)))
- canon_reg (XEXP (y, 0), NULL_RTX);
+ canon_reg (XEXP (y, 0), insn);
}
else if (GET_CODE (y) == USE
&& ! (REG_P (XEXP (y, 0))
&& REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER))
- canon_reg (y, NULL_RTX);
+ canon_reg (y, insn);
else if (GET_CODE (y) == CALL)
{
/* The result of apply_change_group can be ignored; see
else if (GET_CODE (x) == CLOBBER)
{
if (MEM_P (XEXP (x, 0)))
- canon_reg (XEXP (x, 0), NULL_RTX);
+ canon_reg (XEXP (x, 0), insn);
}
/* Canonicalize a USE of a pseudo register or memory location. */
else if (GET_CODE (x) == USE
&& ! (REG_P (XEXP (x, 0))
&& REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER))
- canon_reg (XEXP (x, 0), NULL_RTX);
+ canon_reg (XEXP (x, 0), insn);
else if (GET_CODE (x) == CALL)
{
/* The result of apply_change_group can be ignored; see canon_reg. */
&& (! rtx_equal_p (XEXP (tem, 0), SET_SRC (sets[0].rtl))
|| GET_CODE (SET_DEST (sets[0].rtl)) == STRICT_LOW_PART))
{
- src_eqv = fold_rtx (canon_reg (XEXP (tem, 0), NULL_RTX), insn);
- XEXP (tem, 0) = src_eqv;
+ /* The result of apply_change_group can be ignored; see canon_reg. */
+ canon_reg (XEXP (tem, 0), insn);
+ apply_change_group ();
+ src_eqv = fold_rtx (XEXP (tem, 0), insn);
+ XEXP (tem, 0) = copy_rtx (src_eqv);
+ df_notes_rescan (insn);
}
/* Canonicalize sources and addresses of destinations.
const_elt; const_elt = const_elt->next_same_value)
if (REG_P (const_elt->exp))
{
- src_related = gen_lowpart (mode,
- const_elt->exp);
+ src_related = gen_lowpart (mode, const_elt->exp);
break;
}
}
larger_elt; larger_elt = larger_elt->next_same_value)
if (REG_P (larger_elt->exp))
{
- src_related = gen_lowpart (mode,
- larger_elt->exp);
+ src_related = gen_lowpart (mode, larger_elt->exp);
break;
}
;
/* Look for a substitution that makes a valid insn. */
- else if (validate_change (insn, &SET_SRC (sets[i].rtl), trial, 0))
+ else if (validate_unshare_change
+ (insn, &SET_SRC (sets[i].rtl), trial, 0))
{
rtx new = canon_reg (SET_SRC (sets[i].rtl), insn);
XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0),
sets[i].orig_src,
copy_rtx (new));
+ df_notes_rescan (libcall_insn);
}
/* The result of apply_change_group can be ignored; see
validate_change (insn, &SET_SRC (sets[i].rtl), new, 1);
apply_change_group ();
- /* With non-call exceptions, if this was an insn that could
- trap, we may have made it non-throwing now. For example
- we may have replaced a load with a register. */
- if (flag_non_call_exceptions
- && insn == BB_END (BLOCK_FOR_INSN (insn)))
- purge_dead_edges (BLOCK_FOR_INSN (insn));
-
break;
}
/* Record the actual constant value in a REG_EQUAL note,
making a new one if one does not already exist. */
set_unique_reg_note (insn, REG_EQUAL, src_const);
+ df_notes_rescan (insn);
}
}
else if (dest == pc_rtx && GET_CODE (src) == LABEL_REF
&& !LABEL_REF_NONLOCAL_P (src))
{
- /* Now emit a BARRIER after the unconditional jump. */
- if (NEXT_INSN (insn) == 0
- || !BARRIER_P (NEXT_INSN (insn)))
- emit_barrier_after (insn);
-
/* We reemit the jump in as many cases as possible just in
case the form of an unconditional jump is significantly
different than a computed jump or conditional jump.
delete_insn_and_edges (insn);
insn = new;
-
- /* Now emit a BARRIER after the unconditional jump. */
- if (NEXT_INSN (insn) == 0
- || !BARRIER_P (NEXT_INSN (insn)))
- emit_barrier_after (insn);
}
else
INSN_CODE (insn) = -1;
{
if (insert_regs (x, NULL, 0))
{
+ rtx dest = SET_DEST (sets[i].rtl);
+
rehash_using_reg (x);
hash = HASH (x, mode);
+ sets[i].dest_hash = HASH (dest, GET_MODE (dest));
}
elt = insert (x, NULL, hash, mode);
}
but it knows that reg_tick has been incremented, and
it leaves reg_in_table as -1 . */
unsigned int regno = REGNO (x);
- unsigned int endregno
- = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
- : hard_regno_nregs[regno][GET_MODE (x)]);
+ unsigned int endregno = END_REGNO (x);
unsigned int i;
for (i = regno; i < endregno; i++)
Return the replacement for X. */
static rtx
-cse_process_notes (rtx x, rtx object)
+cse_process_notes_1 (rtx x, rtx object, bool *changed)
{
enum rtx_code code = GET_CODE (x);
const char *fmt = GET_RTX_FORMAT (code);
case MEM:
validate_change (x, &XEXP (x, 0),
- cse_process_notes (XEXP (x, 0), x), 0);
+ cse_process_notes (XEXP (x, 0), x, changed), 0);
return x;
case EXPR_LIST:
case INSN_LIST:
if (REG_NOTE_KIND (x) == REG_EQUAL)
- XEXP (x, 0) = cse_process_notes (XEXP (x, 0), NULL_RTX);
+ XEXP (x, 0) = cse_process_notes (XEXP (x, 0), NULL_RTX, changed);
if (XEXP (x, 1))
- XEXP (x, 1) = cse_process_notes (XEXP (x, 1), NULL_RTX);
+ XEXP (x, 1) = cse_process_notes (XEXP (x, 1), NULL_RTX, changed);
return x;
case SIGN_EXTEND:
case ZERO_EXTEND:
case SUBREG:
{
- rtx new = cse_process_notes (XEXP (x, 0), object);
+ rtx new = cse_process_notes (XEXP (x, 0), object, changed);
/* We don't substitute VOIDmode constants into these rtx,
since they would impede folding. */
if (GET_MODE (new) != VOIDmode)
for (i = 0; i < GET_RTX_LENGTH (code); i++)
if (fmt[i] == 'e')
validate_change (object, &XEXP (x, i),
- cse_process_notes (XEXP (x, i), object), 0);
+ cse_process_notes (XEXP (x, i), object, changed), 0);
return x;
}
+
+static rtx
+cse_process_notes (rtx x, rtx object, bool *changed)
+{
+ rtx new = cse_process_notes_1 (x, object, changed);
+ if (new != x)
+ *changed = true;
+ return new;
+}
+
\f
/* Find a path in the CFG, starting with FIRST_BB to perform CSE on.
Otherwise, DATA->path is filled and the function returns TRUE indicating
that a path to follow was found.
- If FOLLOW_JUMPS is false, the maximum path lenghth is 1 and the only
+ If FOLLOW_JUMPS is false, the maximum path length is 1 and the only
block in the path will be FIRST_BB. */
static bool
{
bb = FALLTHRU_EDGE (previous_bb_in_path)->dest;
if (bb != EXIT_BLOCK_PTR
- && single_pred_p (bb))
+ && single_pred_p (bb)
+ /* We used to assert here that we would only see blocks
+ that we have not visited yet. But we may end up
+ visiting basic blocks twice if the CFG has changed
+ in this run of cse_main, because when the CFG changes
+ the topological sort of the CFG also changes. A basic
+ blocks that previously had more than two predecessors
+ may now have a single predecessor, and become part of
+ a path that starts at another basic block.
+
+ We still want to visit each basic block only once, so
+ halt the path here if we have already visited BB. */
+ && !TEST_BIT (cse_visited_basic_blocks, bb->index))
{
-#if ENABLE_CHECKING
- /* We should only see blocks here that we have not
- visited yet. */
- gcc_assert (!TEST_BIT (cse_visited_basic_blocks, bb->index));
-#endif
SET_BIT (cse_visited_basic_blocks, bb->index);
data->path[path_size++].bb = bb;
break;
e = NULL;
if (e && e->dest != EXIT_BLOCK_PTR
- && single_pred_p (e->dest))
+ && single_pred_p (e->dest)
+ /* Avoid visiting basic blocks twice. The large comment
+ above explains why this can happen. */
+ && !TEST_BIT (cse_visited_basic_blocks, e->dest->index))
{
basic_block bb2 = e->dest;
-
- /* We should only see blocks here that we have not
- visited yet. */
- gcc_assert (!TEST_BIT (cse_visited_basic_blocks, bb2->index));
-
SET_BIT (cse_visited_basic_blocks, bb2->index);
data->path[path_size++].bb = bb2;
bb = bb2;
}
\f
+/* Return true if BB has exception handling successor edges. */
+
+static bool
+have_eh_succ_edges (basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e->flags & EDGE_EH)
+ return true;
+
+ return false;
+}
+
+\f
/* Scan to the end of the path described by DATA. Return an estimate of
- the total number of SETs, and the lowest and highest insn CUID, of all
- insns in the path. */
+ the total number of SETs of all insns in the path. */
static void
cse_prescan_path (struct cse_basic_block_data *data)
{
int nsets = 0;
- int low_cuid = -1, high_cuid = -1; /* FIXME low_cuid not computed correctly */
int path_size = data->path_size;
int path_entry;
nsets += XVECLEN (PATTERN (insn), 0);
else
nsets += 1;
-
- /* Ignore insns made by CSE in a previous traversal of this
- basic block. They cannot affect the boundaries of the
- basic block.
- FIXME: When we only visit each basic block at most once,
- this can go away. */
- if (INSN_UID (insn) <= max_uid && INSN_CUID (insn) > high_cuid)
- high_cuid = INSN_CUID (insn);
- if (INSN_UID (insn) <= max_uid && INSN_CUID (insn) < low_cuid)
- low_cuid = INSN_CUID (insn);
}
}
- data->low_cuid = low_cuid;
- data->high_cuid = high_cuid;
data->nsets = nsets;
}
\f
qty_table = XNEWVEC (struct qty_table_elem, max_qty);
new_basic_block ();
+ cse_ebb_live_in = df_get_live_in (ebb_data->path[0].bb);
+ cse_ebb_live_out = df_get_live_out (ebb_data->path[path_size - 1].bb);
for (path_entry = 0; path_entry < path_size; path_entry++)
{
basic_block bb;
/* Process notes first so we have all notes in canonical forms
when looking for duplicate operations. */
if (REG_NOTES (insn))
- REG_NOTES (insn) = cse_process_notes (REG_NOTES (insn),
- NULL_RTX);
+ {
+ bool changed = false;
+ REG_NOTES (insn) = cse_process_notes (REG_NOTES (insn),
+ NULL_RTX, &changed);
+ if (changed)
+ df_notes_rescan (insn);
+ }
/* Track when we are inside in LIBCALL block. Inside such
a block we do not want to record destinations. The last
/* Make sure that libcalls don't span multiple basic blocks. */
gcc_assert (libcall_insn == NULL_RTX);
+ /* With non-call exceptions, we are not always able to update
+ the CFG properly inside cse_insn. So clean up possibly
+ redundant EH edges here. */
+ if (flag_non_call_exceptions && have_eh_succ_edges (bb))
+ purge_dead_edges (bb);
+
/* If we changed a conditional jump, we may have terminated
the path we are following. Check that by verifying that
the edge we would take still exists. If the edge does
free (qty_table);
}
+
\f
/* Perform cse on the instructions of a function.
F is the first instruction.
int *rc_order = XNEWVEC (int, last_basic_block);
int i, n_blocks;
+ df_set_flags (DF_LR_RUN_DCE);
+ df_analyze ();
+ df_set_flags (DF_DEFER_INSN_RESCAN);
+
+ reg_scan (get_insns (), max_reg_num ());
init_cse_reg_info (nregs);
ebb_data.path = XNEWVEC (struct branch_path,
cse_visited_basic_blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (cse_visited_basic_blocks);
- /* Compute the mapping from uids to cuids.
- CUIDs are numbers assigned to insns, like uids, except that
- that cuids increase monotonically through the code. */
- max_uid = get_max_uid ();
- uid_cuid = XCNEWVEC (int, max_uid + 1);
- i = 0;
- FOR_EACH_BB (bb)
- {
- rtx insn;
- FOR_BB_INSNS (bb, insn)
- INSN_CUID (insn) = ++i;
- }
-
- /* Loop over basic blocks in DFS order,
+ /* Loop over basic blocks in reverse completion order (RPO),
excluding the ENTRY and EXIT blocks. */
n_blocks = pre_and_rev_post_order_compute (NULL, rc_order, false);
i = 0;
while (i < n_blocks)
{
- /* Find the first block in the DFS queue that we have not yet
+ /* Find the first block in the RPO queue that we have not yet
processed before. */
do
{
if (ebb_data.nsets == 0)
continue;
- /* Get a reasonable extimate for the maximum number of qty's
+ /* Get a reasonable estimate for the maximum number of qty's
needed for this path. For this, we take the number of sets
and multiply that by MAX_RECOG_OPERANDS. */
max_qty = ebb_data.nsets * MAX_RECOG_OPERANDS;
- cse_basic_block_start = ebb_data.low_cuid;
- cse_basic_block_end = ebb_data.high_cuid;
/* Dump the path we're about to process. */
if (dump_file)
/* Clean up. */
end_alias_analysis ();
- free (uid_cuid);
free (reg_eqv_table);
free (ebb_data.path);
sbitmap_free (cse_visited_basic_blocks);
/* If this is a dead insn, delete it and show registers in it aren't
being used. */
- if (! live_insn)
+ if (! live_insn && dbg_cnt (delete_trivial_dead))
{
count_reg_usage (insn, counts, NULL_RTX, -1);
delete_insn_and_edges (insn);
rest_of_handle_cse (void)
{
int tem;
+
if (dump_file)
dump_flow_info (dump_file, dump_flags);
- reg_scan (get_insns (), max_reg_num ());
-
tem = cse_main (get_insns (), max_reg_num ());
/* If we are not running more CSE passes, then we are no longer
expecting CSE to be run. But always rerun it in a cheap mode. */
cse_not_expected = !flag_rerun_cse_after_loop && !flag_gcse;
- /* If there are dead edges to purge, we haven't properly updated
- the CFG incrementally. */
- gcc_assert (!purge_all_dead_edges ());
-
if (tem)
rebuild_jump_labels (get_insns ());
if (tem || optimize > 1)
- cleanup_cfg (CLEANUP_EXPENSIVE);
+ cleanup_cfg (0);
return 0;
}
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
+ TODO_df_finish |
TODO_dump_func |
TODO_ggc_collect |
TODO_verify_flow, /* todo_flags_finish */
bypassed safely. */
cse_condition_code_reg ();
- /* If there are dead edges to purge, we haven't properly updated
- the CFG incrementally. */
- gcc_assert (!purge_all_dead_edges ());
-
delete_trivially_dead_insns (get_insns (), max_reg_num ());
if (tem)
{
timevar_push (TV_JUMP);
rebuild_jump_labels (get_insns ());
- delete_dead_jumptables ();
- cleanup_cfg (CLEANUP_EXPENSIVE);
+ cleanup_cfg (0);
timevar_pop (TV_JUMP);
}
- reg_scan (get_insns (), max_reg_num ());
cse_not_expected = 1;
return 0;
}
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
+ TODO_df_finish |
TODO_dump_func |
TODO_ggc_collect |
TODO_verify_flow, /* todo_flags_finish */
OSDN Git Service
