gcc/varpool.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
   3    Contributed by Jan Hubicka
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  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
  37 /*  This file contains basic routines manipulating variable pool.
  38
  39     Varpool acts as interface in between the front-end and middle-end
  40     and drives the decision process on what variables and when are
  41     going to be compiled.
  42
  43     The varpool nodes are allocated lazily for declarations
  44     either by frontend or at callgraph construction time.
  45     All variables supposed to be output into final file needs to be
  46     explicitly marked by frontend via VARPOOL_FINALIZE_DECL function.  */
  47
  48 /* Hash table used to convert declarations into nodes.  */
  49 static GTY((param_is (struct varpool_node))) htab_t varpool_hash;
  50
  51 /* The linked list of cgraph varpool nodes.
  52    Linked via node->next pointer.  */
  53 struct varpool_node *varpool_nodes;
  54
  55 /* Queue of cgraph nodes scheduled to be lowered and output.
  56    The queue is maintained via mark_needed_node, linked via node->next_needed
  57    pointer.
  58
  59    LAST_NNEDED_NODE points to the end of queue, so it can be maintained in forward
  60    order.  QTY is needed to make it friendly to PCH.
  61
  62    During unit-at-a-time compilation we construct the queue of needed variables
  63    twice: first time it is during cgraph construction, second time it is at the
  64    end of compilation in VARPOOL_REMOVE_UNREFERENCED_DECLS so we can avoid
  65    optimized out variables being output.
  66
  67    Each variable is thus first analyzed and then later possibly output.
  68    FIRST_UNANALYZED_NODE points to first node in queue that was not analyzed
  69    yet and is moved via VARPOOL_ANALYZE_PENDING_DECLS.  */
  70
  71 struct varpool_node *varpool_nodes_queue;
  72 static GTY(()) struct varpool_node *varpool_last_needed_node;
  73 static GTY(()) struct varpool_node *varpool_first_unanalyzed_node;
  74
  75 /* Lists all assembled variables to be sent to debugger output later on.  */
  76 static GTY(()) struct varpool_node *varpool_assembled_nodes_queue;
  77
  78 /* Return name of the node used in debug output.  */
  79 static const char *
  80 varpool_node_name (struct varpool_node *node)
  81 {
  82   return lang_hooks.decl_printable_name (node->decl, 2);
  83 }
  84
  85 /* Returns a hash code for P.  */
  86 static hashval_t
  87 hash_varpool_node (const void *p)
  88 {
  89   const struct varpool_node *n = (const struct varpool_node *) p;
  90   return (hashval_t) DECL_UID (n->decl);
  91 }
  92
  93 /* Returns nonzero if P1 and P2 are equal.  */
  94 static int
  95 eq_varpool_node (const void *p1, const void *p2)
  96 {
  97   const struct varpool_node *n1 =
  98     (const struct varpool_node *) p1;
  99   const struct varpool_node *n2 =
 100     (const struct varpool_node *) p2;
 101   return DECL_UID (n1->decl) == DECL_UID (n2->decl);
 102 }
 103
 104 /* Return varpool node assigned to DECL.  Create new one when needed.  */
 105 struct varpool_node *
 106 varpool_node (tree decl)
 107 {
 108   struct varpool_node key, *node, **slot;
 109
 110   gcc_assert (DECL_P (decl) && TREE_CODE (decl) != FUNCTION_DECL);
 111
 112   if (!varpool_hash)
 113     varpool_hash = htab_create_ggc (10, hash_varpool_node,
 114                                            eq_varpool_node, NULL);
 115   key.decl = decl;
 116   slot = (struct varpool_node **)
 117     htab_find_slot (varpool_hash, &key, INSERT);
 118   if (*slot)
 119     return *slot;
 120   node = GGC_CNEW (struct varpool_node);
 121   node->decl = decl;
 122   node->order = cgraph_order++;
 123   node->next = varpool_nodes;
 124   varpool_nodes = node;
 125   *slot = node;
 126   return node;
 127 }
 128
 129 /* Dump given cgraph node.  */
 130 void
 131 dump_varpool_node (FILE *f, struct varpool_node *node)
 132 {
 133   fprintf (f, "%s:", varpool_node_name (node));
 134   fprintf (f, " availability:%s",
 135            cgraph_function_flags_ready
 136            ? cgraph_availability_names[cgraph_variable_initializer_availability (node)]
 137            : "not-ready");
 138   if (DECL_INITIAL (node->decl))
 139     fprintf (f, " initialized");
 140   if (node->needed)
 141     fprintf (f, " needed");
 142   if (node->analyzed)
 143     fprintf (f, " analyzed");
 144   if (node->finalized)
 145     fprintf (f, " finalized");
 146   if (node->output)
 147     fprintf (f, " output");
 148   if (node->externally_visible)
 149     fprintf (f, " externally_visible");
 150   fprintf (f, "\n");
 151 }
 152
 153 /* Dump the variable pool.  */
 154 void
 155 dump_varpool (FILE *f)
 156 {
 157   struct varpool_node *node;
 158
 159   fprintf (f, "variable pool:\n\n");
 160   for (node = varpool_nodes; node; node = node->next_needed)
 161     dump_varpool_node (f, node);
 162 }
 163
 164 /* Given an assembler name, lookup node.  */
 165 struct varpool_node *
 166 varpool_node_for_asm (tree asmname)
 167 {
 168   struct varpool_node *node;
 169
 170   for (node = varpool_nodes; node ; node = node->next)
 171     if (decl_assembler_name_equal (node->decl, asmname))
 172       return node;
 173
 174   return NULL;
 175 }
 176
 177 /* Helper function for finalization code - add node into lists so it will
 178    be analyzed and compiled.  */
 179 static void
 180 varpool_enqueue_needed_node (struct varpool_node *node)
 181 {
 182   if (varpool_last_needed_node)
 183     varpool_last_needed_node->next_needed = node;
 184   varpool_last_needed_node = node;
 185   node->next_needed = NULL;
 186   if (!varpool_nodes_queue)
 187     varpool_nodes_queue = node;
 188   if (!varpool_first_unanalyzed_node)
 189     varpool_first_unanalyzed_node = node;
 190   notice_global_symbol (node->decl);
 191 }
 192
 193 /* Notify finalize_compilation_unit that given node is reachable
 194    or needed.  */
 195 void
 196 varpool_mark_needed_node (struct varpool_node *node)
 197 {
 198   if (!node->needed && node->finalized
 199       && !TREE_ASM_WRITTEN (node->decl))
 200     varpool_enqueue_needed_node (node);
 201   node->needed = 1;
 202 }
 203
 204 /* Reset the queue of needed nodes.  */
 205 static void
 206 varpool_reset_queue (void)
 207 {
 208   varpool_last_needed_node = NULL;
 209   varpool_nodes_queue = NULL;
 210   varpool_first_unanalyzed_node = NULL;
 211 }
 212
 213 /* Determine if variable DECL is needed.  That is, visible to something
 214    either outside this translation unit, something magic in the system
 215    configury, or (if not doing unit-at-a-time) to something we haven't
 216    seen yet.  */
 217 bool
 218 decide_is_variable_needed (struct varpool_node *node, tree decl)
 219 {
 220   /* If the user told us it is used, then it must be so.  */
 221   if (node->externally_visible || node->force_output)
 222     return true;
 223   if (!flag_unit_at_a_time
 224       && lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
 225     return true;
 226
 227   /* ??? If the assembler name is set by hand, it is possible to assemble
 228      the name later after finalizing the function and the fact is noticed
 229      in assemble_name then.  This is arguably a bug.  */
 230   if (DECL_ASSEMBLER_NAME_SET_P (decl)
 231       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 232     return true;
 233
 234   /* If we decided it was needed before, but at the time we didn't have
 235      the definition available, then it's still needed.  */
 236   if (node->needed)
 237     return true;
 238
 239   /* Externally visible variables must be output.  The exception is
 240      COMDAT variables that must be output only when they are needed.  */
 241   if (TREE_PUBLIC (decl) && !flag_whole_program && !DECL_COMDAT (decl)
 242       && !DECL_EXTERNAL (decl))
 243     return true;
 244
 245   /* When emulating tls, we actually see references to the control
 246      variable, rather than the user-level variable.  */
 247   if (!targetm.have_tls
 248       && TREE_CODE (decl) == VAR_DECL
 249       && DECL_THREAD_LOCAL_P (decl))
 250     {
 251       tree control = emutls_decl (decl);
 252       if (decide_is_variable_needed (varpool_node (control), control))
 253         return true;
 254     }
 255
 256   /* When not reordering top level variables, we have to assume that
 257      we are going to keep everything.  */
 258   if (flag_unit_at_a_time && flag_toplevel_reorder)
 259     return false;
 260
 261   /* We want to emit COMDAT variables only when absolutely necessary.  */
 262   if (DECL_COMDAT (decl))
 263     return false;
 264   return true;
 265 }
 266
 267 /* Mark DECL as finalized.  By finalizing the declaration, frontend instruct the
 268    middle end to output the variable to asm file, if needed or externally
 269    visible.  */
 270 void
 271 varpool_finalize_decl (tree decl)
 272 {
 273   struct varpool_node *node = varpool_node (decl);
 274
 275   /* The first declaration of a variable that comes through this function
 276      decides whether it is global (in C, has external linkage)
 277      or local (in C, has internal linkage).  So do nothing more
 278      if this function has already run.  */
 279   if (node->finalized)
 280     {
 281       if (cgraph_global_info_ready || (!flag_unit_at_a_time && !flag_openmp))
 282         varpool_assemble_pending_decls ();
 283       return;
 284     }
 285   if (node->needed)
 286     varpool_enqueue_needed_node (node);
 287   node->finalized = true;
 288
 289   if (decide_is_variable_needed (node, decl))
 290     varpool_mark_needed_node (node);
 291   /* Since we reclaim unreachable nodes at the end of every language
 292      level unit, we need to be conservative about possible entry points
 293      there.  */
 294   else if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 295     varpool_mark_needed_node (node);
 296   if (cgraph_global_info_ready || (!flag_unit_at_a_time && !flag_openmp))
 297     varpool_assemble_pending_decls ();
 298 }
 299
 300 /* Return variable availability.  See cgraph.h for description of individual
 301    return values.  */
 302 enum availability
 303 cgraph_variable_initializer_availability (struct varpool_node *node)
 304 {
 305   gcc_assert (cgraph_function_flags_ready);
 306   if (!node->finalized)
 307     return AVAIL_NOT_AVAILABLE;
 308   if (!TREE_PUBLIC (node->decl))
 309     return AVAIL_AVAILABLE;
 310   /* If the variable can be overwritten, return OVERWRITABLE.  Takes
 311      care of at least two notable extensions - the COMDAT variables
 312      used to share template instantiations in C++.  */
 313   if (!(*targetm.binds_local_p) (node->decl) && !DECL_COMDAT (node->decl))
 314     return AVAIL_OVERWRITABLE;
 315   return AVAIL_AVAILABLE;
 316 }
 317
 318 /* Walk the decls we marked as necessary and see if they reference new
 319    variables or functions and add them into the worklists.  */
 320 bool
 321 varpool_analyze_pending_decls (void)
 322 {
 323   bool changed = false;
 324   timevar_push (TV_CGRAPH);
 325
 326   while (varpool_first_unanalyzed_node)
 327     {
 328       tree decl = varpool_first_unanalyzed_node->decl;
 329
 330       varpool_first_unanalyzed_node->analyzed = true;
 331
 332       varpool_first_unanalyzed_node = varpool_first_unanalyzed_node->next_needed;
 333
 334       /* Compute the alignment early so function body expanders are
 335          already informed about increased alignment.  */
 336       align_variable (decl, 0);
 337
 338       if (DECL_INITIAL (decl))
 339         record_references_in_initializer (decl);
 340       changed = true;
 341     }
 342   timevar_pop (TV_CGRAPH);
 343   return changed;
 344 }
 345
 346 /* Output one variable, if necessary.  Return whether we output it.  */
 347 bool
 348 varpool_assemble_decl (struct varpool_node *node)
 349 {
 350   tree decl = node->decl;
 351
 352   if (!TREE_ASM_WRITTEN (decl)
 353       && !node->alias
 354       && !DECL_EXTERNAL (decl)
 355       && (TREE_CODE (decl) != VAR_DECL || !DECL_HAS_VALUE_EXPR_P (decl)))
 356     {
 357       assemble_variable (decl, 0, 1, 0);
 358       return TREE_ASM_WRITTEN (decl);
 359     }
 360
 361   return false;
 362 }
 363
 364 /* Optimization of function bodies might've rendered some variables as
 365    unnecessary so we want to avoid these from being compiled.
 366
 367    This is done by pruning the queue and keeping only the variables that
 368    really appear needed (ie they are either externally visible or referenced
 369    by compiled function). Re-doing the reachability analysis on variables
 370    brings back the remaining variables referenced by these.  */
 371 void
 372 varpool_remove_unreferenced_decls (void)
 373 {
 374   struct varpool_node *next, *node = varpool_nodes_queue;
 375
 376   varpool_reset_queue ();
 377
 378   if (errorcount || sorrycount)
 379     return;
 380
 381   while (node)
 382     {
 383       tree decl = node->decl;
 384       next = node->next_needed;
 385       node->needed = 0;
 386
 387       if (node->finalized
 388           && (decide_is_variable_needed (node, decl)
 389               /* ??? Cgraph does not yet rule the world with an iron hand,
 390                  and does not control the emission of debug information.
 391                  After a variable has its DECL_RTL set, we must assume that
 392                  it may be referenced by the debug information, and we can
 393                  no longer elide it.  */
 394               || DECL_RTL_SET_P (decl)))
 395         varpool_mark_needed_node (node);
 396
 397       node = next;
 398     }
 399   /* Make sure we mark alias targets as used targets.  */
 400   finish_aliases_1 ();
 401   varpool_analyze_pending_decls ();
 402 }
 403
 404 /* Output all variables enqueued to be assembled.  */
 405 bool
 406 varpool_assemble_pending_decls (void)
 407 {
 408   bool changed = false;
 409
 410   if (errorcount || sorrycount)
 411     return false;
 412
 413   /* EH might mark decls as needed during expansion.  This should be safe since
 414      we don't create references to new function, but it should not be used
 415      elsewhere.  */
 416   varpool_analyze_pending_decls ();
 417
 418   while (varpool_nodes_queue)
 419     {
 420       struct varpool_node *node = varpool_nodes_queue;
 421
 422       varpool_nodes_queue = varpool_nodes_queue->next_needed;
 423       if (varpool_assemble_decl (node))
 424         {
 425           changed = true;
 426           node->next_needed = varpool_assembled_nodes_queue;
 427           varpool_assembled_nodes_queue = node;
 428           node->finalized = 1;
 429         }
 430       else
 431         node->next_needed = NULL;
 432     }
 433   /* varpool_nodes_queue is now empty, clear the pointer to the last element
 434      in the queue.  */
 435   varpool_last_needed_node = NULL;
 436   return changed;
 437 }
 438
 439 /* Output all variables enqueued to be assembled.  */
 440 void
 441 varpool_output_debug_info (void)
 442 {
 443   timevar_push (TV_SYMOUT);
 444   if (errorcount == 0 && sorrycount == 0)
 445     while (varpool_assembled_nodes_queue)
 446       {
 447         struct varpool_node *node = varpool_assembled_nodes_queue;
 448
 449         /* Local static variables are never seen by check_global_declarations
 450            so we need to output debug info by hand.  */
 451         if (DECL_CONTEXT (node->decl)
 452             && (TREE_CODE (DECL_CONTEXT (node->decl)) == BLOCK
 453                 || TREE_CODE (DECL_CONTEXT (node->decl)) == FUNCTION_DECL)
 454             && errorcount == 0 && sorrycount == 0)
 455              (*debug_hooks->global_decl) (node->decl);
 456         varpool_assembled_nodes_queue = node->next_needed;
 457         node->next_needed = 0;
 458       }
 459   timevar_pop (TV_SYMOUT);
 460 }
 461
 462 #include "gt-varpool.h"