[gcc/devel/autopar_devel] Implement a new partitioning algorithm
Giuliano Belinassi
giulianob@gcc.gnu.org
Tue Jun 9 03:18:25 GMT 2020
https://gcc.gnu.org/g:3ec7662202099738819ea521b65faada5c0a6c70
commit 3ec7662202099738819ea521b65faada5c0a6c70
Author: Giuliano Belinassi <giuliano.belinassi@usp.br>
Date: Tue Jun 9 00:10:07 2020 -0300
Implement a new partitioning algorithm
Implements a new partitioning algorithm based on add_node_to_partition
logic, still using a union find datastructure for quick merging
partitions. libgcc is compiling, libstdc++ fails to link.
gcc/ChangeLog
2020-06-08 Giuliano Belinassi <giuliano.belinassi@usp.br>
* cgraphunit.c (cgraph_node::expand): Quick return if no body is
available.
(ipa_passes): Skip empty partitions.
* gcc.c (append_split_outputs): Fix misleading identation.
* ipa.c (symbol_table::remove_unreachable_nodes): Assert for
split_outputs.
* lto-cgraph.c (lto_apply_partition_mask): set body_removed when
body is removed.
* lto-partition.c: (current_working_partition): New variable.
* (add_symbol_to_partition): Check if insertion on correct
partition. Also check if nodes from the same COMDAT group are
mapped to the partition.
(union_find::print_roots): New function.
(ds): New variable.
(ds_print_roots): New function.
(analyse_symbol_references): New function.
(analyse_symbol_1): New function.
(int_cast): Remove.
(lto_max_no_alonevap_map): Replace with new algorithm.
Diff:
---
gcc/ChangeLog | 22 ++++++++
gcc/cgraphunit.c | 9 +++
gcc/gcc.c | 6 +-
gcc/ipa.c | 2 +-
gcc/lto-cgraph.c | 1 +
gcc/lto-partition.c | 159 ++++++++++++++++++++++++++++++++++++++++++----------
6 files changed, 165 insertions(+), 34 deletions(-)
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 79397f93aae..04a42c18bc7 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,25 @@
+2020-06-08 Giuliano Belinassi <giuliano.belinassi@usp.br>
+
+ * cgraphunit.c (cgraph_node::expand): Quick return if no body is
+ available.
+ (ipa_passes): Skip empty partitions.
+ * gcc.c (append_split_outputs): Fix misleading identation.
+ * ipa.c (symbol_table::remove_unreachable_nodes): Assert for
+ split_outputs.
+ * lto-cgraph.c (lto_apply_partition_mask): set body_removed when
+ body is removed.
+ * lto-partition.c: (current_working_partition): New variable.
+ * (add_symbol_to_partition): Check if insertion on correct
+ partition. Also check if nodes from the same COMDAT group are
+ mapped to the partition.
+ (union_find::print_roots): New function.
+ (ds): New variable.
+ (ds_print_roots): New function.
+ (analyse_symbol_references): New function.
+ (analyse_symbol_1): New function.
+ (int_cast): Remove.
+ (lto_max_no_alonevap_map): Replace with new algorithm.
+
2020-06-05 Giuliano Belinassi <giuliano.belinassi@usp.br>
* cgraph.h (symtab_node): New attribute aux2.
diff --git a/gcc/cgraphunit.c b/gcc/cgraphunit.c
index 5d8cddd6850..27ffcb3a57f 100644
--- a/gcc/cgraphunit.c
+++ b/gcc/cgraphunit.c
@@ -2256,6 +2256,11 @@ cgraph_node::expand (void)
{
location_t saved_loc;
+ /* FIXME: Find out why body-removed nodes are marked for output. */
+ if (body_removed)
+ return;
+
+
/* We ought to not compile any inline clones. */
gcc_assert (!inlined_to);
@@ -2694,6 +2699,10 @@ 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. */
+
pids[i] = fork ();
if (pids[i] == 0)
{
diff --git a/gcc/gcc.c b/gcc/gcc.c
index 5144ae28d8d..f53d9dfeaf9 100644
--- a/gcc/gcc.c
+++ b/gcc/gcc.c
@@ -3341,8 +3341,10 @@ static void append_split_outputs (extra_arg_storer *storer,
}
if (have_c)
- argv[argc++] = "-fPIE";
- argv[argc++] = "-fPIC";
+ {
+ argv[argc++] = "-fPIE";
+ argv[argc++] = "-fPIC";
+ }
argv[argc] = NULL;
diff --git a/gcc/ipa.c b/gcc/ipa.c
index 55481931668..6a336746ef0 100644
--- a/gcc/ipa.c
+++ b/gcc/ipa.c
@@ -561,7 +561,7 @@ symbol_table::remove_unreachable_nodes (FILE *file)
}
else
gcc_assert (node->clone_of || !node->has_gimple_body_p ()
- || in_lto_p || DECL_RESULT (node->decl));
+ || in_lto_p || split_outputs || DECL_RESULT (node->decl));
}
/* Inline clones might be kept around so their materializing allows further
diff --git a/gcc/lto-cgraph.c b/gcc/lto-cgraph.c
index 7a32159ea69..dd2df8f3743 100644
--- a/gcc/lto-cgraph.c
+++ b/gcc/lto-cgraph.c
@@ -2108,6 +2108,7 @@ lto_apply_partition_mask (ltrans_partition partition)
{
maybe_release_function_dominators (cnode);
cnode->release_body ();
+ cnode->body_removed = true;
}
node->in_other_partition = true;
diff --git a/gcc/lto-partition.c b/gcc/lto-partition.c
index 449dcfa6f41..a1eef093e35 100644
--- a/gcc/lto-partition.c
+++ b/gcc/lto-partition.c
@@ -124,6 +124,8 @@ 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. */
@@ -138,6 +140,10 @@ 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.
@@ -215,6 +221,10 @@ add_symbol_to_partition_1 (ltrans_partition part, symtab_node *node)
node1 != node; node1 = node1->same_comdat_group)
if (!node->alias)
{
+ if (node->aux2 != node1->aux2)
+ fatal_error (UNKNOWN_LOCATION, "Nodes from the same COMDAT group in"
+ "distinct partitions");
+
bool added = add_symbol_to_partition_1 (part, node1);
gcc_assert (added);
}
@@ -435,21 +445,125 @@ public:
if (rank[x_root] == rank[y_root])
rank[x_root]++;
}
+
+ void print_roots ()
+ {
+ int i;
+ for (i = 0; i < n; ++i)
+ printf ("%d, ", find (i));
+ printf ("\n");
+ }
};
-/* Cast an void * to integer. Shall not work if sizeof (void*) greater
- than int. */
+static union_find *ds;
+
+DEBUG_FUNCTION void ds_print_roots (void)
+{
+ ds->print_roots ();
+}
+
+static void analyse_symbol (symtab_node *, int);
+
+static void
+analyse_symbol_references (symtab_node *node, int set)
+{
+ int i;
+ struct ipa_ref *ref = NULL;
+
+ /* Add all duplicated references to the partition. */
+ for (i = 0; node->iterate_reference (i, ref); i++)
+ if (ref->referred->get_partitioning_class () == SYMBOL_DUPLICATE)
+ {
+ symtab_node *node1 = ref->referred;
+ analyse_symbol (node1, set);
+ }
+ /* References to a readonly variable may be constant foled into its value.
+ Recursively look into the initializers of the constant variable and add
+ references, too. */
+ else if (is_a <varpool_node *> (ref->referred)
+ /* && (dyn_cast <varpool_node *> (ref->referred)
+ ->ctor_useable_for_folding_p ()))*/)
+ {
+ symtab_node *node1 = ref->referred;
+ analyse_symbol (node1, set);
+ }
+}
+
+static bool analyse_symbol_1 (symtab_node *node, int set)
+{
+ struct ipa_ref *ref;
+ symtab_node *node1;
+
+ ds->unite (node->aux2, set);
+
+ /* If NODE was already analysed, return. */
+ if (symbol_partitioned_p (node))
+ return true;
+
+ /* Indicate that we analysed this node once. */
+ node->aux = (void *)((size_t)node->aux + 1);
+
+ if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
+ {
+ struct cgraph_edge *e;
+
+ /* Add all inline clones and callees that are duplicated. */
+ for (e = cnode->callees; e; e = e->next_callee)
+ if (!e->inline_failed || TREE_STATIC (e->callee->decl))
+ analyse_symbol_1 (e->callee, set);
+ else if (e->callee->get_partitioning_class () == SYMBOL_DUPLICATE)
+ analyse_symbol (e->callee, set);
+
+ /* Add all thunks associated with the function. */
+ for (e = cnode->callers; e; e = e->next_caller)
+ if (e->caller->thunk.thunk_p && !e->caller->inlined_to)
+ analyse_symbol_1 (e->caller, set);
+ }
+
+ analyse_symbol_references (node, set);
+
+ /* Add all aliases associated with the symbol. */
+
+ FOR_EACH_ALIAS (node, ref)
+ if (!ref->referring->transparent_alias)
+ analyse_symbol_1 (ref->referring, set);
+ else
+ {
+ struct ipa_ref *ref2;
+ /* We do not need to add transparent aliases if they are not used.
+ However we must add aliases of transparent aliases if they exist. */
+ FOR_EACH_ALIAS (ref->referring, ref2)
+ {
+ /* Nested transparent aliases are not permitted. */
+ gcc_checking_assert (!ref2->referring->transparent_alias);
+ analyse_symbol_1 (ref2->referring, set);
+ }
+ }
-static inline int int_cast (void *x)
+ /* Ensure that SAME_COMDAT_GROUP lists all allways added in a group. */
+ if (node->same_comdat_group)
+ for (node1 = node->same_comdat_group;
+ node1 != node; node1 = node1->same_comdat_group)
+ if (!node->alias)
+ {
+ bool added = analyse_symbol_1 (node1, set);
+ gcc_assert (added);
+ }
+ return true;
+}
+
+static void analyse_symbol (symtab_node *node, int set)
{
- union void_to_int
+ symtab_node *node1;
+
+
+ while ((node1 = contained_in_symbol (node)) != node)
{
- void *ptr;
- int val;
- } u;
+ ds->unite (node->aux2, node1->aux2);
+ node = node1;
+ }
+ analyse_symbol_1 (node, set);
- u.ptr = x;
- return u.val;
}
/* Maximal partitioning with a restriction: Varnodes can't be let alone in a
@@ -460,7 +574,6 @@ void
lto_max_no_alonevap_map (void)
{
symtab_node *node;
- cgraph_node *cnode;
int n_partitions = 0, i, n = 0, j = 0;
int *compression;
@@ -468,6 +581,7 @@ lto_max_no_alonevap_map (void)
node->aux2 = n++;
union_find disjoint_sets = union_find (n);
+ ds = &disjoint_sets;
/* Look for each function neighbor, checking for global-like variables that
it references. Complexity:
@@ -479,26 +593,8 @@ lto_max_no_alonevap_map (void)
of a single union operation, wich is log*(n). The fact that such sum
is |2E|*log*(n) is a consequence from the handshake lemma. */
- FOR_EACH_FUNCTION (cnode)
- {
- struct ipa_ref *ref = NULL;
- cgraph_edge *e;
-
- for (i = 0; cnode->iterate_reference (i, ref); i++)
- {
- symtab_node *node = ref->referred;
- if (is_a <varpool_node *> (node))
- disjoint_sets.unite (cnode->aux2, node->aux2);
- }
-
- for (e = cnode->callees; e; e = e->next_callee)
- {
- cgraph_node *node = e->callee;
- if (TREE_STATIC (node->decl))
- disjoint_sets.unite (cnode->aux2, node->aux2);
- }
-
- }
+ FOR_EACH_SYMBOL (node)
+ analyse_symbol (node, node->aux2);
/* Allocate a compression vector, where we will map each disjoint set into
0, ..., n_partitions - 1. Complexity: n. */
@@ -522,6 +618,7 @@ lto_max_no_alonevap_map (void)
{
int root = disjoint_sets.find (i);
node->aux2 = root;
+ node->aux = NULL;
if (compression[root] < 0)
compression[root] = j++;
i++;
@@ -535,7 +632,7 @@ lto_max_no_alonevap_map (void)
FOR_EACH_SYMBOL (node)
{
int p = compression[node->aux2];
- node->aux2 = -1;
+ current_working_partition = node->aux2;
if (node->get_partitioning_class () != SYMBOL_PARTITION
|| symbol_partitioned_p (node))
More information about the Gcc-cvs
mailing list