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 898 : cmp_partitions_order (const void *a, const void *b)
56 : {
57 898 : const struct ltrans_partition_def *pa
58 : = *(struct ltrans_partition_def *const *)a;
59 898 : const struct ltrans_partition_def *pb
60 : = *(struct ltrans_partition_def *const *)b;
61 898 : int ordera = -1, orderb = -1;
62 :
63 898 : if (lto_symtab_encoder_size (pa->encoder))
64 898 : ordera = lto_symtab_encoder_deref (pa->encoder, 0)->order;
65 898 : if (lto_symtab_encoder_size (pb->encoder))
66 898 : orderb = lto_symtab_encoder_deref (pb->encoder, 0)->order;
67 898 : return ordera - orderb;
68 : }
69 :
70 : /* Create new partition with name NAME.
71 : Does not push into ltrans_partitions. */
72 : static ltrans_partition
73 8191 : new_partition_no_push (const char *name)
74 : {
75 8191 : ltrans_partition part = XCNEW (struct ltrans_partition_def);
76 8191 : part->encoder = lto_symtab_encoder_new (false);
77 8191 : part->name = name;
78 8191 : part->insns = 0;
79 8191 : part->symbols = 0;
80 8191 : return part;
81 : }
82 :
83 : /* Create new partition with name NAME. */
84 :
85 : static ltrans_partition
86 8191 : new_partition (const char *name)
87 : {
88 8191 : ltrans_partition part = new_partition_no_push (name);
89 8191 : ltrans_partitions.safe_push (part);
90 8191 : 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 322 : create_partition_if_empty ()
97 : {
98 322 : if (!ltrans_partitions.length ())
99 2 : new_partition ("empty");
100 322 : }
101 :
102 : /* Free memory used by ltrans partition.
103 : Encoder can be kept to be freed after streaming. */
104 : static void
105 8191 : free_ltrans_partition (ltrans_partition part, bool delete_encoder)
106 : {
107 8191 : if (part->initializers_visited)
108 1452 : delete part->initializers_visited;
109 8191 : if (delete_encoder)
110 1 : lto_symtab_encoder_delete (part->encoder);
111 8191 : free (part);
112 8191 : }
113 :
114 : /* Free memory used by ltrans datastructures. */
115 :
116 : void
117 7815 : free_ltrans_partitions (void)
118 : {
119 7815 : unsigned int idx;
120 7815 : ltrans_partition part;
121 16005 : for (idx = 0; ltrans_partitions.iterate (idx, &part); idx++)
122 8190 : free_ltrans_partition (part, false);
123 7815 : ltrans_partitions.release ();
124 7815 : }
125 :
126 : /* Return true if symbol is already in some partition. */
127 :
128 : static inline bool
129 603279 : symbol_partitioned_p (symtab_node *node)
130 : {
131 603279 : return node->aux;
132 : }
133 :
134 : /* Add references into the partition. */
135 : static void
136 91165 : add_references_to_partition (ltrans_partition part, symtab_node *node)
137 : {
138 91165 : int i;
139 91165 : struct ipa_ref *ref = NULL;
140 :
141 : /* Add all duplicated references to the partition. */
142 282083 : for (i = 0; node->iterate_reference (i, ref); i++)
143 190918 : 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 381628 : else if (is_a <varpool_node *> (ref->referred)
149 174627 : && (dyn_cast <varpool_node *> (ref->referred)
150 174627 : ->ctor_useable_for_folding_p ())
151 9390 : && !lto_symtab_encoder_in_partition_p (part->encoder, ref->referred))
152 : {
153 6011 : if (!part->initializers_visited)
154 1452 : part->initializers_visited = new hash_set<symtab_node *>;
155 6011 : if (!part->initializers_visited->add (ref->referred))
156 3285 : add_references_to_partition (part, ref->referred);
157 : }
158 91165 : }
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 88001 : add_symbol_to_partition_1 (ltrans_partition part, symtab_node *node)
165 : {
166 88001 : enum symbol_partitioning_class c = node->get_partitioning_class ();
167 88001 : struct ipa_ref *ref;
168 88001 : symtab_node *node1;
169 :
170 : /* If NODE is already there, we have nothing to do. */
171 88001 : 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 66458 : if (c == SYMBOL_PARTITION && !DECL_COMDAT (node->decl)
180 154173 : && 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 87880 : gcc_assert (c != SYMBOL_EXTERNAL
186 : && (c == SYMBOL_DUPLICATE || !symbol_partitioned_p (node)));
187 :
188 87880 : part->symbols++;
189 :
190 87880 : lto_set_symtab_encoder_in_partition (part->encoder, node);
191 :
192 87880 : 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 87880 : node->aux = (void *)((size_t)node->aux + 1);
201 :
202 87880 : if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
203 : {
204 64144 : struct cgraph_edge *e;
205 64144 : if (!node->alias && c == SYMBOL_PARTITION)
206 32877 : part->insns += ipa_size_summaries->get (cnode)->size;
207 :
208 : /* Add all inline clones and callees that are duplicated. */
209 318629 : for (e = cnode->callees; e; e = e->next_callee)
210 254485 : if (!e->inline_failed)
211 21242 : add_symbol_to_partition_1 (part, e->callee);
212 233243 : 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 187456 : for (e = cnode->callers; e; e = e->next_caller)
217 123312 : if (e->caller->thunk && !e->caller->inlined_to)
218 13 : add_symbol_to_partition_1 (part, e->caller);
219 : }
220 :
221 87880 : add_references_to_partition (part, node);
222 :
223 : /* Add all aliases associated with the symbol. */
224 :
225 98116 : FOR_EACH_ALIAS (node, ref)
226 10236 : if (!ref->referring->transparent_alias)
227 10231 : 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 allways added in a group. */
242 87880 : 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 585219 : 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 585219 : if (node->transparent_alias)
264 : return node;
265 585211 : if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
266 : {
267 555190 : cnode = cnode->function_symbol ();
268 555190 : if (cnode->inlined_to)
269 78649 : cnode = cnode->inlined_to;
270 555190 : return cnode;
271 : }
272 30021 : else if (varpool_node *vnode = dyn_cast <varpool_node *> (node))
273 30021 : 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 56530 : add_symbol_to_partition (ltrans_partition part, toplevel_node *tnode)
282 : {
283 56530 : symtab_node *node1;
284 56530 : symtab_node* node = dyn_cast <symtab_node*> (tnode);
285 56530 : 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 56457 : gcc_checking_assert (node->get_partitioning_class () == SYMBOL_DUPLICATE
293 : || !symbol_partitioned_p (node));
294 :
295 56559 : 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 56457 : gcc_assert (node->get_partitioning_class () == SYMBOL_DUPLICATE
306 : || DECL_COMDAT (node->decl)
307 : || !symbol_partitioned_p (node));
308 :
309 56457 : 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 226 : 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 449 : 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 5861 : node_into_file_partition (toplevel_node* node,
345 : hash_map<lto_file_decl_data *,
346 : ltrans_partition>& pmap)
347 : {
348 5861 : ltrans_partition partition;
349 :
350 5861 : struct lto_file_decl_data *file_data = node->lto_file_data;
351 :
352 5861 : if (file_data)
353 : {
354 5861 : ltrans_partition *slot = &pmap.get_or_insert (file_data);
355 5861 : if (*slot)
356 : partition = *slot;
357 : else
358 : {
359 543 : partition = new_partition (file_data->file_name);
360 543 : *slot = partition;
361 : }
362 : }
363 : else
364 0 : partition = new_partition ("");
365 :
366 5861 : add_symbol_to_partition (partition, node);
367 5861 : }
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 353 : map_1_to_1 (map1to1_content content)
388 : {
389 353 : symtab_node *node;
390 353 : hash_map<lto_file_decl_data *, ltrans_partition> pmap;
391 :
392 8535 : FOR_EACH_SYMBOL (node)
393 : {
394 8182 : if (node->get_partitioning_class () != SYMBOL_PARTITION
395 8182 : || symbol_partitioned_p (node))
396 1318 : continue;
397 :
398 6864 : if (!(content & map1to1_other_symbols) && !node->must_remain_in_tu_name
399 5755 : && !node->must_remain_in_tu_body && !node->no_reorder)
400 1075 : continue;
401 :
402 5789 : node_into_file_partition (node, pmap);
403 : }
404 :
405 353 : struct asm_node *anode;
406 353 : if (content & map1to1_asm)
407 421 : 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 692 : ltrans_partitions.qsort (cmp_partitions_order);
414 353 : }
415 :
416 : /* Group cgrah nodes by input files. This is used mainly for testing
417 : right now. */
418 :
419 : void
420 303 : lto_1_to_1_map (void)
421 : {
422 303 : map_1_to_1 (map1to1_all);
423 303 : create_partition_if_empty ();
424 303 : }
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 7497 : create_asm_partitions (int64_t target_size)
437 : {
438 7497 : if (!symtab->first_asm_symbol ())
439 7466 : 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 64 : 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 : 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 5610 : for (lsei = lsei_start (encoder); !lsei_end_p (lsei);
463 5581 : lsei_next (&lsei))
464 : {
465 5581 : toplevel_node* tnode = lsei_node (lsei);
466 5581 : if (symtab_node *snode = dyn_cast <symtab_node*> (tnode))
467 : {
468 5551 : if (snode->must_remain_in_tu_name)
469 1 : if (nonrenameable_symbols.add (snode->asm_name ()))
470 0 : goto finish_partition;
471 : }
472 5611 : 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 5581 : 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 249 : FOR_EACH_SYMBOL (node)
509 : {
510 234 : if (node->get_partitioning_class () != SYMBOL_PARTITION
511 234 : || symbol_partitioned_p (node))
512 56 : 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 545628 : node_cmp (const void *pa, const void *pb)
523 : {
524 545628 : const symtab_node *a = *static_cast<const symtab_node * const *> (pa);
525 545628 : const symtab_node *b = *static_cast<const symtab_node * const *> (pb);
526 545628 : return a->order - b->order;
527 : }
528 :
529 : /* Add all symtab nodes from NEXT_NODE to PARTITION in order. */
530 :
531 : static void
532 32087 : add_sorted_nodes (vec<symtab_node *> &next_nodes, ltrans_partition partition)
533 : {
534 32087 : unsigned i;
535 32087 : symtab_node *node;
536 :
537 32087 : next_nodes.qsort (node_cmp);
538 42065 : FOR_EACH_VEC_ELT (next_nodes, i, node)
539 9978 : if (!symbol_partitioned_p (node))
540 4257 : add_symbol_to_partition (partition, node);
541 32087 : }
542 :
543 : /* Return true if we should account reference from N1 to N2 in cost
544 : of partition boundary. */
545 :
546 : bool
547 676493 : account_reference_p (symtab_node *n1, symtab_node *n2)
548 : {
549 676493 : 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 676493 : 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 657961 : if (n1 == n2
560 657849 : || !n2->definition
561 1186736 : || n2->get_partitioning_class () != SYMBOL_PARTITION)
562 129301 : 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 528660 : if (contained_in_symbol (n1)
571 528660 : ->get_partitioning_class () == SYMBOL_EXTERNAL)
572 : 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 : 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 interger 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 (min_partition_size),
991 4 : max_partition_size (max_partition_size)
992 : {
993 4 : gcc_assert (min_partition_size != 0);
994 4 : gcc_assert (max_partition_size != 0);
995 4 : }
996 4 : virtual ~partitioner_base ()
997 : {}
998 :
999 : /* Joins all symbol groups into one finalized partition. */
1000 : void
1001 4 : finalize (partition_set& p)
1002 : {
1003 4 : ltrans_partition joined = NULL;
1004 :
1005 5 : for (ltrans_partition g: p.sym_groups)
1006 1 : joined = join_partitions (joined, g);
1007 :
1008 4 : if (joined)
1009 1 : ltrans_partitions.safe_push (joined);
1010 4 : }
1011 :
1012 : /* Splits all partition_sets. */
1013 : void
1014 0 : split_list (std::vector<partition_set>& ps, uintptr_t state)
1015 : {
1016 0 : for (partition_set& p: ps)
1017 0 : split (p, state);
1018 0 : }
1019 :
1020 : /* Handles common cases:
1021 : too large or small n_partitions, or n_partitions = 1.
1022 : And then calls split_state. */
1023 : void
1024 4 : split (partition_set& p, uintptr_t state)
1025 : {
1026 4 : size_t min_partitions = p.insns / max_partition_size + 1;
1027 4 : size_t max_partitions = p.insns / min_partition_size;
1028 4 : if (!p.data.splitable)
1029 0 : max_partitions = std::min (max_partitions, p.sym_groups.size ());
1030 :
1031 4 : p.n_partitions = std::max (p.n_partitions, min_partitions);
1032 4 : p.n_partitions = std::min (p.n_partitions, max_partitions);
1033 :
1034 4 : if (p.n_partitions <= 1)
1035 4 : return finalize (p);
1036 :
1037 0 : split_state (p, state);
1038 : }
1039 :
1040 : /* State machine for specific partitioner implementation. */
1041 : virtual void
1042 : split_state (partition_set& p, uintptr_t state) = 0;
1043 :
1044 : int64_t min_partition_size, max_partition_size;
1045 : };
1046 :
1047 :
1048 : /* Partitioner combining fixed, over_target, and binary partitionings. */
1049 4 : class partitioner_default: public partitioner_base
1050 : {
1051 : public:
1052 4 : partitioner_default (int64_t min_partition_size, int64_t max_partition_size):
1053 8 : partitioner_base (min_partition_size, max_partition_size)
1054 : {}
1055 :
1056 : private:
1057 : virtual void
1058 0 : split_state (partition_set& p, uintptr_t state)
1059 : {
1060 0 : const uintptr_t FIXED = 0;
1061 0 : const uintptr_t OVER_TARGET = 1;
1062 0 : const uintptr_t BINARY = 2;
1063 :
1064 0 : std::vector<partition_set> ps;
1065 :
1066 0 : switch (state)
1067 : {
1068 0 : case FIXED:
1069 0 : if (p.n_partitions > 64 && p.sym_groups.size () >= 4)
1070 : {
1071 0 : ps = partition_fixed_split (p, 4);
1072 0 : split_list (ps, OVER_TARGET);
1073 0 : break;
1074 : }
1075 :
1076 : /* FALLTHROUGH */
1077 0 : case OVER_TARGET:
1078 0 : ps = partition_over_target_split (p);
1079 0 : if (!ps.empty ())
1080 : {
1081 0 : split_list (ps, BINARY);
1082 0 : break;
1083 : }
1084 :
1085 : /* FALLTHROUGH */
1086 0 : case BINARY:
1087 0 : ps = partition_binary_split (p);
1088 0 : if (!ps.empty ())
1089 : {
1090 0 : split_list (ps, OVER_TARGET);
1091 0 : break;
1092 : }
1093 :
1094 : /* FALLTHROUGH */
1095 0 : default:
1096 0 : finalize (p);
1097 : }
1098 0 : }
1099 : };
1100 :
1101 : /* Group cgraph nodes into equally-sized partitions.
1102 : It tries to keep symbols from single source file together to minimize
1103 : propagation of divergence.
1104 :
1105 : It starts with symbols already grouped by source files. If reasonably
1106 : possible it only either combines several files into one final partition,
1107 : or, if a file is large, split the file into several final partitions.
1108 :
1109 : Intermediate representation is partition_set which contains set of
1110 : groups of symbols (each group corresponding to original source file) and
1111 : number of final partitions this partition_set should split into.
1112 :
1113 : First partition_fixed_split splits partition_set into constant number of
1114 : partition_sets with equal number of symbols groups. If for example there
1115 : are 39 source files, the resulting partition_sets will contain 10, 10,
1116 : 10, and 9 source files. This splitting intentionally ignores estimated
1117 : instruction counts to minimize propagation of divergence.
1118 :
1119 : Second partition_over_target_split separates too large files and splits
1120 : them into individual symbols to be combined back into several smaller
1121 : files in next step.
1122 :
1123 : Third partition_binary_split splits partition_set into two halves until
1124 : it should be split into only one final partition, at which point the
1125 : remaining symbols are joined into one final partition.
1126 : */
1127 :
1128 : void
1129 4 : lto_cache_map (int n_lto_partitions, int max_partition_size)
1130 : {
1131 4 : cgraph_node *node;
1132 4 : int64_t total_size = 0;
1133 14 : FOR_EACH_DEFINED_FUNCTION (node)
1134 10 : if (node->get_partitioning_class () == SYMBOL_PARTITION && !node->alias)
1135 10 : total_size += ipa_size_summaries->get (node)->size;
1136 :
1137 : /* Separates toplevel asm into its own partitions and handles name conflicts.
1138 :
1139 : We could do this directly in cache partitioning without separating asm
1140 : into its own partitions in most cases. */
1141 4 : create_asm_partitions (total_size / n_lto_partitions);
1142 4 : unsigned asm_n = ltrans_partitions.length ();
1143 :
1144 4 : map_1_to_1 (map1to1_symbols);
1145 4 : create_partition_if_empty ();
1146 :
1147 4 : std::vector<ltrans_partition> partitions;
1148 5 : for (unsigned i = asm_n; i < ltrans_partitions.length (); ++i)
1149 : {
1150 1 : ltrans_partition part = ltrans_partitions[i];
1151 1 : partitions.push_back (part);
1152 : }
1153 4 : ltrans_partitions.truncate (asm_n);
1154 :
1155 4 : partitioner_default partitioner = partitioner_default
1156 4 : (param_min_partition_size, max_partition_size);
1157 :
1158 4 : partitioner.apply (partitions, n_lto_partitions);
1159 4 : }
1160 :
1161 : /* Group cgraph nodes into equally-sized partitions.
1162 :
1163 : The partitioning algorithm is simple: nodes are taken in predefined order.
1164 : The order corresponds to the order we want functions to have in the final
1165 : output. In the future this will be given by function reordering pass, but
1166 : at the moment we use the topological order, which is a good approximation.
1167 :
1168 : The goal is to partition this linear order into intervals (partitions) so
1169 : that all the partitions have approximately the same size and the number of
1170 : callgraph or IPA reference edges crossing boundaries is minimal.
1171 :
1172 : This is a lot faster (O(n) in size of callgraph) than algorithms doing
1173 : priority-based graph clustering that are generally O(n^2) and, since
1174 : WHOPR is designed to make things go well across partitions, it leads
1175 : to good results.
1176 :
1177 : We compute the expected size of a partition as:
1178 :
1179 : max (total_size / lto_partitions, min_partition_size)
1180 :
1181 : We use dynamic expected size of partition so small programs are partitioned
1182 : into enough partitions to allow use of multiple CPUs, while large programs
1183 : are not partitioned too much. Creating too many partitions significantly
1184 : increases the streaming overhead.
1185 :
1186 : In the future, we would like to bound the maximal size of partitions so as
1187 : to prevent the LTRANS stage from consuming too much memory. At the moment,
1188 : however, the WPA stage is the most memory intensive for large benchmarks,
1189 : since too many types and declarations are read into memory.
1190 :
1191 : The function implements a simple greedy algorithm. Nodes are being added
1192 : to the current partition until after 3/4 of the expected partition size is
1193 : reached. Past this threshold, we keep track of boundary size (number of
1194 : edges going to other partitions) and continue adding functions until after
1195 : the current partition has grown to twice the expected partition size. Then
1196 : the process is undone to the point where the minimal ratio of boundary size
1197 : and in-partition calls was reached. */
1198 :
1199 : void
1200 7493 : lto_balanced_map (int n_lto_partitions, int max_partition_size)
1201 : {
1202 7493 : int n_varpool_nodes = 0, varpool_pos = 0, best_varpool_pos = 0;
1203 7493 : int best_noreorder_pos = 0;
1204 7493 : auto_vec <cgraph_node *> order (symtab->cgraph_count);
1205 7493 : auto_vec<cgraph_node *> noreorder;
1206 7493 : auto_vec<varpool_node *> varpool_order;
1207 7493 : struct cgraph_node *node;
1208 7493 : int64_t original_total_size, total_size = 0;
1209 7493 : int64_t partition_size;
1210 7493 : ltrans_partition partition;
1211 7493 : int last_visited_node = 0;
1212 7493 : varpool_node *vnode;
1213 7493 : int64_t cost = 0, internal = 0;
1214 7493 : unsigned int best_n_nodes = 0, best_i = 0;
1215 7493 : int64_t best_cost = -1, best_internal = 0, best_size = 0;
1216 7493 : int npartitions;
1217 7493 : int current_order = -1;
1218 7493 : int noreorder_pos = 0;
1219 :
1220 31440 : FOR_EACH_VARIABLE (vnode)
1221 23947 : gcc_assert (!vnode->aux);
1222 :
1223 70531 : FOR_EACH_DEFINED_FUNCTION (node)
1224 63038 : if (node->get_partitioning_class () == SYMBOL_PARTITION)
1225 : {
1226 41896 : if (node->no_reorder)
1227 7468 : noreorder.safe_push (node);
1228 : else
1229 34428 : order.safe_push (node);
1230 41896 : if (!node->alias)
1231 31999 : total_size += ipa_size_summaries->get (node)->size;
1232 : }
1233 :
1234 7493 : original_total_size = total_size;
1235 :
1236 : /* Streaming works best when the source units do not cross partition
1237 : boundaries much. This is because importing function from a source
1238 : unit tends to import a lot of global trees defined there. We should
1239 : get better about minimizing the function bounday, but until that
1240 : things works smoother if we order in source order. */
1241 7493 : order.qsort (tp_first_run_node_cmp);
1242 7493 : noreorder.qsort (node_cmp);
1243 :
1244 7493 : if (dump_file)
1245 : {
1246 0 : for (unsigned i = 0; i < order.length (); i++)
1247 0 : fprintf (dump_file, "Balanced map symbol order:%s:%u\n",
1248 0 : order[i]->dump_name (), order[i]->tp_first_run);
1249 0 : for (unsigned i = 0; i < noreorder.length (); i++)
1250 0 : fprintf (dump_file, "Balanced map symbol no_reorder:%s:%u\n",
1251 0 : noreorder[i]->dump_name (), noreorder[i]->tp_first_run);
1252 : }
1253 :
1254 : /* Collect all variables that should not be reordered. */
1255 31440 : FOR_EACH_VARIABLE (vnode)
1256 23947 : if (vnode->get_partitioning_class () == SYMBOL_PARTITION
1257 23947 : && vnode->no_reorder)
1258 1399 : varpool_order.safe_push (vnode);
1259 7493 : n_varpool_nodes = varpool_order.length ();
1260 7493 : varpool_order.qsort (node_cmp);
1261 :
1262 : /* Compute partition size and create the first partition. */
1263 7493 : if (param_min_partition_size > max_partition_size)
1264 0 : fatal_error (input_location, "min partition size cannot be greater "
1265 : "than max partition size");
1266 :
1267 7493 : partition_size = total_size / n_lto_partitions;
1268 7493 : if (partition_size < param_min_partition_size)
1269 : partition_size = param_min_partition_size;
1270 7493 : npartitions = 1;
1271 7493 : if (dump_file)
1272 0 : fprintf (dump_file, "Total unit size: %" PRId64 ", partition size: %" PRId64 "\n",
1273 : total_size, partition_size);
1274 :
1275 7493 : create_asm_partitions (partition_size);
1276 7493 : if (ltrans_partitions.length ())
1277 : {
1278 : int64_t insns = 0;
1279 : unsigned partitions = ltrans_partitions.length ();
1280 27 : for (unsigned i = 0; i + 1 < partitions ; i++)
1281 0 : insns += ltrans_partitions[i]->insns;
1282 :
1283 27 : total_size -= insns;
1284 27 : if (partition_size)
1285 27 : n_lto_partitions -= insns / partition_size;
1286 27 : if (n_lto_partitions < 1)
1287 : n_lto_partitions = 1;
1288 :
1289 27 : partition_size = total_size / n_lto_partitions;
1290 27 : if (partition_size < param_min_partition_size)
1291 : partition_size = param_min_partition_size;
1292 :
1293 27 : partition = ltrans_partitions[partitions - 1];
1294 : }
1295 : else
1296 7466 : partition = new_partition ("");
1297 :
1298 :
1299 7493 : auto_vec<symtab_node *> next_nodes;
1300 :
1301 41921 : for (unsigned i = 0; i < order.length (); i++)
1302 : {
1303 34430 : if (symbol_partitioned_p (order[i]))
1304 9836 : continue;
1305 :
1306 24594 : current_order = order[i]->order;
1307 :
1308 : /* Output noreorder and varpool in program order first. */
1309 24594 : next_nodes.truncate (0);
1310 24594 : while (varpool_pos < n_varpool_nodes
1311 24639 : && varpool_order[varpool_pos]->order < current_order)
1312 45 : next_nodes.safe_push (varpool_order[varpool_pos++]);
1313 24765 : while (noreorder_pos < (int)noreorder.length ()
1314 25040 : && noreorder[noreorder_pos]->order < current_order)
1315 171 : next_nodes.safe_push (noreorder[noreorder_pos++]);
1316 24594 : add_sorted_nodes (next_nodes, partition);
1317 :
1318 24594 : if (!symbol_partitioned_p (order[i]))
1319 24523 : add_symbol_to_partition (partition, order[i]);
1320 :
1321 :
1322 : /* Once we added a new node to the partition, we also want to add
1323 : all referenced variables unless they was already added into some
1324 : earlier partition.
1325 : add_symbol_to_partition adds possibly multiple nodes and
1326 : variables that are needed to satisfy needs of ORDER[i].
1327 : We remember last visited cgraph and varpool node from last iteration
1328 : of outer loop that allows us to process every new addition.
1329 :
1330 : At the same time we compute size of the boundary into COST. Every
1331 : callgraph or IPA reference edge leaving the partition contributes into
1332 : COST. Every edge inside partition was earlier computed as one leaving
1333 : it and thus we need to subtract it from COST. */
1334 202480 : for (; last_visited_node < lto_symtab_encoder_size (partition->encoder);
1335 : last_visited_node++)
1336 : {
1337 76646 : int j;
1338 76646 : struct ipa_ref *ref = NULL;
1339 76646 : toplevel_node *tnode = lto_symtab_encoder_deref (partition->encoder,
1340 : last_visited_node);
1341 :
1342 76646 : symtab_node* snode = dyn_cast <symtab_node*> (tnode);
1343 76646 : if (!snode)
1344 5 : continue;
1345 :
1346 76641 : if (cgraph_node *node = dyn_cast <cgraph_node *> (snode))
1347 : {
1348 54849 : struct cgraph_edge *edge;
1349 :
1350 54849 : gcc_assert (node->definition || node->weakref);
1351 :
1352 : /* Compute boundary cost of callgraph edges. */
1353 297255 : for (edge = node->callees; edge; edge = edge->next_callee)
1354 : /* Inline edges will always end up local. */
1355 242406 : if (edge->inline_failed
1356 242406 : && account_reference_p (node, edge->callee))
1357 : {
1358 93711 : int edge_cost = edge->frequency ();
1359 93711 : int index;
1360 :
1361 93711 : if (!edge_cost)
1362 : edge_cost = 1;
1363 36329 : gcc_assert (edge_cost > 0);
1364 187422 : index = lto_symtab_encoder_lookup (partition->encoder,
1365 93711 : edge->callee);
1366 93711 : if (index != LCC_NOT_FOUND && index < last_visited_node)
1367 88202 : cost -= edge_cost, internal += edge_cost;
1368 : else
1369 5509 : cost += edge_cost;
1370 : }
1371 169737 : for (edge = node->callers; edge; edge = edge->next_caller)
1372 114888 : if (edge->inline_failed
1373 114888 : && account_reference_p (edge->caller, node))
1374 : {
1375 93745 : int edge_cost = edge->frequency ();
1376 93745 : int index;
1377 :
1378 93745 : gcc_assert (edge->caller->definition);
1379 93745 : if (!edge_cost)
1380 : edge_cost = 1;
1381 36363 : gcc_assert (edge_cost > 0);
1382 93745 : index = lto_symtab_encoder_lookup (partition->encoder,
1383 : edge->caller);
1384 93745 : if (index != LCC_NOT_FOUND && index < last_visited_node)
1385 5497 : cost -= edge_cost, internal += edge_cost;
1386 : else
1387 88248 : cost += edge_cost;
1388 : }
1389 : }
1390 :
1391 : /* Compute boundary cost of IPA REF edges and at the same time look into
1392 : variables referenced from current partition and try to add them. */
1393 516238 : for (j = 0; snode->iterate_reference (j, ref); j++)
1394 181478 : if (!account_reference_p (snode, ref->referred))
1395 : ;
1396 170601 : else if (is_a <varpool_node *> (ref->referred))
1397 : {
1398 168007 : int index;
1399 :
1400 168007 : vnode = dyn_cast <varpool_node *> (ref->referred);
1401 168007 : if (!symbol_partitioned_p (vnode)
1402 21496 : && !vnode->no_reorder
1403 189456 : && vnode->get_partitioning_class () == SYMBOL_PARTITION)
1404 21449 : add_symbol_to_partition (partition, vnode);
1405 168007 : index = lto_symtab_encoder_lookup (partition->encoder,
1406 : vnode);
1407 168007 : if (index != LCC_NOT_FOUND && index < last_visited_node)
1408 106949 : cost--, internal++;
1409 : else
1410 61058 : cost++;
1411 : }
1412 : else
1413 : {
1414 2594 : int index;
1415 :
1416 2594 : node = dyn_cast <cgraph_node *> (ref->referred);
1417 2594 : index = lto_symtab_encoder_lookup (partition->encoder,
1418 : node);
1419 2594 : if (index != LCC_NOT_FOUND && index < last_visited_node)
1420 2259 : cost--, internal++;
1421 : else
1422 335 : cost++;
1423 : }
1424 256596 : for (j = 0; snode->iterate_referring (j, ref); j++)
1425 179955 : if (!account_reference_p (ref->referring, snode))
1426 : ;
1427 170603 : else if (is_a <varpool_node *> (ref->referring))
1428 : {
1429 3249 : int index;
1430 :
1431 3249 : vnode = dyn_cast <varpool_node *> (ref->referring);
1432 3249 : gcc_assert (vnode->definition);
1433 : /* It is better to couple variables with their users,
1434 : because it allows them to be removed. Coupling
1435 : with objects they refer to only helps to reduce
1436 : number of symbols promoted to hidden. */
1437 3249 : if (!symbol_partitioned_p (vnode)
1438 674 : && !vnode->no_reorder
1439 635 : && !vnode->can_remove_if_no_refs_p ()
1440 3271 : && vnode->get_partitioning_class () == SYMBOL_PARTITION)
1441 22 : add_symbol_to_partition (partition, vnode);
1442 3249 : index = lto_symtab_encoder_lookup (partition->encoder,
1443 : vnode);
1444 3249 : if (index != LCC_NOT_FOUND && index < last_visited_node)
1445 2496 : cost--, internal++;
1446 : else
1447 753 : cost++;
1448 : }
1449 : else
1450 : {
1451 167354 : int index;
1452 :
1453 167354 : node = dyn_cast <cgraph_node *> (ref->referring);
1454 167354 : gcc_assert (node->definition);
1455 167354 : index = lto_symtab_encoder_lookup (partition->encoder,
1456 : node);
1457 167354 : if (index != LCC_NOT_FOUND && index < last_visited_node)
1458 58855 : cost--, internal++;
1459 : else
1460 108499 : cost++;
1461 : }
1462 : }
1463 :
1464 24594 : gcc_assert (cost >= 0 && internal >= 0);
1465 :
1466 : /* If the partition is large enough, start looking for smallest boundary cost.
1467 : If partition still seems too small (less than 7/8 of target weight) accept
1468 : any cost. If partition has right size, optimize for highest internal/cost.
1469 : Later we stop building partition if its size is 9/8 of the target wight. */
1470 24594 : if (partition->insns < partition_size * 7 / 8
1471 43 : || best_cost == -1
1472 24635 : || (!cost
1473 40 : || ((sreal)best_internal * (sreal) cost
1474 80 : < ((sreal) internal * (sreal)best_cost))))
1475 : {
1476 24583 : best_cost = cost;
1477 24583 : best_internal = internal;
1478 24583 : best_size = partition->insns;
1479 24583 : best_i = i;
1480 24583 : best_n_nodes = lto_symtab_encoder_size (partition->encoder);
1481 : best_varpool_pos = varpool_pos;
1482 : best_noreorder_pos = noreorder_pos;
1483 : }
1484 24594 : if (dump_file)
1485 0 : fprintf (dump_file, "Step %i: added %s, size %i, "
1486 : "cost %" PRId64 "/%" PRId64 " "
1487 : "best %" PRId64 "/%" PRId64", step %i\n", i,
1488 0 : order[i]->dump_name (),
1489 : partition->insns, cost, internal,
1490 : best_cost, best_internal, best_i);
1491 : /* Partition is too large, unwind into step when best cost was reached and
1492 : start new partition. */
1493 24594 : if (partition->insns > 9 * partition_size / 8
1494 24590 : || partition->insns > max_partition_size)
1495 : {
1496 4 : if (best_i != i)
1497 : {
1498 1 : if (dump_file)
1499 0 : fprintf (dump_file, "Unwinding %i insertions to step %i\n",
1500 : i - best_i, best_i);
1501 1 : undo_partition (partition, best_n_nodes);
1502 1 : varpool_pos = best_varpool_pos;
1503 1 : noreorder_pos = best_noreorder_pos;
1504 : }
1505 4 : gcc_assert (best_size == partition->insns);
1506 4 : i = best_i;
1507 4 : if (dump_file)
1508 0 : fprintf (dump_file,
1509 : "Partition insns: %i (want %" PRId64 ")\n",
1510 : partition->insns, partition_size);
1511 : /* When we are finished, avoid creating empty partition. */
1512 4 : while (i < order.length () - 1 && symbol_partitioned_p (order[i + 1]))
1513 : i++;
1514 4 : if (i == order.length () - 1)
1515 : break;
1516 2 : total_size -= partition->insns;
1517 2 : partition = new_partition ("");
1518 2 : last_visited_node = 0;
1519 2 : cost = 0;
1520 :
1521 2 : if (dump_file)
1522 0 : fprintf (dump_file, "New partition\n");
1523 2 : best_n_nodes = 0;
1524 2 : best_cost = -1;
1525 :
1526 : /* Since the size of partitions is just approximate, update the size after
1527 : we finished current one. */
1528 2 : if (npartitions < n_lto_partitions)
1529 2 : partition_size = total_size / (n_lto_partitions - npartitions);
1530 : else
1531 : /* Watch for overflow. */
1532 : partition_size = INT_MAX / 16;
1533 :
1534 2 : if (dump_file)
1535 0 : fprintf (dump_file,
1536 : "Total size: %" PRId64 " partition_size: %" PRId64 "\n",
1537 : total_size, partition_size);
1538 2 : if (partition_size < param_min_partition_size)
1539 : partition_size = param_min_partition_size;
1540 2 : npartitions ++;
1541 : }
1542 : }
1543 :
1544 7493 : next_nodes.truncate (0);
1545 :
1546 : /* Varables that are not reachable from the code go into last partition. */
1547 31440 : FOR_EACH_VARIABLE (vnode)
1548 23947 : if (vnode->get_partitioning_class () == SYMBOL_PARTITION
1549 23947 : && !symbol_partitioned_p (vnode))
1550 1111 : next_nodes.safe_push (vnode);
1551 :
1552 : /* Output remaining ordered symbols. */
1553 8847 : while (varpool_pos < n_varpool_nodes)
1554 1354 : next_nodes.safe_push (varpool_order[varpool_pos++]);
1555 23769 : while (noreorder_pos < (int)noreorder.length ())
1556 7297 : next_nodes.safe_push (noreorder[noreorder_pos++]);
1557 : /* For one partition the cost of boundary should be 0 unless we added final
1558 : symbols here (these are not accounted) or we have accounting bug. */
1559 7493 : gcc_assert (next_nodes.length () || ltrans_partitions.length () != 1
1560 : || !best_cost || best_cost == -1);
1561 7493 : add_sorted_nodes (next_nodes, partition);
1562 :
1563 7493 : if (dump_file)
1564 : {
1565 0 : fprintf (dump_file, "\nPartition sizes:\n");
1566 0 : unsigned partitions = ltrans_partitions.length ();
1567 :
1568 0 : for (unsigned i = 0; i < partitions ; i++)
1569 : {
1570 0 : ltrans_partition p = ltrans_partitions[i];
1571 0 : fprintf (dump_file, "partition %d contains %d (%2.2f%%)"
1572 : " symbols and %d (%2.2f%%) insns\n", i, p->symbols,
1573 0 : 100.0 * p->symbols / order.length (), p->insns,
1574 0 : 100.0 * p->insns / original_total_size);
1575 : }
1576 :
1577 0 : fprintf (dump_file, "\n");
1578 : }
1579 7493 : }
1580 :
1581 : /* Add all references of NODE into PARTITION. */
1582 :
1583 : static void
1584 0 : add_node_references_to_partition (ltrans_partition partition, symtab_node *node)
1585 : {
1586 0 : struct ipa_ref *ref = NULL;
1587 0 : varpool_node *vnode;
1588 0 : for (int j = 0; node->iterate_reference (j, ref); j++)
1589 0 : if (is_a <varpool_node *> (ref->referred))
1590 : {
1591 0 : vnode = dyn_cast <varpool_node *> (ref->referred);
1592 0 : if (!symbol_partitioned_p (vnode)
1593 0 : && !vnode->no_reorder
1594 0 : && vnode->get_partitioning_class () == SYMBOL_PARTITION)
1595 : {
1596 0 : add_symbol_to_partition (partition, vnode);
1597 0 : if (dump_file)
1598 0 : fprintf (dump_file, "Varpool Node: %s\n", vnode->dump_asm_name ());
1599 0 : add_node_references_to_partition (partition, vnode);
1600 : }
1601 : }
1602 :
1603 0 : for (int j = 0; node->iterate_referring (j, ref); j++)
1604 0 : if (is_a <varpool_node *> (ref->referring))
1605 : {
1606 0 : vnode = dyn_cast <varpool_node *> (ref->referring);
1607 0 : gcc_assert (vnode->definition);
1608 0 : if (!symbol_partitioned_p (vnode)
1609 0 : && !vnode->no_reorder
1610 0 : && !vnode->can_remove_if_no_refs_p ()
1611 0 : && vnode->get_partitioning_class () == SYMBOL_PARTITION)
1612 : {
1613 0 : add_symbol_to_partition (partition, vnode);
1614 0 : if (dump_file)
1615 0 : fprintf (dump_file, "Varpool Node: %s\n", vnode->dump_asm_name ());
1616 0 : add_node_references_to_partition (partition, vnode);
1617 : }
1618 : }
1619 0 : if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
1620 : {
1621 0 : struct cgraph_edge *e;
1622 :
1623 : /* Add all inline clones and callees that are duplicated. */
1624 0 : for (e = cnode->callees; e; e = e->next_callee)
1625 0 : if (e->callee->get_partitioning_class () == SYMBOL_DUPLICATE)
1626 0 : add_node_references_to_partition (partition, e->callee);
1627 :
1628 : /* Add all thunks associated with the function. */
1629 0 : for (e = cnode->callers; e; e = e->next_caller)
1630 0 : if (e->caller->thunk && !e->caller->inlined_to)
1631 0 : add_node_references_to_partition (partition, e->caller);
1632 : }
1633 :
1634 0 : }
1635 :
1636 : /* Create and return the created partition of name NAME. */
1637 :
1638 : static ltrans_partition
1639 0 : create_partition (int &npartitions, const char *name)
1640 : {
1641 0 : npartitions++;
1642 0 : return new_partition (name);
1643 : }
1644 :
1645 : /* Partitioning for code locality.
1646 : The partitioning plan (and prerequisite cloning) will have been done by the
1647 : IPA locality cloning pass. This function just implements that plan by
1648 : assigning those partitions to ltrans_parititions. */
1649 :
1650 : void
1651 0 : lto_locality_map (int max_partition_size)
1652 : {
1653 0 : symtab_node *snode;
1654 0 : int npartitions = 0;
1655 :
1656 0 : auto_vec<varpool_node *> varpool_order;
1657 0 : struct cgraph_node *node;
1658 :
1659 0 : if (locality_partitions.length () == 0)
1660 : {
1661 0 : if (dump_file)
1662 : {
1663 0 : fprintf (dump_file, "Locality partition: falling back to balanced "
1664 : "model\n");
1665 : }
1666 0 : lto_balanced_map (param_lto_partitions, param_max_partition_size);
1667 0 : return;
1668 : }
1669 0 : ltrans_partition partition = nullptr;
1670 0 : for (auto part : locality_partitions)
1671 : {
1672 0 : partition = create_partition (npartitions, "");
1673 0 : for (unsigned j = 0; j < part->nodes.length (); j++)
1674 : {
1675 0 : node = part->nodes[j];
1676 0 : if (symbol_partitioned_p (node))
1677 0 : continue;
1678 :
1679 0 : add_symbol_to_partition (partition, node);
1680 0 : add_node_references_to_partition (partition, node);
1681 : }
1682 : }
1683 :
1684 0 : int64_t partition_size = max_partition_size;
1685 : /* All other unpartitioned symbols. */
1686 0 : FOR_EACH_SYMBOL (snode)
1687 : {
1688 0 : if (snode->get_partitioning_class () == SYMBOL_PARTITION
1689 0 : && !symbol_partitioned_p (snode))
1690 : {
1691 0 : if (partition->insns > partition_size)
1692 0 : partition = create_partition (npartitions, "");
1693 :
1694 0 : add_symbol_to_partition (partition, snode);
1695 0 : if (dump_file)
1696 0 : fprintf (dump_file, "Un-ordered Node: %s\n", snode->dump_asm_name ());
1697 : }
1698 : }
1699 0 : }
1700 :
1701 : /* Return true if we must not change the name of the NODE. The name as
1702 : extracted from the corresponding decl should be passed in NAME. */
1703 :
1704 : static bool
1705 167656 : must_not_rename (symtab_node *node, const char *name)
1706 : {
1707 : /* Our renaming machinery do not handle more than one change of assembler name.
1708 : We should not need more than one anyway. */
1709 167656 : if (node->lto_file_data
1710 167656 : && lto_get_decl_name_mapping (node->lto_file_data, name) != name)
1711 : {
1712 217 : if (dump_file)
1713 0 : fprintf (dump_file,
1714 : "Not privatizing symbol name: %s. It privatized already.\n",
1715 : name);
1716 217 : return true;
1717 : }
1718 : /* Avoid mangling of already mangled clones.
1719 : ??? should have a flag whether a symbol has a 'private' name already,
1720 : since we produce some symbols like that i.e. for global constructors
1721 : that are not really clones.
1722 : ??? it is what unique_name means. We only need to set it when doing
1723 : private symbols. */
1724 167439 : if (node->unique_name)
1725 : {
1726 43273 : if (dump_file)
1727 0 : fprintf (dump_file,
1728 : "Not privatizing symbol name: %s. Has unique name.\n",
1729 : name);
1730 43273 : return true;
1731 : }
1732 : return false;
1733 : }
1734 :
1735 : /* If we are an offload compiler, we may have to rewrite symbols to be
1736 : valid on this target. Return either PTR or a modified version of it. */
1737 :
1738 : static const char *
1739 0 : maybe_rewrite_identifier (const char *ptr)
1740 : {
1741 : #if defined ACCEL_COMPILER && (defined NO_DOT_IN_LABEL || defined NO_DOLLAR_IN_LABEL)
1742 : #ifndef NO_DOT_IN_LABEL
1743 : char valid = '.';
1744 : const char reject[] = "$";
1745 : #elif !defined NO_DOLLAR_IN_LABEL
1746 : char valid = '$';
1747 : const char reject[] = ".";
1748 : #else
1749 : char valid = '_';
1750 : const char reject[] = ".$";
1751 : #endif
1752 :
1753 : char *copy = NULL;
1754 : const char *match = ptr;
1755 : for (;;)
1756 : {
1757 : size_t off = strcspn (match, reject);
1758 : if (match[off] == '\0')
1759 : break;
1760 : if (copy == NULL)
1761 : {
1762 : copy = xstrdup (ptr);
1763 : match = copy;
1764 : }
1765 : copy[off] = valid;
1766 : }
1767 : if (copy)
1768 : {
1769 : match = IDENTIFIER_POINTER (get_identifier (copy));
1770 : free (copy);
1771 : }
1772 : return match;
1773 : #else
1774 0 : return ptr;
1775 : #endif
1776 : }
1777 :
1778 : /* Ensure that the symbol in NODE is valid for the target, and if not,
1779 : rewrite it. */
1780 :
1781 : static void
1782 167262 : validize_symbol_for_target (symtab_node *node)
1783 : {
1784 167262 : tree decl = node->decl;
1785 167262 : const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
1786 :
1787 167262 : if (must_not_rename (node, name))
1788 : return;
1789 :
1790 : const char *name2 = maybe_rewrite_identifier (name);
1791 : if (name2 != name)
1792 : {
1793 : symtab->change_decl_assembler_name (decl, get_identifier (name2));
1794 : if (node->lto_file_data)
1795 : lto_record_renamed_decl (node->lto_file_data, name, name2);
1796 : }
1797 : }
1798 :
1799 : /* Maps symbol names to unique lto clone counters. */
1800 : static hash_map<const char *, unsigned> *lto_clone_numbers;
1801 :
1802 : /* Helper for privatize_symbol_name. Mangle NODE symbol name
1803 : represented by DECL. */
1804 :
1805 : static bool
1806 394 : privatize_symbol_name_1 (symtab_node *node, tree decl)
1807 : {
1808 394 : const char *name0 = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
1809 :
1810 394 : if (must_not_rename (node, name0))
1811 : return false;
1812 :
1813 329 : const char *name = maybe_rewrite_identifier (name0);
1814 329 : unsigned &clone_number = lto_clone_numbers->get_or_insert (name);
1815 329 : symtab->change_decl_assembler_name (decl,
1816 : clone_function_name (
1817 329 : name, "lto_priv", clone_number));
1818 329 : clone_number++;
1819 :
1820 329 : if (node->lto_file_data)
1821 658 : lto_record_renamed_decl (node->lto_file_data, name0,
1822 329 : IDENTIFIER_POINTER
1823 : (DECL_ASSEMBLER_NAME (decl)));
1824 :
1825 329 : if (dump_file)
1826 0 : fprintf (dump_file,
1827 : "Privatizing symbol name: %s -> %s\n",
1828 0 : name, IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl)));
1829 :
1830 : return true;
1831 : }
1832 :
1833 : /* Mangle NODE symbol name into a local name.
1834 : This is necessary to do
1835 : 1) if two or more static vars of same assembler name
1836 : are merged into single ltrans unit.
1837 : 2) if previously static var was promoted hidden to avoid possible conflict
1838 : with symbols defined out of the LTO world. */
1839 :
1840 : static bool
1841 394 : privatize_symbol_name (symtab_node *node)
1842 : {
1843 0 : if (!privatize_symbol_name_1 (node, node->decl))
1844 : return false;
1845 :
1846 : return true;
1847 : }
1848 :
1849 : /* Promote variable VNODE to be static. */
1850 :
1851 : static void
1852 232 : promote_symbol (symtab_node *node)
1853 : {
1854 : /* We already promoted ... */
1855 232 : if (DECL_VISIBILITY (node->decl) == VISIBILITY_HIDDEN
1856 7 : && DECL_VISIBILITY_SPECIFIED (node->decl)
1857 239 : && TREE_PUBLIC (node->decl))
1858 : {
1859 7 : validize_symbol_for_target (node);
1860 7 : return;
1861 : }
1862 :
1863 225 : gcc_checking_assert (!TREE_PUBLIC (node->decl)
1864 : && !DECL_EXTERNAL (node->decl));
1865 : /* Be sure that newly public symbol does not conflict with anything already
1866 : defined by the non-LTO part. */
1867 225 : privatize_symbol_name (node);
1868 225 : TREE_PUBLIC (node->decl) = 1;
1869 : /* After privatization the node should not conflict with any other symbol,
1870 : so it is prevailing. This is important to keep binds_to_current_def_p
1871 : to work across partitions. */
1872 225 : node->resolution = LDPR_PREVAILING_DEF_IRONLY;
1873 225 : node->semantic_interposition = false;
1874 225 : DECL_VISIBILITY (node->decl) = VISIBILITY_HIDDEN;
1875 225 : DECL_VISIBILITY_SPECIFIED (node->decl) = true;
1876 225 : if (dump_file)
1877 0 : fprintf (dump_file,
1878 : "Promoting as hidden: %s (%s)\n", node->dump_name (),
1879 0 : IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
1880 :
1881 : /* Promoting a symbol also promotes all transparent aliases with exception
1882 : of weakref where the visibility flags are always wrong and set to
1883 : !PUBLIC. */
1884 : ipa_ref *ref;
1885 232 : for (unsigned i = 0; node->iterate_direct_aliases (i, ref); i++)
1886 : {
1887 7 : struct symtab_node *alias = ref->referring;
1888 7 : if (alias->transparent_alias && !alias->weakref)
1889 : {
1890 0 : TREE_PUBLIC (alias->decl) = 1;
1891 0 : DECL_VISIBILITY (alias->decl) = VISIBILITY_HIDDEN;
1892 0 : DECL_VISIBILITY_SPECIFIED (alias->decl) = true;
1893 0 : if (dump_file)
1894 0 : fprintf (dump_file,
1895 : "Promoting alias as hidden: %s\n",
1896 0 : IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
1897 : }
1898 7 : gcc_assert (!alias->weakref || TREE_PUBLIC (alias->decl));
1899 : }
1900 : }
1901 :
1902 : /* Return true if NODE needs named section even if it won't land in
1903 : the partition symbol table.
1904 :
1905 : FIXME: we should really not use named sections for master clones. */
1906 :
1907 : static bool
1908 108769 : may_need_named_section_p (lto_symtab_encoder_t encoder, symtab_node *node)
1909 : {
1910 214658 : struct cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1911 : /* We do not need to handle variables since we never clone them. */
1912 100204 : if (!cnode)
1913 : return false;
1914 : /* Only master clones will have bodies streamed. */
1915 100204 : if (cnode->clone_of)
1916 : return false;
1917 67665 : if (node->real_symbol_p ())
1918 : return false;
1919 2880 : return (!encoder
1920 2880 : || (lto_symtab_encoder_lookup (encoder, node) != LCC_NOT_FOUND
1921 2868 : && lto_symtab_encoder_encode_body_p (encoder,
1922 : cnode)));
1923 : }
1924 :
1925 : /* If NODE represents a static variable. See if there are other variables
1926 : of the same name in partition ENCODER (or in whole compilation unit if
1927 : ENCODER is NULL) and if so, mangle the statics. Always mangle all
1928 : conflicting statics, so we reduce changes of silently miscompiling
1929 : asm statements referring to them by symbol name. */
1930 :
1931 : static void
1932 167487 : rename_statics (lto_symtab_encoder_t encoder, symtab_node *node)
1933 : {
1934 167487 : tree decl = node->decl;
1935 167487 : symtab_node *s;
1936 167487 : tree name = DECL_ASSEMBLER_NAME (decl);
1937 :
1938 : /* See if this is static symbol. */
1939 49640 : if (((node->externally_visible && !node->weakref)
1940 : /* FIXME: externally_visible is somewhat illogically not set for
1941 : external symbols (i.e. those not defined). Remove this test
1942 : once this is fixed. */
1943 117847 : || DECL_EXTERNAL (node->decl)
1944 94101 : || !node->real_symbol_p ())
1945 262096 : && !may_need_named_section_p (encoder, node))
1946 : return;
1947 :
1948 : /* Now walk symbols sharing the same name and see if there are any conflicts.
1949 : (all types of symbols counts here, since we cannot have static of the
1950 : same name as external or public symbol.) */
1951 74321 : for (s = symtab_node::get_for_asmname (name);
1952 161338 : s; s = s->next_sharing_asm_name)
1953 101263 : if ((s->real_symbol_p () || may_need_named_section_p (encoder, s))
1954 74388 : && s->decl != node->decl
1955 87229 : && (!encoder
1956 76 : || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND))
1957 : break;
1958 :
1959 : /* OK, no confict, so we have nothing to do. */
1960 74321 : if (!s)
1961 : return;
1962 :
1963 92 : if (dump_file)
1964 0 : fprintf (dump_file,
1965 : "Renaming statics with asm name: %s\n", node->dump_name ());
1966 :
1967 : /* Assign every symbol in the set that shares the same ASM name an unique
1968 : mangled name. */
1969 285 : for (s = symtab_node::get_for_asmname (name); s;)
1970 16 : if ((!s->externally_visible || s->weakref)
1971 : /* Transparent aliases having same name as target are renamed at a
1972 : time their target gets new name. Transparent aliases that use
1973 : separate assembler name require the name to be unique. */
1974 177 : && (!s->transparent_alias || !s->definition || s->weakref
1975 6 : || !symbol_table::assembler_names_equal_p
1976 6 : (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (s->decl)),
1977 6 : IDENTIFIER_POINTER
1978 : (DECL_ASSEMBLER_NAME (s->get_alias_target()->decl))))
1979 171 : && ((s->real_symbol_p ()
1980 167 : && !DECL_EXTERNAL (s->decl)
1981 165 : && !TREE_PUBLIC (s->decl))
1982 6 : || may_need_named_section_p (encoder, s))
1983 362 : && (!encoder
1984 85 : || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND))
1985 : {
1986 169 : if (privatize_symbol_name (s))
1987 : /* Re-start from beginning since we do not know how many
1988 : symbols changed a name. */
1989 164 : s = symtab_node::get_for_asmname (name);
1990 5 : else s = s->next_sharing_asm_name;
1991 : }
1992 24 : else s = s->next_sharing_asm_name;
1993 : }
1994 :
1995 : /* Find out all static decls that need to be promoted to global because
1996 : of cross file sharing. This function must be run in the WPA mode after
1997 : all inlinees are added. */
1998 :
1999 : void
2000 7815 : lto_promote_cross_file_statics (void)
2001 : {
2002 7815 : unsigned i, n_sets;
2003 :
2004 7815 : gcc_assert (flag_wpa);
2005 :
2006 7815 : lto_stream_offload_p = false;
2007 7815 : select_what_to_stream ();
2008 :
2009 : /* First compute boundaries. */
2010 7815 : n_sets = ltrans_partitions.length ();
2011 16005 : for (i = 0; i < n_sets; i++)
2012 : {
2013 8190 : ltrans_partition part
2014 8190 : = ltrans_partitions[i];
2015 8190 : if (dump_file)
2016 0 : fprintf (dump_file, "lto_promote_cross_file_statics for part %s %p\n",
2017 0 : part->name, (void *)part->encoder);
2018 8190 : part->encoder = compute_ltrans_boundary (part->encoder);
2019 8190 : if (dump_file)
2020 0 : fprintf (dump_file, "new encoder %p\n", (void *)part->encoder);
2021 : }
2022 :
2023 7815 : lto_clone_numbers = new hash_map<const char *, unsigned>;
2024 :
2025 : /* Look at boundaries and promote symbols as needed. */
2026 16005 : for (i = 0; i < n_sets; i++)
2027 : {
2028 8190 : lto_symtab_encoder_iterator lsei;
2029 8190 : lto_symtab_encoder_t encoder = ltrans_partitions[i]->encoder;
2030 :
2031 115981 : for (lsei = lsei_start (encoder); !lsei_end_p (lsei);
2032 107791 : lsei_next (&lsei))
2033 : {
2034 107791 : toplevel_node *tnode = lsei_node (lsei);
2035 107791 : symtab_node *node = dyn_cast <symtab_node*> (tnode);
2036 107791 : if (!node)
2037 72 : continue;
2038 :
2039 : /* If symbol is static, rename it if its assembler name
2040 : clashes with anything else in this unit. */
2041 107719 : rename_statics (encoder, node);
2042 :
2043 : /* No need to promote if symbol already is externally visible ... */
2044 215206 : if (node->externally_visible
2045 : /* ... or if it is part of current partition ... */
2046 96463 : || lto_symtab_encoder_in_partition_p (encoder, node)
2047 : /* ... or if we do not partition it. This mean that it will
2048 : appear in every partition referencing it. */
2049 127542 : || node->get_partitioning_class () != SYMBOL_PARTITION)
2050 : {
2051 107487 : validize_symbol_for_target (node);
2052 107487 : continue;
2053 : }
2054 :
2055 232 : promote_symbol (node);
2056 : }
2057 : }
2058 15630 : delete lto_clone_numbers;
2059 7815 : }
2060 :
2061 : /* Rename statics in the whole unit in the case that
2062 : we do -flto-partition=none. */
2063 :
2064 : void
2065 4396 : lto_promote_statics_nonwpa (void)
2066 : {
2067 4396 : symtab_node *node;
2068 :
2069 4396 : lto_clone_numbers = new hash_map<const char *, unsigned>;
2070 64164 : FOR_EACH_SYMBOL (node)
2071 : {
2072 59768 : rename_statics (NULL, node);
2073 59768 : validize_symbol_for_target (node);
2074 : }
2075 8792 : delete lto_clone_numbers;
2076 4396 : }
|
