LCOV - code coverage report
Current view: top level - gcc/lto - lto-partition.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 478 520 91.9 %
Date: 2020-03-28 11:57:23 Functions: 22 24 91.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

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

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.