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