From e778bf0fc6f0d6e15f81976b4fc461337ef63146 Mon Sep 17 00:00:00 2001 From: Giuliano Belinassi Date: Wed, 24 Jun 2020 18:17:54 -0300 Subject: Merge small partitions. Current partitioner seems to create one huge partitions and several other small partitions. This commit improves the partitioning algorithm by merging small partitions together. It also avoids wasting time partitioning if the program size is `small'. Note that small here is subjective. gcc/ChangeLog: 2020-06-24 Giuliano Belinassi * cgraphunit.c (ipa_passes): Assert for non-empty partition. * lto-partition.c: Remove currrent_working_partition. (add_symbol_to_partition): Remove useless check. (lto_max_no_alonevap_map): Use an heuristic to merge small partitions. Also fix creation of empty partitions. --- gcc/ChangeLog | 8 ++++ gcc/cgraphunit.c | 4 +- gcc/lto-partition.c | 118 +++++++++++++++++++++++++++++++++++++++++++--------- 3 files changed, 108 insertions(+), 22 deletions(-) (limited to 'gcc') diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b999b1f..3cdc5eb 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +2020-06-24 Giuliano Belinassi + + * cgraphunit.c (ipa_passes): Assert for non-empty partition. + * lto-partition.c: Remove currrent_working_partition. + (add_symbol_to_partition): Remove useless check. + (lto_max_no_alonevap_map): Use an heuristic to merge small + partitions. Also fix creation of empty partitions. + 2020-06-23 Giuliano Belinassi * cgraphunit.c (ipa_passes): Run ipa passes also when diff --git a/gcc/cgraphunit.c b/gcc/cgraphunit.c index 4665fda..381d360 100644 --- a/gcc/cgraphunit.c +++ b/gcc/cgraphunit.c @@ -2702,9 +2702,7 @@ ipa_passes (void) /* Run serially for now. */ for (i = 0; i < partitions; ++i) { - if (ltrans_partitions[i]->symbols == 0) - continue; /* FIXME: Find out why we are generating empty - partitions. */ + gcc_assert (ltrans_partitions[i]->symbols > 0); pids[i] = fork (); if (pids[i] == 0) diff --git a/gcc/lto-partition.c b/gcc/lto-partition.c index 812a3f1..72a2bdb 100644 --- a/gcc/lto-partition.c +++ b/gcc/lto-partition.c @@ -124,8 +124,6 @@ add_references_to_partition (ltrans_partition part, symtab_node *node) } } -static int current_working_partition = -1; - /* Helper function for add_symbol_to_partition doing the actual dirty work of adding NODE to PART. */ @@ -140,10 +138,6 @@ add_symbol_to_partition_1 (ltrans_partition part, symtab_node *node) if (lto_symtab_encoder_in_partition_p (part->encoder, node)) return true; - if (current_working_partition != node->aux2) - fatal_error (UNKNOWN_LOCATION, "Adding node to partition which was meant to" - "be in another partition"); - /* non-duplicated aliases or tunks of a duplicated symbol needs to be output just once. @@ -577,7 +571,9 @@ lto_max_no_alonevap_map (void) { symtab_node *node; int n_partitions = 0, i, n = 0, j = 0; + int total_size = 0, max_size = -1; int *compression; + int *sizes; FOR_EACH_SYMBOL (node) node->aux2 = n++; @@ -599,18 +595,94 @@ lto_max_no_alonevap_map (void) analyse_symbol (node, node->aux2); /* Allocate a compression vector, where we will map each disjoint set into - 0, ..., n_partitions - 1. Complexity: n. */ + 0, ..., n_partitions - 1. Also allocates a size vector which will + hold each partition size. Complexity: n. */ compression = (int *) alloca (n * sizeof (*compression)); + sizes = (int *) alloca (n * sizeof (*sizes)); + memset (sizes, 0, n * sizeof (*sizes)); for (i = 0; i < n; ++i) compression[i] = -1; /* Invalid value. */ - /* Create LTRANS partitions. */ - n_partitions = n - disjoint_sets.successful_unions; - ltrans_partitions.create (n_partitions); - for (i = 0; i < n_partitions; i++) - new_partition (""); + /* Compute the size of each partition. */ + i = 0; + FOR_EACH_SYMBOL (node) + { + cgraph_node *cnode = dyn_cast (node); + if (!cnode) + { + i++; + continue; + } + + ipa_size_summary *summary = ipa_size_summaries->get (cnode); + if (summary) + { + int root = disjoint_sets.find (i); + sizes[root] += summary->size; + } + i++; + } + + /* Compute the total size and maximum size. */ + for (i = 0; i < n; ++i) + { + total_size += sizes[i]; + max_size = MAX (max_size, sizes[i]); + } + + /* Quick return if total size is small. */ + if (total_size < param_min_partition_size) + return; + + /* Unite small partitions. */ + + for (i = -1, j = 0; j < n; ++j) + { + if (sizes[j] == 0) + continue; + + if (i == -1) + i = j; + else + { + if (sizes[i] + sizes[j] < max_size) + { + ds->unite (i, j); + sizes[j] += sizes[i]; + sizes[i] = 0; + } + else + i = j; + } + } + + /* Unite the smallest partition with the second smallest. This is + to avoid having one very big partition and two other very small ones. */ + int smallest_pos = -1; + int second_smallest_pos = -1; + int smallest = INT_MAX; + + for (i = 0; i < n; ++i) + { + if (sizes[i] == 0) + continue; + + if (sizes[i] < smallest) + { + smallest = sizes[i]; + second_smallest_pos = smallest_pos; + smallest_pos = i; + } + } + + if (smallest_pos != -1 && second_smallest_pos != -1) + { + ds->unite (smallest_pos, second_smallest_pos); + sizes[smallest_pos] += sizes[second_smallest_pos]; + sizes[second_smallest_pos] = 0; + } /* Compress 0...(n-1) into 0...(n_partitions-1) so that we avoid manuvers with the LTRANS partitions. Complexity: n * log*(n). */ @@ -621,25 +693,33 @@ lto_max_no_alonevap_map (void) int root = disjoint_sets.find (i); node->aux2 = root; node->aux = NULL; - if (compression[root] < 0) + + if (node->get_partitioning_class () == SYMBOL_PARTITION + && compression[root] < 0) compression[root] = j++; i++; } - /* A invariant of the above loop. */ - gcc_assert (n_partitions == j); + n_partitions = j; + + /* Quick return if we have only one partition. */ + if (n_partitions <= 1) + return; + + /* Create LTRANS partitions. */ + ltrans_partitions.create (n_partitions); + for (i = 0; i < n_partitions; i++) + new_partition (""); /* Indeed insert vertex into the LTRANS partitions, and clear AUX variable. Complexity: n. */ FOR_EACH_SYMBOL (node) { - int p = compression[node->aux2]; - current_working_partition = node->aux2; - if (node->get_partitioning_class () != SYMBOL_PARTITION || symbol_partitioned_p (node)) continue; - + + int p = compression[node->aux2]; add_symbol_to_partition (ltrans_partitions[p], node); } } -- cgit v1.1