This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[dataflow]: PATCH COMMITTED to improve cache performance.
- From: Kenneth Zadeck <zadeck at naturalbridge dot com>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>, "Berlin, Daniel" <dberlin at dberlin dot org>, "Zadeck, Kenneth" <zadeck at naturalbridge dot com>, Seongbae Park <seongbae dot park at gmail dot com>, "Hubicha, Jan" <jh at suse dot cz>
- Date: Fri, 05 Jan 2007 08:23:58 -0500
- Subject: [dataflow]: PATCH COMMITTED to improve cache performance.
This is the second patch to improve the cache locality of the df. This
fixes web and also changes the way that DU and UD chains are printed.
The change to the printing is necessary because the ref tables are now
only available within the passes that use them, otherwise they are never
created. The printing used these tables. Now the chains are printed in
insn order, which is in fact easier to read.
This has been bootstrapped and regression tested on x86-64, x86-32, ppc
and ia-64.
Kenny
2007-01-05 Kenneth Zadeck <zadeck@naturalbridge.com>
* see.c (see_update_defs_relevancy): Type fixed.
* df-scan.c (df_reg_chain_unlink, df_ref_verify): Made tolerant of
refs table not being there.
(df_drop_organized_tables): New function.
* df-core.c (df_finish_pass): Drop refs tables after each pass.
* web.c (web_main): Reorganized access to not use ref tables and
go in order of insns.
* df.h (df_drop_organized_tables): New function.
* df-problems.c (df_chain_start_dump): Deleted function.
(df_chain_top_dump, df_chain_bottom_dump): New functions.
Index: see.c
===================================================================
--- see.c (revision 120477)
+++ see.c (working copy)
@@ -3536,7 +3536,7 @@ see_update_defs_relevancy (rtx insn, str
curr_entry_extra_info->relevancy = et;
curr_entry_extra_info->local_relevancy = et;
- DF_REF_ID(ref) = index;
+ DF_REF_ID (ref) = index;
if (et != EXTENDED_DEF)
{
Index: df-scan.c
===================================================================
--- df-scan.c (revision 120477)
+++ df-scan.c (working copy)
@@ -752,7 +752,7 @@ df_reg_chain_unlink (struct df_ref *ref)
if (DF_REF_TYPE (ref) == DF_REF_REG_DEF)
{
reg_info = DF_REG_DEF_GET (DF_REF_REGNO (ref));
- if (id >= 0)
+ if (id >= 0 && df->def_info.refs)
{
gcc_assert (id < (int)df->def_info.table_size);
DF_DEFS_SET (id, NULL);
@@ -764,7 +764,7 @@ df_reg_chain_unlink (struct df_ref *ref)
reg_info = DF_REG_EQ_USE_GET (DF_REF_REGNO (ref));
else
reg_info = DF_REG_USE_GET (DF_REF_REGNO (ref));
- if (id >= 0)
+ if (id >= 0 && df->use_info.refs)
{
gcc_assert (id < (int)df->use_info.table_size);
DF_USES_SET (id, NULL);
@@ -1399,6 +1399,33 @@ df_maybe_reorganize_def_refs (void)
df_reorganize_refs (&df->def_info, df->def_regs, NULL);
}
+
+/* Discard the organized tables of refs and uses. */
+
+void
+df_drop_organized_tables (void)
+{
+ df->def_info.add_refs_inline = false;
+ df->def_info.refs_organized_with_eq_uses = false;
+ df->def_info.refs_organized_alone = false;
+ df->use_info.add_refs_inline = false;
+ df->use_info.refs_organized_with_eq_uses = false;
+ df->use_info.refs_organized_alone = false;
+
+ if (df->def_info.refs)
+ {
+ free (df->def_info.refs);
+ df->def_info.refs = NULL;
+ df->def_info.refs_size = 0;
+ }
+ if (df->use_info.refs)
+ {
+ free (df->use_info.refs);
+ df->use_info.refs = NULL;
+ df->use_info.refs_size = 0;
+ }
+}
+
#ifdef DEBUG_DF_RESCAN
/* Return true if the contents of two df_ref's are identical.
@@ -3273,7 +3300,7 @@ df_compute_regs_ever_live (bool reset)
Dataflow ref information verification functions.
df_reg_chain_mark (refs, regno, is_def, is_eq_use)
- df_ref_chain_verify_and_clear_marks (refs, mask)
+ df_ref_chain_verify_and_unmark (refs, mask)
df_ref_verify (ref, bool)
df_ref_chain_mark_duplicate (src_refs, dest_refs)
df_ref_chain_free (refs)
@@ -3405,7 +3432,7 @@ df_ref_verify (struct df_ref *this_ref,
}
/* Verify ref_info->refs array. */
- if ((DF_REF_ID (old_ref) >= 0)
+ if ((DF_REF_ID (old_ref) >= 0 && ref_info->refs)
&& (ref_info->refs[DF_REF_ID (old_ref)] != old_ref))
{
if (abort_if_fail)
Index: df-core.c
===================================================================
--- df-core.c (revision 120477)
+++ df-core.c (working copy)
@@ -618,6 +618,8 @@ df_finish_pass (void)
if (!df)
return;
+ df_drop_organized_tables ();
+
#ifdef ENABLE_CHECKING
saved_flags = df->changeable_flags;
#endif
@@ -647,13 +649,6 @@ df_finish_pass (void)
df_mark_solutions_dirty ();
}
- df->def_info.add_refs_inline = false;
- df->def_info.refs_organized_with_eq_uses = false;
- df->def_info.refs_organized_alone = false;
- df->use_info.add_refs_inline = false;
- df->use_info.refs_organized_with_eq_uses = false;
- df->use_info.refs_organized_alone = false;
-
#ifdef ENABLE_CHECKING
/* Verification will fail in DF_NO_INSN_RESCAN. */
if (!(saved_flags & DF_NO_INSN_RESCAN))
Index: web.c
===================================================================
--- web.c (revision 120477)
+++ web.c (working copy)
@@ -262,41 +262,74 @@ web_main (void)
{
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;
+ basic_block bb;
+ unsigned int uses_num = 0;
+ rtx insn;
+ struct df_ref *ref;
+
df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
df_chain_add_problem (DF_UD_CHAIN);
df_analyze ();
- df_maybe_reorganize_use_refs ();
df_set_flags (DF_DEFER_INSN_RESCAN);
- def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE ());
- use_entry = XCNEWVEC (struct web_entry, DF_USES_TABLE_SIZE ());
+ /* Assign ids to the uses. */
+ FOR_ALL_BB (bb)
+ FOR_BB_INSNS (bb, insn)
+ {
+ unsigned int uid = INSN_UID (insn);
+ if (INSN_P (insn))
+ {
+ for (ref = DF_INSN_UID_USES (uid); ref; ref = ref->next_ref)
+ if (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER)
+ DF_REF_ID (ref) = uses_num++;
+ for (ref = DF_INSN_UID_EQ_USES (uid); ref; ref = ref->next_ref)
+ if (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER)
+ DF_REF_ID (ref) = uses_num++;
+ }
+ }
+
+ /* 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_USES_TABLE_SIZE (); i++)
+ FOR_ALL_BB (bb)
+ FOR_BB_INSNS (bb, insn)
{
- struct df_ref *use = DF_USES_GET (i);
- if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
- union_defs (use, def_entry, use_entry, unionfind_union);
+ unsigned int uid = INSN_UID (insn);
+ if (INSN_P (insn))
+ {
+ for (ref = DF_INSN_UID_USES (uid); ref; ref = ref->next_ref)
+ if (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER)
+ union_defs (ref, def_entry, use_entry, unionfind_union);
+ for (ref = DF_INSN_UID_EQ_USES (uid); ref; ref = ref->next_ref)
+ if (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER)
+ union_defs (ref, def_entry, use_entry, unionfind_union);
+ }
}
/* Update the instruction stream, allocating new registers for split pseudos
in progress. */
- for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
- {
- struct df_ref *use = DF_USES_GET (i);
- if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
- replace_ref (use, entry_register (use_entry + i, use, used));
- }
- for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
+ FOR_ALL_BB (bb)
+ FOR_BB_INSNS (bb, insn)
{
- struct df_ref *def = DF_DEFS_GET (i);
- if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
- replace_ref (def, entry_register (def_entry + i, def, used));
+ unsigned int uid = INSN_UID (insn);
+ if (INSN_P (insn))
+ {
+ for (ref = DF_INSN_UID_USES (uid); ref; ref = ref->next_ref)
+ if (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER)
+ replace_ref (ref, entry_register (use_entry + DF_REF_ID (ref), ref, used));
+ for (ref = DF_INSN_UID_EQ_USES (uid); ref; ref = ref->next_ref)
+ if (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER)
+ replace_ref (ref, entry_register (use_entry + DF_REF_ID (ref), ref, used));
+ for (ref = DF_INSN_UID_DEFS (uid); ref; ref = ref->next_ref)
+ if (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER)
+ replace_ref (ref, entry_register (def_entry + DF_REF_ID (ref), ref, used));
+ }
}
free (def_entry);
Index: df.h
===================================================================
--- df.h (revision 120477)
+++ df.h (working copy)
@@ -907,6 +907,7 @@ extern void df_recompute_luids (basic_bl
extern void df_insn_change_bb (rtx);
extern void df_maybe_reorganize_use_refs (void);
extern void df_maybe_reorganize_def_refs (void);
+extern void df_drop_organized_tables (void);
extern void df_ref_change_reg_with_loc (int, int, rtx);
extern void df_notes_rescan (rtx);
extern void df_hard_reg_init (void);
Index: df-problems.c
===================================================================
--- df-problems.c (revision 120477)
+++ df-problems.c (working copy)
@@ -3754,56 +3754,101 @@ df_chain_free (void)
/* Debugging info. */
static void
-df_chain_start_dump (FILE *file)
+df_chain_top_dump (basic_block bb, FILE *file)
{
- unsigned int j;
-
if (df_chain_problem_p (DF_DU_CHAIN))
{
- fprintf (file, ";; Def-use chains:\n");
- for (j = 0; j < DF_DEFS_TABLE_SIZE (); j++)
+ rtx insn;
+ struct df_ref *ref = df_get_artificial_defs (bb->index);
+ if (ref)
{
- struct df_ref *def = DF_DEFS_GET (j);
- if (def)
+ fprintf (file, ";; DU chains for artificial defs\n");
+ while (ref)
{
- fprintf (file, ";; d%d bb %d luid %d insn %d reg %d ",
- j, DF_REF_BBNO (def),
- DF_REF_INSN (def) ?
- DF_INSN_LUID (DF_REF_INSN (def)):
- -1,
- DF_REF_INSN (def) ? DF_REF_INSN_UID (def) : -1,
- DF_REF_REGNO (def));
- if (def->flags & DF_REF_READ_WRITE)
- fprintf (file, "read/write ");
- df_chain_dump (DF_REF_CHAIN (def), file);
+ fprintf (file, ";; reg %d ", DF_REF_REGNO (ref));
+ df_chain_dump (DF_REF_CHAIN (ref), file);
fprintf (file, "\n");
+ ref = ref->next_ref;
+ }
+ }
+
+ FOR_BB_INSNS (bb, insn)
+ {
+ unsigned int uid = INSN_UID (insn);
+ if (INSN_P (insn))
+ {
+ ref = DF_INSN_UID_DEFS (uid);
+ if (ref)
+ {
+ fprintf (file, ";; DU chains for insn luid %d uid %d\n",
+ DF_INSN_LUID (insn), uid);
+
+ while (ref)
+ {
+ fprintf (file, ";; reg %d ", DF_REF_REGNO (ref));
+ if (ref->flags & DF_REF_READ_WRITE)
+ fprintf (file, "read/write ");
+ df_chain_dump (DF_REF_CHAIN (ref), file);
+ fprintf (file, "\n");
+ ref = ref->next_ref;
+ }
+ }
}
}
}
+}
+
+static void
+df_chain_bottom_dump (basic_block bb, FILE *file)
+{
if (df_chain_problem_p (DF_UD_CHAIN))
{
- fprintf (file, ";; Use-def chains:\n");
- for (j = 0; j < DF_USES_TABLE_SIZE (); j++)
+ rtx insn;
+ struct df_ref *ref = df_get_artificial_uses (bb->index);
+
+ if (ref)
{
- struct df_ref *use = DF_USES_GET (j);
- if (use)
+ fprintf (file, ";; UD chains for artificial uses\n");
+ while (ref)
{
- fprintf (file, ";; u%d bb %d luid %d insn %d reg %d ",
- j, DF_REF_BBNO (use),
- DF_REF_INSN (use) ?
- DF_INSN_LUID (DF_REF_INSN (use))
- : -1,
- DF_REF_INSN (DF_USES_GET (j)) ?
- DF_REF_INSN_UID (DF_USES_GET (j))
- : -1,
- DF_REF_REGNO (use));
- if (use->flags & DF_REF_READ_WRITE)
- fprintf (file, "read/write ");
- if (use->flags & DF_REF_IN_NOTE)
- fprintf (file, "note ");
- df_chain_dump (DF_REF_CHAIN (use), file);
+ fprintf (file, ";; reg %d ", DF_REF_REGNO (ref));
+ df_chain_dump (DF_REF_CHAIN (ref), file);
fprintf (file, "\n");
+ ref = ref->next_ref;
+ }
+ }
+
+ FOR_BB_INSNS (bb, insn)
+ {
+ unsigned int uid = INSN_UID (insn);
+ if (INSN_P (insn))
+ {
+ struct df_ref *refn = DF_INSN_UID_EQ_USES (uid);
+ ref = DF_INSN_UID_USES (uid);
+ if (ref || refn)
+ {
+ fprintf (file, ";; UD chains for insn luid %d uid %d\n",
+ DF_INSN_LUID (insn), uid);
+
+ while (ref)
+ {
+ fprintf (file, ";; reg %d ", DF_REF_REGNO (ref));
+ if (ref->flags & DF_REF_READ_WRITE)
+ fprintf (file, "read/write ");
+ df_chain_dump (DF_REF_CHAIN (ref), file);
+ fprintf (file, "\n");
+ ref = ref->next_ref;
+ }
+ ref = refn;
+ while (ref)
+ {
+ fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (ref));
+ df_chain_dump (DF_REF_CHAIN (ref), file);
+ fprintf (file, "\n");
+ ref = ref->next_ref;
+ }
+ }
}
}
}
@@ -3826,9 +3871,9 @@ static struct df_problem problem_CHAIN =
df_chain_finalize, /* Finalize function. */
df_chain_free, /* Free all of the problem information. */
df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
- df_chain_start_dump, /* Debugging. */
- NULL, /* Debugging start block. */
- NULL, /* Debugging end block. */
+ NULL, /* Debugging. */
+ df_chain_top_dump, /* Debugging start block. */
+ df_chain_bottom_dump, /* Debugging end block. */
NULL, /* Incremental solution verify start. */
NULL, /* Incremental solution verfiy end. */
&problem_RD /* Dependent problem. */