1 /* LTO partitioning logic routines.
2 Copyright (C) 2009-2015 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"
29 #include "fold-const.h"
32 #include "hard-reg-set.h"
35 #include "basic-block.h"
36 #include "tree-ssa-alias.h"
37 #include "internal-fn.h"
38 #include "gimple-expr.h"
41 #include "plugin-api.h"
44 #include "lto-streamer.h"
47 #include "alloc-pool.h"
48 #include "symbol-summary.h"
50 #include "ipa-inline.h"
51 #include "ipa-utils.h"
52 #include "lto-partition.h"
53 #include "stringpool.h"
55 vec
<ltrans_partition
> ltrans_partitions
;
57 static void add_symbol_to_partition (ltrans_partition part
, symtab_node
*node
);
60 /* Create new partition with name NAME. */
62 static ltrans_partition
63 new_partition (const char *name
)
65 ltrans_partition part
= XCNEW (struct ltrans_partition_def
);
66 part
->encoder
= lto_symtab_encoder_new (false);
70 ltrans_partitions
.safe_push (part
);
74 /* Free memory used by ltrans datastructures. */
77 free_ltrans_partitions (void)
80 ltrans_partition part
;
81 for (idx
= 0; ltrans_partitions
.iterate (idx
, &part
); idx
++)
83 if (part
->initializers_visited
)
84 delete part
->initializers_visited
;
85 /* Symtab encoder is freed after streaming. */
88 ltrans_partitions
.release ();
91 /* Return true if symbol is already in some partition. */
94 symbol_partitioned_p (symtab_node
*node
)
99 /* Add references into the partition. */
101 add_references_to_partition (ltrans_partition part
, symtab_node
*node
)
104 struct ipa_ref
*ref
= NULL
;
106 /* Add all duplicated references to the partition. */
107 for (i
= 0; node
->iterate_reference (i
, ref
); i
++)
108 if (ref
->referred
->get_partitioning_class () == SYMBOL_DUPLICATE
)
109 add_symbol_to_partition (part
, ref
->referred
);
110 /* References to a readonly variable may be constant foled into its value.
111 Recursively look into the initializers of the constant variable and add
113 else if (is_a
<varpool_node
*> (ref
->referred
)
114 && (dyn_cast
<varpool_node
*> (ref
->referred
)
115 ->ctor_useable_for_folding_p ()
116 || POINTER_BOUNDS_P (ref
->referred
->decl
))
117 && !lto_symtab_encoder_in_partition_p (part
->encoder
, ref
->referred
))
119 if (!part
->initializers_visited
)
120 part
->initializers_visited
= new hash_set
<symtab_node
*>;
121 if (!part
->initializers_visited
->add (ref
->referred
))
122 add_references_to_partition (part
, ref
->referred
);
126 /* Helper function for add_symbol_to_partition doing the actual dirty work
127 of adding NODE to PART. */
130 add_symbol_to_partition_1 (ltrans_partition part
, symtab_node
*node
)
132 enum symbol_partitioning_class c
= node
->get_partitioning_class ();
136 /* If NODE is already there, we have nothing to do. */
137 if (lto_symtab_encoder_in_partition_p (part
->encoder
, node
))
140 /* non-duplicated aliases or tunks of a duplicated symbol needs to be output
143 Be lax about comdats; they may or may not be duplicated and we may
144 end up in need to duplicate keyed comdat because it has unkeyed alias. */
145 if (c
== SYMBOL_PARTITION
&& !DECL_COMDAT (node
->decl
)
146 && symbol_partitioned_p (node
))
149 /* Be sure that we never try to duplicate partitioned symbol
150 or add external symbol. */
151 gcc_assert (c
!= SYMBOL_EXTERNAL
152 && (c
== SYMBOL_DUPLICATE
|| !symbol_partitioned_p (node
)));
156 lto_set_symtab_encoder_in_partition (part
->encoder
, node
);
158 if (symbol_partitioned_p (node
))
160 node
->in_other_partition
= 1;
161 if (symtab
->dump_file
)
162 fprintf (symtab
->dump_file
,
163 "Symbol node %s now used in multiple partitions\n",
166 node
->aux
= (void *)((size_t)node
->aux
+ 1);
168 if (cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
))
170 struct cgraph_edge
*e
;
172 part
->insns
+= inline_summaries
->get (cnode
)->self_size
;
174 /* Add all inline clones and callees that are duplicated. */
175 for (e
= cnode
->callees
; e
; e
= e
->next_callee
)
176 if (!e
->inline_failed
)
177 add_symbol_to_partition_1 (part
, e
->callee
);
178 else if (e
->callee
->get_partitioning_class () == SYMBOL_DUPLICATE
)
179 add_symbol_to_partition (part
, e
->callee
);
181 /* Add all thunks associated with the function. */
182 for (e
= cnode
->callers
; e
; e
= e
->next_caller
)
183 if (e
->caller
->thunk
.thunk_p
)
184 add_symbol_to_partition_1 (part
, e
->caller
);
186 /* Instrumented version is actually the same function.
187 Therefore put it into the same partition. */
188 if (cnode
->instrumented_version
)
189 add_symbol_to_partition_1 (part
, cnode
->instrumented_version
);
192 add_references_to_partition (part
, node
);
194 /* Add all aliases associated with the symbol. */
196 FOR_EACH_ALIAS (node
, ref
)
198 add_symbol_to_partition_1 (part
, ref
->referring
);
200 /* Ensure that SAME_COMDAT_GROUP lists all allways added in a group. */
201 if (node
->same_comdat_group
)
202 for (node1
= node
->same_comdat_group
;
203 node1
!= node
; node1
= node1
->same_comdat_group
)
206 bool added
= add_symbol_to_partition_1 (part
, node1
);
212 /* If symbol NODE is really part of other symbol's definition (i.e. it is
213 internal label, thunk, alias or so), return the outer symbol.
214 When add_symbol_to_partition_1 is called on the outer symbol it must
215 eventually add NODE, too. */
217 contained_in_symbol (symtab_node
*node
)
219 /* Weakrefs are never contained in anything. */
222 if (cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
))
224 cnode
= cnode
->function_symbol ();
225 if (cnode
->global
.inlined_to
)
226 cnode
= cnode
->global
.inlined_to
;
229 else if (varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
))
230 return vnode
->ultimate_alias_target ();
234 /* Add symbol NODE to partition. When definition of NODE is part
235 of other symbol definition, add the other symbol, too. */
238 add_symbol_to_partition (ltrans_partition part
, symtab_node
*node
)
242 /* Verify that we do not try to duplicate something that can not be. */
243 gcc_checking_assert (node
->get_partitioning_class () == SYMBOL_DUPLICATE
244 || !symbol_partitioned_p (node
));
246 while ((node1
= contained_in_symbol (node
)) != node
)
249 /* If we have duplicated symbol contained in something we can not duplicate,
250 we are very badly screwed. The other way is possible, so we do not
251 assert this in add_symbol_to_partition_1.
253 Be lax about comdats; they may or may not be duplicated and we may
254 end up in need to duplicate keyed comdat because it has unkeyed alias. */
256 gcc_assert (node
->get_partitioning_class () == SYMBOL_DUPLICATE
257 || DECL_COMDAT (node
->decl
)
258 || !symbol_partitioned_p (node
));
260 add_symbol_to_partition_1 (part
, node
);
263 /* Undo all additions until number of cgraph nodes in PARITION is N_CGRAPH_NODES
264 and number of varpool nodes is N_VARPOOL_NODES. */
267 undo_partition (ltrans_partition partition
, unsigned int n_nodes
)
269 while (lto_symtab_encoder_size (partition
->encoder
) > (int)n_nodes
)
271 symtab_node
*node
= lto_symtab_encoder_deref (partition
->encoder
,
273 partition
->symbols
--;
276 /* After UNDO we no longer know what was visited. */
277 if (partition
->initializers_visited
)
278 delete partition
->initializers_visited
;
279 partition
->initializers_visited
= NULL
;
281 if (!node
->alias
&& (cnode
= dyn_cast
<cgraph_node
*> (node
)))
282 partition
->insns
-= inline_summaries
->get (cnode
)->self_size
;
283 lto_symtab_encoder_delete_node (partition
->encoder
, node
);
284 node
->aux
= (void *)((size_t)node
->aux
- 1);
288 /* Group cgrah nodes by input files. This is used mainly for testing
292 lto_1_to_1_map (void)
295 struct lto_file_decl_data
*file_data
;
296 hash_map
<lto_file_decl_data
*, ltrans_partition
> pmap
;
297 ltrans_partition partition
;
300 FOR_EACH_SYMBOL (node
)
302 if (node
->get_partitioning_class () != SYMBOL_PARTITION
303 || symbol_partitioned_p (node
))
306 file_data
= node
->lto_file_data
;
310 ltrans_partition
*slot
= &pmap
.get_or_insert (file_data
);
315 partition
= new_partition (file_data
->file_name
);
320 else if (!file_data
&& ltrans_partitions
.length ())
321 partition
= ltrans_partitions
[0];
324 partition
= new_partition ("");
325 pmap
.put (NULL
, partition
);
329 add_symbol_to_partition (partition
, node
);
332 /* If the cgraph is empty, create one cgraph node set so that there is still
333 an output file for any variables that need to be exported in a DSO. */
335 new_partition ("empty");
339 /* Maximal partitioning. Put every new symbol into new partition if possible. */
345 ltrans_partition partition
;
348 FOR_EACH_SYMBOL (node
)
350 if (node
->get_partitioning_class () != SYMBOL_PARTITION
351 || symbol_partitioned_p (node
))
353 partition
= new_partition (node
->asm_name ());
354 add_symbol_to_partition (partition
, node
);
358 new_partition ("empty");
361 /* Helper function for qsort; sort nodes by order. noreorder functions must have
362 been removed earlier. */
364 node_cmp (const void *pa
, const void *pb
)
366 const struct cgraph_node
*a
= *(const struct cgraph_node
* const *) pa
;
367 const struct cgraph_node
*b
= *(const struct cgraph_node
* const *) pb
;
369 /* Profile reorder flag enables function reordering based on first execution
370 of a function. All functions with profile are placed in ascending
371 order at the beginning. */
373 if (flag_profile_reorder_functions
)
375 /* Functions with time profile are sorted in ascending order. */
376 if (a
->tp_first_run
&& b
->tp_first_run
)
377 return a
->tp_first_run
!= b
->tp_first_run
378 ? a
->tp_first_run
- b
->tp_first_run
379 : a
->order
- b
->order
;
381 /* Functions with time profile are sorted before the functions
382 that do not have the profile. */
383 if (a
->tp_first_run
|| b
->tp_first_run
)
384 return b
->tp_first_run
- a
->tp_first_run
;
387 return b
->order
- a
->order
;
390 /* Helper function for qsort; sort nodes by order. */
392 varpool_node_cmp (const void *pa
, const void *pb
)
394 const symtab_node
*a
= *static_cast<const symtab_node
* const *> (pa
);
395 const symtab_node
*b
= *static_cast<const symtab_node
* const *> (pb
);
396 return b
->order
- a
->order
;
399 /* Add all symtab nodes from NEXT_NODE to PARTITION in order. */
402 add_sorted_nodes (vec
<symtab_node
*> &next_nodes
, ltrans_partition partition
)
407 next_nodes
.qsort (varpool_node_cmp
);
408 FOR_EACH_VEC_ELT (next_nodes
, i
, node
)
409 if (!symbol_partitioned_p (node
))
410 add_symbol_to_partition (partition
, node
);
414 /* Group cgraph nodes into equally-sized partitions.
416 The partitioning algorithm is simple: nodes are taken in predefined order.
417 The order corresponds to the order we want functions to have in the final
418 output. In the future this will be given by function reordering pass, but
419 at the moment we use the topological order, which is a good approximation.
421 The goal is to partition this linear order into intervals (partitions) so
422 that all the partitions have approximately the same size and the number of
423 callgraph or IPA reference edges crossing boundaries is minimal.
425 This is a lot faster (O(n) in size of callgraph) than algorithms doing
426 priority-based graph clustering that are generally O(n^2) and, since
427 WHOPR is designed to make things go well across partitions, it leads
430 We compute the expected size of a partition as:
432 max (total_size / lto_partitions, min_partition_size)
434 We use dynamic expected size of partition so small programs are partitioned
435 into enough partitions to allow use of multiple CPUs, while large programs
436 are not partitioned too much. Creating too many partitions significantly
437 increases the streaming overhead.
439 In the future, we would like to bound the maximal size of partitions so as
440 to prevent the LTRANS stage from consuming too much memory. At the moment,
441 however, the WPA stage is the most memory intensive for large benchmarks,
442 since too many types and declarations are read into memory.
444 The function implements a simple greedy algorithm. Nodes are being added
445 to the current partition until after 3/4 of the expected partition size is
446 reached. Past this threshold, we keep track of boundary size (number of
447 edges going to other partitions) and continue adding functions until after
448 the current partition has grown to twice the expected partition size. Then
449 the process is undone to the point where the minimal ratio of boundary size
450 and in-partition calls was reached. */
453 lto_balanced_map (int n_lto_partitions
)
456 int n_varpool_nodes
= 0, varpool_pos
= 0, best_varpool_pos
= 0;
457 struct cgraph_node
**order
= XNEWVEC (cgraph_node
*, symtab
->cgraph_max_uid
);
458 auto_vec
<cgraph_node
*> noreorder
;
459 auto_vec
<varpool_node
*> varpool_order
;
461 struct cgraph_node
*node
;
462 int original_total_size
, total_size
= 0, best_total_size
= 0;
464 ltrans_partition partition
;
465 int last_visited_node
= 0;
467 int cost
= 0, internal
= 0;
468 int best_n_nodes
= 0, best_i
= 0, best_cost
=
469 INT_MAX
, best_internal
= 0;
471 int current_order
= -1;
472 int noreorder_pos
= 0;
474 FOR_EACH_VARIABLE (vnode
)
475 gcc_assert (!vnode
->aux
);
477 FOR_EACH_DEFINED_FUNCTION (node
)
478 if (node
->get_partitioning_class () == SYMBOL_PARTITION
)
480 if (node
->no_reorder
)
481 noreorder
.safe_push (node
);
483 order
[n_nodes
++] = node
;
485 total_size
+= inline_summaries
->get (node
)->size
;
488 original_total_size
= total_size
;
490 /* Streaming works best when the source units do not cross partition
491 boundaries much. This is because importing function from a source
492 unit tends to import a lot of global trees defined there. We should
493 get better about minimizing the function bounday, but until that
494 things works smoother if we order in source order. */
495 qsort (order
, n_nodes
, sizeof (struct cgraph_node
*), node_cmp
);
496 noreorder
.qsort (node_cmp
);
498 if (symtab
->dump_file
)
500 for(i
= 0; i
< n_nodes
; i
++)
501 fprintf (symtab
->dump_file
, "Balanced map symbol order:%s:%u\n",
502 order
[i
]->name (), order
[i
]->tp_first_run
);
503 for(i
= 0; i
< (int)noreorder
.length(); i
++)
504 fprintf (symtab
->dump_file
, "Balanced map symbol no_reorder:%s:%u\n",
505 noreorder
[i
]->name (), noreorder
[i
]->tp_first_run
);
508 /* Collect all variables that should not be reordered. */
509 FOR_EACH_VARIABLE (vnode
)
510 if (vnode
->get_partitioning_class () == SYMBOL_PARTITION
511 && (!flag_toplevel_reorder
|| vnode
->no_reorder
))
512 varpool_order
.safe_push (vnode
);
513 n_varpool_nodes
= varpool_order
.length ();
514 varpool_order
.qsort (varpool_node_cmp
);
516 /* Compute partition size and create the first partition. */
517 partition_size
= total_size
/ n_lto_partitions
;
518 if (partition_size
< PARAM_VALUE (MIN_PARTITION_SIZE
))
519 partition_size
= PARAM_VALUE (MIN_PARTITION_SIZE
);
521 partition
= new_partition ("");
522 if (symtab
->dump_file
)
523 fprintf (symtab
->dump_file
, "Total unit size: %i, partition size: %i\n",
524 total_size
, partition_size
);
526 auto_vec
<symtab_node
*> next_nodes
;
528 for (i
= 0; i
< n_nodes
; i
++)
530 if (symbol_partitioned_p (order
[i
]))
533 current_order
= order
[i
]->order
;
535 /* Output noreorder and varpool in program order first. */
536 next_nodes
.truncate (0);
537 while (varpool_pos
< n_varpool_nodes
538 && varpool_order
[varpool_pos
]->order
< current_order
)
539 next_nodes
.safe_push (varpool_order
[varpool_pos
++]);
540 while (noreorder_pos
< (int)noreorder
.length ()
541 && noreorder
[noreorder_pos
]->order
< current_order
)
543 if (!noreorder
[noreorder_pos
]->alias
)
544 total_size
-= inline_summaries
->get (noreorder
[noreorder_pos
])->size
;
545 next_nodes
.safe_push (noreorder
[noreorder_pos
++]);
547 add_sorted_nodes (next_nodes
, partition
);
549 add_symbol_to_partition (partition
, order
[i
]);
550 if (!order
[i
]->alias
)
551 total_size
-= inline_summaries
->get (order
[i
])->size
;
554 /* Once we added a new node to the partition, we also want to add
555 all referenced variables unless they was already added into some
557 add_symbol_to_partition adds possibly multiple nodes and
558 variables that are needed to satisfy needs of ORDER[i].
559 We remember last visited cgraph and varpool node from last iteration
560 of outer loop that allows us to process every new addition.
562 At the same time we compute size of the boundary into COST. Every
563 callgraph or IPA reference edge leaving the partition contributes into
564 COST. Every edge inside partition was earlier computed as one leaving
565 it and thus we need to subtract it from COST. */
566 while (last_visited_node
< lto_symtab_encoder_size (partition
->encoder
))
568 symtab_node
*refs_node
;
570 struct ipa_ref
*ref
= NULL
;
571 symtab_node
*snode
= lto_symtab_encoder_deref (partition
->encoder
,
574 if (cgraph_node
*node
= dyn_cast
<cgraph_node
*> (snode
))
576 struct cgraph_edge
*edge
;
582 gcc_assert (node
->definition
|| node
->weakref
);
584 /* Compute boundary cost of callgraph edges. */
585 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
586 if (edge
->callee
->definition
)
588 int edge_cost
= edge
->frequency
;
593 gcc_assert (edge_cost
> 0);
594 index
= lto_symtab_encoder_lookup (partition
->encoder
,
596 if (index
!= LCC_NOT_FOUND
597 && index
< last_visited_node
- 1)
598 cost
-= edge_cost
, internal
+= edge_cost
;
602 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
604 int edge_cost
= edge
->frequency
;
607 gcc_assert (edge
->caller
->definition
);
610 gcc_assert (edge_cost
> 0);
611 index
= lto_symtab_encoder_lookup (partition
->encoder
,
613 if (index
!= LCC_NOT_FOUND
614 && index
< last_visited_node
- 1)
626 /* Compute boundary cost of IPA REF edges and at the same time look into
627 variables referenced from current partition and try to add them. */
628 for (j
= 0; refs_node
->iterate_reference (j
, ref
); j
++)
629 if (is_a
<varpool_node
*> (ref
->referred
))
633 vnode
= dyn_cast
<varpool_node
*> (ref
->referred
);
634 if (!vnode
->definition
)
636 if (!symbol_partitioned_p (vnode
) && flag_toplevel_reorder
637 && !vnode
->no_reorder
638 && vnode
->get_partitioning_class () == SYMBOL_PARTITION
)
639 add_symbol_to_partition (partition
, vnode
);
640 index
= lto_symtab_encoder_lookup (partition
->encoder
,
642 if (index
!= LCC_NOT_FOUND
643 && index
< last_visited_node
- 1)
652 node
= dyn_cast
<cgraph_node
*> (ref
->referred
);
653 if (!node
->definition
)
655 index
= lto_symtab_encoder_lookup (partition
->encoder
,
657 if (index
!= LCC_NOT_FOUND
658 && index
< last_visited_node
- 1)
663 for (j
= 0; refs_node
->iterate_referring (j
, ref
); j
++)
664 if (is_a
<varpool_node
*> (ref
->referring
))
668 vnode
= dyn_cast
<varpool_node
*> (ref
->referring
);
669 gcc_assert (vnode
->definition
);
670 /* It is better to couple variables with their users, because it allows them
671 to be removed. Coupling with objects they refer to only helps to reduce
672 number of symbols promoted to hidden. */
673 if (!symbol_partitioned_p (vnode
) && flag_toplevel_reorder
674 && !vnode
->no_reorder
675 && !vnode
->can_remove_if_no_refs_p ()
676 && vnode
->get_partitioning_class () == SYMBOL_PARTITION
)
677 add_symbol_to_partition (partition
, vnode
);
678 index
= lto_symtab_encoder_lookup (partition
->encoder
,
680 if (index
!= LCC_NOT_FOUND
681 && index
< last_visited_node
- 1)
690 node
= dyn_cast
<cgraph_node
*> (ref
->referring
);
691 gcc_assert (node
->definition
);
692 index
= lto_symtab_encoder_lookup (partition
->encoder
,
694 if (index
!= LCC_NOT_FOUND
695 && index
< last_visited_node
- 1)
702 /* If the partition is large enough, start looking for smallest boundary cost. */
703 if (partition
->insns
< partition_size
* 3 / 4
704 || best_cost
== INT_MAX
706 || (best_internal
* (HOST_WIDE_INT
) cost
707 > (internal
* (HOST_WIDE_INT
)best_cost
)))
708 && partition
->insns
< partition_size
* 5 / 4))
711 best_internal
= internal
;
713 best_n_nodes
= lto_symtab_encoder_size (partition
->encoder
);
714 best_total_size
= total_size
;
715 best_varpool_pos
= varpool_pos
;
717 if (symtab
->dump_file
)
718 fprintf (symtab
->dump_file
, "Step %i: added %s/%i, size %i, cost %i/%i "
719 "best %i/%i, step %i\n", i
,
720 order
[i
]->name (), order
[i
]->order
,
721 partition
->insns
, cost
, internal
,
722 best_cost
, best_internal
, best_i
);
723 /* Partition is too large, unwind into step when best cost was reached and
724 start new partition. */
725 if (partition
->insns
> 2 * partition_size
)
729 if (symtab
->dump_file
)
730 fprintf (symtab
->dump_file
, "Unwinding %i insertions to step %i\n",
732 undo_partition (partition
, best_n_nodes
);
733 varpool_pos
= best_varpool_pos
;
736 /* When we are finished, avoid creating empty partition. */
737 while (i
< n_nodes
- 1 && symbol_partitioned_p (order
[i
+ 1]))
739 if (i
== n_nodes
- 1)
741 partition
= new_partition ("");
742 last_visited_node
= 0;
743 total_size
= best_total_size
;
746 if (symtab
->dump_file
)
747 fprintf (symtab
->dump_file
, "New partition\n");
751 /* Since the size of partitions is just approximate, update the size after
752 we finished current one. */
753 if (npartitions
< n_lto_partitions
)
754 partition_size
= total_size
/ (n_lto_partitions
- npartitions
);
756 partition_size
= INT_MAX
;
758 if (partition_size
< PARAM_VALUE (MIN_PARTITION_SIZE
))
759 partition_size
= PARAM_VALUE (MIN_PARTITION_SIZE
);
764 next_nodes
.truncate (0);
766 /* Varables that are not reachable from the code go into last partition. */
767 if (flag_toplevel_reorder
)
769 FOR_EACH_VARIABLE (vnode
)
770 if (vnode
->get_partitioning_class () == SYMBOL_PARTITION
771 && !symbol_partitioned_p (vnode
)
772 && !vnode
->no_reorder
)
773 next_nodes
.safe_push (vnode
);
776 /* Output remaining ordered symbols. */
777 while (varpool_pos
< n_varpool_nodes
)
778 next_nodes
.safe_push (varpool_order
[varpool_pos
++]);
779 while (noreorder_pos
< (int)noreorder
.length ())
780 next_nodes
.safe_push (noreorder
[noreorder_pos
++]);
781 add_sorted_nodes (next_nodes
, partition
);
785 if (symtab
->dump_file
)
787 fprintf (symtab
->dump_file
, "\nPartition sizes:\n");
788 unsigned partitions
= ltrans_partitions
.length ();
790 for (unsigned i
= 0; i
< partitions
; i
++)
792 ltrans_partition p
= ltrans_partitions
[i
];
793 fprintf (symtab
->dump_file
, "partition %d contains %d (%2.2f%%)"
794 " symbols and %d (%2.2f%%) insns\n", i
, p
->symbols
,
795 100.0 * p
->symbols
/ n_nodes
, p
->insns
,
796 100.0 * p
->insns
/ original_total_size
);
799 fprintf (symtab
->dump_file
, "\n");
803 /* Return true if we must not change the name of the NODE. The name as
804 extracted from the corresponding decl should be passed in NAME. */
807 must_not_rename (symtab_node
*node
, const char *name
)
809 /* Our renaming machinery do not handle more than one change of assembler name.
810 We should not need more than one anyway. */
811 if (node
->lto_file_data
812 && lto_get_decl_name_mapping (node
->lto_file_data
, name
) != name
)
814 if (symtab
->dump_file
)
815 fprintf (symtab
->dump_file
,
816 "Not privatizing symbol name: %s. It privatized already.\n",
820 /* Avoid mangling of already mangled clones.
821 ??? should have a flag whether a symbol has a 'private' name already,
822 since we produce some symbols like that i.e. for global constructors
823 that are not really clones. */
824 if (node
->unique_name
)
826 if (symtab
->dump_file
)
827 fprintf (symtab
->dump_file
,
828 "Not privatizing symbol name: %s. Has unique name.\n",
835 /* If we are an offload compiler, we may have to rewrite symbols to be
836 valid on this target. Return either PTR or a modified version of it. */
839 maybe_rewrite_identifier (const char *ptr
)
841 #if defined ACCEL_COMPILER && (defined NO_DOT_IN_LABEL || defined NO_DOLLAR_IN_LABEL)
842 #ifndef NO_DOT_IN_LABEL
844 const char reject
[] = "$";
845 #elif !defined NO_DOLLAR_IN_LABEL
847 const char reject
[] = ".";
850 const char reject
[] = ".$";
854 const char *match
= ptr
;
857 size_t off
= strcspn (match
, reject
);
858 if (match
[off
] == '\0')
862 copy
= xstrdup (ptr
);
873 /* Ensure that the symbol in NODE is valid for the target, and if not,
877 validize_symbol_for_target (symtab_node
*node
)
879 tree decl
= node
->decl
;
880 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
));
882 if (must_not_rename (node
, name
))
885 const char *name2
= maybe_rewrite_identifier (name
);
888 symtab
->change_decl_assembler_name (decl
, get_identifier (name2
));
889 if (node
->lto_file_data
)
890 lto_record_renamed_decl (node
->lto_file_data
, name
,
892 (DECL_ASSEMBLER_NAME (decl
)));
896 /* Helper for privatize_symbol_name. Mangle NODE symbol name
897 represented by DECL. */
900 privatize_symbol_name_1 (symtab_node
*node
, tree decl
)
902 const char *name
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
));
904 if (must_not_rename (node
, name
))
907 name
= maybe_rewrite_identifier (name
);
908 symtab
->change_decl_assembler_name (decl
,
909 clone_function_name_1 (name
,
912 if (node
->lto_file_data
)
913 lto_record_renamed_decl (node
->lto_file_data
, name
,
915 (DECL_ASSEMBLER_NAME (decl
)));
917 if (symtab
->dump_file
)
918 fprintf (symtab
->dump_file
,
919 "Privatizing symbol name: %s -> %s\n",
920 name
, IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl
)));
925 /* Mangle NODE symbol name into a local name.
926 This is necessary to do
927 1) if two or more static vars of same assembler name
928 are merged into single ltrans unit.
929 2) if previously static var was promoted hidden to avoid possible conflict
930 with symbols defined out of the LTO world. */
933 privatize_symbol_name (symtab_node
*node
)
935 if (!privatize_symbol_name_1 (node
, node
->decl
))
938 /* We could change name which is a target of transparent alias
939 chain of instrumented function name. Fix alias chain if so .*/
940 if (cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
))
942 tree iname
= NULL_TREE
;
943 if (cnode
->instrumentation_clone
)
945 /* If we want to privatize instrumentation clone
946 then we also need to privatize original function. */
947 if (cnode
->instrumented_version
)
948 privatize_symbol_name (cnode
->instrumented_version
);
950 privatize_symbol_name_1 (cnode
, cnode
->orig_decl
);
951 iname
= DECL_ASSEMBLER_NAME (cnode
->decl
);
952 TREE_CHAIN (iname
) = DECL_ASSEMBLER_NAME (cnode
->orig_decl
);
954 else if (cnode
->instrumented_version
955 && cnode
->instrumented_version
->orig_decl
== cnode
->decl
)
957 iname
= DECL_ASSEMBLER_NAME (cnode
->instrumented_version
->decl
);
958 TREE_CHAIN (iname
) = DECL_ASSEMBLER_NAME (cnode
->decl
);
965 /* Promote variable VNODE to be static. */
968 promote_symbol (symtab_node
*node
)
970 /* We already promoted ... */
971 if (DECL_VISIBILITY (node
->decl
) == VISIBILITY_HIDDEN
972 && DECL_VISIBILITY_SPECIFIED (node
->decl
)
973 && TREE_PUBLIC (node
->decl
))
975 validize_symbol_for_target (node
);
979 gcc_checking_assert (!TREE_PUBLIC (node
->decl
)
980 && !DECL_EXTERNAL (node
->decl
));
981 /* Be sure that newly public symbol does not conflict with anything already
982 defined by the non-LTO part. */
983 privatize_symbol_name (node
);
984 TREE_PUBLIC (node
->decl
) = 1;
985 DECL_VISIBILITY (node
->decl
) = VISIBILITY_HIDDEN
;
986 DECL_VISIBILITY_SPECIFIED (node
->decl
) = true;
987 if (symtab
->dump_file
)
988 fprintf (symtab
->dump_file
,
989 "Promoting as hidden: %s\n", node
->name ());
992 /* Return true if NODE needs named section even if it won't land in the partition
994 FIXME: we should really not use named sections for inline clones and master clones. */
997 may_need_named_section_p (lto_symtab_encoder_t encoder
, symtab_node
*node
)
999 struct cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1002 if (node
->real_symbol_p ())
1005 || (lto_symtab_encoder_lookup (encoder
, node
) != LCC_NOT_FOUND
1006 && lto_symtab_encoder_encode_body_p (encoder
,
1010 /* If NODE represents a static variable. See if there are other variables
1011 of the same name in partition ENCODER (or in whole compilation unit if
1012 ENCODER is NULL) and if so, mangle the statics. Always mangle all
1013 conflicting statics, so we reduce changes of silently miscompiling
1014 asm statements referring to them by symbol name. */
1017 rename_statics (lto_symtab_encoder_t encoder
, symtab_node
*node
)
1019 tree decl
= node
->decl
;
1021 tree name
= DECL_ASSEMBLER_NAME (decl
);
1023 /* See if this is static symbol. */
1024 if ((node
->externally_visible
1025 /* FIXME: externally_visible is somewhat illogically not set for
1026 external symbols (i.e. those not defined). Remove this test
1027 once this is fixed. */
1028 || DECL_EXTERNAL (node
->decl
)
1029 || !node
->real_symbol_p ())
1030 && !may_need_named_section_p (encoder
, node
))
1033 /* Now walk symbols sharing the same name and see if there are any conflicts.
1034 (all types of symbols counts here, since we can not have static of the
1035 same name as external or public symbol.) */
1036 for (s
= symtab_node::get_for_asmname (name
);
1037 s
; s
= s
->next_sharing_asm_name
)
1038 if ((s
->real_symbol_p () || may_need_named_section_p (encoder
, s
))
1039 && s
->decl
!= node
->decl
1041 || lto_symtab_encoder_lookup (encoder
, s
) != LCC_NOT_FOUND
))
1044 /* OK, no confict, so we have nothing to do. */
1048 if (symtab
->dump_file
)
1049 fprintf (symtab
->dump_file
,
1050 "Renaming statics with asm name: %s\n", node
->name ());
1052 /* Assign every symbol in the set that shares the same ASM name an unique
1054 for (s
= symtab_node::get_for_asmname (name
); s
;)
1055 if (!s
->externally_visible
1056 && ((s
->real_symbol_p ()
1057 && !DECL_EXTERNAL (node
->decl
)
1058 && !TREE_PUBLIC (node
->decl
))
1059 || may_need_named_section_p (encoder
, s
))
1061 || lto_symtab_encoder_lookup (encoder
, s
) != LCC_NOT_FOUND
))
1063 if (privatize_symbol_name (s
))
1064 /* Re-start from beginning since we do not know how many symbols changed a name. */
1065 s
= symtab_node::get_for_asmname (name
);
1066 else s
= s
->next_sharing_asm_name
;
1068 else s
= s
->next_sharing_asm_name
;
1071 /* Find out all static decls that need to be promoted to global because
1072 of cross file sharing. This function must be run in the WPA mode after
1073 all inlinees are added. */
1076 lto_promote_cross_file_statics (void)
1080 gcc_assert (flag_wpa
);
1082 lto_stream_offload_p
= false;
1083 select_what_to_stream ();
1085 /* First compute boundaries. */
1086 n_sets
= ltrans_partitions
.length ();
1087 for (i
= 0; i
< n_sets
; i
++)
1089 ltrans_partition part
1090 = ltrans_partitions
[i
];
1091 part
->encoder
= compute_ltrans_boundary (part
->encoder
);
1094 /* Look at boundaries and promote symbols as needed. */
1095 for (i
= 0; i
< n_sets
; i
++)
1097 lto_symtab_encoder_iterator lsei
;
1098 lto_symtab_encoder_t encoder
= ltrans_partitions
[i
]->encoder
;
1100 for (lsei
= lsei_start (encoder
); !lsei_end_p (lsei
);
1103 symtab_node
*node
= lsei_node (lsei
);
1105 /* If symbol is static, rename it if its assembler name clash with
1106 anything else in this unit. */
1107 rename_statics (encoder
, node
);
1109 /* No need to promote if symbol already is externally visible ... */
1110 if (node
->externally_visible
1111 /* ... or if it is part of current partition ... */
1112 || lto_symtab_encoder_in_partition_p (encoder
, node
)
1113 /* ... or if we do not partition it. This mean that it will
1114 appear in every partition refernecing it. */
1115 || node
->get_partitioning_class () != SYMBOL_PARTITION
)
1117 validize_symbol_for_target (node
);
1121 promote_symbol (node
);
1126 /* Rename statics in the whole unit in the case that
1127 we do -flto-partition=none. */
1130 lto_promote_statics_nonwpa (void)
1133 FOR_EACH_SYMBOL (node
)
1135 rename_statics (NULL
, node
);
1136 validize_symbol_for_target (node
);