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