#include "hashtab.h"
#include "df.h"
#include "dbgcnt.h"
-
-/* Propagate flow information through back edges and thus enable PRE's
- moving loop invariant calculations out of loops.
-
- Originally this tended to create worse overall code, but several
- improvements during the development of PRE seem to have made following
- back edges generally a win.
-
- Note much of the loop invariant code motion done here would normally
- be done by loop.c, which has more heuristics for when to move invariants
- out of loops. At some point we might need to move some of those
- heuristics into gcse.c. */
+#include "target.h"
/* We support GCSE via Partial Redundancy Elimination. PRE optimizations
- are a superset of those done by GCSE.
+ are a superset of those done by classic GCSE.
We perform the following steps:
conditional jumps if the condition can be computed from a value of
an incoming edge.
- 5) Perform store motion.
-
Two passes of copy/constant propagation are done because the first one
enables more GCSE and the second one helps to clean up the copies that
GCSE creates. This is needed more for PRE than for Classic because Classic
(set (pseudo-reg) (expression)).
Function want_to_gcse_p says what these are.
- In addition, expressions in REG_EQUAL notes are candidates for GXSE-ing.
+ In addition, expressions in REG_EQUAL notes are candidates for GCSE-ing.
This allows PRE to hoist expressions that are expressed in multiple insns,
- such as comprex address calculations (e.g. for PIC code, or loads with a
- high part and as lowe part).
+ such as complex address calculations (e.g. for PIC code, or loads with a
+ high part and a low part).
PRE handles moving invariant expressions out of loops (by treating them as
partially redundant).
- Eventually it would be nice to replace cse.c/gcse.c with SSA (static single
- assignment) based GVN (global value numbering). L. T. Simpson's paper
- (Rice University) on value numbering is a useful reference for this.
-
**********************
We used to support multiple passes but there are diminishing returns in
argue it is not. The number of iterations for the algorithm to converge
is typically 2-4 so I don't view it as that expensive (relatively speaking).
- PRE GCSE depends heavily on the second CSE pass to clean up the copies
+ PRE GCSE depends heavily on the second CPROP pass to clean up the copies
we create. To make an expression reach the place where it's redundant,
the result of the expression is copied to a new register, and the redundant
expression is deleted by replacing it with this new register. Classic GCSE
[one could build a mapping table without holes afterwards though].
Someday I'll perform the computation and figure it out. */
-struct hash_table
+struct hash_table_d
{
/* The table itself.
This is an array of `expr_hash_table_size' elements. */
};
/* Expression hash table. */
-static struct hash_table expr_hash_table;
+static struct hash_table_d expr_hash_table;
/* Copy propagation hash table. */
-static struct hash_table set_hash_table;
+static struct hash_table_d set_hash_table;
/* This is a list of expressions which are MEMs and will be used by load
or store motion.
static void *gcse_alloc (unsigned long);
static void alloc_gcse_mem (void);
static void free_gcse_mem (void);
-static void hash_scan_insn (rtx, struct hash_table *);
-static void hash_scan_set (rtx, rtx, struct hash_table *);
-static void hash_scan_clobber (rtx, rtx, struct hash_table *);
-static void hash_scan_call (rtx, rtx, struct hash_table *);
+static void hash_scan_insn (rtx, struct hash_table_d *);
+static void hash_scan_set (rtx, rtx, struct hash_table_d *);
+static void hash_scan_clobber (rtx, rtx, struct hash_table_d *);
+static void hash_scan_call (rtx, rtx, struct hash_table_d *);
static int want_to_gcse_p (rtx);
static bool gcse_constant_p (const_rtx);
static int oprs_unchanged_p (const_rtx, const_rtx, int);
static int oprs_anticipatable_p (const_rtx, const_rtx);
static int oprs_available_p (const_rtx, const_rtx);
static void insert_expr_in_table (rtx, enum machine_mode, rtx, int, int,
- struct hash_table *);
-static void insert_set_in_table (rtx, rtx, struct hash_table *);
+ struct hash_table_d *);
+static void insert_set_in_table (rtx, rtx, struct hash_table_d *);
static unsigned int hash_expr (const_rtx, enum machine_mode, int *, int);
static unsigned int hash_set (int, int);
static int expr_equiv_p (const_rtx, const_rtx);
static void record_last_reg_set_info (rtx, int);
static void record_last_mem_set_info (rtx);
static void record_last_set_info (rtx, const_rtx, void *);
-static void compute_hash_table (struct hash_table *);
-static void alloc_hash_table (int, struct hash_table *, int);
-static void free_hash_table (struct hash_table *);
-static void compute_hash_table_work (struct hash_table *);
-static void dump_hash_table (FILE *, const char *, struct hash_table *);
-static struct expr *lookup_set (unsigned int, struct hash_table *);
+static void compute_hash_table (struct hash_table_d *);
+static void alloc_hash_table (struct hash_table_d *, int);
+static void free_hash_table (struct hash_table_d *);
+static void compute_hash_table_work (struct hash_table_d *);
+static void dump_hash_table (FILE *, const char *, struct hash_table_d *);
+static struct expr *lookup_set (unsigned int, struct hash_table_d *);
static struct expr *next_set (unsigned int, struct expr *);
static void reset_opr_set_tables (void);
static int oprs_not_set_p (const_rtx, const_rtx);
static void compute_transp (const_rtx, int, sbitmap *, int);
static void compute_transpout (void);
static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *,
- struct hash_table *);
+ struct hash_table_d *);
static void compute_cprop_data (void);
static void find_used_regs (rtx *, void *);
static int try_replace_reg (rtx, rtx, rtx);
static void
compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc,
- struct hash_table *table)
+ struct hash_table_d *table)
{
unsigned int i;
if (antloc)
for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
{
- SET_BIT (antloc[BLOCK_NUM (occr->insn)], indx);
+ SET_BIT (antloc[BLOCK_FOR_INSN (occr->insn)->index], indx);
/* While we're scanning the table, this is a good place to
initialize this. */
if (comp)
for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
{
- SET_BIT (comp[BLOCK_NUM (occr->insn)], indx);
+ SET_BIT (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
/* While we're scanning the table, this is a good place to
initialize this. */
/* Return true if we can assign X to a pseudo register such that the
resulting insn does not result in clobbering a hard register as a
side-effect.
+
+ Additionally, if the target requires it, check that the resulting insn
+ can be copied. If it cannot, this means that X is special and probably
+ has hidden side-effects we don't want to mess with.
+
This function is typically used by code motion passes, to verify
that it is safe to insert an insn without worrying about clobbering
maybe live hard regs. */
valid. */
PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x));
SET_SRC (PATTERN (test_insn)) = x;
- return ((icode = recog (PATTERN (test_insn), test_insn, &num_clobbers)) >= 0
- && (num_clobbers == 0 || ! added_clobbers_hard_reg_p (icode)));
+
+ icode = recog (PATTERN (test_insn), test_insn, &num_clobbers);
+ if (icode < 0)
+ return false;
+
+ if (num_clobbers > 0 && added_clobbers_hard_reg_p (icode))
+ return false;
+
+ if (targetm.cannot_copy_insn_p && targetm.cannot_copy_insn_p (test_insn))
+ return false;
+
+ return true;
}
/* Return nonzero if the operands of expression X are unchanged from the
static void
insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p,
- int avail_p, struct hash_table *table)
+ int avail_p, struct hash_table_d *table)
{
int found, do_not_record_p;
unsigned int hash;
{
antic_occr = cur_expr->antic_occr;
- if (antic_occr && BLOCK_NUM (antic_occr->insn) != BLOCK_NUM (insn))
+ if (antic_occr
+ && BLOCK_FOR_INSN (antic_occr->insn) != BLOCK_FOR_INSN (insn))
antic_occr = NULL;
if (antic_occr)
{
avail_occr = cur_expr->avail_occr;
- if (avail_occr && BLOCK_NUM (avail_occr->insn) == BLOCK_NUM (insn))
+ if (avail_occr
+ && BLOCK_FOR_INSN (avail_occr->insn) == BLOCK_FOR_INSN (insn))
{
/* Found another instance of the expression in the same basic block.
Prefer this occurrence to the currently recorded one. We want
basic block. */
static void
-insert_set_in_table (rtx x, rtx insn, struct hash_table *table)
+insert_set_in_table (rtx x, rtx insn, struct hash_table_d *table)
{
int found;
unsigned int hash;
/* Now record the occurrence. */
cur_occr = cur_expr->avail_occr;
- if (cur_occr && BLOCK_NUM (cur_occr->insn) == BLOCK_NUM (insn))
+ if (cur_occr
+ && BLOCK_FOR_INSN (cur_occr->insn) == BLOCK_FOR_INSN (insn))
{
/* Found another instance of the expression in the same basic block.
Prefer this occurrence to the currently recorded one. We want
{
/* Consider a COMPARE of two integers constant. */
if (GET_CODE (x) == COMPARE
- && GET_CODE (XEXP (x, 0)) == CONST_INT
- && GET_CODE (XEXP (x, 1)) == CONST_INT)
+ && CONST_INT_P (XEXP (x, 0))
+ && CONST_INT_P (XEXP (x, 1)))
return true;
/* Consider a COMPARE of the same registers is a constant
expression one). */
static void
-hash_scan_set (rtx pat, rtx insn, struct hash_table *table)
+hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table)
{
rtx src = SET_SRC (pat);
rtx dest = SET_DEST (pat);
/* Don't GCSE something if we can't do a reg/reg copy. */
&& can_copy_p (GET_MODE (dest))
/* GCSE commonly inserts instruction after the insn. We can't
- do that easily for EH_REGION notes so disable GCSE on these
- for now. */
- && !find_reg_note (insn, REG_EH_REGION, NULL_RTX)
+ do that easily for EH edges so disable GCSE on these for now. */
+ /* ??? We can now easily create new EH landing pads at the
+ gimple level, for splitting edges; there's no reason we
+ can't do the same thing at the rtl level. */
+ && !can_throw_internal (insn)
/* Is SET_SRC something we want to gcse? */
&& want_to_gcse_p (src)
/* Don't CSE a nop. */
/* Don't GCSE something if we can't do a reg/reg copy. */
&& can_copy_p (GET_MODE (src))
/* GCSE commonly inserts instruction after the insn. We can't
- do that easily for EH_REGION notes so disable GCSE on these
- for now. */
- && ! find_reg_note (insn, REG_EH_REGION, NULL_RTX)
+ do that easily for EH edges so disable GCSE on these for now. */
+ && !can_throw_internal (insn)
/* Is SET_DEST something we want to gcse? */
&& want_to_gcse_p (dest)
/* Don't CSE a nop. */
static void
hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
- struct hash_table *table ATTRIBUTE_UNUSED)
+ struct hash_table_d *table ATTRIBUTE_UNUSED)
{
/* Currently nothing to do. */
}
static void
hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
- struct hash_table *table ATTRIBUTE_UNUSED)
+ struct hash_table_d *table ATTRIBUTE_UNUSED)
{
/* Currently nothing to do. */
}
otherwise it is for the expression hash table. */
static void
-hash_scan_insn (rtx insn, struct hash_table *table)
+hash_scan_insn (rtx insn, struct hash_table_d *table)
{
rtx pat = PATTERN (insn);
int i;
}
static void
-dump_hash_table (FILE *file, const char *name, struct hash_table *table)
+dump_hash_table (FILE *file, const char *name, struct hash_table_d *table)
{
int i;
/* Flattened out table, so it's printed in proper order. */
dest_addr = get_addr (XEXP (dest, 0));
dest_addr = canon_rtx (dest_addr);
insn = (rtx) v_insn;
- bb = BLOCK_NUM (insn);
+ bb = BLOCK_FOR_INSN (insn)->index;
canon_modify_mem_list[bb] =
alloc_EXPR_LIST (VOIDmode, dest_addr, canon_modify_mem_list[bb]);
static void
record_last_mem_set_info (rtx insn)
{
- int bb = BLOCK_NUM (insn);
+ int bb = BLOCK_FOR_INSN (insn)->index;
/* load_killed_in_block_p will handle the case of calls clobbering
everything. */
TABLE is the table computed. */
static void
-compute_hash_table_work (struct hash_table *table)
+compute_hash_table_work (struct hash_table_d *table)
{
int i;
}
/* Allocate space for the set/expr hash TABLE.
- N_INSNS is the number of instructions in the function.
It is used to determine the number of buckets to use.
SET_P determines whether set or expression table will
be created. */
static void
-alloc_hash_table (int n_insns, struct hash_table *table, int set_p)
+alloc_hash_table (struct hash_table_d *table, int set_p)
{
int n;
- table->size = n_insns / 4;
+ n = get_max_insn_count ();
+
+ table->size = n / 4;
if (table->size < 11)
table->size = 11;
/* Free things allocated by alloc_hash_table. */
static void
-free_hash_table (struct hash_table *table)
+free_hash_table (struct hash_table_d *table)
{
free (table->table);
}
expression hash table. */
static void
-compute_hash_table (struct hash_table *table)
+compute_hash_table (struct hash_table_d *table)
{
/* Initialize count of number of entries in hash table. */
table->n_elems = 0;
table entry, or NULL if not found. */
static struct expr *
-lookup_set (unsigned int regno, struct hash_table *table)
+lookup_set (unsigned int regno, struct hash_table_d *table)
{
unsigned int hash = hash_set (regno, table->size);
struct expr *expr;
/* Now iterate over the blocks which have memory modifications
but which do not have any calls. */
- EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set,
+ EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set,
blocks_with_calls,
0, bb_index, bi)
{
with our replacement. */
if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
set_unique_reg_note (insn, REG_EQUAL,
- simplify_replace_rtx (XEXP (note, 0), from,
- copy_rtx (to)));
+ simplify_replace_rtx (XEXP (note, 0), from, to));
if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
{
/* If above failed and this is a single set, try to simplify the source of
which contains INSN. */
while (set)
{
- if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index))
+ if (TEST_BIT (cprop_avin[BLOCK_FOR_INSN (insn)->index],
+ set->bitmap_index))
break;
set = next_set (regno, set);
}
}
}
+ if (changed && DEBUG_INSN_P (insn))
+ return 0;
+
return changed;
}
for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
{
removed_p = 0;
-
+
if (e->flags & EDGE_COMPLEX)
{
ei_next (&ei);
src = SET_SRC (pc_set (jump));
if (setcc != NULL)
- src = simplify_replace_rtx (src,
- SET_DEST (PATTERN (setcc)),
- SET_SRC (PATTERN (setcc)));
+ src = simplify_replace_rtx (src,
+ SET_DEST (PATTERN (setcc)),
+ SET_SRC (PATTERN (setcc)));
new_rtx = simplify_replace_rtx (src, reg_used->reg_rtx,
- SET_SRC (set->expr));
+ SET_SRC (set->expr));
/* Jump bypassing may have already placed instructions on
edges of the CFG. We can't bypass an outgoing edge that
{
setcc = NULL_RTX;
FOR_BB_INSNS (bb, insn)
- if (NONJUMP_INSN_P (insn))
+ if (DEBUG_INSN_P (insn))
+ continue;
+ else if (NONJUMP_INSN_P (insn))
{
if (setcc)
break;
{
edge pred;
edge_iterator ei;
-
+
FOR_EACH_EDGE (pred, ei, bb->preds)
{
basic_block pred_bb = pred->src;
if (insn_invalid_p (insn))
gcc_unreachable ();
}
-
+
pat = get_insns ();
end_sequence ();
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,
+ BLOCK_FOR_INSN (insn)->index, INSN_UID (new_insn), indx,
INSN_UID (insn), regno);
}
gcc_obstack_init (&gcse_obstack);
alloc_gcse_mem ();
- alloc_hash_table (get_max_uid (), &expr_hash_table, 0);
+ alloc_hash_table (&expr_hash_table, 0);
add_noreturn_fake_exit_edges ();
if (flag_gcse_lm)
compute_ld_motion_mems ();
gcc_obstack_init (&gcse_obstack);
alloc_gcse_mem ();
- alloc_hash_table (get_max_uid (), &expr_hash_table, 0);
+ alloc_hash_table (&expr_hash_table, 0);
compute_hash_table (&expr_hash_table);
if (dump_file)
dump_hash_table (dump_file, "Code Hosting Expressions", &expr_hash_table);
{
FOR_BB_INSNS (bb, insn)
{
- if (INSN_P (insn))
+ if (NONDEBUG_INSN_P (insn))
{
if (GET_CODE (PATTERN (insn)) == SET)
{
rtx pat = PATTERN (insn);
rtx src = SET_SRC (pat);
rtx reg = expr->reaching_reg;
- rtx copy, new_rtx;
+ rtx copy;
/* If we've already copied it, continue. */
if (expr->reaching_reg == src)
}
copy = gen_move_insn (reg, copy_rtx (SET_SRC (pat)));
- new_rtx = emit_insn_before (copy, insn);
+ emit_insn_before (copy, insn);
SET_SRC (pat) = reg;
df_insn_rescan (insn);
FIXME: This local pass should not be necessary after CSE (but for
some reason it still is). It is also (proven) not necessary
to run the local pass right after FWPWOP.
-
+
FIXME: The global analysis would not get into infinite loops if it
would use the DF solver (via df_simple_dataflow) instead of
the solver implemented in this file. */
implicit_sets = XCNEWVEC (rtx, last_basic_block);
find_implicit_sets ();
- alloc_hash_table (get_max_uid (), &set_hash_table, 1);
+ alloc_hash_table (&set_hash_table, 1);
compute_hash_table (&set_hash_table);
/* Free implicit_sets before peak usage. */
execute_rtl_cprop (void)
{
delete_unreachable_blocks ();
- df_note_add_problem ();
df_set_flags (DF_LR_RUN_DCE);
df_analyze ();
flag_rerun_cse_after_global_opts |= one_cprop_pass ();
execute_rtl_pre (void)
{
delete_unreachable_blocks ();
- df_note_add_problem ();
df_analyze ();
flag_rerun_cse_after_global_opts |= one_pre_gcse_pass ();
return 0;
execute_rtl_hoist (void)
{
delete_unreachable_blocks ();
- df_note_add_problem ();
df_analyze ();
flag_rerun_cse_after_global_opts |= one_code_hoisting_pass ();
return 0;
{
RTL_PASS,
"cprop", /* name */
- gate_rtl_cprop, /* gate */
- execute_rtl_cprop, /* execute */
+ gate_rtl_cprop, /* gate */
+ execute_rtl_cprop, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
{
{
RTL_PASS,
- "pre", /* name */
- gate_rtl_pre, /* gate */
- execute_rtl_pre, /* execute */
+ "rtl pre", /* name */
+ gate_rtl_pre, /* gate */
+ execute_rtl_pre, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
{
RTL_PASS,
"hoist", /* name */
- gate_rtl_hoist, /* gate */
- execute_rtl_hoist, /* execute */
+ gate_rtl_hoist, /* gate */
+ execute_rtl_hoist, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
OSDN Git Service
