138fd1498Szrj /* LTO partitioning logic routines.
238fd1498Szrj Copyright (C) 2009-2018 Free Software Foundation, Inc.
338fd1498Szrj
438fd1498Szrj This file is part of GCC.
538fd1498Szrj
638fd1498Szrj GCC is free software; you can redistribute it and/or modify it under
738fd1498Szrj the terms of the GNU General Public License as published by the Free
838fd1498Szrj Software Foundation; either version 3, or (at your option) any later
938fd1498Szrj version.
1038fd1498Szrj
1138fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT ANY
1238fd1498Szrj WARRANTY; without even the implied warranty of MERCHANTABILITY or
1338fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1438fd1498Szrj for more details.
1538fd1498Szrj
1638fd1498Szrj You should have received a copy of the GNU General Public License
1738fd1498Szrj along with GCC; see the file COPYING3. If not see
1838fd1498Szrj <http://www.gnu.org/licenses/>. */
1938fd1498Szrj
2038fd1498Szrj #include "config.h"
2138fd1498Szrj #include "system.h"
2238fd1498Szrj #include "coretypes.h"
2338fd1498Szrj #include "target.h"
2438fd1498Szrj #include "function.h"
2538fd1498Szrj #include "basic-block.h"
2638fd1498Szrj #include "tree.h"
2738fd1498Szrj #include "gimple.h"
2838fd1498Szrj #include "alloc-pool.h"
2938fd1498Szrj #include "stringpool.h"
3038fd1498Szrj #include "cgraph.h"
3138fd1498Szrj #include "lto-streamer.h"
3238fd1498Szrj #include "params.h"
3338fd1498Szrj #include "symbol-summary.h"
3438fd1498Szrj #include "tree-vrp.h"
3538fd1498Szrj #include "ipa-prop.h"
3638fd1498Szrj #include "ipa-fnsummary.h"
3738fd1498Szrj #include "lto-partition.h"
38*58e805e6Szrj #include "sreal.h"
3938fd1498Szrj
4038fd1498Szrj vec<ltrans_partition> ltrans_partitions;
4138fd1498Szrj
4238fd1498Szrj static void add_symbol_to_partition (ltrans_partition part, symtab_node *node);
4338fd1498Szrj
4438fd1498Szrj
45*58e805e6Szrj /* Helper for qsort; compare partitions and return one with smaller order. */
46*58e805e6Szrj
47*58e805e6Szrj static int
cmp_partitions_order(const void * a,const void * b)48*58e805e6Szrj cmp_partitions_order (const void *a, const void *b)
49*58e805e6Szrj {
50*58e805e6Szrj const struct ltrans_partition_def *pa
51*58e805e6Szrj = *(struct ltrans_partition_def *const *)a;
52*58e805e6Szrj const struct ltrans_partition_def *pb
53*58e805e6Szrj = *(struct ltrans_partition_def *const *)b;
54*58e805e6Szrj int ordera = -1, orderb = -1;
55*58e805e6Szrj
56*58e805e6Szrj if (lto_symtab_encoder_size (pa->encoder))
57*58e805e6Szrj ordera = lto_symtab_encoder_deref (pa->encoder, 0)->order;
58*58e805e6Szrj if (lto_symtab_encoder_size (pb->encoder))
59*58e805e6Szrj orderb = lto_symtab_encoder_deref (pb->encoder, 0)->order;
60*58e805e6Szrj return orderb - ordera;
61*58e805e6Szrj }
62*58e805e6Szrj
6338fd1498Szrj /* Create new partition with name NAME. */
6438fd1498Szrj
6538fd1498Szrj static ltrans_partition
new_partition(const char * name)6638fd1498Szrj new_partition (const char *name)
6738fd1498Szrj {
6838fd1498Szrj ltrans_partition part = XCNEW (struct ltrans_partition_def);
6938fd1498Szrj part->encoder = lto_symtab_encoder_new (false);
7038fd1498Szrj part->name = name;
7138fd1498Szrj part->insns = 0;
7238fd1498Szrj part->symbols = 0;
7338fd1498Szrj ltrans_partitions.safe_push (part);
7438fd1498Szrj return part;
7538fd1498Szrj }
7638fd1498Szrj
7738fd1498Szrj /* Free memory used by ltrans datastructures. */
7838fd1498Szrj
7938fd1498Szrj void
free_ltrans_partitions(void)8038fd1498Szrj free_ltrans_partitions (void)
8138fd1498Szrj {
8238fd1498Szrj unsigned int idx;
8338fd1498Szrj ltrans_partition part;
8438fd1498Szrj for (idx = 0; ltrans_partitions.iterate (idx, &part); idx++)
8538fd1498Szrj {
8638fd1498Szrj if (part->initializers_visited)
8738fd1498Szrj delete part->initializers_visited;
8838fd1498Szrj /* Symtab encoder is freed after streaming. */
8938fd1498Szrj free (part);
9038fd1498Szrj }
9138fd1498Szrj ltrans_partitions.release ();
9238fd1498Szrj }
9338fd1498Szrj
9438fd1498Szrj /* Return true if symbol is already in some partition. */
9538fd1498Szrj
9638fd1498Szrj static inline bool
symbol_partitioned_p(symtab_node * node)9738fd1498Szrj symbol_partitioned_p (symtab_node *node)
9838fd1498Szrj {
9938fd1498Szrj return node->aux;
10038fd1498Szrj }
10138fd1498Szrj
10238fd1498Szrj /* Add references into the partition. */
10338fd1498Szrj static void
add_references_to_partition(ltrans_partition part,symtab_node * node)10438fd1498Szrj add_references_to_partition (ltrans_partition part, symtab_node *node)
10538fd1498Szrj {
10638fd1498Szrj int i;
10738fd1498Szrj struct ipa_ref *ref = NULL;
10838fd1498Szrj
10938fd1498Szrj /* Add all duplicated references to the partition. */
11038fd1498Szrj for (i = 0; node->iterate_reference (i, ref); i++)
11138fd1498Szrj if (ref->referred->get_partitioning_class () == SYMBOL_DUPLICATE)
11238fd1498Szrj add_symbol_to_partition (part, ref->referred);
11338fd1498Szrj /* References to a readonly variable may be constant foled into its value.
11438fd1498Szrj Recursively look into the initializers of the constant variable and add
11538fd1498Szrj references, too. */
11638fd1498Szrj else if (is_a <varpool_node *> (ref->referred)
11738fd1498Szrj && (dyn_cast <varpool_node *> (ref->referred)
11838fd1498Szrj ->ctor_useable_for_folding_p ()
11938fd1498Szrj || POINTER_BOUNDS_P (ref->referred->decl))
12038fd1498Szrj && !lto_symtab_encoder_in_partition_p (part->encoder, ref->referred))
12138fd1498Szrj {
12238fd1498Szrj if (!part->initializers_visited)
12338fd1498Szrj part->initializers_visited = new hash_set<symtab_node *>;
12438fd1498Szrj if (!part->initializers_visited->add (ref->referred))
12538fd1498Szrj add_references_to_partition (part, ref->referred);
12638fd1498Szrj }
12738fd1498Szrj }
12838fd1498Szrj
12938fd1498Szrj /* Helper function for add_symbol_to_partition doing the actual dirty work
13038fd1498Szrj of adding NODE to PART. */
13138fd1498Szrj
13238fd1498Szrj static bool
add_symbol_to_partition_1(ltrans_partition part,symtab_node * node)13338fd1498Szrj add_symbol_to_partition_1 (ltrans_partition part, symtab_node *node)
13438fd1498Szrj {
13538fd1498Szrj enum symbol_partitioning_class c = node->get_partitioning_class ();
13638fd1498Szrj struct ipa_ref *ref;
13738fd1498Szrj symtab_node *node1;
13838fd1498Szrj
13938fd1498Szrj /* If NODE is already there, we have nothing to do. */
14038fd1498Szrj if (lto_symtab_encoder_in_partition_p (part->encoder, node))
14138fd1498Szrj return true;
14238fd1498Szrj
14338fd1498Szrj /* non-duplicated aliases or tunks of a duplicated symbol needs to be output
14438fd1498Szrj just once.
14538fd1498Szrj
14638fd1498Szrj Be lax about comdats; they may or may not be duplicated and we may
14738fd1498Szrj end up in need to duplicate keyed comdat because it has unkeyed alias. */
14838fd1498Szrj if (c == SYMBOL_PARTITION && !DECL_COMDAT (node->decl)
14938fd1498Szrj && symbol_partitioned_p (node))
15038fd1498Szrj return false;
15138fd1498Szrj
15238fd1498Szrj /* Be sure that we never try to duplicate partitioned symbol
15338fd1498Szrj or add external symbol. */
15438fd1498Szrj gcc_assert (c != SYMBOL_EXTERNAL
15538fd1498Szrj && (c == SYMBOL_DUPLICATE || !symbol_partitioned_p (node)));
15638fd1498Szrj
15738fd1498Szrj part->symbols++;
15838fd1498Szrj
15938fd1498Szrj lto_set_symtab_encoder_in_partition (part->encoder, node);
16038fd1498Szrj
16138fd1498Szrj if (symbol_partitioned_p (node))
16238fd1498Szrj {
16338fd1498Szrj node->in_other_partition = 1;
16438fd1498Szrj if (symtab->dump_file)
16538fd1498Szrj fprintf (symtab->dump_file,
16638fd1498Szrj "Symbol node %s now used in multiple partitions\n",
16738fd1498Szrj node->name ());
16838fd1498Szrj }
16938fd1498Szrj node->aux = (void *)((size_t)node->aux + 1);
17038fd1498Szrj
17138fd1498Szrj if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
17238fd1498Szrj {
17338fd1498Szrj struct cgraph_edge *e;
174*58e805e6Szrj if (!node->alias && c == SYMBOL_PARTITION)
175*58e805e6Szrj part->insns += ipa_fn_summaries->get (cnode)->size;
17638fd1498Szrj
17738fd1498Szrj /* Add all inline clones and callees that are duplicated. */
17838fd1498Szrj for (e = cnode->callees; e; e = e->next_callee)
17938fd1498Szrj if (!e->inline_failed)
18038fd1498Szrj add_symbol_to_partition_1 (part, e->callee);
18138fd1498Szrj else if (e->callee->get_partitioning_class () == SYMBOL_DUPLICATE)
18238fd1498Szrj add_symbol_to_partition (part, e->callee);
18338fd1498Szrj
18438fd1498Szrj /* Add all thunks associated with the function. */
18538fd1498Szrj for (e = cnode->callers; e; e = e->next_caller)
18638fd1498Szrj if (e->caller->thunk.thunk_p && !e->caller->global.inlined_to)
18738fd1498Szrj add_symbol_to_partition_1 (part, e->caller);
18838fd1498Szrj
18938fd1498Szrj /* Instrumented version is actually the same function.
19038fd1498Szrj Therefore put it into the same partition. */
19138fd1498Szrj if (cnode->instrumented_version)
19238fd1498Szrj add_symbol_to_partition_1 (part, cnode->instrumented_version);
19338fd1498Szrj }
19438fd1498Szrj
19538fd1498Szrj add_references_to_partition (part, node);
19638fd1498Szrj
19738fd1498Szrj /* Add all aliases associated with the symbol. */
19838fd1498Szrj
19938fd1498Szrj FOR_EACH_ALIAS (node, ref)
20038fd1498Szrj if (!ref->referring->transparent_alias)
20138fd1498Szrj add_symbol_to_partition_1 (part, ref->referring);
20238fd1498Szrj else
20338fd1498Szrj {
20438fd1498Szrj struct ipa_ref *ref2;
20538fd1498Szrj /* We do not need to add transparent aliases if they are not used.
20638fd1498Szrj However we must add aliases of transparent aliases if they exist. */
20738fd1498Szrj FOR_EACH_ALIAS (ref->referring, ref2)
20838fd1498Szrj {
20938fd1498Szrj /* Nested transparent aliases are not permitted. */
21038fd1498Szrj gcc_checking_assert (!ref2->referring->transparent_alias);
21138fd1498Szrj add_symbol_to_partition_1 (part, ref2->referring);
21238fd1498Szrj }
21338fd1498Szrj }
21438fd1498Szrj
21538fd1498Szrj /* Ensure that SAME_COMDAT_GROUP lists all allways added in a group. */
21638fd1498Szrj if (node->same_comdat_group)
21738fd1498Szrj for (node1 = node->same_comdat_group;
21838fd1498Szrj node1 != node; node1 = node1->same_comdat_group)
21938fd1498Szrj if (!node->alias)
22038fd1498Szrj {
22138fd1498Szrj bool added = add_symbol_to_partition_1 (part, node1);
22238fd1498Szrj gcc_assert (added);
22338fd1498Szrj }
22438fd1498Szrj return true;
22538fd1498Szrj }
22638fd1498Szrj
22738fd1498Szrj /* If symbol NODE is really part of other symbol's definition (i.e. it is
22838fd1498Szrj internal label, thunk, alias or so), return the outer symbol.
22938fd1498Szrj When add_symbol_to_partition_1 is called on the outer symbol it must
23038fd1498Szrj eventually add NODE, too. */
23138fd1498Szrj static symtab_node *
contained_in_symbol(symtab_node * node)23238fd1498Szrj contained_in_symbol (symtab_node *node)
23338fd1498Szrj {
23438fd1498Szrj /* There is no need to consider transparent aliases to be part of the
23538fd1498Szrj definition: they are only useful insite the partition they are output
23638fd1498Szrj and thus we will always see an explicit reference to it. */
23738fd1498Szrj if (node->transparent_alias)
23838fd1498Szrj return node;
23938fd1498Szrj if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
24038fd1498Szrj {
24138fd1498Szrj cnode = cnode->function_symbol ();
24238fd1498Szrj if (cnode->global.inlined_to)
24338fd1498Szrj cnode = cnode->global.inlined_to;
24438fd1498Szrj return cnode;
24538fd1498Szrj }
24638fd1498Szrj else if (varpool_node *vnode = dyn_cast <varpool_node *> (node))
24738fd1498Szrj return vnode->ultimate_alias_target ();
24838fd1498Szrj return node;
24938fd1498Szrj }
25038fd1498Szrj
25138fd1498Szrj /* Add symbol NODE to partition. When definition of NODE is part
25238fd1498Szrj of other symbol definition, add the other symbol, too. */
25338fd1498Szrj
25438fd1498Szrj static void
add_symbol_to_partition(ltrans_partition part,symtab_node * node)25538fd1498Szrj add_symbol_to_partition (ltrans_partition part, symtab_node *node)
25638fd1498Szrj {
25738fd1498Szrj symtab_node *node1;
25838fd1498Szrj
25938fd1498Szrj /* Verify that we do not try to duplicate something that can not be. */
26038fd1498Szrj gcc_checking_assert (node->get_partitioning_class () == SYMBOL_DUPLICATE
26138fd1498Szrj || !symbol_partitioned_p (node));
26238fd1498Szrj
26338fd1498Szrj while ((node1 = contained_in_symbol (node)) != node)
26438fd1498Szrj node = node1;
26538fd1498Szrj
26638fd1498Szrj /* If we have duplicated symbol contained in something we can not duplicate,
26738fd1498Szrj we are very badly screwed. The other way is possible, so we do not
26838fd1498Szrj assert this in add_symbol_to_partition_1.
26938fd1498Szrj
27038fd1498Szrj Be lax about comdats; they may or may not be duplicated and we may
27138fd1498Szrj end up in need to duplicate keyed comdat because it has unkeyed alias. */
27238fd1498Szrj
27338fd1498Szrj gcc_assert (node->get_partitioning_class () == SYMBOL_DUPLICATE
27438fd1498Szrj || DECL_COMDAT (node->decl)
27538fd1498Szrj || !symbol_partitioned_p (node));
27638fd1498Szrj
27738fd1498Szrj add_symbol_to_partition_1 (part, node);
27838fd1498Szrj }
27938fd1498Szrj
28038fd1498Szrj /* Undo all additions until number of cgraph nodes in PARITION is N_CGRAPH_NODES
28138fd1498Szrj and number of varpool nodes is N_VARPOOL_NODES. */
28238fd1498Szrj
28338fd1498Szrj static void
undo_partition(ltrans_partition partition,unsigned int n_nodes)28438fd1498Szrj undo_partition (ltrans_partition partition, unsigned int n_nodes)
28538fd1498Szrj {
28638fd1498Szrj while (lto_symtab_encoder_size (partition->encoder) > (int)n_nodes)
28738fd1498Szrj {
28838fd1498Szrj symtab_node *node = lto_symtab_encoder_deref (partition->encoder,
28938fd1498Szrj n_nodes);
29038fd1498Szrj partition->symbols--;
29138fd1498Szrj cgraph_node *cnode;
29238fd1498Szrj
29338fd1498Szrj /* After UNDO we no longer know what was visited. */
29438fd1498Szrj if (partition->initializers_visited)
29538fd1498Szrj delete partition->initializers_visited;
29638fd1498Szrj partition->initializers_visited = NULL;
29738fd1498Szrj
298*58e805e6Szrj if (!node->alias && (cnode = dyn_cast <cgraph_node *> (node))
299*58e805e6Szrj && node->get_partitioning_class () == SYMBOL_PARTITION)
300*58e805e6Szrj partition->insns -= ipa_fn_summaries->get (cnode)->size;
30138fd1498Szrj lto_symtab_encoder_delete_node (partition->encoder, node);
30238fd1498Szrj node->aux = (void *)((size_t)node->aux - 1);
30338fd1498Szrj }
30438fd1498Szrj }
30538fd1498Szrj
30638fd1498Szrj /* Group cgrah nodes by input files. This is used mainly for testing
30738fd1498Szrj right now. */
30838fd1498Szrj
30938fd1498Szrj void
lto_1_to_1_map(void)31038fd1498Szrj lto_1_to_1_map (void)
31138fd1498Szrj {
31238fd1498Szrj symtab_node *node;
31338fd1498Szrj struct lto_file_decl_data *file_data;
31438fd1498Szrj hash_map<lto_file_decl_data *, ltrans_partition> pmap;
31538fd1498Szrj ltrans_partition partition;
31638fd1498Szrj int npartitions = 0;
31738fd1498Szrj
31838fd1498Szrj FOR_EACH_SYMBOL (node)
31938fd1498Szrj {
32038fd1498Szrj if (node->get_partitioning_class () != SYMBOL_PARTITION
32138fd1498Szrj || symbol_partitioned_p (node))
32238fd1498Szrj continue;
32338fd1498Szrj
32438fd1498Szrj file_data = node->lto_file_data;
32538fd1498Szrj
32638fd1498Szrj if (file_data)
32738fd1498Szrj {
32838fd1498Szrj ltrans_partition *slot = &pmap.get_or_insert (file_data);
32938fd1498Szrj if (*slot)
33038fd1498Szrj partition = *slot;
33138fd1498Szrj else
33238fd1498Szrj {
33338fd1498Szrj partition = new_partition (file_data->file_name);
33438fd1498Szrj *slot = partition;
33538fd1498Szrj npartitions++;
33638fd1498Szrj }
33738fd1498Szrj }
33838fd1498Szrj else if (!file_data && ltrans_partitions.length ())
33938fd1498Szrj partition = ltrans_partitions[0];
34038fd1498Szrj else
34138fd1498Szrj {
34238fd1498Szrj partition = new_partition ("");
34338fd1498Szrj pmap.put (NULL, partition);
34438fd1498Szrj npartitions++;
34538fd1498Szrj }
34638fd1498Szrj
34738fd1498Szrj add_symbol_to_partition (partition, node);
34838fd1498Szrj }
34938fd1498Szrj
35038fd1498Szrj /* If the cgraph is empty, create one cgraph node set so that there is still
35138fd1498Szrj an output file for any variables that need to be exported in a DSO. */
35238fd1498Szrj if (!npartitions)
35338fd1498Szrj new_partition ("empty");
35438fd1498Szrj
355*58e805e6Szrj /* Order partitions by order of symbols because they are linked into binary
356*58e805e6Szrj that way. */
357*58e805e6Szrj ltrans_partitions.qsort (cmp_partitions_order);
35838fd1498Szrj }
35938fd1498Szrj
36038fd1498Szrj /* Maximal partitioning. Put every new symbol into new partition if possible. */
36138fd1498Szrj
36238fd1498Szrj void
lto_max_map(void)36338fd1498Szrj lto_max_map (void)
36438fd1498Szrj {
36538fd1498Szrj symtab_node *node;
36638fd1498Szrj ltrans_partition partition;
36738fd1498Szrj int npartitions = 0;
36838fd1498Szrj
36938fd1498Szrj FOR_EACH_SYMBOL (node)
37038fd1498Szrj {
37138fd1498Szrj if (node->get_partitioning_class () != SYMBOL_PARTITION
37238fd1498Szrj || symbol_partitioned_p (node))
37338fd1498Szrj continue;
37438fd1498Szrj partition = new_partition (node->asm_name ());
37538fd1498Szrj add_symbol_to_partition (partition, node);
37638fd1498Szrj npartitions++;
37738fd1498Szrj }
37838fd1498Szrj if (!npartitions)
37938fd1498Szrj new_partition ("empty");
38038fd1498Szrj }
38138fd1498Szrj
38238fd1498Szrj /* Helper function for qsort; sort nodes by order. noreorder functions must have
38338fd1498Szrj been removed earlier. */
38438fd1498Szrj static int
node_cmp(const void * pa,const void * pb)38538fd1498Szrj node_cmp (const void *pa, const void *pb)
38638fd1498Szrj {
38738fd1498Szrj const struct cgraph_node *a = *(const struct cgraph_node * const *) pa;
38838fd1498Szrj const struct cgraph_node *b = *(const struct cgraph_node * const *) pb;
38938fd1498Szrj
39038fd1498Szrj /* Profile reorder flag enables function reordering based on first execution
39138fd1498Szrj of a function. All functions with profile are placed in ascending
39238fd1498Szrj order at the beginning. */
39338fd1498Szrj
39438fd1498Szrj if (flag_profile_reorder_functions)
39538fd1498Szrj {
39638fd1498Szrj /* Functions with time profile are sorted in ascending order. */
39738fd1498Szrj if (a->tp_first_run && b->tp_first_run)
39838fd1498Szrj return a->tp_first_run != b->tp_first_run
39938fd1498Szrj ? a->tp_first_run - b->tp_first_run
40038fd1498Szrj : a->order - b->order;
40138fd1498Szrj
40238fd1498Szrj /* Functions with time profile are sorted before the functions
40338fd1498Szrj that do not have the profile. */
40438fd1498Szrj if (a->tp_first_run || b->tp_first_run)
40538fd1498Szrj return b->tp_first_run - a->tp_first_run;
40638fd1498Szrj }
40738fd1498Szrj
40838fd1498Szrj return b->order - a->order;
40938fd1498Szrj }
41038fd1498Szrj
41138fd1498Szrj /* Helper function for qsort; sort nodes by order. */
41238fd1498Szrj static int
varpool_node_cmp(const void * pa,const void * pb)41338fd1498Szrj varpool_node_cmp (const void *pa, const void *pb)
41438fd1498Szrj {
41538fd1498Szrj const symtab_node *a = *static_cast<const symtab_node * const *> (pa);
41638fd1498Szrj const symtab_node *b = *static_cast<const symtab_node * const *> (pb);
41738fd1498Szrj return b->order - a->order;
41838fd1498Szrj }
41938fd1498Szrj
42038fd1498Szrj /* Add all symtab nodes from NEXT_NODE to PARTITION in order. */
42138fd1498Szrj
42238fd1498Szrj static void
add_sorted_nodes(vec<symtab_node * > & next_nodes,ltrans_partition partition)42338fd1498Szrj add_sorted_nodes (vec<symtab_node *> &next_nodes, ltrans_partition partition)
42438fd1498Szrj {
42538fd1498Szrj unsigned i;
42638fd1498Szrj symtab_node *node;
42738fd1498Szrj
42838fd1498Szrj next_nodes.qsort (varpool_node_cmp);
42938fd1498Szrj FOR_EACH_VEC_ELT (next_nodes, i, node)
43038fd1498Szrj if (!symbol_partitioned_p (node))
43138fd1498Szrj add_symbol_to_partition (partition, node);
43238fd1498Szrj }
43338fd1498Szrj
434*58e805e6Szrj /* Return true if we should account reference from N1 to N2 in cost
435*58e805e6Szrj of partition boundary. */
436*58e805e6Szrj
437*58e805e6Szrj bool
account_reference_p(symtab_node * n1,symtab_node * n2)438*58e805e6Szrj account_reference_p (symtab_node *n1, symtab_node *n2)
439*58e805e6Szrj {
440*58e805e6Szrj if (cgraph_node *cnode = dyn_cast <cgraph_node *> (n1))
441*58e805e6Szrj n1 = cnode;
442*58e805e6Szrj /* Do not account references from aliases - they are never split across
443*58e805e6Szrj partitions. */
444*58e805e6Szrj if (n1->alias)
445*58e805e6Szrj return false;
446*58e805e6Szrj /* Do not account recursion - the code below will handle it incorrectly
447*58e805e6Szrj otherwise. Do not account references to external symbols: they will
448*58e805e6Szrj never become local. Finally do not account references to duplicated
449*58e805e6Szrj symbols: they will be always local. */
450*58e805e6Szrj if (n1 == n2
451*58e805e6Szrj || !n2->definition
452*58e805e6Szrj || n2->get_partitioning_class () != SYMBOL_PARTITION)
453*58e805e6Szrj return false;
454*58e805e6Szrj /* If referring node is external symbol do not account it to boundary
455*58e805e6Szrj cost. Those are added into units only to enable possible constant
456*58e805e6Szrj folding and devirtulization.
457*58e805e6Szrj
458*58e805e6Szrj Here we do not know if it will ever be added to some partition
459*58e805e6Szrj (this is decided by compute_ltrans_boundary) and second it is not
460*58e805e6Szrj that likely that constant folding will actually use the reference. */
461*58e805e6Szrj if (contained_in_symbol (n1)
462*58e805e6Szrj ->get_partitioning_class () == SYMBOL_EXTERNAL)
463*58e805e6Szrj return false;
464*58e805e6Szrj return true;
465*58e805e6Szrj }
466*58e805e6Szrj
46738fd1498Szrj
46838fd1498Szrj /* Group cgraph nodes into equally-sized partitions.
46938fd1498Szrj
47038fd1498Szrj The partitioning algorithm is simple: nodes are taken in predefined order.
47138fd1498Szrj The order corresponds to the order we want functions to have in the final
47238fd1498Szrj output. In the future this will be given by function reordering pass, but
47338fd1498Szrj at the moment we use the topological order, which is a good approximation.
47438fd1498Szrj
47538fd1498Szrj The goal is to partition this linear order into intervals (partitions) so
47638fd1498Szrj that all the partitions have approximately the same size and the number of
47738fd1498Szrj callgraph or IPA reference edges crossing boundaries is minimal.
47838fd1498Szrj
47938fd1498Szrj This is a lot faster (O(n) in size of callgraph) than algorithms doing
48038fd1498Szrj priority-based graph clustering that are generally O(n^2) and, since
48138fd1498Szrj WHOPR is designed to make things go well across partitions, it leads
48238fd1498Szrj to good results.
48338fd1498Szrj
48438fd1498Szrj We compute the expected size of a partition as:
48538fd1498Szrj
48638fd1498Szrj max (total_size / lto_partitions, min_partition_size)
48738fd1498Szrj
48838fd1498Szrj We use dynamic expected size of partition so small programs are partitioned
48938fd1498Szrj into enough partitions to allow use of multiple CPUs, while large programs
49038fd1498Szrj are not partitioned too much. Creating too many partitions significantly
49138fd1498Szrj increases the streaming overhead.
49238fd1498Szrj
49338fd1498Szrj In the future, we would like to bound the maximal size of partitions so as
49438fd1498Szrj to prevent the LTRANS stage from consuming too much memory. At the moment,
49538fd1498Szrj however, the WPA stage is the most memory intensive for large benchmarks,
49638fd1498Szrj since too many types and declarations are read into memory.
49738fd1498Szrj
49838fd1498Szrj The function implements a simple greedy algorithm. Nodes are being added
49938fd1498Szrj to the current partition until after 3/4 of the expected partition size is
50038fd1498Szrj reached. Past this threshold, we keep track of boundary size (number of
50138fd1498Szrj edges going to other partitions) and continue adding functions until after
50238fd1498Szrj the current partition has grown to twice the expected partition size. Then
50338fd1498Szrj the process is undone to the point where the minimal ratio of boundary size
50438fd1498Szrj and in-partition calls was reached. */
50538fd1498Szrj
50638fd1498Szrj void
lto_balanced_map(int n_lto_partitions,int max_partition_size)50738fd1498Szrj lto_balanced_map (int n_lto_partitions, int max_partition_size)
50838fd1498Szrj {
50938fd1498Szrj int n_varpool_nodes = 0, varpool_pos = 0, best_varpool_pos = 0;
510*58e805e6Szrj auto_vec <cgraph_node *> order (symtab->cgraph_count);
51138fd1498Szrj auto_vec<cgraph_node *> noreorder;
51238fd1498Szrj auto_vec<varpool_node *> varpool_order;
51338fd1498Szrj struct cgraph_node *node;
514*58e805e6Szrj int64_t original_total_size, total_size = 0;
515*58e805e6Szrj int64_t partition_size;
51638fd1498Szrj ltrans_partition partition;
51738fd1498Szrj int last_visited_node = 0;
51838fd1498Szrj varpool_node *vnode;
519*58e805e6Szrj int64_t cost = 0, internal = 0;
520*58e805e6Szrj unsigned int best_n_nodes = 0, best_i = 0;
521*58e805e6Szrj int64_t best_cost = -1, best_internal = 0, best_size = 0;
52238fd1498Szrj int npartitions;
52338fd1498Szrj int current_order = -1;
52438fd1498Szrj int noreorder_pos = 0;
52538fd1498Szrj
52638fd1498Szrj FOR_EACH_VARIABLE (vnode)
52738fd1498Szrj gcc_assert (!vnode->aux);
52838fd1498Szrj
52938fd1498Szrj FOR_EACH_DEFINED_FUNCTION (node)
53038fd1498Szrj if (node->get_partitioning_class () == SYMBOL_PARTITION)
53138fd1498Szrj {
53238fd1498Szrj if (node->no_reorder)
53338fd1498Szrj noreorder.safe_push (node);
53438fd1498Szrj else
535*58e805e6Szrj order.safe_push (node);
53638fd1498Szrj if (!node->alias)
53738fd1498Szrj total_size += ipa_fn_summaries->get (node)->size;
53838fd1498Szrj }
53938fd1498Szrj
54038fd1498Szrj original_total_size = total_size;
54138fd1498Szrj
54238fd1498Szrj /* Streaming works best when the source units do not cross partition
54338fd1498Szrj boundaries much. This is because importing function from a source
54438fd1498Szrj unit tends to import a lot of global trees defined there. We should
54538fd1498Szrj get better about minimizing the function bounday, but until that
54638fd1498Szrj things works smoother if we order in source order. */
547*58e805e6Szrj order.qsort (node_cmp);
54838fd1498Szrj noreorder.qsort (node_cmp);
54938fd1498Szrj
55038fd1498Szrj if (symtab->dump_file)
55138fd1498Szrj {
552*58e805e6Szrj for (unsigned i = 0; i < order.length (); i++)
55338fd1498Szrj fprintf (symtab->dump_file, "Balanced map symbol order:%s:%u\n",
55438fd1498Szrj order[i]->name (), order[i]->tp_first_run);
555*58e805e6Szrj for (unsigned i = 0; i < noreorder.length (); i++)
55638fd1498Szrj fprintf (symtab->dump_file, "Balanced map symbol no_reorder:%s:%u\n",
55738fd1498Szrj noreorder[i]->name (), noreorder[i]->tp_first_run);
55838fd1498Szrj }
55938fd1498Szrj
56038fd1498Szrj /* Collect all variables that should not be reordered. */
56138fd1498Szrj FOR_EACH_VARIABLE (vnode)
56238fd1498Szrj if (vnode->get_partitioning_class () == SYMBOL_PARTITION
56338fd1498Szrj && vnode->no_reorder)
56438fd1498Szrj varpool_order.safe_push (vnode);
56538fd1498Szrj n_varpool_nodes = varpool_order.length ();
56638fd1498Szrj varpool_order.qsort (varpool_node_cmp);
56738fd1498Szrj
56838fd1498Szrj /* Compute partition size and create the first partition. */
56938fd1498Szrj if (PARAM_VALUE (MIN_PARTITION_SIZE) > max_partition_size)
570*58e805e6Szrj fatal_error (input_location, "min partition size cannot be greater "
571*58e805e6Szrj "than max partition size");
57238fd1498Szrj
57338fd1498Szrj partition_size = total_size / n_lto_partitions;
57438fd1498Szrj if (partition_size < PARAM_VALUE (MIN_PARTITION_SIZE))
57538fd1498Szrj partition_size = PARAM_VALUE (MIN_PARTITION_SIZE);
57638fd1498Szrj npartitions = 1;
57738fd1498Szrj partition = new_partition ("");
57838fd1498Szrj if (symtab->dump_file)
579*58e805e6Szrj fprintf (symtab->dump_file, "Total unit size: %" PRId64
580*58e805e6Szrj ", partition size: %" PRId64 "\n",
58138fd1498Szrj total_size, partition_size);
58238fd1498Szrj
58338fd1498Szrj auto_vec<symtab_node *> next_nodes;
58438fd1498Szrj
585*58e805e6Szrj for (unsigned i = 0; i < order.length (); i++)
58638fd1498Szrj {
58738fd1498Szrj if (symbol_partitioned_p (order[i]))
58838fd1498Szrj continue;
58938fd1498Szrj
59038fd1498Szrj current_order = order[i]->order;
59138fd1498Szrj
59238fd1498Szrj /* Output noreorder and varpool in program order first. */
59338fd1498Szrj next_nodes.truncate (0);
59438fd1498Szrj while (varpool_pos < n_varpool_nodes
59538fd1498Szrj && varpool_order[varpool_pos]->order < current_order)
59638fd1498Szrj next_nodes.safe_push (varpool_order[varpool_pos++]);
59738fd1498Szrj while (noreorder_pos < (int)noreorder.length ()
59838fd1498Szrj && noreorder[noreorder_pos]->order < current_order)
59938fd1498Szrj next_nodes.safe_push (noreorder[noreorder_pos++]);
60038fd1498Szrj add_sorted_nodes (next_nodes, partition);
60138fd1498Szrj
60238fd1498Szrj if (!symbol_partitioned_p (order[i]))
60338fd1498Szrj add_symbol_to_partition (partition, order[i]);
60438fd1498Szrj
60538fd1498Szrj
60638fd1498Szrj /* Once we added a new node to the partition, we also want to add
60738fd1498Szrj all referenced variables unless they was already added into some
60838fd1498Szrj earlier partition.
60938fd1498Szrj add_symbol_to_partition adds possibly multiple nodes and
61038fd1498Szrj variables that are needed to satisfy needs of ORDER[i].
61138fd1498Szrj We remember last visited cgraph and varpool node from last iteration
61238fd1498Szrj of outer loop that allows us to process every new addition.
61338fd1498Szrj
61438fd1498Szrj At the same time we compute size of the boundary into COST. Every
61538fd1498Szrj callgraph or IPA reference edge leaving the partition contributes into
61638fd1498Szrj COST. Every edge inside partition was earlier computed as one leaving
61738fd1498Szrj it and thus we need to subtract it from COST. */
61838fd1498Szrj while (last_visited_node < lto_symtab_encoder_size (partition->encoder))
61938fd1498Szrj {
62038fd1498Szrj int j;
62138fd1498Szrj struct ipa_ref *ref = NULL;
62238fd1498Szrj symtab_node *snode = lto_symtab_encoder_deref (partition->encoder,
62338fd1498Szrj last_visited_node);
62438fd1498Szrj
62538fd1498Szrj if (cgraph_node *node = dyn_cast <cgraph_node *> (snode))
62638fd1498Szrj {
62738fd1498Szrj struct cgraph_edge *edge;
62838fd1498Szrj
62938fd1498Szrj
63038fd1498Szrj last_visited_node++;
63138fd1498Szrj
63238fd1498Szrj gcc_assert (node->definition || node->weakref);
63338fd1498Szrj
63438fd1498Szrj /* Compute boundary cost of callgraph edges. */
63538fd1498Szrj for (edge = node->callees; edge; edge = edge->next_callee)
636*58e805e6Szrj /* Inline edges will always end up local. */
637*58e805e6Szrj if (edge->inline_failed
638*58e805e6Szrj && account_reference_p (node, edge->callee))
63938fd1498Szrj {
64038fd1498Szrj int edge_cost = edge->frequency ();
64138fd1498Szrj int index;
64238fd1498Szrj
64338fd1498Szrj if (!edge_cost)
64438fd1498Szrj edge_cost = 1;
64538fd1498Szrj gcc_assert (edge_cost > 0);
64638fd1498Szrj index = lto_symtab_encoder_lookup (partition->encoder,
64738fd1498Szrj edge->callee);
64838fd1498Szrj if (index != LCC_NOT_FOUND
64938fd1498Szrj && index < last_visited_node - 1)
65038fd1498Szrj cost -= edge_cost, internal += edge_cost;
65138fd1498Szrj else
65238fd1498Szrj cost += edge_cost;
65338fd1498Szrj }
65438fd1498Szrj for (edge = node->callers; edge; edge = edge->next_caller)
655*58e805e6Szrj if (edge->inline_failed
656*58e805e6Szrj && account_reference_p (edge->caller, node))
65738fd1498Szrj {
65838fd1498Szrj int edge_cost = edge->frequency ();
65938fd1498Szrj int index;
66038fd1498Szrj
66138fd1498Szrj gcc_assert (edge->caller->definition);
66238fd1498Szrj if (!edge_cost)
66338fd1498Szrj edge_cost = 1;
66438fd1498Szrj gcc_assert (edge_cost > 0);
66538fd1498Szrj index = lto_symtab_encoder_lookup (partition->encoder,
66638fd1498Szrj edge->caller);
66738fd1498Szrj if (index != LCC_NOT_FOUND
66838fd1498Szrj && index < last_visited_node - 1)
669*58e805e6Szrj cost -= edge_cost, internal += edge_cost;
67038fd1498Szrj else
67138fd1498Szrj cost += edge_cost;
67238fd1498Szrj }
67338fd1498Szrj }
67438fd1498Szrj else
67538fd1498Szrj last_visited_node++;
67638fd1498Szrj
67738fd1498Szrj /* Compute boundary cost of IPA REF edges and at the same time look into
67838fd1498Szrj variables referenced from current partition and try to add them. */
679*58e805e6Szrj for (j = 0; snode->iterate_reference (j, ref); j++)
680*58e805e6Szrj if (!account_reference_p (snode, ref->referred))
681*58e805e6Szrj ;
682*58e805e6Szrj else if (is_a <varpool_node *> (ref->referred))
68338fd1498Szrj {
68438fd1498Szrj int index;
68538fd1498Szrj
68638fd1498Szrj vnode = dyn_cast <varpool_node *> (ref->referred);
68738fd1498Szrj if (!symbol_partitioned_p (vnode)
68838fd1498Szrj && !vnode->no_reorder
68938fd1498Szrj && vnode->get_partitioning_class () == SYMBOL_PARTITION)
69038fd1498Szrj add_symbol_to_partition (partition, vnode);
69138fd1498Szrj index = lto_symtab_encoder_lookup (partition->encoder,
69238fd1498Szrj vnode);
69338fd1498Szrj if (index != LCC_NOT_FOUND
69438fd1498Szrj && index < last_visited_node - 1)
69538fd1498Szrj cost--, internal++;
69638fd1498Szrj else
69738fd1498Szrj cost++;
69838fd1498Szrj }
69938fd1498Szrj else
70038fd1498Szrj {
70138fd1498Szrj int index;
70238fd1498Szrj
70338fd1498Szrj node = dyn_cast <cgraph_node *> (ref->referred);
70438fd1498Szrj index = lto_symtab_encoder_lookup (partition->encoder,
70538fd1498Szrj node);
70638fd1498Szrj if (index != LCC_NOT_FOUND
70738fd1498Szrj && index < last_visited_node - 1)
70838fd1498Szrj cost--, internal++;
70938fd1498Szrj else
71038fd1498Szrj cost++;
71138fd1498Szrj }
712*58e805e6Szrj for (j = 0; snode->iterate_referring (j, ref); j++)
713*58e805e6Szrj if (!account_reference_p (ref->referring, snode))
714*58e805e6Szrj ;
715*58e805e6Szrj else if (is_a <varpool_node *> (ref->referring))
71638fd1498Szrj {
71738fd1498Szrj int index;
71838fd1498Szrj
71938fd1498Szrj vnode = dyn_cast <varpool_node *> (ref->referring);
72038fd1498Szrj gcc_assert (vnode->definition);
72138fd1498Szrj /* It is better to couple variables with their users,
72238fd1498Szrj because it allows them to be removed. Coupling
72338fd1498Szrj with objects they refer to only helps to reduce
72438fd1498Szrj number of symbols promoted to hidden. */
72538fd1498Szrj if (!symbol_partitioned_p (vnode)
72638fd1498Szrj && !vnode->no_reorder
72738fd1498Szrj && !vnode->can_remove_if_no_refs_p ()
72838fd1498Szrj && vnode->get_partitioning_class () == SYMBOL_PARTITION)
72938fd1498Szrj add_symbol_to_partition (partition, vnode);
73038fd1498Szrj index = lto_symtab_encoder_lookup (partition->encoder,
73138fd1498Szrj vnode);
73238fd1498Szrj if (index != LCC_NOT_FOUND
73338fd1498Szrj && index < last_visited_node - 1)
734*58e805e6Szrj cost--, internal++;
73538fd1498Szrj else
73638fd1498Szrj cost++;
73738fd1498Szrj }
73838fd1498Szrj else
73938fd1498Szrj {
74038fd1498Szrj int index;
74138fd1498Szrj
74238fd1498Szrj node = dyn_cast <cgraph_node *> (ref->referring);
74338fd1498Szrj gcc_assert (node->definition);
74438fd1498Szrj index = lto_symtab_encoder_lookup (partition->encoder,
74538fd1498Szrj node);
74638fd1498Szrj if (index != LCC_NOT_FOUND
74738fd1498Szrj && index < last_visited_node - 1)
748*58e805e6Szrj cost--, internal++;
74938fd1498Szrj else
75038fd1498Szrj cost++;
75138fd1498Szrj }
75238fd1498Szrj }
75338fd1498Szrj
754*58e805e6Szrj gcc_assert (cost >= 0 && internal >= 0);
755*58e805e6Szrj
756*58e805e6Szrj /* If the partition is large enough, start looking for smallest boundary cost.
757*58e805e6Szrj If partition still seems too small (less than 7/8 of target weight) accept
758*58e805e6Szrj any cost. If partition has right size, optimize for highest internal/cost.
759*58e805e6Szrj Later we stop building partition if its size is 9/8 of the target wight. */
760*58e805e6Szrj if (partition->insns < partition_size * 7 / 8
761*58e805e6Szrj || best_cost == -1
762*58e805e6Szrj || (!cost
763*58e805e6Szrj || ((sreal)best_internal * (sreal) cost
764*58e805e6Szrj < ((sreal) internal * (sreal)best_cost))))
76538fd1498Szrj {
76638fd1498Szrj best_cost = cost;
76738fd1498Szrj best_internal = internal;
768*58e805e6Szrj best_size = partition->insns;
76938fd1498Szrj best_i = i;
77038fd1498Szrj best_n_nodes = lto_symtab_encoder_size (partition->encoder);
77138fd1498Szrj best_varpool_pos = varpool_pos;
77238fd1498Szrj }
77338fd1498Szrj if (symtab->dump_file)
774*58e805e6Szrj fprintf (symtab->dump_file, "Step %i: added %s/%i, size %i, "
775*58e805e6Szrj "cost %" PRId64 "/%" PRId64 " "
776*58e805e6Szrj "best %" PRId64 "/%" PRId64", step %i\n", i,
77738fd1498Szrj order[i]->name (), order[i]->order,
77838fd1498Szrj partition->insns, cost, internal,
77938fd1498Szrj best_cost, best_internal, best_i);
78038fd1498Szrj /* Partition is too large, unwind into step when best cost was reached and
78138fd1498Szrj start new partition. */
782*58e805e6Szrj if (partition->insns > 9 * partition_size / 8
78338fd1498Szrj || partition->insns > max_partition_size)
78438fd1498Szrj {
78538fd1498Szrj if (best_i != i)
78638fd1498Szrj {
78738fd1498Szrj if (symtab->dump_file)
78838fd1498Szrj fprintf (symtab->dump_file, "Unwinding %i insertions to step %i\n",
78938fd1498Szrj i - best_i, best_i);
79038fd1498Szrj undo_partition (partition, best_n_nodes);
79138fd1498Szrj varpool_pos = best_varpool_pos;
79238fd1498Szrj }
793*58e805e6Szrj gcc_assert (best_size == partition->insns);
79438fd1498Szrj i = best_i;
795*58e805e6Szrj if (symtab->dump_file)
796*58e805e6Szrj fprintf (symtab->dump_file,
797*58e805e6Szrj "Partition insns: %i (want %" PRId64 ")\n",
798*58e805e6Szrj partition->insns, partition_size);
79938fd1498Szrj /* When we are finished, avoid creating empty partition. */
800*58e805e6Szrj while (i < order.length () - 1 && symbol_partitioned_p (order[i + 1]))
80138fd1498Szrj i++;
802*58e805e6Szrj if (i == order.length () - 1)
80338fd1498Szrj break;
804*58e805e6Szrj total_size -= partition->insns;
80538fd1498Szrj partition = new_partition ("");
80638fd1498Szrj last_visited_node = 0;
80738fd1498Szrj cost = 0;
80838fd1498Szrj
80938fd1498Szrj if (symtab->dump_file)
81038fd1498Szrj fprintf (symtab->dump_file, "New partition\n");
81138fd1498Szrj best_n_nodes = 0;
812*58e805e6Szrj best_cost = -1;
81338fd1498Szrj
81438fd1498Szrj /* Since the size of partitions is just approximate, update the size after
81538fd1498Szrj we finished current one. */
81638fd1498Szrj if (npartitions < n_lto_partitions)
81738fd1498Szrj partition_size = total_size / (n_lto_partitions - npartitions);
81838fd1498Szrj else
81938fd1498Szrj /* Watch for overflow. */
82038fd1498Szrj partition_size = INT_MAX / 16;
82138fd1498Szrj
822*58e805e6Szrj if (symtab->dump_file)
823*58e805e6Szrj fprintf (symtab->dump_file,
824*58e805e6Szrj "Total size: %" PRId64 " partition_size: %" PRId64 "\n",
825*58e805e6Szrj total_size, partition_size);
82638fd1498Szrj if (partition_size < PARAM_VALUE (MIN_PARTITION_SIZE))
82738fd1498Szrj partition_size = PARAM_VALUE (MIN_PARTITION_SIZE);
82838fd1498Szrj npartitions ++;
82938fd1498Szrj }
83038fd1498Szrj }
83138fd1498Szrj
83238fd1498Szrj next_nodes.truncate (0);
83338fd1498Szrj
83438fd1498Szrj /* Varables that are not reachable from the code go into last partition. */
83538fd1498Szrj FOR_EACH_VARIABLE (vnode)
83638fd1498Szrj if (vnode->get_partitioning_class () == SYMBOL_PARTITION
83738fd1498Szrj && !symbol_partitioned_p (vnode))
83838fd1498Szrj next_nodes.safe_push (vnode);
83938fd1498Szrj
84038fd1498Szrj /* Output remaining ordered symbols. */
84138fd1498Szrj while (varpool_pos < n_varpool_nodes)
84238fd1498Szrj next_nodes.safe_push (varpool_order[varpool_pos++]);
84338fd1498Szrj while (noreorder_pos < (int)noreorder.length ())
84438fd1498Szrj next_nodes.safe_push (noreorder[noreorder_pos++]);
845*58e805e6Szrj /* For one partition the cost of boundary should be 0 unless we added final
846*58e805e6Szrj symbols here (these are not accounted) or we have accounting bug. */
847*58e805e6Szrj gcc_assert (next_nodes.length () || npartitions != 1 || !best_cost || best_cost == -1);
84838fd1498Szrj add_sorted_nodes (next_nodes, partition);
84938fd1498Szrj
85038fd1498Szrj if (symtab->dump_file)
85138fd1498Szrj {
85238fd1498Szrj fprintf (symtab->dump_file, "\nPartition sizes:\n");
85338fd1498Szrj unsigned partitions = ltrans_partitions.length ();
85438fd1498Szrj
85538fd1498Szrj for (unsigned i = 0; i < partitions ; i++)
85638fd1498Szrj {
85738fd1498Szrj ltrans_partition p = ltrans_partitions[i];
85838fd1498Szrj fprintf (symtab->dump_file, "partition %d contains %d (%2.2f%%)"
85938fd1498Szrj " symbols and %d (%2.2f%%) insns\n", i, p->symbols,
860*58e805e6Szrj 100.0 * p->symbols / order.length (), p->insns,
86138fd1498Szrj 100.0 * p->insns / original_total_size);
86238fd1498Szrj }
86338fd1498Szrj
86438fd1498Szrj fprintf (symtab->dump_file, "\n");
86538fd1498Szrj }
86638fd1498Szrj }
86738fd1498Szrj
86838fd1498Szrj /* Return true if we must not change the name of the NODE. The name as
86938fd1498Szrj extracted from the corresponding decl should be passed in NAME. */
87038fd1498Szrj
87138fd1498Szrj static bool
must_not_rename(symtab_node * node,const char * name)87238fd1498Szrj must_not_rename (symtab_node *node, const char *name)
87338fd1498Szrj {
87438fd1498Szrj /* Our renaming machinery do not handle more than one change of assembler name.
87538fd1498Szrj We should not need more than one anyway. */
87638fd1498Szrj if (node->lto_file_data
87738fd1498Szrj && lto_get_decl_name_mapping (node->lto_file_data, name) != name)
87838fd1498Szrj {
87938fd1498Szrj if (symtab->dump_file)
88038fd1498Szrj fprintf (symtab->dump_file,
88138fd1498Szrj "Not privatizing symbol name: %s. It privatized already.\n",
88238fd1498Szrj name);
88338fd1498Szrj return true;
88438fd1498Szrj }
88538fd1498Szrj /* Avoid mangling of already mangled clones.
88638fd1498Szrj ??? should have a flag whether a symbol has a 'private' name already,
88738fd1498Szrj since we produce some symbols like that i.e. for global constructors
88838fd1498Szrj that are not really clones. */
88938fd1498Szrj if (node->unique_name)
89038fd1498Szrj {
89138fd1498Szrj if (symtab->dump_file)
89238fd1498Szrj fprintf (symtab->dump_file,
89338fd1498Szrj "Not privatizing symbol name: %s. Has unique name.\n",
89438fd1498Szrj name);
89538fd1498Szrj return true;
89638fd1498Szrj }
89738fd1498Szrj return false;
89838fd1498Szrj }
89938fd1498Szrj
90038fd1498Szrj /* If we are an offload compiler, we may have to rewrite symbols to be
90138fd1498Szrj valid on this target. Return either PTR or a modified version of it. */
90238fd1498Szrj
90338fd1498Szrj static const char *
maybe_rewrite_identifier(const char * ptr)90438fd1498Szrj maybe_rewrite_identifier (const char *ptr)
90538fd1498Szrj {
90638fd1498Szrj #if defined ACCEL_COMPILER && (defined NO_DOT_IN_LABEL || defined NO_DOLLAR_IN_LABEL)
90738fd1498Szrj #ifndef NO_DOT_IN_LABEL
90838fd1498Szrj char valid = '.';
90938fd1498Szrj const char reject[] = "$";
91038fd1498Szrj #elif !defined NO_DOLLAR_IN_LABEL
91138fd1498Szrj char valid = '$';
91238fd1498Szrj const char reject[] = ".";
91338fd1498Szrj #else
91438fd1498Szrj char valid = '_';
91538fd1498Szrj const char reject[] = ".$";
91638fd1498Szrj #endif
91738fd1498Szrj
91838fd1498Szrj char *copy = NULL;
91938fd1498Szrj const char *match = ptr;
92038fd1498Szrj for (;;)
92138fd1498Szrj {
92238fd1498Szrj size_t off = strcspn (match, reject);
92338fd1498Szrj if (match[off] == '\0')
92438fd1498Szrj break;
92538fd1498Szrj if (copy == NULL)
92638fd1498Szrj {
92738fd1498Szrj copy = xstrdup (ptr);
92838fd1498Szrj match = copy;
92938fd1498Szrj }
93038fd1498Szrj copy[off] = valid;
93138fd1498Szrj }
93238fd1498Szrj return match;
93338fd1498Szrj #else
93438fd1498Szrj return ptr;
93538fd1498Szrj #endif
93638fd1498Szrj }
93738fd1498Szrj
93838fd1498Szrj /* Ensure that the symbol in NODE is valid for the target, and if not,
93938fd1498Szrj rewrite it. */
94038fd1498Szrj
94138fd1498Szrj static void
validize_symbol_for_target(symtab_node * node)94238fd1498Szrj validize_symbol_for_target (symtab_node *node)
94338fd1498Szrj {
94438fd1498Szrj tree decl = node->decl;
94538fd1498Szrj const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
94638fd1498Szrj
94738fd1498Szrj if (must_not_rename (node, name))
94838fd1498Szrj return;
94938fd1498Szrj
95038fd1498Szrj const char *name2 = maybe_rewrite_identifier (name);
95138fd1498Szrj if (name2 != name)
95238fd1498Szrj {
95338fd1498Szrj symtab->change_decl_assembler_name (decl, get_identifier (name2));
95438fd1498Szrj if (node->lto_file_data)
95538fd1498Szrj lto_record_renamed_decl (node->lto_file_data, name,
95638fd1498Szrj IDENTIFIER_POINTER
95738fd1498Szrj (DECL_ASSEMBLER_NAME (decl)));
95838fd1498Szrj }
95938fd1498Szrj }
96038fd1498Szrj
96138fd1498Szrj /* Helper for privatize_symbol_name. Mangle NODE symbol name
96238fd1498Szrj represented by DECL. */
96338fd1498Szrj
96438fd1498Szrj static bool
privatize_symbol_name_1(symtab_node * node,tree decl)96538fd1498Szrj privatize_symbol_name_1 (symtab_node *node, tree decl)
96638fd1498Szrj {
96738fd1498Szrj const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
96838fd1498Szrj
96938fd1498Szrj if (must_not_rename (node, name))
97038fd1498Szrj return false;
97138fd1498Szrj
97238fd1498Szrj name = maybe_rewrite_identifier (name);
97338fd1498Szrj symtab->change_decl_assembler_name (decl,
97438fd1498Szrj clone_function_name_1 (name,
97538fd1498Szrj "lto_priv"));
97638fd1498Szrj
97738fd1498Szrj if (node->lto_file_data)
97838fd1498Szrj lto_record_renamed_decl (node->lto_file_data, name,
97938fd1498Szrj IDENTIFIER_POINTER
98038fd1498Szrj (DECL_ASSEMBLER_NAME (decl)));
98138fd1498Szrj
98238fd1498Szrj if (symtab->dump_file)
98338fd1498Szrj fprintf (symtab->dump_file,
98438fd1498Szrj "Privatizing symbol name: %s -> %s\n",
98538fd1498Szrj name, IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl)));
98638fd1498Szrj
98738fd1498Szrj return true;
98838fd1498Szrj }
98938fd1498Szrj
99038fd1498Szrj /* Mangle NODE symbol name into a local name.
99138fd1498Szrj This is necessary to do
99238fd1498Szrj 1) if two or more static vars of same assembler name
99338fd1498Szrj are merged into single ltrans unit.
99438fd1498Szrj 2) if previously static var was promoted hidden to avoid possible conflict
99538fd1498Szrj with symbols defined out of the LTO world. */
99638fd1498Szrj
99738fd1498Szrj static bool
privatize_symbol_name(symtab_node * node)99838fd1498Szrj privatize_symbol_name (symtab_node *node)
99938fd1498Szrj {
100038fd1498Szrj if (!privatize_symbol_name_1 (node, node->decl))
100138fd1498Szrj return false;
100238fd1498Szrj
100338fd1498Szrj /* We could change name which is a target of transparent alias
100438fd1498Szrj chain of instrumented function name. Fix alias chain if so .*/
100538fd1498Szrj if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
100638fd1498Szrj {
100738fd1498Szrj tree iname = NULL_TREE;
100838fd1498Szrj if (cnode->instrumentation_clone)
100938fd1498Szrj {
101038fd1498Szrj /* If we want to privatize instrumentation clone
101138fd1498Szrj then we also need to privatize original function. */
101238fd1498Szrj if (cnode->instrumented_version)
101338fd1498Szrj privatize_symbol_name (cnode->instrumented_version);
101438fd1498Szrj else
101538fd1498Szrj privatize_symbol_name_1 (cnode, cnode->orig_decl);
101638fd1498Szrj iname = DECL_ASSEMBLER_NAME (cnode->decl);
101738fd1498Szrj TREE_CHAIN (iname) = DECL_ASSEMBLER_NAME (cnode->orig_decl);
101838fd1498Szrj }
101938fd1498Szrj else if (cnode->instrumented_version
102038fd1498Szrj && cnode->instrumented_version->orig_decl == cnode->decl)
102138fd1498Szrj {
102238fd1498Szrj iname = DECL_ASSEMBLER_NAME (cnode->instrumented_version->decl);
102338fd1498Szrj TREE_CHAIN (iname) = DECL_ASSEMBLER_NAME (cnode->decl);
102438fd1498Szrj }
102538fd1498Szrj }
102638fd1498Szrj
102738fd1498Szrj return true;
102838fd1498Szrj }
102938fd1498Szrj
103038fd1498Szrj /* Promote variable VNODE to be static. */
103138fd1498Szrj
103238fd1498Szrj static void
promote_symbol(symtab_node * node)103338fd1498Szrj promote_symbol (symtab_node *node)
103438fd1498Szrj {
103538fd1498Szrj /* We already promoted ... */
103638fd1498Szrj if (DECL_VISIBILITY (node->decl) == VISIBILITY_HIDDEN
103738fd1498Szrj && DECL_VISIBILITY_SPECIFIED (node->decl)
103838fd1498Szrj && TREE_PUBLIC (node->decl))
103938fd1498Szrj {
104038fd1498Szrj validize_symbol_for_target (node);
104138fd1498Szrj return;
104238fd1498Szrj }
104338fd1498Szrj
104438fd1498Szrj gcc_checking_assert (!TREE_PUBLIC (node->decl)
104538fd1498Szrj && !DECL_EXTERNAL (node->decl));
104638fd1498Szrj /* Be sure that newly public symbol does not conflict with anything already
104738fd1498Szrj defined by the non-LTO part. */
104838fd1498Szrj privatize_symbol_name (node);
104938fd1498Szrj TREE_PUBLIC (node->decl) = 1;
105038fd1498Szrj DECL_VISIBILITY (node->decl) = VISIBILITY_HIDDEN;
105138fd1498Szrj DECL_VISIBILITY_SPECIFIED (node->decl) = true;
105238fd1498Szrj if (symtab->dump_file)
105338fd1498Szrj fprintf (symtab->dump_file,
105438fd1498Szrj "Promoting as hidden: %s (%s)\n", node->name (),
105538fd1498Szrj IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
105638fd1498Szrj
105738fd1498Szrj /* Promoting a symbol also promotes all transparent aliases with exception
105838fd1498Szrj of weakref where the visibility flags are always wrong and set to
105938fd1498Szrj !PUBLIC. */
106038fd1498Szrj ipa_ref *ref;
106138fd1498Szrj for (unsigned i = 0; node->iterate_direct_aliases (i, ref); i++)
106238fd1498Szrj {
106338fd1498Szrj struct symtab_node *alias = ref->referring;
106438fd1498Szrj if (alias->transparent_alias && !alias->weakref)
106538fd1498Szrj {
106638fd1498Szrj TREE_PUBLIC (alias->decl) = 1;
106738fd1498Szrj DECL_VISIBILITY (alias->decl) = VISIBILITY_HIDDEN;
106838fd1498Szrj DECL_VISIBILITY_SPECIFIED (alias->decl) = true;
106938fd1498Szrj if (symtab->dump_file)
107038fd1498Szrj fprintf (symtab->dump_file,
107138fd1498Szrj "Promoting alias as hidden: %s\n",
107238fd1498Szrj IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
107338fd1498Szrj }
107438fd1498Szrj gcc_assert (!alias->weakref || TREE_PUBLIC (alias->decl));
107538fd1498Szrj }
107638fd1498Szrj }
107738fd1498Szrj
107838fd1498Szrj /* Return true if NODE needs named section even if it won't land in
107938fd1498Szrj the partition symbol table.
108038fd1498Szrj
108138fd1498Szrj FIXME: we should really not use named sections for inline clones
108238fd1498Szrj and master clones. */
108338fd1498Szrj
108438fd1498Szrj static bool
may_need_named_section_p(lto_symtab_encoder_t encoder,symtab_node * node)108538fd1498Szrj may_need_named_section_p (lto_symtab_encoder_t encoder, symtab_node *node)
108638fd1498Szrj {
108738fd1498Szrj struct cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
108838fd1498Szrj if (!cnode)
108938fd1498Szrj return false;
109038fd1498Szrj if (node->real_symbol_p ())
109138fd1498Szrj return false;
109238fd1498Szrj return (!encoder
109338fd1498Szrj || (lto_symtab_encoder_lookup (encoder, node) != LCC_NOT_FOUND
109438fd1498Szrj && lto_symtab_encoder_encode_body_p (encoder,
109538fd1498Szrj cnode)));
109638fd1498Szrj }
109738fd1498Szrj
109838fd1498Szrj /* If NODE represents a static variable. See if there are other variables
109938fd1498Szrj of the same name in partition ENCODER (or in whole compilation unit if
110038fd1498Szrj ENCODER is NULL) and if so, mangle the statics. Always mangle all
110138fd1498Szrj conflicting statics, so we reduce changes of silently miscompiling
110238fd1498Szrj asm statements referring to them by symbol name. */
110338fd1498Szrj
110438fd1498Szrj static void
rename_statics(lto_symtab_encoder_t encoder,symtab_node * node)110538fd1498Szrj rename_statics (lto_symtab_encoder_t encoder, symtab_node *node)
110638fd1498Szrj {
110738fd1498Szrj tree decl = node->decl;
110838fd1498Szrj symtab_node *s;
110938fd1498Szrj tree name = DECL_ASSEMBLER_NAME (decl);
111038fd1498Szrj
111138fd1498Szrj /* See if this is static symbol. */
111238fd1498Szrj if (((node->externally_visible && !node->weakref)
111338fd1498Szrj /* FIXME: externally_visible is somewhat illogically not set for
111438fd1498Szrj external symbols (i.e. those not defined). Remove this test
111538fd1498Szrj once this is fixed. */
111638fd1498Szrj || DECL_EXTERNAL (node->decl)
111738fd1498Szrj || !node->real_symbol_p ())
111838fd1498Szrj && !may_need_named_section_p (encoder, node))
111938fd1498Szrj return;
112038fd1498Szrj
112138fd1498Szrj /* Now walk symbols sharing the same name and see if there are any conflicts.
112238fd1498Szrj (all types of symbols counts here, since we can not have static of the
112338fd1498Szrj same name as external or public symbol.) */
112438fd1498Szrj for (s = symtab_node::get_for_asmname (name);
112538fd1498Szrj s; s = s->next_sharing_asm_name)
112638fd1498Szrj if ((s->real_symbol_p () || may_need_named_section_p (encoder, s))
112738fd1498Szrj && s->decl != node->decl
112838fd1498Szrj && (!encoder
112938fd1498Szrj || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND))
113038fd1498Szrj break;
113138fd1498Szrj
113238fd1498Szrj /* OK, no confict, so we have nothing to do. */
113338fd1498Szrj if (!s)
113438fd1498Szrj return;
113538fd1498Szrj
113638fd1498Szrj if (symtab->dump_file)
113738fd1498Szrj fprintf (symtab->dump_file,
113838fd1498Szrj "Renaming statics with asm name: %s\n", node->name ());
113938fd1498Szrj
114038fd1498Szrj /* Assign every symbol in the set that shares the same ASM name an unique
114138fd1498Szrj mangled name. */
114238fd1498Szrj for (s = symtab_node::get_for_asmname (name); s;)
114338fd1498Szrj if ((!s->externally_visible || s->weakref)
114438fd1498Szrj /* Transparent aliases having same name as target are renamed at a
114538fd1498Szrj time their target gets new name. Transparent aliases that use
114638fd1498Szrj separate assembler name require the name to be unique. */
114738fd1498Szrj && (!s->transparent_alias || !s->definition || s->weakref
114838fd1498Szrj || !symbol_table::assembler_names_equal_p
114938fd1498Szrj (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (s->decl)),
115038fd1498Szrj IDENTIFIER_POINTER
115138fd1498Szrj (DECL_ASSEMBLER_NAME (s->get_alias_target()->decl))))
115238fd1498Szrj && ((s->real_symbol_p ()
115338fd1498Szrj && !DECL_EXTERNAL (s->decl)
115438fd1498Szrj && !TREE_PUBLIC (s->decl))
115538fd1498Szrj || may_need_named_section_p (encoder, s))
115638fd1498Szrj && (!encoder
115738fd1498Szrj || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND))
115838fd1498Szrj {
115938fd1498Szrj if (privatize_symbol_name (s))
116038fd1498Szrj /* Re-start from beginning since we do not know how many
116138fd1498Szrj symbols changed a name. */
116238fd1498Szrj s = symtab_node::get_for_asmname (name);
116338fd1498Szrj else s = s->next_sharing_asm_name;
116438fd1498Szrj }
116538fd1498Szrj else s = s->next_sharing_asm_name;
116638fd1498Szrj }
116738fd1498Szrj
116838fd1498Szrj /* Find out all static decls that need to be promoted to global because
116938fd1498Szrj of cross file sharing. This function must be run in the WPA mode after
117038fd1498Szrj all inlinees are added. */
117138fd1498Szrj
117238fd1498Szrj void
lto_promote_cross_file_statics(void)117338fd1498Szrj lto_promote_cross_file_statics (void)
117438fd1498Szrj {
117538fd1498Szrj unsigned i, n_sets;
117638fd1498Szrj
117738fd1498Szrj gcc_assert (flag_wpa);
117838fd1498Szrj
117938fd1498Szrj lto_stream_offload_p = false;
118038fd1498Szrj select_what_to_stream ();
118138fd1498Szrj
118238fd1498Szrj /* First compute boundaries. */
118338fd1498Szrj n_sets = ltrans_partitions.length ();
118438fd1498Szrj for (i = 0; i < n_sets; i++)
118538fd1498Szrj {
118638fd1498Szrj ltrans_partition part
118738fd1498Szrj = ltrans_partitions[i];
118838fd1498Szrj part->encoder = compute_ltrans_boundary (part->encoder);
118938fd1498Szrj }
119038fd1498Szrj
119138fd1498Szrj /* Look at boundaries and promote symbols as needed. */
119238fd1498Szrj for (i = 0; i < n_sets; i++)
119338fd1498Szrj {
119438fd1498Szrj lto_symtab_encoder_iterator lsei;
119538fd1498Szrj lto_symtab_encoder_t encoder = ltrans_partitions[i]->encoder;
119638fd1498Szrj
119738fd1498Szrj for (lsei = lsei_start (encoder); !lsei_end_p (lsei);
119838fd1498Szrj lsei_next (&lsei))
119938fd1498Szrj {
120038fd1498Szrj symtab_node *node = lsei_node (lsei);
120138fd1498Szrj
120238fd1498Szrj /* If symbol is static, rename it if its assembler name
120338fd1498Szrj clashes with anything else in this unit. */
120438fd1498Szrj rename_statics (encoder, node);
120538fd1498Szrj
120638fd1498Szrj /* No need to promote if symbol already is externally visible ... */
120738fd1498Szrj if (node->externally_visible
120838fd1498Szrj /* ... or if it is part of current partition ... */
120938fd1498Szrj || lto_symtab_encoder_in_partition_p (encoder, node)
121038fd1498Szrj /* ... or if we do not partition it. This mean that it will
121138fd1498Szrj appear in every partition referencing it. */
121238fd1498Szrj || node->get_partitioning_class () != SYMBOL_PARTITION)
121338fd1498Szrj {
121438fd1498Szrj validize_symbol_for_target (node);
121538fd1498Szrj continue;
121638fd1498Szrj }
121738fd1498Szrj
121838fd1498Szrj promote_symbol (node);
121938fd1498Szrj }
122038fd1498Szrj }
122138fd1498Szrj }
122238fd1498Szrj
122338fd1498Szrj /* Rename statics in the whole unit in the case that
122438fd1498Szrj we do -flto-partition=none. */
122538fd1498Szrj
122638fd1498Szrj void
lto_promote_statics_nonwpa(void)122738fd1498Szrj lto_promote_statics_nonwpa (void)
122838fd1498Szrj {
122938fd1498Szrj symtab_node *node;
123038fd1498Szrj FOR_EACH_SYMBOL (node)
123138fd1498Szrj {
123238fd1498Szrj rename_statics (NULL, node);
123338fd1498Szrj validize_symbol_for_target (node);
123438fd1498Szrj }
123538fd1498Szrj }
1236