1 /* LTO partitioning logic routines.
2 Copyright 2009, 2010, 2011, 2012 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"
27 #include "lto-streamer.h"
30 #include "ipa-inline.h"
31 #include "ipa-utils.h"
32 #include "lto-partition.h"
34 VEC(ltrans_partition
, heap
) *ltrans_partitions
;
36 static void add_cgraph_node_to_partition (ltrans_partition part
, struct cgraph_node
*node
);
37 static void add_varpool_node_to_partition (ltrans_partition part
, struct varpool_node
*vnode
);
39 /* Create new partition with name NAME. */
40 static ltrans_partition
41 new_partition (const char *name
)
43 ltrans_partition part
= XCNEW (struct ltrans_partition_def
);
44 part
->cgraph_set
= cgraph_node_set_new ();
45 part
->varpool_set
= varpool_node_set_new ();
48 VEC_safe_push (ltrans_partition
, heap
, ltrans_partitions
, part
);
52 /* Free memory used by ltrans datastructures. */
54 free_ltrans_partitions (void)
57 ltrans_partition part
;
58 for (idx
= 0; VEC_iterate (ltrans_partition
, ltrans_partitions
, idx
, part
); idx
++)
60 free_cgraph_node_set (part
->cgraph_set
);
63 VEC_free (ltrans_partition
, heap
, ltrans_partitions
);
66 /* See all references that go to comdat objects and bring them into partition too.
67 Also see all aliases of the newly added entry and bring them, too. */
69 add_references_to_partition (ltrans_partition part
, struct ipa_ref_list
*refs
)
73 for (i
= 0; ipa_ref_list_reference_iterate (refs
, i
, ref
); i
++)
75 if (symtab_function_p (ref
->referred
)
76 && (DECL_COMDAT (cgraph_function_node (ipa_ref_node (ref
),
78 || (ref
->use
== IPA_REF_ALIAS
80 ("weakref", DECL_ATTRIBUTES (ipa_ref_node (ref
)->symbol
.decl
))))
81 && !cgraph_node_in_set_p (ipa_ref_node (ref
), part
->cgraph_set
))
82 add_cgraph_node_to_partition (part
, ipa_ref_node (ref
));
84 if (symtab_variable_p (ref
->referred
)
85 && (DECL_COMDAT (ipa_ref_varpool_node (ref
)->symbol
.decl
)
86 || DECL_EXTERNAL (ipa_ref_varpool_node (ref
)->symbol
.decl
)
87 || (ref
->use
== IPA_REF_ALIAS
90 DECL_ATTRIBUTES (ipa_ref_varpool_node (ref
)->symbol
.decl
))))
91 && !varpool_node_in_set_p (ipa_ref_varpool_node (ref
),
93 add_varpool_node_to_partition (part
, ipa_ref_varpool_node (ref
));
95 for (i
= 0; ipa_ref_list_referring_iterate (refs
, i
, ref
); i
++)
97 if (symtab_function_p (ref
->referring
)
98 && ref
->use
== IPA_REF_ALIAS
99 && !cgraph_node_in_set_p (ipa_ref_referring_node (ref
),
101 && !lookup_attribute ("weakref",
103 (ipa_ref_referring_node (ref
)->symbol
.decl
)))
104 add_cgraph_node_to_partition (part
, ipa_ref_referring_node (ref
));
106 if (symtab_variable_p (ref
->referring
)
107 && ref
->use
== IPA_REF_ALIAS
108 && !varpool_node_in_set_p (ipa_ref_referring_varpool_node (ref
),
110 && !lookup_attribute ("weakref",
112 (ipa_ref_referring_varpool_node (ref
)->symbol
.decl
)))
113 add_varpool_node_to_partition (part
,
114 ipa_ref_referring_varpool_node (ref
));
118 /* Worker for add_cgraph_node_to_partition. */
121 add_cgraph_node_to_partition_1 (struct cgraph_node
*node
, void *data
)
123 ltrans_partition part
= (ltrans_partition
) data
;
125 /* non-COMDAT aliases of COMDAT functions needs to be output just once. */
126 if (!DECL_COMDAT (node
->symbol
.decl
)
127 && !node
->global
.inlined_to
130 gcc_assert (node
->thunk
.thunk_p
|| node
->alias
);
134 if (node
->symbol
.aux
)
136 node
->symbol
.in_other_partition
= 1;
137 if (cgraph_dump_file
)
138 fprintf (cgraph_dump_file
, "Node %s/%i now used in multiple partitions\n",
139 cgraph_node_name (node
), node
->uid
);
141 node
->symbol
.aux
= (void *)((size_t)node
->symbol
.aux
+ 1);
142 cgraph_node_set_add (part
->cgraph_set
, node
);
146 /* Add NODE to partition as well as the inline callees and referred comdats into partition PART. */
149 add_cgraph_node_to_partition (ltrans_partition part
, struct cgraph_node
*node
)
151 struct cgraph_edge
*e
;
152 cgraph_node_set_iterator csi
;
153 struct cgraph_node
*n
;
155 /* If NODE is already there, we have nothing to do. */
156 csi
= cgraph_node_set_find (part
->cgraph_set
, node
);
157 if (!csi_end_p (csi
))
160 cgraph_for_node_thunks_and_aliases (node
, add_cgraph_node_to_partition_1
, part
, true);
162 part
->insns
+= inline_summary (node
)->self_size
;
165 cgraph_node_set_add (part
->cgraph_set
, node
);
167 for (e
= node
->callees
; e
; e
= e
->next_callee
)
168 if ((!e
->inline_failed
169 || DECL_COMDAT (cgraph_function_node (e
->callee
, NULL
)->symbol
.decl
))
170 && !cgraph_node_in_set_p (e
->callee
, part
->cgraph_set
))
171 add_cgraph_node_to_partition (part
, e
->callee
);
173 /* The only way to assemble non-weakref alias is to add the aliased object into
175 add_references_to_partition (part
, &node
->symbol
.ref_list
);
176 n
= cgraph_function_node (node
, NULL
);
178 && !lookup_attribute ("weakref",
179 DECL_ATTRIBUTES (node
->symbol
.decl
)))
180 add_cgraph_node_to_partition (part
, n
);
182 if (node
->symbol
.same_comdat_group
)
183 for (n
= cgraph (node
->symbol
.same_comdat_group
);
184 n
!= node
; n
= cgraph (n
->symbol
.same_comdat_group
))
185 add_cgraph_node_to_partition (part
, n
);
188 /* Add VNODE to partition as well as comdat references partition PART. */
191 add_varpool_node_to_partition (ltrans_partition part
, struct varpool_node
*vnode
)
193 varpool_node_set_iterator vsi
;
194 struct varpool_node
*v
;
196 /* If NODE is already there, we have nothing to do. */
197 vsi
= varpool_node_set_find (part
->varpool_set
, vnode
);
198 if (!vsi_end_p (vsi
))
201 varpool_node_set_add (part
->varpool_set
, vnode
);
203 if (vnode
->symbol
.aux
)
205 vnode
->symbol
.in_other_partition
= 1;
206 if (cgraph_dump_file
)
207 fprintf (cgraph_dump_file
, "Varpool node %s now used in multiple partitions\n",
208 varpool_node_name (vnode
));
210 vnode
->symbol
.aux
= (void *)((size_t)vnode
->symbol
.aux
+ 1);
212 /* The only way to assemble non-weakref alias is to add the aliased object into
214 v
= varpool_variable_node (vnode
, NULL
);
216 && !lookup_attribute ("weakref",
217 DECL_ATTRIBUTES (vnode
->symbol
.decl
)))
218 add_varpool_node_to_partition (part
, v
);
220 add_references_to_partition (part
, &vnode
->symbol
.ref_list
);
222 if (vnode
->symbol
.same_comdat_group
223 && !varpool_node_in_set_p (varpool (vnode
->symbol
.same_comdat_group
),
225 add_varpool_node_to_partition (part
, varpool (vnode
->symbol
.same_comdat_group
));
228 /* Undo all additions until number of cgraph nodes in PARITION is N_CGRAPH_NODES
229 and number of varpool nodes is N_VARPOOL_NODES. */
232 undo_partition (ltrans_partition partition
, unsigned int n_cgraph_nodes
,
233 unsigned int n_varpool_nodes
)
235 while (VEC_length (cgraph_node_ptr
, partition
->cgraph_set
->nodes
) >
238 struct cgraph_node
*node
= VEC_index (cgraph_node_ptr
,
239 partition
->cgraph_set
->nodes
,
241 partition
->insns
-= inline_summary (node
)->self_size
;
242 cgraph_node_set_remove (partition
->cgraph_set
, node
);
243 node
->symbol
.aux
= (void *)((size_t)node
->symbol
.aux
- 1);
245 while (VEC_length (varpool_node_ptr
, partition
->varpool_set
->nodes
) >
248 struct varpool_node
*node
= VEC_index (varpool_node_ptr
,
249 partition
->varpool_set
->nodes
,
251 varpool_node_set_remove (partition
->varpool_set
, node
);
252 node
->symbol
.aux
= (void *)((size_t)node
->symbol
.aux
- 1);
256 /* Return true if NODE should be partitioned.
257 This means that partitioning algorithm should put NODE into one of partitions.
258 This apply to most functions with bodies. Functions that are not partitions
259 are put into every unit needing them. This is the case of i.e. COMDATs. */
262 partition_cgraph_node_p (struct cgraph_node
*node
)
264 /* We will get proper partition based on function they are inlined to. */
265 if (node
->global
.inlined_to
)
267 /* Nodes without a body do not need partitioning. */
270 /* Extern inlines and comdat are always only in partitions they are needed. */
271 if (DECL_EXTERNAL (node
->symbol
.decl
)
272 || (DECL_COMDAT (node
->symbol
.decl
)
273 && !node
->symbol
.force_output
274 && !symtab_used_from_object_file_p ((symtab_node
) node
)))
276 if (lookup_attribute ("weakref", DECL_ATTRIBUTES (node
->symbol
.decl
)))
281 /* Return true if VNODE should be partitioned.
282 This means that partitioning algorithm should put VNODE into one of partitions. */
285 partition_varpool_node_p (struct varpool_node
*vnode
)
287 if (vnode
->alias
|| !vnode
->analyzed
)
289 /* Constant pool and comdat are always only in partitions they are needed. */
290 if (DECL_IN_CONSTANT_POOL (vnode
->symbol
.decl
)
291 || DECL_EXTERNAL (vnode
->symbol
.decl
)
292 || (DECL_COMDAT (vnode
->symbol
.decl
)
293 && !vnode
->symbol
.force_output
294 && !symtab_used_from_object_file_p ((symtab_node
) vnode
)))
296 if (lookup_attribute ("weakref", DECL_ATTRIBUTES (vnode
->symbol
.decl
)))
301 /* Group cgrah nodes by input files. This is used mainly for testing
305 lto_1_to_1_map (void)
307 struct cgraph_node
*node
;
308 struct varpool_node
*vnode
;
309 struct lto_file_decl_data
*file_data
;
310 struct pointer_map_t
*pmap
;
311 ltrans_partition partition
;
315 timevar_push (TV_WHOPR_WPA
);
317 pmap
= pointer_map_create ();
319 FOR_EACH_DEFINED_FUNCTION (node
)
321 if (!partition_cgraph_node_p (node
)
325 file_data
= node
->symbol
.lto_file_data
;
329 slot
= pointer_map_contains (pmap
, file_data
);
331 partition
= (ltrans_partition
) *slot
;
334 partition
= new_partition (file_data
->file_name
);
335 slot
= pointer_map_insert (pmap
, file_data
);
341 && VEC_length (ltrans_partition
, ltrans_partitions
))
342 partition
= VEC_index (ltrans_partition
, ltrans_partitions
, 0);
345 partition
= new_partition ("");
346 slot
= pointer_map_insert (pmap
, NULL
);
351 add_cgraph_node_to_partition (partition
, node
);
354 FOR_EACH_VARIABLE (vnode
)
356 if (!partition_varpool_node_p (vnode
)
357 || vnode
->symbol
.aux
)
359 file_data
= vnode
->symbol
.lto_file_data
;
360 slot
= pointer_map_contains (pmap
, file_data
);
362 partition
= (ltrans_partition
) *slot
;
365 partition
= new_partition (file_data
->file_name
);
366 slot
= pointer_map_insert (pmap
, file_data
);
371 add_varpool_node_to_partition (partition
, vnode
);
373 FOR_EACH_FUNCTION (node
)
374 node
->symbol
.aux
= NULL
;
375 FOR_EACH_VARIABLE (vnode
)
376 vnode
->symbol
.aux
= NULL
;
378 /* If the cgraph is empty, create one cgraph node set so that there is still
379 an output file for any variables that need to be exported in a DSO. */
381 new_partition ("empty");
383 pointer_map_destroy (pmap
);
385 timevar_pop (TV_WHOPR_WPA
);
387 lto_stats
.num_cgraph_partitions
+= VEC_length (ltrans_partition
,
391 /* Helper function for qsort; sort nodes by order. */
393 node_cmp (const void *pa
, const void *pb
)
395 const struct cgraph_node
*a
= *(const struct cgraph_node
* const *) pa
;
396 const struct cgraph_node
*b
= *(const struct cgraph_node
* const *) pb
;
397 return b
->symbol
.order
- a
->symbol
.order
;
400 /* Helper function for qsort; sort nodes by order. */
402 varpool_node_cmp (const void *pa
, const void *pb
)
404 const struct varpool_node
*a
= *(const struct varpool_node
* const *) pa
;
405 const struct varpool_node
*b
= *(const struct varpool_node
* const *) pb
;
406 return b
->symbol
.order
- a
->symbol
.order
;
409 /* Group cgraph nodes into equally-sized partitions.
411 The partitioning algorithm is simple: nodes are taken in predefined order.
412 The order corresponds to the order we want functions to have in the final
413 output. In the future this will be given by function reordering pass, but
414 at the moment we use the topological order, which is a good approximation.
416 The goal is to partition this linear order into intervals (partitions) so
417 that all the partitions have approximately the same size and the number of
418 callgraph or IPA reference edges crossing boundaries is minimal.
420 This is a lot faster (O(n) in size of callgraph) than algorithms doing
421 priority-based graph clustering that are generally O(n^2) and, since
422 WHOPR is designed to make things go well across partitions, it leads
425 We compute the expected size of a partition as:
427 max (total_size / lto_partitions, min_partition_size)
429 We use dynamic expected size of partition so small programs are partitioned
430 into enough partitions to allow use of multiple CPUs, while large programs
431 are not partitioned too much. Creating too many partitions significantly
432 increases the streaming overhead.
434 In the future, we would like to bound the maximal size of partitions so as
435 to prevent the LTRANS stage from consuming too much memory. At the moment,
436 however, the WPA stage is the most memory intensive for large benchmarks,
437 since too many types and declarations are read into memory.
439 The function implements a simple greedy algorithm. Nodes are being added
440 to the current partition until after 3/4 of the expected partition size is
441 reached. Past this threshold, we keep track of boundary size (number of
442 edges going to other partitions) and continue adding functions until after
443 the current partition has grown to twice the expected partition size. Then
444 the process is undone to the point where the minimal ratio of boundary size
445 and in-partition calls was reached. */
448 lto_balanced_map (void)
451 int n_varpool_nodes
= 0, varpool_pos
= 0;
452 struct cgraph_node
**postorder
=
453 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
454 struct cgraph_node
**order
= XNEWVEC (struct cgraph_node
*, cgraph_max_uid
);
455 struct varpool_node
**varpool_order
= NULL
;
456 int i
, postorder_len
;
457 struct cgraph_node
*node
;
458 int total_size
= 0, best_total_size
= 0;
460 ltrans_partition partition
;
461 unsigned int last_visited_cgraph_node
= 0, last_visited_varpool_node
= 0;
462 struct varpool_node
*vnode
;
463 int cost
= 0, internal
= 0;
464 int best_n_nodes
= 0, best_n_varpool_nodes
= 0, best_i
= 0, best_cost
=
465 INT_MAX
, best_internal
= 0;
467 int current_order
= -1;
469 FOR_EACH_VARIABLE (vnode
)
470 gcc_assert (!vnode
->symbol
.aux
);
471 /* Until we have better ordering facility, use toplogical order.
472 Include only nodes we will partition and compute estimate of program
473 size. Note that since nodes that are not partitioned might be put into
474 multiple partitions, this is just an estimate of real size. This is why
475 we keep partition_size updated after every partition is finalized. */
476 postorder_len
= ipa_reverse_postorder (postorder
);
478 for (i
= 0; i
< postorder_len
; i
++)
481 if (partition_cgraph_node_p (node
))
483 order
[n_nodes
++] = node
;
484 total_size
+= inline_summary (node
)->size
;
489 if (!flag_toplevel_reorder
)
491 qsort (order
, n_nodes
, sizeof (struct cgraph_node
*), node_cmp
);
493 FOR_EACH_VARIABLE (vnode
)
494 if (partition_varpool_node_p (vnode
))
496 varpool_order
= XNEWVEC (struct varpool_node
*, n_varpool_nodes
);
499 FOR_EACH_VARIABLE (vnode
)
500 if (partition_varpool_node_p (vnode
))
501 varpool_order
[n_varpool_nodes
++] = vnode
;
502 qsort (varpool_order
, n_varpool_nodes
, sizeof (struct varpool_node
*),
506 /* Compute partition size and create the first partition. */
507 partition_size
= total_size
/ PARAM_VALUE (PARAM_LTO_PARTITIONS
);
508 if (partition_size
< PARAM_VALUE (MIN_PARTITION_SIZE
))
509 partition_size
= PARAM_VALUE (MIN_PARTITION_SIZE
);
511 partition
= new_partition ("");
512 if (cgraph_dump_file
)
513 fprintf (cgraph_dump_file
, "Total unit size: %i, partition size: %i\n",
514 total_size
, partition_size
);
516 for (i
= 0; i
< n_nodes
; i
++)
518 if (order
[i
]->symbol
.aux
)
521 current_order
= order
[i
]->symbol
.order
;
523 if (!flag_toplevel_reorder
)
524 while (varpool_pos
< n_varpool_nodes
525 && varpool_order
[varpool_pos
]->symbol
.order
< current_order
)
527 if (!varpool_order
[varpool_pos
]->symbol
.aux
)
528 add_varpool_node_to_partition (partition
, varpool_order
[varpool_pos
]);
532 add_cgraph_node_to_partition (partition
, order
[i
]);
533 total_size
-= inline_summary (order
[i
])->size
;
536 /* Once we added a new node to the partition, we also want to add
537 all referenced variables unless they was already added into some
539 add_cgraph_node_to_partition adds possibly multiple nodes and
540 variables that are needed to satisfy needs of ORDER[i].
541 We remember last visited cgraph and varpool node from last iteration
542 of outer loop that allows us to process every new addition.
544 At the same time we compute size of the boundary into COST. Every
545 callgraph or IPA reference edge leaving the partition contributes into
546 COST. Every edge inside partition was earlier computed as one leaving
547 it and thus we need to subtract it from COST. */
548 while (last_visited_cgraph_node
<
549 VEC_length (cgraph_node_ptr
, partition
->cgraph_set
->nodes
)
550 || last_visited_varpool_node
< VEC_length (varpool_node_ptr
,
551 partition
->varpool_set
->
554 struct ipa_ref_list
*refs
;
557 bool cgraph_p
= false;
559 if (last_visited_cgraph_node
<
560 VEC_length (cgraph_node_ptr
, partition
->cgraph_set
->nodes
))
562 struct cgraph_edge
*edge
;
565 node
= VEC_index (cgraph_node_ptr
, partition
->cgraph_set
->nodes
,
566 last_visited_cgraph_node
);
567 refs
= &node
->symbol
.ref_list
;
569 last_visited_cgraph_node
++;
571 gcc_assert (node
->analyzed
);
573 /* Compute boundary cost of callgraph edges. */
574 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
575 if (edge
->callee
->analyzed
)
577 int edge_cost
= edge
->frequency
;
578 cgraph_node_set_iterator csi
;
582 gcc_assert (edge_cost
> 0);
583 csi
= cgraph_node_set_find (partition
->cgraph_set
, edge
->callee
);
585 && csi
.index
< last_visited_cgraph_node
- 1)
586 cost
-= edge_cost
, internal
+= edge_cost
;
590 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
592 int edge_cost
= edge
->frequency
;
593 cgraph_node_set_iterator csi
;
595 gcc_assert (edge
->caller
->analyzed
);
598 gcc_assert (edge_cost
> 0);
599 csi
= cgraph_node_set_find (partition
->cgraph_set
, edge
->caller
);
601 && csi
.index
< last_visited_cgraph_node
)
610 &VEC_index (varpool_node_ptr
, partition
->varpool_set
->nodes
,
611 last_visited_varpool_node
)->symbol
.ref_list
;
612 last_visited_varpool_node
++;
615 /* Compute boundary cost of IPA REF edges and at the same time look into
616 variables referenced from current partition and try to add them. */
617 for (j
= 0; ipa_ref_list_reference_iterate (refs
, j
, ref
); j
++)
618 if (symtab_variable_p (ref
->referred
))
620 varpool_node_set_iterator vsi
;
622 vnode
= ipa_ref_varpool_node (ref
);
623 if (!vnode
->finalized
)
625 if (!vnode
->symbol
.aux
&& flag_toplevel_reorder
626 && partition_varpool_node_p (vnode
))
627 add_varpool_node_to_partition (partition
, vnode
);
628 vsi
= varpool_node_set_find (partition
->varpool_set
, vnode
);
630 && vsi
.index
< last_visited_varpool_node
- !cgraph_p
)
637 cgraph_node_set_iterator csi
;
639 node
= ipa_ref_node (ref
);
642 csi
= cgraph_node_set_find (partition
->cgraph_set
, node
);
644 && csi
.index
< last_visited_cgraph_node
- cgraph_p
)
649 for (j
= 0; ipa_ref_list_referring_iterate (refs
, j
, ref
); j
++)
650 if (symtab_variable_p (ref
->referring
))
652 varpool_node_set_iterator vsi
;
654 vnode
= ipa_ref_referring_varpool_node (ref
);
655 gcc_assert (vnode
->finalized
);
656 if (!vnode
->symbol
.aux
&& flag_toplevel_reorder
657 && partition_varpool_node_p (vnode
))
658 add_varpool_node_to_partition (partition
, vnode
);
659 vsi
= varpool_node_set_find (partition
->varpool_set
, vnode
);
661 && vsi
.index
< last_visited_varpool_node
)
668 cgraph_node_set_iterator csi
;
670 node
= ipa_ref_referring_node (ref
);
671 gcc_assert (node
->analyzed
);
672 csi
= cgraph_node_set_find (partition
->cgraph_set
, node
);
674 && csi
.index
< last_visited_cgraph_node
)
681 /* If the partition is large enough, start looking for smallest boundary cost. */
682 if (partition
->insns
< partition_size
* 3 / 4
683 || best_cost
== INT_MAX
685 || (best_internal
* (HOST_WIDE_INT
) cost
686 > (internal
* (HOST_WIDE_INT
)best_cost
)))
687 && partition
->insns
< partition_size
* 5 / 4))
690 best_internal
= internal
;
692 best_n_nodes
= VEC_length (cgraph_node_ptr
,
693 partition
->cgraph_set
->nodes
);
694 best_n_varpool_nodes
= VEC_length (varpool_node_ptr
,
695 partition
->varpool_set
->nodes
);
696 best_total_size
= total_size
;
698 if (cgraph_dump_file
)
699 fprintf (cgraph_dump_file
, "Step %i: added %s/%i, size %i, cost %i/%i best %i/%i, step %i\n", i
,
700 cgraph_node_name (order
[i
]), order
[i
]->uid
, partition
->insns
, cost
, internal
,
701 best_cost
, best_internal
, best_i
);
702 /* Partition is too large, unwind into step when best cost was reached and
703 start new partition. */
704 if (partition
->insns
> 2 * partition_size
)
708 if (cgraph_dump_file
)
709 fprintf (cgraph_dump_file
, "Unwinding %i insertions to step %i\n",
711 undo_partition (partition
, best_n_nodes
, best_n_varpool_nodes
);
714 /* When we are finished, avoid creating empty partition. */
715 while (i
< n_nodes
- 1 && order
[i
+ 1]->symbol
.aux
)
717 if (i
== n_nodes
- 1)
719 partition
= new_partition ("");
720 last_visited_cgraph_node
= 0;
721 last_visited_varpool_node
= 0;
722 total_size
= best_total_size
;
725 if (cgraph_dump_file
)
726 fprintf (cgraph_dump_file
, "New partition\n");
728 best_n_varpool_nodes
= 0;
731 /* Since the size of partitions is just approximate, update the size after
732 we finished current one. */
733 if (npartitions
< PARAM_VALUE (PARAM_LTO_PARTITIONS
))
734 partition_size
= total_size
735 / (PARAM_VALUE (PARAM_LTO_PARTITIONS
) - npartitions
);
737 partition_size
= INT_MAX
;
739 if (partition_size
< PARAM_VALUE (MIN_PARTITION_SIZE
))
740 partition_size
= PARAM_VALUE (MIN_PARTITION_SIZE
);
745 /* Varables that are not reachable from the code go into last partition. */
746 if (flag_toplevel_reorder
)
748 FOR_EACH_VARIABLE (vnode
)
749 if (partition_varpool_node_p (vnode
) && !vnode
->symbol
.aux
)
750 add_varpool_node_to_partition (partition
, vnode
);
754 while (varpool_pos
< n_varpool_nodes
)
756 if (!varpool_order
[varpool_pos
]->symbol
.aux
)
757 add_varpool_node_to_partition (partition
, varpool_order
[varpool_pos
]);
760 free (varpool_order
);
765 /* Promote variable VNODE to be static. */
768 promote_var (struct varpool_node
*vnode
)
770 if (TREE_PUBLIC (vnode
->symbol
.decl
) || DECL_EXTERNAL (vnode
->symbol
.decl
))
772 gcc_assert (flag_wpa
);
773 TREE_PUBLIC (vnode
->symbol
.decl
) = 1;
774 DECL_VISIBILITY (vnode
->symbol
.decl
) = VISIBILITY_HIDDEN
;
775 DECL_VISIBILITY_SPECIFIED (vnode
->symbol
.decl
) = true;
776 if (cgraph_dump_file
)
777 fprintf (cgraph_dump_file
,
778 "Promoting var as hidden: %s\n", varpool_node_name (vnode
));
782 /* Promote function NODE to be static. */
785 promote_fn (struct cgraph_node
*node
)
787 gcc_assert (flag_wpa
);
788 if (TREE_PUBLIC (node
->symbol
.decl
) || DECL_EXTERNAL (node
->symbol
.decl
))
790 TREE_PUBLIC (node
->symbol
.decl
) = 1;
791 DECL_VISIBILITY (node
->symbol
.decl
) = VISIBILITY_HIDDEN
;
792 DECL_VISIBILITY_SPECIFIED (node
->symbol
.decl
) = true;
793 if (cgraph_dump_file
)
794 fprintf (cgraph_dump_file
,
795 "Promoting function as hidden: %s/%i\n",
796 cgraph_node_name (node
), node
->uid
);
800 /* Return if LIST contain references from other partitions.
801 TODO: remove this once lto partitioning is using encoders. */
804 set_referenced_from_other_partition_p (struct ipa_ref_list
*list
, cgraph_node_set set
,
805 varpool_node_set vset
)
809 for (i
= 0; ipa_ref_list_referring_iterate (list
, i
, ref
); i
++)
811 if (symtab_function_p (ref
->referring
))
813 if (ipa_ref_referring_node (ref
)->symbol
.in_other_partition
814 || !cgraph_node_in_set_p (ipa_ref_referring_node (ref
), set
))
819 if (ipa_ref_referring_varpool_node (ref
)->symbol
.in_other_partition
820 || !varpool_node_in_set_p (ipa_ref_referring_varpool_node (ref
),
828 /* Return true when node is reachable from other partition.
829 TODO: remove this once lto partitioning is using encoders. */
832 set_reachable_from_other_partition_p (struct cgraph_node
*node
, cgraph_node_set set
)
834 struct cgraph_edge
*e
;
837 if (node
->global
.inlined_to
)
839 for (e
= node
->callers
; e
; e
= e
->next_caller
)
840 if (e
->caller
->symbol
.in_other_partition
841 || !cgraph_node_in_set_p (e
->caller
, set
))
847 /* Return if LIST contain references from other partitions.
848 TODO: remove this once lto partitioning is using encoders. */
851 set_referenced_from_this_partition_p (struct ipa_ref_list
*list
, cgraph_node_set set
,
852 varpool_node_set vset
)
856 for (i
= 0; ipa_ref_list_referring_iterate (list
, i
, ref
); i
++)
858 if (symtab_function_p (ref
->referring
))
860 if (cgraph_node_in_set_p (ipa_ref_referring_node (ref
), set
))
865 if (varpool_node_in_set_p (ipa_ref_referring_varpool_node (ref
),
873 /* Find out all static decls that need to be promoted to global because
874 of cross file sharing. This function must be run in the WPA mode after
875 all inlinees are added. */
878 lto_promote_cross_file_statics (void)
880 struct varpool_node
*vnode
;
883 varpool_node_set vset
;
884 cgraph_node_set_iterator csi
;
885 varpool_node_set_iterator vsi
;
886 VEC(varpool_node_ptr
, heap
) *promoted_initializers
= NULL
;
887 struct pointer_set_t
*inserted
= pointer_set_create ();
889 gcc_assert (flag_wpa
);
891 n_sets
= VEC_length (ltrans_partition
, ltrans_partitions
);
892 for (i
= 0; i
< n_sets
; i
++)
894 ltrans_partition part
895 = VEC_index (ltrans_partition
, ltrans_partitions
, i
);
896 set
= part
->cgraph_set
;
897 vset
= part
->varpool_set
;
899 /* If node called or referred to from other partition, it needs to be
901 for (csi
= csi_start (set
); !csi_end_p (csi
); csi_next (&csi
))
903 struct cgraph_node
*node
= csi_node (csi
);
904 if (node
->symbol
.externally_visible
)
906 if (node
->global
.inlined_to
)
908 if ((!DECL_EXTERNAL (node
->symbol
.decl
)
909 && !DECL_COMDAT (node
->symbol
.decl
))
910 && (set_referenced_from_other_partition_p (&node
->symbol
.ref_list
, set
, vset
)
911 || set_reachable_from_other_partition_p (node
, set
)))
914 for (vsi
= vsi_start (vset
); !vsi_end_p (vsi
); vsi_next (&vsi
))
916 vnode
= vsi_node (vsi
);
917 /* Constant pool references use internal labels and thus can not
918 be made global. It is sensible to keep those ltrans local to
919 allow better optimization. */
920 if (!DECL_IN_CONSTANT_POOL (vnode
->symbol
.decl
)
921 && !DECL_EXTERNAL (vnode
->symbol
.decl
)
922 && !DECL_COMDAT (vnode
->symbol
.decl
)
923 && !vnode
->symbol
.externally_visible
&& vnode
->analyzed
924 && set_referenced_from_other_partition_p (&vnode
->symbol
.ref_list
,
929 /* We export the initializer of a read-only var into each partition
930 referencing the var. Folding might take declarations from the
931 initializer and use them, so everything referenced from the
932 initializer can be accessed from this partition after folding.
934 This means that we need to promote all variables and functions
935 referenced from all initializers of read-only vars referenced
936 from this partition that are not in this partition. This needs
937 to be done recursively. */
938 FOR_EACH_VARIABLE (vnode
)
939 if (const_value_known_p (vnode
->symbol
.decl
)
940 && DECL_INITIAL (vnode
->symbol
.decl
)
941 && !varpool_node_in_set_p (vnode
, vset
)
942 && set_referenced_from_this_partition_p (&vnode
->symbol
.ref_list
, set
, vset
)
943 && !pointer_set_insert (inserted
, vnode
))
944 VEC_safe_push (varpool_node_ptr
, heap
, promoted_initializers
, vnode
);
946 while (!VEC_empty (varpool_node_ptr
, promoted_initializers
))
951 vnode
= VEC_pop (varpool_node_ptr
, promoted_initializers
);
953 ipa_ref_list_reference_iterate (&vnode
->symbol
.ref_list
, i
, ref
);
956 if (symtab_function_p (ref
->referred
))
958 struct cgraph_node
*n
= ipa_ref_node (ref
);
959 gcc_assert (!n
->global
.inlined_to
);
960 if (!n
->symbol
.externally_visible
961 && !cgraph_node_in_set_p (n
, set
))
966 struct varpool_node
*v
= ipa_ref_varpool_node (ref
);
967 if (varpool_node_in_set_p (v
, vset
))
970 /* Constant pool references use internal labels and thus
971 cannot be made global. It is sensible to keep those
972 ltrans local to allow better optimization.
973 Similarly we ship external vars initializers into
974 every ltrans unit possibly referring to it. */
975 if (DECL_IN_CONSTANT_POOL (v
->symbol
.decl
)
976 || DECL_EXTERNAL (v
->symbol
.decl
))
978 if (!pointer_set_insert (inserted
, vnode
))
979 VEC_safe_push (varpool_node_ptr
, heap
,
980 promoted_initializers
, v
);
982 else if (!v
->symbol
.externally_visible
&& v
->analyzed
)
985 && DECL_INITIAL (v
->symbol
.decl
)
986 && const_value_known_p (v
->symbol
.decl
)
987 && !pointer_set_insert (inserted
, vnode
))
988 VEC_safe_push (varpool_node_ptr
, heap
,
989 promoted_initializers
, v
);
995 pointer_set_destroy (inserted
);