1 /* LTO partitioning logic routines.
2 Copyright (C) 2009-2020 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
22 #include "coretypes.h"
25 #include "basic-block.h"
28 #include "alloc-pool.h"
29 #include "stringpool.h"
31 #include "lto-streamer.h"
32 #include "symbol-summary.h"
35 #include "ipa-fnsummary.h"
36 #include "lto-partition.h"
39 vec
<ltrans_partition
> ltrans_partitions
;
41 static void add_symbol_to_partition (ltrans_partition part
, symtab_node
*node
);
44 /* Helper for qsort; compare partitions and return one with smaller order. */
47 cmp_partitions_order (const void *a
, const void *b
)
49 const struct ltrans_partition_def
*pa
50 = *(struct ltrans_partition_def
*const *)a
;
51 const struct ltrans_partition_def
*pb
52 = *(struct ltrans_partition_def
*const *)b
;
53 int ordera
= -1, orderb
= -1;
55 if (lto_symtab_encoder_size (pa
->encoder
))
56 ordera
= lto_symtab_encoder_deref (pa
->encoder
, 0)->order
;
57 if (lto_symtab_encoder_size (pb
->encoder
))
58 orderb
= lto_symtab_encoder_deref (pb
->encoder
, 0)->order
;
59 return orderb
- ordera
;
62 /* Create new partition with name NAME. */
64 static ltrans_partition
65 new_partition (const char *name
)
67 ltrans_partition part
= XCNEW (struct ltrans_partition_def
);
68 part
->encoder
= lto_symtab_encoder_new (false);
72 ltrans_partitions
.safe_push (part
);
76 /* Free memory used by ltrans datastructures. */
79 free_ltrans_partitions (void)
82 ltrans_partition part
;
83 for (idx
= 0; ltrans_partitions
.iterate (idx
, &part
); idx
++)
85 if (part
->initializers_visited
)
86 delete part
->initializers_visited
;
87 /* Symtab encoder is freed after streaming. */
90 ltrans_partitions
.release ();
93 /* Return true if symbol is already in some partition. */
96 symbol_partitioned_p (symtab_node
*node
)
101 /* Add references into the partition. */
103 add_references_to_partition (ltrans_partition part
, symtab_node
*node
)
106 struct ipa_ref
*ref
= NULL
;
108 /* Add all duplicated references to the partition. */
109 for (i
= 0; node
->iterate_reference (i
, ref
); i
++)
110 if (ref
->referred
->get_partitioning_class () == SYMBOL_DUPLICATE
)
111 add_symbol_to_partition (part
, ref
->referred
);
112 /* References to a readonly variable may be constant foled into its value.
113 Recursively look into the initializers of the constant variable and add
115 else if (is_a
<varpool_node
*> (ref
->referred
)
116 && (dyn_cast
<varpool_node
*> (ref
->referred
)
117 ->ctor_useable_for_folding_p ())
118 && !lto_symtab_encoder_in_partition_p (part
->encoder
, ref
->referred
))
120 if (!part
->initializers_visited
)
121 part
->initializers_visited
= new hash_set
<symtab_node
*>;
122 if (!part
->initializers_visited
->add (ref
->referred
))
123 add_references_to_partition (part
, ref
->referred
);
127 /* Helper function for add_symbol_to_partition doing the actual dirty work
128 of adding NODE to PART. */
131 add_symbol_to_partition_1 (ltrans_partition part
, symtab_node
*node
)
133 enum symbol_partitioning_class c
= node
->get_partitioning_class ();
137 /* If NODE is already there, we have nothing to do. */
138 if (lto_symtab_encoder_in_partition_p (part
->encoder
, node
))
141 /* non-duplicated aliases or tunks of a duplicated symbol needs to be output
144 Be lax about comdats; they may or may not be duplicated and we may
145 end up in need to duplicate keyed comdat because it has unkeyed alias. */
146 if (c
== SYMBOL_PARTITION
&& !DECL_COMDAT (node
->decl
)
147 && symbol_partitioned_p (node
))
150 /* Be sure that we never try to duplicate partitioned symbol
151 or add external symbol. */
152 gcc_assert (c
!= SYMBOL_EXTERNAL
153 && (c
== SYMBOL_DUPLICATE
|| !symbol_partitioned_p (node
)));
157 lto_set_symtab_encoder_in_partition (part
->encoder
, node
);
159 if (symbol_partitioned_p (node
))
161 node
->in_other_partition
= 1;
164 "Symbol node %s now used in multiple partitions\n",
167 node
->aux
= (void *)((size_t)node
->aux
+ 1);
169 if (cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
))
171 struct cgraph_edge
*e
;
172 if (!node
->alias
&& c
== SYMBOL_PARTITION
)
173 part
->insns
+= ipa_size_summaries
->get (cnode
)->size
;
175 /* Add all inline clones and callees that are duplicated. */
176 for (e
= cnode
->callees
; e
; e
= e
->next_callee
)
177 if (!e
->inline_failed
)
178 add_symbol_to_partition_1 (part
, e
->callee
);
179 else if (e
->callee
->get_partitioning_class () == SYMBOL_DUPLICATE
)
180 add_symbol_to_partition (part
, e
->callee
);
182 /* Add all thunks associated with the function. */
183 for (e
= cnode
->callers
; e
; e
= e
->next_caller
)
184 if (e
->caller
->thunk
.thunk_p
&& !e
->caller
->inlined_to
)
185 add_symbol_to_partition_1 (part
, e
->caller
);
188 add_references_to_partition (part
, node
);
190 /* Add all aliases associated with the symbol. */
192 FOR_EACH_ALIAS (node
, ref
)
193 if (!ref
->referring
->transparent_alias
)
194 add_symbol_to_partition_1 (part
, ref
->referring
);
197 struct ipa_ref
*ref2
;
198 /* We do not need to add transparent aliases if they are not used.
199 However we must add aliases of transparent aliases if they exist. */
200 FOR_EACH_ALIAS (ref
->referring
, ref2
)
202 /* Nested transparent aliases are not permitted. */
203 gcc_checking_assert (!ref2
->referring
->transparent_alias
);
204 add_symbol_to_partition_1 (part
, ref2
->referring
);
208 /* Ensure that SAME_COMDAT_GROUP lists all allways added in a group. */
209 if (node
->same_comdat_group
)
210 for (node1
= node
->same_comdat_group
;
211 node1
!= node
; node1
= node1
->same_comdat_group
)
214 bool added
= add_symbol_to_partition_1 (part
, node1
);
220 /* If symbol NODE is really part of other symbol's definition (i.e. it is
221 internal label, thunk, alias or so), return the outer symbol.
222 When add_symbol_to_partition_1 is called on the outer symbol it must
223 eventually add NODE, too. */
225 contained_in_symbol (symtab_node
*node
)
227 /* There is no need to consider transparent aliases to be part of the
228 definition: they are only useful insite the partition they are output
229 and thus we will always see an explicit reference to it. */
230 if (node
->transparent_alias
)
232 if (cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
))
234 cnode
= cnode
->function_symbol ();
235 if (cnode
->inlined_to
)
236 cnode
= cnode
->inlined_to
;
239 else if (varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
))
240 return vnode
->ultimate_alias_target ();
244 /* Add symbol NODE to partition. When definition of NODE is part
245 of other symbol definition, add the other symbol, too. */
248 add_symbol_to_partition (ltrans_partition part
, symtab_node
*node
)
252 /* Verify that we do not try to duplicate something that cannot be. */
253 gcc_checking_assert (node
->get_partitioning_class () == SYMBOL_DUPLICATE
254 || !symbol_partitioned_p (node
));
256 while ((node1
= contained_in_symbol (node
)) != node
)
259 /* If we have duplicated symbol contained in something we cannot duplicate,
260 we are very badly screwed. The other way is possible, so we do not
261 assert this in add_symbol_to_partition_1.
263 Be lax about comdats; they may or may not be duplicated and we may
264 end up in need to duplicate keyed comdat because it has unkeyed alias. */
266 gcc_assert (node
->get_partitioning_class () == SYMBOL_DUPLICATE
267 || DECL_COMDAT (node
->decl
)
268 || !symbol_partitioned_p (node
));
270 add_symbol_to_partition_1 (part
, node
);
273 /* Undo all additions until number of cgraph nodes in PARITION is N_CGRAPH_NODES
274 and number of varpool nodes is N_VARPOOL_NODES. */
277 undo_partition (ltrans_partition partition
, unsigned int n_nodes
)
279 while (lto_symtab_encoder_size (partition
->encoder
) > (int)n_nodes
)
281 symtab_node
*node
= lto_symtab_encoder_deref (partition
->encoder
,
283 partition
->symbols
--;
286 /* After UNDO we no longer know what was visited. */
287 if (partition
->initializers_visited
)
288 delete partition
->initializers_visited
;
289 partition
->initializers_visited
= NULL
;
291 if (!node
->alias
&& (cnode
= dyn_cast
<cgraph_node
*> (node
))
292 && node
->get_partitioning_class () == SYMBOL_PARTITION
)
293 partition
->insns
-= ipa_size_summaries
->get (cnode
)->size
;
294 lto_symtab_encoder_delete_node (partition
->encoder
, node
);
295 node
->aux
= (void *)((size_t)node
->aux
- 1);
299 /* Group cgrah nodes by input files. This is used mainly for testing
303 lto_1_to_1_map (void)
306 struct lto_file_decl_data
*file_data
;
307 hash_map
<lto_file_decl_data
*, ltrans_partition
> pmap
;
308 ltrans_partition partition
;
311 FOR_EACH_SYMBOL (node
)
313 if (node
->get_partitioning_class () != SYMBOL_PARTITION
314 || symbol_partitioned_p (node
))
317 file_data
= node
->lto_file_data
;
321 ltrans_partition
*slot
= &pmap
.get_or_insert (file_data
);
326 partition
= new_partition (file_data
->file_name
);
331 else if (!file_data
&& ltrans_partitions
.length ())
332 partition
= ltrans_partitions
[0];
335 partition
= new_partition ("");
336 pmap
.put (NULL
, partition
);
340 add_symbol_to_partition (partition
, node
);
343 /* If the cgraph is empty, create one cgraph node set so that there is still
344 an output file for any variables that need to be exported in a DSO. */
346 new_partition ("empty");
348 /* Order partitions by order of symbols because they are linked into binary
350 ltrans_partitions
.qsort (cmp_partitions_order
);
353 /* Maximal partitioning. Put every new symbol into new partition if possible. */
359 ltrans_partition partition
;
362 FOR_EACH_SYMBOL (node
)
364 if (node
->get_partitioning_class () != SYMBOL_PARTITION
365 || symbol_partitioned_p (node
))
367 partition
= new_partition (node
->asm_name ());
368 add_symbol_to_partition (partition
, node
);
372 new_partition ("empty");
375 /* Helper function for qsort; sort nodes by order. */
377 node_cmp (const void *pa
, const void *pb
)
379 const symtab_node
*a
= *static_cast<const symtab_node
* const *> (pa
);
380 const symtab_node
*b
= *static_cast<const symtab_node
* const *> (pb
);
381 return b
->order
- a
->order
;
384 /* Add all symtab nodes from NEXT_NODE to PARTITION in order. */
387 add_sorted_nodes (vec
<symtab_node
*> &next_nodes
, ltrans_partition partition
)
392 next_nodes
.qsort (node_cmp
);
393 FOR_EACH_VEC_ELT (next_nodes
, i
, node
)
394 if (!symbol_partitioned_p (node
))
395 add_symbol_to_partition (partition
, node
);
398 /* Return true if we should account reference from N1 to N2 in cost
399 of partition boundary. */
402 account_reference_p (symtab_node
*n1
, symtab_node
*n2
)
404 if (cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (n1
))
406 /* Do not account references from aliases - they are never split across
410 /* Do not account recursion - the code below will handle it incorrectly
411 otherwise. Do not account references to external symbols: they will
412 never become local. Finally do not account references to duplicated
413 symbols: they will be always local. */
416 || n2
->get_partitioning_class () != SYMBOL_PARTITION
)
418 /* If referring node is external symbol do not account it to boundary
419 cost. Those are added into units only to enable possible constant
420 folding and devirtulization.
422 Here we do not know if it will ever be added to some partition
423 (this is decided by compute_ltrans_boundary) and second it is not
424 that likely that constant folding will actually use the reference. */
425 if (contained_in_symbol (n1
)
426 ->get_partitioning_class () == SYMBOL_EXTERNAL
)
432 /* Group cgraph nodes into equally-sized partitions.
434 The partitioning algorithm is simple: nodes are taken in predefined order.
435 The order corresponds to the order we want functions to have in the final
436 output. In the future this will be given by function reordering pass, but
437 at the moment we use the topological order, which is a good approximation.
439 The goal is to partition this linear order into intervals (partitions) so
440 that all the partitions have approximately the same size and the number of
441 callgraph or IPA reference edges crossing boundaries is minimal.
443 This is a lot faster (O(n) in size of callgraph) than algorithms doing
444 priority-based graph clustering that are generally O(n^2) and, since
445 WHOPR is designed to make things go well across partitions, it leads
448 We compute the expected size of a partition as:
450 max (total_size / lto_partitions, min_partition_size)
452 We use dynamic expected size of partition so small programs are partitioned
453 into enough partitions to allow use of multiple CPUs, while large programs
454 are not partitioned too much. Creating too many partitions significantly
455 increases the streaming overhead.
457 In the future, we would like to bound the maximal size of partitions so as
458 to prevent the LTRANS stage from consuming too much memory. At the moment,
459 however, the WPA stage is the most memory intensive for large benchmarks,
460 since too many types and declarations are read into memory.
462 The function implements a simple greedy algorithm. Nodes are being added
463 to the current partition until after 3/4 of the expected partition size is
464 reached. Past this threshold, we keep track of boundary size (number of
465 edges going to other partitions) and continue adding functions until after
466 the current partition has grown to twice the expected partition size. Then
467 the process is undone to the point where the minimal ratio of boundary size
468 and in-partition calls was reached. */
471 lto_balanced_map (int n_lto_partitions
, int max_partition_size
)
473 int n_varpool_nodes
= 0, varpool_pos
= 0, best_varpool_pos
= 0;
474 auto_vec
<cgraph_node
*> order (symtab
->cgraph_count
);
475 auto_vec
<cgraph_node
*> noreorder
;
476 auto_vec
<varpool_node
*> varpool_order
;
477 struct cgraph_node
*node
;
478 int64_t original_total_size
, total_size
= 0;
479 int64_t partition_size
;
480 ltrans_partition partition
;
481 int last_visited_node
= 0;
483 int64_t cost
= 0, internal
= 0;
484 unsigned int best_n_nodes
= 0, best_i
= 0;
485 int64_t best_cost
= -1, best_internal
= 0, best_size
= 0;
487 int current_order
= -1;
488 int noreorder_pos
= 0;
490 FOR_EACH_VARIABLE (vnode
)
491 gcc_assert (!vnode
->aux
);
493 FOR_EACH_DEFINED_FUNCTION (node
)
494 if (node
->get_partitioning_class () == SYMBOL_PARTITION
)
496 if (node
->no_reorder
)
497 noreorder
.safe_push (node
);
499 order
.safe_push (node
);
501 total_size
+= ipa_size_summaries
->get (node
)->size
;
504 original_total_size
= total_size
;
506 /* Streaming works best when the source units do not cross partition
507 boundaries much. This is because importing function from a source
508 unit tends to import a lot of global trees defined there. We should
509 get better about minimizing the function bounday, but until that
510 things works smoother if we order in source order. */
511 order
.qsort (tp_first_run_node_cmp
);
512 noreorder
.qsort (node_cmp
);
516 for (unsigned i
= 0; i
< order
.length (); i
++)
517 fprintf (dump_file
, "Balanced map symbol order:%s:%u\n",
518 order
[i
]->name (), order
[i
]->tp_first_run
);
519 for (unsigned i
= 0; i
< noreorder
.length (); i
++)
520 fprintf (dump_file
, "Balanced map symbol no_reorder:%s:%u\n",
521 noreorder
[i
]->name (), noreorder
[i
]->tp_first_run
);
524 /* Collect all variables that should not be reordered. */
525 FOR_EACH_VARIABLE (vnode
)
526 if (vnode
->get_partitioning_class () == SYMBOL_PARTITION
527 && vnode
->no_reorder
)
528 varpool_order
.safe_push (vnode
);
529 n_varpool_nodes
= varpool_order
.length ();
530 varpool_order
.qsort (node_cmp
);
532 /* Compute partition size and create the first partition. */
533 if (param_min_partition_size
> max_partition_size
)
534 fatal_error (input_location
, "min partition size cannot be greater "
535 "than max partition size");
537 partition_size
= total_size
/ n_lto_partitions
;
538 if (partition_size
< param_min_partition_size
)
539 partition_size
= param_min_partition_size
;
541 partition
= new_partition ("");
543 fprintf (dump_file
, "Total unit size: %" PRId64
", partition size: %" PRId64
"\n",
544 total_size
, partition_size
);
546 auto_vec
<symtab_node
*> next_nodes
;
548 for (unsigned i
= 0; i
< order
.length (); i
++)
550 if (symbol_partitioned_p (order
[i
]))
553 current_order
= order
[i
]->order
;
555 /* Output noreorder and varpool in program order first. */
556 next_nodes
.truncate (0);
557 while (varpool_pos
< n_varpool_nodes
558 && varpool_order
[varpool_pos
]->order
< current_order
)
559 next_nodes
.safe_push (varpool_order
[varpool_pos
++]);
560 while (noreorder_pos
< (int)noreorder
.length ()
561 && noreorder
[noreorder_pos
]->order
< current_order
)
562 next_nodes
.safe_push (noreorder
[noreorder_pos
++]);
563 add_sorted_nodes (next_nodes
, partition
);
565 if (!symbol_partitioned_p (order
[i
]))
566 add_symbol_to_partition (partition
, order
[i
]);
569 /* Once we added a new node to the partition, we also want to add
570 all referenced variables unless they was already added into some
572 add_symbol_to_partition adds possibly multiple nodes and
573 variables that are needed to satisfy needs of ORDER[i].
574 We remember last visited cgraph and varpool node from last iteration
575 of outer loop that allows us to process every new addition.
577 At the same time we compute size of the boundary into COST. Every
578 callgraph or IPA reference edge leaving the partition contributes into
579 COST. Every edge inside partition was earlier computed as one leaving
580 it and thus we need to subtract it from COST. */
581 while (last_visited_node
< lto_symtab_encoder_size (partition
->encoder
))
584 struct ipa_ref
*ref
= NULL
;
585 symtab_node
*snode
= lto_symtab_encoder_deref (partition
->encoder
,
588 if (cgraph_node
*node
= dyn_cast
<cgraph_node
*> (snode
))
590 struct cgraph_edge
*edge
;
595 gcc_assert (node
->definition
|| node
->weakref
);
597 /* Compute boundary cost of callgraph edges. */
598 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
599 /* Inline edges will always end up local. */
600 if (edge
->inline_failed
601 && account_reference_p (node
, edge
->callee
))
603 int edge_cost
= edge
->frequency ();
608 gcc_assert (edge_cost
> 0);
609 index
= lto_symtab_encoder_lookup (partition
->encoder
,
611 if (index
!= LCC_NOT_FOUND
612 && index
< last_visited_node
- 1)
613 cost
-= edge_cost
, internal
+= edge_cost
;
617 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
618 if (edge
->inline_failed
619 && account_reference_p (edge
->caller
, node
))
621 int edge_cost
= edge
->frequency ();
624 gcc_assert (edge
->caller
->definition
);
627 gcc_assert (edge_cost
> 0);
628 index
= lto_symtab_encoder_lookup (partition
->encoder
,
630 if (index
!= LCC_NOT_FOUND
631 && index
< last_visited_node
- 1)
632 cost
-= edge_cost
, internal
+= edge_cost
;
640 /* Compute boundary cost of IPA REF edges and at the same time look into
641 variables referenced from current partition and try to add them. */
642 for (j
= 0; snode
->iterate_reference (j
, ref
); j
++)
643 if (!account_reference_p (snode
, ref
->referred
))
645 else if (is_a
<varpool_node
*> (ref
->referred
))
649 vnode
= dyn_cast
<varpool_node
*> (ref
->referred
);
650 if (!symbol_partitioned_p (vnode
)
651 && !vnode
->no_reorder
652 && vnode
->get_partitioning_class () == SYMBOL_PARTITION
)
653 add_symbol_to_partition (partition
, vnode
);
654 index
= lto_symtab_encoder_lookup (partition
->encoder
,
656 if (index
!= LCC_NOT_FOUND
657 && index
< last_visited_node
- 1)
666 node
= dyn_cast
<cgraph_node
*> (ref
->referred
);
667 index
= lto_symtab_encoder_lookup (partition
->encoder
,
669 if (index
!= LCC_NOT_FOUND
670 && index
< last_visited_node
- 1)
675 for (j
= 0; snode
->iterate_referring (j
, ref
); j
++)
676 if (!account_reference_p (ref
->referring
, snode
))
678 else if (is_a
<varpool_node
*> (ref
->referring
))
682 vnode
= dyn_cast
<varpool_node
*> (ref
->referring
);
683 gcc_assert (vnode
->definition
);
684 /* It is better to couple variables with their users,
685 because it allows them to be removed. Coupling
686 with objects they refer to only helps to reduce
687 number of symbols promoted to hidden. */
688 if (!symbol_partitioned_p (vnode
)
689 && !vnode
->no_reorder
690 && !vnode
->can_remove_if_no_refs_p ()
691 && vnode
->get_partitioning_class () == SYMBOL_PARTITION
)
692 add_symbol_to_partition (partition
, vnode
);
693 index
= lto_symtab_encoder_lookup (partition
->encoder
,
695 if (index
!= LCC_NOT_FOUND
696 && index
< last_visited_node
- 1)
705 node
= dyn_cast
<cgraph_node
*> (ref
->referring
);
706 gcc_assert (node
->definition
);
707 index
= lto_symtab_encoder_lookup (partition
->encoder
,
709 if (index
!= LCC_NOT_FOUND
710 && index
< last_visited_node
- 1)
717 gcc_assert (cost
>= 0 && internal
>= 0);
719 /* If the partition is large enough, start looking for smallest boundary cost.
720 If partition still seems too small (less than 7/8 of target weight) accept
721 any cost. If partition has right size, optimize for highest internal/cost.
722 Later we stop building partition if its size is 9/8 of the target wight. */
723 if (partition
->insns
< partition_size
* 7 / 8
726 || ((sreal
)best_internal
* (sreal
) cost
727 < ((sreal
) internal
* (sreal
)best_cost
))))
730 best_internal
= internal
;
731 best_size
= partition
->insns
;
733 best_n_nodes
= lto_symtab_encoder_size (partition
->encoder
);
734 best_varpool_pos
= varpool_pos
;
737 fprintf (dump_file
, "Step %i: added %s/%i, size %i, "
738 "cost %" PRId64
"/%" PRId64
" "
739 "best %" PRId64
"/%" PRId64
", step %i\n", i
,
740 order
[i
]->name (), order
[i
]->order
,
741 partition
->insns
, cost
, internal
,
742 best_cost
, best_internal
, best_i
);
743 /* Partition is too large, unwind into step when best cost was reached and
744 start new partition. */
745 if (partition
->insns
> 9 * partition_size
/ 8
746 || partition
->insns
> max_partition_size
)
751 fprintf (dump_file
, "Unwinding %i insertions to step %i\n",
753 undo_partition (partition
, best_n_nodes
);
754 varpool_pos
= best_varpool_pos
;
756 gcc_assert (best_size
== partition
->insns
);
760 "Partition insns: %i (want %" PRId64
")\n",
761 partition
->insns
, partition_size
);
762 /* When we are finished, avoid creating empty partition. */
763 while (i
< order
.length () - 1 && symbol_partitioned_p (order
[i
+ 1]))
765 if (i
== order
.length () - 1)
767 total_size
-= partition
->insns
;
768 partition
= new_partition ("");
769 last_visited_node
= 0;
773 fprintf (dump_file
, "New partition\n");
777 /* Since the size of partitions is just approximate, update the size after
778 we finished current one. */
779 if (npartitions
< n_lto_partitions
)
780 partition_size
= total_size
/ (n_lto_partitions
- npartitions
);
782 /* Watch for overflow. */
783 partition_size
= INT_MAX
/ 16;
787 "Total size: %" PRId64
" partition_size: %" PRId64
"\n",
788 total_size
, partition_size
);
789 if (partition_size
< param_min_partition_size
)
790 partition_size
= param_min_partition_size
;
795 next_nodes
.truncate (0);
797 /* Varables that are not reachable from the code go into last partition. */
798 FOR_EACH_VARIABLE (vnode
)
799 if (vnode
->get_partitioning_class () == SYMBOL_PARTITION
800 && !symbol_partitioned_p (vnode
))
801 next_nodes
.safe_push (vnode
);
803 /* Output remaining ordered symbols. */
804 while (varpool_pos
< n_varpool_nodes
)
805 next_nodes
.safe_push (varpool_order
[varpool_pos
++]);
806 while (noreorder_pos
< (int)noreorder
.length ())
807 next_nodes
.safe_push (noreorder
[noreorder_pos
++]);
808 /* For one partition the cost of boundary should be 0 unless we added final
809 symbols here (these are not accounted) or we have accounting bug. */
810 gcc_assert (next_nodes
.length () || npartitions
!= 1 || !best_cost
|| best_cost
== -1);
811 add_sorted_nodes (next_nodes
, partition
);
815 fprintf (dump_file
, "\nPartition sizes:\n");
816 unsigned partitions
= ltrans_partitions
.length ();
818 for (unsigned i
= 0; i
< partitions
; i
++)
820 ltrans_partition p
= ltrans_partitions
[i
];
821 fprintf (dump_file
, "partition %d contains %d (%2.2f%%)"
822 " symbols and %d (%2.2f%%) insns\n", i
, p
->symbols
,
823 100.0 * p
->symbols
/ order
.length (), p
->insns
,
824 100.0 * p
->insns
/ original_total_size
);
827 fprintf (dump_file
, "\n");
831 /* Return true if we must not change the name of the NODE. The name as
832 extracted from the corresponding decl should be passed in NAME. */
835 must_not_rename (symtab_node
*node
, const char *name
)
837 /* Our renaming machinery do not handle more than one change of assembler name.
838 We should not need more than one anyway. */
839 if (node
->lto_file_data
840 && lto_get_decl_name_mapping (node
->lto_file_data
, name
) != name
)
844 "Not privatizing symbol name: %s. It privatized already.\n",
848 /* Avoid mangling of already mangled clones.
849 ??? should have a flag whether a symbol has a 'private' name already,
850 since we produce some symbols like that i.e. for global constructors
851 that are not really clones. */
852 if (node
->unique_name
)
856 "Not privatizing symbol name: %s. Has unique name.\n",
863 /* If we are an offload compiler, we may have to rewrite symbols to be
864 valid on this target. Return either PTR or a modified version of it. */
867 maybe_rewrite_identifier (const char *ptr
)
869 #if defined ACCEL_COMPILER && (defined NO_DOT_IN_LABEL || defined NO_DOLLAR_IN_LABEL)
870 #ifndef NO_DOT_IN_LABEL
872 const char reject
[] = "$";
873 #elif !defined NO_DOLLAR_IN_LABEL
875 const char reject
[] = ".";
878 const char reject
[] = ".$";
882 const char *match
= ptr
;
885 size_t off
= strcspn (match
, reject
);
886 if (match
[off
] == '\0')
890 copy
= xstrdup (ptr
);
901 /* Ensure that the symbol in NODE is valid for the target, and if not,
905 validize_symbol_for_target (symtab_node
*node
)
907 tree decl
= node
->decl
;
908 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
));
910 if (must_not_rename (node
, name
))
913 const char *name2
= maybe_rewrite_identifier (name
);
916 symtab
->change_decl_assembler_name (decl
, get_identifier (name2
));
917 if (node
->lto_file_data
)
918 lto_record_renamed_decl (node
->lto_file_data
, name
,
920 (DECL_ASSEMBLER_NAME (decl
)));
924 /* Maps symbol names to unique lto clone counters. */
925 static hash_map
<const char *, unsigned> *lto_clone_numbers
;
927 /* Helper for privatize_symbol_name. Mangle NODE symbol name
928 represented by DECL. */
931 privatize_symbol_name_1 (symtab_node
*node
, tree decl
)
933 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
));
935 if (must_not_rename (node
, name
))
938 name
= maybe_rewrite_identifier (name
);
939 unsigned &clone_number
= lto_clone_numbers
->get_or_insert (name
);
940 symtab
->change_decl_assembler_name (decl
,
941 clone_function_name (
942 name
, "lto_priv", clone_number
));
945 if (node
->lto_file_data
)
946 lto_record_renamed_decl (node
->lto_file_data
, name
,
948 (DECL_ASSEMBLER_NAME (decl
)));
952 "Privatizing symbol name: %s -> %s\n",
953 name
, IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
)));
958 /* Mangle NODE symbol name into a local name.
959 This is necessary to do
960 1) if two or more static vars of same assembler name
961 are merged into single ltrans unit.
962 2) if previously static var was promoted hidden to avoid possible conflict
963 with symbols defined out of the LTO world. */
966 privatize_symbol_name (symtab_node
*node
)
968 if (!privatize_symbol_name_1 (node
, node
->decl
))
974 /* Promote variable VNODE to be static. */
977 promote_symbol (symtab_node
*node
)
979 /* We already promoted ... */
980 if (DECL_VISIBILITY (node
->decl
) == VISIBILITY_HIDDEN
981 && DECL_VISIBILITY_SPECIFIED (node
->decl
)
982 && TREE_PUBLIC (node
->decl
))
984 validize_symbol_for_target (node
);
988 gcc_checking_assert (!TREE_PUBLIC (node
->decl
)
989 && !DECL_EXTERNAL (node
->decl
));
990 /* Be sure that newly public symbol does not conflict with anything already
991 defined by the non-LTO part. */
992 privatize_symbol_name (node
);
993 TREE_PUBLIC (node
->decl
) = 1;
994 DECL_VISIBILITY (node
->decl
) = VISIBILITY_HIDDEN
;
995 DECL_VISIBILITY_SPECIFIED (node
->decl
) = true;
998 "Promoting as hidden: %s (%s)\n", node
->name (),
999 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node
->decl
)));
1001 /* Promoting a symbol also promotes all transparent aliases with exception
1002 of weakref where the visibility flags are always wrong and set to
1005 for (unsigned i
= 0; node
->iterate_direct_aliases (i
, ref
); i
++)
1007 struct symtab_node
*alias
= ref
->referring
;
1008 if (alias
->transparent_alias
&& !alias
->weakref
)
1010 TREE_PUBLIC (alias
->decl
) = 1;
1011 DECL_VISIBILITY (alias
->decl
) = VISIBILITY_HIDDEN
;
1012 DECL_VISIBILITY_SPECIFIED (alias
->decl
) = true;
1015 "Promoting alias as hidden: %s\n",
1016 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node
->decl
)));
1018 gcc_assert (!alias
->weakref
|| TREE_PUBLIC (alias
->decl
));
1022 /* Return true if NODE needs named section even if it won't land in
1023 the partition symbol table.
1025 FIXME: we should really not use named sections for inline clones
1026 and master clones. */
1029 may_need_named_section_p (lto_symtab_encoder_t encoder
, symtab_node
*node
)
1031 struct cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1034 if (node
->real_symbol_p ())
1037 || (lto_symtab_encoder_lookup (encoder
, node
) != LCC_NOT_FOUND
1038 && lto_symtab_encoder_encode_body_p (encoder
,
1042 /* If NODE represents a static variable. See if there are other variables
1043 of the same name in partition ENCODER (or in whole compilation unit if
1044 ENCODER is NULL) and if so, mangle the statics. Always mangle all
1045 conflicting statics, so we reduce changes of silently miscompiling
1046 asm statements referring to them by symbol name. */
1049 rename_statics (lto_symtab_encoder_t encoder
, symtab_node
*node
)
1051 tree decl
= node
->decl
;
1053 tree name
= DECL_ASSEMBLER_NAME (decl
);
1055 /* See if this is static symbol. */
1056 if (((node
->externally_visible
&& !node
->weakref
)
1057 /* FIXME: externally_visible is somewhat illogically not set for
1058 external symbols (i.e. those not defined). Remove this test
1059 once this is fixed. */
1060 || DECL_EXTERNAL (node
->decl
)
1061 || !node
->real_symbol_p ())
1062 && !may_need_named_section_p (encoder
, node
))
1065 /* Now walk symbols sharing the same name and see if there are any conflicts.
1066 (all types of symbols counts here, since we cannot have static of the
1067 same name as external or public symbol.) */
1068 for (s
= symtab_node::get_for_asmname (name
);
1069 s
; s
= s
->next_sharing_asm_name
)
1070 if ((s
->real_symbol_p () || may_need_named_section_p (encoder
, s
))
1071 && s
->decl
!= node
->decl
1073 || lto_symtab_encoder_lookup (encoder
, s
) != LCC_NOT_FOUND
))
1076 /* OK, no confict, so we have nothing to do. */
1082 "Renaming statics with asm name: %s\n", node
->name ());
1084 /* Assign every symbol in the set that shares the same ASM name an unique
1086 for (s
= symtab_node::get_for_asmname (name
); s
;)
1087 if ((!s
->externally_visible
|| s
->weakref
)
1088 /* Transparent aliases having same name as target are renamed at a
1089 time their target gets new name. Transparent aliases that use
1090 separate assembler name require the name to be unique. */
1091 && (!s
->transparent_alias
|| !s
->definition
|| s
->weakref
1092 || !symbol_table::assembler_names_equal_p
1093 (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (s
->decl
)),
1095 (DECL_ASSEMBLER_NAME (s
->get_alias_target()->decl
))))
1096 && ((s
->real_symbol_p ()
1097 && !DECL_EXTERNAL (s
->decl
)
1098 && !TREE_PUBLIC (s
->decl
))
1099 || may_need_named_section_p (encoder
, s
))
1101 || lto_symtab_encoder_lookup (encoder
, s
) != LCC_NOT_FOUND
))
1103 if (privatize_symbol_name (s
))
1104 /* Re-start from beginning since we do not know how many
1105 symbols changed a name. */
1106 s
= symtab_node::get_for_asmname (name
);
1107 else s
= s
->next_sharing_asm_name
;
1109 else s
= s
->next_sharing_asm_name
;
1112 /* Find out all static decls that need to be promoted to global because
1113 of cross file sharing. This function must be run in the WPA mode after
1114 all inlinees are added. */
1117 lto_promote_cross_file_statics (void)
1121 gcc_assert (flag_wpa
);
1123 lto_stream_offload_p
= false;
1124 select_what_to_stream ();
1126 /* First compute boundaries. */
1127 n_sets
= ltrans_partitions
.length ();
1128 for (i
= 0; i
< n_sets
; i
++)
1130 ltrans_partition part
1131 = ltrans_partitions
[i
];
1132 part
->encoder
= compute_ltrans_boundary (part
->encoder
);
1135 lto_clone_numbers
= new hash_map
<const char *, unsigned>;
1137 /* Look at boundaries and promote symbols as needed. */
1138 for (i
= 0; i
< n_sets
; i
++)
1140 lto_symtab_encoder_iterator lsei
;
1141 lto_symtab_encoder_t encoder
= ltrans_partitions
[i
]->encoder
;
1143 for (lsei
= lsei_start (encoder
); !lsei_end_p (lsei
);
1146 symtab_node
*node
= lsei_node (lsei
);
1148 /* If symbol is static, rename it if its assembler name
1149 clashes with anything else in this unit. */
1150 rename_statics (encoder
, node
);
1152 /* No need to promote if symbol already is externally visible ... */
1153 if (node
->externally_visible
1154 /* ... or if it is part of current partition ... */
1155 || lto_symtab_encoder_in_partition_p (encoder
, node
)
1156 /* ... or if we do not partition it. This mean that it will
1157 appear in every partition referencing it. */
1158 || node
->get_partitioning_class () != SYMBOL_PARTITION
)
1160 validize_symbol_for_target (node
);
1164 promote_symbol (node
);
1167 delete lto_clone_numbers
;
1170 /* Rename statics in the whole unit in the case that
1171 we do -flto-partition=none. */
1174 lto_promote_statics_nonwpa (void)
1178 lto_clone_numbers
= new hash_map
<const char *, unsigned>;
1179 FOR_EACH_SYMBOL (node
)
1181 rename_statics (NULL
, node
);
1182 validize_symbol_for_target (node
);
1184 delete lto_clone_numbers
;