gcc/varpool.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003, 2004, 2005, 2006 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)
 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 not reordering top level variables, we have to assume that
 246      we are going to keep everything.  */
 247   if (flag_unit_at_a_time && flag_toplevel_reorder)
 248     return false;
 249
 250   /* We want to emit COMDAT variables only when absolutely necessary.  */
 251   if (DECL_COMDAT (decl))
 252     return false;
 253   return true;
 254 }
 255
 256 /* Mark DECL as finalized.  By finalizing the declaration, frontend instruct the
 257    middle end to output the variable to asm file, if needed or externally
 258    visible.  */
 259 void
 260 varpool_finalize_decl (tree decl)
 261 {
 262   struct varpool_node *node = varpool_node (decl);
 263
 264   /* The first declaration of a variable that comes through this function
 265      decides whether it is global (in C, has external linkage)
 266      or local (in C, has internal linkage).  So do nothing more
 267      if this function has already run.  */
 268   if (node->finalized)
 269     {
 270       if (cgraph_global_info_ready || (!flag_unit_at_a_time && !flag_openmp))
 271         varpool_assemble_pending_decls ();
 272       return;
 273     }
 274   if (node->needed)
 275     varpool_enqueue_needed_node (node);
 276   node->finalized = true;
 277
 278   if (decide_is_variable_needed (node, decl))
 279     varpool_mark_needed_node (node);
 280   /* Since we reclaim unreachable nodes at the end of every language
 281      level unit, we need to be conservative about possible entry points
 282      there.  */
 283   else if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 284     varpool_mark_needed_node (node);
 285   if (cgraph_global_info_ready || (!flag_unit_at_a_time && !flag_openmp))
 286     varpool_assemble_pending_decls ();
 287 }
 288
 289 /* Return variable availability.  See cgraph.h for description of individual
 290    return values.  */
 291 enum availability
 292 cgraph_variable_initializer_availability (struct varpool_node *node)
 293 {
 294   gcc_assert (cgraph_function_flags_ready);
 295   if (!node->finalized)
 296     return AVAIL_NOT_AVAILABLE;
 297   if (!TREE_PUBLIC (node->decl))
 298     return AVAIL_AVAILABLE;
 299   /* If the variable can be overwritten, return OVERWRITABLE.  Takes
 300      care of at least two notable extensions - the COMDAT variables
 301      used to share template instantiations in C++.  */
 302   if (!(*targetm.binds_local_p) (node->decl) && !DECL_COMDAT (node->decl))
 303     return AVAIL_OVERWRITABLE;
 304   return AVAIL_AVAILABLE;
 305 }
 306
 307 /* Walk the decls we marked as necessary and see if they reference new
 308    variables or functions and add them into the worklists.  */
 309 bool
 310 varpool_analyze_pending_decls (void)
 311 {
 312   bool changed = false;
 313   timevar_push (TV_CGRAPH);
 314
 315   while (varpool_first_unanalyzed_node)
 316     {
 317       tree decl = varpool_first_unanalyzed_node->decl;
 318
 319       varpool_first_unanalyzed_node->analyzed = true;
 320
 321       varpool_first_unanalyzed_node = varpool_first_unanalyzed_node->next_needed;
 322
 323       /* Compute the alignment early so function body expanders are
 324          already informed about increased alignment.  */
 325       align_variable (decl, 0);
 326
 327       if (DECL_INITIAL (decl))
 328         record_references_in_initializer (decl);
 329       changed = true;
 330     }
 331   timevar_pop (TV_CGRAPH);
 332   return changed;
 333 }
 334
 335 /* Output one variable, if necessary.  Return whether we output it.  */
 336 bool
 337 varpool_assemble_decl (struct varpool_node *node)
 338 {
 339   tree decl = node->decl;
 340
 341   if (!TREE_ASM_WRITTEN (decl)
 342       && !node->alias
 343       && !DECL_EXTERNAL (decl)
 344       && (TREE_CODE (decl) != VAR_DECL || !DECL_HAS_VALUE_EXPR_P (decl)))
 345     {
 346       assemble_variable (decl, 0, 1, 0);
 347       return TREE_ASM_WRITTEN (decl);
 348     }
 349
 350   return false;
 351 }
 352
 353 /* Optimization of function bodies might've rendered some variables as
 354    unnecessary so we want to avoid these from being compiled.
 355
 356    This is done by pruning the queue and keeping only the variables that
 357    really appear needed (ie they are either externally visible or referenced
 358    by compiled function). Re-doing the reachability analysis on variables
 359    brings back the remaining variables referenced by these.  */
 360 void
 361 varpool_remove_unreferenced_decls (void)
 362 {
 363   struct varpool_node *next, *node = varpool_nodes_queue;
 364
 365   varpool_reset_queue ();
 366
 367   if (errorcount || sorrycount)
 368     return;
 369
 370   while (node)
 371     {
 372       tree decl = node->decl;
 373       next = node->next_needed;
 374       node->needed = 0;
 375
 376       if (node->finalized
 377           && ((DECL_ASSEMBLER_NAME_SET_P (decl)
 378                && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 379               || node->force_output
 380               || decide_is_variable_needed (node, decl)
 381               /* ??? Cgraph does not yet rule the world with an iron hand,
 382                  and does not control the emission of debug information.
 383                  After a variable has its DECL_RTL set, we must assume that
 384                  it may be referenced by the debug information, and we can
 385                  no longer elide it.  */
 386               || DECL_RTL_SET_P (decl)))
 387         varpool_mark_needed_node (node);
 388
 389       node = next;
 390     }
 391   /* Make sure we mark alias targets as used targets.  */
 392   finish_aliases_1 ();
 393   varpool_analyze_pending_decls ();
 394 }
 395
 396 /* Output all variables enqueued to be assembled.  */
 397 bool
 398 varpool_assemble_pending_decls (void)
 399 {
 400   bool changed = false;
 401
 402   if (errorcount || sorrycount)
 403     return false;
 404
 405   /* EH might mark decls as needed during expansion.  This should be safe since
 406      we don't create references to new function, but it should not be used
 407      elsewhere.  */
 408   varpool_analyze_pending_decls ();
 409
 410   while (varpool_nodes_queue)
 411     {
 412       struct varpool_node *node = varpool_nodes_queue;
 413
 414       varpool_nodes_queue = varpool_nodes_queue->next_needed;
 415       if (varpool_assemble_decl (node))
 416         {
 417           changed = true;
 418           node->next_needed = varpool_assembled_nodes_queue;
 419           varpool_assembled_nodes_queue = node;
 420           node->finalized = 1;
 421         }
 422       else
 423         node->next_needed = NULL;
 424     }
 425   return changed;
 426 }
 427
 428 /* Output all variables enqueued to be assembled.  */
 429 void
 430 varpool_output_debug_info (void)
 431 {
 432   timevar_push (TV_SYMOUT);
 433   if (errorcount == 0 && sorrycount == 0)
 434     while (varpool_assembled_nodes_queue)
 435       {
 436         struct varpool_node *node = varpool_assembled_nodes_queue;
 437
 438         /* Local static variables are never seen by check_global_declarations
 439            so we need to output debug info by hand.  */
 440         if (DECL_CONTEXT (node->decl)
 441             && (TREE_CODE (DECL_CONTEXT (node->decl)) == BLOCK
 442                 || TREE_CODE (DECL_CONTEXT (node->decl)) == FUNCTION_DECL)
 443             && errorcount == 0 && sorrycount == 0)
 444              (*debug_hooks->global_decl) (node->decl);
 445         varpool_assembled_nodes_queue = node->next_needed;
 446         node->next_needed = 0;
 447       }
 448   timevar_pop (TV_SYMOUT);
 449 }
 450
 451 #include "gt-varpool.h"