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