1/* Localize comdats. 2 Copyright (C) 2014-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along 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 81tree 82propagate_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 177void 178enqueue_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 224bool 225set_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 239bool 240set_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 248static unsigned int 249ipa_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 396namespace { 397 398const 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 411class pass_ipa_comdats : public ipa_opt_pass_d 412{ 413public: 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 433bool 434pass_ipa_comdats::gate (function *) 435{ 436 return optimize; 437} 438 439} // anon namespace 440 441ipa_opt_pass_d * 442make_pass_ipa_comdats (gcc::context *ctxt) 443{ 444 return new pass_ipa_comdats (ctxt); 445} 446