Using known data structure hierarchy in GC and PCH?

[Richard Biener]

On Mon, Dec 10, 2012 at 7:25 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> Hello,
>
> 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?

Just to mention - we do have some of the GC edges marked GTY(("skip")) to
avoid visiting them if we know they point to something we visit anyway from
a different point.  Of course that doesn't work for pointers saved in a PCH.

Richard.

> Ciao!
> Steven