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