/* Web construction code for GNU compiler.
Contributed by Jan Hubicka.
- Copyright (C) 2001, 2002, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2004, 2006, 2007
+ Free Software Foundation, Inc.
This file is part of GCC.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/* Simple optimization pass that splits independent uses of each pseudo,
increasing effectiveness of other optimizations. The optimization can
#include "rtl.h"
#include "hard-reg-set.h"
#include "flags.h"
+#include "obstack.h"
#include "basic-block.h"
#include "output.h"
#include "df.h"
#include "function.h"
+#include "timevar.h"
+#include "tree-pass.h"
-/* This entry is allocated for each reference in the insn stream. */
-struct web_entry
-{
- /* Pointer to the parent in the union/find tree. */
- struct web_entry *pred;
- /* Newly assigned register to the entry. Set only for roots. */
- rtx reg;
-};
-
-static struct web_entry *unionfind_root (struct web_entry *);
-static void unionfind_union (struct web_entry *, struct web_entry *);
-static void union_defs (struct df *, struct ref *, struct web_entry *,
- struct web_entry *);
-static rtx entry_register (struct web_entry *, struct ref *, char *, char *);
-static void replace_ref (struct ref *, rtx);
-static int mark_addressof (rtx *, void *);
+static rtx entry_register (struct web_entry *, struct df_ref *, char *);
+static void replace_ref (struct df_ref *, rtx);
/* Find the root of unionfind tree (the representative of set). */
-static struct web_entry *
+struct web_entry *
unionfind_root (struct web_entry *element)
{
struct web_entry *element1 = element, *element2;
return element;
}
-/* Union sets. */
+/* Union sets.
+ Return true if FIRST and SECOND points to the same web entry structure and
+ nothing is done. Otherwise, return false. */
-static void
+bool
unionfind_union (struct web_entry *first, struct web_entry *second)
{
first = unionfind_root (first);
second = unionfind_root (second);
if (first == second)
- return;
+ return true;
second->pred = first;
+ return false;
}
/* For each use, all possible defs reaching it must come in the same
- register, union them. */
+ register, union them.
+ FUN is the function that does the union. */
-static void
-union_defs (struct df *df, struct ref *use, struct web_entry *def_entry,
- struct web_entry *use_entry)
+void
+union_defs (struct df_ref *use, struct web_entry *def_entry,
+ struct web_entry *use_entry,
+ bool (*fun) (struct web_entry *, struct web_entry *))
{
rtx insn = DF_REF_INSN (use);
struct df_link *link = DF_REF_CHAIN (use);
- struct df_link *use_link = DF_INSN_USES (df, insn);
- struct df_link *def_link = DF_INSN_DEFS (df, insn);
- rtx set = single_set (insn);
+ struct df_ref **use_link;
+ struct df_ref **eq_use_link;
+ struct df_ref **def_link;
+ rtx set;
+
+ if (insn)
+ {
+ use_link = DF_INSN_USES (insn);
+ eq_use_link = DF_INSN_EQ_USES (insn);
+ def_link = DF_INSN_DEFS (insn);
+ set = single_set (insn);
+ }
+ else
+ {
+ use_link = NULL;
+ eq_use_link = NULL;
+ def_link = NULL;
+ set = NULL;
+ }
/* Some instructions may use match_dup for their operands. In case the
operands are dead, we will assign them different pseudos, creating
invalid instructions, so union all uses of the same operand for each
insn. */
- while (use_link)
- {
- if (use != use_link->ref
- && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (use_link->ref))
- unionfind_union (use_entry + DF_REF_ID (use),
- use_entry + DF_REF_ID (use_link->ref));
- use_link = use_link->next;
+ if (use_link)
+ while (*use_link)
+ {
+ if (use != *use_link
+ && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*use_link))
+ (*fun) (use_entry + DF_REF_ID (use),
+ use_entry + DF_REF_ID (*use_link));
+ use_link++;
+ }
+
+ if (eq_use_link)
+ while (*eq_use_link)
+ {
+ if (use != *eq_use_link
+ && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
+ (*fun) (use_entry + DF_REF_ID (use),
+ use_entry + DF_REF_ID (*eq_use_link));
+ eq_use_link++;
}
/* Recognize trivial noop moves and attempt to keep them as noop.
&& SET_SRC (set) == DF_REF_REG (use)
&& SET_SRC (set) == SET_DEST (set))
{
- while (def_link)
- {
- if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def_link->ref))
- unionfind_union (use_entry + DF_REF_ID (use),
- def_entry + DF_REF_ID (def_link->ref));
- def_link = def_link->next;
- }
+ if (def_link)
+ while (*def_link)
+ {
+ if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
+ (*fun) (use_entry + DF_REF_ID (use),
+ def_entry + DF_REF_ID (*def_link));
+ def_link++;
+ }
}
while (link)
{
- unionfind_union (use_entry + DF_REF_ID (use),
- def_entry + DF_REF_ID (link->ref));
+ (*fun) (use_entry + DF_REF_ID (use),
+ def_entry + DF_REF_ID (link->ref));
link = link->next;
}
register. Find it and union. */
if (use->flags & DF_REF_READ_WRITE)
{
- struct df_link *link = DF_INSN_DEFS (df, DF_REF_INSN (use));
-
- while (DF_REF_REAL_REG (link->ref) != DF_REF_REAL_REG (use))
- link = link->next;
-
- unionfind_union (use_entry + DF_REF_ID (use),
- def_entry + DF_REF_ID (link->ref));
+ struct df_ref **link;
+
+ if (DF_REF_INSN (use))
+ link = DF_INSN_DEFS (DF_REF_INSN (use));
+ else
+ link = NULL;
+
+ if (link)
+ while (*link)
+ {
+ if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
+ (*fun) (use_entry + DF_REF_ID (use),
+ def_entry + DF_REF_ID (*link));
+ link++;
+ }
}
}
/* Find the corresponding register for the given entry. */
static rtx
-entry_register (struct web_entry *entry, struct ref *ref, char *used,
- char *use_addressof)
+entry_register (struct web_entry *entry, struct df_ref *ref, char *used)
{
struct web_entry *root;
rtx reg, newreg;
"New web forced to keep reg=%i (user variable)\n",
REGNO (reg));
}
- else if (use_addressof [REGNO (reg)])
- {
- newreg = reg;
- if (dump_file)
- fprintf (dump_file,
- "New web forced to keep reg=%i (address taken)\n",
- REGNO (reg));
- }
else
{
newreg = gen_reg_rtx (GET_MODE (reg));
REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
REG_POINTER (newreg) = REG_POINTER (reg);
- REG_LOOP_TEST_P (newreg) = REG_LOOP_TEST_P (reg);
- RTX_UNCHANGING_P (newreg) = RTX_UNCHANGING_P (reg);
REG_ATTRS (newreg) = REG_ATTRS (reg);
if (dump_file)
fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
/* Replace the reference by REG. */
static void
-replace_ref (struct ref *ref, rtx reg)
+replace_ref (struct df_ref *ref, rtx reg)
{
rtx oldreg = DF_REF_REAL_REG (ref);
rtx *loc = DF_REF_REAL_LOC (ref);
+ unsigned int uid = INSN_UID (DF_REF_INSN (ref));
if (oldreg == reg)
return;
if (dump_file)
fprintf (dump_file, "Updating insn %i (%i->%i)\n",
- INSN_UID (DF_REF_INSN (ref)), REGNO (oldreg), REGNO (reg));
+ uid, REGNO (oldreg), REGNO (reg));
*loc = reg;
+ df_insn_rescan (DF_REF_INSN (ref));
}
-/* Mark each pseudo whose address is taken. */
-
-static int
-mark_addressof (rtx *rtl, void *data)
+\f
+static bool
+gate_handle_web (void)
{
- if (!*rtl)
- return 0;
- if (GET_CODE (*rtl) == ADDRESSOF
- && REG_P (XEXP (*rtl, 0)))
- ((char *)data)[REGNO (XEXP (*rtl, 0))] = 1;
- return 0;
+ return (optimize > 0 && flag_web);
}
/* Main entry point. */
-void
+static unsigned int
web_main (void)
{
- struct df *df;
struct web_entry *def_entry;
struct web_entry *use_entry;
- unsigned int i;
- int max = max_reg_num ();
+ unsigned int max = max_reg_num ();
char *used;
- char *use_addressof;
+ basic_block bb;
+ unsigned int uses_num = 0;
rtx insn;
- df = df_init ();
- df_analyze (df, 0, DF_UD_CHAIN | DF_EQUIV_NOTES);
+ df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
+ df_chain_add_problem (DF_UD_CHAIN);
+ df_analyze ();
+ df_set_flags (DF_DEFER_INSN_RESCAN);
- def_entry = xcalloc (df->n_defs, sizeof (struct web_entry));
- use_entry = xcalloc (df->n_uses, sizeof (struct web_entry));
- used = xcalloc (max, sizeof (char));
- use_addressof = xcalloc (max, sizeof (char));
+ /* Assign ids to the uses. */
+ FOR_ALL_BB (bb)
+ FOR_BB_INSNS (bb, insn)
+ {
+ unsigned int uid = INSN_UID (insn);
+ if (INSN_P (insn))
+ {
+ struct df_ref **use_rec;
+ for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
+ DF_REF_ID (use) = uses_num++;
+ }
+ for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
+ DF_REF_ID (use) = uses_num++;
+ }
+ }
+ }
- if (dump_file)
- df_dump (df, DF_UD_CHAIN | DF_DU_CHAIN, dump_file);
+ /* Record the number of uses and defs at the beginning of the optimization. */
+ def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE());
+ used = XCNEWVEC (char, max);
+ use_entry = XCNEWVEC (struct web_entry, uses_num);
/* Produce the web. */
- for (i = 0; i < df->n_uses; i++)
- union_defs (df, df->uses[i], def_entry, use_entry);
-
- /* We can not safely rename registers whose address is taken. */
- for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
- if (INSN_P (insn))
- for_each_rtx (&PATTERN (insn), mark_addressof, use_addressof);
+ FOR_ALL_BB (bb)
+ FOR_BB_INSNS (bb, insn)
+ {
+ unsigned int uid = INSN_UID (insn);
+ if (INSN_P (insn))
+ {
+ struct df_ref **use_rec;
+ for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
+ union_defs (use, def_entry, use_entry, unionfind_union);
+ }
+ for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
+ union_defs (use, def_entry, use_entry, unionfind_union);
+ }
+ }
+ }
/* Update the instruction stream, allocating new registers for split pseudos
in progress. */
- for (i = 0; i < df->n_uses; i++)
- replace_ref (df->uses[i], entry_register (use_entry + i, df->uses[i],
- used, use_addressof));
- for (i = 0; i < df->n_defs; i++)
- replace_ref (df->defs[i], entry_register (def_entry + i, df->defs[i],
- used, use_addressof));
-
- /* Dataflow information is corrupt here, but it can be easily updated
- by creating new entries for new registers and updates or calling
- df_insns_modify. */
+ FOR_ALL_BB (bb)
+ FOR_BB_INSNS (bb, insn)
+ {
+ unsigned int uid = INSN_UID (insn);
+ if (INSN_P (insn))
+ {
+ struct df_ref **use_rec;
+ struct df_ref **def_rec;
+ for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
+ replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
+ }
+ for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
+ {
+ struct df_ref *use = *use_rec;
+ if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
+ replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
+ }
+ for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+ {
+ struct df_ref *def = *def_rec;
+ if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
+ replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
+ }
+ }
+ }
+
free (def_entry);
free (use_entry);
free (used);
- free (use_addressof);
- df_finish (df);
+ return 0;
}
+\f
+struct tree_opt_pass pass_web =
+{
+ "web", /* name */
+ gate_handle_web, /* gate */
+ web_main, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_WEB, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_df_finish |
+ TODO_dump_func, /* todo_flags_finish */
+ 'Z' /* letter */
+};
+