Using known data structure hierarchy in GC and PCH?

Steven Bosscher
Mon Dec 10 18:26:00 GMT 2012


While trying to bootstrap with GCAC checking enabled and some
instrumentation to measure how often objects are being marked, I
noticed that a lot of cache misses happen because already-marked
objects are being tested again (e.g. via ggc_marked_p). This struck me
as rather odd, until I looked at what the GC markers for my favorite
data structures (the CFG) look like.

Basic blocks live in GC space because they can point to other GC-space
objects (rtx, gimple), and these objects can point back to the basic
block they're contained in. In addition, the (function-specific)
basic_block_info array points to all live basic blocks and of course
the edges have basic_block pointers as well. Finally, loop have
pointers to the loop header and latch basic_blocks.

The effect is that, on average, ggc_marked_p or one of its variants
gets called 17 times on each basic_block, *per ggc_collect call*!

This turns out to be typical for many data structures. It's more
difficult to get accurate numbers, but GCAC is especially slow when
building a large PCH and I'm guessing that this is in part due to
tree-to-tree pointers.

This all made me wonder why we can't use the known hierarchy of the
intermediate representations. Ideally, there should be only two
classes of objects: global state variables (not ideal, but a reality)
and objects reachable from the symbol table. AFAICT anything that
isn't in one of those two categories has probably become garbage
somewhere along the way.

As an experiment, I did a small modification to the GC walkers of the
CFG. I'd have started with the symbol table, but there's no
documentation and I don't know how memory is managed or what
invariants should hold (e.g. "everything that will be output must be
reachable via the symbol table"). Modifying the CFG was easier.

The effect for building my set of cc1-i files with a GCAC-checking
enabled compiler is a ~20% speedup.

It seems to be that this hierarchy could also be useful if/when GCC
will move away from generated walkers (i.e. gengtype). If we can
somehow enforce a hierarchy, the markers become much simpler. Also,
the hierarchy could be used to verify "no leaks" from alloc pools, and
probably for other things I can't think of right now.

Honza, can you please add some documentation about the symtab? What do
you think of the above from your symtab point of view?

Another "problem" with gengtype is that it doesn't know what types can
end up in a PCH. The CFG data structures can *never* be in a PCH, but
there still are PCH writer functions. This is true for many other data
structures as well. Has anyone ever measured/investigated what PCH
writer functions are actually used? Should we (as an intermediate step
towards streaming PCHs) explicitly GTY-mark types that should have PCH
writer functions, and not generate such functions for unmarked types?

-------------- next part --------------
A non-text attachment was scrubbed...
Name: GC_hierarchy.diff
Type: application/octet-stream
Size: 5109 bytes
Desc: not available
URL: <>

More information about the Gcc mailing list