contrib/gcc-5.0/gcc/lto/lto-partition.c

   1 /* LTO partitioning logic routines.
   2    Copyright (C) 2009-2015 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #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
  62 vec<ltrans_partition> ltrans_partitions;
  63
  64 static void add_symbol_to_partition (ltrans_partition part, symtab_node *node);
  65
  66
  67 /* Create new partition with name NAME.  */
  68
  69 static ltrans_partition
  70 new_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
  82 void
  83 free_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
  99 static inline bool
 100 symbol_partitioned_p (symtab_node *node)
 101 {
 102   return node->aux;
 103 }
 104
 105 /* Add references into the partition.  */
 106 static void
 107 add_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
 135 static bool
 136 add_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.  */
 220 static symtab_node *
 221 contained_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
 241 static void
 242 add_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
 270 static void
 271 undo_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
 294 void
 295 lto_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
 344 void
 345 lto_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.  */
 366 static int
 367 node_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.  */
 394 static int
 395 varpool_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
 404 static void
 405 add_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
 455 void
 456 lto_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
 790 static bool
 791 must_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
 822 static const char *
 823 maybe_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
 860 static void
 861 validize_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 /* Mangle NODE symbol name into a local name.
 881    This is necessary to do
 882    1) if two or more static vars of same assembler name
 883       are merged into single ltrans unit.
 884    2) if previously static var was promoted hidden to avoid possible conflict
 885       with symbols defined out of the LTO world.  */
 886
 887 static bool
 888 privatize_symbol_name (symtab_node *node)
 889 {
 890   tree decl = node->decl;
 891   const char *name;
 892   cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
 893
 894   /* If we want to privatize instrumentation clone
 895      then we need to change original function name
 896      which is used via transparent alias chain.  */
 897   if (cnode && cnode->instrumentation_clone)
 898     decl = cnode->orig_decl;
 899
 900   name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
 901
 902   if (must_not_rename (node, name))
 903     return false;
 904
 905   name = maybe_rewrite_identifier (name);
 906   symtab->change_decl_assembler_name (decl,
 907                                       clone_function_name_1 (name,
 908                                                              "lto_priv"));
 909   if (node->lto_file_data)
 910     lto_record_renamed_decl (node->lto_file_data, name,
 911                              IDENTIFIER_POINTER
 912                              (DECL_ASSEMBLER_NAME (decl)));
 913   /* We could change name which is a target of transparent alias
 914      chain of instrumented function name.  Fix alias chain if so  .*/
 915   if (cnode)
 916     {
 917       tree iname = NULL_TREE;
 918       if (cnode->instrumentation_clone)
 919         iname = DECL_ASSEMBLER_NAME (cnode->decl);
 920       else if (cnode->instrumented_version
 921                && cnode->instrumented_version->orig_decl == decl)
 922         iname = DECL_ASSEMBLER_NAME (cnode->instrumented_version->decl);
 923
 924       if (iname)
 925         {
 926           gcc_assert (IDENTIFIER_TRANSPARENT_ALIAS (iname));
 927           TREE_CHAIN (iname) = DECL_ASSEMBLER_NAME (decl);
 928         }
 929     }
 930   if (symtab->dump_file)
 931     fprintf (symtab->dump_file,
 932             "Privatizing symbol name: %s -> %s\n",
 933             name, IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl)));
 934   return true;
 935 }
 936
 937 /* Promote variable VNODE to be static.  */
 938
 939 static void
 940 promote_symbol (symtab_node *node)
 941 {
 942   /* We already promoted ... */
 943   if (DECL_VISIBILITY (node->decl) == VISIBILITY_HIDDEN
 944       && DECL_VISIBILITY_SPECIFIED (node->decl)
 945       && TREE_PUBLIC (node->decl))
 946     {
 947       validize_symbol_for_target (node);
 948       return;
 949     }
 950
 951   gcc_checking_assert (!TREE_PUBLIC (node->decl)
 952                        && !DECL_EXTERNAL (node->decl));
 953   /* Be sure that newly public symbol does not conflict with anything already
 954      defined by the non-LTO part.  */
 955   privatize_symbol_name (node);
 956   TREE_PUBLIC (node->decl) = 1;
 957   DECL_VISIBILITY (node->decl) = VISIBILITY_HIDDEN;
 958   DECL_VISIBILITY_SPECIFIED (node->decl) = true;
 959   if (symtab->dump_file)
 960     fprintf (symtab->dump_file,
 961             "Promoting as hidden: %s\n", node->name ());
 962 }
 963
 964 /* Return true if NODE needs named section even if it won't land in the partition
 965    symbol table.
 966    FIXME: we should really not use named sections for inline clones and master clones.  */
 967
 968 static bool
 969 may_need_named_section_p (lto_symtab_encoder_t encoder, symtab_node *node)
 970 {
 971   struct cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
 972   if (!cnode)
 973     return false;
 974   if (node->real_symbol_p ())
 975     return false;
 976   return (!encoder
 977           || (lto_symtab_encoder_lookup (encoder, node) != LCC_NOT_FOUND
 978               && lto_symtab_encoder_encode_body_p (encoder,
 979                                                    cnode)));
 980 }
 981
 982 /* If NODE represents a static variable.  See if there are other variables
 983    of the same name in partition ENCODER (or in whole compilation unit if
 984    ENCODER is NULL) and if so, mangle the statics.  Always mangle all
 985    conflicting statics, so we reduce changes of silently miscompiling
 986    asm statements referring to them by symbol name.  */
 987
 988 static void
 989 rename_statics (lto_symtab_encoder_t encoder, symtab_node *node)
 990 {
 991   tree decl = node->decl;
 992   symtab_node *s;
 993   tree name = DECL_ASSEMBLER_NAME (decl);
 994
 995   /* See if this is static symbol. */
 996   if ((node->externally_visible
 997       /* FIXME: externally_visible is somewhat illogically not set for
 998          external symbols (i.e. those not defined).  Remove this test
 999          once this is fixed.  */
1000         || DECL_EXTERNAL (node->decl)
1001         || !node->real_symbol_p ())
1002        && !may_need_named_section_p (encoder, node))
1003     return;
1004
1005   /* Now walk symbols sharing the same name and see if there are any conflicts.
1006      (all types of symbols counts here, since we can not have static of the
1007      same name as external or public symbol.)  */
1008   for (s = symtab_node::get_for_asmname (name);
1009        s; s = s->next_sharing_asm_name)
1010     if ((s->real_symbol_p () || may_need_named_section_p (encoder, s))
1011         && s->decl != node->decl
1012         && (!encoder
1013             || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND))
1014        break;
1015
1016   /* OK, no confict, so we have nothing to do.  */
1017   if (!s)
1018     return;
1019
1020   if (symtab->dump_file)
1021     fprintf (symtab->dump_file,
1022             "Renaming statics with asm name: %s\n", node->name ());
1023
1024   /* Assign every symbol in the set that shares the same ASM name an unique
1025      mangled name.  */
1026   for (s = symtab_node::get_for_asmname (name); s;)
1027     if (!s->externally_visible
1028         && ((s->real_symbol_p ()
1029              && !DECL_EXTERNAL (node->decl)
1030              && !TREE_PUBLIC (node->decl))
1031             || may_need_named_section_p (encoder, s))
1032         && (!encoder
1033             || lto_symtab_encoder_lookup (encoder, s) != LCC_NOT_FOUND))
1034       {
1035         if (privatize_symbol_name (s))
1036           /* Re-start from beginning since we do not know how many symbols changed a name.  */
1037           s = symtab_node::get_for_asmname (name);
1038         else s = s->next_sharing_asm_name;
1039       }
1040     else s = s->next_sharing_asm_name;
1041 }
1042
1043 /* Find out all static decls that need to be promoted to global because
1044    of cross file sharing.  This function must be run in the WPA mode after
1045    all inlinees are added.  */
1046
1047 void
1048 lto_promote_cross_file_statics (void)
1049 {
1050   unsigned i, n_sets;
1051
1052   gcc_assert (flag_wpa);
1053
1054   lto_stream_offload_p = false;
1055   select_what_to_stream ();
1056
1057   /* First compute boundaries.  */
1058   n_sets = ltrans_partitions.length ();
1059   for (i = 0; i < n_sets; i++)
1060     {
1061       ltrans_partition part
1062         = ltrans_partitions[i];
1063       part->encoder = compute_ltrans_boundary (part->encoder);
1064     }
1065
1066   /* Look at boundaries and promote symbols as needed.  */
1067   for (i = 0; i < n_sets; i++)
1068     {
1069       lto_symtab_encoder_iterator lsei;
1070       lto_symtab_encoder_t encoder = ltrans_partitions[i]->encoder;
1071
1072       for (lsei = lsei_start (encoder); !lsei_end_p (lsei);
1073            lsei_next (&lsei))
1074         {
1075           symtab_node *node = lsei_node (lsei);
1076
1077           /* If symbol is static, rename it if its assembler name clash with
1078              anything else in this unit.  */
1079           rename_statics (encoder, node);
1080
1081           /* No need to promote if symbol already is externally visible ... */
1082           if (node->externally_visible
1083               /* ... or if it is part of current partition ... */
1084               || lto_symtab_encoder_in_partition_p (encoder, node)
1085               /* ... or if we do not partition it. This mean that it will
1086                  appear in every partition refernecing it.  */
1087               || node->get_partitioning_class () != SYMBOL_PARTITION)
1088             {
1089               validize_symbol_for_target (node);
1090               continue;
1091             }
1092
1093           promote_symbol (node);
1094         }
1095     }
1096 }
1097
1098 /* Rename statics in the whole unit in the case that
1099    we do -flto-partition=none.  */
1100
1101 void
1102 lto_promote_statics_nonwpa (void)
1103 {
1104   symtab_node *node;
1105   FOR_EACH_SYMBOL (node)
1106     {
1107       rename_statics (NULL, node);
1108       validize_symbol_for_target (node);
1109     }
1110 }