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 we see inline clone, its comdat group actually
 146            corresponds to the comdat group of the function it is inlined
 147            to.  */
 148
 149         if (cgraph_node * cn = dyn_cast <cgraph_node *> (symbol2))
 150           {
 151             if (cn->global.inlined_to)
 152               symbol2 = cn->global.inlined_to;
 153           }
 154
 155         /* The actual merge operation.  */
 156
 157         tree *val2 = map.get (symbol2);
 158
 159         if (val2 && *val2 != newgroup)
 160           {
 161             if (!newgroup)
 162               newgroup = *val2;
 163             else
 164               newgroup = error_mark_node;
 165           }
 166       }
 167   return newgroup;
 168 }
 169
 170
 171 /* Add all references of SYMBOL that are defined into queue started by FIRST
 172    and linked by AUX pointer (unless they are already enqueued).
 173    Walk recursively inlined functions.  */
 174
 175 void
 176 enqueue_references (symtab_node **first,
 177                     symtab_node *symbol)
 178 {
 179   int i;
 180   struct ipa_ref *ref = NULL;
 181
 182   for (i = 0; symbol->iterate_reference (i, ref); i++)
 183     {
 184       symtab_node *node = ref->referred->ultimate_alias_target ();
 185       if (!node->aux && node->definition)
 186         {
 187            node->aux = *first;
 188            *first = node;
 189         }
 190     }
 191
 192   if (cgraph_node *cnode = dyn_cast <cgraph_node *> (symbol))
 193     {
 194       struct cgraph_edge *edge;
 195
 196       for (edge = cnode->callees; edge; edge = edge->next_callee)
 197         if (!edge->inline_failed)
 198           enqueue_references (first, edge->callee);
 199         else
 200           {
 201             symtab_node *node = edge->callee->ultimate_alias_target ();
 202             if (!node->aux && node->definition)
 203               {
 204                  node->aux = *first;
 205                  *first = node;
 206               }
 207           }
 208     }
 209 }
 210
 211 /* Set comdat group of SYMBOL to GROUP.
 212    Callback for symtab_for_node_and_aliases.  */
 213
 214 bool
 215 set_comdat_group (symtab_node *symbol,
 216                   void *head_p)
 217 {
 218   symtab_node *head = (symtab_node *)head_p;
 219
 220   gcc_assert (!symbol->get_comdat_group ());
 221   symbol->set_comdat_group (head->get_comdat_group ());
 222   symbol->add_to_same_comdat_group (head);
 223   return false;
 224 }
 225
 226 /* The actual pass with the main dataflow loop.  */
 227
 228 static unsigned int
 229 ipa_comdats (void)
 230 {
 231   hash_map<symtab_node *, tree> map (251);
 232   hash_map<tree, symtab_node *> comdat_head_map (251);
 233   symtab_node *symbol;
 234   bool comdat_group_seen = false;
 235   symtab_node *first = (symtab_node *) (void *) 1;
 236   tree group;
 237
 238   /* Start the dataflow by assigning comdat group to symbols that are in comdat
 239      groups already.  All other externally visible symbols must stay, we use
 240      ERROR_MARK_NODE as bottom for the propagation.  */
 241
 242   FOR_EACH_DEFINED_SYMBOL (symbol)
 243     if (!symbol->real_symbol_p ())
 244       ;
 245     else if ((group = symbol->get_comdat_group ()) != NULL)
 246       {
 247         map.put (symbol, group);
 248         comdat_head_map.put (group, symbol);
 249         comdat_group_seen = true;
 250
 251         /* Mark the symbol so we won't waste time visiting it for dataflow.  */
 252         symbol->aux = (symtab_node *) (void *) 1;
 253       }
 254     /* See symbols that can not be privatized to comdats; that is externally
 255        visible symbols or otherwise used ones.  We also do not want to mangle
 256        user section names.  */
 257     else if (symbol->externally_visible
 258              || symbol->force_output
 259              || symbol->used_from_other_partition
 260              || TREE_THIS_VOLATILE (symbol->decl)
 261              || symbol->get_section ()
 262              || (TREE_CODE (symbol->decl) == FUNCTION_DECL
 263                  && (DECL_STATIC_CONSTRUCTOR (symbol->decl)
 264                      || DECL_STATIC_DESTRUCTOR (symbol->decl))))
 265       {
 266         map.put (symbol->ultimate_alias_target (), error_mark_node);
 267
 268         /* Mark the symbol so we won't waste time visiting it for dataflow.  */
 269         symbol->aux = (symtab_node *) (void *) 1;
 270       }
 271     else
 272       {
 273         /* Enqueue symbol for dataflow.  */
 274         symbol->aux = first;
 275         first = symbol;
 276       }
 277
 278   if (!comdat_group_seen)
 279     {
 280       FOR_EACH_DEFINED_SYMBOL (symbol)
 281         symbol->aux = NULL;
 282       return 0;
 283     }
 284
 285   /* The actual dataflow.  */
 286
 287   while (first != (void *) 1)
 288     {
 289       tree group = NULL;
 290       tree newgroup, *val;
 291
 292       symbol = first;
 293       first = (symtab_node *)first->aux;
 294
 295       /* Get current lattice value of SYMBOL.  */
 296       val = map.get (symbol);
 297       if (val)
 298         group = *val;
 299
 300       /* If it is bottom, there is nothing to do; do not clear AUX
 301          so we won't re-queue the symbol.  */
 302       if (group == error_mark_node)
 303         continue;
 304
 305       newgroup = propagate_comdat_group (symbol, group, map);
 306
 307       /* If nothing changed, proceed to next symbol.  */
 308       if (newgroup == group)
 309         {
 310           symbol->aux = NULL;
 311           continue;
 312         }
 313
 314       /* Update lattice value and enqueue all references for re-visiting.  */
 315       gcc_assert (newgroup);
 316       if (val)
 317         *val = newgroup;
 318       else
 319         map.put (symbol, newgroup);
 320       enqueue_references (&first, symbol);
 321
 322       /* We may need to revisit the symbol unless it is BOTTOM.  */
 323       if (newgroup != error_mark_node)
 324         symbol->aux = NULL;
 325     }
 326
 327   /* Finally assign symbols to the sections.  */
 328
 329   FOR_EACH_DEFINED_SYMBOL (symbol)
 330     {
 331       symbol->aux = NULL;
 332       if (!symbol->get_comdat_group ()
 333           && !symbol->alias
 334           && symbol->real_symbol_p ())
 335         {
 336           tree *val = map.get (symbol);
 337
 338           /* A NULL here means that SYMBOL is unreachable in the definition
 339              of ipa-comdats. Either ipa-comdats is wrong about this or someone
 340              forgot to cleanup and remove unreachable functions earlier.  */
 341           gcc_assert (val);
 342
 343           tree group = *val;
 344
 345           if (group == error_mark_node)
 346             continue;
 347           if (dump_file)
 348             {
 349               fprintf (dump_file, "Localizing symbol\n");
 350               symbol->dump (dump_file);
 351               fprintf (dump_file, "To group: %s\n", IDENTIFIER_POINTER (group));
 352             }
 353           symbol->call_for_symbol_and_aliases (set_comdat_group,
 354                                              *comdat_head_map.get (group),
 355                                              true);
 356         }
 357     }
 358   return 0;
 359 }
 360
 361 namespace {
 362
 363 const pass_data pass_data_ipa_comdats =
 364 {
 365   IPA_PASS, /* type */
 366   "comdats", /* name */
 367   OPTGROUP_NONE, /* optinfo_flags */
 368   TV_IPA_COMDATS, /* tv_id */
 369   0, /* properties_required */
 370   0, /* properties_provided */
 371   0, /* properties_destroyed */
 372   0, /* todo_flags_start */
 373   0, /* todo_flags_finish */
 374 };
 375
 376 class pass_ipa_comdats : public ipa_opt_pass_d
 377 {
 378 public:
 379   pass_ipa_comdats (gcc::context *ctxt)
 380     : ipa_opt_pass_d (pass_data_ipa_comdats, ctxt,
 381                       NULL, /* generate_summary */
 382                       NULL, /* write_summary */
 383                       NULL, /* read_summary */
 384                       NULL, /* write_optimization_summary */
 385                       NULL, /* read_optimization_summary */
 386                       NULL, /* stmt_fixup */
 387                       0, /* function_transform_todo_flags_start */
 388                       NULL, /* function_transform */
 389                       NULL) /* variable_transform */
 390   {}
 391
 392   /* opt_pass methods: */
 393   virtual bool gate (function *);
 394   virtual unsigned int execute (function *) { return ipa_comdats (); }
 395
 396 }; // class pass_ipa_comdats
 397
 398 bool
 399 pass_ipa_comdats::gate (function *)
 400 {
 401   return optimize;
 402 }
 403
 404 } // anon namespace
 405
 406 ipa_opt_pass_d *
 407 make_pass_ipa_comdats (gcc::context *ctxt)
 408 {
 409   return new pass_ipa_comdats (ctxt);
 410 }