gcc/ipa-comdats.c

   1 /* Localize comdats.
   2    Copyright (C) 2014-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 /* This is very simple pass that looks for static symbols that are used
  21    exlusively by symbol within one comdat group.  In this case it makes
  22    sense to bring the symbol itself into the group to avoid dead code
  23    that would arrise when the comdat group from current unit is replaced
  24    by a different copy.  Consider for example:
  25
  26     static int q(void)
  27     {
  28       ....
  29     }
  30     inline int t(void)
  31     {
  32       return q();
  33     }
  34
  35    if Q is used only by T, it makes sense to put Q into T's comdat group.
  36
  37    The pass solve simple dataflow across the callgraph trying to prove what
  38    symbols are used exclusively from a given comdat group.
  39
  40    The implementation maintains a queue linked by AUX pointer terminated by
  41    pointer value 1. Lattice values are NULL for TOP, actual comdat group, or
  42    ERROR_MARK_NODE for bottom.
  43
  44    TODO: When symbol is used only by comdat symbols, but from different groups,
  45    it would make sense to produce a new comdat group for it with anonymous name.
  46
  47    TODO2: We can't mix variables and functions within one group.  Currently
  48    we just give up on references of symbols of different types.  We also should
  49    handle this by anonymous comdat group section.  */
  50
  51 #include "config.h"
  52 #include "system.h"
  53 #include "coretypes.h"
  54 #include "tm.h"
  55 #include "alias.h"
  56 #include "symtab.h"
  57 #include "tree.h"
  58 #include "plugin-api.h"
  59 #include "hard-reg-set.h"
  60 #include "function.h"
  61 #include "ipa-ref.h"
  62 #include "cgraph.h"
  63 #include "tree-pass.h"
  64
  65 /* Main dataflow loop propagating comdat groups across
  66    the symbol table.  All references to SYMBOL are examined
  67    and NEWGROUP is updated accordingly. MAP holds current lattice
  68    values for individual symbols.  */
  69
  70 tree
  71 propagate_comdat_group (struct symtab_node *symbol,
  72                         tree newgroup, hash_map<symtab_node *, tree> &map)
  73 {
  74   int i;
  75   struct ipa_ref *ref;
  76
  77   /* Walk all references to SYMBOL, recursively dive into aliases.  */
  78
  79   for (i = 0;
  80        symbol->iterate_referring (i, ref)
  81        && newgroup != error_mark_node; i++)
  82     {
  83       struct symtab_node *symbol2 = ref->referring;
  84
  85       if (ref->use == IPA_REF_ALIAS)
  86         {
  87           newgroup = propagate_comdat_group (symbol2, newgroup, map);
  88           continue;
  89         }
  90
  91       /* One COMDAT group can not hold both variables and functions at
  92          a same time.  For now we just go to BOTTOM, in future we may
  93          invent special comdat groups for this case.  */
  94
  95       if (symbol->type != symbol2->type)
  96         {
  97           newgroup = error_mark_node;
  98           break;
  99         }
 100
 101       /* If we see inline clone, its comdat group actually
 102          corresponds to the comdat group of the function it is inlined
 103          to.  */
 104
 105       if (cgraph_node * cn = dyn_cast <cgraph_node *> (symbol2))
 106         {
 107           if (cn->global.inlined_to)
 108             symbol2 = cn->global.inlined_to;
 109         }
 110
 111       /* The actual merge operation.  */
 112
 113       tree *val2 = map.get (symbol2);
 114
 115       if (val2 && *val2 != newgroup)
 116         {
 117           if (!newgroup)
 118             newgroup = *val2;
 119           else
 120             newgroup = error_mark_node;
 121         }
 122     }
 123
 124   /* If we analyze function, walk also callers.  */
 125
 126   cgraph_node *cnode = dyn_cast <cgraph_node *> (symbol);
 127
 128   if (cnode)
 129     for (struct cgraph_edge * edge = cnode->callers;
 130          edge && newgroup != error_mark_node; edge = edge->next_caller)
 131       {
 132         struct symtab_node *symbol2 = edge->caller;
 133
 134         if (cgraph_node * cn = dyn_cast <cgraph_node *> (symbol2))
 135           {
 136             /* Thunks can not call across section boundary.  */
 137             if (cn->thunk.thunk_p)
 138               newgroup = propagate_comdat_group (symbol2, newgroup, map);
 139             /* If we see inline clone, its comdat group actually
 140                corresponds to the comdat group of the function it
 141                is inlined to.  */
 142             if (cn->global.inlined_to)
 143               symbol2 = cn->global.inlined_to;
 144           }
 145
 146         /* The actual merge operation.  */
 147
 148         tree *val2 = map.get (symbol2);
 149
 150         if (val2 && *val2 != newgroup)
 151           {
 152             if (!newgroup)
 153               newgroup = *val2;
 154             else
 155               newgroup = error_mark_node;
 156           }
 157       }
 158   return newgroup;
 159 }
 160
 161
 162 /* Add all references of SYMBOL that are defined into queue started by FIRST
 163    and linked by AUX pointer (unless they are already enqueued).
 164    Walk recursively inlined functions.  */
 165
 166 void
 167 enqueue_references (symtab_node **first,
 168                     symtab_node *symbol)
 169 {
 170   int i;
 171   struct ipa_ref *ref = NULL;
 172
 173   for (i = 0; symbol->iterate_reference (i, ref); i++)
 174     {
 175       symtab_node *node = ref->referred->ultimate_alias_target ();
 176
 177       /* Always keep thunks in same sections as target function.  */
 178       if (is_a <cgraph_node *>(node))
 179         node = dyn_cast <cgraph_node *> (node)->function_symbol ();
 180       if (!node->aux && node->definition)
 181         {
 182            node->aux = *first;
 183            *first = node;
 184         }
 185     }
 186
 187   if (cgraph_node *cnode = dyn_cast <cgraph_node *> (symbol))
 188     {
 189       struct cgraph_edge *edge;
 190
 191       for (edge = cnode->callees; edge; edge = edge->next_callee)
 192         if (!edge->inline_failed)
 193           enqueue_references (first, edge->callee);
 194         else
 195           {
 196             symtab_node *node = edge->callee->ultimate_alias_target ();
 197
 198             /* Always keep thunks in same sections as target function.  */
 199             if (is_a <cgraph_node *>(node))
 200               node = dyn_cast <cgraph_node *> (node)->function_symbol ();
 201             if (!node->aux && node->definition)
 202               {
 203                  node->aux = *first;
 204                  *first = node;
 205               }
 206           }
 207     }
 208 }
 209
 210 /* Set comdat group of SYMBOL to GROUP.
 211    Callback for for_node_and_aliases.  */
 212
 213 bool
 214 set_comdat_group (symtab_node *symbol,
 215                   void *head_p)
 216 {
 217   symtab_node *head = (symtab_node *)head_p;
 218
 219   gcc_assert (!symbol->get_comdat_group ());
 220   symbol->set_comdat_group (head->get_comdat_group ());
 221   symbol->add_to_same_comdat_group (head);
 222   return false;
 223 }
 224
 225 /* Set comdat group of SYMBOL to GROUP.
 226    Callback for for_node_thunks_and_aliases.  */
 227
 228 bool
 229 set_comdat_group_1 (cgraph_node *symbol,
 230                     void *head_p)
 231 {
 232   return set_comdat_group (symbol, head_p);
 233 }
 234
 235 /* The actual pass with the main dataflow loop.  */
 236
 237 static unsigned int
 238 ipa_comdats (void)
 239 {
 240   hash_map<symtab_node *, tree> map (251);
 241   hash_map<tree, symtab_node *> comdat_head_map (251);
 242   symtab_node *symbol;
 243   bool comdat_group_seen = false;
 244   symtab_node *first = (symtab_node *) (void *) 1;
 245   tree group;
 246
 247   /* Start the dataflow by assigning comdat group to symbols that are in comdat
 248      groups already.  All other externally visible symbols must stay, we use
 249      ERROR_MARK_NODE as bottom for the propagation.  */
 250
 251   FOR_EACH_DEFINED_SYMBOL (symbol)
 252     if (!symbol->real_symbol_p ())
 253       ;
 254     else if ((group = symbol->get_comdat_group ()) != NULL)
 255       {
 256         map.put (symbol, group);
 257         comdat_head_map.put (group, symbol);
 258         comdat_group_seen = true;
 259
 260         /* Mark the symbol so we won't waste time visiting it for dataflow.  */
 261         symbol->aux = (symtab_node *) (void *) 1;
 262       }
 263     /* See symbols that can not be privatized to comdats; that is externally
 264        visible symbols or otherwise used ones.  We also do not want to mangle
 265        user section names.  */
 266     else if (symbol->externally_visible
 267              || symbol->force_output
 268              || symbol->used_from_other_partition
 269              || TREE_THIS_VOLATILE (symbol->decl)
 270              || symbol->get_section ()
 271              || (TREE_CODE (symbol->decl) == FUNCTION_DECL
 272                  && (DECL_STATIC_CONSTRUCTOR (symbol->decl)
 273                      || DECL_STATIC_DESTRUCTOR (symbol->decl))))
 274       {
 275         symtab_node *target = symbol->ultimate_alias_target ();
 276
 277         /* Always keep thunks in same sections as target function.  */
 278         if (is_a <cgraph_node *>(target))
 279           target = dyn_cast <cgraph_node *> (target)->function_symbol ();
 280         map.put (target, error_mark_node);
 281
 282         /* Mark the symbol so we won't waste time visiting it for dataflow.  */
 283         symbol->aux = (symtab_node *) (void *) 1;
 284       }
 285     else
 286       {
 287         /* Enqueue symbol for dataflow.  */
 288         symbol->aux = first;
 289         first = symbol;
 290       }
 291
 292   if (!comdat_group_seen)
 293     {
 294       FOR_EACH_DEFINED_SYMBOL (symbol)
 295         symbol->aux = NULL;
 296       return 0;
 297     }
 298
 299   /* The actual dataflow.  */
 300
 301   while (first != (void *) 1)
 302     {
 303       tree group = NULL;
 304       tree newgroup, *val;
 305
 306       symbol = first;
 307       first = (symtab_node *)first->aux;
 308
 309       /* Get current lattice value of SYMBOL.  */
 310       val = map.get (symbol);
 311       if (val)
 312         group = *val;
 313
 314       /* If it is bottom, there is nothing to do; do not clear AUX
 315          so we won't re-queue the symbol.  */
 316       if (group == error_mark_node)
 317         continue;
 318
 319       newgroup = propagate_comdat_group (symbol, group, map);
 320
 321       /* If nothing changed, proceed to next symbol.  */
 322       if (newgroup == group)
 323         {
 324           symbol->aux = NULL;
 325           continue;
 326         }
 327
 328       /* Update lattice value and enqueue all references for re-visiting.  */
 329       gcc_assert (newgroup);
 330       if (val)
 331         *val = newgroup;
 332       else
 333         map.put (symbol, newgroup);
 334       enqueue_references (&first, symbol);
 335
 336       /* We may need to revisit the symbol unless it is BOTTOM.  */
 337       if (newgroup != error_mark_node)
 338         symbol->aux = NULL;
 339     }
 340
 341   /* Finally assign symbols to the sections.  */
 342
 343   FOR_EACH_DEFINED_SYMBOL (symbol)
 344     {
 345       struct cgraph_node *fun;
 346       symbol->aux = NULL;
 347       if (!symbol->get_comdat_group ()
 348           && !symbol->alias
 349           && (!(fun = dyn_cast <cgraph_node *> (symbol))
 350               || !fun->thunk.thunk_p)
 351           && symbol->real_symbol_p ())
 352         {
 353           tree *val = map.get (symbol);
 354
 355           /* A NULL here means that SYMBOL is unreachable in the definition
 356              of ipa-comdats. Either ipa-comdats is wrong about this or someone
 357              forgot to cleanup and remove unreachable functions earlier.  */
 358           gcc_assert (val);
 359
 360           tree group = *val;
 361
 362           if (group == error_mark_node)
 363             continue;
 364           if (dump_file)
 365             {
 366               fprintf (dump_file, "Localizing symbol\n");
 367               symbol->dump (dump_file);
 368               fprintf (dump_file, "To group: %s\n", IDENTIFIER_POINTER (group));
 369             }
 370           if (is_a <cgraph_node *> (symbol))
 371            dyn_cast <cgraph_node *>(symbol)->call_for_symbol_thunks_and_aliases
 372                   (set_comdat_group_1,
 373                    *comdat_head_map.get (group),
 374                    true);
 375           else
 376            symbol->call_for_symbol_and_aliases
 377                   (set_comdat_group,
 378                    *comdat_head_map.get (group),
 379                    true);
 380         }
 381     }
 382   return 0;
 383 }
 384
 385 namespace {
 386
 387 const pass_data pass_data_ipa_comdats =
 388 {
 389   IPA_PASS, /* type */
 390   "comdats", /* name */
 391   OPTGROUP_NONE, /* optinfo_flags */
 392   TV_IPA_COMDATS, /* tv_id */
 393   0, /* properties_required */
 394   0, /* properties_provided */
 395   0, /* properties_destroyed */
 396   0, /* todo_flags_start */
 397   0, /* todo_flags_finish */
 398 };
 399
 400 class pass_ipa_comdats : public ipa_opt_pass_d
 401 {
 402 public:
 403   pass_ipa_comdats (gcc::context *ctxt)
 404     : ipa_opt_pass_d (pass_data_ipa_comdats, ctxt,
 405                       NULL, /* generate_summary */
 406                       NULL, /* write_summary */
 407                       NULL, /* read_summary */
 408                       NULL, /* write_optimization_summary */
 409                       NULL, /* read_optimization_summary */
 410                       NULL, /* stmt_fixup */
 411                       0, /* function_transform_todo_flags_start */
 412                       NULL, /* function_transform */
 413                       NULL) /* variable_transform */
 414   {}
 415
 416   /* opt_pass methods: */
 417   virtual bool gate (function *);
 418   virtual unsigned int execute (function *) { return ipa_comdats (); }
 419
 420 }; // class pass_ipa_comdats
 421
 422 bool
 423 pass_ipa_comdats::gate (function *)
 424 {
 425   return optimize;
 426 }
 427
 428 } // anon namespace
 429
 430 ipa_opt_pass_d *
 431 make_pass_ipa_comdats (gcc::context *ctxt)
 432 {
 433   return new pass_ipa_comdats (ctxt);
 434 }