Line data Source code
1 : /* LTO partitioning logic routines.
2 : Copyright (C) 2009-2026 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 : #define INCLUDE_VECTOR
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "target.h"
25 : #include "function.h"
26 : #include "basic-block.h"
27 : #include "tree.h"
28 : #include "gimple.h"
29 : #include "alloc-pool.h"
30 : #include "stringpool.h"
31 : #include "cgraph.h"
32 : #include "lto-streamer.h"
33 : #include "symbol-summary.h"
34 : #include "tree-vrp.h"
35 : #include "sreal.h"
36 : #include "ipa-cp.h"
37 : #include "ipa-prop.h"
38 : #include "ipa-fnsummary.h"
39 : #include "lto-partition.h"
40 : #include "ipa-locality-cloning.h"
41 :
42 : #include <limits>
43 :
44 : vec<ltrans_partition> ltrans_partitions;
45 :
46 : static void add_symbol_to_partition (ltrans_partition part,
47 : toplevel_node *node);
48 : static ltrans_partition join_partitions (ltrans_partition into,
49 : ltrans_partition from);
50 :
51 :
52 : /* Helper for qsort; compare partitions and return one with smaller order. */
53 :
54 : static int
55 944 : cmp_partitions_order (const void *a, const void *b)
56 : {
57 944 : const struct ltrans_partition_def *pa
58 : = *(struct ltrans_partition_def *const *)a;
59 944 : const struct ltrans_partition_def *pb
60 : = *(struct ltrans_partition_def *const *)b;
61 944 : int ordera = -1, orderb = -1;
62 :
63 944 : if (lto_symtab_encoder_size (pa->encoder))
64 944 : ordera = lto_symtab_encoder_deref (pa->encoder, 0)->order;
65 944 : if (lto_symtab_encoder_size (pb->encoder))
66 944 : orderb = lto_symtab_encoder_deref (pb->encoder, 0)->order;
67 944 : return ordera - orderb;
68 : }
69 :
70 : /* Create new partition with name NAME.
71 : Does not push into ltrans_partitions. */
72 : static ltrans_partition
73 8275 : new_partition_no_push (const char *name)
74 : {
75 8275 : ltrans_partition part = XCNEW (struct ltrans_partition_def);
76 8275 : part->encoder = lto_symtab_encoder_new (false);
77 8275 : part->name = name;
78 8275 : part->insns = 0;
79 8275 : part->symbols = 0;
80 8275 : return part;
81 : }
82 :
83 : /* Create new partition with name NAME. */
84 :
85 : static ltrans_partition
86 8275 : new_partition (const char *name)
87 : {
88 8275 : ltrans_partition part = new_partition_no_push (name);
89 8275 : ltrans_partitions.safe_push (part);
90 8275 : return part;
91 : }
92 :
93 : /* If the cgraph is empty, create one cgraph node set so that there is still
94 : an output file for any variables that need to be exported in a DSO. */
95 : static void
96 332 : create_partition_if_empty ()
97 : {
98 332 : if (!ltrans_partitions.length ())
99 2 : new_partition ("empty");
100 332 : }
101 :
102 : /* Free memory used by ltrans partition.
103 : Encoder can be kept to be freed after streaming. */
104 : static void
105 8275 : free_ltrans_partition (ltrans_partition part, bool delete_encoder)
106 : {
107 8275 : if (part->initializers_visited)
108 1487 : delete part->initializers_visited;
109 8275 : if (delete_encoder)
110 1 : lto_symtab_encoder_delete (part->encoder);
111 8275 : free (part);
112 8275 : }
113 :
114 : /* Free memory used by ltrans datastructures. */
115 :
116 : void
117 7889 : free_ltrans_partitions (void)
118 : {
119 7889 : unsigned int idx;
120 7889 : ltrans_partition part;
121 16163 : for (idx = 0; ltrans_partitions.iterate (idx, &part); idx++)
122 8274 : free_ltrans_partition (part, false);
123 7889 : ltrans_partitions.release ();
124 7889 : }
125 :
126 : /* Return true if symbol is already in some partition. */
127 :
128 : static inline bool
129 606329 : symbol_partitioned_p (symtab_node *node)
130 : {
131 606329 : return node->aux;
132 : }
133 :
134 : /* Add references into the partition. */
135 : static void
136 91791 : add_references_to_partition (ltrans_partition part, symtab_node *node)
137 : {
138 91791 : int i;
139 91791 : struct ipa_ref *ref = NULL;
140 :
141 : /* Add all duplicated references to the partition. */
142 283024 : for (i = 0; node->iterate_reference (i, ref); i++)
143 191233 : if (ref->referred->get_partitioning_class () == SYMBOL_DUPLICATE)
144 208 : add_symbol_to_partition (part, ref->referred);
145 : /* References to a readonly variable may be constant foled into its value.
146 : Recursively look into the initializers of the constant variable and add
147 : references, too. */
148 382258 : else if (is_a <varpool_node *> (ref->referred)
149 174920 : && (dyn_cast <varpool_node *> (ref->referred)
150 174920 : ->ctor_useable_for_folding_p ())
151 9479 : && !lto_symtab_encoder_in_partition_p (part->encoder, ref->referred))
152 : {
153 6092 : if (!part->initializers_visited)
154 1487 : part->initializers_visited = new hash_set<symtab_node *>;
155 6092 : if (!part->initializers_visited->add (ref->referred))
156 3342 : add_references_to_partition (part, ref->referred);
157 : }
158 91791 : }
159 :
160 : /* Helper function for add_symbol_to_partition doing the actual dirty work
161 : of adding NODE to PART. */
162 :
163 : static bool
164 88570 : add_symbol_to_partition_1 (ltrans_partition part, symtab_node *node)
165 : {
166 88570 : enum symbol_partitioning_class c = node->get_partitioning_class ();
167 88570 : struct ipa_ref *ref;
168 88570 : symtab_node *node1;
169 :
170 : /* If NODE is already there, we have nothing to do. */
171 88570 : if (lto_symtab_encoder_in_partition_p (part->encoder, node))
172 : return true;
173 :
174 : /* non-duplicated aliases or tunks of a duplicated symbol needs to be output
175 : just once.
176 :
177 : Be lax about comdats; they may or may not be duplicated and we may
178 : end up in need to duplicate keyed comdat because it has unkeyed alias. */
179 66867 : if (c == SYMBOL_PARTITION && !DECL_COMDAT (node->decl)
180 155151 : && symbol_partitioned_p (node))
181 : return false;
182 :
183 : /* Be sure that we never try to duplicate partitioned symbol
184 : or add external symbol. */
185 88449 : gcc_assert (c != SYMBOL_EXTERNAL
186 : && (c == SYMBOL_DUPLICATE || !symbol_partitioned_p (node)));
187 :
188 88449 : part->symbols++;
189 :
190 88449 : lto_set_symtab_encoder_in_partition (part->encoder, node);
191 :
192 88449 : if (symbol_partitioned_p (node))
193 : {
194 16 : node->in_other_partition = 1;
195 16 : if (dump_file)
196 0 : fprintf (dump_file,
197 : "Symbol node %s now used in multiple partitions\n",
198 : node->dump_name ());
199 : }
200 88449 : node->aux = (void *)((size_t)node->aux + 1);
201 :
202 88449 : if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
203 : {
204 64536 : struct cgraph_edge *e;
205 64536 : if (!node->alias && c == SYMBOL_PARTITION)
206 33102 : part->insns += ipa_size_summaries->get (cnode)->size;
207 :
208 : /* Add all inline clones and callees that are duplicated. */
209 319539 : for (e = cnode->callees; e; e = e->next_callee)
210 255003 : if (!e->inline_failed)
211 21402 : add_symbol_to_partition_1 (part, e->callee);
212 233601 : else if (e->callee->get_partitioning_class () == SYMBOL_DUPLICATE)
213 28 : add_symbol_to_partition (part, e->callee);
214 :
215 : /* Add all thunks associated with the function. */
216 188095 : for (e = cnode->callers; e; e = e->next_caller)
217 123559 : if (e->caller->thunk && !e->caller->inlined_to)
218 13 : add_symbol_to_partition_1 (part, e->caller);
219 : }
220 :
221 88449 : add_references_to_partition (part, node);
222 :
223 : /* Add all aliases associated with the symbol. */
224 :
225 187147 : FOR_EACH_ALIAS (node, ref)
226 10249 : if (!ref->referring->transparent_alias)
227 10244 : add_symbol_to_partition_1 (part, ref->referring);
228 : else
229 : {
230 : struct ipa_ref *ref2;
231 : /* We do not need to add transparent aliases if they are not used.
232 : However we must add aliases of transparent aliases if they exist. */
233 5 : FOR_EACH_ALIAS (ref->referring, ref2)
234 : {
235 : /* Nested transparent aliases are not permitted. */
236 0 : gcc_checking_assert (!ref2->referring->transparent_alias);
237 0 : add_symbol_to_partition_1 (part, ref2->referring);
238 : }
239 : }
240 :
241 : /* Ensure that SAME_COMDAT_GROUP lists all always added in a group. */
242 88449 : if (node->same_comdat_group)
243 86 : for (node1 = node->same_comdat_group;
244 136 : node1 != node; node1 = node1->same_comdat_group)
245 86 : if (!node->alias)
246 : {
247 58 : bool added = add_symbol_to_partition_1 (part, node1);
248 58 : gcc_assert (added);
249 : }
250 : return true;
251 : }
252 :
253 : /* If symbol NODE is really part of other symbol's definition (i.e. it is
254 : internal label, thunk, alias or so), return the outer symbol.
255 : When add_symbol_to_partition_1 is called on the outer symbol it must
256 : eventually add NODE, too. */
257 : static symtab_node *
258 586305 : contained_in_symbol (symtab_node *node)
259 : {
260 : /* There is no need to consider transparent aliases to be part of the
261 : definition: they are only useful insite the partition they are output
262 : and thus we will always see an explicit reference to it. */
263 586305 : if (node->transparent_alias)
264 : return node;
265 586297 : if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
266 : {
267 556055 : cnode = cnode->function_symbol ();
268 556055 : if (cnode->inlined_to)
269 78773 : cnode = cnode->inlined_to;
270 : return cnode;
271 : }
272 30242 : else if (varpool_node *vnode = dyn_cast <varpool_node *> (node))
273 30242 : return vnode->ultimate_alias_target ();
274 : return node;
275 : }
276 :
277 : /* Add symbol NODE to partition. When definition of NODE is part
278 : of other symbol definition, add the other symbol, too. */
279 :
280 : static void
281 56926 : add_symbol_to_partition (ltrans_partition part, toplevel_node *tnode)
282 : {
283 56926 : symtab_node *node1;
284 56926 : symtab_node* node = dyn_cast <symtab_node*> (tnode);
285 56926 : if (!node)
286 : {
287 73 : lto_set_symtab_encoder_in_partition (part->encoder, tnode);
288 73 : return;
289 : }
290 :
291 : /* Verify that we do not try to duplicate something that cannot be. */
292 56853 : gcc_checking_assert (node->get_partitioning_class () == SYMBOL_DUPLICATE
293 : || !symbol_partitioned_p (node));
294 :
295 56955 : while ((node1 = contained_in_symbol (node)) != node)
296 : node = node1;
297 :
298 : /* If we have duplicated symbol contained in something we cannot duplicate,
299 : we are very badly screwed. The other way is possible, so we do not
300 : assert this in add_symbol_to_partition_1.
301 :
302 : Be lax about comdats; they may or may not be duplicated and we may
303 : end up in need to duplicate keyed comdat because it has unkeyed alias. */
304 :
305 56853 : gcc_assert (node->get_partitioning_class () == SYMBOL_DUPLICATE
306 : || DECL_COMDAT (node->decl)
307 : || !symbol_partitioned_p (node));
308 :
309 56853 : add_symbol_to_partition_1 (part, node);
310 : }
311 :
312 : /* Undo all additions until number of cgraph nodes in PARITION is N_CGRAPH_NODES
313 : and number of varpool nodes is N_VARPOOL_NODES. */
314 :
315 : static void
316 1 : undo_partition (ltrans_partition partition, unsigned int n_nodes)
317 : {
318 450 : while (lto_symtab_encoder_size (partition->encoder) > (int)n_nodes)
319 : {
320 224 : toplevel_node *tnode = lto_symtab_encoder_deref (partition->encoder,
321 : n_nodes);
322 :
323 : /* After UNDO we no longer know what was visited. */
324 224 : if (partition->initializers_visited)
325 0 : delete partition->initializers_visited;
326 224 : partition->initializers_visited = NULL;
327 :
328 224 : lto_symtab_encoder_delete_node (partition->encoder, tnode);
329 :
330 448 : if (symtab_node* node = dyn_cast <symtab_node *> (tnode))
331 : {
332 224 : partition->symbols--;
333 224 : cgraph_node *cnode;
334 450 : if (!node->alias && (cnode = dyn_cast <cgraph_node *> (node))
335 226 : && node->get_partitioning_class () == SYMBOL_PARTITION)
336 2 : partition->insns -= ipa_size_summaries->get (cnode)->size;
337 224 : node->aux = (void *)((size_t)node->aux - 1);
338 : }
339 : }
340 1 : }
341 :
342 : /* Insert node into its file partition. */
343 : static void
344 5904 : node_into_file_partition (toplevel_node* node,
345 : hash_map<lto_file_decl_data *,
346 : ltrans_partition>& pmap)
347 : {
348 5904 : ltrans_partition partition;
349 :
350 5904 : struct lto_file_decl_data *file_data = node->lto_file_data;
351 :
352 5904 : if (file_data)
353 : {
354 5904 : ltrans_partition *slot = &pmap.get_or_insert (file_data);
355 5904 : if (*slot)
356 : partition = *slot;
357 : else
358 : {
359 563 : partition = new_partition (file_data->file_name);
360 563 : *slot = partition;
361 : }
362 : }
363 : else
364 0 : partition = new_partition ("");
365 :
366 5904 : add_symbol_to_partition (partition, node);
367 5904 : }
368 :
369 : /* map_1_to_1 is able to partition a subset of symbols/asm.
370 : map1to1_forced covers symbols/asm that we are forced to partition
371 : with 1_to_1 partitioning, otherwise they may become broken.
372 : Other symbols may be partitioned arbitrarily. */
373 : enum map1to1_content {
374 : /* Forced symbols are always attempted. */
375 : map1to1_forced_symbols = 0,
376 :
377 : map1to1_asm = 1,
378 : map1to1_other_symbols = 2,
379 : map1to1_symbols = map1to1_forced_symbols | map1to1_other_symbols,
380 : map1to1_forced = map1to1_asm | map1to1_forced_symbols,
381 : map1to1_all = map1to1_symbols | map1to1_asm,
382 : };
383 :
384 : /* Group cgraph nodes by input files. Used for symbols that must remain
385 : together. */
386 : static void
387 363 : map_1_to_1 (map1to1_content content)
388 : {
389 363 : symtab_node *node;
390 363 : hash_map<lto_file_decl_data *, ltrans_partition> pmap;
391 :
392 8610 : FOR_EACH_SYMBOL (node)
393 : {
394 8247 : if (node->get_partitioning_class () != SYMBOL_PARTITION
395 8247 : || symbol_partitioned_p (node))
396 1343 : continue;
397 :
398 6904 : if (!(content & map1to1_other_symbols) && !node->must_remain_in_tu_name
399 5736 : && !node->must_remain_in_tu_body && !node->no_reorder)
400 1072 : continue;
401 :
402 5832 : node_into_file_partition (node, pmap);
403 : }
404 :
405 363 : struct asm_node *anode;
406 363 : if (content & map1to1_asm)
407 431 : for (anode = symtab->first_asm_symbol (); anode;
408 72 : anode = safe_as_a<asm_node*>(anode->next))
409 72 : node_into_file_partition (anode, pmap);
410 :
411 : /* Order partitions by order of symbols because they are linked into binary
412 : that way. */
413 712 : ltrans_partitions.qsort (cmp_partitions_order);
414 363 : }
415 :
416 : /* Group cgrah nodes by input files. This is used mainly for testing
417 : right now. */
418 :
419 : void
420 313 : lto_1_to_1_map (void)
421 : {
422 313 : map_1_to_1 (map1to1_all);
423 313 : create_partition_if_empty ();
424 313 : }
425 :
426 : /* Toplevel assembly and symbols referenced by it can be required to remain
427 : in the same partition and not be renamed.
428 : noreroder symbols are also handled here to keep their order in respect to
429 : these symbols.
430 :
431 : This functions partitions these symbols with 1to1 partitioning and unites
432 : translation units to target_size as long as there is no name conflict.
433 :
434 : Remaining symbols can be partitioned with any strategy. */
435 : static void
436 7561 : create_asm_partitions (int64_t target_size)
437 : {
438 7561 : if (!symtab->first_asm_symbol ())
439 7530 : return;
440 31 : map_1_to_1 (map1to1_forced);
441 :
442 31 : size_t join_into = 0;
443 31 : size_t join_from = 0;
444 31 : hash_set<const char*> nonrenameable_symbols;
445 31 : lto_symtab_encoder_iterator lsei;
446 :
447 95 : for (; join_from < ltrans_partitions.length (); join_into++)
448 : {
449 33 : ltrans_partitions[join_into] = ltrans_partitions[join_from];
450 33 : ltrans_partition p_into = ltrans_partitions[join_into];
451 33 : nonrenameable_symbols.empty ();
452 :
453 33 : bool first_partition = true;
454 62 : for (; join_from < ltrans_partitions.length (); join_from++)
455 : {
456 34 : ltrans_partition p_from = ltrans_partitions[join_from];
457 34 : if (p_into->insns > target_size)
458 : break;
459 :
460 29 : lto_symtab_encoder_t encoder = p_from->encoder;
461 : /* All symbols that cannot be renamed and might collide. */
462 5591 : for (lsei = lsei_start (encoder); !lsei_end_p (lsei);
463 5562 : lsei_next (&lsei))
464 : {
465 5562 : toplevel_node* tnode = lsei_node (lsei);
466 5562 : if (symtab_node *snode = dyn_cast <symtab_node*> (tnode))
467 : {
468 5532 : if (snode->must_remain_in_tu_name)
469 1 : if (nonrenameable_symbols.add (snode->asm_name ()))
470 0 : goto finish_partition;
471 : }
472 5592 : else if (asm_node *anode = dyn_cast <asm_node*> (tnode))
473 : {
474 : symtab_node* snode;
475 : unsigned i = 0;
476 : /* This covers symbols defined by extended assembly. */
477 5562 : for (; anode->symbols_referenced.iterate (i, &snode); i++)
478 : {
479 0 : if (snode->must_remain_in_tu_name)
480 0 : if (nonrenameable_symbols.add (snode->asm_name ()))
481 0 : goto finish_partition;
482 : }
483 : }
484 : }
485 29 : first_partition = false;
486 :
487 29 : if (p_into != p_from)
488 1 : join_partitions (p_into, p_from);
489 : }
490 33 : finish_partition: {}
491 33 : if (first_partition)
492 5 : join_from++;
493 : }
494 31 : ltrans_partitions.truncate (join_into);
495 31 : }
496 :
497 : /* Maximal partitioning. Put every new symbol into new partition if possible. */
498 :
499 : void
500 15 : lto_max_map (void)
501 : {
502 15 : symtab_node *node;
503 15 : ltrans_partition partition;
504 :
505 : /* Needed for toplevel assembly. */
506 15 : map_1_to_1 (map1to1_forced);
507 :
508 247 : FOR_EACH_SYMBOL (node)
509 : {
510 232 : if (node->get_partitioning_class () != SYMBOL_PARTITION
511 232 : || symbol_partitioned_p (node))
512 54 : continue;
513 178 : partition = new_partition (node->asm_name ());
514 178 : add_symbol_to_partition (partition, node);
515 : }
516 :
517 15 : create_partition_if_empty ();
518 15 : }
519 :
520 : /* Helper function for qsort; sort nodes by order. */
521 : static int
522 544817 : node_cmp (const void *pa, const void *pb)
523 : {
524 544817 : const symtab_node *a = *static_cast<const symtab_node * const *> (pa);
525 544817 : const symtab_node *b = *static_cast<const symtab_node * const *> (pb);
526 544817 : return a->order - b->order;
527 : }
528 :
529 : /* Add all symtab nodes from NEXT_NODE to PARTITION in order. */
530 :
531 : static void
532 32383 : add_sorted_nodes (vec<symtab_node *> &next_nodes, ltrans_partition partition)
533 : {
534 32383 : unsigned i;
535 32383 : symtab_node *node;
536 :
537 32383 : next_nodes.qsort (node_cmp);
538 42329 : FOR_EACH_VEC_ELT (next_nodes, i, node)
539 9946 : if (!symbol_partitioned_p (node))
540 4236 : add_symbol_to_partition (partition, node);
541 32383 : }
542 :
543 : /* Return true if we should account reference from N1 to N2 in cost
544 : of partition boundary. */
545 :
546 : bool
547 677430 : account_reference_p (symtab_node *n1, symtab_node *n2)
548 : {
549 677430 : if (cgraph_node *cnode = dyn_cast <cgraph_node *> (n1))
550 : n1 = cnode;
551 : /* Do not account references from aliases - they are never split across
552 : partitions. */
553 677430 : if (n1->alias)
554 : return false;
555 : /* Do not account recursion - the code below will handle it incorrectly
556 : otherwise. Do not account references to external symbols: they will
557 : never become local. Finally do not account references to duplicated
558 : symbols: they will be always local. */
559 658866 : if (n1 == n2
560 658756 : || !n2->definition
561 1188332 : || n2->get_partitioning_class () != SYMBOL_PARTITION)
562 : return false;
563 : /* If referring node is external symbol do not account it to boundary
564 : cost. Those are added into units only to enable possible constant
565 : folding and devirtulization.
566 :
567 : Here we do not know if it will ever be added to some partition
568 : (this is decided by compute_ltrans_boundary) and second it is not
569 : that likely that constant folding will actually use the reference. */
570 529350 : if (contained_in_symbol (n1)
571 529350 : ->get_partitioning_class () == SYMBOL_EXTERNAL)
572 0 : return false;
573 : return true;
574 : }
575 :
576 : /* Joins two partitions into one.
577 : NULL partitions are equivalent to empty partition.
578 : If both partition are non-null, symbols from FROM are added into INTO. */
579 : static ltrans_partition
580 2 : join_partitions (ltrans_partition into, ltrans_partition from)
581 : {
582 2 : if (!into)
583 : return from;
584 1 : if (!from)
585 : return into;
586 :
587 1 : lto_symtab_encoder_iterator lsei;
588 1 : lto_symtab_encoder_t encoder = from->encoder;
589 :
590 : /* If aux is non zero, it will not be added to the new partition. Since
591 : adding symbols is recursive, it is safer to reduce aux of all symbols
592 : before adding any symbols to other partition. */
593 5 : for (lsei = lsei_start (encoder); !lsei_end_p (lsei); lsei_next (&lsei))
594 : {
595 8 : if (symtab_node *node = dyn_cast <symtab_node*> (lsei_node (lsei)))
596 3 : node->aux = (void *)((size_t)node->aux - 1);
597 : }
598 :
599 5 : for (lsei = lsei_start (encoder); !lsei_end_p (lsei); lsei_next (&lsei))
600 : {
601 4 : toplevel_node *node = lsei_node (lsei);
602 :
603 4 : if (symtab_node *snode = dyn_cast <symtab_node*> (node))
604 3 : if (symbol_partitioned_p (snode))
605 0 : continue;
606 :
607 4 : add_symbol_to_partition (into, node);
608 : }
609 :
610 1 : free_ltrans_partition (from, true);
611 :
612 1 : return into;
613 : }
614 :
615 : /* Takes symbols from given partitions and splits them into N partitions where
616 : each partitions contains one symbol and its requirements. */
617 : static std::vector<ltrans_partition>
618 0 : split_partition_into_nodes (ltrans_partition part)
619 : {
620 0 : std::vector<ltrans_partition> partitions;
621 :
622 0 : lto_symtab_encoder_iterator lsei;
623 0 : lto_symtab_encoder_t encoder = part->encoder;
624 :
625 0 : for (lsei = lsei_start (encoder); !lsei_end_p (lsei); lsei_next (&lsei))
626 : {
627 0 : if (symtab_node *node = dyn_cast <symtab_node*> (lsei_node (lsei)))
628 0 : node->aux = (void *)((size_t)node->aux - 1);
629 : }
630 :
631 0 : for (lsei = lsei_start (encoder); !lsei_end_p (lsei); lsei_next (&lsei))
632 : {
633 0 : toplevel_node *node = lsei_node (lsei);
634 :
635 0 : symtab_node *snode = dyn_cast <symtab_node*> (node);
636 0 : if (snode && (snode->get_partitioning_class () != SYMBOL_PARTITION
637 0 : || symbol_partitioned_p (snode)))
638 0 : continue;
639 :
640 0 : ltrans_partition new_part = new_partition_no_push (part->name);
641 0 : add_symbol_to_partition (new_part, node);
642 0 : partitions.push_back (new_part);
643 : }
644 :
645 0 : return partitions;
646 : }
647 :
648 : /* Returns whether partition contains symbols that cannot be reordered. */
649 : static bool
650 0 : is_partition_reorder (ltrans_partition part)
651 : {
652 0 : lto_symtab_encoder_iterator lsei;
653 0 : lto_symtab_encoder_t encoder = part->encoder;
654 :
655 0 : for (lsei = lsei_start (encoder); !lsei_end_p (lsei); lsei_next (&lsei))
656 : {
657 0 : symtab_node *node = dyn_cast <symtab_node*> (lsei_node (lsei));
658 0 : if (!node || node->no_reorder)
659 : return false;
660 : }
661 : return true;
662 : }
663 :
664 : /* Represents groups of symbols, that should be partitioned into n_partitions
665 : partitions. */
666 0 : class partition_set
667 : {
668 : public:
669 : /* Metadata to easily pass copy to new partition_set. */
670 : class metadata
671 : {
672 : public:
673 : /* Partitions can be reordered. */
674 : bool reorder;
675 : /* Partitions can be split into individual symbols. */
676 : bool splitable;
677 :
678 4 : metadata (bool reorder, bool splitable):
679 4 : reorder (reorder), splitable (splitable)
680 : {}
681 : };
682 : metadata data;
683 :
684 : /* Symbol groups. Use push (g) to insert symbols. */
685 : std::vector<ltrans_partition> sym_groups;
686 : /* Number of partitions these symbols should be partitioned into. */
687 : size_t n_partitions;
688 : /* Total number of instructions of all symbols. */
689 : int64_t insns;
690 :
691 : /* Constructor. Symbols and n_partitions can be added later. */
692 4 : partition_set (metadata data, std::vector<ltrans_partition> sym_groups = {},
693 : size_t n_partitions = 0)
694 4 : : data (data), sym_groups (std::move (sym_groups)),
695 4 : n_partitions (n_partitions), insns (0)
696 : {
697 5 : for (ltrans_partition g: this->sym_groups)
698 1 : insns += g->insns;
699 4 : }
700 :
701 : /* Adds symbol group and updates total insns. */
702 : void
703 0 : push (ltrans_partition g)
704 : {
705 0 : sym_groups.push_back (g);
706 0 : insns += g->insns;
707 : }
708 :
709 : /* Returns whether any symbols group is contained. */
710 : bool
711 0 : empty ()
712 : {
713 0 : return sym_groups.empty ();
714 : }
715 : };
716 :
717 : /* Distributes total n_partitions among partition_sets.
718 : Aims to be as fair as possible. */
719 : static void
720 0 : distribute_n_partitions (std::vector<partition_set>& ps, size_t n_partitions)
721 : {
722 0 : gcc_assert (ps.size ());
723 0 : gcc_assert (ps.size () <= n_partitions);
724 :
725 0 : int64_t total_size = 0;
726 :
727 0 : for (partition_set& p: ps)
728 : {
729 0 : total_size += p.insns;
730 0 : p.n_partitions = 0;
731 : }
732 :
733 0 : if (total_size <= 0)
734 : total_size = 1;
735 :
736 0 : size_t n_partitions_allocated = 0;
737 :
738 : /* First we allocate largest amount of partitions so that target_sizes are
739 : larger than target size of total (insns/total_size).
740 : All partition_set must have n_partitions at least one. */
741 0 : for (partition_set& p: ps)
742 : {
743 0 : p.n_partitions = n_partitions * p.insns / total_size;
744 0 : if (p.n_partitions == 0 && p.sym_groups.size ())
745 0 : p.n_partitions = 1;
746 0 : if (!p.data.splitable)
747 0 : p.n_partitions = std::min (p.n_partitions, p.sym_groups.size ());
748 :
749 0 : n_partitions_allocated += p.n_partitions;
750 : }
751 :
752 : /* Rare special case, with a lot of initially 0 sized splits. */
753 0 : while (n_partitions_allocated > n_partitions)
754 : {
755 : size_t idx = 0;
756 : int64_t min = std::numeric_limits<int64_t>::max ();
757 :
758 0 : for (size_t i = 0; i < ps.size (); ++i)
759 : {
760 0 : if (ps[i].n_partitions <= 1)
761 0 : continue;
762 :
763 0 : int64_t target_size = ps[i].insns / ps[i].n_partitions;
764 0 : if (min > target_size)
765 : {
766 0 : min = target_size;
767 0 : idx = i;
768 : }
769 : }
770 :
771 0 : ps[idx].n_partitions--;
772 0 : n_partitions_allocated--;
773 : }
774 :
775 : /* Typical case where with any increase of n_partitions target size will cross
776 : total target size. We optimize for minimal:
777 : (old_target_size - total_target_size)
778 : - (total_target_size - new_target_size). */
779 0 : while (n_partitions_allocated < n_partitions)
780 : {
781 : size_t idx = 0;
782 : int64_t max = 0;
783 :
784 0 : for (size_t i = 0; i < ps.size (); ++i)
785 : {
786 0 : if (ps[i].sym_groups.size () <= 1 && !ps[i].data.splitable)
787 0 : continue;
788 :
789 0 : int64_t target_size = ps[i].insns / ps[i].n_partitions;
790 0 : int64_t new_target_size = ps[i].insns / (ps[i].n_partitions + 1);
791 :
792 0 : int64_t positive_change = target_size + new_target_size;
793 :
794 0 : if (max < positive_change)
795 : {
796 0 : max = positive_change;
797 0 : idx = i;
798 : }
799 : }
800 :
801 0 : ps[idx].n_partitions++;
802 0 : n_partitions_allocated++;
803 : }
804 0 : }
805 :
806 : /* Splits off symbol groups that are larger than target size.
807 : n_partitions are then distributed between individual
808 : split off symbol groups, and everything else as a whole.
809 :
810 : Split off symbol groups with n_partitions > 1, are
811 : then split into individual symbols.
812 :
813 : Order is not conserved. This pass is ignored if reorder is not allowed. */
814 : static std::vector<partition_set>
815 0 : partition_over_target_split (partition_set& p)
816 : {
817 0 : gcc_assert (p.n_partitions >= 1);
818 :
819 0 : std::vector<partition_set> all;
820 0 : partition_set small (p.data);
821 :
822 0 : int64_t target_size = p.insns / p.n_partitions;
823 :
824 0 : for (ltrans_partition g: p.sym_groups)
825 : {
826 0 : if (g->insns > target_size
827 0 : && (p.data.reorder || is_partition_reorder (g)))
828 0 : all.push_back (partition_set (p.data, {g}));
829 : else
830 0 : small.push (g);
831 : }
832 :
833 0 : if (all.empty ())
834 0 : return {};
835 :
836 0 : if (small.sym_groups.size ())
837 : {
838 : /* Handles special case where n_partitions might be smaller than
839 : all.size (). Which can happen as result of integer division or with
840 : 0 sized partition_sets. Then also prevents too small symbol group.
841 : This should also be a special case; more common one,
842 : but with no correctness problems. */
843 0 : if (all.size () && (
844 0 : small.insns < (int64_t) p.n_partitions
845 0 : || small.insns < target_size * 0.6
846 0 : || small.insns < param_min_partition_size))
847 : {
848 : size_t idx = 0;
849 : int64_t min_insns = std::numeric_limits<int64_t>::max ();
850 0 : for (size_t i = 0; i < all.size (); ++i)
851 : {
852 0 : if (all[i].insns < min_insns)
853 : {
854 0 : min_insns = all[i].insns;
855 0 : idx = i;
856 : }
857 : }
858 :
859 0 : gcc_assert (all[idx].sym_groups.size () == 1);
860 :
861 : ltrans_partition& into = all[idx].sym_groups[0];
862 0 : for (ltrans_partition g: small.sym_groups)
863 0 : into = join_partitions (into, g);
864 :
865 0 : all[idx].insns = into->insns;
866 : }
867 : else
868 : {
869 0 : gcc_assert (all.size () < p.n_partitions);
870 0 : all.push_back (std::move (small));
871 : }
872 : }
873 :
874 0 : distribute_n_partitions (all, p.n_partitions);
875 :
876 0 : for (partition_set& p: all)
877 : {
878 0 : gcc_assert (p.sym_groups.size ());
879 :
880 : /* Handles large symbol groups (large files) that will be
881 : further divided. */
882 0 : if (p.sym_groups.size () == 1 && p.n_partitions > 1)
883 : {
884 0 : p.sym_groups = split_partition_into_nodes (p.sym_groups[0]);
885 0 : p.data.reorder = false;
886 0 : p.data.splitable = false;
887 : }
888 : }
889 :
890 0 : return all;
891 0 : }
892 :
893 : /* Splits partition_set into two partition_sets with
894 : equal or off by one n_partitions.
895 : Order is conserved. */
896 : static std::vector<partition_set>
897 0 : partition_binary_split (partition_set& p)
898 : {
899 0 : gcc_assert (p.n_partitions > 1);
900 :
901 0 : if (p.sym_groups.size () < 2)
902 0 : return {};
903 :
904 0 : int64_t target_size = p.insns / p.n_partitions;
905 :
906 :
907 0 : std::vector<partition_set> result (2, partition_set (p.data));
908 0 : partition_set& first = result[0];
909 0 : partition_set& second = result[1];
910 :
911 0 : first.n_partitions = p.n_partitions/2;
912 0 : second.n_partitions = p.n_partitions - first.n_partitions;
913 :
914 0 : int64_t first_target_size = first.n_partitions * target_size;
915 :
916 0 : int64_t insns = 0;
917 0 : for (ltrans_partition g: p.sym_groups)
918 : {
919 : /* We want at least one symbol in first partition. */
920 0 : if (first.empty ())
921 0 : first.push (g);
922 0 : else if (insns < first_target_size)
923 : {
924 0 : if (insns + g->insns < first_target_size)
925 0 : first.push (g);
926 : else
927 : {
928 : /* Target splitting point is in this symbol group. */
929 0 : int64_t diff_first = first_target_size - insns;
930 0 : int64_t diff_second = (insns + g->insns) - first_target_size;
931 :
932 0 : if (diff_first * second.n_partitions
933 0 : > diff_second * first.n_partitions)
934 0 : first.push (g);
935 : else
936 0 : second.push (g);
937 : }
938 : }
939 : else
940 0 : second.push (g);
941 :
942 0 : insns += g->insns;
943 : }
944 :
945 0 : return result;
946 0 : }
947 :
948 : /* Split partition_set into 'into' partition_sets with equal or off by one
949 : number of symbol groups. Sizes of symbol groups are ignored for deciding
950 : where to split. n_partitions is then distributed among new partition_sets
951 : based on their sizes.
952 : Order in conserved. */
953 : static std::vector<partition_set>
954 0 : partition_fixed_split (partition_set& p, size_t into)
955 : {
956 0 : gcc_assert (into < p.n_partitions);
957 :
958 0 : std::vector<partition_set> result;
959 :
960 0 : for (size_t i = 0; i < into; ++i)
961 : {
962 0 : size_t begin = i * p.sym_groups.size () / into;
963 0 : size_t end = (i + 1) * p.sym_groups.size () / into;
964 :
965 0 : auto it = p.sym_groups.begin ();
966 0 : result.push_back (partition_set (p.data, {it + begin, it + end}));
967 : }
968 :
969 0 : distribute_n_partitions (result, p.n_partitions);
970 :
971 0 : return result;
972 : }
973 :
974 :
975 : /* Base implementation to inherit from for all Partitioners. */
976 : class partitioner_base {
977 : public:
978 : /* Partitions sym_groups into n_partitions partitions inserted into
979 : ltrans_partitions. */
980 : void
981 4 : apply (std::vector<ltrans_partition>& sym_groups, int n_partitions)
982 : {
983 4 : partition_set p (partition_set::metadata (true, true),
984 4 : std::move (sym_groups), n_partitions);
985 4 : split (p, 0);
986 4 : }
987 :
988 : protected:
989 4 : partitioner_base (int64_t min_partition_size, int64_t max_partition_size):
990 4 : min_partition_size (std::max<int64_t>(min_partition_size, 1)),
991 4 : max_partition_size (std::max<int64_t>(max_partition_size, 1))
992 : {
993 : }
994 4 : virtual ~partitioner_base ()
995 : {}
996 :
997 : /* Joins all symbol groups into one finalized partition. */
998 : void
999 4 : finalize (partition_set& p)
1000 : {
1001 4 : ltrans_partition joined = NULL;
1002 :
1003 5 : for (ltrans_partition g: p.sym_groups)
1004 1 : joined = join_partitions (joined, g);
1005 :
1006 4 : if (joined)
1007 1 : ltrans_partitions.safe_push (joined);
1008 4 : }
1009 :
1010 : /* Splits all partition_sets. */
1011 : void
1012 0 : split_list (std::vector<partition_set>& ps, uintptr_t state)
1013 : {
1014 0 : for (partition_set& p: ps)
1015 0 : split (p, state);
1016 0 : }
1017 :
1018 : /* Handles common cases:
1019 : too large or small n_partitions, or n_partitions = 1.
1020 : And then calls split_state. */
1021 : void
1022 4 : split (partition_set& p, uintptr_t state)
1023 : {
1024 4 : size_t min_partitions = p.insns / max_partition_size + 1;
1025 4 : size_t max_partitions = p.insns / min_partition_size;
1026 4 : if (!p.data.splitable)
1027 0 : max_partitions = std::min (max_partitions, p.sym_groups.size ());
1028 :
1029 4 : p.n_partitions = std::max (p.n_partitions, min_partitions);
1030 4 : p.n_partitions = std::min (p.n_partitions, max_partitions);
1031 :
1032 4 : if (p.n_partitions <= 1)
1033 4 : return finalize (p);
1034 :
1035 0 : split_state (p, state);
1036 : }
1037 :
1038 : /* State machine for specific partitioner implementation. */
1039 : virtual void
1040 : split_state (partition_set& p, uintptr_t state) = 0;
1041 :
1042 : int64_t min_partition_size, max_partition_size;
1043 : };
1044 :
1045 :
1046 : /* Partitioner combining fixed, over_target, and binary partitionings. */
1047 4 : class partitioner_default: public partitioner_base
1048 : {
1049 : public:
1050 4 : partitioner_default (int64_t min_partition_size, int64_t max_partition_size):
1051 4 : partitioner_base (min_partition_size, max_partition_size)
1052 : {}
1053 :
1054 : private:
1055 : virtual void
1056 0 : split_state (partition_set& p, uintptr_t state)
1057 : {
1058 0 : const uintptr_t FIXED = 0;
1059 0 : const uintptr_t OVER_TARGET = 1;
1060 0 : const uintptr_t BINARY = 2;
1061 :
1062 0 : std::vector<partition_set> ps;
1063 :
1064 0 : switch (state)
1065 : {
1066 0 : case FIXED:
1067 0 : if (p.n_partitions > 64 && p.sym_groups.size () >= 4)
1068 : {
1069 0 : ps = partition_fixed_split (p, 4);
1070 0 : split_list (ps, OVER_TARGET);
1071 0 : break;
1072 : }
1073 :
1074 : /* FALLTHROUGH */
1075 0 : case OVER_TARGET:
1076 0 : ps = partition_over_target_split (p);
1077 0 : if (!ps.empty ())
1078 : {
1079 0 : split_list (ps, BINARY);
1080 0 : break;
1081 : }
1082 :
1083 : /* FALLTHROUGH */
1084 0 : case BINARY:
1085 0 : ps = partition_binary_split (p);
1086 0 : if (!ps.empty ())
1087 : {
1088 0 : split_list (ps, OVER_TARGET);
1089 0 : break;
1090 : }
1091 :
1092 : /* FALLTHROUGH */
1093 0 : default:
1094 0 : finalize (p);
1095 : }
1096 0 : }
1097 : };
1098 :
1099 : /* Group cgraph nodes into equally-sized partitions.
1100 : It tries to keep symbols from single source file together to minimize
1101 : propagation of divergence.
1102 :
1103 : It starts with symbols already grouped by source files. If reasonably
1104 : possible it only either combines several files into one final partition,
1105 : or, if a file is large, split the file into several final partitions.
1106 :
1107 : Intermediate representation is partition_set which contains set of
1108 : groups of symbols (each group corresponding to original source file) and
1109 : number of final partitions this partition_set should split into.
1110 :
1111 : First partition_fixed_split splits partition_set into constant number of
1112 : partition_sets with equal number of symbols groups. If for example there
1113 : are 39 source files, the resulting partition_sets will contain 10, 10,
1114 : 10, and 9 source files. This splitting intentionally ignores estimated
1115 : instruction counts to minimize propagation of divergence.
1116 :
1117 : Second partition_over_target_split separates too large files and splits
1118 : them into individual symbols to be combined back into several smaller
1119 : files in next step.
1120 :
1121 : Third partition_binary_split splits partition_set into two halves until
1122 : it should be split into only one final partition, at which point the
1123 : remaining symbols are joined into one final partition.
1124 : */
1125 :
1126 : void
1127 4 : lto_cache_map (int n_lto_partitions, int max_partition_size)
1128 : {
1129 4 : cgraph_node *node;
1130 4 : int64_t total_size = 0;
1131 14 : FOR_EACH_DEFINED_FUNCTION (node)
1132 10 : if (node->get_partitioning_class () == SYMBOL_PARTITION && !node->alias)
1133 10 : total_size += ipa_size_summaries->get (node)->size;
1134 :
1135 : /* Separates toplevel asm into its own partitions and handles name conflicts.
1136 :
1137 : We could do this directly in cache partitioning without separating asm
1138 : into its own partitions in most cases. */
1139 4 : create_asm_partitions (total_size / n_lto_partitions);
1140 4 : unsigned asm_n = ltrans_partitions.length ();
1141 :
1142 4 : map_1_to_1 (map1to1_symbols);
1143 4 : create_partition_if_empty ();
1144 :
1145 4 : std::vector<ltrans_partition> partitions;
1146 5 : for (unsigned i = asm_n; i < ltrans_partitions.length (); ++i)
1147 : {
1148 1 : ltrans_partition part = ltrans_partitions[i];
1149 1 : partitions.push_back (part);
1150 : }
1151 4 : ltrans_partitions.truncate (asm_n);
1152 :
1153 4 : partitioner_default partitioner = partitioner_default
1154 4 : (param_min_partition_size, max_partition_size);
1155 :
1156 4 : partitioner.apply (partitions, n_lto_partitions);
1157 4 : }
1158 :
1159 : /* Group cgraph nodes into equally-sized partitions.
1160 :
1161 : The partitioning algorithm is simple: nodes are taken in predefined order.
1162 : The order corresponds to the order we want functions to have in the final
1163 : output. In the future this will be given by function reordering pass, but
1164 : at the moment we use the topological order, which is a good approximation.
1165 :
1166 : The goal is to partition this linear order into intervals (partitions) so
1167 : that all the partitions have approximately the same size and the number of
1168 : callgraph or IPA reference edges crossing boundaries is minimal.
1169 :
1170 : This is a lot faster (O(n) in size of callgraph) than algorithms doing
1171 : priority-based graph clustering that are generally O(n^2) and, since
1172 : WHOPR is designed to make things go well across partitions, it leads
1173 : to good results.
1174 :
1175 : We compute the expected size of a partition as:
1176 :
1177 : max (total_size / lto_partitions, min_partition_size)
1178 :
1179 : We use dynamic expected size of partition so small programs are partitioned
1180 : into enough partitions to allow use of multiple CPUs, while large programs
1181 : are not partitioned too much. Creating too many partitions significantly
1182 : increases the streaming overhead.
1183 :
1184 : In the future, we would like to bound the maximal size of partitions so as
1185 : to prevent the LTRANS stage from consuming too much memory. At the moment,
1186 : however, the WPA stage is the most memory intensive for large benchmarks,
1187 : since too many types and declarations are read into memory.
1188 :
1189 : The function implements a simple greedy algorithm. Nodes are being added
1190 : to the current partition until after 3/4 of the expected partition size is
1191 : reached. Past this threshold, we keep track of boundary size (number of
1192 : edges going to other partitions) and continue adding functions until after
1193 : the current partition has grown to twice the expected partition size. Then
1194 : the process is undone to the point where the minimal ratio of boundary size
1195 : and in-partition calls was reached. */
1196 :
1197 : void
1198 7557 : lto_balanced_map (int n_lto_partitions, int max_partition_size)
1199 : {
1200 7557 : int n_varpool_nodes = 0, varpool_pos = 0, best_varpool_pos = 0;
1201 7557 : int best_noreorder_pos = 0;
1202 7557 : auto_vec <cgraph_node *> order (symtab->cgraph_count);
1203 7557 : auto_vec<cgraph_node *> noreorder;
1204 7557 : auto_vec<varpool_node *> varpool_order;
1205 7557 : struct cgraph_node *node;
1206 7557 : int64_t original_total_size, total_size = 0;
1207 7557 : int64_t partition_size;
1208 7557 : ltrans_partition partition;
1209 7557 : int last_visited_node = 0;
1210 7557 : varpool_node *vnode;
1211 7557 : int64_t cost = 0, internal = 0;
1212 7557 : unsigned int best_n_nodes = 0, best_i = 0;
1213 7557 : int64_t best_cost = -1, best_internal = 0, best_size = 0;
1214 7557 : int npartitions;
1215 7557 : int current_order = -1;
1216 7557 : int noreorder_pos = 0;
1217 :
1218 31666 : FOR_EACH_VARIABLE (vnode)
1219 24109 : gcc_assert (!vnode->aux);
1220 :
1221 70939 : FOR_EACH_DEFINED_FUNCTION (node)
1222 63382 : if (node->get_partitioning_class () == SYMBOL_PARTITION)
1223 : {
1224 42091 : if (node->no_reorder)
1225 7424 : noreorder.safe_push (node);
1226 : else
1227 34667 : order.safe_push (node);
1228 42091 : if (!node->alias)
1229 32187 : total_size += ipa_size_summaries->get (node)->size;
1230 : }
1231 :
1232 7557 : original_total_size = total_size;
1233 :
1234 : /* Streaming works best when the source units do not cross partition
1235 : boundaries much. This is because importing function from a source
1236 : unit tends to import a lot of global trees defined there. We should
1237 : get better about minimizing the function boundary, but until that
1238 : things works smoother if we order in source order. */
1239 7557 : order.qsort (tp_first_run_node_cmp);
1240 7557 : noreorder.qsort (node_cmp);
1241 :
1242 7557 : if (dump_file)
1243 : {
1244 0 : for (unsigned i = 0; i < order.length (); i++)
1245 0 : fprintf (dump_file, "Balanced map symbol order:%s:%u\n",
1246 0 : order[i]->dump_name (), order[i]->tp_first_run);
1247 0 : for (unsigned i = 0; i < noreorder.length (); i++)
1248 0 : fprintf (dump_file, "Balanced map symbol no_reorder:%s:%u\n",
1249 0 : noreorder[i]->dump_name (), noreorder[i]->tp_first_run);
1250 : }
1251 :
1252 : /* Collect all variables that should not be reordered. */
1253 31666 : FOR_EACH_VARIABLE (vnode)
1254 24109 : if (vnode->get_partitioning_class () == SYMBOL_PARTITION
1255 24109 : && vnode->no_reorder)
1256 1406 : varpool_order.safe_push (vnode);
1257 7557 : n_varpool_nodes = varpool_order.length ();
1258 7557 : varpool_order.qsort (node_cmp);
1259 :
1260 : /* Compute partition size and create the first partition. */
1261 7557 : if (param_min_partition_size > max_partition_size)
1262 0 : fatal_error (input_location, "min partition size cannot be greater "
1263 : "than max partition size");
1264 :
1265 7557 : partition_size = total_size / n_lto_partitions;
1266 7557 : if (partition_size < param_min_partition_size)
1267 : partition_size = param_min_partition_size;
1268 7557 : npartitions = 1;
1269 7557 : if (dump_file)
1270 0 : fprintf (dump_file, "Total unit size: %" PRId64 ", partition size: %" PRId64 "\n",
1271 : total_size, partition_size);
1272 :
1273 7557 : create_asm_partitions (partition_size);
1274 7557 : if (ltrans_partitions.length ())
1275 : {
1276 : int64_t insns = 0;
1277 : unsigned partitions = ltrans_partitions.length ();
1278 27 : for (unsigned i = 0; i + 1 < partitions ; i++)
1279 0 : insns += ltrans_partitions[i]->insns;
1280 :
1281 27 : total_size -= insns;
1282 27 : if (partition_size)
1283 27 : n_lto_partitions -= insns / partition_size;
1284 27 : if (n_lto_partitions < 1)
1285 : n_lto_partitions = 1;
1286 :
1287 27 : partition_size = total_size / n_lto_partitions;
1288 27 : if (partition_size < param_min_partition_size)
1289 : partition_size = param_min_partition_size;
1290 :
1291 27 : partition = ltrans_partitions[partitions - 1];
1292 : }
1293 : else
1294 7530 : partition = new_partition ("");
1295 :
1296 :
1297 7557 : auto_vec<symtab_node *> next_nodes;
1298 :
1299 42224 : for (unsigned i = 0; i < order.length (); i++)
1300 : {
1301 34669 : if (symbol_partitioned_p (order[i]))
1302 9843 : continue;
1303 :
1304 24826 : current_order = order[i]->order;
1305 :
1306 : /* Output noreorder and varpool in program order first. */
1307 24826 : next_nodes.truncate (0);
1308 24826 : while (varpool_pos < n_varpool_nodes
1309 24871 : && varpool_order[varpool_pos]->order < current_order)
1310 45 : next_nodes.safe_push (varpool_order[varpool_pos++]);
1311 24997 : while (noreorder_pos < (int)noreorder.length ()
1312 25272 : && noreorder[noreorder_pos]->order < current_order)
1313 171 : next_nodes.safe_push (noreorder[noreorder_pos++]);
1314 24826 : add_sorted_nodes (next_nodes, partition);
1315 :
1316 24826 : if (!symbol_partitioned_p (order[i]))
1317 24755 : add_symbol_to_partition (partition, order[i]);
1318 :
1319 :
1320 : /* Once we added a new node to the partition, we also want to add
1321 : all referenced variables unless they was already added into some
1322 : earlier partition.
1323 : add_symbol_to_partition adds possibly multiple nodes and
1324 : variables that are needed to satisfy needs of ORDER[i].
1325 : We remember last visited cgraph and varpool node from last iteration
1326 : of outer loop that allows us to process every new addition.
1327 :
1328 : At the same time we compute size of the boundary into COST. Every
1329 : callgraph or IPA reference edge leaving the partition contributes into
1330 : COST. Every edge inside partition was earlier computed as one leaving
1331 : it and thus we need to subtract it from COST. */
1332 204020 : for (; last_visited_node < lto_symtab_encoder_size (partition->encoder);
1333 : last_visited_node++)
1334 : {
1335 77184 : int j;
1336 77184 : struct ipa_ref *ref = NULL;
1337 77184 : toplevel_node *tnode = lto_symtab_encoder_deref (partition->encoder,
1338 : last_visited_node);
1339 :
1340 77184 : symtab_node* snode = dyn_cast <symtab_node*> (tnode);
1341 77184 : if (!snode)
1342 5 : continue;
1343 :
1344 77179 : if (cgraph_node *node = dyn_cast <cgraph_node *> (snode))
1345 : {
1346 55239 : struct cgraph_edge *edge;
1347 :
1348 55239 : gcc_assert (node->definition || node->weakref);
1349 :
1350 : /* Compute boundary cost of callgraph edges. */
1351 298095 : for (edge = node->callees; edge; edge = edge->next_callee)
1352 : /* Inline edges will always end up local. */
1353 242856 : if (edge->inline_failed
1354 242856 : && account_reference_p (node, edge->callee))
1355 : {
1356 93815 : int edge_cost = edge->frequency ();
1357 93815 : int index;
1358 :
1359 93815 : if (!edge_cost)
1360 : edge_cost = 1;
1361 36444 : gcc_assert (edge_cost > 0);
1362 187630 : index = lto_symtab_encoder_lookup (partition->encoder,
1363 93815 : edge->callee);
1364 93815 : if (index != LCC_NOT_FOUND && index < last_visited_node)
1365 88346 : cost -= edge_cost, internal += edge_cost;
1366 : else
1367 5469 : cost += edge_cost;
1368 : }
1369 170379 : for (edge = node->callers; edge; edge = edge->next_caller)
1370 115140 : if (edge->inline_failed
1371 115140 : && account_reference_p (edge->caller, node))
1372 : {
1373 93849 : int edge_cost = edge->frequency ();
1374 93849 : int index;
1375 :
1376 93849 : gcc_assert (edge->caller->definition);
1377 93849 : if (!edge_cost)
1378 : edge_cost = 1;
1379 36478 : gcc_assert (edge_cost > 0);
1380 93849 : index = lto_symtab_encoder_lookup (partition->encoder,
1381 : edge->caller);
1382 93849 : if (index != LCC_NOT_FOUND && index < last_visited_node)
1383 5457 : cost -= edge_cost, internal += edge_cost;
1384 : else
1385 88392 : cost += edge_cost;
1386 : }
1387 : }
1388 :
1389 : /* Compute boundary cost of IPA REF edges and at the same time look into
1390 : variables referenced from current partition and try to add them. */
1391 517864 : for (j = 0; snode->iterate_reference (j, ref); j++)
1392 181753 : if (!account_reference_p (snode, ref->referred))
1393 : ;
1394 170842 : else if (is_a <varpool_node *> (ref->referred))
1395 : {
1396 168219 : int index;
1397 :
1398 168219 : vnode = dyn_cast <varpool_node *> (ref->referred);
1399 168219 : if (!symbol_partitioned_p (vnode)
1400 21638 : && !vnode->no_reorder
1401 189810 : && vnode->get_partitioning_class () == SYMBOL_PARTITION)
1402 21591 : add_symbol_to_partition (partition, vnode);
1403 168219 : index = lto_symtab_encoder_lookup (partition->encoder,
1404 : vnode);
1405 168219 : if (index != LCC_NOT_FOUND && index < last_visited_node)
1406 106939 : cost--, internal++;
1407 : else
1408 61280 : cost++;
1409 : }
1410 : else
1411 : {
1412 2623 : int index;
1413 :
1414 2623 : node = dyn_cast <cgraph_node *> (ref->referred);
1415 2623 : index = lto_symtab_encoder_lookup (partition->encoder,
1416 : node);
1417 2623 : if (index != LCC_NOT_FOUND && index < last_visited_node)
1418 2288 : cost--, internal++;
1419 : else
1420 335 : cost++;
1421 : }
1422 257390 : for (j = 0; snode->iterate_referring (j, ref); j++)
1423 180211 : if (!account_reference_p (ref->referring, snode))
1424 : ;
1425 170844 : else if (is_a <varpool_node *> (ref->referring))
1426 : {
1427 3274 : int index;
1428 :
1429 3274 : vnode = dyn_cast <varpool_node *> (ref->referring);
1430 3274 : gcc_assert (vnode->definition);
1431 : /* It is better to couple variables with their users,
1432 : because it allows them to be removed. Coupling
1433 : with objects they refer to only helps to reduce
1434 : number of symbols promoted to hidden. */
1435 3274 : if (!symbol_partitioned_p (vnode)
1436 686 : && !vnode->no_reorder
1437 647 : && !vnode->can_remove_if_no_refs_p ()
1438 3296 : && vnode->get_partitioning_class () == SYMBOL_PARTITION)
1439 22 : add_symbol_to_partition (partition, vnode);
1440 3274 : index = lto_symtab_encoder_lookup (partition->encoder,
1441 : vnode);
1442 3274 : if (index != LCC_NOT_FOUND && index < last_visited_node)
1443 2509 : cost--, internal++;
1444 : else
1445 765 : cost++;
1446 : }
1447 : else
1448 : {
1449 167570 : int index;
1450 :
1451 167570 : node = dyn_cast <cgraph_node *> (ref->referring);
1452 167570 : gcc_assert (node->definition);
1453 167570 : index = lto_symtab_encoder_lookup (partition->encoder,
1454 : node);
1455 167570 : if (index != LCC_NOT_FOUND && index < last_visited_node)
1456 59064 : cost--, internal++;
1457 : else
1458 108506 : cost++;
1459 : }
1460 : }
1461 :
1462 24826 : gcc_assert (cost >= 0 && internal >= 0);
1463 :
1464 : /* If the partition is large enough, start looking for smallest boundary cost.
1465 : If partition still seems too small (less than 7/8 of target weight) accept
1466 : any cost. If partition has right size, optimize for highest internal/cost.
1467 : Later we stop building partition if its size is 9/8 of the target wight. */
1468 24826 : if (partition->insns < partition_size * 7 / 8
1469 43 : || best_cost == -1
1470 24867 : || (!cost
1471 40 : || ((sreal)best_internal * (sreal) cost
1472 24866 : < ((sreal) internal * (sreal)best_cost))))
1473 : {
1474 24815 : best_cost = cost;
1475 24815 : best_internal = internal;
1476 24815 : best_size = partition->insns;
1477 24815 : best_i = i;
1478 24815 : best_n_nodes = lto_symtab_encoder_size (partition->encoder);
1479 : best_varpool_pos = varpool_pos;
1480 : best_noreorder_pos = noreorder_pos;
1481 : }
1482 24826 : if (dump_file)
1483 0 : fprintf (dump_file, "Step %i: added %s, size %i, "
1484 : "cost %" PRId64 "/%" PRId64 " "
1485 : "best %" PRId64 "/%" PRId64", step %i\n", i,
1486 0 : order[i]->dump_name (),
1487 : partition->insns, cost, internal,
1488 : best_cost, best_internal, best_i);
1489 : /* Partition is too large, unwind into step when best cost was reached and
1490 : start new partition. */
1491 24826 : if (partition->insns > 9 * partition_size / 8
1492 24822 : || partition->insns > max_partition_size)
1493 : {
1494 4 : if (best_i != i)
1495 : {
1496 1 : if (dump_file)
1497 0 : fprintf (dump_file, "Unwinding %i insertions to step %i\n",
1498 : i - best_i, best_i);
1499 1 : undo_partition (partition, best_n_nodes);
1500 1 : varpool_pos = best_varpool_pos;
1501 1 : noreorder_pos = best_noreorder_pos;
1502 : }
1503 4 : gcc_assert (best_size == partition->insns);
1504 4 : i = best_i;
1505 4 : if (dump_file)
1506 0 : fprintf (dump_file,
1507 : "Partition insns: %i (want %" PRId64 ")\n",
1508 : partition->insns, partition_size);
1509 : /* When we are finished, avoid creating empty partition. */
1510 4 : while (i < order.length () - 1 && symbol_partitioned_p (order[i + 1]))
1511 : i++;
1512 4 : if (i == order.length () - 1)
1513 : break;
1514 2 : total_size -= partition->insns;
1515 2 : partition = new_partition ("");
1516 2 : last_visited_node = 0;
1517 2 : cost = 0;
1518 :
1519 2 : if (dump_file)
1520 0 : fprintf (dump_file, "New partition\n");
1521 2 : best_n_nodes = 0;
1522 2 : best_cost = -1;
1523 :
1524 : /* Since the size of partitions is just approximate, update the size after
1525 : we finished current one. */
1526 2 : if (npartitions < n_lto_partitions)
1527 2 : partition_size = total_size / (n_lto_partitions - npartitions);
1528 : else
1529 : /* Watch for overflow. */
1530 : partition_size = INT_MAX / 16;
1531 :
1532 2 : if (dump_file)
1533 0 : fprintf (dump_file,
1534 : "Total size: %" PRId64 " partition_size: %" PRId64 "\n",
1535 : total_size, partition_size);
1536 2 : if (partition_size < param_min_partition_size)
1537 : partition_size = param_min_partition_size;
1538 2 : npartitions ++;
1539 : }
1540 : }
1541 :
1542 7557 : next_nodes.truncate (0);
1543 :
1544 : /* Variables that are not reachable from the code go into last partition. */
1545 31666 : FOR_EACH_VARIABLE (vnode)
1546 24109 : if (vnode->get_partitioning_class () == SYMBOL_PARTITION
1547 24109 : && !symbol_partitioned_p (vnode))
1548 1116 : next_nodes.safe_push (vnode);
1549 :
1550 : /* Output remaining ordered symbols. */
1551 8918 : while (varpool_pos < n_varpool_nodes)
1552 1361 : next_nodes.safe_push (varpool_order[varpool_pos++]);
1553 23708 : while (noreorder_pos < (int)noreorder.length ())
1554 7253 : next_nodes.safe_push (noreorder[noreorder_pos++]);
1555 : /* For one partition the cost of boundary should be 0 unless we added final
1556 : symbols here (these are not accounted) or we have accounting bug. */
1557 7557 : gcc_assert (next_nodes.length () || ltrans_partitions.length () != 1
1558 : || !best_cost || best_cost == -1);
1559 7557 : add_sorted_nodes (next_nodes, partition);
1560 :
1561 7557 : if (dump_file)
1562 : {
1563 0 : fprintf (dump_file, "\nPartition sizes:\n");
1564 0 : unsigned partitions = ltrans_partitions.length ();
1565 :
1566 0 : for (unsigned i = 0; i < partitions ; i++)
1567 : {
1568 0 : ltrans_partition p = ltrans_partitions[i];
1569 0 : fprintf (dump_file, "partition %d contains %d (%2.2f%%)"
1570 : " symbols and %d (%2.2f%%) insns\n", i, p->symbols,
1571 0 : 100.0 * p->symbols / order.length (), p->insns,
1572 0 : 100.0 * p->insns / original_total_size);
1573 : }
1574 :
1575 0 : fprintf (dump_file, "\n");
1576 : }
1577 7557 : }
1578 :
1579 : /* Add all references of NODE into PARTITION. */
1580 :
1581 : static void
1582 0 : add_node_references_to_partition (ltrans_partition partition, symtab_node *node)
1583 : {
1584 0 : struct ipa_ref *ref = NULL;
1585 0 : varpool_node *vnode;
1586 0 : for (int j = 0; node->iterate_reference (j, ref); j++)
1587 0 : if (is_a <varpool_node *> (ref->referred))
1588 : {
1589 0 : vnode = dyn_cast <varpool_node *> (ref->referred);
1590 0 : if (!symbol_partitioned_p (vnode)
1591 0 : && !vnode->no_reorder
1592 0 : && vnode->get_partitioning_class () == SYMBOL_PARTITION)
1593 : {
1594 0 : add_symbol_to_partition (partition, vnode);
1595 0 : if (dump_file)
1596 0 : fprintf (dump_file, "Varpool Node: %s\n", vnode->dump_asm_name ());
1597 0 : add_node_references_to_partition (partition, vnode);
1598 : }
1599 : }
1600 :
1601 0 : for (int j = 0; node->iterate_referring (j, ref); j++)
1602 0 : if (is_a <varpool_node *> (ref->referring))
1603 : {
1604 0 : vnode = dyn_cast <varpool_node *> (ref->referring);
1605 0 : gcc_assert (vnode->definition);
1606 0 : if (!symbol_partitioned_p (vnode)
1607 0 : && !vnode->no_reorder
1608 0 : && !vnode->can_remove_if_no_refs_p ()
1609 0 : && vnode->get_partitioning_class () == SYMBOL_PARTITION)
1610 : {
1611 0 : add_symbol_to_partition (partition, vnode);
1612 0 : if (dump_file)
1613 0 : fprintf (dump_file, "Varpool Node: %s\n", vnode->dump_asm_name ());
1614 0 : add_node_references_to_partition (partition, vnode);
1615 : }
1616 : }
1617 0 : if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
1618 : {
1619 0 : struct cgraph_edge *e;
1620 :
1621 : /* Add all inline clones and callees that are duplicated. */
1622 0 : for (e = cnode->callees; e; e = e->next_callee)
1623 0 : if (e->callee->get_partitioning_class () == SYMBOL_DUPLICATE)
1624 0 : add_node_references_to_partition (partition, e->callee);
1625 :
1626 : /* Add all thunks associated with the function. */
1627 0 : for (e = cnode->callers; e; e = e->next_caller)
1628 0 : if (e->caller->thunk && !e->caller->inlined_to)
1629 0 : add_node_references_to_partition (partition, e->caller);
1630 : }
1631 :
1632 0 : }
1633 :
1634 : /* Create and return the created partition of name NAME. */
1635 :
1636 : static ltrans_partition
1637 0 : create_partition (int &npartitions, const char *name)
1638 : {
1639 0 : npartitions++;
1640 0 : return new_partition (name);
1641 : }
1642 :
1643 : /* Partitioning for code locality.
1644 : The partitioning plan (and prerequisite cloning) will have been done by the
1645 : IPA locality cloning pass. This function just implements that plan by
1646 : assigning those partitions to ltrans_parititions. */
1647 :
1648 : void
1649 0 : lto_locality_map (int max_partition_size)
1650 : {
1651 0 : symtab_node *snode;
1652 0 : int npartitions = 0;
1653 :
1654 0 : auto_vec<varpool_node *> varpool_order;
1655 0 : struct cgraph_node *node;
1656 :
1657 0 : if (locality_partitions.length () == 0)
1658 : {
1659 0 : if (dump_file)
1660 : {
1661 0 : fprintf (dump_file, "Locality partition: falling back to balanced "
1662 : "model\n");
1663 : }
1664 0 : lto_balanced_map (param_lto_partitions, param_max_partition_size);
1665 0 : return;
1666 : }
1667 0 : ltrans_partition partition = nullptr;
1668 0 : for (auto part : locality_partitions)
1669 : {
1670 0 : partition = create_partition (npartitions, "");
1671 0 : for (unsigned j = 0; j < part->nodes.length (); j++)
1672 : {
1673 0 : node = part->nodes[j];
1674 0 : if (symbol_partitioned_p (node))
1675 0 : continue;
1676 :
1677 0 : add_symbol_to_partition (partition, node);
1678 0 : add_node_references_to_partition (partition, node);
1679 : }
1680 : }
1681 :
1682 0 : int64_t partition_size = max_partition_size;
1683 : /* All other unpartitioned symbols. */
1684 0 : FOR_EACH_SYMBOL (snode)
1685 : {
1686 0 : if (snode->get_partitioning_class () == SYMBOL_PARTITION
1687 0 : && !symbol_partitioned_p (snode))
1688 : {
1689 0 : if (partition->insns > partition_size)
1690 0 : partition = create_partition (npartitions, "");
1691 :
1692 0 : add_symbol_to_partition (partition, snode);
1693 0 : if (dump_file)
1694 0 : fprintf (dump_file, "Un-ordered Node: %s\n", snode->dump_asm_name ());
1695 : }
1696 : }
1697 0 : }
1698 :
1699 : /* Return true if we must not change the name of the NODE. The name as
1700 : extracted from the corresponding decl should be passed in NAME. */
1701 :
1702 : static bool
1703 168993 : must_not_rename (symtab_node *node, const char *name)
1704 : {
1705 : /* Our renaming machinery do not handle more than one change of assembler name.
1706 : We should not need more than one anyway. */
1707 168993 : if (node->lto_file_data
1708 168993 : && lto_get_decl_name_mapping (node->lto_file_data, name) != name)
1709 : {
1710 217 : if (dump_file)
1711 0 : fprintf (dump_file,
1712 : "Not privatizing symbol name: %s. It privatized already.\n",
1713 : name);
1714 : return true;
1715 : }
1716 : /* Avoid mangling of already mangled clones.
1717 : ??? should have a flag whether a symbol has a 'private' name already,
1718 : since we produce some symbols like that i.e. for global constructors
1719 : that are not really clones.
1720 : ??? it is what unique_name means. We only need to set it when doing
1721 : private symbols. */
1722 168776 : if (node->unique_name)
1723 : {
1724 43419 : if (dump_file)
1725 0 : fprintf (dump_file,
1726 : "Not privatizing symbol name: %s. Has unique name.\n",
1727 : name);
1728 : return true;
1729 : }
1730 : return false;
1731 : }
1732 :
1733 : /* If we are an offload compiler, we may have to rewrite symbols to be
1734 : valid on this target. Return either PTR or a modified version of it. */
1735 :
1736 : static const char *
1737 0 : maybe_rewrite_identifier (const char *ptr)
1738 : {
1739 : #if defined ACCEL_COMPILER && (defined NO_DOT_IN_LABEL || defined NO_DOLLAR_IN_LABEL)
1740 : #ifndef NO_DOT_IN_LABEL
1741 : char valid = '.';
1742 : const char reject[] = "$";
1743 : #elif !defined NO_DOLLAR_IN_LABEL
1744 : char valid = '$';
1745 : const char reject[] = ".";
1746 : #else
1747 : char valid = '_';
1748 : const char reject[] = ".$";
1749 : #endif
1750 :
1751 : char *copy = NULL;
1752 : const char *match = ptr;
1753 : for (;;)
1754 : {
1755 : size_t off = strcspn (match, reject);
1756 : if (match[off] == '\0')
1757 : break;
1758 : if (copy == NULL)
1759 : {
1760 : copy = xstrdup (ptr);
1761 : match = copy;
1762 : }
1763 : copy[off] = valid;
1764 : }
1765 : if (copy)
1766 : {
1767 : match = IDENTIFIER_POINTER (get_identifier (copy));
1768 : free (copy);
1769 : }
1770 : return match;
1771 : #else
1772 0 : return ptr;
1773 : #endif
1774 : }
1775 :
1776 : /* Ensure that the symbol in NODE is valid for the target, and if not,
1777 : rewrite it. */
1778 :
1779 : static void
1780 168599 : validize_symbol_for_target (symtab_node *node)
1781 : {
1782 168599 : tree decl = node->decl;
1783 168599 : const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
1784 :
1785 168599 : if (must_not_rename (node, name))
1786 : return;
1787 :
1788 : const char *name2 = maybe_rewrite_identifier (name);
1789 : if (name2 != name)
1790 : {
1791 : symtab->change_decl_assembler_name (decl, get_identifier (name2));
1792 : if (node->lto_file_data)
1793 : lto_record_renamed_decl (node->lto_file_data, name, name2);
1794 : }
1795 : }
1796 :
1797 : /* Maps symbol names to unique lto clone counters. */
1798 : static hash_map<const char *, unsigned> *lto_clone_numbers;
1799 :
1800 : /* Helper for privatize_symbol_name. Mangle NODE symbol name
1801 : represented by DECL. */
1802 :
1803 : static bool
1804 394 : privatize_symbol_name_1 (symtab_node *node, tree decl)
1805 : {
1806 394 : const char *name0 = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
1807 :
1808 394 : if (must_not_rename (node, name0))
1809 : return false;
1810 :
1811 329 : const char *name = maybe_rewrite_identifier (name0);
1812 329 : unsigned &clone_number = lto_clone_numbers->get_or_insert (name);
1813 329 : symtab->change_decl_assembler_name (decl,
1814 : clone_function_name (
1815 329 : name, "lto_priv", clone_number));
1816 329 : clone_number++;
1817 :
1818 329 : if (node->lto_file_data)
1819 658 : lto_record_renamed_decl (node->lto_file_data, name0,
1820 329 : IDENTIFIER_POINTER
1821 : (DECL_ASSEMBLER_NAME (decl)));
1822 :
1823 329 : if (dump_file)
1824 0 : fprintf (dump_file,
1825 : "Privatizing symbol name: %s -> %s\n",
1826 0 : name, IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl)));
1827 :
1828 : return true;
1829 : }
1830 :
1831 : /* Mangle NODE symbol name into a local name.
1832 : This is necessary to do
1833 : 1) if two or more static vars of same assembler name
1834 : are merged into single ltrans unit.
1835 : 2) if previously static var was promoted hidden to avoid possible conflict
1836 : with symbols defined out of the LTO world. */
1837 :
1838 : static bool
1839 394 : privatize_symbol_name (symtab_node *node)
1840 : {
1841 0 : if (!privatize_symbol_name_1 (node, node->decl))
1842 : return false;
1843 :
1844 : return true;
1845 : }
1846 :
1847 : /* Promote variable VNODE to be static. */
1848 :
1849 : static void
1850 232 : promote_symbol (symtab_node *node)
1851 : {
1852 : /* We already promoted ... */
1853 232 : if (DECL_VISIBILITY (node->decl) == VISIBILITY_HIDDEN
1854 7 : && DECL_VISIBILITY_SPECIFIED (node->decl)
1855 239 : && TREE_PUBLIC (node->decl))
1856 : {
1857 7 : validize_symbol_for_target (node);
1858 7 : return;
1859 : }
1860 :
1861 225 : gcc_checking_assert (!TREE_PUBLIC (node->decl)
1862 : && !DECL_EXTERNAL (node->decl));
1863 : /* Be sure that newly public symbol does not conflict with anything already
1864 : defined by the non-LTO part. */
1865 225 : privatize_symbol_name (node);
1866 225 : TREE_PUBLIC (node->decl) = 1;
1867 : /* After privatization the node should not conflict with any other symbol,
1868 : so it is prevailing. This is important to keep binds_to_current_def_p
1869 : to work across partitions. */
1870 225 : node->resolution = LDPR_PREVAILING_DEF_IRONLY;
1871 225 : node->semantic_interposition = false;
1872 225 : DECL_VISIBILITY (node->decl) = VISIBILITY_HIDDEN;
1873 225 : DECL_VISIBILITY_SPECIFIED (node->decl) = true;
1874 225 : if (dump_file)
1875 0 : fprintf (dump_file,
1876 : "Promoting as hidden: %s (%s)\n", node->dump_name (),
1877 0 : IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
1878 :
1879 : /* Promoting a symbol also promotes all transparent aliases with exception
1880 : of weakref where the visibility flags are always wrong and set to
1881 : !PUBLIC. */
1882 225 : ipa_ref *ref;
1883 232 : for (unsigned i = 0; node->iterate_direct_aliases (i, ref); i++)
1884 : {
1885 7 : struct symtab_node *alias = ref->referring;
1886 7 : if (alias->transparent_alias && !alias->weakref)
1887 : {
1888 0 : TREE_PUBLIC (alias->decl) = 1;
1889 0 : DECL_VISIBILITY (alias->decl) = VISIBILITY_HIDDEN;
1890 0 : DECL_VISIBILITY_SPECIFIED (alias->decl) = true;
1891 0 : if (dump_file)
1892 0 : fprintf (dump_file,
1893 : "Promoting alias as hidden: %s\n",
1894 0 : IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
1895 : }
1896 7 : gcc_assert (!alias->weakref || TREE_PUBLIC (alias->decl));
1897 : }
1898 : }
1899 :
1900 : /* Return true if NODE needs named section even if it won't land in
1901 : the partition symbol table.
1902 :
1903 : FIXME: we should really not use named sections for master clones. */
1904 :
1905 : static bool
1906 109804 : may_need_named_section_p (lto_symtab_encoder_t encoder, symtab_node *node)
1907 : {
1908 109804 : struct cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1909 : /* We do not need to handle variables since we never clone them. */
1910 101122 : if (!cnode)
1911 : return false;
1912 : /* Only master clones will have bodies streamed. */
1913 101122 : if (cnode->clone_of)
1914 : return false;
1915 68398 : if (node->real_symbol_p ())
1916 : return false;
1917 2918 : return (!encoder
1918 2918 : || (lto_symtab_encoder_lookup (encoder, node) != LCC_NOT_FOUND
1919 2906 : && lto_symtab_encoder_encode_body_p (encoder,
1920 : cnode)));
1921 : }
1922 :
1923 : /* If NODE represents a static variable. See if there are other variables
1924 : of the same name in partition ENCODER (or in whole compilation unit if
1925 : ENCODER is NULL) and if so, mangle the statics. Always mangle all
1926 : conflicting statics, so we reduce changes of silently miscompiling
1927 : asm statements referring to them by symbol name. */
1928 :
1929 : static void
1930 168824 : rename_statics (lto_symtab_encoder_t encoder, symtab_node *node)
1931 : {
1932 168824 : tree decl = node->decl;
1933 168824 : symtab_node *s;
1934 168824 : tree name = DECL_ASSEMBLER_NAME (decl);
1935 :
1936 : /* See if this is static symbol. */
1937 50156 : if (((node->externally_visible && !node->weakref)
1938 : /* FIXME: externally_visible is somewhat illogically not set for
1939 : external symbols (i.e. those not defined). Remove this test
1940 : once this is fixed. */
1941 118668 : || DECL_EXTERNAL (node->decl)
1942 94571 : || !node->real_symbol_p ())
1943 264404 : && !may_need_named_section_p (encoder, node))
1944 : return;
1945 :
1946 : /* Now walk symbols sharing the same name and see if there are any conflicts.
1947 : (all types of symbols counts here, since we cannot have static of the
1948 : same name as external or public symbol.) */
1949 74706 : for (s = symtab_node::get_for_asmname (name);
1950 162153 : s; s = s->next_sharing_asm_name)
1951 101757 : if ((s->real_symbol_p () || may_need_named_section_p (encoder, s))
1952 74773 : && s->decl != node->decl
1953 87659 : && (!encoder
1954 76 : || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND))
1955 : break;
1956 :
1957 : /* OK, no conflict, so we have nothing to do. */
1958 74706 : if (!s)
1959 : return;
1960 :
1961 92 : if (dump_file)
1962 0 : fprintf (dump_file,
1963 : "Renaming statics with asm name: %s\n", node->dump_name ());
1964 :
1965 : /* Assign every symbol in the set that shares the same ASM name an unique
1966 : mangled name. */
1967 285 : for (s = symtab_node::get_for_asmname (name); s;)
1968 16 : if ((!s->externally_visible || s->weakref)
1969 : /* Transparent aliases having same name as target are renamed at a
1970 : time their target gets new name. Transparent aliases that use
1971 : separate assembler name require the name to be unique. */
1972 177 : && (!s->transparent_alias || !s->definition || s->weakref
1973 6 : || !symbol_table::assembler_names_equal_p
1974 6 : (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (s->decl)),
1975 6 : IDENTIFIER_POINTER
1976 : (DECL_ASSEMBLER_NAME (s->get_alias_target()->decl))))
1977 171 : && ((s->real_symbol_p ()
1978 167 : && !DECL_EXTERNAL (s->decl)
1979 165 : && !TREE_PUBLIC (s->decl))
1980 6 : || may_need_named_section_p (encoder, s))
1981 362 : && (!encoder
1982 85 : || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND))
1983 : {
1984 169 : if (privatize_symbol_name (s))
1985 : /* Re-start from beginning since we do not know how many
1986 : symbols changed a name. */
1987 164 : s = symtab_node::get_for_asmname (name);
1988 5 : else s = s->next_sharing_asm_name;
1989 : }
1990 24 : else s = s->next_sharing_asm_name;
1991 : }
1992 :
1993 : /* Find out all static decls that need to be promoted to global because
1994 : of cross file sharing. This function must be run in the WPA mode after
1995 : all inlinees are added. */
1996 :
1997 : void
1998 7889 : lto_promote_cross_file_statics (void)
1999 : {
2000 7889 : unsigned i, n_sets;
2001 :
2002 7889 : gcc_assert (flag_wpa);
2003 :
2004 7889 : lto_stream_offload_p = false;
2005 7889 : select_what_to_stream ();
2006 :
2007 : /* First compute boundaries. */
2008 7889 : n_sets = ltrans_partitions.length ();
2009 16163 : for (i = 0; i < n_sets; i++)
2010 : {
2011 8274 : ltrans_partition part
2012 8274 : = ltrans_partitions[i];
2013 8274 : if (dump_file)
2014 0 : fprintf (dump_file, "lto_promote_cross_file_statics for part %s %p\n",
2015 0 : part->name, (void *)part->encoder);
2016 8274 : part->encoder = compute_ltrans_boundary (part->encoder);
2017 8274 : if (dump_file)
2018 0 : fprintf (dump_file, "new encoder %p\n", (void *)part->encoder);
2019 : }
2020 :
2021 7889 : lto_clone_numbers = new hash_map<const char *, unsigned>;
2022 :
2023 : /* Look at boundaries and promote symbols as needed. */
2024 16163 : for (i = 0; i < n_sets; i++)
2025 : {
2026 8274 : lto_symtab_encoder_iterator lsei;
2027 8274 : lto_symtab_encoder_t encoder = ltrans_partitions[i]->encoder;
2028 :
2029 116856 : for (lsei = lsei_start (encoder); !lsei_end_p (lsei);
2030 108582 : lsei_next (&lsei))
2031 : {
2032 108582 : toplevel_node *tnode = lsei_node (lsei);
2033 108582 : symtab_node *node = dyn_cast <symtab_node*> (tnode);
2034 108582 : if (!node)
2035 72 : continue;
2036 :
2037 : /* If symbol is static, rename it if its assembler name
2038 : clashes with anything else in this unit. */
2039 108510 : rename_statics (encoder, node);
2040 :
2041 : /* No need to promote if symbol already is externally visible ... */
2042 216788 : if (node->externally_visible
2043 : /* ... or if it is part of current partition ... */
2044 97064 : || lto_symtab_encoder_in_partition_p (encoder, node)
2045 : /* ... or if we do not partition it. This mean that it will
2046 : appear in every partition referencing it. */
2047 128536 : || node->get_partitioning_class () != SYMBOL_PARTITION)
2048 : {
2049 108278 : validize_symbol_for_target (node);
2050 108278 : continue;
2051 : }
2052 :
2053 232 : promote_symbol (node);
2054 : }
2055 : }
2056 15778 : delete lto_clone_numbers;
2057 7889 : }
2058 :
2059 : /* Rename statics in the whole unit in the case that
2060 : we do -flto-partition=none. */
2061 :
2062 : void
2063 4491 : lto_promote_statics_nonwpa (void)
2064 : {
2065 4491 : symtab_node *node;
2066 :
2067 4491 : lto_clone_numbers = new hash_map<const char *, unsigned>;
2068 64805 : FOR_EACH_SYMBOL (node)
2069 : {
2070 60314 : rename_statics (NULL, node);
2071 60314 : validize_symbol_for_target (node);
2072 : }
2073 8982 : delete lto_clone_numbers;
2074 4491 : }
|
