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