#include "except.h"
#include "ggc.h"
#include "params.h"
+#include "cselib.h"
#include "obstack.h"
-#define obstack_chunk_alloc gmalloc
-#define obstack_chunk_free free
/* Propagate flow information through back edges and thus enable PRE's
moving loop invariant calculations out of loops.
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. */
-#define FOLLOW_BACK_EDGES 1
/* We support GCSE via Partial Redundancy Elimination. PRE optimizations
are a superset of those done by GCSE.
static void mems_conflict_for_gcse_p PARAMS ((rtx, rtx, void *));
static int load_killed_in_block_p PARAMS ((basic_block, int, rtx, int));
static void canon_list_insert PARAMS ((rtx, rtx, void *));
-static int cprop_insn PARAMS ((basic_block, rtx, int));
+static int cprop_insn PARAMS ((rtx, int));
static int cprop PARAMS ((int));
static int one_cprop_pass PARAMS ((int, int));
+static bool constprop_register PARAMS ((rtx, rtx, rtx, int));
static struct expr *find_bypass_set PARAMS ((int, int));
static int bypass_block PARAMS ((basic_block, rtx, rtx));
static int bypass_conditional_jumps PARAMS ((void));
static void clear_modify_mem_tables PARAMS ((void));
static void free_modify_mem_tables PARAMS ((void));
static rtx gcse_emit_move_after PARAMS ((rtx, rtx, rtx));
+static bool do_local_cprop PARAMS ((rtx, rtx, int));
+static void local_cprop_pass PARAMS ((int));
\f
/* Entry point for global common subexpression elimination.
F is the first instruction in the function. */
return xrealloc (ptr, size);
}
-/* Cover function to obstack_alloc.
- We don't need to record the bytes allocated here since
- obstack_chunk_alloc is set to gmalloc. */
+/* Cover function to obstack_alloc. */
static char *
gcse_alloc (size)
unsigned long size;
{
+ bytes_used += size;
return (char *) obstack_alloc (&gcse_obstack, size);
}
\f
/* Hash table support. */
-/* For each register, the cuid of the first/last insn in the block
- that set it, or -1 if not set. */
-#define NEVER_SET -1
-
struct reg_avail_info
{
basic_block last_bb;
int success = 0;
rtx set = single_set (insn);
- success = validate_replace_src (from, to, insn);
+ validate_replace_src_group (from, to, insn);
+ if (num_changes_pending () && apply_change_group ())
+ success = 1;
- /* If above failed and this is a single set, try to simplify the source of
- the set given our substitution. We could perhaps try this for multiple
- SETs, but it probably won't buy us anything. */
- if (!success && set != 0)
+ 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
+ the set given our substitution. We could perhaps try this for multiple
+ SETs, but it probably won't buy us anything. */
src = simplify_replace_rtx (SET_SRC (set), from, to);
if (!rtx_equal_p (src, SET_SRC (set))
&& validate_change (insn, &SET_SRC (set), src, 0))
success = 1;
- }
- /* If we've failed to do replacement, have a single SET, and don't already
- have a note, add a REG_EQUAL note to not lose information. */
- if (!success && note == 0 && set != 0)
- note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
+ /* If we've failed to do replacement, have a single SET, and don't already
+ have a note, add a REG_EQUAL note to not lose information. */
+ if (!success && note == 0 && set != 0)
+ note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
+ }
/* If there is already a NOTE, update the expression in it with our
replacement. */
return 1;
}
+static bool
+constprop_register (insn, from, to, alter_jumps)
+ rtx insn;
+ rtx from;
+ rtx to;
+ int alter_jumps;
+{
+ rtx sset;
+
+ /* Check for reg or cc0 setting instructions followed by
+ conditional branch instructions first. */
+ if (alter_jumps
+ && (sset = single_set (insn)) != NULL
+ && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
+ {
+ rtx dest = SET_DEST (sset);
+ if ((REG_P (dest) || CC0_P (dest))
+ && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), from, to))
+ return 1;
+ }
+
+ /* Handle normal insns next. */
+ if (GET_CODE (insn) == INSN
+ && try_replace_reg (from, to, insn))
+ return 1;
+
+ /* Try to propagate a CONST_INT into a conditional jump.
+ We're pretty specific about what we will handle in this
+ code, we can extend this as necessary over time.
+
+ Right now the insn in question must look like
+ (set (pc) (if_then_else ...)) */
+ else if (alter_jumps && any_condjump_p (insn) && onlyjump_p (insn))
+ return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to);
+ return 0;
+}
+
/* Perform constant and copy propagation on INSN.
The result is non-zero if a change was made. */
static int
-cprop_insn (bb, insn, alter_jumps)
- basic_block bb;
+cprop_insn (insn, alter_jumps)
rtx insn;
int alter_jumps;
{
/* Constant propagation. */
if (CONSTANT_P (src))
{
- rtx sset;
-
- /* Check for reg or cc0 setting instructions followed by
- conditional branch instructions first. */
- if (alter_jumps
- && (sset = single_set (insn)) != NULL
- && any_condjump_p (NEXT_INSN (insn))
- && onlyjump_p (NEXT_INSN (insn)))
- {
- rtx dest = SET_DEST (sset);
- if ((REG_P (dest) || CC0_P (dest))
- && cprop_jump (bb, insn, NEXT_INSN (insn),
- reg_used->reg_rtx, src))
- {
- changed = 1;
- break;
- }
- }
-
- /* Handle normal insns next. */
- if (GET_CODE (insn) == INSN
- && try_replace_reg (reg_used->reg_rtx, src, insn))
+ if (constprop_register (insn, reg_used->reg_rtx, src, alter_jumps))
{
changed = 1;
const_prop_count++;
if (gcse_file != NULL)
{
- fprintf (gcse_file, "CONST-PROP: Replacing reg %d in ",
- regno);
- fprintf (gcse_file, "insn %d with constant ",
- INSN_UID (insn));
+ fprintf (gcse_file, "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
+ fprintf (gcse_file, "insn %d with constant ", INSN_UID (insn));
print_rtl (gcse_file, src);
fprintf (gcse_file, "\n");
}
-
- /* The original insn setting reg_used may or may not now be
- deletable. We leave the deletion to flow. */
}
-
- /* Try to propagate a CONST_INT into a conditional jump.
- We're pretty specific about what we will handle in this
- code, we can extend this as necessary over time.
-
- Right now the insn in question must look like
- (set (pc) (if_then_else ...)) */
- else if (alter_jumps
- && any_condjump_p (insn)
- && onlyjump_p (insn))
- changed |= cprop_jump (bb, NULL, insn, reg_used->reg_rtx, src);
-
}
else if (GET_CODE (src) == REG
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
copy_prop_count++;
if (gcse_file != NULL)
{
- fprintf (gcse_file, "COPY-PROP: Replacing reg %d in insn %d",
+ fprintf (gcse_file, "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
regno, INSN_UID (insn));
fprintf (gcse_file, " with reg %d\n", REGNO (src));
}
return changed;
}
+static bool
+do_local_cprop (x, insn, alter_jumps)
+ rtx x;
+ rtx insn;
+ int alter_jumps;
+{
+ rtx newreg = NULL, newcnst = NULL;
+
+ /* Rule out USE instructions and ASM statements as we don't want to change the hard
+ registers mentioned. */
+ if (GET_CODE (x) == REG
+ && (REGNO (x) >= FIRST_PSEUDO_REGISTER
+ || (GET_CODE (PATTERN (insn)) != USE && asm_noperands (PATTERN (insn)) < 0)))
+ {
+ cselib_val *val = cselib_lookup (x, GET_MODE (x), 0);
+ struct elt_loc_list *l;
+
+ if (!val)
+ return false;
+ for (l = val->locs; l; l = l->next)
+ {
+ rtx this_rtx = l->loc;
+ rtx note;
+
+ if (CONSTANT_P (this_rtx))
+ newcnst = this_rtx;
+ if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER
+ /* Don't copy propagate if it has attached REG_EQUIV note.
+ At this point this only function parameters should have
+ REG_EQUIV notes and if the argument slot is used somewhere
+ explicitly, it means address of parameter has been taken,
+ so we should not extend the lifetime of the pseudo. */
+ && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
+ || GET_CODE (XEXP (note, 0)) != MEM))
+ newreg = this_rtx;
+ }
+ if (newcnst && constprop_register (insn, x, newcnst, alter_jumps))
+ {
+ if (gcse_file != NULL)
+ {
+ fprintf (gcse_file, "LOCAL CONST-PROP: Replacing reg %d in ",
+ REGNO (x));
+ fprintf (gcse_file, "insn %d with constant ",
+ INSN_UID (insn));
+ print_rtl (gcse_file, newcnst);
+ fprintf (gcse_file, "\n");
+ }
+ const_prop_count++;
+ return true;
+ }
+ else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
+ {
+ if (gcse_file != NULL)
+ {
+ fprintf (gcse_file,
+ "LOCAL COPY-PROP: Replacing reg %d in insn %d",
+ REGNO (x), INSN_UID (insn));
+ fprintf (gcse_file, " with reg %d\n", REGNO (newreg));
+ }
+ copy_prop_count++;
+ return true;
+ }
+ }
+ return false;
+}
+
+static void
+local_cprop_pass (alter_jumps)
+ int alter_jumps;
+{
+ rtx insn;
+ struct reg_use *reg_used;
+
+ cselib_init ();
+ for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+ {
+ if (INSN_P (insn))
+ {
+ rtx note = find_reg_equal_equiv_note (insn);
+
+ do
+ {
+ reg_use_count = 0;
+ note_uses (&PATTERN (insn), find_used_regs, NULL);
+ if (note)
+ find_used_regs (&XEXP (note, 0), NULL);
+
+ for (reg_used = ®_use_table[0]; reg_use_count > 0;
+ reg_used++, reg_use_count--)
+ if (do_local_cprop (reg_used->reg_rtx, insn, alter_jumps))
+ break;
+ }
+ while (reg_use_count);
+ }
+ cselib_process_insn (insn);
+ }
+ cselib_finish ();
+}
+
/* Forward propagate copies. This includes copies and constants. Return
non-zero if a change was made. */
insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
- changed |= cprop_insn (bb, insn, alter_jumps);
+ changed |= cprop_insn (insn, alter_jumps);
/* Keep track of everything modified by this insn. */
/* ??? Need to be careful w.r.t. mods done to INSN. Don't
const_prop_count = 0;
copy_prop_count = 0;
+ local_cprop_pass (alter_jumps);
+
alloc_set_hash_table (max_cuid);
compute_set_hash_table ();
if (gcse_file)
rtx src, dest, insn;
{
rtx new;
- rtx set = single_set (insn);
+ 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_rtx_SET (VOIDmode, dest, src), insn);
-
- /* want_to_gcse_p verifies that this move will be valid. Still this call
- is mandatory as it may create clobbers required by the pattern. */
- if (insn_invalid_p (insn))
- abort ();
+ 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
dominance_info dominators;
/* ??? We could compute post dominators and run this algorithm in
- reverse to to perform tail merging, doing so would probably be
+ 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
if (pred->src == ENTRY_BLOCK_PTR)
break;
+ else if (pred_bb == expr_bb)
+ continue;
else if (visited[pred_bb->index])
continue;