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