gcc/varpool.c

   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
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along 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.  */
  52 static 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.  */
  56 struct 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
  75 struct varpool_node *varpool_nodes_queue;
  76 static GTY(()) struct varpool_node *varpool_last_needed_node;
  77 static GTY(()) struct varpool_node *varpool_first_unanalyzed_node;
  78
  79 /* Lists all assembled variables to be sent to debugger output later on.  */
  80 static GTY(()) struct varpool_node *varpool_assembled_nodes_queue;
  81
  82 /* Return name of the node used in debug output.  */
  83 const char *
  84 varpool_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.  */
  90 static hashval_t
  91 hash_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.  */
  98 static int
  99 eq_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 without creating new one.  */
 109 struct varpool_node *
 110 varpool_get_node (tree decl)
 111 {
 112   struct varpool_node key, **slot;
 113
 114   gcc_assert (DECL_P (decl) && TREE_CODE (decl) != FUNCTION_DECL);
 115
 116   if (!varpool_hash)
 117     return NULL;
 118   key.decl = decl;
 119   slot = (struct varpool_node **)
 120     htab_find_slot (varpool_hash, &key, INSERT);
 121   return *slot;
 122 }
 123
 124 /* Return varpool node assigned to DECL.  Create new one when needed.  */
 125 struct varpool_node *
 126 varpool_node (tree decl)
 127 {
 128   struct varpool_node key, *node, **slot;
 129
 130   gcc_assert (DECL_P (decl) && TREE_CODE (decl) != FUNCTION_DECL);
 131
 132   if (!varpool_hash)
 133     varpool_hash = htab_create_ggc (10, hash_varpool_node,
 134                                            eq_varpool_node, NULL);
 135   key.decl = decl;
 136   slot = (struct varpool_node **)
 137     htab_find_slot (varpool_hash, &key, INSERT);
 138   if (*slot)
 139     return *slot;
 140   node = GGC_CNEW (struct varpool_node);
 141   node->decl = decl;
 142   node->order = cgraph_order++;
 143   node->next = varpool_nodes;
 144   if (varpool_nodes)
 145     varpool_nodes->prev = node;
 146   varpool_nodes = node;
 147   *slot = node;
 148   return node;
 149 }
 150
 151 /* Remove node from the varpool.  */
 152 void
 153 varpool_remove_node (struct varpool_node *node)
 154 {
 155   void **slot;
 156   slot = htab_find_slot (varpool_hash, node, NO_INSERT);
 157   gcc_assert (*slot == node);
 158   htab_clear_slot (varpool_hash, slot);
 159   gcc_assert (!varpool_assembled_nodes_queue);
 160   if (!node->alias)
 161     while (node->extra_name)
 162       varpool_remove_node (node->extra_name);
 163   if (node->next)
 164     node->next->prev = node->prev;
 165   if (node->prev)
 166     node->prev->next = node->next;
 167   else
 168     {
 169       if (node->alias)
 170         {
 171           gcc_assert (node->extra_name->extra_name == node);
 172           node->extra_name->extra_name = node->next;
 173         }
 174       else
 175         {
 176           gcc_assert (varpool_nodes == node);
 177           varpool_nodes = node->next;
 178         }
 179     }
 180   if (varpool_first_unanalyzed_node == node)
 181     varpool_first_unanalyzed_node = node->next_needed;
 182   if (node->next_needed)
 183     node->next_needed->prev_needed = node->prev_needed;
 184   else if (node->prev_needed)
 185     {
 186       gcc_assert (varpool_last_needed_node);
 187       varpool_last_needed_node = node->prev_needed;
 188     }
 189   if (node->prev_needed)
 190     node->prev_needed->next_needed = node->next_needed;
 191   else if (node->next_needed)
 192     {
 193       gcc_assert (varpool_nodes_queue == node);
 194       varpool_nodes_queue = node->next_needed;
 195     }
 196   if (DECL_INITIAL (node->decl))
 197     DECL_INITIAL (node->decl) = error_mark_node;
 198   ggc_free (node);
 199 }
 200
 201 /* Dump given cgraph node.  */
 202 void
 203 dump_varpool_node (FILE *f, struct varpool_node *node)
 204 {
 205   fprintf (f, "%s:", varpool_node_name (node));
 206   fprintf (f, " availability:%s",
 207            cgraph_function_flags_ready
 208            ? cgraph_availability_names[cgraph_variable_initializer_availability (node)]
 209            : "not-ready");
 210   if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
 211     fprintf (f, " (asm: %s)", IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
 212   if (DECL_INITIAL (node->decl))
 213     fprintf (f, " initialized");
 214   if (TREE_ASM_WRITTEN (node->decl))
 215     fprintf (f, " (asm written)");
 216   if (node->needed)
 217     fprintf (f, " needed");
 218   if (node->analyzed)
 219     fprintf (f, " analyzed");
 220   if (node->finalized)
 221     fprintf (f, " finalized");
 222   if (node->output)
 223     fprintf (f, " output");
 224   if (node->externally_visible)
 225     fprintf (f, " externally_visible");
 226   if (node->in_other_partition)
 227     fprintf (f, " in_other_partition");
 228   else if (node->used_from_other_partition)
 229     fprintf (f, " used_from_other_partition");
 230   fprintf (f, "\n");
 231 }
 232
 233 /* Dump the variable pool.  */
 234 void
 235 dump_varpool (FILE *f)
 236 {
 237   struct varpool_node *node;
 238
 239   fprintf (f, "variable pool:\n\n");
 240   for (node = varpool_nodes; node; node = node->next)
 241     dump_varpool_node (f, node);
 242 }
 243
 244 /* Dump the variable pool to stderr.  */
 245
 246 void
 247 debug_varpool (void)
 248 {
 249   dump_varpool (stderr);
 250 }
 251
 252 /* Given an assembler name, lookup node.  */
 253 struct varpool_node *
 254 varpool_node_for_asm (tree asmname)
 255 {
 256   struct varpool_node *node;
 257
 258   for (node = varpool_nodes; node ; node = node->next)
 259     if (decl_assembler_name_equal (node->decl, asmname))
 260       return node;
 261
 262   return NULL;
 263 }
 264
 265 /* Helper function for finalization code - add node into lists so it will
 266    be analyzed and compiled.  */
 267 static void
 268 varpool_enqueue_needed_node (struct varpool_node *node)
 269 {
 270   if (varpool_last_needed_node)
 271     {
 272       varpool_last_needed_node->next_needed = node;
 273       node->prev_needed = varpool_last_needed_node;
 274     }
 275   varpool_last_needed_node = node;
 276   node->next_needed = NULL;
 277   if (!varpool_nodes_queue)
 278     varpool_nodes_queue = node;
 279   if (!varpool_first_unanalyzed_node)
 280     varpool_first_unanalyzed_node = node;
 281   notice_global_symbol (node->decl);
 282 }
 283
 284 /* Notify finalize_compilation_unit that given node is reachable
 285    or needed.  */
 286 void
 287 varpool_mark_needed_node (struct varpool_node *node)
 288 {
 289   if (node->alias && node->extra_name)
 290     node = node->extra_name;
 291   if (!node->needed && node->finalized
 292       && !TREE_ASM_WRITTEN (node->decl))
 293     varpool_enqueue_needed_node (node);
 294   node->needed = 1;
 295 }
 296
 297 /* Reset the queue of needed nodes.  */
 298 static void
 299 varpool_reset_queue (void)
 300 {
 301   varpool_last_needed_node = NULL;
 302   varpool_nodes_queue = NULL;
 303   varpool_first_unanalyzed_node = NULL;
 304 }
 305
 306 /* Determine if variable DECL is needed.  That is, visible to something
 307    either outside this translation unit, something magic in the system
 308    configury */
 309 bool
 310 decide_is_variable_needed (struct varpool_node *node, tree decl)
 311 {
 312   if (node->used_from_other_partition)
 313     return true;
 314   /* If the user told us it is used, then it must be so.  */
 315   if ((node->externally_visible && !DECL_COMDAT (decl))
 316       || node->force_output)
 317     return true;
 318
 319   /* ??? If the assembler name is set by hand, it is possible to assemble
 320      the name later after finalizing the function and the fact is noticed
 321      in assemble_name then.  This is arguably a bug.  */
 322   if (DECL_ASSEMBLER_NAME_SET_P (decl)
 323       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 324     return true;
 325
 326   /* Externally visible variables must be output.  The exception is
 327      COMDAT variables that must be output only when they are needed.  */
 328   if (TREE_PUBLIC (decl)
 329       && !flag_whole_program
 330       && !flag_lto
 331       && !flag_whopr
 332       && !DECL_COMDAT (decl)
 333       && !DECL_EXTERNAL (decl))
 334     return true;
 335
 336   /* When emulating tls, we actually see references to the control
 337      variable, rather than the user-level variable.  */
 338   if (!targetm.have_tls
 339       && TREE_CODE (decl) == VAR_DECL
 340       && DECL_THREAD_LOCAL_P (decl))
 341     {
 342       tree control = emutls_decl (decl);
 343       if (decide_is_variable_needed (varpool_node (control), control))
 344         return true;
 345     }
 346
 347   /* When not reordering top level variables, we have to assume that
 348      we are going to keep everything.  */
 349   if (flag_toplevel_reorder)
 350     return false;
 351
 352   /* We want to emit COMDAT variables only when absolutely necessary.  */
 353   if (DECL_COMDAT (decl))
 354     return false;
 355   return true;
 356 }
 357
 358 /* Mark DECL as finalized.  By finalizing the declaration, frontend instruct the
 359    middle end to output the variable to asm file, if needed or externally
 360    visible.  */
 361 void
 362 varpool_finalize_decl (tree decl)
 363 {
 364   struct varpool_node *node = varpool_node (decl);
 365
 366   /* The first declaration of a variable that comes through this function
 367      decides whether it is global (in C, has external linkage)
 368      or local (in C, has internal linkage).  So do nothing more
 369      if this function has already run.  */
 370   if (node->finalized)
 371     {
 372       if (cgraph_global_info_ready)
 373         varpool_assemble_pending_decls ();
 374       return;
 375     }
 376   if (node->needed)
 377     varpool_enqueue_needed_node (node);
 378   node->finalized = true;
 379
 380   if (decide_is_variable_needed (node, decl))
 381     varpool_mark_needed_node (node);
 382   /* Since we reclaim unreachable nodes at the end of every language
 383      level unit, we need to be conservative about possible entry points
 384      there.  */
 385   else if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 386     varpool_mark_needed_node (node);
 387   if (cgraph_global_info_ready)
 388     varpool_assemble_pending_decls ();
 389 }
 390
 391 /* Return variable availability.  See cgraph.h for description of individual
 392    return values.  */
 393 enum availability
 394 cgraph_variable_initializer_availability (struct varpool_node *node)
 395 {
 396   gcc_assert (cgraph_function_flags_ready);
 397   if (!node->finalized)
 398     return AVAIL_NOT_AVAILABLE;
 399   if (!TREE_PUBLIC (node->decl))
 400     return AVAIL_AVAILABLE;
 401   /* If the variable can be overwritten, return OVERWRITABLE.  Takes
 402      care of at least two notable extensions - the COMDAT variables
 403      used to share template instantiations in C++.  */
 404   if (!(*targetm.binds_local_p) (node->decl) && !DECL_COMDAT (node->decl))
 405     return AVAIL_OVERWRITABLE;
 406   return AVAIL_AVAILABLE;
 407 }
 408
 409 /* Walk the decls we marked as necessary and see if they reference new
 410    variables or functions and add them into the worklists.  */
 411 bool
 412 varpool_analyze_pending_decls (void)
 413 {
 414   bool changed = false;
 415
 416   timevar_push (TV_VARPOOL);
 417   while (varpool_first_unanalyzed_node)
 418     {
 419       tree decl = varpool_first_unanalyzed_node->decl;
 420       bool analyzed = varpool_first_unanalyzed_node->analyzed;
 421
 422       varpool_first_unanalyzed_node->analyzed = true;
 423
 424       varpool_first_unanalyzed_node = varpool_first_unanalyzed_node->next_needed;
 425
 426       /* When reading back varpool at LTO time, we re-construct the queue in order
 427          to have "needed" list right by inserting all needed nodes into varpool.
 428          We however don't want to re-analyze already analyzed nodes.  */
 429       if (!analyzed)
 430         {
 431           gcc_assert (!in_lto_p || cgraph_function_flags_ready);
 432           /* Compute the alignment early so function body expanders are
 433              already informed about increased alignment.  */
 434           align_variable (decl, 0);
 435         }
 436       if (DECL_INITIAL (decl))
 437         record_references_in_initializer (decl, analyzed);
 438       changed = true;
 439     }
 440   timevar_pop (TV_VARPOOL);
 441   return changed;
 442 }
 443
 444 /* Output one variable, if necessary.  Return whether we output it.  */
 445 bool
 446 varpool_assemble_decl (struct varpool_node *node)
 447 {
 448   tree decl = node->decl;
 449
 450   if (!TREE_ASM_WRITTEN (decl)
 451       && !node->alias
 452       && !node->in_other_partition
 453       && !DECL_EXTERNAL (decl)
 454       && (TREE_CODE (decl) != VAR_DECL || !DECL_HAS_VALUE_EXPR_P (decl)))
 455     {
 456       assemble_variable (decl, 0, 1, 0);
 457       if (TREE_ASM_WRITTEN (decl))
 458         {
 459           struct varpool_node *alias;
 460
 461           node->next_needed = varpool_assembled_nodes_queue;
 462           node->prev_needed = NULL;
 463           if (varpool_assembled_nodes_queue)
 464             varpool_assembled_nodes_queue->prev_needed = node;
 465           varpool_assembled_nodes_queue = node;
 466           node->finalized = 1;
 467
 468           /* Also emit any extra name aliases.  */
 469           for (alias = node->extra_name; alias; alias = alias->next)
 470             {
 471               /* Update linkage fields in case they've changed.  */
 472               DECL_WEAK (alias->decl) = DECL_WEAK (decl);
 473               TREE_PUBLIC (alias->decl) = TREE_PUBLIC (decl);
 474               DECL_VISIBILITY (alias->decl) = DECL_VISIBILITY (decl);
 475               assemble_alias (alias->decl, DECL_ASSEMBLER_NAME (decl));
 476             }
 477
 478           return true;
 479         }
 480     }
 481
 482   return false;
 483 }
 484
 485 /* Optimization of function bodies might've rendered some variables as
 486    unnecessary so we want to avoid these from being compiled.
 487
 488    This is done by pruning the queue and keeping only the variables that
 489    really appear needed (ie they are either externally visible or referenced
 490    by compiled function). Re-doing the reachability analysis on variables
 491    brings back the remaining variables referenced by these.  */
 492 void
 493 varpool_remove_unreferenced_decls (void)
 494 {
 495   struct varpool_node *next, *node = varpool_nodes_queue;
 496
 497   varpool_reset_queue ();
 498
 499   if (errorcount || sorrycount)
 500     return;
 501
 502   while (node)
 503     {
 504       tree decl = node->decl;
 505       next = node->next_needed;
 506       node->needed = 0;
 507
 508       if (node->finalized
 509           && (decide_is_variable_needed (node, decl)
 510               /* ??? Cgraph does not yet rule the world with an iron hand,
 511                  and does not control the emission of debug information.
 512                  After a variable has its DECL_RTL set, we must assume that
 513                  it may be referenced by the debug information, and we can
 514                  no longer elide it.  */
 515               || DECL_RTL_SET_P (decl)))
 516         varpool_mark_needed_node (node);
 517
 518       node = next;
 519     }
 520   /* Make sure we mark alias targets as used targets.  */
 521   finish_aliases_1 ();
 522   varpool_analyze_pending_decls ();
 523 }
 524
 525 /* Output all variables enqueued to be assembled.  */
 526 bool
 527 varpool_assemble_pending_decls (void)
 528 {
 529   bool changed = false;
 530
 531   if (errorcount || sorrycount)
 532     return false;
 533
 534   timevar_push (TV_VAROUT);
 535   /* EH might mark decls as needed during expansion.  This should be safe since
 536      we don't create references to new function, but it should not be used
 537      elsewhere.  */
 538   varpool_analyze_pending_decls ();
 539
 540   while (varpool_nodes_queue)
 541     {
 542       struct varpool_node *node = varpool_nodes_queue;
 543
 544       varpool_nodes_queue = varpool_nodes_queue->next_needed;
 545       if (varpool_assemble_decl (node))
 546         changed = true;
 547       else
 548         {
 549           node->prev_needed = NULL;
 550           node->next_needed = NULL;
 551         }
 552     }
 553   /* varpool_nodes_queue is now empty, clear the pointer to the last element
 554      in the queue.  */
 555   varpool_last_needed_node = NULL;
 556   timevar_pop (TV_VAROUT);
 557   return changed;
 558 }
 559
 560 /* Remove all elements from the queue so we can re-use it for debug output.  */
 561 void
 562 varpool_empty_needed_queue (void)
 563 {
 564   /* EH might mark decls as needed during expansion.  This should be safe since
 565      we don't create references to new function, but it should not be used
 566      elsewhere.  */
 567   varpool_analyze_pending_decls ();
 568
 569   while (varpool_nodes_queue)
 570     {
 571       struct varpool_node *node = varpool_nodes_queue;
 572       varpool_nodes_queue = varpool_nodes_queue->next_needed;
 573       node->next_needed = NULL;
 574       node->prev_needed = NULL;
 575     }
 576   /* varpool_nodes_queue is now empty, clear the pointer to the last element
 577      in the queue.  */
 578   varpool_last_needed_node = NULL;
 579 }
 580
 581 /* Create a new global variable of type TYPE.  */
 582 tree
 583 add_new_static_var (tree type)
 584 {
 585   tree new_decl;
 586   struct varpool_node *new_node;
 587
 588   new_decl = create_tmp_var (type, NULL);
 589   DECL_NAME (new_decl) = create_tmp_var_name (NULL);
 590   TREE_READONLY (new_decl) = 0;
 591   TREE_STATIC (new_decl) = 1;
 592   TREE_USED (new_decl) = 1;
 593   DECL_CONTEXT (new_decl) = NULL_TREE;
 594   DECL_ABSTRACT (new_decl) = 0;
 595   lang_hooks.dup_lang_specific_decl (new_decl);
 596   create_var_ann (new_decl);
 597   new_node = varpool_node (new_decl);
 598   varpool_mark_needed_node (new_node);
 599   add_referenced_var (new_decl);
 600   varpool_finalize_decl (new_decl);
 601
 602   return new_node->decl;
 603 }
 604
 605 /* Attempt to mark ALIAS as an alias to DECL.  Return TRUE if successful.
 606    Extra name aliases are output whenever DECL is output.  */
 607
 608 bool
 609 varpool_extra_name_alias (tree alias, tree decl)
 610 {
 611   struct varpool_node key, *alias_node, *decl_node, **slot;
 612
 613 #ifndef ASM_OUTPUT_DEF
 614   /* If aliases aren't supported by the assembler, fail.  */
 615   return false;
 616 #endif
 617
 618   gcc_assert (TREE_CODE (decl) == VAR_DECL);
 619   gcc_assert (TREE_CODE (alias) == VAR_DECL);
 620   /* Make sure the hash table has been created.  */
 621   decl_node = varpool_node (decl);
 622
 623   key.decl = alias;
 624
 625   slot = (struct varpool_node **) htab_find_slot (varpool_hash, &key, INSERT);
 626
 627   /* If the varpool_node has been already created, fail.  */
 628   if (*slot)
 629     return false;
 630
 631   alias_node = GGC_CNEW (struct varpool_node);
 632   alias_node->decl = alias;
 633   alias_node->alias = 1;
 634   alias_node->extra_name = decl_node;
 635   alias_node->next = decl_node->extra_name;
 636   if (decl_node->extra_name)
 637     decl_node->extra_name->prev = alias_node;
 638   decl_node->extra_name = alias_node;
 639   *slot = alias_node;
 640   return true;
 641 }
 642
 643 #include "gt-varpool.h"