1/* Callgraph handling code. 2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2010 3 Free Software Foundation, Inc. 4 Contributed by Jan Hubicka 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 3, or (at your option) any later 11version. 12 13GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING3. If not see 20<http://www.gnu.org/licenses/>. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "tree.h" 27#include "cgraph.h" 28#include "langhooks.h" 29#include "diagnostic.h" 30#include "hashtab.h" 31#include "ggc.h" 32#include "timevar.h" 33#include "debug.h" 34#include "target.h" 35#include "output.h" 36#include "gimple.h" 37#include "tree-flow.h" 38#include "flags.h" 39 40/* This file contains basic routines manipulating variable pool. 41 42 Varpool acts as interface in between the front-end and middle-end 43 and drives the decision process on what variables and when are 44 going to be compiled. 45 46 The varpool nodes are allocated lazily for declarations 47 either by frontend or at callgraph construction time. 48 All variables supposed to be output into final file needs to be 49 explicitly marked by frontend via VARPOOL_FINALIZE_DECL function. */ 50 51/* Hash table used to convert declarations into nodes. */ 52static GTY((param_is (struct varpool_node))) htab_t varpool_hash; 53 54/* The linked list of cgraph varpool nodes. 55 Linked via node->next pointer. */ 56struct varpool_node *varpool_nodes; 57 58/* Queue of cgraph nodes scheduled to be lowered and output. 59 The queue is maintained via mark_needed_node, linked via node->next_needed 60 pointer. 61 62 LAST_NEEDED_NODE points to the end of queue, so it can be 63 maintained in forward order. GTY is needed to make it friendly to 64 PCH. 65 66 During compilation we construct the queue of needed variables 67 twice: first time it is during cgraph construction, second time it is at the 68 end of compilation in VARPOOL_REMOVE_UNREFERENCED_DECLS so we can avoid 69 optimized out variables being output. 70 71 Each variable is thus first analyzed and then later possibly output. 72 FIRST_UNANALYZED_NODE points to first node in queue that was not analyzed 73 yet and is moved via VARPOOL_ANALYZE_PENDING_DECLS. */ 74 75struct varpool_node *varpool_nodes_queue; 76static GTY(()) struct varpool_node *varpool_last_needed_node; 77static GTY(()) struct varpool_node *varpool_first_unanalyzed_node; 78 79/* Lists all assembled variables to be sent to debugger output later on. */ 80static GTY(()) struct varpool_node *varpool_assembled_nodes_queue; 81 82/* Return name of the node used in debug output. */ 83const char * 84varpool_node_name (struct varpool_node *node) 85{ 86 return lang_hooks.decl_printable_name (node->decl, 2); 87} 88 89/* Returns a hash code for P. */ 90static hashval_t 91hash_varpool_node (const void *p) 92{ 93 const struct varpool_node *n = (const struct varpool_node *) p; 94 return (hashval_t) DECL_UID (n->decl); 95} 96 97/* Returns nonzero if P1 and P2 are equal. */ 98static int 99eq_varpool_node (const void *p1, const void *p2) 100{ 101 const struct varpool_node *n1 = 102 (const struct varpool_node *) p1; 103 const struct varpool_node *n2 = 104 (const struct varpool_node *) p2; 105 return DECL_UID (n1->decl) == DECL_UID (n2->decl); 106} 107 108/* Return varpool node assigned to DECL. Create new one when needed. */ 109struct varpool_node * 110varpool_node (tree decl) 111{ 112 struct varpool_node key, *node, **slot; 113 114 gcc_assert (DECL_P (decl) && TREE_CODE (decl) != FUNCTION_DECL); 115 116 if (!varpool_hash) 117 varpool_hash = htab_create_ggc (10, hash_varpool_node, 118 eq_varpool_node, NULL); 119 key.decl = decl; 120 slot = (struct varpool_node **) 121 htab_find_slot (varpool_hash, &key, INSERT); 122 if (*slot) 123 return *slot; 124 node = GGC_CNEW (struct varpool_node); 125 node->decl = decl; 126 node->order = cgraph_order++; 127 node->next = varpool_nodes; 128 varpool_nodes = node; 129 *slot = node; 130 return node; 131} 132 133/* Dump given cgraph node. */ 134void 135dump_varpool_node (FILE *f, struct varpool_node *node) 136{ 137 fprintf (f, "%s:", varpool_node_name (node)); 138 fprintf (f, " availability:%s", 139 cgraph_function_flags_ready 140 ? cgraph_availability_names[cgraph_variable_initializer_availability (node)] 141 : "not-ready"); 142 if (DECL_INITIAL (node->decl)) 143 fprintf (f, " initialized"); 144 if (node->needed) 145 fprintf (f, " needed"); 146 if (node->analyzed) 147 fprintf (f, " analyzed"); 148 if (node->finalized) 149 fprintf (f, " finalized"); 150 if (node->output) 151 fprintf (f, " output"); 152 if (node->externally_visible) 153 fprintf (f, " externally_visible"); 154 fprintf (f, "\n"); 155} 156 157/* Dump the variable pool. */ 158void 159dump_varpool (FILE *f) 160{ 161 struct varpool_node *node; 162 163 fprintf (f, "variable pool:\n\n"); 164 for (node = varpool_nodes; node; node = node->next) 165 dump_varpool_node (f, node); 166} 167 168/* Dump the variable pool to stderr. */ 169 170void 171debug_varpool (void) 172{ 173 dump_varpool (stderr); 174} 175 176/* Given an assembler name, lookup node. */ 177struct varpool_node * 178varpool_node_for_asm (tree asmname) 179{ 180 struct varpool_node *node; 181 182 for (node = varpool_nodes; node ; node = node->next) 183 if (decl_assembler_name_equal (node->decl, asmname)) 184 return node; 185 186 return NULL; 187} 188 189/* Helper function for finalization code - add node into lists so it will 190 be analyzed and compiled. */ 191static void 192varpool_enqueue_needed_node (struct varpool_node *node) 193{ 194 if (varpool_last_needed_node) 195 varpool_last_needed_node->next_needed = node; 196 varpool_last_needed_node = node; 197 node->next_needed = NULL; 198 if (!varpool_nodes_queue) 199 varpool_nodes_queue = node; 200 if (!varpool_first_unanalyzed_node) 201 varpool_first_unanalyzed_node = node; 202 notice_global_symbol (node->decl); 203} 204 205/* Notify finalize_compilation_unit that given node is reachable 206 or needed. */ 207void 208varpool_mark_needed_node (struct varpool_node *node) 209{ 210 if (node->alias && node->extra_name) 211 node = node->extra_name; 212 if (!node->needed && node->finalized 213 && !TREE_ASM_WRITTEN (node->decl)) 214 varpool_enqueue_needed_node (node); 215 node->needed = 1; 216} 217 218/* Reset the queue of needed nodes. */ 219static void 220varpool_reset_queue (void) 221{ 222 varpool_last_needed_node = NULL; 223 varpool_nodes_queue = NULL; 224 varpool_first_unanalyzed_node = NULL; 225} 226 227/* Determine if variable DECL is needed. That is, visible to something 228 either outside this translation unit, something magic in the system 229 configury */ 230bool 231decide_is_variable_needed (struct varpool_node *node, tree decl) 232{ 233 /* If the user told us it is used, then it must be so. */ 234 if ((node->externally_visible && !DECL_COMDAT (decl)) 235 || node->force_output) 236 return true; 237 238 /* ??? If the assembler name is set by hand, it is possible to assemble 239 the name later after finalizing the function and the fact is noticed 240 in assemble_name then. This is arguably a bug. */ 241 if (DECL_ASSEMBLER_NAME_SET_P (decl) 242 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))) 243 return true; 244 245 /* Externally visible variables must be output. The exception is 246 COMDAT variables that must be output only when they are needed. */ 247 if (TREE_PUBLIC (decl) 248 && !flag_whole_program 249 && !flag_lto 250 && !flag_whopr 251 && !DECL_COMDAT (decl) 252 && !DECL_EXTERNAL (decl)) 253 return true; 254 255 /* When emulating tls, we actually see references to the control 256 variable, rather than the user-level variable. */ 257 if (!targetm.have_tls 258 && TREE_CODE (decl) == VAR_DECL 259 && DECL_THREAD_LOCAL_P (decl)) 260 { 261 tree control = emutls_decl (decl); 262 if (decide_is_variable_needed (varpool_node (control), control)) 263 return true; 264 } 265 266 /* When not reordering top level variables, we have to assume that 267 we are going to keep everything. */ 268 if (flag_toplevel_reorder) 269 return false; 270 271 /* We want to emit COMDAT variables only when absolutely necessary. */ 272 if (DECL_COMDAT (decl)) 273 return false; 274 return true; 275} 276 277/* Mark DECL as finalized. By finalizing the declaration, frontend instruct the 278 middle end to output the variable to asm file, if needed or externally 279 visible. */ 280void 281varpool_finalize_decl (tree decl) 282{ 283 struct varpool_node *node = varpool_node (decl); 284 285 /* FIXME: We don't really stream varpool datastructure and instead rebuild it 286 by varpool_finalize_decl. This is not quite correct since this way we can't 287 attach any info to varpool. Eventually we will want to stream varpool nodes 288 and the flags. 289 290 For the moment just prevent analysis of varpool nodes to happen again, so 291 we will re-try to compute "address_taken" flag of varpool that breaks 292 in presence of clones. */ 293 if (in_lto_p) 294 node->analyzed = true; 295 296 /* The first declaration of a variable that comes through this function 297 decides whether it is global (in C, has external linkage) 298 or local (in C, has internal linkage). So do nothing more 299 if this function has already run. */ 300 if (node->finalized) 301 { 302 if (cgraph_global_info_ready) 303 varpool_assemble_pending_decls (); 304 return; 305 } 306 if (node->needed) 307 varpool_enqueue_needed_node (node); 308 node->finalized = true; 309 310 if (decide_is_variable_needed (node, decl)) 311 varpool_mark_needed_node (node); 312 /* Since we reclaim unreachable nodes at the end of every language 313 level unit, we need to be conservative about possible entry points 314 there. */ 315 else if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)) 316 varpool_mark_needed_node (node); 317 if (cgraph_global_info_ready) 318 varpool_assemble_pending_decls (); 319} 320 321/* Return variable availability. See cgraph.h for description of individual 322 return values. */ 323enum availability 324cgraph_variable_initializer_availability (struct varpool_node *node) 325{ 326 gcc_assert (cgraph_function_flags_ready); 327 if (!node->finalized) 328 return AVAIL_NOT_AVAILABLE; 329 if (!TREE_PUBLIC (node->decl)) 330 return AVAIL_AVAILABLE; 331 /* If the variable can be overwritten, return OVERWRITABLE. Takes 332 care of at least two notable extensions - the COMDAT variables 333 used to share template instantiations in C++. */ 334 if (!(*targetm.binds_local_p) (node->decl) && !DECL_COMDAT (node->decl)) 335 return AVAIL_OVERWRITABLE; 336 return AVAIL_AVAILABLE; 337} 338 339/* Walk the decls we marked as necessary and see if they reference new 340 variables or functions and add them into the worklists. */ 341bool 342varpool_analyze_pending_decls (void) 343{ 344 bool changed = false; 345 timevar_push (TV_CGRAPH); 346 347 while (varpool_first_unanalyzed_node) 348 { 349 tree decl = varpool_first_unanalyzed_node->decl; 350 bool analyzed = varpool_first_unanalyzed_node->analyzed; 351 352 varpool_first_unanalyzed_node->analyzed = true; 353 354 varpool_first_unanalyzed_node = varpool_first_unanalyzed_node->next_needed; 355 356 /* When reading back varpool at LTO time, we re-construct the queue in order 357 to have "needed" list right by inserting all needed nodes into varpool. 358 We however don't want to re-analyze already analyzed nodes. */ 359 if (!analyzed) 360 { 361 gcc_assert (!in_lto_p); 362 /* Compute the alignment early so function body expanders are 363 already informed about increased alignment. */ 364 align_variable (decl, 0); 365 } 366 if (DECL_INITIAL (decl)) 367 record_references_in_initializer (decl, analyzed); 368 changed = true; 369 } 370 timevar_pop (TV_CGRAPH); 371 return changed; 372} 373 374/* Output one variable, if necessary. Return whether we output it. */ 375bool 376varpool_assemble_decl (struct varpool_node *node) 377{ 378 tree decl = node->decl; 379 380 if (!TREE_ASM_WRITTEN (decl) 381 && !node->alias 382 && !DECL_EXTERNAL (decl) 383 && (TREE_CODE (decl) != VAR_DECL || !DECL_HAS_VALUE_EXPR_P (decl))) 384 { 385 assemble_variable (decl, 0, 1, 0); 386 if (TREE_ASM_WRITTEN (decl)) 387 { 388 struct varpool_node *alias; 389 390 node->next_needed = varpool_assembled_nodes_queue; 391 varpool_assembled_nodes_queue = node; 392 node->finalized = 1; 393 394 /* Also emit any extra name aliases. */ 395 for (alias = node->extra_name; alias; alias = alias->next) 396 { 397 /* Update linkage fields in case they've changed. */ 398 DECL_WEAK (alias->decl) = DECL_WEAK (decl); 399 TREE_PUBLIC (alias->decl) = TREE_PUBLIC (decl); 400 DECL_VISIBILITY (alias->decl) = DECL_VISIBILITY (decl); 401 assemble_alias (alias->decl, DECL_ASSEMBLER_NAME (decl)); 402 } 403 404 return true; 405 } 406 } 407 408 return false; 409} 410 411/* Optimization of function bodies might've rendered some variables as 412 unnecessary so we want to avoid these from being compiled. 413 414 This is done by pruning the queue and keeping only the variables that 415 really appear needed (ie they are either externally visible or referenced 416 by compiled function). Re-doing the reachability analysis on variables 417 brings back the remaining variables referenced by these. */ 418void 419varpool_remove_unreferenced_decls (void) 420{ 421 struct varpool_node *next, *node = varpool_nodes_queue; 422 423 varpool_reset_queue (); 424 425 if (errorcount || sorrycount) 426 return; 427 428 while (node) 429 { 430 tree decl = node->decl; 431 next = node->next_needed; 432 node->needed = 0; 433 434 if (node->finalized 435 && (decide_is_variable_needed (node, decl) 436 /* ??? Cgraph does not yet rule the world with an iron hand, 437 and does not control the emission of debug information. 438 After a variable has its DECL_RTL set, we must assume that 439 it may be referenced by the debug information, and we can 440 no longer elide it. */ 441 || DECL_RTL_SET_P (decl))) 442 varpool_mark_needed_node (node); 443 444 node = next; 445 } 446 /* Make sure we mark alias targets as used targets. */ 447 finish_aliases_1 (); 448 varpool_analyze_pending_decls (); 449} 450 451/* Output all variables enqueued to be assembled. */ 452bool 453varpool_assemble_pending_decls (void) 454{ 455 bool changed = false; 456 457 if (errorcount || sorrycount) 458 return false; 459 460 /* EH might mark decls as needed during expansion. This should be safe since 461 we don't create references to new function, but it should not be used 462 elsewhere. */ 463 varpool_analyze_pending_decls (); 464 465 while (varpool_nodes_queue) 466 { 467 struct varpool_node *node = varpool_nodes_queue; 468 469 varpool_nodes_queue = varpool_nodes_queue->next_needed; 470 if (varpool_assemble_decl (node)) 471 changed = true; 472 else 473 node->next_needed = NULL; 474 } 475 /* varpool_nodes_queue is now empty, clear the pointer to the last element 476 in the queue. */ 477 varpool_last_needed_node = NULL; 478 return changed; 479} 480 481/* Remove all elements from the queue so we can re-use it for debug output. */ 482void 483varpool_empty_needed_queue (void) 484{ 485 /* EH might mark decls as needed during expansion. This should be safe since 486 we don't create references to new function, but it should not be used 487 elsewhere. */ 488 varpool_analyze_pending_decls (); 489 490 while (varpool_nodes_queue) 491 { 492 struct varpool_node *node = varpool_nodes_queue; 493 varpool_nodes_queue = varpool_nodes_queue->next_needed; 494 node->next_needed = NULL; 495 } 496 /* varpool_nodes_queue is now empty, clear the pointer to the last element 497 in the queue. */ 498 varpool_last_needed_node = NULL; 499} 500 501/* Create a new global variable of type TYPE. */ 502tree 503add_new_static_var (tree type) 504{ 505 tree new_decl; 506 struct varpool_node *new_node; 507 508 new_decl = create_tmp_var (type, NULL); 509 DECL_NAME (new_decl) = create_tmp_var_name (NULL); 510 TREE_READONLY (new_decl) = 0; 511 TREE_STATIC (new_decl) = 1; 512 TREE_USED (new_decl) = 1; 513 DECL_CONTEXT (new_decl) = NULL_TREE; 514 DECL_ABSTRACT (new_decl) = 0; 515 lang_hooks.dup_lang_specific_decl (new_decl); 516 create_var_ann (new_decl); 517 new_node = varpool_node (new_decl); 518 varpool_mark_needed_node (new_node); 519 add_referenced_var (new_decl); 520 varpool_finalize_decl (new_decl); 521 522 return new_node->decl; 523} 524 525/* Attempt to mark ALIAS as an alias to DECL. Return TRUE if successful. 526 Extra name aliases are output whenever DECL is output. */ 527 528bool 529varpool_extra_name_alias (tree alias, tree decl) 530{ 531 struct varpool_node key, *alias_node, *decl_node, **slot; 532 533#ifndef ASM_OUTPUT_DEF 534 /* If aliases aren't supported by the assembler, fail. */ 535 return false; 536#endif 537 538 gcc_assert (TREE_CODE (decl) == VAR_DECL); 539 gcc_assert (TREE_CODE (alias) == VAR_DECL); 540 /* Make sure the hash table has been created. */ 541 decl_node = varpool_node (decl); 542 543 key.decl = alias; 544 545 slot = (struct varpool_node **) htab_find_slot (varpool_hash, &key, INSERT); 546 547 /* If the varpool_node has been already created, fail. */ 548 if (*slot) 549 return false; 550 551 alias_node = GGC_CNEW (struct varpool_node); 552 alias_node->decl = alias; 553 alias_node->alias = 1; 554 alias_node->extra_name = decl_node; 555 alias_node->next = decl_node->extra_name; 556 decl_node->extra_name = alias_node; 557 *slot = alias_node; 558 return true; 559} 560 561#include "gt-varpool.h" 562