remove reverse_die_lists
Geoffrey Keating
gkeating@apple.com
Sat Apr 22 08:45:00 GMT 2006
This patch gives another couple of percent performance increase
(they're starting to add up now) when using DWARF with a big PCH file;
it's now only about 13% slower than using STABS. Most of the patch is
concerned with removing reverse_die_lists, by linking DIEs into a
circular linked list and having the entry point of the list be the
last element of the list (so that the first element is one indirection
away).
However, this is not enough to get a performance gain! The big
benefit of removing reverse_all_dies is not that it removes that loop,
since even with a PCH there are only tens of thousands of DIEs to loop
over, but that because the loop writes to the DIEs it causes lots of
copy-on-write faults. The problem is that prune_unmark_dies would
also write to the same pages, and is actually worse with this patch,
because the loop in prune_unmark_dies is changed to read the page
before writing to it, meaning there have to be two trips into the
kernel. So, this patch makes prune_unmark_dies write only
conditionally. I actually think that the first call to
prune_unmark_dies is unnecessary and hope to replace it with a
verification routine (on only when checking is enabled) in a future
patch.
Bootstrapped & tested on powerpc-darwin8.
--
- Geoffrey Keating <geoffk@apple.com>
===File ~/patches/gcc-dwarf-circulardies.patch==============
2006-04-21 Geoffrey Keating <geoffk@apple.com>
* dwarf2out.c (struct die_struct): Document that die_sib makes
a circular linked list.
(FOR_EACH_CHILD): New.
(reverse_die_lists): Delete.
(reverse_all_dies): Delete.
(add_dwarf_attr): Correct documentation.
(remove_child_with_prev): New.
(remove_child_TAG): Update for change to die_struct, use
remove_child_with_prev.
(add_child_die): Update for change to die_struct.
(splice_child_die): Use remove_child_with_prev and add_child_die.
(print_die): Use FOR_EACH_CHILD.
(die_checksum): Likewise.
(assign_symbol_names): Likewise.
(output_location_lists): Likewise.
(build_abbrev_table): Likewise.
(calc_die_sizes): Likewise.
(mark_dies): Likewise.
(unmark_dies): Likewise.
(unmark_all_dies): Likewise.
(output_die): Likewise.
(prune_unused_types_mark): Likewise.
(prune_unused_types_walk): Likewise.
(same_die_p): Update for change to die_struct.
(break_out_includes): Likewise.
(prune_unused_types_prune): Likewise.
(add_sibling_attributes): Use FOR_EACH_CHILD, simplify logic.
(prune_unmark_dies): Use FOR_EACH_CHILD, don't clear die_mark if
it's already clear.
(dwarf2out_finish): Don't call reverse_all_dies.
Index: dwarf2out.c
===================================================================
--- dwarf2out.c (revision 113108)
+++ dwarf2out.c (working copy)
@@ -3688,7 +3688,9 @@
DEF_VEC_O(dw_attr_node);
DEF_VEC_ALLOC_O(dw_attr_node,gc);
-/* The Debugging Information Entry (DIE) structure */
+/* The Debugging Information Entry (DIE) structure. DIEs form a tree.
+ The children of each node form a circular list linked by
+ die_sib. die_child points to the node *before* the "first" child node. */
typedef struct die_struct GTY(())
{
@@ -3708,6 +3710,15 @@
}
die_node;
+/* Evaluate 'expr' while 'c' is set to each child of DIE in order. */
+#define FOR_EACH_CHILD(die, c, expr) do { \
+ c = die->die_child; \
+ if (c) do { \
+ c = c->die_sib; \
+ expr; \
+ } while (c != die->die_child); \
+} while (0)
+
/* The pubname structure */
typedef struct pubname_struct GTY(())
@@ -4042,8 +4053,6 @@
static void print_spaces (FILE *);
static void print_die (dw_die_ref, FILE *);
static void print_dwarf_line_table (FILE *);
-static void reverse_die_lists (dw_die_ref);
-static void reverse_all_dies (dw_die_ref);
static dw_die_ref push_new_compile_unit (dw_die_ref, dw_die_ref);
static dw_die_ref pop_compile_unit (dw_die_ref);
static void loc_checksum (dw_loc_descr_ref, struct md5_ctx *);
@@ -4838,8 +4847,7 @@
return context;
}
-/* Add an attribute/value pair to a DIE. We build the lists up in reverse
- addition order, and correct that in reverse_all_dies. */
+/* Add an attribute/value pair to a DIE. */
static inline void
add_dwarf_attr (dw_die_ref die, dw_attr_ref attr)
@@ -5406,56 +5414,77 @@
}
}
-/* Remove child die whose die_tag is specified tag. */
+/* Remove CHILD from its parent. PREV must have the property that
+ PREV->DIE_SIB == CHILD. Does not alter CHILD. */
static void
-remove_child_TAG (dw_die_ref die, enum dwarf_tag tag)
+remove_child_with_prev (dw_die_ref child, dw_die_ref prev)
{
- dw_die_ref current, prev, next;
- current = die->die_child;
- prev = NULL;
- while (current != NULL)
+ gcc_assert (child->die_parent == prev->die_parent);
+ gcc_assert (prev->die_sib == child);
+ if (prev == child)
{
- if (current->die_tag == tag)
- {
- next = current->die_sib;
- if (prev == NULL)
- die->die_child = next;
- else
- prev->die_sib = next;
- current = next;
- }
- else
- {
- prev = current;
- current = current->die_sib;
- }
+ gcc_assert (child->die_parent->die_child == child);
+ prev = NULL;
}
+ else
+ prev->die_sib = child->die_sib;
+ if (child->die_parent->die_child == child)
+ child->die_parent->die_child = prev;
}
-/* Add a child DIE below its parent. We build the lists up in reverse
- addition order, and correct that in reverse_all_dies. */
+/* Remove child DIE whose die_tag is TAG. Do nothing if no child
+ matches TAG. */
-static inline void
+static void
+remove_child_TAG (dw_die_ref die, enum dwarf_tag tag)
+{
+ dw_die_ref c;
+
+ c = die->die_child;
+ if (c) do {
+ dw_die_ref prev = c;
+ c = c->die_sib;
+ while (c->die_tag == tag)
+ {
+ remove_child_with_prev (c, prev);
+ /* Might have removed every child. */
+ if (c == c->die_sib)
+ return;
+ c = c->die_sib;
+ }
+ } while (c != die->die_child);
+}
+
+/* Add a CHILD_DIE as the last child of DIE. */
+
+static void
add_child_die (dw_die_ref die, dw_die_ref child_die)
{
- if (die != NULL && child_die != NULL)
- {
- gcc_assert (die != child_die);
+ /* FIXME this should probably be an assert. */
+ if (! die || ! child_die)
+ return;
+ gcc_assert (die != child_die);
- child_die->die_parent = die;
- child_die->die_sib = die->die_child;
- die->die_child = child_die;
+ child_die->die_parent = die;
+ if (die->die_child)
+ {
+ child_die->die_sib = die->die_child->die_sib;
+ die->die_child->die_sib = child_die;
}
+ else
+ child_die->die_sib = child_die;
+ die->die_child = child_die;
}
/* Move CHILD, which must be a child of PARENT or the DIE for which PARENT
- is the specification, to the front of PARENT's list of children. */
+ is the specification, to the end of PARENT's list of children.
+ This is done by removing and re-adding it. */
static void
splice_child_die (dw_die_ref parent, dw_die_ref child)
{
- dw_die_ref *p;
+ dw_die_ref p;
/* We want the declaration DIE from inside the class, not the
specification DIE at toplevel. */
@@ -5470,17 +5499,15 @@
gcc_assert (child->die_parent == parent
|| (child->die_parent
== get_AT_ref (parent, DW_AT_specification)));
-
- for (p = &(child->die_parent->die_child); *p; p = &((*p)->die_sib))
- if (*p == child)
+
+ for (p = child->die_parent->die_child; ; p = p->die_sib)
+ if (p->die_sib == child)
{
- *p = child->die_sib;
+ remove_child_with_prev (child, p);
break;
}
- child->die_parent = parent;
- child->die_sib = parent->die_child;
- parent->die_child = child;
+ add_child_die (parent, child);
}
/* Return a pointer to a newly created DIE node. */
@@ -5727,9 +5754,7 @@
if (die->die_child != NULL)
{
print_indent += 4;
- for (c = die->die_child; c != NULL; c = c->die_sib)
- print_die (c, outfile);
-
+ FOR_EACH_CHILD (die, c, print_die (c, outfile));
print_indent -= 4;
}
if (print_indent == 0)
@@ -5779,42 +5804,6 @@
print_dwarf_line_table (stderr);
}
-/* We build up the lists of children and attributes by pushing new ones
- onto the beginning of the list. Reverse the lists for DIE so that
- they are in order of addition. */
-
-static void
-reverse_die_lists (dw_die_ref die)
-{
- dw_die_ref c, cp, cn;
-
- for (c = die->die_child, cp = 0; c; c = cn)
- {
- cn = c->die_sib;
- c->die_sib = cp;
- cp = c;
- }
-
- die->die_child = cp;
-}
-
-/* reverse_die_lists only reverses the single die you pass it. Since we used to
- reverse all dies in add_sibling_attributes, which runs through all the dies,
- it would reverse all the dies. Now, however, since we don't call
- reverse_die_lists in add_sibling_attributes, we need a routine to
- recursively reverse all the dies. This is that routine. */
-
-static void
-reverse_all_dies (dw_die_ref die)
-{
- dw_die_ref c;
-
- reverse_die_lists (die);
-
- for (c = die->die_child; c; c = c->die_sib)
- reverse_all_dies (c);
-}
-
/* Start a new compilation unit DIE for an include file. OLD_UNIT is the CU
for the enclosing include file, if any. BINCL_DIE is the DW_TAG_GNU_BINCL
DIE that marks the start of the DIEs for this include file. */
@@ -5943,8 +5932,7 @@
for (ix = 0; VEC_iterate (dw_attr_node, die->die_attr, ix, a); ix++)
attr_checksum (a, ctx, mark);
- for (c = die->die_child; c; c = c->die_sib)
- die_checksum (c, ctx, mark);
+ FOR_EACH_CHILD (die, c, die_checksum (c, ctx, mark));
}
#undef CHECKSUM
@@ -6067,13 +6055,28 @@
if (!same_attr_p (a1, VEC_index (dw_attr_node, die2->die_attr, ix), mark))
return 0;
- for (c1 = die1->die_child, c2 = die2->die_child;
- c1 && c2;
- c1 = c1->die_sib, c2 = c2->die_sib)
- if (!same_die_p (c1, c2, mark))
- return 0;
- if (c1 || c2)
- return 0;
+ c1 = die1->die_child;
+ c2 = die2->die_child;
+ if (! c1)
+ {
+ if (c2)
+ return 0;
+ }
+ else
+ for (;;)
+ {
+ if (!same_die_p (c1, c2, mark))
+ return 0;
+ c1 = c1->die_sib;
+ c2 = c2->die_sib;
+ if (c1 == die1->die_child)
+ {
+ if (c2 == die2->die_child)
+ break;
+ else
+ return 0;
+ }
+ }
return 1;
}
@@ -6238,8 +6241,7 @@
die->die_symbol = gen_internal_sym ("LDIE");
}
- for (c = die->die_child; c != NULL; c = c->die_sib)
- assign_symbol_names (c);
+ FOR_EACH_CHILD (die, c, assign_symbol_names (c));
}
struct cu_hash_table_entry
@@ -6337,36 +6339,35 @@
static void
break_out_includes (dw_die_ref die)
{
- dw_die_ref *ptr;
+ dw_die_ref c;
dw_die_ref unit = NULL;
limbo_die_node *node, **pnode;
htab_t cu_hash_table;
- for (ptr = &(die->die_child); *ptr;)
- {
- dw_die_ref c = *ptr;
+ c = die->die_child;
+ if (c) do {
+ dw_die_ref prev = c;
+ c = c->die_sib;
+ while (c->die_tag == DW_TAG_GNU_BINCL || c->die_tag == DW_TAG_GNU_EINCL
+ || (unit && is_comdat_die (c)))
+ {
+ dw_die_ref next = c->die_sib;
- if (c->die_tag == DW_TAG_GNU_BINCL || c->die_tag == DW_TAG_GNU_EINCL
- || (unit && is_comdat_die (c)))
- {
- /* This DIE is for a secondary CU; remove it from the main one. */
- *ptr = c->die_sib;
+ /* This DIE is for a secondary CU; remove it from the main one. */
+ remove_child_with_prev (c, prev);
+
+ if (c->die_tag == DW_TAG_GNU_BINCL)
+ unit = push_new_compile_unit (unit, c);
+ else if (c->die_tag == DW_TAG_GNU_EINCL)
+ unit = pop_compile_unit (unit);
+ else
+ add_child_die (unit, c);
+ c = next;
+ if (c == die->die_child)
+ break;
+ }
+ } while (c != die->die_child);
- if (c->die_tag == DW_TAG_GNU_BINCL)
- unit = push_new_compile_unit (unit, c);
- else if (c->die_tag == DW_TAG_GNU_EINCL)
- unit = pop_compile_unit (unit);
- else
- add_child_die (unit, c);
- }
- else
- {
- /* Leave this DIE in the main CU. */
- ptr = &(c->die_sib);
- continue;
- }
- }
-
#if 0
/* We can only use this in debugging, since the frontend doesn't check
to make sure that we leave every include file we enter. */
@@ -6406,13 +6407,13 @@
{
dw_die_ref c;
- if (die->die_tag != DW_TAG_compile_unit
- && die->die_sib && die->die_child != NULL)
- /* Add the sibling link to the front of the attribute list. */
+ if (! die->die_child)
+ return;
+
+ if (die->die_parent && die != die->die_parent->die_child)
add_AT_die_ref (die, DW_AT_sibling, die->die_sib);
- for (c = die->die_child; c != NULL; c = c->die_sib)
- add_sibling_attributes (c);
+ FOR_EACH_CHILD (die, c, add_sibling_attributes (c));
}
/* Output all location lists for the DIE and its children. */
@@ -6428,9 +6429,7 @@
if (AT_class (a) == dw_val_class_loc_list)
output_loc_list (AT_loc_list (a));
- for (c = die->die_child; c != NULL; c = c->die_sib)
- output_location_lists (c);
-
+ FOR_EACH_CHILD (die, c, output_location_lists (c));
}
/* The format of each DIE (and its attribute value pairs) is encoded in an
@@ -6506,8 +6505,7 @@
}
die->die_abbrev = abbrev_id;
- for (c = die->die_child; c != NULL; c = c->die_sib)
- build_abbrev_table (c);
+ FOR_EACH_CHILD (die, c, build_abbrev_table (c));
}
/* Return the power-of-two number of bytes necessary to represent VALUE. */
@@ -6623,8 +6621,7 @@
die->die_offset = next_die_offset;
next_die_offset += size_of_die (die);
- for (c = die->die_child; c != NULL; c = c->die_sib)
- calc_die_sizes (c);
+ FOR_EACH_CHILD (die, c, calc_die_sizes (c));
if (die->die_child != NULL)
/* Count the null byte used to terminate sibling lists. */
@@ -6644,8 +6641,7 @@
gcc_assert (!die->die_mark);
die->die_mark = 1;
- for (c = die->die_child; c; c = c->die_sib)
- mark_dies (c);
+ FOR_EACH_CHILD (die, c, mark_dies (c));
}
/* Clear the marks for a die and its children. */
@@ -6658,8 +6654,7 @@
gcc_assert (die->die_mark);
die->die_mark = 0;
- for (c = die->die_child; c; c = c->die_sib)
- unmark_dies (c);
+ FOR_EACH_CHILD (die, c, unmark_dies (c));
}
/* Clear the marks for a die, its children and referred dies. */
@@ -6675,8 +6670,7 @@
return;
die->die_mark = 0;
- for (c = die->die_child; c; c = c->die_sib)
- unmark_all_dies (c);
+ FOR_EACH_CHILD (die, c, unmark_all_dies (c));
for (ix = 0; VEC_iterate (dw_attr_node, die->die_attr, ix, a); ix++)
if (AT_class (a) == dw_val_class_die_ref)
@@ -7148,8 +7142,7 @@
}
}
- for (c = die->die_child; c != NULL; c = c->die_sib)
- output_die (c);
+ FOR_EACH_CHILD (die, c, output_die (c));
/* Add null byte to terminate sibling list. */
if (die->die_child != NULL)
@@ -13846,9 +13839,10 @@
prune_unmark_dies (dw_die_ref die)
{
dw_die_ref c;
- die->die_mark = 0;
- for (c = die->die_child; c; c = c->die_sib)
- prune_unmark_dies (c);
+
+ if (die->die_mark)
+ die->die_mark = 0;
+ FOR_EACH_CHILD (die, c, prune_unmark_dies (c));
}
@@ -13916,16 +13910,12 @@
Remember that we've walked the kids. */
die->die_mark = 2;
- /* Walk them. */
- for (c = die->die_child; c; c = c->die_sib)
- {
- /* If this is an array type, we need to make sure our
- kids get marked, even if they're types. */
- if (die->die_tag == DW_TAG_array_type)
- prune_unused_types_mark (c, 1);
- else
- prune_unused_types_walk (c);
- }
+ /* If this is an array type, we need to make sure our
+ kids get marked, even if they're types. */
+ if (die->die_tag == DW_TAG_array_type)
+ FOR_EACH_CHILD (die, c, prune_unused_types_mark (c, 1));
+ else
+ FOR_EACH_CHILD (die, c, prune_unused_types_walk (c));
}
}
@@ -13978,8 +13968,7 @@
prune_unused_types_walk_attribs (die);
/* Mark children. */
- for (c = die->die_child; c; c = c->die_sib)
- prune_unused_types_walk (c);
+ FOR_EACH_CHILD (die, c, prune_unused_types_walk (c));
}
/* Increment the string counts on strings referred to from DIE's
@@ -14016,29 +14005,36 @@
static void
prune_unused_types_prune (dw_die_ref die)
{
- dw_die_ref *p;
+ dw_die_ref c;
gcc_assert (die->die_mark);
- p = &die->die_child;
- while (*p)
- {
- dw_die_ref c = *p;
- if (c && ! c->die_mark)
+ if (! die->die_child)
+ return;
+
+ c = die->die_child;
+ do {
+ dw_die_ref prev = c;
+ for (c = c->die_sib; ! c->die_mark; c = c->die_sib)
+ if (c == die->die_child)
{
- do {
- c = c->die_sib;
- } while (c && ! c->die_mark);
- *p = c;
+ /* No marked children between 'prev' and the end of the list. */
+ if (prev == c)
+ /* No marked children at all. */
+ die->die_child = NULL;
+ else
+ {
+ prev->die_sib = c->die_sib;
+ die->die_child = prev;
+ }
+ return;
}
-
- if (c)
- {
- prune_unused_types_update_strings (c);
- prune_unused_types_prune (c);
- p = &c->die_sib;
- }
- }
+
+ if (c != prev->die_sib)
+ prev->die_sib = c;
+ prune_unused_types_update_strings (c);
+ prune_unused_types_prune (c);
+ } while (c != die->die_child);
}
@@ -14166,10 +14162,6 @@
emit full debugging info for them. */
retry_incomplete_types ();
- /* We need to reverse all the dies before break_out_includes, or
- we'll see the end of an include file before the beginning. */
- reverse_all_dies (comp_unit_die);
-
if (flag_eliminate_unused_debug_types)
prune_unused_types ();
============================================================
More information about the Gcc-patches
mailing list