/* RTL-based forward propagation pass for GNU compiler.
- Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
+ Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
Free Software Foundation, Inc.
Contributed by Paolo Bonzini and Steven Bosscher.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "toplev.h"
+#include "diagnostic-core.h"
+#include "sparseset.h"
#include "timevar.h"
#include "rtl.h"
#include "tm_p.h"
- address_cost (new_rtx, mode, as, speed));
/* If the addresses have equivalent cost, prefer the new address
- if it has the highest `rtx_cost'. That has the potential of
+ if it has the highest `set_src_cost'. That has the potential of
eliminating the most insns without additional costs, and it
is the same that cse.c used to do. */
if (gain == 0)
- gain = rtx_cost (new_rtx, SET, speed) - rtx_cost (old_rtx, SET, speed);
+ gain = set_src_cost (new_rtx, speed) - set_src_cost (old_rtx, speed);
return (gain > 0);
}
}
\f
-struct find_occurrence_data
-{
- rtx find;
- rtx *retval;
-};
+static df_ref *active_defs;
+#ifdef ENABLE_CHECKING
+static sparseset active_defs_check;
+#endif
-/* Callback for for_each_rtx, used in find_occurrence.
- See if PX is the rtx we have to find. Return 1 to stop for_each_rtx
- if successful, or 0 to continue traversing otherwise. */
+/* Fill the ACTIVE_DEFS array with the use->def link for the registers
+ mentioned in USE_REC. Register the valid entries in ACTIVE_DEFS_CHECK
+ too, for checking purposes. */
-static int
-find_occurrence_callback (rtx *px, void *data)
+static void
+register_active_defs (df_ref *use_rec)
{
- struct find_occurrence_data *fod = (struct find_occurrence_data *) data;
- rtx x = *px;
- rtx find = fod->find;
-
- if (x == find)
+ while (*use_rec)
{
- fod->retval = px;
- return 1;
- }
+ df_ref use = *use_rec++;
+ df_ref def = get_def_for_use (use);
+ int regno = DF_REF_REGNO (use);
- return 0;
+#ifdef ENABLE_CHECKING
+ sparseset_set_bit (active_defs_check, regno);
+#endif
+ active_defs[regno] = def;
+ }
}
-/* Return a pointer to one of the occurrences of register FIND in *PX. */
-static rtx *
-find_occurrence (rtx *px, rtx find)
+/* Build the use->def links that we use to update the dataflow info
+ for new uses. Note that building the links is very cheap and if
+ it were done earlier, they could be used to rule out invalid
+ propagations (in addition to what is done in all_uses_available_at).
+ I'm not doing this yet, though. */
+
+static void
+update_df_init (rtx def_insn, rtx insn)
{
- struct find_occurrence_data data;
+#ifdef ENABLE_CHECKING
+ sparseset_clear (active_defs_check);
+#endif
+ register_active_defs (DF_INSN_USES (def_insn));
+ register_active_defs (DF_INSN_USES (insn));
+ register_active_defs (DF_INSN_EQ_USES (insn));
+}
- gcc_assert (REG_P (find)
- || (GET_CODE (find) == SUBREG
- && REG_P (SUBREG_REG (find))));
- data.find = find;
- data.retval = NULL;
- for_each_rtx (px, find_occurrence_callback, &data);
- return data.retval;
-}
+/* Update the USE_DEF_REF array for the given use, using the active definitions
+ in the ACTIVE_DEFS array to match pseudos to their def. */
-\f
-/* Inside INSN, the expression rooted at *LOC has been changed, moving some
- uses from USE_VEC. Find those that are present, and create new items
- in the data flow object of the pass. Mark any new uses as having the
- given TYPE. */
-static void
-update_df (rtx insn, rtx *loc, df_ref *use_rec, enum df_ref_type type,
- int new_flags)
+static inline void
+update_uses (df_ref *use_rec)
{
- bool changed = false;
-
- /* Add a use for the registers that were propagated. */
while (*use_rec)
{
- df_ref use = *use_rec;
- df_ref orig_use = use, new_use;
- int width = -1;
- int offset = -1;
- enum machine_mode mode = VOIDmode;
- rtx *new_loc = find_occurrence (loc, DF_REF_REG (orig_use));
- use_rec++;
-
- if (!new_loc)
- continue;
+ df_ref use = *use_rec++;
+ int regno = DF_REF_REGNO (use);
- if (DF_REF_FLAGS_IS_SET (orig_use, DF_REF_SIGN_EXTRACT | DF_REF_ZERO_EXTRACT))
- {
- width = DF_REF_EXTRACT_WIDTH (orig_use);
- offset = DF_REF_EXTRACT_OFFSET (orig_use);
- mode = DF_REF_EXTRACT_MODE (orig_use);
- }
+ /* Set up the use-def chain. */
+ if (DF_REF_ID (use) >= (int) VEC_length (df_ref, use_def_ref))
+ VEC_safe_grow_cleared (df_ref, heap, use_def_ref,
+ DF_REF_ID (use) + 1);
- /* Add a new insn use. Use the original type, because it says if the
- use was within a MEM. */
- new_use = df_ref_create (DF_REF_REG (orig_use), new_loc,
- insn, BLOCK_FOR_INSN (insn),
- type, DF_REF_FLAGS (orig_use) | new_flags,
- width, offset, mode);
+#ifdef ENABLE_CHECKING
+ gcc_assert (sparseset_bit_p (active_defs_check, regno));
+#endif
+ VEC_replace (df_ref, use_def_ref, DF_REF_ID (use), active_defs[regno]);
+ }
+}
- /* Set up the use-def chain. */
- gcc_assert (DF_REF_ID (new_use) == (int) VEC_length (df_ref, use_def_ref));
- VEC_safe_push (df_ref, heap, use_def_ref, get_def_for_use (orig_use));
- changed = true;
+
+/* Update the USE_DEF_REF array for the uses in INSN. Only update note
+ uses if NOTES_ONLY is true. */
+
+static void
+update_df (rtx insn, rtx note)
+{
+ struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
+
+ if (note)
+ {
+ df_uses_create (&XEXP (note, 0), insn, DF_REF_IN_NOTE);
+ df_notes_rescan (insn);
+ }
+ else
+ {
+ df_uses_create (&PATTERN (insn), insn, 0);
+ df_insn_rescan (insn);
+ update_uses (DF_INSN_INFO_USES (insn_info));
}
- if (changed)
- df_insn_rescan (insn);
+
+ update_uses (DF_INSN_INFO_EQ_USES (insn_info));
}
try_fwprop_subst (df_ref use, rtx *loc, rtx new_rtx, rtx def_insn, bool set_reg_equal)
{
rtx insn = DF_REF_INSN (use);
- enum df_ref_type type = DF_REF_TYPE (use);
- int flags = DF_REF_FLAGS (use);
rtx set = single_set (insn);
+ rtx note = NULL_RTX;
bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
int old_cost = 0;
bool ok;
+ update_df_init (def_insn, insn);
+
/* forward_propagate_subreg may be operating on an instruction with
multiple sets. If so, assume the cost of the new instruction is
not greater than the old one. */
if (set)
- old_cost = rtx_cost (SET_SRC (set), SET, speed);
+ old_cost = set_src_cost (SET_SRC (set), speed);
if (dump_file)
{
fprintf (dump_file, "\nIn insn %d, replacing\n ", INSN_UID (insn));
else if (DF_REF_TYPE (use) == DF_REF_REG_USE
&& set
- && rtx_cost (SET_SRC (set), SET, speed) > old_cost)
+ && set_src_cost (SET_SRC (set), speed) > old_cost)
{
if (dump_file)
fprintf (dump_file, "Changes to insn %d not profitable\n",
{
confirm_change_group ();
num_changes++;
-
- df_ref_remove (use);
- if (!CONSTANT_P (new_rtx))
- {
- struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
- update_df (insn, loc, DF_INSN_INFO_USES (insn_info), type, flags);
- update_df (insn, loc, DF_INSN_INFO_EQ_USES (insn_info), type, flags);
- }
}
else
{
if (dump_file)
fprintf (dump_file, " Setting REG_EQUAL note\n");
- set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
-
- /* ??? Is this still necessary if we add the note through
- set_unique_reg_note? */
- if (!CONSTANT_P (new_rtx))
- {
- struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
- update_df (insn, loc, DF_INSN_INFO_USES (insn_info),
- type, DF_REF_IN_NOTE);
- update_df (insn, loc, DF_INSN_INFO_EQ_USES (insn_info),
- type, DF_REF_IN_NOTE);
- }
+ note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
}
}
+ if ((ok || note) && !CONSTANT_P (new_rtx))
+ update_df (insn, note);
+
return ok;
}
src = SET_SRC (def_set);
if (GET_CODE (src) == SUBREG
&& REG_P (SUBREG_REG (src))
+ && REGNO (SUBREG_REG (src)) >= FIRST_PSEUDO_REGISTER
&& GET_MODE (SUBREG_REG (src)) == use_mode
&& subreg_lowpart_p (src)
&& all_uses_available_at (def_insn, use_insn))
/* If this is a SUBREG of a ZERO_EXTEND or SIGN_EXTEND, and the SUBREG
is the low part of the reg being extended then just use the inner
operand. Don't do this if the ZERO_EXTEND or SIGN_EXTEND insn will
- be removed due to it matching a LOAD_EXTEND_OP load from memory. */
+ be removed due to it matching a LOAD_EXTEND_OP load from memory,
+ or due to the operation being a no-op when applied to registers.
+ For example, if we have:
+
+ A: (set (reg:DI X) (sign_extend:DI (reg:SI Y)))
+ B: (... (subreg:SI (reg:DI X)) ...)
+
+ and mode_rep_extended says that Y is already sign-extended,
+ the backend will typically allow A to be combined with the
+ definition of Y or, failing that, allow A to be deleted after
+ reload through register tying. Introducing more uses of Y
+ prevents both optimisations. */
else if (subreg_lowpart_p (use_reg))
{
use_insn = DF_REF_INSN (use);
if ((GET_CODE (src) == ZERO_EXTEND
|| GET_CODE (src) == SIGN_EXTEND)
&& REG_P (XEXP (src, 0))
+ && REGNO (XEXP (src, 0)) >= FIRST_PSEUDO_REGISTER
&& GET_MODE (XEXP (src, 0)) == use_mode
&& !free_load_extend (src, def_insn)
+ && (targetm.mode_rep_extended (use_mode, GET_MODE (src))
+ != (int) GET_CODE (src))
&& all_uses_available_at (def_insn, use_insn))
return try_fwprop_subst (use, DF_REF_LOC (use), XEXP (src, 0),
def_insn, false);
if (use_vec[0] && use_vec[1])
return false;
+ update_df_init (def_insn, use_insn);
speed_p = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn));
asm_operands = NULL_RTX;
switch (GET_CODE (use_pat))
if (num_changes_pending () == 0 || !apply_change_group ())
return false;
+ update_df (use_insn, NULL);
num_changes++;
return true;
}
/* If def and use are subreg, check if they match. */
reg = DF_REF_REG (use);
- if (GET_CODE (reg) == SUBREG
- && GET_CODE (SET_DEST (def_set)) == SUBREG
- && (SUBREG_BYTE (SET_DEST (def_set)) != SUBREG_BYTE (reg)
- || GET_MODE (SET_DEST (def_set)) != GET_MODE (reg)))
- return false;
-
+ if (GET_CODE (reg) == SUBREG && GET_CODE (SET_DEST (def_set)) == SUBREG)
+ {
+ if (SUBREG_BYTE (SET_DEST (def_set)) != SUBREG_BYTE (reg))
+ return false;
+ }
/* Check if the def had a subreg, but the use has the whole reg. */
- if (REG_P (reg) && GET_CODE (SET_DEST (def_set)) == SUBREG)
+ else if (REG_P (reg) && GET_CODE (SET_DEST (def_set)) == SUBREG)
return false;
-
/* Check if the use has a subreg, but the def had the whole reg. Unlike the
previous case, the optimization is possible and often useful indeed. */
- if (GET_CODE (reg) == SUBREG && REG_P (SET_DEST (def_set)))
+ else if (GET_CODE (reg) == SUBREG && REG_P (SET_DEST (def_set)))
reg = SUBREG_REG (reg);
+ /* Make sure that we can treat REG as having the same mode as the
+ source of DEF_SET. */
+ if (GET_MODE (SET_DEST (def_set)) != GET_MODE (reg))
+ return false;
+
/* Check if the substitution is valid (last, because it's the most
expensive check!). */
src = SET_SRC (def_set);
loc = &SET_SRC (use_set);
/* Do not replace an existing REG_EQUAL note if the insn is not
- recognized. Either we're already replacing in the note, or
- we'll separately try plugging the definition in the note and
- simplifying. */
- set_reg_equal = (note == NULL_RTX);
+ recognized. Either we're already replacing in the note, or we'll
+ separately try plugging the definition in the note and simplifying.
+ And only install a REQ_EQUAL note when the destination is a REG,
+ as the note would be invalid otherwise. */
+ set_reg_equal = (note == NULL_RTX && REG_P (SET_DEST (use_set)));
}
if (GET_MODE (*loc) == VOIDmode)
/* Given a use USE of an insn, if it has a single reaching
- definition, try to forward propagate it into that insn. */
+ definition, try to forward propagate it into that insn.
+ Return true if cfg cleanup will be needed. */
-static void
+static bool
forward_propagate_into (df_ref use)
{
df_ref def;
rtx parent;
if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
- return;
+ return false;
if (DF_REF_IS_ARTIFICIAL (use))
- return;
+ return false;
/* Only consider uses that have a single definition. */
def = get_def_for_use (use);
if (!def)
- return;
+ return false;
if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
- return;
+ return false;
if (DF_REF_IS_ARTIFICIAL (def))
- return;
+ return false;
/* Do not propagate loop invariant definitions inside the loop. */
if (DF_REF_BB (def)->loop_father != DF_REF_BB (use)->loop_father)
- return;
+ return false;
/* Check if the use is still present in the insn! */
use_insn = DF_REF_INSN (use);
parent = PATTERN (use_insn);
if (!reg_mentioned_p (DF_REF_REG (use), parent))
- return;
+ return false;
def_insn = DF_REF_INSN (def);
if (multiple_sets (def_insn))
- return;
+ return false;
def_set = single_set (def_insn);
if (!def_set)
- return;
+ return false;
/* Only try one kind of propagation. If two are possible, we'll
do it on the following iterations. */
- if (!forward_propagate_and_simplify (use, def_insn, def_set))
- forward_propagate_subreg (use, def_insn, def_set);
+ if (forward_propagate_and_simplify (use, def_insn, def_set)
+ || forward_propagate_subreg (use, def_insn, def_set))
+ {
+ if (cfun->can_throw_non_call_exceptions
+ && find_reg_note (use_insn, REG_EH_REGION, NULL_RTX)
+ && purge_dead_edges (DF_REF_BB (use)))
+ return true;
+ }
+ return false;
}
\f
build_single_def_use_links ();
df_set_flags (DF_DEFER_INSN_RESCAN);
+
+ active_defs = XNEWVEC (df_ref, max_reg_num ());
+#ifdef ENABLE_CHECKING
+ active_defs_check = sparseset_alloc (max_reg_num ());
+#endif
}
static void
loop_optimizer_finalize ();
VEC_free (df_ref, heap, use_def_ref);
+ free (active_defs);
+#ifdef ENABLE_CHECKING
+ sparseset_free (active_defs_check);
+#endif
+
free_dominance_info (CDI_DOMINATORS);
cleanup_cfg (0);
delete_trivially_dead_insns (get_insns (), max_reg_num ());
fwprop (void)
{
unsigned i;
+ bool need_cleanup = false;
fwprop_init ();
- /* Go through all the uses. update_df will create new ones at the
+ /* Go through all the uses. df_uses_create will create new ones at the
end, and we'll go through them as well.
Do not forward propagate addresses into loops until after unrolling.
|| DF_REF_BB (use)->loop_father == NULL
/* The outer most loop is not really a loop. */
|| loop_outer (DF_REF_BB (use)->loop_father) == NULL)
- forward_propagate_into (use);
+ need_cleanup |= forward_propagate_into (use);
}
fwprop_done ();
+ if (need_cleanup)
+ cleanup_cfg (0);
return 0;
}
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_df_finish | TODO_verify_rtl_sharing |
- TODO_dump_func /* todo_flags_finish */
+ TODO_df_finish
+ | TODO_verify_flow
+ | TODO_verify_rtl_sharing /* todo_flags_finish */
}
};
fwprop_addr (void)
{
unsigned i;
+ bool need_cleanup = false;
+
fwprop_init ();
- /* Go through all the uses. update_df will create new ones at the
+ /* Go through all the uses. df_uses_create will create new ones at the
end, and we'll go through them as well. */
for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
{
&& DF_REF_BB (use)->loop_father != NULL
/* The outer most loop is not really a loop. */
&& loop_outer (DF_REF_BB (use)->loop_father) != NULL)
- forward_propagate_into (use);
+ need_cleanup |= forward_propagate_into (use);
}
fwprop_done ();
+ if (need_cleanup)
+ cleanup_cfg (0);
return 0;
}
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_df_finish | TODO_verify_rtl_sharing |
- TODO_dump_func /* todo_flags_finish */
+ TODO_df_finish | TODO_verify_rtl_sharing /* todo_flags_finish */
}
};