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