lto: Implement cache partitioning

This patch implements new cache partitioning. It tries to keep symbols
from single source file together to minimize propagation of divergence.

It starts with symbols already grouped by source files. If reasonably
possible it only either combines several files into one final partition,
or, if a file is large, split the file into several final partitions.

Intermediate representation is partition_set which contains set of
groups of symbols (each group corresponding to original source file) and
number of final partitions this partition_set should split into.

First partition_fixed_split splits partition_set into constant number of
partition_sets with equal number of symbols groups. If for example there
are 39 source files, the resulting partition_sets will contain 10, 10,
10, and 9 source files. This splitting intentionally ignores estimated
instruction counts to minimize propagation of divergence.

Second partition_over_target_split separates too large files and splits
them into individual symbols to be combined back into several smaller
files in next step.

Third partition_binary_split splits partition_set into two halves until
it should be split into only one final partition, at which point the
remaining symbols are joined into one final partition.

Bootstrapped/regtested on x86_64-pc-linux-gnu

gcc/ChangeLog:

	* common.opt: Add cache partitioning.
	* flag-types.h (enum lto_partition_model): Likewise.

gcc/lto/ChangeLog:

	* lto-partition.cc (new_partition): Use new_partition_no_push.
	(new_partition_no_push): New.
	(free_ltrans_partition): New.
	(free_ltrans_partitions): Use free_ltrans_partition.
	(join_partitions): New.
	(split_partition_into_nodes): New.
	(is_partition_reorder): New.
	(class partition_set): New.
	(distribute_n_partitions): New.
	(partition_over_target_split): New.
	(partition_binary_split): New.
	(partition_fixed_split): New.
	(class partitioner_base): New.
	(class partitioner_default): New.
	(lto_cache_map): New.
	* lto-partition.h (lto_cache_map): New.
	* lto.cc (do_whole_program_analysis): Use lto_cache_map.

gcc/testsuite/ChangeLog:

	* gcc.dg/completion-2.c: Add -flto-partition=cache.

0 files changed, 0 insertions, 0 deletions