Implement a new partitioner for parallel compilation

When using the LTO infrastructure to compile files in parallel, we
can't simply use any of the LTO partitioner, once extra dependency
analysis is required to ensure that some nodes are correctly
partitioned together.

Therefore, here we implement a new partitioner called
"lto_merge_comdat_map" that does all these required analysis.
The partitioner works as follows:

1. We create a number of disjoint sets and inserts each node into a
   separate set, which may be merged together in the future.

2. Find COMDAT groups, and mark them to be partitioned together.

3. Check all nodes that would require any COMDAT group to be
   copied to its partition (which we name "COMDAT frontier"),
   and mark them to be partitioned together.
   This avoids duplication of COMDAT groups and crashes on the LTO
   partitioning infrastructure.

4. Check if the user allows the partitioner to promote non-public
   functions or variables to global to improve parallelization
   opportunity with a cost of modifying the output code layout.

5. Balance generated partitions for performance unless not told to.

The choice of 1. was by design, so we could use a union-find
data structure, which are know for being very fast on set unite
operations.

For 3. to work properly, we also had to modify
lto_promote_cross_file_statics to handle this case.

The parameters --param=promote-statics and --param=balance-partitions
control 4. and 5., respectively

gcc/ChangeLog:
2020-08-20  Giuliano Belinassi  <giuliano.belinassi@usp.br>

	* Makefile.in: Add lto-partition.o
	* cgraph.h (struct symtab_node::aux2): New variable.
	* lto-partition.c: Move from gcc/lto/lto-partition.c
	(add_symbol_to_partition_1): Only compute insn size
	if information is available.
	(node_cmp): Same as above.
	(class union_find): New.
	(ds_print_roots): New function.
	(balance_partitions): New function.
	(build_ltrans_partitions): New function.
	(merge_comdat_nodes): New function.
	(merge_static_calls): New function.
	(merge_contained_symbols): New function.
	(lto_merge_comdat_map): New function.
	(privatize_symbol_name_1): Handle when WPA is not enabled.
	(privatize_symbol_name): Same as above.
	(lto_promote_cross_file_statics): New parameter to select when
	to promote to global.
	(lto_check_usage_from_other_partitions): New function.
	* lto-partition.h: Move from gcc/lto/lto-partition.h
	(lto_promote_cross_file_statics): Update prototype.
	(lto_check_usage_from_other_partitions): Declare.
	(lto_merge_comdat_map): Declare.

gcc/lto/ChangeLog:
2020-08-20  Giuliano Belinassi  <giuliano.belinassi@usp.br>

	* lto-partition.c: Move to gcc/lto-partition.c.
	* lto-partition.h: Move to gcc/lto-partition.h.
	* lto.c: Update call to lto_promote_cross_file_statics.
	* Makefile.in: Remove lto-partition.o.

0 files changed, 0 insertions, 0 deletions