1/* LTO partitioning logic routines. 2 Copyright (C) 2009-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING3. If not see 18<http://www.gnu.org/licenses/>. */ 19 20#include "config.h" 21#include "system.h" 22#include "coretypes.h" 23#include "toplev.h" 24#include "hash-set.h" 25#include "machmode.h" 26#include "vec.h" 27#include "double-int.h" 28#include "input.h" 29#include "alias.h" 30#include "symtab.h" 31#include "options.h" 32#include "wide-int.h" 33#include "inchash.h" 34#include "tree.h" 35#include "fold-const.h" 36#include "predict.h" 37#include "tm.h" 38#include "hard-reg-set.h" 39#include "input.h" 40#include "function.h" 41#include "basic-block.h" 42#include "tree-ssa-alias.h" 43#include "internal-fn.h" 44#include "gimple-expr.h" 45#include "is-a.h" 46#include "gimple.h" 47#include "hash-map.h" 48#include "plugin-api.h" 49#include "ipa-ref.h" 50#include "cgraph.h" 51#include "lto-streamer.h" 52#include "timevar.h" 53#include "params.h" 54#include "alloc-pool.h" 55#include "symbol-summary.h" 56#include "ipa-prop.h" 57#include "ipa-inline.h" 58#include "ipa-utils.h" 59#include "lto-partition.h" 60#include "stringpool.h" 61 62vec<ltrans_partition> ltrans_partitions; 63 64static void add_symbol_to_partition (ltrans_partition part, symtab_node *node); 65 66 67/* Create new partition with name NAME. */ 68 69static ltrans_partition 70new_partition (const char *name) 71{ 72 ltrans_partition part = XCNEW (struct ltrans_partition_def); 73 part->encoder = lto_symtab_encoder_new (false); 74 part->name = name; 75 part->insns = 0; 76 ltrans_partitions.safe_push (part); 77 return part; 78} 79 80/* Free memory used by ltrans datastructures. */ 81 82void 83free_ltrans_partitions (void) 84{ 85 unsigned int idx; 86 ltrans_partition part; 87 for (idx = 0; ltrans_partitions.iterate (idx, &part); idx++) 88 { 89 if (part->initializers_visited) 90 delete part->initializers_visited; 91 /* Symtab encoder is freed after streaming. */ 92 free (part); 93 } 94 ltrans_partitions.release (); 95} 96 97/* Return true if symbol is already in some partition. */ 98 99static inline bool 100symbol_partitioned_p (symtab_node *node) 101{ 102 return node->aux; 103} 104 105/* Add references into the partition. */ 106static void 107add_references_to_partition (ltrans_partition part, symtab_node *node) 108{ 109 int i; 110 struct ipa_ref *ref = NULL; 111 112 /* Add all duplicated references to the partition. */ 113 for (i = 0; node->iterate_reference (i, ref); i++) 114 if (ref->referred->get_partitioning_class () == SYMBOL_DUPLICATE) 115 add_symbol_to_partition (part, ref->referred); 116 /* References to a readonly variable may be constant foled into its value. 117 Recursively look into the initializers of the constant variable and add 118 references, too. */ 119 else if (is_a <varpool_node *> (ref->referred) 120 && (dyn_cast <varpool_node *> (ref->referred) 121 ->ctor_useable_for_folding_p () 122 || POINTER_BOUNDS_P (ref->referred->decl)) 123 && !lto_symtab_encoder_in_partition_p (part->encoder, ref->referred)) 124 { 125 if (!part->initializers_visited) 126 part->initializers_visited = new hash_set<symtab_node *>; 127 if (!part->initializers_visited->add (ref->referred)) 128 add_references_to_partition (part, ref->referred); 129 } 130} 131 132/* Helper function for add_symbol_to_partition doing the actual dirty work 133 of adding NODE to PART. */ 134 135static bool 136add_symbol_to_partition_1 (ltrans_partition part, symtab_node *node) 137{ 138 enum symbol_partitioning_class c = node->get_partitioning_class (); 139 struct ipa_ref *ref; 140 symtab_node *node1; 141 142 /* If NODE is already there, we have nothing to do. */ 143 if (lto_symtab_encoder_in_partition_p (part->encoder, node)) 144 return true; 145 146 /* non-duplicated aliases or tunks of a duplicated symbol needs to be output 147 just once. 148 149 Be lax about comdats; they may or may not be duplicated and we may 150 end up in need to duplicate keyed comdat because it has unkeyed alias. */ 151 if (c == SYMBOL_PARTITION && !DECL_COMDAT (node->decl) 152 && symbol_partitioned_p (node)) 153 return false; 154 155 /* Be sure that we never try to duplicate partitioned symbol 156 or add external symbol. */ 157 gcc_assert (c != SYMBOL_EXTERNAL 158 && (c == SYMBOL_DUPLICATE || !symbol_partitioned_p (node))); 159 160 lto_set_symtab_encoder_in_partition (part->encoder, node); 161 162 if (symbol_partitioned_p (node)) 163 { 164 node->in_other_partition = 1; 165 if (symtab->dump_file) 166 fprintf (symtab->dump_file, 167 "Symbol node %s now used in multiple partitions\n", 168 node->name ()); 169 } 170 node->aux = (void *)((size_t)node->aux + 1); 171 172 if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node)) 173 { 174 struct cgraph_edge *e; 175 if (!node->alias) 176 part->insns += inline_summaries->get (cnode)->self_size; 177 178 /* Add all inline clones and callees that are duplicated. */ 179 for (e = cnode->callees; e; e = e->next_callee) 180 if (!e->inline_failed) 181 add_symbol_to_partition_1 (part, e->callee); 182 else if (e->callee->get_partitioning_class () == SYMBOL_DUPLICATE) 183 add_symbol_to_partition (part, e->callee); 184 185 /* Add all thunks associated with the function. */ 186 for (e = cnode->callers; e; e = e->next_caller) 187 if (e->caller->thunk.thunk_p) 188 add_symbol_to_partition_1 (part, e->caller); 189 190 /* Instrumented version is actually the same function. 191 Therefore put it into the same partition. */ 192 if (cnode->instrumented_version) 193 add_symbol_to_partition_1 (part, cnode->instrumented_version); 194 } 195 196 add_references_to_partition (part, node); 197 198 /* Add all aliases associated with the symbol. */ 199 200 FOR_EACH_ALIAS (node, ref) 201 if (!node->weakref) 202 add_symbol_to_partition_1 (part, ref->referring); 203 204 /* Ensure that SAME_COMDAT_GROUP lists all allways added in a group. */ 205 if (node->same_comdat_group) 206 for (node1 = node->same_comdat_group; 207 node1 != node; node1 = node1->same_comdat_group) 208 if (!node->alias) 209 { 210 bool added = add_symbol_to_partition_1 (part, node1); 211 gcc_assert (added); 212 } 213 return true; 214} 215 216/* If symbol NODE is really part of other symbol's definition (i.e. it is 217 internal label, thunk, alias or so), return the outer symbol. 218 When add_symbol_to_partition_1 is called on the outer symbol it must 219 eventually add NODE, too. */ 220static symtab_node * 221contained_in_symbol (symtab_node *node) 222{ 223 /* Weakrefs are never contained in anything. */ 224 if (node->weakref) 225 return node; 226 if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node)) 227 { 228 cnode = cnode->function_symbol (); 229 if (cnode->global.inlined_to) 230 cnode = cnode->global.inlined_to; 231 return cnode; 232 } 233 else if (varpool_node *vnode = dyn_cast <varpool_node *> (node)) 234 return vnode->ultimate_alias_target (); 235 return node; 236} 237 238/* Add symbol NODE to partition. When definition of NODE is part 239 of other symbol definition, add the other symbol, too. */ 240 241static void 242add_symbol_to_partition (ltrans_partition part, symtab_node *node) 243{ 244 symtab_node *node1; 245 246 /* Verify that we do not try to duplicate something that can not be. */ 247 gcc_checking_assert (node->get_partitioning_class () == SYMBOL_DUPLICATE 248 || !symbol_partitioned_p (node)); 249 250 while ((node1 = contained_in_symbol (node)) != node) 251 node = node1; 252 253 /* If we have duplicated symbol contained in something we can not duplicate, 254 we are very badly screwed. The other way is possible, so we do not 255 assert this in add_symbol_to_partition_1. 256 257 Be lax about comdats; they may or may not be duplicated and we may 258 end up in need to duplicate keyed comdat because it has unkeyed alias. */ 259 260 gcc_assert (node->get_partitioning_class () == SYMBOL_DUPLICATE 261 || DECL_COMDAT (node->decl) 262 || !symbol_partitioned_p (node)); 263 264 add_symbol_to_partition_1 (part, node); 265} 266 267/* Undo all additions until number of cgraph nodes in PARITION is N_CGRAPH_NODES 268 and number of varpool nodes is N_VARPOOL_NODES. */ 269 270static void 271undo_partition (ltrans_partition partition, unsigned int n_nodes) 272{ 273 while (lto_symtab_encoder_size (partition->encoder) > (int)n_nodes) 274 { 275 symtab_node *node = lto_symtab_encoder_deref (partition->encoder, 276 n_nodes); 277 cgraph_node *cnode; 278 279 /* After UNDO we no longer know what was visited. */ 280 if (partition->initializers_visited) 281 delete partition->initializers_visited; 282 partition->initializers_visited = NULL; 283 284 if (!node->alias && (cnode = dyn_cast <cgraph_node *> (node))) 285 partition->insns -= inline_summaries->get (cnode)->self_size; 286 lto_symtab_encoder_delete_node (partition->encoder, node); 287 node->aux = (void *)((size_t)node->aux - 1); 288 } 289} 290 291/* Group cgrah nodes by input files. This is used mainly for testing 292 right now. */ 293 294void 295lto_1_to_1_map (void) 296{ 297 symtab_node *node; 298 struct lto_file_decl_data *file_data; 299 hash_map<lto_file_decl_data *, ltrans_partition> pmap; 300 ltrans_partition partition; 301 int npartitions = 0; 302 303 FOR_EACH_SYMBOL (node) 304 { 305 if (node->get_partitioning_class () != SYMBOL_PARTITION 306 || symbol_partitioned_p (node)) 307 continue; 308 309 file_data = node->lto_file_data; 310 311 if (file_data) 312 { 313 ltrans_partition *slot = &pmap.get_or_insert (file_data); 314 if (*slot) 315 partition = *slot; 316 else 317 { 318 partition = new_partition (file_data->file_name); 319 *slot = partition; 320 npartitions++; 321 } 322 } 323 else if (!file_data && ltrans_partitions.length ()) 324 partition = ltrans_partitions[0]; 325 else 326 { 327 partition = new_partition (""); 328 pmap.put (NULL, partition); 329 npartitions++; 330 } 331 332 add_symbol_to_partition (partition, node); 333 } 334 335 /* If the cgraph is empty, create one cgraph node set so that there is still 336 an output file for any variables that need to be exported in a DSO. */ 337 if (!npartitions) 338 new_partition ("empty"); 339 340} 341 342/* Maximal partitioning. Put every new symbol into new partition if possible. */ 343 344void 345lto_max_map (void) 346{ 347 symtab_node *node; 348 ltrans_partition partition; 349 int npartitions = 0; 350 351 FOR_EACH_SYMBOL (node) 352 { 353 if (node->get_partitioning_class () != SYMBOL_PARTITION 354 || symbol_partitioned_p (node)) 355 continue; 356 partition = new_partition (node->asm_name ()); 357 add_symbol_to_partition (partition, node); 358 npartitions++; 359 } 360 if (!npartitions) 361 new_partition ("empty"); 362} 363 364/* Helper function for qsort; sort nodes by order. noreorder functions must have 365 been removed earlier. */ 366static int 367node_cmp (const void *pa, const void *pb) 368{ 369 const struct cgraph_node *a = *(const struct cgraph_node * const *) pa; 370 const struct cgraph_node *b = *(const struct cgraph_node * const *) pb; 371 372 /* Profile reorder flag enables function reordering based on first execution 373 of a function. All functions with profile are placed in ascending 374 order at the beginning. */ 375 376 if (flag_profile_reorder_functions) 377 { 378 /* Functions with time profile are sorted in ascending order. */ 379 if (a->tp_first_run && b->tp_first_run) 380 return a->tp_first_run != b->tp_first_run 381 ? a->tp_first_run - b->tp_first_run 382 : a->order - b->order; 383 384 /* Functions with time profile are sorted before the functions 385 that do not have the profile. */ 386 if (a->tp_first_run || b->tp_first_run) 387 return b->tp_first_run - a->tp_first_run; 388 } 389 390 return b->order - a->order; 391} 392 393/* Helper function for qsort; sort nodes by order. */ 394static int 395varpool_node_cmp (const void *pa, const void *pb) 396{ 397 const symtab_node *a = *static_cast<const symtab_node * const *> (pa); 398 const symtab_node *b = *static_cast<const symtab_node * const *> (pb); 399 return b->order - a->order; 400} 401 402/* Add all symtab nodes from NEXT_NODE to PARTITION in order. */ 403 404static void 405add_sorted_nodes (vec<symtab_node *> &next_nodes, ltrans_partition partition) 406{ 407 unsigned i; 408 symtab_node *node; 409 410 next_nodes.qsort (varpool_node_cmp); 411 FOR_EACH_VEC_ELT (next_nodes, i, node) 412 if (!symbol_partitioned_p (node)) 413 add_symbol_to_partition (partition, node); 414} 415 416 417/* Group cgraph nodes into equally-sized partitions. 418 419 The partitioning algorithm is simple: nodes are taken in predefined order. 420 The order corresponds to the order we want functions to have in the final 421 output. In the future this will be given by function reordering pass, but 422 at the moment we use the topological order, which is a good approximation. 423 424 The goal is to partition this linear order into intervals (partitions) so 425 that all the partitions have approximately the same size and the number of 426 callgraph or IPA reference edges crossing boundaries is minimal. 427 428 This is a lot faster (O(n) in size of callgraph) than algorithms doing 429 priority-based graph clustering that are generally O(n^2) and, since 430 WHOPR is designed to make things go well across partitions, it leads 431 to good results. 432 433 We compute the expected size of a partition as: 434 435 max (total_size / lto_partitions, min_partition_size) 436 437 We use dynamic expected size of partition so small programs are partitioned 438 into enough partitions to allow use of multiple CPUs, while large programs 439 are not partitioned too much. Creating too many partitions significantly 440 increases the streaming overhead. 441 442 In the future, we would like to bound the maximal size of partitions so as 443 to prevent the LTRANS stage from consuming too much memory. At the moment, 444 however, the WPA stage is the most memory intensive for large benchmarks, 445 since too many types and declarations are read into memory. 446 447 The function implements a simple greedy algorithm. Nodes are being added 448 to the current partition until after 3/4 of the expected partition size is 449 reached. Past this threshold, we keep track of boundary size (number of 450 edges going to other partitions) and continue adding functions until after 451 the current partition has grown to twice the expected partition size. Then 452 the process is undone to the point where the minimal ratio of boundary size 453 and in-partition calls was reached. */ 454 455void 456lto_balanced_map (int n_lto_partitions) 457{ 458 int n_nodes = 0; 459 int n_varpool_nodes = 0, varpool_pos = 0, best_varpool_pos = 0; 460 struct cgraph_node **order = XNEWVEC (cgraph_node *, symtab->cgraph_max_uid); 461 auto_vec<cgraph_node *> noreorder; 462 auto_vec<varpool_node *> varpool_order; 463 int i; 464 struct cgraph_node *node; 465 int total_size = 0, best_total_size = 0; 466 int partition_size; 467 ltrans_partition partition; 468 int last_visited_node = 0; 469 varpool_node *vnode; 470 int cost = 0, internal = 0; 471 int best_n_nodes = 0, best_i = 0, best_cost = 472 INT_MAX, best_internal = 0; 473 int npartitions; 474 int current_order = -1; 475 int noreorder_pos = 0; 476 477 FOR_EACH_VARIABLE (vnode) 478 gcc_assert (!vnode->aux); 479 480 FOR_EACH_DEFINED_FUNCTION (node) 481 if (node->get_partitioning_class () == SYMBOL_PARTITION) 482 { 483 if (node->no_reorder) 484 noreorder.safe_push (node); 485 else 486 order[n_nodes++] = node; 487 if (!node->alias) 488 total_size += inline_summaries->get (node)->size; 489 } 490 491 /* Streaming works best when the source units do not cross partition 492 boundaries much. This is because importing function from a source 493 unit tends to import a lot of global trees defined there. We should 494 get better about minimizing the function bounday, but until that 495 things works smoother if we order in source order. */ 496 qsort (order, n_nodes, sizeof (struct cgraph_node *), node_cmp); 497 noreorder.qsort (node_cmp); 498 499 if (symtab->dump_file) 500 { 501 for(i = 0; i < n_nodes; i++) 502 fprintf (symtab->dump_file, "Balanced map symbol order:%s:%u\n", 503 order[i]->name (), order[i]->tp_first_run); 504 for(i = 0; i < (int)noreorder.length(); i++) 505 fprintf (symtab->dump_file, "Balanced map symbol no_reorder:%s:%u\n", 506 noreorder[i]->name (), noreorder[i]->tp_first_run); 507 } 508 509 /* Collect all variables that should not be reordered. */ 510 FOR_EACH_VARIABLE (vnode) 511 if (vnode->get_partitioning_class () == SYMBOL_PARTITION 512 && (!flag_toplevel_reorder || vnode->no_reorder)) 513 varpool_order.safe_push (vnode); 514 n_varpool_nodes = varpool_order.length (); 515 varpool_order.qsort (varpool_node_cmp); 516 517 /* Compute partition size and create the first partition. */ 518 partition_size = total_size / n_lto_partitions; 519 if (partition_size < PARAM_VALUE (MIN_PARTITION_SIZE)) 520 partition_size = PARAM_VALUE (MIN_PARTITION_SIZE); 521 npartitions = 1; 522 partition = new_partition (""); 523 if (symtab->dump_file) 524 fprintf (symtab->dump_file, "Total unit size: %i, partition size: %i\n", 525 total_size, partition_size); 526 527 auto_vec<symtab_node *> next_nodes; 528 529 for (i = 0; i < n_nodes; i++) 530 { 531 if (symbol_partitioned_p (order[i])) 532 continue; 533 534 current_order = order[i]->order; 535 536 /* Output noreorder and varpool in program order first. */ 537 next_nodes.truncate (0); 538 while (varpool_pos < n_varpool_nodes 539 && varpool_order[varpool_pos]->order < current_order) 540 next_nodes.safe_push (varpool_order[varpool_pos++]); 541 while (noreorder_pos < (int)noreorder.length () 542 && noreorder[noreorder_pos]->order < current_order) 543 { 544 if (!noreorder[noreorder_pos]->alias) 545 total_size -= inline_summaries->get (noreorder[noreorder_pos])->size; 546 next_nodes.safe_push (noreorder[noreorder_pos++]); 547 } 548 add_sorted_nodes (next_nodes, partition); 549 550 add_symbol_to_partition (partition, order[i]); 551 if (!order[i]->alias) 552 total_size -= inline_summaries->get (order[i])->size; 553 554 555 /* Once we added a new node to the partition, we also want to add 556 all referenced variables unless they was already added into some 557 earlier partition. 558 add_symbol_to_partition adds possibly multiple nodes and 559 variables that are needed to satisfy needs of ORDER[i]. 560 We remember last visited cgraph and varpool node from last iteration 561 of outer loop that allows us to process every new addition. 562 563 At the same time we compute size of the boundary into COST. Every 564 callgraph or IPA reference edge leaving the partition contributes into 565 COST. Every edge inside partition was earlier computed as one leaving 566 it and thus we need to subtract it from COST. */ 567 while (last_visited_node < lto_symtab_encoder_size (partition->encoder)) 568 { 569 symtab_node *refs_node; 570 int j; 571 struct ipa_ref *ref = NULL; 572 symtab_node *snode = lto_symtab_encoder_deref (partition->encoder, 573 last_visited_node); 574 575 if (cgraph_node *node = dyn_cast <cgraph_node *> (snode)) 576 { 577 struct cgraph_edge *edge; 578 579 refs_node = node; 580 581 last_visited_node++; 582 583 gcc_assert (node->definition || node->weakref); 584 585 /* Compute boundary cost of callgraph edges. */ 586 for (edge = node->callees; edge; edge = edge->next_callee) 587 if (edge->callee->definition) 588 { 589 int edge_cost = edge->frequency; 590 int index; 591 592 if (!edge_cost) 593 edge_cost = 1; 594 gcc_assert (edge_cost > 0); 595 index = lto_symtab_encoder_lookup (partition->encoder, 596 edge->callee); 597 if (index != LCC_NOT_FOUND 598 && index < last_visited_node - 1) 599 cost -= edge_cost, internal += edge_cost; 600 else 601 cost += edge_cost; 602 } 603 for (edge = node->callers; edge; edge = edge->next_caller) 604 { 605 int edge_cost = edge->frequency; 606 int index; 607 608 gcc_assert (edge->caller->definition); 609 if (!edge_cost) 610 edge_cost = 1; 611 gcc_assert (edge_cost > 0); 612 index = lto_symtab_encoder_lookup (partition->encoder, 613 edge->caller); 614 if (index != LCC_NOT_FOUND 615 && index < last_visited_node - 1) 616 cost -= edge_cost; 617 else 618 cost += edge_cost; 619 } 620 } 621 else 622 { 623 refs_node = snode; 624 last_visited_node++; 625 } 626 627 /* Compute boundary cost of IPA REF edges and at the same time look into 628 variables referenced from current partition and try to add them. */ 629 for (j = 0; refs_node->iterate_reference (j, ref); j++) 630 if (is_a <varpool_node *> (ref->referred)) 631 { 632 int index; 633 634 vnode = dyn_cast <varpool_node *> (ref->referred); 635 if (!vnode->definition) 636 continue; 637 if (!symbol_partitioned_p (vnode) && flag_toplevel_reorder 638 && !vnode->no_reorder 639 && vnode->get_partitioning_class () == SYMBOL_PARTITION) 640 add_symbol_to_partition (partition, vnode); 641 index = lto_symtab_encoder_lookup (partition->encoder, 642 vnode); 643 if (index != LCC_NOT_FOUND 644 && index < last_visited_node - 1) 645 cost--, internal++; 646 else 647 cost++; 648 } 649 else 650 { 651 int index; 652 653 node = dyn_cast <cgraph_node *> (ref->referred); 654 if (!node->definition) 655 continue; 656 index = lto_symtab_encoder_lookup (partition->encoder, 657 node); 658 if (index != LCC_NOT_FOUND 659 && index < last_visited_node - 1) 660 cost--, internal++; 661 else 662 cost++; 663 } 664 for (j = 0; refs_node->iterate_referring (j, ref); j++) 665 if (is_a <varpool_node *> (ref->referring)) 666 { 667 int index; 668 669 vnode = dyn_cast <varpool_node *> (ref->referring); 670 gcc_assert (vnode->definition); 671 /* It is better to couple variables with their users, because it allows them 672 to be removed. Coupling with objects they refer to only helps to reduce 673 number of symbols promoted to hidden. */ 674 if (!symbol_partitioned_p (vnode) && flag_toplevel_reorder 675 && !vnode->no_reorder 676 && !vnode->can_remove_if_no_refs_p () 677 && vnode->get_partitioning_class () == SYMBOL_PARTITION) 678 add_symbol_to_partition (partition, vnode); 679 index = lto_symtab_encoder_lookup (partition->encoder, 680 vnode); 681 if (index != LCC_NOT_FOUND 682 && index < last_visited_node - 1) 683 cost--; 684 else 685 cost++; 686 } 687 else 688 { 689 int index; 690 691 node = dyn_cast <cgraph_node *> (ref->referring); 692 gcc_assert (node->definition); 693 index = lto_symtab_encoder_lookup (partition->encoder, 694 node); 695 if (index != LCC_NOT_FOUND 696 && index < last_visited_node - 1) 697 cost--; 698 else 699 cost++; 700 } 701 } 702 703 /* If the partition is large enough, start looking for smallest boundary cost. */ 704 if (partition->insns < partition_size * 3 / 4 705 || best_cost == INT_MAX 706 || ((!cost 707 || (best_internal * (HOST_WIDE_INT) cost 708 > (internal * (HOST_WIDE_INT)best_cost))) 709 && partition->insns < partition_size * 5 / 4)) 710 { 711 best_cost = cost; 712 best_internal = internal; 713 best_i = i; 714 best_n_nodes = lto_symtab_encoder_size (partition->encoder); 715 best_total_size = total_size; 716 best_varpool_pos = varpool_pos; 717 } 718 if (symtab->dump_file) 719 fprintf (symtab->dump_file, "Step %i: added %s/%i, size %i, cost %i/%i " 720 "best %i/%i, step %i\n", i, 721 order[i]->name (), order[i]->order, 722 partition->insns, cost, internal, 723 best_cost, best_internal, best_i); 724 /* Partition is too large, unwind into step when best cost was reached and 725 start new partition. */ 726 if (partition->insns > 2 * partition_size) 727 { 728 if (best_i != i) 729 { 730 if (symtab->dump_file) 731 fprintf (symtab->dump_file, "Unwinding %i insertions to step %i\n", 732 i - best_i, best_i); 733 undo_partition (partition, best_n_nodes); 734 varpool_pos = best_varpool_pos; 735 } 736 i = best_i; 737 /* When we are finished, avoid creating empty partition. */ 738 while (i < n_nodes - 1 && symbol_partitioned_p (order[i + 1])) 739 i++; 740 if (i == n_nodes - 1) 741 break; 742 partition = new_partition (""); 743 last_visited_node = 0; 744 total_size = best_total_size; 745 cost = 0; 746 747 if (symtab->dump_file) 748 fprintf (symtab->dump_file, "New partition\n"); 749 best_n_nodes = 0; 750 best_cost = INT_MAX; 751 752 /* Since the size of partitions is just approximate, update the size after 753 we finished current one. */ 754 if (npartitions < n_lto_partitions) 755 partition_size = total_size / (n_lto_partitions - npartitions); 756 else 757 partition_size = INT_MAX; 758 759 if (partition_size < PARAM_VALUE (MIN_PARTITION_SIZE)) 760 partition_size = PARAM_VALUE (MIN_PARTITION_SIZE); 761 npartitions ++; 762 } 763 } 764 765 next_nodes.truncate (0); 766 767 /* Varables that are not reachable from the code go into last partition. */ 768 if (flag_toplevel_reorder) 769 { 770 FOR_EACH_VARIABLE (vnode) 771 if (vnode->get_partitioning_class () == SYMBOL_PARTITION 772 && !symbol_partitioned_p (vnode) 773 && !vnode->no_reorder) 774 next_nodes.safe_push (vnode); 775 } 776 777 /* Output remaining ordered symbols. */ 778 while (varpool_pos < n_varpool_nodes) 779 next_nodes.safe_push (varpool_order[varpool_pos++]); 780 while (noreorder_pos < (int)noreorder.length ()) 781 next_nodes.safe_push (noreorder[noreorder_pos++]); 782 add_sorted_nodes (next_nodes, partition); 783 784 free (order); 785} 786 787/* Return true if we must not change the name of the NODE. The name as 788 extracted from the corresponding decl should be passed in NAME. */ 789 790static bool 791must_not_rename (symtab_node *node, const char *name) 792{ 793 /* Our renaming machinery do not handle more than one change of assembler name. 794 We should not need more than one anyway. */ 795 if (node->lto_file_data 796 && lto_get_decl_name_mapping (node->lto_file_data, name) != name) 797 { 798 if (symtab->dump_file) 799 fprintf (symtab->dump_file, 800 "Not privatizing symbol name: %s. It privatized already.\n", 801 name); 802 return true; 803 } 804 /* Avoid mangling of already mangled clones. 805 ??? should have a flag whether a symbol has a 'private' name already, 806 since we produce some symbols like that i.e. for global constructors 807 that are not really clones. */ 808 if (node->unique_name) 809 { 810 if (symtab->dump_file) 811 fprintf (symtab->dump_file, 812 "Not privatizing symbol name: %s. Has unique name.\n", 813 name); 814 return true; 815 } 816 return false; 817} 818 819/* If we are an offload compiler, we may have to rewrite symbols to be 820 valid on this target. Return either PTR or a modified version of it. */ 821 822static const char * 823maybe_rewrite_identifier (const char *ptr) 824{ 825#if defined ACCEL_COMPILER && (defined NO_DOT_IN_LABEL || defined NO_DOLLAR_IN_LABEL) 826#ifndef NO_DOT_IN_LABEL 827 char valid = '.'; 828 const char reject[] = "$"; 829#elif !defined NO_DOLLAR_IN_LABEL 830 char valid = '$'; 831 const char reject[] = "."; 832#else 833 char valid = '_'; 834 const char reject[] = ".$"; 835#endif 836 837 char *copy = NULL; 838 const char *match = ptr; 839 for (;;) 840 { 841 size_t off = strcspn (match, reject); 842 if (match[off] == '\0') 843 break; 844 if (copy == NULL) 845 { 846 copy = xstrdup (ptr); 847 match = copy; 848 } 849 copy[off] = valid; 850 } 851 return match; 852#else 853 return ptr; 854#endif 855} 856 857/* Ensure that the symbol in NODE is valid for the target, and if not, 858 rewrite it. */ 859 860static void 861validize_symbol_for_target (symtab_node *node) 862{ 863 tree decl = node->decl; 864 const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl)); 865 866 if (must_not_rename (node, name)) 867 return; 868 869 const char *name2 = maybe_rewrite_identifier (name); 870 if (name2 != name) 871 { 872 symtab->change_decl_assembler_name (decl, get_identifier (name2)); 873 if (node->lto_file_data) 874 lto_record_renamed_decl (node->lto_file_data, name, 875 IDENTIFIER_POINTER 876 (DECL_ASSEMBLER_NAME (decl))); 877 } 878} 879 880/* Helper for privatize_symbol_name. Mangle NODE symbol name 881 represented by DECL. */ 882 883static bool 884privatize_symbol_name_1 (symtab_node *node, tree decl) 885{ 886 const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl)); 887 888 if (must_not_rename (node, name)) 889 return false; 890 891 name = maybe_rewrite_identifier (name); 892 symtab->change_decl_assembler_name (decl, 893 clone_function_name_1 (name, 894 "lto_priv")); 895 896 if (node->lto_file_data) 897 lto_record_renamed_decl (node->lto_file_data, name, 898 IDENTIFIER_POINTER 899 (DECL_ASSEMBLER_NAME (decl))); 900 901 if (symtab->dump_file) 902 fprintf (symtab->dump_file, 903 "Privatizing symbol name: %s -> %s\n", 904 name, IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl))); 905 906 return true; 907} 908 909/* Mangle NODE symbol name into a local name. 910 This is necessary to do 911 1) if two or more static vars of same assembler name 912 are merged into single ltrans unit. 913 2) if previously static var was promoted hidden to avoid possible conflict 914 with symbols defined out of the LTO world. */ 915 916static bool 917privatize_symbol_name (symtab_node *node) 918{ 919 if (!privatize_symbol_name_1 (node, node->decl)) 920 return false; 921 922 /* We could change name which is a target of transparent alias 923 chain of instrumented function name. Fix alias chain if so .*/ 924 if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node)) 925 { 926 tree iname = NULL_TREE; 927 if (cnode->instrumentation_clone) 928 { 929 /* If we want to privatize instrumentation clone 930 then we also need to privatize original function. */ 931 if (cnode->instrumented_version) 932 privatize_symbol_name (cnode->instrumented_version); 933 else 934 privatize_symbol_name_1 (cnode, cnode->orig_decl); 935 iname = DECL_ASSEMBLER_NAME (cnode->decl); 936 TREE_CHAIN (iname) = DECL_ASSEMBLER_NAME (cnode->orig_decl); 937 } 938 else if (cnode->instrumented_version 939 && cnode->instrumented_version->orig_decl == cnode->decl) 940 { 941 iname = DECL_ASSEMBLER_NAME (cnode->instrumented_version->decl); 942 TREE_CHAIN (iname) = DECL_ASSEMBLER_NAME (cnode->decl); 943 } 944 } 945 946 return true; 947} 948 949/* Promote variable VNODE to be static. */ 950 951static void 952promote_symbol (symtab_node *node) 953{ 954 /* We already promoted ... */ 955 if (DECL_VISIBILITY (node->decl) == VISIBILITY_HIDDEN 956 && DECL_VISIBILITY_SPECIFIED (node->decl) 957 && TREE_PUBLIC (node->decl)) 958 { 959 validize_symbol_for_target (node); 960 return; 961 } 962 963 gcc_checking_assert (!TREE_PUBLIC (node->decl) 964 && !DECL_EXTERNAL (node->decl)); 965 /* Be sure that newly public symbol does not conflict with anything already 966 defined by the non-LTO part. */ 967 privatize_symbol_name (node); 968 TREE_PUBLIC (node->decl) = 1; 969 DECL_VISIBILITY (node->decl) = VISIBILITY_HIDDEN; 970 DECL_VISIBILITY_SPECIFIED (node->decl) = true; 971 if (symtab->dump_file) 972 fprintf (symtab->dump_file, 973 "Promoting as hidden: %s\n", node->name ()); 974} 975 976/* Return true if NODE needs named section even if it won't land in the partition 977 symbol table. 978 FIXME: we should really not use named sections for inline clones and master clones. */ 979 980static bool 981may_need_named_section_p (lto_symtab_encoder_t encoder, symtab_node *node) 982{ 983 struct cgraph_node *cnode = dyn_cast <cgraph_node *> (node); 984 if (!cnode) 985 return false; 986 if (node->real_symbol_p ()) 987 return false; 988 return (!encoder 989 || (lto_symtab_encoder_lookup (encoder, node) != LCC_NOT_FOUND 990 && lto_symtab_encoder_encode_body_p (encoder, 991 cnode))); 992} 993 994/* If NODE represents a static variable. See if there are other variables 995 of the same name in partition ENCODER (or in whole compilation unit if 996 ENCODER is NULL) and if so, mangle the statics. Always mangle all 997 conflicting statics, so we reduce changes of silently miscompiling 998 asm statements referring to them by symbol name. */ 999 1000static void 1001rename_statics (lto_symtab_encoder_t encoder, symtab_node *node) 1002{ 1003 tree decl = node->decl; 1004 symtab_node *s; 1005 tree name = DECL_ASSEMBLER_NAME (decl); 1006 1007 /* See if this is static symbol. */ 1008 if ((node->externally_visible 1009 /* FIXME: externally_visible is somewhat illogically not set for 1010 external symbols (i.e. those not defined). Remove this test 1011 once this is fixed. */ 1012 || DECL_EXTERNAL (node->decl) 1013 || !node->real_symbol_p ()) 1014 && !may_need_named_section_p (encoder, node)) 1015 return; 1016 1017 /* Now walk symbols sharing the same name and see if there are any conflicts. 1018 (all types of symbols counts here, since we can not have static of the 1019 same name as external or public symbol.) */ 1020 for (s = symtab_node::get_for_asmname (name); 1021 s; s = s->next_sharing_asm_name) 1022 if ((s->real_symbol_p () || may_need_named_section_p (encoder, s)) 1023 && s->decl != node->decl 1024 && (!encoder 1025 || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND)) 1026 break; 1027 1028 /* OK, no confict, so we have nothing to do. */ 1029 if (!s) 1030 return; 1031 1032 if (symtab->dump_file) 1033 fprintf (symtab->dump_file, 1034 "Renaming statics with asm name: %s\n", node->name ()); 1035 1036 /* Assign every symbol in the set that shares the same ASM name an unique 1037 mangled name. */ 1038 for (s = symtab_node::get_for_asmname (name); s;) 1039 if (!s->externally_visible 1040 && ((s->real_symbol_p () 1041 && !DECL_EXTERNAL (s->decl) 1042 && !TREE_PUBLIC (s->decl)) 1043 || may_need_named_section_p (encoder, s)) 1044 && (!encoder 1045 || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND)) 1046 { 1047 if (privatize_symbol_name (s)) 1048 /* Re-start from beginning since we do not know how many symbols changed a name. */ 1049 s = symtab_node::get_for_asmname (name); 1050 else s = s->next_sharing_asm_name; 1051 } 1052 else s = s->next_sharing_asm_name; 1053} 1054 1055/* Find out all static decls that need to be promoted to global because 1056 of cross file sharing. This function must be run in the WPA mode after 1057 all inlinees are added. */ 1058 1059void 1060lto_promote_cross_file_statics (void) 1061{ 1062 unsigned i, n_sets; 1063 1064 gcc_assert (flag_wpa); 1065 1066 lto_stream_offload_p = false; 1067 select_what_to_stream (); 1068 1069 /* First compute boundaries. */ 1070 n_sets = ltrans_partitions.length (); 1071 for (i = 0; i < n_sets; i++) 1072 { 1073 ltrans_partition part 1074 = ltrans_partitions[i]; 1075 part->encoder = compute_ltrans_boundary (part->encoder); 1076 } 1077 1078 /* Look at boundaries and promote symbols as needed. */ 1079 for (i = 0; i < n_sets; i++) 1080 { 1081 lto_symtab_encoder_iterator lsei; 1082 lto_symtab_encoder_t encoder = ltrans_partitions[i]->encoder; 1083 1084 for (lsei = lsei_start (encoder); !lsei_end_p (lsei); 1085 lsei_next (&lsei)) 1086 { 1087 symtab_node *node = lsei_node (lsei); 1088 1089 /* If symbol is static, rename it if its assembler name clash with 1090 anything else in this unit. */ 1091 rename_statics (encoder, node); 1092 1093 /* No need to promote if symbol already is externally visible ... */ 1094 if (node->externally_visible 1095 /* ... or if it is part of current partition ... */ 1096 || lto_symtab_encoder_in_partition_p (encoder, node) 1097 /* ... or if we do not partition it. This mean that it will 1098 appear in every partition refernecing it. */ 1099 || node->get_partitioning_class () != SYMBOL_PARTITION) 1100 { 1101 validize_symbol_for_target (node); 1102 continue; 1103 } 1104 1105 promote_symbol (node); 1106 } 1107 } 1108} 1109 1110/* Rename statics in the whole unit in the case that 1111 we do -flto-partition=none. */ 1112 1113void 1114lto_promote_statics_nonwpa (void) 1115{ 1116 symtab_node *node; 1117 FOR_EACH_SYMBOL (node) 1118 { 1119 rename_statics (NULL, node); 1120 validize_symbol_for_target (node); 1121 } 1122} 1123