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