1 /* LTO partitioning logic routines.
2 Copyright (C) 2009-2020 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "target.h"
24 #include "function.h"
25 #include "basic-block.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "alloc-pool.h"
29 #include "stringpool.h"
30 #include "cgraph.h"
31 #include "lto-streamer.h"
32 #include "symbol-summary.h"
33 #include "tree-vrp.h"
34 #include "ipa-prop.h"
35 #include "ipa-fnsummary.h"
36 #include "lto-partition.h"
37 #include "sreal.h"
38
39 vec<ltrans_partition> ltrans_partitions;
40
41 static void add_symbol_to_partition (ltrans_partition part, symtab_node *node);
42
43
44 /* Helper for qsort; compare partitions and return one with smaller order. */
45
46 static int
cmp_partitions_order(const void * a,const void * b)47 cmp_partitions_order (const void *a, const void *b)
48 {
49 const struct ltrans_partition_def *pa
50 = *(struct ltrans_partition_def *const *)a;
51 const struct ltrans_partition_def *pb
52 = *(struct ltrans_partition_def *const *)b;
53 int ordera = -1, orderb = -1;
54
55 if (lto_symtab_encoder_size (pa->encoder))
56 ordera = lto_symtab_encoder_deref (pa->encoder, 0)->order;
57 if (lto_symtab_encoder_size (pb->encoder))
58 orderb = lto_symtab_encoder_deref (pb->encoder, 0)->order;
59 return orderb - ordera;
60 }
61
62 /* Create new partition with name NAME. */
63
64 static ltrans_partition
new_partition(const char * name)65 new_partition (const char *name)
66 {
67 ltrans_partition part = XCNEW (struct ltrans_partition_def);
68 part->encoder = lto_symtab_encoder_new (false);
69 part->name = name;
70 part->insns = 0;
71 part->symbols = 0;
72 ltrans_partitions.safe_push (part);
73 return part;
74 }
75
76 /* Free memory used by ltrans datastructures. */
77
78 void
free_ltrans_partitions(void)79 free_ltrans_partitions (void)
80 {
81 unsigned int idx;
82 ltrans_partition part;
83 for (idx = 0; ltrans_partitions.iterate (idx, &part); idx++)
84 {
85 if (part->initializers_visited)
86 delete part->initializers_visited;
87 /* Symtab encoder is freed after streaming. */
88 free (part);
89 }
90 ltrans_partitions.release ();
91 }
92
93 /* Return true if symbol is already in some partition. */
94
95 static inline bool
symbol_partitioned_p(symtab_node * node)96 symbol_partitioned_p (symtab_node *node)
97 {
98 return node->aux;
99 }
100
101 /* Add references into the partition. */
102 static void
add_references_to_partition(ltrans_partition part,symtab_node * node)103 add_references_to_partition (ltrans_partition part, symtab_node *node)
104 {
105 int i;
106 struct ipa_ref *ref = NULL;
107
108 /* Add all duplicated references to the partition. */
109 for (i = 0; node->iterate_reference (i, ref); i++)
110 if (ref->referred->get_partitioning_class () == SYMBOL_DUPLICATE)
111 add_symbol_to_partition (part, ref->referred);
112 /* References to a readonly variable may be constant foled into its value.
113 Recursively look into the initializers of the constant variable and add
114 references, too. */
115 else if (is_a <varpool_node *> (ref->referred)
116 && (dyn_cast <varpool_node *> (ref->referred)
117 ->ctor_useable_for_folding_p ())
118 && !lto_symtab_encoder_in_partition_p (part->encoder, ref->referred))
119 {
120 if (!part->initializers_visited)
121 part->initializers_visited = new hash_set<symtab_node *>;
122 if (!part->initializers_visited->add (ref->referred))
123 add_references_to_partition (part, ref->referred);
124 }
125 }
126
127 /* Helper function for add_symbol_to_partition doing the actual dirty work
128 of adding NODE to PART. */
129
130 static bool
add_symbol_to_partition_1(ltrans_partition part,symtab_node * node)131 add_symbol_to_partition_1 (ltrans_partition part, symtab_node *node)
132 {
133 enum symbol_partitioning_class c = node->get_partitioning_class ();
134 struct ipa_ref *ref;
135 symtab_node *node1;
136
137 /* If NODE is already there, we have nothing to do. */
138 if (lto_symtab_encoder_in_partition_p (part->encoder, node))
139 return true;
140
141 /* non-duplicated aliases or tunks of a duplicated symbol needs to be output
142 just once.
143
144 Be lax about comdats; they may or may not be duplicated and we may
145 end up in need to duplicate keyed comdat because it has unkeyed alias. */
146 if (c == SYMBOL_PARTITION && !DECL_COMDAT (node->decl)
147 && symbol_partitioned_p (node))
148 return false;
149
150 /* Be sure that we never try to duplicate partitioned symbol
151 or add external symbol. */
152 gcc_assert (c != SYMBOL_EXTERNAL
153 && (c == SYMBOL_DUPLICATE || !symbol_partitioned_p (node)));
154
155 part->symbols++;
156
157 lto_set_symtab_encoder_in_partition (part->encoder, node);
158
159 if (symbol_partitioned_p (node))
160 {
161 node->in_other_partition = 1;
162 if (dump_file)
163 fprintf (dump_file,
164 "Symbol node %s now used in multiple partitions\n",
165 node->dump_name ());
166 }
167 node->aux = (void *)((size_t)node->aux + 1);
168
169 if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
170 {
171 struct cgraph_edge *e;
172 if (!node->alias && c == SYMBOL_PARTITION)
173 part->insns += ipa_size_summaries->get (cnode)->size;
174
175 /* Add all inline clones and callees that are duplicated. */
176 for (e = cnode->callees; e; e = e->next_callee)
177 if (!e->inline_failed)
178 add_symbol_to_partition_1 (part, e->callee);
179 else if (e->callee->get_partitioning_class () == SYMBOL_DUPLICATE)
180 add_symbol_to_partition (part, e->callee);
181
182 /* Add all thunks associated with the function. */
183 for (e = cnode->callers; e; e = e->next_caller)
184 if (e->caller->thunk.thunk_p && !e->caller->inlined_to)
185 add_symbol_to_partition_1 (part, e->caller);
186 }
187
188 add_references_to_partition (part, node);
189
190 /* Add all aliases associated with the symbol. */
191
192 FOR_EACH_ALIAS (node, ref)
193 if (!ref->referring->transparent_alias)
194 add_symbol_to_partition_1 (part, ref->referring);
195 else
196 {
197 struct ipa_ref *ref2;
198 /* We do not need to add transparent aliases if they are not used.
199 However we must add aliases of transparent aliases if they exist. */
200 FOR_EACH_ALIAS (ref->referring, ref2)
201 {
202 /* Nested transparent aliases are not permitted. */
203 gcc_checking_assert (!ref2->referring->transparent_alias);
204 add_symbol_to_partition_1 (part, ref2->referring);
205 }
206 }
207
208 /* Ensure that SAME_COMDAT_GROUP lists all allways added in a group. */
209 if (node->same_comdat_group)
210 for (node1 = node->same_comdat_group;
211 node1 != node; node1 = node1->same_comdat_group)
212 if (!node->alias)
213 {
214 bool added = add_symbol_to_partition_1 (part, node1);
215 gcc_assert (added);
216 }
217 return true;
218 }
219
220 /* If symbol NODE is really part of other symbol's definition (i.e. it is
221 internal label, thunk, alias or so), return the outer symbol.
222 When add_symbol_to_partition_1 is called on the outer symbol it must
223 eventually add NODE, too. */
224 static symtab_node *
contained_in_symbol(symtab_node * node)225 contained_in_symbol (symtab_node *node)
226 {
227 /* There is no need to consider transparent aliases to be part of the
228 definition: they are only useful insite the partition they are output
229 and thus we will always see an explicit reference to it. */
230 if (node->transparent_alias)
231 return node;
232 if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
233 {
234 cnode = cnode->function_symbol ();
235 if (cnode->inlined_to)
236 cnode = cnode->inlined_to;
237 return cnode;
238 }
239 else if (varpool_node *vnode = dyn_cast <varpool_node *> (node))
240 return vnode->ultimate_alias_target ();
241 return node;
242 }
243
244 /* Add symbol NODE to partition. When definition of NODE is part
245 of other symbol definition, add the other symbol, too. */
246
247 static void
add_symbol_to_partition(ltrans_partition part,symtab_node * node)248 add_symbol_to_partition (ltrans_partition part, symtab_node *node)
249 {
250 symtab_node *node1;
251
252 /* Verify that we do not try to duplicate something that cannot be. */
253 gcc_checking_assert (node->get_partitioning_class () == SYMBOL_DUPLICATE
254 || !symbol_partitioned_p (node));
255
256 while ((node1 = contained_in_symbol (node)) != node)
257 node = node1;
258
259 /* If we have duplicated symbol contained in something we cannot duplicate,
260 we are very badly screwed. The other way is possible, so we do not
261 assert this in add_symbol_to_partition_1.
262
263 Be lax about comdats; they may or may not be duplicated and we may
264 end up in need to duplicate keyed comdat because it has unkeyed alias. */
265
266 gcc_assert (node->get_partitioning_class () == SYMBOL_DUPLICATE
267 || DECL_COMDAT (node->decl)
268 || !symbol_partitioned_p (node));
269
270 add_symbol_to_partition_1 (part, node);
271 }
272
273 /* Undo all additions until number of cgraph nodes in PARITION is N_CGRAPH_NODES
274 and number of varpool nodes is N_VARPOOL_NODES. */
275
276 static void
undo_partition(ltrans_partition partition,unsigned int n_nodes)277 undo_partition (ltrans_partition partition, unsigned int n_nodes)
278 {
279 while (lto_symtab_encoder_size (partition->encoder) > (int)n_nodes)
280 {
281 symtab_node *node = lto_symtab_encoder_deref (partition->encoder,
282 n_nodes);
283 partition->symbols--;
284 cgraph_node *cnode;
285
286 /* After UNDO we no longer know what was visited. */
287 if (partition->initializers_visited)
288 delete partition->initializers_visited;
289 partition->initializers_visited = NULL;
290
291 if (!node->alias && (cnode = dyn_cast <cgraph_node *> (node))
292 && node->get_partitioning_class () == SYMBOL_PARTITION)
293 partition->insns -= ipa_size_summaries->get (cnode)->size;
294 lto_symtab_encoder_delete_node (partition->encoder, node);
295 node->aux = (void *)((size_t)node->aux - 1);
296 }
297 }
298
299 /* Group cgrah nodes by input files. This is used mainly for testing
300 right now. */
301
302 void
lto_1_to_1_map(void)303 lto_1_to_1_map (void)
304 {
305 symtab_node *node;
306 struct lto_file_decl_data *file_data;
307 hash_map<lto_file_decl_data *, ltrans_partition> pmap;
308 ltrans_partition partition;
309 int npartitions = 0;
310
311 FOR_EACH_SYMBOL (node)
312 {
313 if (node->get_partitioning_class () != SYMBOL_PARTITION
314 || symbol_partitioned_p (node))
315 continue;
316
317 file_data = node->lto_file_data;
318
319 if (file_data)
320 {
321 ltrans_partition *slot = &pmap.get_or_insert (file_data);
322 if (*slot)
323 partition = *slot;
324 else
325 {
326 partition = new_partition (file_data->file_name);
327 *slot = partition;
328 npartitions++;
329 }
330 }
331 else if (!file_data && ltrans_partitions.length ())
332 partition = ltrans_partitions[0];
333 else
334 {
335 partition = new_partition ("");
336 pmap.put (NULL, partition);
337 npartitions++;
338 }
339
340 add_symbol_to_partition (partition, node);
341 }
342
343 /* If the cgraph is empty, create one cgraph node set so that there is still
344 an output file for any variables that need to be exported in a DSO. */
345 if (!npartitions)
346 new_partition ("empty");
347
348 /* Order partitions by order of symbols because they are linked into binary
349 that way. */
350 ltrans_partitions.qsort (cmp_partitions_order);
351 }
352
353 /* Maximal partitioning. Put every new symbol into new partition if possible. */
354
355 void
lto_max_map(void)356 lto_max_map (void)
357 {
358 symtab_node *node;
359 ltrans_partition partition;
360 int npartitions = 0;
361
362 FOR_EACH_SYMBOL (node)
363 {
364 if (node->get_partitioning_class () != SYMBOL_PARTITION
365 || symbol_partitioned_p (node))
366 continue;
367 partition = new_partition (node->asm_name ());
368 add_symbol_to_partition (partition, node);
369 npartitions++;
370 }
371 if (!npartitions)
372 new_partition ("empty");
373 }
374
375 /* Helper function for qsort; sort nodes by order. */
376 static int
node_cmp(const void * pa,const void * pb)377 node_cmp (const void *pa, const void *pb)
378 {
379 const symtab_node *a = *static_cast<const symtab_node * const *> (pa);
380 const symtab_node *b = *static_cast<const symtab_node * const *> (pb);
381 return b->order - a->order;
382 }
383
384 /* Add all symtab nodes from NEXT_NODE to PARTITION in order. */
385
386 static void
add_sorted_nodes(vec<symtab_node * > & next_nodes,ltrans_partition partition)387 add_sorted_nodes (vec<symtab_node *> &next_nodes, ltrans_partition partition)
388 {
389 unsigned i;
390 symtab_node *node;
391
392 next_nodes.qsort (node_cmp);
393 FOR_EACH_VEC_ELT (next_nodes, i, node)
394 if (!symbol_partitioned_p (node))
395 add_symbol_to_partition (partition, node);
396 }
397
398 /* Return true if we should account reference from N1 to N2 in cost
399 of partition boundary. */
400
401 bool
account_reference_p(symtab_node * n1,symtab_node * n2)402 account_reference_p (symtab_node *n1, symtab_node *n2)
403 {
404 if (cgraph_node *cnode = dyn_cast <cgraph_node *> (n1))
405 n1 = cnode;
406 /* Do not account references from aliases - they are never split across
407 partitions. */
408 if (n1->alias)
409 return false;
410 /* Do not account recursion - the code below will handle it incorrectly
411 otherwise. Do not account references to external symbols: they will
412 never become local. Finally do not account references to duplicated
413 symbols: they will be always local. */
414 if (n1 == n2
415 || !n2->definition
416 || n2->get_partitioning_class () != SYMBOL_PARTITION)
417 return false;
418 /* If referring node is external symbol do not account it to boundary
419 cost. Those are added into units only to enable possible constant
420 folding and devirtulization.
421
422 Here we do not know if it will ever be added to some partition
423 (this is decided by compute_ltrans_boundary) and second it is not
424 that likely that constant folding will actually use the reference. */
425 if (contained_in_symbol (n1)
426 ->get_partitioning_class () == SYMBOL_EXTERNAL)
427 return false;
428 return true;
429 }
430
431
432 /* Group cgraph nodes into equally-sized partitions.
433
434 The partitioning algorithm is simple: nodes are taken in predefined order.
435 The order corresponds to the order we want functions to have in the final
436 output. In the future this will be given by function reordering pass, but
437 at the moment we use the topological order, which is a good approximation.
438
439 The goal is to partition this linear order into intervals (partitions) so
440 that all the partitions have approximately the same size and the number of
441 callgraph or IPA reference edges crossing boundaries is minimal.
442
443 This is a lot faster (O(n) in size of callgraph) than algorithms doing
444 priority-based graph clustering that are generally O(n^2) and, since
445 WHOPR is designed to make things go well across partitions, it leads
446 to good results.
447
448 We compute the expected size of a partition as:
449
450 max (total_size / lto_partitions, min_partition_size)
451
452 We use dynamic expected size of partition so small programs are partitioned
453 into enough partitions to allow use of multiple CPUs, while large programs
454 are not partitioned too much. Creating too many partitions significantly
455 increases the streaming overhead.
456
457 In the future, we would like to bound the maximal size of partitions so as
458 to prevent the LTRANS stage from consuming too much memory. At the moment,
459 however, the WPA stage is the most memory intensive for large benchmarks,
460 since too many types and declarations are read into memory.
461
462 The function implements a simple greedy algorithm. Nodes are being added
463 to the current partition until after 3/4 of the expected partition size is
464 reached. Past this threshold, we keep track of boundary size (number of
465 edges going to other partitions) and continue adding functions until after
466 the current partition has grown to twice the expected partition size. Then
467 the process is undone to the point where the minimal ratio of boundary size
468 and in-partition calls was reached. */
469
470 void
lto_balanced_map(int n_lto_partitions,int max_partition_size)471 lto_balanced_map (int n_lto_partitions, int max_partition_size)
472 {
473 int n_varpool_nodes = 0, varpool_pos = 0, best_varpool_pos = 0;
474 int best_noreorder_pos = 0;
475 auto_vec <cgraph_node *> order (symtab->cgraph_count);
476 auto_vec<cgraph_node *> noreorder;
477 auto_vec<varpool_node *> varpool_order;
478 struct cgraph_node *node;
479 int64_t original_total_size, total_size = 0;
480 int64_t partition_size;
481 ltrans_partition partition;
482 int last_visited_node = 0;
483 varpool_node *vnode;
484 int64_t cost = 0, internal = 0;
485 unsigned int best_n_nodes = 0, best_i = 0;
486 int64_t best_cost = -1, best_internal = 0, best_size = 0;
487 int npartitions;
488 int current_order = -1;
489 int noreorder_pos = 0;
490
491 FOR_EACH_VARIABLE (vnode)
492 gcc_assert (!vnode->aux);
493
494 FOR_EACH_DEFINED_FUNCTION (node)
495 if (node->get_partitioning_class () == SYMBOL_PARTITION)
496 {
497 if (node->no_reorder)
498 noreorder.safe_push (node);
499 else
500 order.safe_push (node);
501 if (!node->alias)
502 total_size += ipa_size_summaries->get (node)->size;
503 }
504
505 original_total_size = total_size;
506
507 /* Streaming works best when the source units do not cross partition
508 boundaries much. This is because importing function from a source
509 unit tends to import a lot of global trees defined there. We should
510 get better about minimizing the function bounday, but until that
511 things works smoother if we order in source order. */
512 order.qsort (tp_first_run_node_cmp);
513 noreorder.qsort (node_cmp);
514
515 if (dump_file)
516 {
517 for (unsigned i = 0; i < order.length (); i++)
518 fprintf (dump_file, "Balanced map symbol order:%s:%u\n",
519 order[i]->dump_name (), order[i]->tp_first_run);
520 for (unsigned i = 0; i < noreorder.length (); i++)
521 fprintf (dump_file, "Balanced map symbol no_reorder:%s:%u\n",
522 noreorder[i]->dump_name (), noreorder[i]->tp_first_run);
523 }
524
525 /* Collect all variables that should not be reordered. */
526 FOR_EACH_VARIABLE (vnode)
527 if (vnode->get_partitioning_class () == SYMBOL_PARTITION
528 && vnode->no_reorder)
529 varpool_order.safe_push (vnode);
530 n_varpool_nodes = varpool_order.length ();
531 varpool_order.qsort (node_cmp);
532
533 /* Compute partition size and create the first partition. */
534 if (param_min_partition_size > max_partition_size)
535 fatal_error (input_location, "min partition size cannot be greater "
536 "than max partition size");
537
538 partition_size = total_size / n_lto_partitions;
539 if (partition_size < param_min_partition_size)
540 partition_size = param_min_partition_size;
541 npartitions = 1;
542 partition = new_partition ("");
543 if (dump_file)
544 fprintf (dump_file, "Total unit size: %" PRId64 ", partition size: %" PRId64 "\n",
545 total_size, partition_size);
546
547 auto_vec<symtab_node *> next_nodes;
548
549 for (unsigned i = 0; i < order.length (); i++)
550 {
551 if (symbol_partitioned_p (order[i]))
552 continue;
553
554 current_order = order[i]->order;
555
556 /* Output noreorder and varpool in program order first. */
557 next_nodes.truncate (0);
558 while (varpool_pos < n_varpool_nodes
559 && varpool_order[varpool_pos]->order < current_order)
560 next_nodes.safe_push (varpool_order[varpool_pos++]);
561 while (noreorder_pos < (int)noreorder.length ()
562 && noreorder[noreorder_pos]->order < current_order)
563 next_nodes.safe_push (noreorder[noreorder_pos++]);
564 add_sorted_nodes (next_nodes, partition);
565
566 if (!symbol_partitioned_p (order[i]))
567 add_symbol_to_partition (partition, order[i]);
568
569
570 /* Once we added a new node to the partition, we also want to add
571 all referenced variables unless they was already added into some
572 earlier partition.
573 add_symbol_to_partition adds possibly multiple nodes and
574 variables that are needed to satisfy needs of ORDER[i].
575 We remember last visited cgraph and varpool node from last iteration
576 of outer loop that allows us to process every new addition.
577
578 At the same time we compute size of the boundary into COST. Every
579 callgraph or IPA reference edge leaving the partition contributes into
580 COST. Every edge inside partition was earlier computed as one leaving
581 it and thus we need to subtract it from COST. */
582 while (last_visited_node < lto_symtab_encoder_size (partition->encoder))
583 {
584 int j;
585 struct ipa_ref *ref = NULL;
586 symtab_node *snode = lto_symtab_encoder_deref (partition->encoder,
587 last_visited_node);
588
589 if (cgraph_node *node = dyn_cast <cgraph_node *> (snode))
590 {
591 struct cgraph_edge *edge;
592
593
594 last_visited_node++;
595
596 gcc_assert (node->definition || node->weakref);
597
598 /* Compute boundary cost of callgraph edges. */
599 for (edge = node->callees; edge; edge = edge->next_callee)
600 /* Inline edges will always end up local. */
601 if (edge->inline_failed
602 && account_reference_p (node, edge->callee))
603 {
604 int edge_cost = edge->frequency ();
605 int index;
606
607 if (!edge_cost)
608 edge_cost = 1;
609 gcc_assert (edge_cost > 0);
610 index = lto_symtab_encoder_lookup (partition->encoder,
611 edge->callee);
612 if (index != LCC_NOT_FOUND
613 && index < last_visited_node - 1)
614 cost -= edge_cost, internal += edge_cost;
615 else
616 cost += edge_cost;
617 }
618 for (edge = node->callers; edge; edge = edge->next_caller)
619 if (edge->inline_failed
620 && account_reference_p (edge->caller, node))
621 {
622 int edge_cost = edge->frequency ();
623 int index;
624
625 gcc_assert (edge->caller->definition);
626 if (!edge_cost)
627 edge_cost = 1;
628 gcc_assert (edge_cost > 0);
629 index = lto_symtab_encoder_lookup (partition->encoder,
630 edge->caller);
631 if (index != LCC_NOT_FOUND
632 && index < last_visited_node - 1)
633 cost -= edge_cost, internal += edge_cost;
634 else
635 cost += edge_cost;
636 }
637 }
638 else
639 last_visited_node++;
640
641 /* Compute boundary cost of IPA REF edges and at the same time look into
642 variables referenced from current partition and try to add them. */
643 for (j = 0; snode->iterate_reference (j, ref); j++)
644 if (!account_reference_p (snode, ref->referred))
645 ;
646 else if (is_a <varpool_node *> (ref->referred))
647 {
648 int index;
649
650 vnode = dyn_cast <varpool_node *> (ref->referred);
651 if (!symbol_partitioned_p (vnode)
652 && !vnode->no_reorder
653 && vnode->get_partitioning_class () == SYMBOL_PARTITION)
654 add_symbol_to_partition (partition, vnode);
655 index = lto_symtab_encoder_lookup (partition->encoder,
656 vnode);
657 if (index != LCC_NOT_FOUND
658 && index < last_visited_node - 1)
659 cost--, internal++;
660 else
661 cost++;
662 }
663 else
664 {
665 int index;
666
667 node = dyn_cast <cgraph_node *> (ref->referred);
668 index = lto_symtab_encoder_lookup (partition->encoder,
669 node);
670 if (index != LCC_NOT_FOUND
671 && index < last_visited_node - 1)
672 cost--, internal++;
673 else
674 cost++;
675 }
676 for (j = 0; snode->iterate_referring (j, ref); j++)
677 if (!account_reference_p (ref->referring, snode))
678 ;
679 else if (is_a <varpool_node *> (ref->referring))
680 {
681 int index;
682
683 vnode = dyn_cast <varpool_node *> (ref->referring);
684 gcc_assert (vnode->definition);
685 /* It is better to couple variables with their users,
686 because it allows them to be removed. Coupling
687 with objects they refer to only helps to reduce
688 number of symbols promoted to hidden. */
689 if (!symbol_partitioned_p (vnode)
690 && !vnode->no_reorder
691 && !vnode->can_remove_if_no_refs_p ()
692 && vnode->get_partitioning_class () == SYMBOL_PARTITION)
693 add_symbol_to_partition (partition, vnode);
694 index = lto_symtab_encoder_lookup (partition->encoder,
695 vnode);
696 if (index != LCC_NOT_FOUND
697 && index < last_visited_node - 1)
698 cost--, internal++;
699 else
700 cost++;
701 }
702 else
703 {
704 int index;
705
706 node = dyn_cast <cgraph_node *> (ref->referring);
707 gcc_assert (node->definition);
708 index = lto_symtab_encoder_lookup (partition->encoder,
709 node);
710 if (index != LCC_NOT_FOUND
711 && index < last_visited_node - 1)
712 cost--, internal++;
713 else
714 cost++;
715 }
716 }
717
718 gcc_assert (cost >= 0 && internal >= 0);
719
720 /* If the partition is large enough, start looking for smallest boundary cost.
721 If partition still seems too small (less than 7/8 of target weight) accept
722 any cost. If partition has right size, optimize for highest internal/cost.
723 Later we stop building partition if its size is 9/8 of the target wight. */
724 if (partition->insns < partition_size * 7 / 8
725 || best_cost == -1
726 || (!cost
727 || ((sreal)best_internal * (sreal) cost
728 < ((sreal) internal * (sreal)best_cost))))
729 {
730 best_cost = cost;
731 best_internal = internal;
732 best_size = partition->insns;
733 best_i = i;
734 best_n_nodes = lto_symtab_encoder_size (partition->encoder);
735 best_varpool_pos = varpool_pos;
736 best_noreorder_pos = noreorder_pos;
737 }
738 if (dump_file)
739 fprintf (dump_file, "Step %i: added %s, size %i, "
740 "cost %" PRId64 "/%" PRId64 " "
741 "best %" PRId64 "/%" PRId64", step %i\n", i,
742 order[i]->dump_name (),
743 partition->insns, cost, internal,
744 best_cost, best_internal, best_i);
745 /* Partition is too large, unwind into step when best cost was reached and
746 start new partition. */
747 if (partition->insns > 9 * partition_size / 8
748 || partition->insns > max_partition_size)
749 {
750 if (best_i != i)
751 {
752 if (dump_file)
753 fprintf (dump_file, "Unwinding %i insertions to step %i\n",
754 i - best_i, best_i);
755 undo_partition (partition, best_n_nodes);
756 varpool_pos = best_varpool_pos;
757 noreorder_pos = best_noreorder_pos;
758 }
759 gcc_assert (best_size == partition->insns);
760 i = best_i;
761 if (dump_file)
762 fprintf (dump_file,
763 "Partition insns: %i (want %" PRId64 ")\n",
764 partition->insns, partition_size);
765 /* When we are finished, avoid creating empty partition. */
766 while (i < order.length () - 1 && symbol_partitioned_p (order[i + 1]))
767 i++;
768 if (i == order.length () - 1)
769 break;
770 total_size -= partition->insns;
771 partition = new_partition ("");
772 last_visited_node = 0;
773 cost = 0;
774
775 if (dump_file)
776 fprintf (dump_file, "New partition\n");
777 best_n_nodes = 0;
778 best_cost = -1;
779
780 /* Since the size of partitions is just approximate, update the size after
781 we finished current one. */
782 if (npartitions < n_lto_partitions)
783 partition_size = total_size / (n_lto_partitions - npartitions);
784 else
785 /* Watch for overflow. */
786 partition_size = INT_MAX / 16;
787
788 if (dump_file)
789 fprintf (dump_file,
790 "Total size: %" PRId64 " partition_size: %" PRId64 "\n",
791 total_size, partition_size);
792 if (partition_size < param_min_partition_size)
793 partition_size = param_min_partition_size;
794 npartitions ++;
795 }
796 }
797
798 next_nodes.truncate (0);
799
800 /* Varables that are not reachable from the code go into last partition. */
801 FOR_EACH_VARIABLE (vnode)
802 if (vnode->get_partitioning_class () == SYMBOL_PARTITION
803 && !symbol_partitioned_p (vnode))
804 next_nodes.safe_push (vnode);
805
806 /* Output remaining ordered symbols. */
807 while (varpool_pos < n_varpool_nodes)
808 next_nodes.safe_push (varpool_order[varpool_pos++]);
809 while (noreorder_pos < (int)noreorder.length ())
810 next_nodes.safe_push (noreorder[noreorder_pos++]);
811 /* For one partition the cost of boundary should be 0 unless we added final
812 symbols here (these are not accounted) or we have accounting bug. */
813 gcc_assert (next_nodes.length () || npartitions != 1 || !best_cost || best_cost == -1);
814 add_sorted_nodes (next_nodes, partition);
815
816 if (dump_file)
817 {
818 fprintf (dump_file, "\nPartition sizes:\n");
819 unsigned partitions = ltrans_partitions.length ();
820
821 for (unsigned i = 0; i < partitions ; i++)
822 {
823 ltrans_partition p = ltrans_partitions[i];
824 fprintf (dump_file, "partition %d contains %d (%2.2f%%)"
825 " symbols and %d (%2.2f%%) insns\n", i, p->symbols,
826 100.0 * p->symbols / order.length (), p->insns,
827 100.0 * p->insns / original_total_size);
828 }
829
830 fprintf (dump_file, "\n");
831 }
832 }
833
834 /* Return true if we must not change the name of the NODE. The name as
835 extracted from the corresponding decl should be passed in NAME. */
836
837 static bool
must_not_rename(symtab_node * node,const char * name)838 must_not_rename (symtab_node *node, const char *name)
839 {
840 /* Our renaming machinery do not handle more than one change of assembler name.
841 We should not need more than one anyway. */
842 if (node->lto_file_data
843 && lto_get_decl_name_mapping (node->lto_file_data, name) != name)
844 {
845 if (dump_file)
846 fprintf (dump_file,
847 "Not privatizing symbol name: %s. It privatized already.\n",
848 name);
849 return true;
850 }
851 /* Avoid mangling of already mangled clones.
852 ??? should have a flag whether a symbol has a 'private' name already,
853 since we produce some symbols like that i.e. for global constructors
854 that are not really clones. */
855 if (node->unique_name)
856 {
857 if (dump_file)
858 fprintf (dump_file,
859 "Not privatizing symbol name: %s. Has unique name.\n",
860 name);
861 return true;
862 }
863 return false;
864 }
865
866 /* If we are an offload compiler, we may have to rewrite symbols to be
867 valid on this target. Return either PTR or a modified version of it. */
868
869 static const char *
maybe_rewrite_identifier(const char * ptr)870 maybe_rewrite_identifier (const char *ptr)
871 {
872 #if defined ACCEL_COMPILER && (defined NO_DOT_IN_LABEL || defined NO_DOLLAR_IN_LABEL)
873 #ifndef NO_DOT_IN_LABEL
874 char valid = '.';
875 const char reject[] = "$";
876 #elif !defined NO_DOLLAR_IN_LABEL
877 char valid = '$';
878 const char reject[] = ".";
879 #else
880 char valid = '_';
881 const char reject[] = ".$";
882 #endif
883
884 char *copy = NULL;
885 const char *match = ptr;
886 for (;;)
887 {
888 size_t off = strcspn (match, reject);
889 if (match[off] == '\0')
890 break;
891 if (copy == NULL)
892 {
893 copy = xstrdup (ptr);
894 match = copy;
895 }
896 copy[off] = valid;
897 }
898 return match;
899 #else
900 return ptr;
901 #endif
902 }
903
904 /* Ensure that the symbol in NODE is valid for the target, and if not,
905 rewrite it. */
906
907 static void
validize_symbol_for_target(symtab_node * node)908 validize_symbol_for_target (symtab_node *node)
909 {
910 tree decl = node->decl;
911 const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
912
913 if (must_not_rename (node, name))
914 return;
915
916 const char *name2 = maybe_rewrite_identifier (name);
917 if (name2 != name)
918 {
919 symtab->change_decl_assembler_name (decl, get_identifier (name2));
920 if (node->lto_file_data)
921 lto_record_renamed_decl (node->lto_file_data, name,
922 IDENTIFIER_POINTER
923 (DECL_ASSEMBLER_NAME (decl)));
924 }
925 }
926
927 /* Maps symbol names to unique lto clone counters. */
928 static hash_map<const char *, unsigned> *lto_clone_numbers;
929
930 /* Helper for privatize_symbol_name. Mangle NODE symbol name
931 represented by DECL. */
932
933 static bool
privatize_symbol_name_1(symtab_node * node,tree decl)934 privatize_symbol_name_1 (symtab_node *node, tree decl)
935 {
936 const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
937
938 if (must_not_rename (node, name))
939 return false;
940
941 name = maybe_rewrite_identifier (name);
942 unsigned &clone_number = lto_clone_numbers->get_or_insert (name);
943 symtab->change_decl_assembler_name (decl,
944 clone_function_name (
945 name, "lto_priv", clone_number));
946 clone_number++;
947
948 if (node->lto_file_data)
949 lto_record_renamed_decl (node->lto_file_data, name,
950 IDENTIFIER_POINTER
951 (DECL_ASSEMBLER_NAME (decl)));
952
953 if (dump_file)
954 fprintf (dump_file,
955 "Privatizing symbol name: %s -> %s\n",
956 name, IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl)));
957
958 return true;
959 }
960
961 /* Mangle NODE symbol name into a local name.
962 This is necessary to do
963 1) if two or more static vars of same assembler name
964 are merged into single ltrans unit.
965 2) if previously static var was promoted hidden to avoid possible conflict
966 with symbols defined out of the LTO world. */
967
968 static bool
privatize_symbol_name(symtab_node * node)969 privatize_symbol_name (symtab_node *node)
970 {
971 if (!privatize_symbol_name_1 (node, node->decl))
972 return false;
973
974 return true;
975 }
976
977 /* Promote variable VNODE to be static. */
978
979 static void
promote_symbol(symtab_node * node)980 promote_symbol (symtab_node *node)
981 {
982 /* We already promoted ... */
983 if (DECL_VISIBILITY (node->decl) == VISIBILITY_HIDDEN
984 && DECL_VISIBILITY_SPECIFIED (node->decl)
985 && TREE_PUBLIC (node->decl))
986 {
987 validize_symbol_for_target (node);
988 return;
989 }
990
991 gcc_checking_assert (!TREE_PUBLIC (node->decl)
992 && !DECL_EXTERNAL (node->decl));
993 /* Be sure that newly public symbol does not conflict with anything already
994 defined by the non-LTO part. */
995 privatize_symbol_name (node);
996 TREE_PUBLIC (node->decl) = 1;
997 DECL_VISIBILITY (node->decl) = VISIBILITY_HIDDEN;
998 DECL_VISIBILITY_SPECIFIED (node->decl) = true;
999 if (dump_file)
1000 fprintf (dump_file,
1001 "Promoting as hidden: %s (%s)\n", node->dump_name (),
1002 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
1003
1004 /* Promoting a symbol also promotes all transparent aliases with exception
1005 of weakref where the visibility flags are always wrong and set to
1006 !PUBLIC. */
1007 ipa_ref *ref;
1008 for (unsigned i = 0; node->iterate_direct_aliases (i, ref); i++)
1009 {
1010 struct symtab_node *alias = ref->referring;
1011 if (alias->transparent_alias && !alias->weakref)
1012 {
1013 TREE_PUBLIC (alias->decl) = 1;
1014 DECL_VISIBILITY (alias->decl) = VISIBILITY_HIDDEN;
1015 DECL_VISIBILITY_SPECIFIED (alias->decl) = true;
1016 if (dump_file)
1017 fprintf (dump_file,
1018 "Promoting alias as hidden: %s\n",
1019 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
1020 }
1021 gcc_assert (!alias->weakref || TREE_PUBLIC (alias->decl));
1022 }
1023 }
1024
1025 /* Return true if NODE needs named section even if it won't land in
1026 the partition symbol table.
1027
1028 FIXME: we should really not use named sections for inline clones
1029 and master clones. */
1030
1031 static bool
may_need_named_section_p(lto_symtab_encoder_t encoder,symtab_node * node)1032 may_need_named_section_p (lto_symtab_encoder_t encoder, symtab_node *node)
1033 {
1034 struct cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1035 if (!cnode)
1036 return false;
1037 if (node->real_symbol_p ())
1038 return false;
1039 return (!encoder
1040 || (lto_symtab_encoder_lookup (encoder, node) != LCC_NOT_FOUND
1041 && lto_symtab_encoder_encode_body_p (encoder,
1042 cnode)));
1043 }
1044
1045 /* If NODE represents a static variable. See if there are other variables
1046 of the same name in partition ENCODER (or in whole compilation unit if
1047 ENCODER is NULL) and if so, mangle the statics. Always mangle all
1048 conflicting statics, so we reduce changes of silently miscompiling
1049 asm statements referring to them by symbol name. */
1050
1051 static void
rename_statics(lto_symtab_encoder_t encoder,symtab_node * node)1052 rename_statics (lto_symtab_encoder_t encoder, symtab_node *node)
1053 {
1054 tree decl = node->decl;
1055 symtab_node *s;
1056 tree name = DECL_ASSEMBLER_NAME (decl);
1057
1058 /* See if this is static symbol. */
1059 if (((node->externally_visible && !node->weakref)
1060 /* FIXME: externally_visible is somewhat illogically not set for
1061 external symbols (i.e. those not defined). Remove this test
1062 once this is fixed. */
1063 || DECL_EXTERNAL (node->decl)
1064 || !node->real_symbol_p ())
1065 && !may_need_named_section_p (encoder, node))
1066 return;
1067
1068 /* Now walk symbols sharing the same name and see if there are any conflicts.
1069 (all types of symbols counts here, since we cannot have static of the
1070 same name as external or public symbol.) */
1071 for (s = symtab_node::get_for_asmname (name);
1072 s; s = s->next_sharing_asm_name)
1073 if ((s->real_symbol_p () || may_need_named_section_p (encoder, s))
1074 && s->decl != node->decl
1075 && (!encoder
1076 || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND))
1077 break;
1078
1079 /* OK, no confict, so we have nothing to do. */
1080 if (!s)
1081 return;
1082
1083 if (dump_file)
1084 fprintf (dump_file,
1085 "Renaming statics with asm name: %s\n", node->dump_name ());
1086
1087 /* Assign every symbol in the set that shares the same ASM name an unique
1088 mangled name. */
1089 for (s = symtab_node::get_for_asmname (name); s;)
1090 if ((!s->externally_visible || s->weakref)
1091 /* Transparent aliases having same name as target are renamed at a
1092 time their target gets new name. Transparent aliases that use
1093 separate assembler name require the name to be unique. */
1094 && (!s->transparent_alias || !s->definition || s->weakref
1095 || !symbol_table::assembler_names_equal_p
1096 (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (s->decl)),
1097 IDENTIFIER_POINTER
1098 (DECL_ASSEMBLER_NAME (s->get_alias_target()->decl))))
1099 && ((s->real_symbol_p ()
1100 && !DECL_EXTERNAL (s->decl)
1101 && !TREE_PUBLIC (s->decl))
1102 || may_need_named_section_p (encoder, s))
1103 && (!encoder
1104 || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND))
1105 {
1106 if (privatize_symbol_name (s))
1107 /* Re-start from beginning since we do not know how many
1108 symbols changed a name. */
1109 s = symtab_node::get_for_asmname (name);
1110 else s = s->next_sharing_asm_name;
1111 }
1112 else s = s->next_sharing_asm_name;
1113 }
1114
1115 /* Find out all static decls that need to be promoted to global because
1116 of cross file sharing. This function must be run in the WPA mode after
1117 all inlinees are added. */
1118
1119 void
lto_promote_cross_file_statics(void)1120 lto_promote_cross_file_statics (void)
1121 {
1122 unsigned i, n_sets;
1123
1124 gcc_assert (flag_wpa);
1125
1126 lto_stream_offload_p = false;
1127 select_what_to_stream ();
1128
1129 /* First compute boundaries. */
1130 n_sets = ltrans_partitions.length ();
1131 for (i = 0; i < n_sets; i++)
1132 {
1133 ltrans_partition part
1134 = ltrans_partitions[i];
1135 part->encoder = compute_ltrans_boundary (part->encoder);
1136 }
1137
1138 lto_clone_numbers = new hash_map<const char *, unsigned>;
1139
1140 /* Look at boundaries and promote symbols as needed. */
1141 for (i = 0; i < n_sets; i++)
1142 {
1143 lto_symtab_encoder_iterator lsei;
1144 lto_symtab_encoder_t encoder = ltrans_partitions[i]->encoder;
1145
1146 for (lsei = lsei_start (encoder); !lsei_end_p (lsei);
1147 lsei_next (&lsei))
1148 {
1149 symtab_node *node = lsei_node (lsei);
1150
1151 /* If symbol is static, rename it if its assembler name
1152 clashes with anything else in this unit. */
1153 rename_statics (encoder, node);
1154
1155 /* No need to promote if symbol already is externally visible ... */
1156 if (node->externally_visible
1157 /* ... or if it is part of current partition ... */
1158 || lto_symtab_encoder_in_partition_p (encoder, node)
1159 /* ... or if we do not partition it. This mean that it will
1160 appear in every partition referencing it. */
1161 || node->get_partitioning_class () != SYMBOL_PARTITION)
1162 {
1163 validize_symbol_for_target (node);
1164 continue;
1165 }
1166
1167 promote_symbol (node);
1168 }
1169 }
1170 delete lto_clone_numbers;
1171 }
1172
1173 /* Rename statics in the whole unit in the case that
1174 we do -flto-partition=none. */
1175
1176 void
lto_promote_statics_nonwpa(void)1177 lto_promote_statics_nonwpa (void)
1178 {
1179 symtab_node *node;
1180
1181 lto_clone_numbers = new hash_map<const char *, unsigned>;
1182 FOR_EACH_SYMBOL (node)
1183 {
1184 rename_statics (NULL, node);
1185 validize_symbol_for_target (node);
1186 }
1187 delete lto_clone_numbers;
1188 }
1189