163d1a8abSmrg /* LTO partitioning logic routines.
2*ec02198aSmrg Copyright (C) 2009-2020 Free Software Foundation, Inc.
363d1a8abSmrg
463d1a8abSmrg This file is part of GCC.
563d1a8abSmrg
663d1a8abSmrg GCC is free software; you can redistribute it and/or modify it under
763d1a8abSmrg the terms of the GNU General Public License as published by the Free
863d1a8abSmrg Software Foundation; either version 3, or (at your option) any later
963d1a8abSmrg version.
1063d1a8abSmrg
1163d1a8abSmrg GCC is distributed in the hope that it will be useful, but WITHOUT ANY
1263d1a8abSmrg WARRANTY; without even the implied warranty of MERCHANTABILITY or
1363d1a8abSmrg FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1463d1a8abSmrg for more details.
1563d1a8abSmrg
1663d1a8abSmrg You should have received a copy of the GNU General Public License
1763d1a8abSmrg along with GCC; see the file COPYING3. If not see
1863d1a8abSmrg <http://www.gnu.org/licenses/>. */
1963d1a8abSmrg
2063d1a8abSmrg #include "config.h"
2163d1a8abSmrg #include "system.h"
2263d1a8abSmrg #include "coretypes.h"
2363d1a8abSmrg #include "target.h"
2463d1a8abSmrg #include "function.h"
2563d1a8abSmrg #include "basic-block.h"
2663d1a8abSmrg #include "tree.h"
2763d1a8abSmrg #include "gimple.h"
2863d1a8abSmrg #include "alloc-pool.h"
2963d1a8abSmrg #include "stringpool.h"
3063d1a8abSmrg #include "cgraph.h"
3163d1a8abSmrg #include "lto-streamer.h"
3263d1a8abSmrg #include "symbol-summary.h"
3363d1a8abSmrg #include "tree-vrp.h"
3463d1a8abSmrg #include "ipa-prop.h"
35c7a68eb7Smrg #include "ipa-fnsummary.h"
3663d1a8abSmrg #include "lto-partition.h"
37c7a68eb7Smrg #include "sreal.h"
3863d1a8abSmrg
3963d1a8abSmrg vec<ltrans_partition> ltrans_partitions;
4063d1a8abSmrg
4163d1a8abSmrg static void add_symbol_to_partition (ltrans_partition part, symtab_node *node);
4263d1a8abSmrg
4363d1a8abSmrg
44c7a68eb7Smrg /* Helper for qsort; compare partitions and return one with smaller order. */
45c7a68eb7Smrg
46c7a68eb7Smrg static int
cmp_partitions_order(const void * a,const void * b)47c7a68eb7Smrg cmp_partitions_order (const void *a, const void *b)
48c7a68eb7Smrg {
49c7a68eb7Smrg const struct ltrans_partition_def *pa
50c7a68eb7Smrg = *(struct ltrans_partition_def *const *)a;
51c7a68eb7Smrg const struct ltrans_partition_def *pb
52c7a68eb7Smrg = *(struct ltrans_partition_def *const *)b;
53c7a68eb7Smrg int ordera = -1, orderb = -1;
54c7a68eb7Smrg
55c7a68eb7Smrg if (lto_symtab_encoder_size (pa->encoder))
56c7a68eb7Smrg ordera = lto_symtab_encoder_deref (pa->encoder, 0)->order;
57c7a68eb7Smrg if (lto_symtab_encoder_size (pb->encoder))
58c7a68eb7Smrg orderb = lto_symtab_encoder_deref (pb->encoder, 0)->order;
59c7a68eb7Smrg return orderb - ordera;
60c7a68eb7Smrg }
61c7a68eb7Smrg
6263d1a8abSmrg /* Create new partition with name NAME. */
6363d1a8abSmrg
6463d1a8abSmrg static ltrans_partition
new_partition(const char * name)6563d1a8abSmrg new_partition (const char *name)
6663d1a8abSmrg {
6763d1a8abSmrg ltrans_partition part = XCNEW (struct ltrans_partition_def);
6863d1a8abSmrg part->encoder = lto_symtab_encoder_new (false);
6963d1a8abSmrg part->name = name;
7063d1a8abSmrg part->insns = 0;
7163d1a8abSmrg part->symbols = 0;
7263d1a8abSmrg ltrans_partitions.safe_push (part);
7363d1a8abSmrg return part;
7463d1a8abSmrg }
7563d1a8abSmrg
7663d1a8abSmrg /* Free memory used by ltrans datastructures. */
7763d1a8abSmrg
7863d1a8abSmrg void
free_ltrans_partitions(void)7963d1a8abSmrg free_ltrans_partitions (void)
8063d1a8abSmrg {
8163d1a8abSmrg unsigned int idx;
8263d1a8abSmrg ltrans_partition part;
8363d1a8abSmrg for (idx = 0; ltrans_partitions.iterate (idx, &part); idx++)
8463d1a8abSmrg {
8563d1a8abSmrg if (part->initializers_visited)
8663d1a8abSmrg delete part->initializers_visited;
8763d1a8abSmrg /* Symtab encoder is freed after streaming. */
8863d1a8abSmrg free (part);
8963d1a8abSmrg }
9063d1a8abSmrg ltrans_partitions.release ();
9163d1a8abSmrg }
9263d1a8abSmrg
9363d1a8abSmrg /* Return true if symbol is already in some partition. */
9463d1a8abSmrg
9563d1a8abSmrg static inline bool
symbol_partitioned_p(symtab_node * node)9663d1a8abSmrg symbol_partitioned_p (symtab_node *node)
9763d1a8abSmrg {
9863d1a8abSmrg return node->aux;
9963d1a8abSmrg }
10063d1a8abSmrg
10163d1a8abSmrg /* Add references into the partition. */
10263d1a8abSmrg static void
add_references_to_partition(ltrans_partition part,symtab_node * node)10363d1a8abSmrg add_references_to_partition (ltrans_partition part, symtab_node *node)
10463d1a8abSmrg {
10563d1a8abSmrg int i;
10663d1a8abSmrg struct ipa_ref *ref = NULL;
10763d1a8abSmrg
10863d1a8abSmrg /* Add all duplicated references to the partition. */
10963d1a8abSmrg for (i = 0; node->iterate_reference (i, ref); i++)
11063d1a8abSmrg if (ref->referred->get_partitioning_class () == SYMBOL_DUPLICATE)
11163d1a8abSmrg add_symbol_to_partition (part, ref->referred);
11263d1a8abSmrg /* References to a readonly variable may be constant foled into its value.
11363d1a8abSmrg Recursively look into the initializers of the constant variable and add
11463d1a8abSmrg references, too. */
11563d1a8abSmrg else if (is_a <varpool_node *> (ref->referred)
11663d1a8abSmrg && (dyn_cast <varpool_node *> (ref->referred)
1170fc04c29Smrg ->ctor_useable_for_folding_p ())
11863d1a8abSmrg && !lto_symtab_encoder_in_partition_p (part->encoder, ref->referred))
11963d1a8abSmrg {
12063d1a8abSmrg if (!part->initializers_visited)
12163d1a8abSmrg part->initializers_visited = new hash_set<symtab_node *>;
12263d1a8abSmrg if (!part->initializers_visited->add (ref->referred))
12363d1a8abSmrg add_references_to_partition (part, ref->referred);
12463d1a8abSmrg }
12563d1a8abSmrg }
12663d1a8abSmrg
12763d1a8abSmrg /* Helper function for add_symbol_to_partition doing the actual dirty work
12863d1a8abSmrg of adding NODE to PART. */
12963d1a8abSmrg
13063d1a8abSmrg static bool
add_symbol_to_partition_1(ltrans_partition part,symtab_node * node)13163d1a8abSmrg add_symbol_to_partition_1 (ltrans_partition part, symtab_node *node)
13263d1a8abSmrg {
13363d1a8abSmrg enum symbol_partitioning_class c = node->get_partitioning_class ();
13463d1a8abSmrg struct ipa_ref *ref;
13563d1a8abSmrg symtab_node *node1;
13663d1a8abSmrg
13763d1a8abSmrg /* If NODE is already there, we have nothing to do. */
13863d1a8abSmrg if (lto_symtab_encoder_in_partition_p (part->encoder, node))
13963d1a8abSmrg return true;
14063d1a8abSmrg
14163d1a8abSmrg /* non-duplicated aliases or tunks of a duplicated symbol needs to be output
14263d1a8abSmrg just once.
14363d1a8abSmrg
14463d1a8abSmrg Be lax about comdats; they may or may not be duplicated and we may
14563d1a8abSmrg end up in need to duplicate keyed comdat because it has unkeyed alias. */
14663d1a8abSmrg if (c == SYMBOL_PARTITION && !DECL_COMDAT (node->decl)
14763d1a8abSmrg && symbol_partitioned_p (node))
14863d1a8abSmrg return false;
14963d1a8abSmrg
15063d1a8abSmrg /* Be sure that we never try to duplicate partitioned symbol
15163d1a8abSmrg or add external symbol. */
15263d1a8abSmrg gcc_assert (c != SYMBOL_EXTERNAL
15363d1a8abSmrg && (c == SYMBOL_DUPLICATE || !symbol_partitioned_p (node)));
15463d1a8abSmrg
15563d1a8abSmrg part->symbols++;
15663d1a8abSmrg
15763d1a8abSmrg lto_set_symtab_encoder_in_partition (part->encoder, node);
15863d1a8abSmrg
15963d1a8abSmrg if (symbol_partitioned_p (node))
16063d1a8abSmrg {
16163d1a8abSmrg node->in_other_partition = 1;
1620fc04c29Smrg if (dump_file)
1630fc04c29Smrg fprintf (dump_file,
16463d1a8abSmrg "Symbol node %s now used in multiple partitions\n",
165*ec02198aSmrg node->dump_name ());
16663d1a8abSmrg }
16763d1a8abSmrg node->aux = (void *)((size_t)node->aux + 1);
16863d1a8abSmrg
16963d1a8abSmrg if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
17063d1a8abSmrg {
17163d1a8abSmrg struct cgraph_edge *e;
172c7a68eb7Smrg if (!node->alias && c == SYMBOL_PARTITION)
173*ec02198aSmrg part->insns += ipa_size_summaries->get (cnode)->size;
17463d1a8abSmrg
17563d1a8abSmrg /* Add all inline clones and callees that are duplicated. */
17663d1a8abSmrg for (e = cnode->callees; e; e = e->next_callee)
17763d1a8abSmrg if (!e->inline_failed)
17863d1a8abSmrg add_symbol_to_partition_1 (part, e->callee);
17963d1a8abSmrg else if (e->callee->get_partitioning_class () == SYMBOL_DUPLICATE)
18063d1a8abSmrg add_symbol_to_partition (part, e->callee);
18163d1a8abSmrg
18263d1a8abSmrg /* Add all thunks associated with the function. */
18363d1a8abSmrg for (e = cnode->callers; e; e = e->next_caller)
184*ec02198aSmrg if (e->caller->thunk.thunk_p && !e->caller->inlined_to)
18563d1a8abSmrg add_symbol_to_partition_1 (part, e->caller);
18663d1a8abSmrg }
18763d1a8abSmrg
18863d1a8abSmrg add_references_to_partition (part, node);
18963d1a8abSmrg
19063d1a8abSmrg /* Add all aliases associated with the symbol. */
19163d1a8abSmrg
19263d1a8abSmrg FOR_EACH_ALIAS (node, ref)
19363d1a8abSmrg if (!ref->referring->transparent_alias)
19463d1a8abSmrg add_symbol_to_partition_1 (part, ref->referring);
19563d1a8abSmrg else
19663d1a8abSmrg {
19763d1a8abSmrg struct ipa_ref *ref2;
19863d1a8abSmrg /* We do not need to add transparent aliases if they are not used.
19963d1a8abSmrg However we must add aliases of transparent aliases if they exist. */
20063d1a8abSmrg FOR_EACH_ALIAS (ref->referring, ref2)
20163d1a8abSmrg {
20263d1a8abSmrg /* Nested transparent aliases are not permitted. */
20363d1a8abSmrg gcc_checking_assert (!ref2->referring->transparent_alias);
20463d1a8abSmrg add_symbol_to_partition_1 (part, ref2->referring);
20563d1a8abSmrg }
20663d1a8abSmrg }
20763d1a8abSmrg
20863d1a8abSmrg /* Ensure that SAME_COMDAT_GROUP lists all allways added in a group. */
20963d1a8abSmrg if (node->same_comdat_group)
21063d1a8abSmrg for (node1 = node->same_comdat_group;
21163d1a8abSmrg node1 != node; node1 = node1->same_comdat_group)
21263d1a8abSmrg if (!node->alias)
21363d1a8abSmrg {
21463d1a8abSmrg bool added = add_symbol_to_partition_1 (part, node1);
21563d1a8abSmrg gcc_assert (added);
21663d1a8abSmrg }
21763d1a8abSmrg return true;
21863d1a8abSmrg }
21963d1a8abSmrg
22063d1a8abSmrg /* If symbol NODE is really part of other symbol's definition (i.e. it is
22163d1a8abSmrg internal label, thunk, alias or so), return the outer symbol.
22263d1a8abSmrg When add_symbol_to_partition_1 is called on the outer symbol it must
22363d1a8abSmrg eventually add NODE, too. */
22463d1a8abSmrg static symtab_node *
contained_in_symbol(symtab_node * node)22563d1a8abSmrg contained_in_symbol (symtab_node *node)
22663d1a8abSmrg {
22763d1a8abSmrg /* There is no need to consider transparent aliases to be part of the
22863d1a8abSmrg definition: they are only useful insite the partition they are output
22963d1a8abSmrg and thus we will always see an explicit reference to it. */
23063d1a8abSmrg if (node->transparent_alias)
23163d1a8abSmrg return node;
23263d1a8abSmrg if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
23363d1a8abSmrg {
23463d1a8abSmrg cnode = cnode->function_symbol ();
235*ec02198aSmrg if (cnode->inlined_to)
236*ec02198aSmrg cnode = cnode->inlined_to;
23763d1a8abSmrg return cnode;
23863d1a8abSmrg }
23963d1a8abSmrg else if (varpool_node *vnode = dyn_cast <varpool_node *> (node))
24063d1a8abSmrg return vnode->ultimate_alias_target ();
24163d1a8abSmrg return node;
24263d1a8abSmrg }
24363d1a8abSmrg
24463d1a8abSmrg /* Add symbol NODE to partition. When definition of NODE is part
24563d1a8abSmrg of other symbol definition, add the other symbol, too. */
24663d1a8abSmrg
24763d1a8abSmrg static void
add_symbol_to_partition(ltrans_partition part,symtab_node * node)24863d1a8abSmrg add_symbol_to_partition (ltrans_partition part, symtab_node *node)
24963d1a8abSmrg {
25063d1a8abSmrg symtab_node *node1;
25163d1a8abSmrg
25263d1a8abSmrg /* Verify that we do not try to duplicate something that cannot be. */
25363d1a8abSmrg gcc_checking_assert (node->get_partitioning_class () == SYMBOL_DUPLICATE
25463d1a8abSmrg || !symbol_partitioned_p (node));
25563d1a8abSmrg
25663d1a8abSmrg while ((node1 = contained_in_symbol (node)) != node)
25763d1a8abSmrg node = node1;
25863d1a8abSmrg
25963d1a8abSmrg /* If we have duplicated symbol contained in something we cannot duplicate,
26063d1a8abSmrg we are very badly screwed. The other way is possible, so we do not
26163d1a8abSmrg assert this in add_symbol_to_partition_1.
26263d1a8abSmrg
26363d1a8abSmrg Be lax about comdats; they may or may not be duplicated and we may
26463d1a8abSmrg end up in need to duplicate keyed comdat because it has unkeyed alias. */
26563d1a8abSmrg
26663d1a8abSmrg gcc_assert (node->get_partitioning_class () == SYMBOL_DUPLICATE
26763d1a8abSmrg || DECL_COMDAT (node->decl)
26863d1a8abSmrg || !symbol_partitioned_p (node));
26963d1a8abSmrg
27063d1a8abSmrg add_symbol_to_partition_1 (part, node);
27163d1a8abSmrg }
27263d1a8abSmrg
27363d1a8abSmrg /* Undo all additions until number of cgraph nodes in PARITION is N_CGRAPH_NODES
27463d1a8abSmrg and number of varpool nodes is N_VARPOOL_NODES. */
27563d1a8abSmrg
27663d1a8abSmrg static void
undo_partition(ltrans_partition partition,unsigned int n_nodes)27763d1a8abSmrg undo_partition (ltrans_partition partition, unsigned int n_nodes)
27863d1a8abSmrg {
27963d1a8abSmrg while (lto_symtab_encoder_size (partition->encoder) > (int)n_nodes)
28063d1a8abSmrg {
28163d1a8abSmrg symtab_node *node = lto_symtab_encoder_deref (partition->encoder,
28263d1a8abSmrg n_nodes);
28363d1a8abSmrg partition->symbols--;
28463d1a8abSmrg cgraph_node *cnode;
28563d1a8abSmrg
28663d1a8abSmrg /* After UNDO we no longer know what was visited. */
28763d1a8abSmrg if (partition->initializers_visited)
28863d1a8abSmrg delete partition->initializers_visited;
28963d1a8abSmrg partition->initializers_visited = NULL;
29063d1a8abSmrg
291c7a68eb7Smrg if (!node->alias && (cnode = dyn_cast <cgraph_node *> (node))
292c7a68eb7Smrg && node->get_partitioning_class () == SYMBOL_PARTITION)
293*ec02198aSmrg partition->insns -= ipa_size_summaries->get (cnode)->size;
29463d1a8abSmrg lto_symtab_encoder_delete_node (partition->encoder, node);
29563d1a8abSmrg node->aux = (void *)((size_t)node->aux - 1);
29663d1a8abSmrg }
29763d1a8abSmrg }
29863d1a8abSmrg
29963d1a8abSmrg /* Group cgrah nodes by input files. This is used mainly for testing
30063d1a8abSmrg right now. */
30163d1a8abSmrg
30263d1a8abSmrg void
lto_1_to_1_map(void)30363d1a8abSmrg lto_1_to_1_map (void)
30463d1a8abSmrg {
30563d1a8abSmrg symtab_node *node;
30663d1a8abSmrg struct lto_file_decl_data *file_data;
30763d1a8abSmrg hash_map<lto_file_decl_data *, ltrans_partition> pmap;
30863d1a8abSmrg ltrans_partition partition;
30963d1a8abSmrg int npartitions = 0;
31063d1a8abSmrg
31163d1a8abSmrg FOR_EACH_SYMBOL (node)
31263d1a8abSmrg {
31363d1a8abSmrg if (node->get_partitioning_class () != SYMBOL_PARTITION
31463d1a8abSmrg || symbol_partitioned_p (node))
31563d1a8abSmrg continue;
31663d1a8abSmrg
31763d1a8abSmrg file_data = node->lto_file_data;
31863d1a8abSmrg
31963d1a8abSmrg if (file_data)
32063d1a8abSmrg {
32163d1a8abSmrg ltrans_partition *slot = &pmap.get_or_insert (file_data);
32263d1a8abSmrg if (*slot)
32363d1a8abSmrg partition = *slot;
32463d1a8abSmrg else
32563d1a8abSmrg {
32663d1a8abSmrg partition = new_partition (file_data->file_name);
32763d1a8abSmrg *slot = partition;
32863d1a8abSmrg npartitions++;
32963d1a8abSmrg }
33063d1a8abSmrg }
33163d1a8abSmrg else if (!file_data && ltrans_partitions.length ())
33263d1a8abSmrg partition = ltrans_partitions[0];
33363d1a8abSmrg else
33463d1a8abSmrg {
33563d1a8abSmrg partition = new_partition ("");
33663d1a8abSmrg pmap.put (NULL, partition);
33763d1a8abSmrg npartitions++;
33863d1a8abSmrg }
33963d1a8abSmrg
34063d1a8abSmrg add_symbol_to_partition (partition, node);
34163d1a8abSmrg }
34263d1a8abSmrg
34363d1a8abSmrg /* If the cgraph is empty, create one cgraph node set so that there is still
34463d1a8abSmrg an output file for any variables that need to be exported in a DSO. */
34563d1a8abSmrg if (!npartitions)
34663d1a8abSmrg new_partition ("empty");
34763d1a8abSmrg
348c7a68eb7Smrg /* Order partitions by order of symbols because they are linked into binary
349c7a68eb7Smrg that way. */
350c7a68eb7Smrg ltrans_partitions.qsort (cmp_partitions_order);
35163d1a8abSmrg }
35263d1a8abSmrg
35363d1a8abSmrg /* Maximal partitioning. Put every new symbol into new partition if possible. */
35463d1a8abSmrg
35563d1a8abSmrg void
lto_max_map(void)35663d1a8abSmrg lto_max_map (void)
35763d1a8abSmrg {
35863d1a8abSmrg symtab_node *node;
35963d1a8abSmrg ltrans_partition partition;
36063d1a8abSmrg int npartitions = 0;
36163d1a8abSmrg
36263d1a8abSmrg FOR_EACH_SYMBOL (node)
36363d1a8abSmrg {
36463d1a8abSmrg if (node->get_partitioning_class () != SYMBOL_PARTITION
36563d1a8abSmrg || symbol_partitioned_p (node))
36663d1a8abSmrg continue;
36763d1a8abSmrg partition = new_partition (node->asm_name ());
36863d1a8abSmrg add_symbol_to_partition (partition, node);
36963d1a8abSmrg npartitions++;
37063d1a8abSmrg }
37163d1a8abSmrg if (!npartitions)
37263d1a8abSmrg new_partition ("empty");
37363d1a8abSmrg }
37463d1a8abSmrg
37563d1a8abSmrg /* Helper function for qsort; sort nodes by order. */
37663d1a8abSmrg static int
node_cmp(const void * pa,const void * pb)377*ec02198aSmrg node_cmp (const void *pa, const void *pb)
37863d1a8abSmrg {
37963d1a8abSmrg const symtab_node *a = *static_cast<const symtab_node * const *> (pa);
38063d1a8abSmrg const symtab_node *b = *static_cast<const symtab_node * const *> (pb);
38163d1a8abSmrg return b->order - a->order;
38263d1a8abSmrg }
38363d1a8abSmrg
38463d1a8abSmrg /* Add all symtab nodes from NEXT_NODE to PARTITION in order. */
38563d1a8abSmrg
38663d1a8abSmrg static void
add_sorted_nodes(vec<symtab_node * > & next_nodes,ltrans_partition partition)38763d1a8abSmrg add_sorted_nodes (vec<symtab_node *> &next_nodes, ltrans_partition partition)
38863d1a8abSmrg {
38963d1a8abSmrg unsigned i;
39063d1a8abSmrg symtab_node *node;
39163d1a8abSmrg
392*ec02198aSmrg next_nodes.qsort (node_cmp);
39363d1a8abSmrg FOR_EACH_VEC_ELT (next_nodes, i, node)
39463d1a8abSmrg if (!symbol_partitioned_p (node))
39563d1a8abSmrg add_symbol_to_partition (partition, node);
39663d1a8abSmrg }
39763d1a8abSmrg
398c7a68eb7Smrg /* Return true if we should account reference from N1 to N2 in cost
399c7a68eb7Smrg of partition boundary. */
400c7a68eb7Smrg
401c7a68eb7Smrg bool
account_reference_p(symtab_node * n1,symtab_node * n2)402c7a68eb7Smrg account_reference_p (symtab_node *n1, symtab_node *n2)
403c7a68eb7Smrg {
404c7a68eb7Smrg if (cgraph_node *cnode = dyn_cast <cgraph_node *> (n1))
405c7a68eb7Smrg n1 = cnode;
406c7a68eb7Smrg /* Do not account references from aliases - they are never split across
407c7a68eb7Smrg partitions. */
408c7a68eb7Smrg if (n1->alias)
409c7a68eb7Smrg return false;
410c7a68eb7Smrg /* Do not account recursion - the code below will handle it incorrectly
411c7a68eb7Smrg otherwise. Do not account references to external symbols: they will
412c7a68eb7Smrg never become local. Finally do not account references to duplicated
413c7a68eb7Smrg symbols: they will be always local. */
414c7a68eb7Smrg if (n1 == n2
415c7a68eb7Smrg || !n2->definition
416c7a68eb7Smrg || n2->get_partitioning_class () != SYMBOL_PARTITION)
417c7a68eb7Smrg return false;
418c7a68eb7Smrg /* If referring node is external symbol do not account it to boundary
419c7a68eb7Smrg cost. Those are added into units only to enable possible constant
420c7a68eb7Smrg folding and devirtulization.
421c7a68eb7Smrg
422c7a68eb7Smrg Here we do not know if it will ever be added to some partition
423c7a68eb7Smrg (this is decided by compute_ltrans_boundary) and second it is not
424c7a68eb7Smrg that likely that constant folding will actually use the reference. */
425c7a68eb7Smrg if (contained_in_symbol (n1)
426c7a68eb7Smrg ->get_partitioning_class () == SYMBOL_EXTERNAL)
427c7a68eb7Smrg return false;
428c7a68eb7Smrg return true;
429c7a68eb7Smrg }
430c7a68eb7Smrg
43163d1a8abSmrg
43263d1a8abSmrg /* Group cgraph nodes into equally-sized partitions.
43363d1a8abSmrg
43463d1a8abSmrg The partitioning algorithm is simple: nodes are taken in predefined order.
43563d1a8abSmrg The order corresponds to the order we want functions to have in the final
43663d1a8abSmrg output. In the future this will be given by function reordering pass, but
43763d1a8abSmrg at the moment we use the topological order, which is a good approximation.
43863d1a8abSmrg
43963d1a8abSmrg The goal is to partition this linear order into intervals (partitions) so
44063d1a8abSmrg that all the partitions have approximately the same size and the number of
44163d1a8abSmrg callgraph or IPA reference edges crossing boundaries is minimal.
44263d1a8abSmrg
44363d1a8abSmrg This is a lot faster (O(n) in size of callgraph) than algorithms doing
44463d1a8abSmrg priority-based graph clustering that are generally O(n^2) and, since
44563d1a8abSmrg WHOPR is designed to make things go well across partitions, it leads
44663d1a8abSmrg to good results.
44763d1a8abSmrg
44863d1a8abSmrg We compute the expected size of a partition as:
44963d1a8abSmrg
45063d1a8abSmrg max (total_size / lto_partitions, min_partition_size)
45163d1a8abSmrg
45263d1a8abSmrg We use dynamic expected size of partition so small programs are partitioned
45363d1a8abSmrg into enough partitions to allow use of multiple CPUs, while large programs
45463d1a8abSmrg are not partitioned too much. Creating too many partitions significantly
45563d1a8abSmrg increases the streaming overhead.
45663d1a8abSmrg
45763d1a8abSmrg In the future, we would like to bound the maximal size of partitions so as
45863d1a8abSmrg to prevent the LTRANS stage from consuming too much memory. At the moment,
45963d1a8abSmrg however, the WPA stage is the most memory intensive for large benchmarks,
46063d1a8abSmrg since too many types and declarations are read into memory.
46163d1a8abSmrg
46263d1a8abSmrg The function implements a simple greedy algorithm. Nodes are being added
46363d1a8abSmrg to the current partition until after 3/4 of the expected partition size is
46463d1a8abSmrg reached. Past this threshold, we keep track of boundary size (number of
46563d1a8abSmrg edges going to other partitions) and continue adding functions until after
46663d1a8abSmrg the current partition has grown to twice the expected partition size. Then
46763d1a8abSmrg the process is undone to the point where the minimal ratio of boundary size
46863d1a8abSmrg and in-partition calls was reached. */
46963d1a8abSmrg
47063d1a8abSmrg void
lto_balanced_map(int n_lto_partitions,int max_partition_size)47163d1a8abSmrg lto_balanced_map (int n_lto_partitions, int max_partition_size)
47263d1a8abSmrg {
47363d1a8abSmrg int n_varpool_nodes = 0, varpool_pos = 0, best_varpool_pos = 0;
474c7a68eb7Smrg int best_noreorder_pos = 0;
475c7a68eb7Smrg auto_vec <cgraph_node *> order (symtab->cgraph_count);
47663d1a8abSmrg auto_vec<cgraph_node *> noreorder;
47763d1a8abSmrg auto_vec<varpool_node *> varpool_order;
47863d1a8abSmrg struct cgraph_node *node;
479c7a68eb7Smrg int64_t original_total_size, total_size = 0;
480c7a68eb7Smrg int64_t partition_size;
48163d1a8abSmrg ltrans_partition partition;
48263d1a8abSmrg int last_visited_node = 0;
48363d1a8abSmrg varpool_node *vnode;
484c7a68eb7Smrg int64_t cost = 0, internal = 0;
485c7a68eb7Smrg unsigned int best_n_nodes = 0, best_i = 0;
486c7a68eb7Smrg int64_t best_cost = -1, best_internal = 0, best_size = 0;
48763d1a8abSmrg int npartitions;
48863d1a8abSmrg int current_order = -1;
48963d1a8abSmrg int noreorder_pos = 0;
49063d1a8abSmrg
49163d1a8abSmrg FOR_EACH_VARIABLE (vnode)
49263d1a8abSmrg gcc_assert (!vnode->aux);
49363d1a8abSmrg
49463d1a8abSmrg FOR_EACH_DEFINED_FUNCTION (node)
49563d1a8abSmrg if (node->get_partitioning_class () == SYMBOL_PARTITION)
49663d1a8abSmrg {
49763d1a8abSmrg if (node->no_reorder)
49863d1a8abSmrg noreorder.safe_push (node);
49963d1a8abSmrg else
500c7a68eb7Smrg order.safe_push (node);
50163d1a8abSmrg if (!node->alias)
502*ec02198aSmrg total_size += ipa_size_summaries->get (node)->size;
50363d1a8abSmrg }
50463d1a8abSmrg
50563d1a8abSmrg original_total_size = total_size;
50663d1a8abSmrg
50763d1a8abSmrg /* Streaming works best when the source units do not cross partition
50863d1a8abSmrg boundaries much. This is because importing function from a source
50963d1a8abSmrg unit tends to import a lot of global trees defined there. We should
51063d1a8abSmrg get better about minimizing the function bounday, but until that
51163d1a8abSmrg things works smoother if we order in source order. */
512*ec02198aSmrg order.qsort (tp_first_run_node_cmp);
51363d1a8abSmrg noreorder.qsort (node_cmp);
51463d1a8abSmrg
5150fc04c29Smrg if (dump_file)
51663d1a8abSmrg {
517c7a68eb7Smrg for (unsigned i = 0; i < order.length (); i++)
5180fc04c29Smrg fprintf (dump_file, "Balanced map symbol order:%s:%u\n",
519*ec02198aSmrg order[i]->dump_name (), order[i]->tp_first_run);
520c7a68eb7Smrg for (unsigned i = 0; i < noreorder.length (); i++)
5210fc04c29Smrg fprintf (dump_file, "Balanced map symbol no_reorder:%s:%u\n",
522*ec02198aSmrg noreorder[i]->dump_name (), noreorder[i]->tp_first_run);
52363d1a8abSmrg }
52463d1a8abSmrg
52563d1a8abSmrg /* Collect all variables that should not be reordered. */
52663d1a8abSmrg FOR_EACH_VARIABLE (vnode)
52763d1a8abSmrg if (vnode->get_partitioning_class () == SYMBOL_PARTITION
528c7a68eb7Smrg && vnode->no_reorder)
52963d1a8abSmrg varpool_order.safe_push (vnode);
53063d1a8abSmrg n_varpool_nodes = varpool_order.length ();
531*ec02198aSmrg varpool_order.qsort (node_cmp);
53263d1a8abSmrg
53363d1a8abSmrg /* Compute partition size and create the first partition. */
534*ec02198aSmrg if (param_min_partition_size > max_partition_size)
535c7a68eb7Smrg fatal_error (input_location, "min partition size cannot be greater "
536c7a68eb7Smrg "than max partition size");
53763d1a8abSmrg
53863d1a8abSmrg partition_size = total_size / n_lto_partitions;
539*ec02198aSmrg if (partition_size < param_min_partition_size)
540*ec02198aSmrg partition_size = param_min_partition_size;
54163d1a8abSmrg npartitions = 1;
54263d1a8abSmrg partition = new_partition ("");
5430fc04c29Smrg if (dump_file)
5440fc04c29Smrg fprintf (dump_file, "Total unit size: %" PRId64 ", partition size: %" PRId64 "\n",
54563d1a8abSmrg total_size, partition_size);
54663d1a8abSmrg
54763d1a8abSmrg auto_vec<symtab_node *> next_nodes;
54863d1a8abSmrg
549c7a68eb7Smrg for (unsigned i = 0; i < order.length (); i++)
55063d1a8abSmrg {
55163d1a8abSmrg if (symbol_partitioned_p (order[i]))
55263d1a8abSmrg continue;
55363d1a8abSmrg
55463d1a8abSmrg current_order = order[i]->order;
55563d1a8abSmrg
55663d1a8abSmrg /* Output noreorder and varpool in program order first. */
55763d1a8abSmrg next_nodes.truncate (0);
55863d1a8abSmrg while (varpool_pos < n_varpool_nodes
55963d1a8abSmrg && varpool_order[varpool_pos]->order < current_order)
56063d1a8abSmrg next_nodes.safe_push (varpool_order[varpool_pos++]);
56163d1a8abSmrg while (noreorder_pos < (int)noreorder.length ()
56263d1a8abSmrg && noreorder[noreorder_pos]->order < current_order)
56363d1a8abSmrg next_nodes.safe_push (noreorder[noreorder_pos++]);
56463d1a8abSmrg add_sorted_nodes (next_nodes, partition);
56563d1a8abSmrg
566c7a68eb7Smrg if (!symbol_partitioned_p (order[i]))
56763d1a8abSmrg add_symbol_to_partition (partition, order[i]);
56863d1a8abSmrg
56963d1a8abSmrg
57063d1a8abSmrg /* Once we added a new node to the partition, we also want to add
57163d1a8abSmrg all referenced variables unless they was already added into some
57263d1a8abSmrg earlier partition.
57363d1a8abSmrg add_symbol_to_partition adds possibly multiple nodes and
57463d1a8abSmrg variables that are needed to satisfy needs of ORDER[i].
57563d1a8abSmrg We remember last visited cgraph and varpool node from last iteration
57663d1a8abSmrg of outer loop that allows us to process every new addition.
57763d1a8abSmrg
57863d1a8abSmrg At the same time we compute size of the boundary into COST. Every
57963d1a8abSmrg callgraph or IPA reference edge leaving the partition contributes into
58063d1a8abSmrg COST. Every edge inside partition was earlier computed as one leaving
58163d1a8abSmrg it and thus we need to subtract it from COST. */
58263d1a8abSmrg while (last_visited_node < lto_symtab_encoder_size (partition->encoder))
58363d1a8abSmrg {
58463d1a8abSmrg int j;
58563d1a8abSmrg struct ipa_ref *ref = NULL;
58663d1a8abSmrg symtab_node *snode = lto_symtab_encoder_deref (partition->encoder,
58763d1a8abSmrg last_visited_node);
58863d1a8abSmrg
58963d1a8abSmrg if (cgraph_node *node = dyn_cast <cgraph_node *> (snode))
59063d1a8abSmrg {
59163d1a8abSmrg struct cgraph_edge *edge;
59263d1a8abSmrg
59363d1a8abSmrg
59463d1a8abSmrg last_visited_node++;
59563d1a8abSmrg
59663d1a8abSmrg gcc_assert (node->definition || node->weakref);
59763d1a8abSmrg
59863d1a8abSmrg /* Compute boundary cost of callgraph edges. */
59963d1a8abSmrg for (edge = node->callees; edge; edge = edge->next_callee)
600c7a68eb7Smrg /* Inline edges will always end up local. */
601c7a68eb7Smrg if (edge->inline_failed
602c7a68eb7Smrg && account_reference_p (node, edge->callee))
60363d1a8abSmrg {
604c7a68eb7Smrg int edge_cost = edge->frequency ();
60563d1a8abSmrg int index;
60663d1a8abSmrg
60763d1a8abSmrg if (!edge_cost)
60863d1a8abSmrg edge_cost = 1;
60963d1a8abSmrg gcc_assert (edge_cost > 0);
61063d1a8abSmrg index = lto_symtab_encoder_lookup (partition->encoder,
61163d1a8abSmrg edge->callee);
61263d1a8abSmrg if (index != LCC_NOT_FOUND
61363d1a8abSmrg && index < last_visited_node - 1)
61463d1a8abSmrg cost -= edge_cost, internal += edge_cost;
61563d1a8abSmrg else
61663d1a8abSmrg cost += edge_cost;
61763d1a8abSmrg }
61863d1a8abSmrg for (edge = node->callers; edge; edge = edge->next_caller)
619c7a68eb7Smrg if (edge->inline_failed
620c7a68eb7Smrg && account_reference_p (edge->caller, node))
62163d1a8abSmrg {
622c7a68eb7Smrg int edge_cost = edge->frequency ();
62363d1a8abSmrg int index;
62463d1a8abSmrg
62563d1a8abSmrg gcc_assert (edge->caller->definition);
62663d1a8abSmrg if (!edge_cost)
62763d1a8abSmrg edge_cost = 1;
62863d1a8abSmrg gcc_assert (edge_cost > 0);
62963d1a8abSmrg index = lto_symtab_encoder_lookup (partition->encoder,
63063d1a8abSmrg edge->caller);
63163d1a8abSmrg if (index != LCC_NOT_FOUND
63263d1a8abSmrg && index < last_visited_node - 1)
633c7a68eb7Smrg cost -= edge_cost, internal += edge_cost;
63463d1a8abSmrg else
63563d1a8abSmrg cost += edge_cost;
63663d1a8abSmrg }
63763d1a8abSmrg }
63863d1a8abSmrg else
63963d1a8abSmrg last_visited_node++;
64063d1a8abSmrg
64163d1a8abSmrg /* Compute boundary cost of IPA REF edges and at the same time look into
64263d1a8abSmrg variables referenced from current partition and try to add them. */
643c7a68eb7Smrg for (j = 0; snode->iterate_reference (j, ref); j++)
644c7a68eb7Smrg if (!account_reference_p (snode, ref->referred))
645c7a68eb7Smrg ;
646c7a68eb7Smrg else if (is_a <varpool_node *> (ref->referred))
64763d1a8abSmrg {
64863d1a8abSmrg int index;
64963d1a8abSmrg
65063d1a8abSmrg vnode = dyn_cast <varpool_node *> (ref->referred);
651c7a68eb7Smrg if (!symbol_partitioned_p (vnode)
65263d1a8abSmrg && !vnode->no_reorder
65363d1a8abSmrg && vnode->get_partitioning_class () == SYMBOL_PARTITION)
65463d1a8abSmrg add_symbol_to_partition (partition, vnode);
65563d1a8abSmrg index = lto_symtab_encoder_lookup (partition->encoder,
65663d1a8abSmrg vnode);
65763d1a8abSmrg if (index != LCC_NOT_FOUND
65863d1a8abSmrg && index < last_visited_node - 1)
65963d1a8abSmrg cost--, internal++;
66063d1a8abSmrg else
66163d1a8abSmrg cost++;
66263d1a8abSmrg }
66363d1a8abSmrg else
66463d1a8abSmrg {
66563d1a8abSmrg int index;
66663d1a8abSmrg
66763d1a8abSmrg node = dyn_cast <cgraph_node *> (ref->referred);
66863d1a8abSmrg index = lto_symtab_encoder_lookup (partition->encoder,
66963d1a8abSmrg node);
67063d1a8abSmrg if (index != LCC_NOT_FOUND
67163d1a8abSmrg && index < last_visited_node - 1)
67263d1a8abSmrg cost--, internal++;
67363d1a8abSmrg else
67463d1a8abSmrg cost++;
67563d1a8abSmrg }
676c7a68eb7Smrg for (j = 0; snode->iterate_referring (j, ref); j++)
677c7a68eb7Smrg if (!account_reference_p (ref->referring, snode))
678c7a68eb7Smrg ;
679c7a68eb7Smrg else if (is_a <varpool_node *> (ref->referring))
68063d1a8abSmrg {
68163d1a8abSmrg int index;
68263d1a8abSmrg
68363d1a8abSmrg vnode = dyn_cast <varpool_node *> (ref->referring);
68463d1a8abSmrg gcc_assert (vnode->definition);
68563d1a8abSmrg /* It is better to couple variables with their users,
68663d1a8abSmrg because it allows them to be removed. Coupling
68763d1a8abSmrg with objects they refer to only helps to reduce
68863d1a8abSmrg number of symbols promoted to hidden. */
689c7a68eb7Smrg if (!symbol_partitioned_p (vnode)
69063d1a8abSmrg && !vnode->no_reorder
69163d1a8abSmrg && !vnode->can_remove_if_no_refs_p ()
69263d1a8abSmrg && vnode->get_partitioning_class () == SYMBOL_PARTITION)
69363d1a8abSmrg add_symbol_to_partition (partition, vnode);
69463d1a8abSmrg index = lto_symtab_encoder_lookup (partition->encoder,
69563d1a8abSmrg vnode);
69663d1a8abSmrg if (index != LCC_NOT_FOUND
69763d1a8abSmrg && index < last_visited_node - 1)
698c7a68eb7Smrg cost--, internal++;
69963d1a8abSmrg else
70063d1a8abSmrg cost++;
70163d1a8abSmrg }
70263d1a8abSmrg else
70363d1a8abSmrg {
70463d1a8abSmrg int index;
70563d1a8abSmrg
70663d1a8abSmrg node = dyn_cast <cgraph_node *> (ref->referring);
70763d1a8abSmrg gcc_assert (node->definition);
70863d1a8abSmrg index = lto_symtab_encoder_lookup (partition->encoder,
70963d1a8abSmrg node);
71063d1a8abSmrg if (index != LCC_NOT_FOUND
71163d1a8abSmrg && index < last_visited_node - 1)
712c7a68eb7Smrg cost--, internal++;
71363d1a8abSmrg else
71463d1a8abSmrg cost++;
71563d1a8abSmrg }
71663d1a8abSmrg }
71763d1a8abSmrg
718c7a68eb7Smrg gcc_assert (cost >= 0 && internal >= 0);
719c7a68eb7Smrg
720c7a68eb7Smrg /* If the partition is large enough, start looking for smallest boundary cost.
721c7a68eb7Smrg If partition still seems too small (less than 7/8 of target weight) accept
722c7a68eb7Smrg any cost. If partition has right size, optimize for highest internal/cost.
723c7a68eb7Smrg Later we stop building partition if its size is 9/8 of the target wight. */
724c7a68eb7Smrg if (partition->insns < partition_size * 7 / 8
725c7a68eb7Smrg || best_cost == -1
726c7a68eb7Smrg || (!cost
727c7a68eb7Smrg || ((sreal)best_internal * (sreal) cost
728c7a68eb7Smrg < ((sreal) internal * (sreal)best_cost))))
72963d1a8abSmrg {
73063d1a8abSmrg best_cost = cost;
73163d1a8abSmrg best_internal = internal;
732c7a68eb7Smrg best_size = partition->insns;
73363d1a8abSmrg best_i = i;
73463d1a8abSmrg best_n_nodes = lto_symtab_encoder_size (partition->encoder);
73563d1a8abSmrg best_varpool_pos = varpool_pos;
736c7a68eb7Smrg best_noreorder_pos = noreorder_pos;
73763d1a8abSmrg }
7380fc04c29Smrg if (dump_file)
739*ec02198aSmrg fprintf (dump_file, "Step %i: added %s, size %i, "
740c7a68eb7Smrg "cost %" PRId64 "/%" PRId64 " "
741c7a68eb7Smrg "best %" PRId64 "/%" PRId64", step %i\n", i,
742*ec02198aSmrg order[i]->dump_name (),
74363d1a8abSmrg partition->insns, cost, internal,
74463d1a8abSmrg best_cost, best_internal, best_i);
74563d1a8abSmrg /* Partition is too large, unwind into step when best cost was reached and
74663d1a8abSmrg start new partition. */
747c7a68eb7Smrg if (partition->insns > 9 * partition_size / 8
74863d1a8abSmrg || partition->insns > max_partition_size)
74963d1a8abSmrg {
75063d1a8abSmrg if (best_i != i)
75163d1a8abSmrg {
7520fc04c29Smrg if (dump_file)
7530fc04c29Smrg fprintf (dump_file, "Unwinding %i insertions to step %i\n",
75463d1a8abSmrg i - best_i, best_i);
75563d1a8abSmrg undo_partition (partition, best_n_nodes);
75663d1a8abSmrg varpool_pos = best_varpool_pos;
757c7a68eb7Smrg noreorder_pos = best_noreorder_pos;
75863d1a8abSmrg }
759c7a68eb7Smrg gcc_assert (best_size == partition->insns);
76063d1a8abSmrg i = best_i;
7610fc04c29Smrg if (dump_file)
7620fc04c29Smrg fprintf (dump_file,
763c7a68eb7Smrg "Partition insns: %i (want %" PRId64 ")\n",
764c7a68eb7Smrg partition->insns, partition_size);
76563d1a8abSmrg /* When we are finished, avoid creating empty partition. */
766c7a68eb7Smrg while (i < order.length () - 1 && symbol_partitioned_p (order[i + 1]))
76763d1a8abSmrg i++;
768c7a68eb7Smrg if (i == order.length () - 1)
76963d1a8abSmrg break;
770c7a68eb7Smrg total_size -= partition->insns;
77163d1a8abSmrg partition = new_partition ("");
77263d1a8abSmrg last_visited_node = 0;
77363d1a8abSmrg cost = 0;
77463d1a8abSmrg
7750fc04c29Smrg if (dump_file)
7760fc04c29Smrg fprintf (dump_file, "New partition\n");
77763d1a8abSmrg best_n_nodes = 0;
778c7a68eb7Smrg best_cost = -1;
77963d1a8abSmrg
78063d1a8abSmrg /* Since the size of partitions is just approximate, update the size after
78163d1a8abSmrg we finished current one. */
78263d1a8abSmrg if (npartitions < n_lto_partitions)
78363d1a8abSmrg partition_size = total_size / (n_lto_partitions - npartitions);
78463d1a8abSmrg else
78563d1a8abSmrg /* Watch for overflow. */
78663d1a8abSmrg partition_size = INT_MAX / 16;
78763d1a8abSmrg
7880fc04c29Smrg if (dump_file)
7890fc04c29Smrg fprintf (dump_file,
790c7a68eb7Smrg "Total size: %" PRId64 " partition_size: %" PRId64 "\n",
791c7a68eb7Smrg total_size, partition_size);
792*ec02198aSmrg if (partition_size < param_min_partition_size)
793*ec02198aSmrg partition_size = param_min_partition_size;
79463d1a8abSmrg npartitions ++;
79563d1a8abSmrg }
79663d1a8abSmrg }
79763d1a8abSmrg
79863d1a8abSmrg next_nodes.truncate (0);
79963d1a8abSmrg
80063d1a8abSmrg /* Varables that are not reachable from the code go into last partition. */
80163d1a8abSmrg FOR_EACH_VARIABLE (vnode)
80263d1a8abSmrg if (vnode->get_partitioning_class () == SYMBOL_PARTITION
803c7a68eb7Smrg && !symbol_partitioned_p (vnode))
80463d1a8abSmrg next_nodes.safe_push (vnode);
80563d1a8abSmrg
80663d1a8abSmrg /* Output remaining ordered symbols. */
80763d1a8abSmrg while (varpool_pos < n_varpool_nodes)
80863d1a8abSmrg next_nodes.safe_push (varpool_order[varpool_pos++]);
80963d1a8abSmrg while (noreorder_pos < (int)noreorder.length ())
81063d1a8abSmrg next_nodes.safe_push (noreorder[noreorder_pos++]);
811c7a68eb7Smrg /* For one partition the cost of boundary should be 0 unless we added final
812c7a68eb7Smrg symbols here (these are not accounted) or we have accounting bug. */
813c7a68eb7Smrg gcc_assert (next_nodes.length () || npartitions != 1 || !best_cost || best_cost == -1);
81463d1a8abSmrg add_sorted_nodes (next_nodes, partition);
81563d1a8abSmrg
8160fc04c29Smrg if (dump_file)
81763d1a8abSmrg {
8180fc04c29Smrg fprintf (dump_file, "\nPartition sizes:\n");
81963d1a8abSmrg unsigned partitions = ltrans_partitions.length ();
82063d1a8abSmrg
82163d1a8abSmrg for (unsigned i = 0; i < partitions ; i++)
82263d1a8abSmrg {
82363d1a8abSmrg ltrans_partition p = ltrans_partitions[i];
8240fc04c29Smrg fprintf (dump_file, "partition %d contains %d (%2.2f%%)"
82563d1a8abSmrg " symbols and %d (%2.2f%%) insns\n", i, p->symbols,
826c7a68eb7Smrg 100.0 * p->symbols / order.length (), p->insns,
82763d1a8abSmrg 100.0 * p->insns / original_total_size);
82863d1a8abSmrg }
82963d1a8abSmrg
8300fc04c29Smrg fprintf (dump_file, "\n");
83163d1a8abSmrg }
83263d1a8abSmrg }
83363d1a8abSmrg
83463d1a8abSmrg /* Return true if we must not change the name of the NODE. The name as
83563d1a8abSmrg extracted from the corresponding decl should be passed in NAME. */
83663d1a8abSmrg
83763d1a8abSmrg static bool
must_not_rename(symtab_node * node,const char * name)83863d1a8abSmrg must_not_rename (symtab_node *node, const char *name)
83963d1a8abSmrg {
84063d1a8abSmrg /* Our renaming machinery do not handle more than one change of assembler name.
84163d1a8abSmrg We should not need more than one anyway. */
84263d1a8abSmrg if (node->lto_file_data
84363d1a8abSmrg && lto_get_decl_name_mapping (node->lto_file_data, name) != name)
84463d1a8abSmrg {
8450fc04c29Smrg if (dump_file)
8460fc04c29Smrg fprintf (dump_file,
84763d1a8abSmrg "Not privatizing symbol name: %s. It privatized already.\n",
84863d1a8abSmrg name);
84963d1a8abSmrg return true;
85063d1a8abSmrg }
85163d1a8abSmrg /* Avoid mangling of already mangled clones.
85263d1a8abSmrg ??? should have a flag whether a symbol has a 'private' name already,
85363d1a8abSmrg since we produce some symbols like that i.e. for global constructors
85463d1a8abSmrg that are not really clones. */
85563d1a8abSmrg if (node->unique_name)
85663d1a8abSmrg {
8570fc04c29Smrg if (dump_file)
8580fc04c29Smrg fprintf (dump_file,
85963d1a8abSmrg "Not privatizing symbol name: %s. Has unique name.\n",
86063d1a8abSmrg name);
86163d1a8abSmrg return true;
86263d1a8abSmrg }
86363d1a8abSmrg return false;
86463d1a8abSmrg }
86563d1a8abSmrg
86663d1a8abSmrg /* If we are an offload compiler, we may have to rewrite symbols to be
86763d1a8abSmrg valid on this target. Return either PTR or a modified version of it. */
86863d1a8abSmrg
86963d1a8abSmrg static const char *
maybe_rewrite_identifier(const char * ptr)87063d1a8abSmrg maybe_rewrite_identifier (const char *ptr)
87163d1a8abSmrg {
87263d1a8abSmrg #if defined ACCEL_COMPILER && (defined NO_DOT_IN_LABEL || defined NO_DOLLAR_IN_LABEL)
87363d1a8abSmrg #ifndef NO_DOT_IN_LABEL
87463d1a8abSmrg char valid = '.';
87563d1a8abSmrg const char reject[] = "$";
87663d1a8abSmrg #elif !defined NO_DOLLAR_IN_LABEL
87763d1a8abSmrg char valid = '$';
87863d1a8abSmrg const char reject[] = ".";
87963d1a8abSmrg #else
88063d1a8abSmrg char valid = '_';
88163d1a8abSmrg const char reject[] = ".$";
88263d1a8abSmrg #endif
88363d1a8abSmrg
88463d1a8abSmrg char *copy = NULL;
88563d1a8abSmrg const char *match = ptr;
88663d1a8abSmrg for (;;)
88763d1a8abSmrg {
88863d1a8abSmrg size_t off = strcspn (match, reject);
88963d1a8abSmrg if (match[off] == '\0')
89063d1a8abSmrg break;
89163d1a8abSmrg if (copy == NULL)
89263d1a8abSmrg {
89363d1a8abSmrg copy = xstrdup (ptr);
89463d1a8abSmrg match = copy;
89563d1a8abSmrg }
89663d1a8abSmrg copy[off] = valid;
89763d1a8abSmrg }
89863d1a8abSmrg return match;
89963d1a8abSmrg #else
90063d1a8abSmrg return ptr;
90163d1a8abSmrg #endif
90263d1a8abSmrg }
90363d1a8abSmrg
90463d1a8abSmrg /* Ensure that the symbol in NODE is valid for the target, and if not,
90563d1a8abSmrg rewrite it. */
90663d1a8abSmrg
90763d1a8abSmrg static void
validize_symbol_for_target(symtab_node * node)90863d1a8abSmrg validize_symbol_for_target (symtab_node *node)
90963d1a8abSmrg {
91063d1a8abSmrg tree decl = node->decl;
91163d1a8abSmrg const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
91263d1a8abSmrg
91363d1a8abSmrg if (must_not_rename (node, name))
91463d1a8abSmrg return;
91563d1a8abSmrg
91663d1a8abSmrg const char *name2 = maybe_rewrite_identifier (name);
91763d1a8abSmrg if (name2 != name)
91863d1a8abSmrg {
91963d1a8abSmrg symtab->change_decl_assembler_name (decl, get_identifier (name2));
92063d1a8abSmrg if (node->lto_file_data)
92163d1a8abSmrg lto_record_renamed_decl (node->lto_file_data, name,
92263d1a8abSmrg IDENTIFIER_POINTER
92363d1a8abSmrg (DECL_ASSEMBLER_NAME (decl)));
92463d1a8abSmrg }
92563d1a8abSmrg }
92663d1a8abSmrg
9270fc04c29Smrg /* Maps symbol names to unique lto clone counters. */
9280fc04c29Smrg static hash_map<const char *, unsigned> *lto_clone_numbers;
9290fc04c29Smrg
93063d1a8abSmrg /* Helper for privatize_symbol_name. Mangle NODE symbol name
93163d1a8abSmrg represented by DECL. */
93263d1a8abSmrg
93363d1a8abSmrg static bool
privatize_symbol_name_1(symtab_node * node,tree decl)93463d1a8abSmrg privatize_symbol_name_1 (symtab_node *node, tree decl)
93563d1a8abSmrg {
93663d1a8abSmrg const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
93763d1a8abSmrg
93863d1a8abSmrg if (must_not_rename (node, name))
93963d1a8abSmrg return false;
94063d1a8abSmrg
94163d1a8abSmrg name = maybe_rewrite_identifier (name);
9420fc04c29Smrg unsigned &clone_number = lto_clone_numbers->get_or_insert (name);
94363d1a8abSmrg symtab->change_decl_assembler_name (decl,
9440fc04c29Smrg clone_function_name (
9450fc04c29Smrg name, "lto_priv", clone_number));
9460fc04c29Smrg clone_number++;
94763d1a8abSmrg
94863d1a8abSmrg if (node->lto_file_data)
94963d1a8abSmrg lto_record_renamed_decl (node->lto_file_data, name,
95063d1a8abSmrg IDENTIFIER_POINTER
95163d1a8abSmrg (DECL_ASSEMBLER_NAME (decl)));
95263d1a8abSmrg
9530fc04c29Smrg if (dump_file)
9540fc04c29Smrg fprintf (dump_file,
95563d1a8abSmrg "Privatizing symbol name: %s -> %s\n",
95663d1a8abSmrg name, IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl)));
95763d1a8abSmrg
95863d1a8abSmrg return true;
95963d1a8abSmrg }
96063d1a8abSmrg
96163d1a8abSmrg /* Mangle NODE symbol name into a local name.
96263d1a8abSmrg This is necessary to do
96363d1a8abSmrg 1) if two or more static vars of same assembler name
96463d1a8abSmrg are merged into single ltrans unit.
96563d1a8abSmrg 2) if previously static var was promoted hidden to avoid possible conflict
96663d1a8abSmrg with symbols defined out of the LTO world. */
96763d1a8abSmrg
96863d1a8abSmrg static bool
privatize_symbol_name(symtab_node * node)96963d1a8abSmrg privatize_symbol_name (symtab_node *node)
97063d1a8abSmrg {
97163d1a8abSmrg if (!privatize_symbol_name_1 (node, node->decl))
97263d1a8abSmrg return false;
97363d1a8abSmrg
97463d1a8abSmrg return true;
97563d1a8abSmrg }
97663d1a8abSmrg
97763d1a8abSmrg /* Promote variable VNODE to be static. */
97863d1a8abSmrg
97963d1a8abSmrg static void
promote_symbol(symtab_node * node)98063d1a8abSmrg promote_symbol (symtab_node *node)
98163d1a8abSmrg {
98263d1a8abSmrg /* We already promoted ... */
98363d1a8abSmrg if (DECL_VISIBILITY (node->decl) == VISIBILITY_HIDDEN
98463d1a8abSmrg && DECL_VISIBILITY_SPECIFIED (node->decl)
98563d1a8abSmrg && TREE_PUBLIC (node->decl))
98663d1a8abSmrg {
98763d1a8abSmrg validize_symbol_for_target (node);
98863d1a8abSmrg return;
98963d1a8abSmrg }
99063d1a8abSmrg
99163d1a8abSmrg gcc_checking_assert (!TREE_PUBLIC (node->decl)
99263d1a8abSmrg && !DECL_EXTERNAL (node->decl));
99363d1a8abSmrg /* Be sure that newly public symbol does not conflict with anything already
99463d1a8abSmrg defined by the non-LTO part. */
99563d1a8abSmrg privatize_symbol_name (node);
99663d1a8abSmrg TREE_PUBLIC (node->decl) = 1;
99763d1a8abSmrg DECL_VISIBILITY (node->decl) = VISIBILITY_HIDDEN;
99863d1a8abSmrg DECL_VISIBILITY_SPECIFIED (node->decl) = true;
9990fc04c29Smrg if (dump_file)
10000fc04c29Smrg fprintf (dump_file,
1001*ec02198aSmrg "Promoting as hidden: %s (%s)\n", node->dump_name (),
100263d1a8abSmrg IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
100363d1a8abSmrg
100463d1a8abSmrg /* Promoting a symbol also promotes all transparent aliases with exception
100563d1a8abSmrg of weakref where the visibility flags are always wrong and set to
100663d1a8abSmrg !PUBLIC. */
100763d1a8abSmrg ipa_ref *ref;
100863d1a8abSmrg for (unsigned i = 0; node->iterate_direct_aliases (i, ref); i++)
100963d1a8abSmrg {
101063d1a8abSmrg struct symtab_node *alias = ref->referring;
101163d1a8abSmrg if (alias->transparent_alias && !alias->weakref)
101263d1a8abSmrg {
101363d1a8abSmrg TREE_PUBLIC (alias->decl) = 1;
101463d1a8abSmrg DECL_VISIBILITY (alias->decl) = VISIBILITY_HIDDEN;
101563d1a8abSmrg DECL_VISIBILITY_SPECIFIED (alias->decl) = true;
10160fc04c29Smrg if (dump_file)
10170fc04c29Smrg fprintf (dump_file,
101863d1a8abSmrg "Promoting alias as hidden: %s\n",
101963d1a8abSmrg IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
102063d1a8abSmrg }
102163d1a8abSmrg gcc_assert (!alias->weakref || TREE_PUBLIC (alias->decl));
102263d1a8abSmrg }
102363d1a8abSmrg }
102463d1a8abSmrg
102563d1a8abSmrg /* Return true if NODE needs named section even if it won't land in
102663d1a8abSmrg the partition symbol table.
102763d1a8abSmrg
102863d1a8abSmrg FIXME: we should really not use named sections for inline clones
102963d1a8abSmrg and master clones. */
103063d1a8abSmrg
103163d1a8abSmrg static bool
may_need_named_section_p(lto_symtab_encoder_t encoder,symtab_node * node)103263d1a8abSmrg may_need_named_section_p (lto_symtab_encoder_t encoder, symtab_node *node)
103363d1a8abSmrg {
103463d1a8abSmrg struct cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
103563d1a8abSmrg if (!cnode)
103663d1a8abSmrg return false;
103763d1a8abSmrg if (node->real_symbol_p ())
103863d1a8abSmrg return false;
103963d1a8abSmrg return (!encoder
104063d1a8abSmrg || (lto_symtab_encoder_lookup (encoder, node) != LCC_NOT_FOUND
104163d1a8abSmrg && lto_symtab_encoder_encode_body_p (encoder,
104263d1a8abSmrg cnode)));
104363d1a8abSmrg }
104463d1a8abSmrg
104563d1a8abSmrg /* If NODE represents a static variable. See if there are other variables
104663d1a8abSmrg of the same name in partition ENCODER (or in whole compilation unit if
104763d1a8abSmrg ENCODER is NULL) and if so, mangle the statics. Always mangle all
104863d1a8abSmrg conflicting statics, so we reduce changes of silently miscompiling
104963d1a8abSmrg asm statements referring to them by symbol name. */
105063d1a8abSmrg
105163d1a8abSmrg static void
rename_statics(lto_symtab_encoder_t encoder,symtab_node * node)105263d1a8abSmrg rename_statics (lto_symtab_encoder_t encoder, symtab_node *node)
105363d1a8abSmrg {
105463d1a8abSmrg tree decl = node->decl;
105563d1a8abSmrg symtab_node *s;
105663d1a8abSmrg tree name = DECL_ASSEMBLER_NAME (decl);
105763d1a8abSmrg
105863d1a8abSmrg /* See if this is static symbol. */
105963d1a8abSmrg if (((node->externally_visible && !node->weakref)
106063d1a8abSmrg /* FIXME: externally_visible is somewhat illogically not set for
106163d1a8abSmrg external symbols (i.e. those not defined). Remove this test
106263d1a8abSmrg once this is fixed. */
106363d1a8abSmrg || DECL_EXTERNAL (node->decl)
106463d1a8abSmrg || !node->real_symbol_p ())
106563d1a8abSmrg && !may_need_named_section_p (encoder, node))
106663d1a8abSmrg return;
106763d1a8abSmrg
106863d1a8abSmrg /* Now walk symbols sharing the same name and see if there are any conflicts.
106963d1a8abSmrg (all types of symbols counts here, since we cannot have static of the
107063d1a8abSmrg same name as external or public symbol.) */
107163d1a8abSmrg for (s = symtab_node::get_for_asmname (name);
107263d1a8abSmrg s; s = s->next_sharing_asm_name)
107363d1a8abSmrg if ((s->real_symbol_p () || may_need_named_section_p (encoder, s))
107463d1a8abSmrg && s->decl != node->decl
107563d1a8abSmrg && (!encoder
107663d1a8abSmrg || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND))
107763d1a8abSmrg break;
107863d1a8abSmrg
107963d1a8abSmrg /* OK, no confict, so we have nothing to do. */
108063d1a8abSmrg if (!s)
108163d1a8abSmrg return;
108263d1a8abSmrg
10830fc04c29Smrg if (dump_file)
10840fc04c29Smrg fprintf (dump_file,
1085*ec02198aSmrg "Renaming statics with asm name: %s\n", node->dump_name ());
108663d1a8abSmrg
108763d1a8abSmrg /* Assign every symbol in the set that shares the same ASM name an unique
108863d1a8abSmrg mangled name. */
108963d1a8abSmrg for (s = symtab_node::get_for_asmname (name); s;)
109063d1a8abSmrg if ((!s->externally_visible || s->weakref)
109163d1a8abSmrg /* Transparent aliases having same name as target are renamed at a
109263d1a8abSmrg time their target gets new name. Transparent aliases that use
109363d1a8abSmrg separate assembler name require the name to be unique. */
109463d1a8abSmrg && (!s->transparent_alias || !s->definition || s->weakref
109563d1a8abSmrg || !symbol_table::assembler_names_equal_p
109663d1a8abSmrg (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (s->decl)),
109763d1a8abSmrg IDENTIFIER_POINTER
109863d1a8abSmrg (DECL_ASSEMBLER_NAME (s->get_alias_target()->decl))))
109963d1a8abSmrg && ((s->real_symbol_p ()
110063d1a8abSmrg && !DECL_EXTERNAL (s->decl)
110163d1a8abSmrg && !TREE_PUBLIC (s->decl))
110263d1a8abSmrg || may_need_named_section_p (encoder, s))
110363d1a8abSmrg && (!encoder
110463d1a8abSmrg || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND))
110563d1a8abSmrg {
110663d1a8abSmrg if (privatize_symbol_name (s))
110763d1a8abSmrg /* Re-start from beginning since we do not know how many
110863d1a8abSmrg symbols changed a name. */
110963d1a8abSmrg s = symtab_node::get_for_asmname (name);
111063d1a8abSmrg else s = s->next_sharing_asm_name;
111163d1a8abSmrg }
111263d1a8abSmrg else s = s->next_sharing_asm_name;
111363d1a8abSmrg }
111463d1a8abSmrg
111563d1a8abSmrg /* Find out all static decls that need to be promoted to global because
111663d1a8abSmrg of cross file sharing. This function must be run in the WPA mode after
111763d1a8abSmrg all inlinees are added. */
111863d1a8abSmrg
111963d1a8abSmrg void
lto_promote_cross_file_statics(void)112063d1a8abSmrg lto_promote_cross_file_statics (void)
112163d1a8abSmrg {
112263d1a8abSmrg unsigned i, n_sets;
112363d1a8abSmrg
112463d1a8abSmrg gcc_assert (flag_wpa);
112563d1a8abSmrg
112663d1a8abSmrg lto_stream_offload_p = false;
112763d1a8abSmrg select_what_to_stream ();
112863d1a8abSmrg
112963d1a8abSmrg /* First compute boundaries. */
113063d1a8abSmrg n_sets = ltrans_partitions.length ();
113163d1a8abSmrg for (i = 0; i < n_sets; i++)
113263d1a8abSmrg {
113363d1a8abSmrg ltrans_partition part
113463d1a8abSmrg = ltrans_partitions[i];
113563d1a8abSmrg part->encoder = compute_ltrans_boundary (part->encoder);
113663d1a8abSmrg }
113763d1a8abSmrg
11380fc04c29Smrg lto_clone_numbers = new hash_map<const char *, unsigned>;
11390fc04c29Smrg
114063d1a8abSmrg /* Look at boundaries and promote symbols as needed. */
114163d1a8abSmrg for (i = 0; i < n_sets; i++)
114263d1a8abSmrg {
114363d1a8abSmrg lto_symtab_encoder_iterator lsei;
114463d1a8abSmrg lto_symtab_encoder_t encoder = ltrans_partitions[i]->encoder;
114563d1a8abSmrg
114663d1a8abSmrg for (lsei = lsei_start (encoder); !lsei_end_p (lsei);
114763d1a8abSmrg lsei_next (&lsei))
114863d1a8abSmrg {
114963d1a8abSmrg symtab_node *node = lsei_node (lsei);
115063d1a8abSmrg
115163d1a8abSmrg /* If symbol is static, rename it if its assembler name
115263d1a8abSmrg clashes with anything else in this unit. */
115363d1a8abSmrg rename_statics (encoder, node);
115463d1a8abSmrg
115563d1a8abSmrg /* No need to promote if symbol already is externally visible ... */
115663d1a8abSmrg if (node->externally_visible
115763d1a8abSmrg /* ... or if it is part of current partition ... */
115863d1a8abSmrg || lto_symtab_encoder_in_partition_p (encoder, node)
115963d1a8abSmrg /* ... or if we do not partition it. This mean that it will
116063d1a8abSmrg appear in every partition referencing it. */
116163d1a8abSmrg || node->get_partitioning_class () != SYMBOL_PARTITION)
116263d1a8abSmrg {
116363d1a8abSmrg validize_symbol_for_target (node);
116463d1a8abSmrg continue;
116563d1a8abSmrg }
116663d1a8abSmrg
116763d1a8abSmrg promote_symbol (node);
116863d1a8abSmrg }
116963d1a8abSmrg }
11700fc04c29Smrg delete lto_clone_numbers;
117163d1a8abSmrg }
117263d1a8abSmrg
117363d1a8abSmrg /* Rename statics in the whole unit in the case that
117463d1a8abSmrg we do -flto-partition=none. */
117563d1a8abSmrg
117663d1a8abSmrg void
lto_promote_statics_nonwpa(void)117763d1a8abSmrg lto_promote_statics_nonwpa (void)
117863d1a8abSmrg {
117963d1a8abSmrg symtab_node *node;
11800fc04c29Smrg
11810fc04c29Smrg lto_clone_numbers = new hash_map<const char *, unsigned>;
118263d1a8abSmrg FOR_EACH_SYMBOL (node)
118363d1a8abSmrg {
118463d1a8abSmrg rename_statics (NULL, node);
118563d1a8abSmrg validize_symbol_for_target (node);
118663d1a8abSmrg }
11870fc04c29Smrg delete lto_clone_numbers;
118863d1a8abSmrg }
1189