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