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