gcc/varpool.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
   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.  Create new one when needed.  */
 109 struct varpool_node *
 110 varpool_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.  */
 134 void
 135 dump_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.  */
 158 void
 159 dump_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
 170 void
 171 debug_varpool (void)
 172 {
 173   dump_varpool (stderr);
 174 }
 175
 176 /* Given an assembler name, lookup node.  */
 177 struct varpool_node *
 178 varpool_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.  */
 191 static void
 192 varpool_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.  */
 207 void
 208 varpool_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.  */
 219 static void
 220 varpool_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 */
 230 bool
 231 decide_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.  */
 280 void
 281 varpool_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.  */
 323 enum availability
 324 cgraph_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.  */
 341 bool
 342 varpool_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.  */
 375 bool
 376 varpool_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.  */
 418 void
 419 varpool_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.  */
 452 bool
 453 varpool_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.  */
 482 void
 483 varpool_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.  */
 502 tree
 503 add_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
 528 bool
 529 varpool_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"