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