On Tue, 16 Oct 2012, Richard Biener wrote:
>
> This patch shows work-in-progress (read: implementation uglyness
> hopefully to vanish ...) regarding to moving LTO type merging
> work from WPA to compile stage.
>
> The patch re-organizes lto_output_tree (the write_tree streamer
> hook for LTO) in a way so that we output all tree fields
> in easy to discover places. This means that we have forward
> references to trees not yet (fully) written, something the
> current state avoids by "inline-expanding" forward referenced
> trees at the point of reference (which results in interweaved
> trees on disk). To be able to achieve this lto_output_tree
> now performs a DFS walk along tree edges to collect trees
> that need to be output and outputs them in SCC chunks
> in a new LTO stream container, LTO_tree_scc.
>
> This will allow the reader side at WPA stage to call uniquify
> nodes on each tree SCC, avoiding completely the DFS walks done
> there (hopefully, we do DFS walks for both hashing and comparing
> there - note that WPA gathers type SCCs, not tree SCCs - a subtle
> difference that remains to be seen on whether it is important ...)
>
> One complication is how we handle streaming INTEGER_CSTs.
> When an INTEGER_CST refers to an already input type we can
> allocate it using the build_int_cst_wide routine which takes
> care of putting it into the appropriate hashtables for caching.
> If an INTEGER_CST is part of a SCC (TYPE_DOMAIN values are
> the most obvious cases) we now stream them as regular trees
> (they cannot already exist in any cache as the type is being
> read in) - but the patch does not yet populate the caches
> in case the type ends up prevailing (thus it will produce
> some unshared INTEGER_CSTs for now).
>
> One uglyness of the patch is how I mis-use the streamer hooks
> to switch the tree streamer routines from actually writing
> tree references to performing the DFS walk. For the DFS walk
> I need information on the edge, thus a 'from' tree argument
> is added to the write_tree hook. Eventually my plan was
> to transform this to a walk_tree-like interface.
>
> Diego - is PTH still live? Thus, do I need to bother about
> inventing things in a way that can be hook-ized? Do you
> forsee any complication for PTH or C++ modules the way
> I re-arranged things? Any good (C++) ideas on how to
> design this lto_walk_tree?
>
> The patch below survives LTO bootstrap (ok, we are only
> in stage2 yet ...) so it serves as suitable vehicle for
> gathering statistics about tree SCC sizes. It's probably
> the state I'll build on re-organizing uniquify_nodes to
> avoid the various DFS walks done there.
To followup myself, here are statistics for WPAing cc1:
There are a total of 2530667 SCCs, 2405450 of them are
singletons (that's 95%), 98% have less than 5 trees.
The biggest SCCs have 4178 trees.
2405450 1
31929 2
35922 3
15554 4
7648 5
6288 6
5865 7
4677 8
1819 9
3529 10
659 11
1467 12
916 13
320 14
305 15
940 16
138 17
815 18
434 19
341 20
109 21
375 22
...
1 1452
1 1466
1 1470
1 1544
260 1892
1 2042
5 2090
24 4178
LTO file-sizes grow with the current patch and it's certainly
worth optimizing the singleton case some more. It will definitely
be worth optimizing singletons on the merging side as well.
The above info was collected by adding
if (flag_wpa)
fprintf (stderr, "%lu\n", size);
to the LTO_tree_scc path in lto_input_tree.
Richard.
