gcc/ipa-comdats.c

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