* [dataflow]: PATCH COMMITTED to improve cache performance.
@ 2007-01-05 13:24 Kenneth Zadeck
0 siblings, 0 replies; only message in thread
From: Kenneth Zadeck @ 2007-01-05 13:24 UTC (permalink / raw)
To: GCC Patches, Berlin, Daniel, Zadeck, Kenneth, Seongbae Park,
Hubicha, Jan
[-- Attachment #1: Type: text/plain, Size: 1099 bytes --]
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.
[-- Attachment #2: cache2.diff --]
[-- Type: text/x-patch, Size: 12369 bytes --]
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. */
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2007-01-05 13:24 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-01-05 13:24 [dataflow]: PATCH COMMITTED to improve cache performance Kenneth Zadeck
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).