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 emulating tls, we actually see references to the control
 350      variable, rather than the user-level variable.  */
 351   if (!targetm.have_tls
 352       && TREE_CODE (decl) == VAR_DECL
 353       && DECL_THREAD_LOCAL_P (decl))
 354     {
 355       tree control = emutls_decl (decl);
 356       if (decide_is_variable_needed (varpool_node (control), control))
 357         return true;
 358     }
 359
 360   /* When not reordering top level variables, we have to assume that
 361      we are going to keep everything.  */
 362   if (flag_toplevel_reorder)
 363     return false;
 364
 365   /* We want to emit COMDAT variables only when absolutely necessary.  */
 366   if (DECL_COMDAT (decl))
 367     return false;
 368   return true;
 369 }
 370
 371 /* Mark DECL as finalized.  By finalizing the declaration, frontend instruct the
 372    middle end to output the variable to asm file, if needed or externally
 373    visible.  */
 374 void
 375 varpool_finalize_decl (tree decl)
 376 {
 377   struct varpool_node *node = varpool_node (decl);
 378
 379   /* The first declaration of a variable that comes through this function
 380      decides whether it is global (in C, has external linkage)
 381      or local (in C, has internal linkage).  So do nothing more
 382      if this function has already run.  */
 383   if (node->finalized)
 384     {
 385       if (cgraph_global_info_ready)
 386         varpool_assemble_pending_decls ();
 387       return;
 388     }
 389   if (node->needed)
 390     varpool_enqueue_needed_node (node);
 391   node->finalized = true;
 392   if (TREE_THIS_VOLATILE (decl) || DECL_PRESERVE_P (decl))
 393     node->force_output = true;
 394
 395   if (decide_is_variable_needed (node, decl))
 396     varpool_mark_needed_node (node);
 397   /* Since we reclaim unreachable nodes at the end of every language
 398      level unit, we need to be conservative about possible entry points
 399      there.  */
 400   else if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 401     varpool_mark_needed_node (node);
 402   if (cgraph_global_info_ready)
 403     varpool_assemble_pending_decls ();
 404 }
 405
 406 /* Return variable availability.  See cgraph.h for description of individual
 407    return values.  */
 408 enum availability
 409 cgraph_variable_initializer_availability (struct varpool_node *node)
 410 {
 411   gcc_assert (cgraph_function_flags_ready);
 412   if (!node->finalized)
 413     return AVAIL_NOT_AVAILABLE;
 414   if (!TREE_PUBLIC (node->decl))
 415     return AVAIL_AVAILABLE;
 416   /* If the variable can be overwritten, return OVERWRITABLE.  Takes
 417      care of at least two notable extensions - the COMDAT variables
 418      used to share template instantiations in C++.  */
 419   if (!(*targetm.binds_local_p) (node->decl) && !DECL_COMDAT (node->decl))
 420     return AVAIL_OVERWRITABLE;
 421   return AVAIL_AVAILABLE;
 422 }
 423
 424 /* Walk the decls we marked as necessary and see if they reference new
 425    variables or functions and add them into the worklists.  */
 426 bool
 427 varpool_analyze_pending_decls (void)
 428 {
 429   bool changed = false;
 430
 431   timevar_push (TV_VARPOOL);
 432   while (varpool_first_unanalyzed_node)
 433     {
 434       struct varpool_node *node = varpool_first_unanalyzed_node, *next;
 435       tree decl = node->decl;
 436       bool analyzed = node->analyzed;
 437
 438       varpool_first_unanalyzed_node->analyzed = true;
 439
 440       varpool_first_unanalyzed_node = varpool_first_unanalyzed_node->next_needed;
 441
 442       /* When reading back varpool at LTO time, we re-construct the queue in order
 443          to have "needed" list right by inserting all needed nodes into varpool.
 444          We however don't want to re-analyze already analyzed nodes.  */
 445       if (!analyzed)
 446         {
 447           gcc_assert (!in_lto_p || cgraph_function_flags_ready);
 448           /* Compute the alignment early so function body expanders are
 449              already informed about increased alignment.  */
 450           align_variable (decl, 0);
 451         }
 452       if (DECL_INITIAL (decl))
 453         record_references_in_initializer (decl, analyzed);
 454       if (node->same_comdat_group)
 455         {
 456           for (next = node->same_comdat_group;
 457                next != node;
 458                next = next->same_comdat_group)
 459             varpool_mark_needed_node (next);
 460         }
 461       changed = true;
 462     }
 463   timevar_pop (TV_VARPOOL);
 464   return changed;
 465 }
 466
 467 /* Output one variable, if necessary.  Return whether we output it.  */
 468 bool
 469 varpool_assemble_decl (struct varpool_node *node)
 470 {
 471   tree decl = node->decl;
 472
 473   if (!TREE_ASM_WRITTEN (decl)
 474       && !node->alias
 475       && !node->in_other_partition
 476       && !DECL_EXTERNAL (decl)
 477       && (TREE_CODE (decl) != VAR_DECL || !DECL_HAS_VALUE_EXPR_P (decl)))
 478     {
 479       assemble_variable (decl, 0, 1, 0);
 480       if (TREE_ASM_WRITTEN (decl))
 481         {
 482           struct varpool_node *alias;
 483
 484           node->next_needed = varpool_assembled_nodes_queue;
 485           node->prev_needed = NULL;
 486           if (varpool_assembled_nodes_queue)
 487             varpool_assembled_nodes_queue->prev_needed = node;
 488           varpool_assembled_nodes_queue = node;
 489           node->finalized = 1;
 490
 491           /* Also emit any extra name aliases.  */
 492           for (alias = node->extra_name; alias; alias = alias->next)
 493             {
 494               /* Update linkage fields in case they've changed.  */
 495               DECL_WEAK (alias->decl) = DECL_WEAK (decl);
 496               TREE_PUBLIC (alias->decl) = TREE_PUBLIC (decl);
 497               DECL_VISIBILITY (alias->decl) = DECL_VISIBILITY (decl);
 498               assemble_alias (alias->decl, DECL_ASSEMBLER_NAME (decl));
 499             }
 500
 501           return true;
 502         }
 503     }
 504
 505   return false;
 506 }
 507
 508 /* Optimization of function bodies might've rendered some variables as
 509    unnecessary so we want to avoid these from being compiled.
 510
 511    This is done by pruning the queue and keeping only the variables that
 512    really appear needed (ie they are either externally visible or referenced
 513    by compiled function). Re-doing the reachability analysis on variables
 514    brings back the remaining variables referenced by these.  */
 515 void
 516 varpool_remove_unreferenced_decls (void)
 517 {
 518   struct varpool_node *next, *node = varpool_nodes_queue;
 519
 520   varpool_reset_queue ();
 521
 522   if (seen_error ())
 523     return;
 524
 525   while (node)
 526     {
 527       tree decl = node->decl;
 528       next = node->next_needed;
 529       node->needed = 0;
 530
 531       if (node->finalized
 532           && (decide_is_variable_needed (node, decl)
 533               /* ??? Cgraph does not yet rule the world with an iron hand,
 534                  and does not control the emission of debug information.
 535                  After a variable has its DECL_RTL set, we must assume that
 536                  it may be referenced by the debug information, and we can
 537                  no longer elide it.  */
 538               || DECL_RTL_SET_P (decl)))
 539         varpool_mark_needed_node (node);
 540
 541       node = next;
 542     }
 543   /* Make sure we mark alias targets as used targets.  */
 544   finish_aliases_1 ();
 545   varpool_analyze_pending_decls ();
 546 }
 547
 548 /* Output all variables enqueued to be assembled.  */
 549 bool
 550 varpool_assemble_pending_decls (void)
 551 {
 552   bool changed = false;
 553
 554   if (seen_error ())
 555     return false;
 556
 557   timevar_push (TV_VAROUT);
 558   /* EH might mark decls as needed during expansion.  This should be safe since
 559      we don't create references to new function, but it should not be used
 560      elsewhere.  */
 561   varpool_analyze_pending_decls ();
 562
 563   while (varpool_nodes_queue)
 564     {
 565       struct varpool_node *node = varpool_nodes_queue;
 566
 567       varpool_nodes_queue = varpool_nodes_queue->next_needed;
 568       if (varpool_assemble_decl (node))
 569         changed = true;
 570       else
 571         {
 572           node->prev_needed = NULL;
 573           node->next_needed = NULL;
 574         }
 575     }
 576   /* varpool_nodes_queue is now empty, clear the pointer to the last element
 577      in the queue.  */
 578   varpool_last_needed_node = NULL;
 579   timevar_pop (TV_VAROUT);
 580   return changed;
 581 }
 582
 583 /* Remove all elements from the queue so we can re-use it for debug output.  */
 584 void
 585 varpool_empty_needed_queue (void)
 586 {
 587   /* EH might mark decls as needed during expansion.  This should be safe since
 588      we don't create references to new function, but it should not be used
 589      elsewhere.  */
 590   varpool_analyze_pending_decls ();
 591
 592   while (varpool_nodes_queue)
 593     {
 594       struct varpool_node *node = varpool_nodes_queue;
 595       varpool_nodes_queue = varpool_nodes_queue->next_needed;
 596       node->next_needed = NULL;
 597       node->prev_needed = NULL;
 598     }
 599   /* varpool_nodes_queue is now empty, clear the pointer to the last element
 600      in the queue.  */
 601   varpool_last_needed_node = NULL;
 602 }
 603
 604 /* Create a new global variable of type TYPE.  */
 605 tree
 606 add_new_static_var (tree type)
 607 {
 608   tree new_decl;
 609   struct varpool_node *new_node;
 610
 611   new_decl = create_tmp_var (type, NULL);
 612   DECL_NAME (new_decl) = create_tmp_var_name (NULL);
 613   TREE_READONLY (new_decl) = 0;
 614   TREE_STATIC (new_decl) = 1;
 615   TREE_USED (new_decl) = 1;
 616   DECL_CONTEXT (new_decl) = NULL_TREE;
 617   DECL_ABSTRACT (new_decl) = 0;
 618   lang_hooks.dup_lang_specific_decl (new_decl);
 619   create_var_ann (new_decl);
 620   new_node = varpool_node (new_decl);
 621   varpool_mark_needed_node (new_node);
 622   add_referenced_var (new_decl);
 623   varpool_finalize_decl (new_decl);
 624
 625   return new_node->decl;
 626 }
 627
 628 /* Attempt to mark ALIAS as an alias to DECL.  Return TRUE if successful.
 629    Extra name aliases are output whenever DECL is output.  */
 630
 631 bool
 632 varpool_extra_name_alias (tree alias, tree decl)
 633 {
 634   struct varpool_node key, *alias_node, *decl_node, **slot;
 635
 636 #ifndef ASM_OUTPUT_DEF
 637   /* If aliases aren't supported by the assembler, fail.  */
 638   return false;
 639 #endif
 640
 641   gcc_assert (TREE_CODE (decl) == VAR_DECL);
 642   gcc_assert (TREE_CODE (alias) == VAR_DECL);
 643   /* Make sure the hash table has been created.  */
 644   decl_node = varpool_node (decl);
 645
 646   key.decl = alias;
 647
 648   slot = (struct varpool_node **) htab_find_slot (varpool_hash, &key, INSERT);
 649
 650   /* If the varpool_node has been already created, fail.  */
 651   if (*slot)
 652     return false;
 653
 654   alias_node = ggc_alloc_cleared_varpool_node ();
 655   alias_node->decl = alias;
 656   alias_node->alias = 1;
 657   alias_node->extra_name = decl_node;
 658   alias_node->next = decl_node->extra_name;
 659   ipa_empty_ref_list (&alias_node->ref_list);
 660   if (decl_node->extra_name)
 661     decl_node->extra_name->prev = alias_node;
 662   decl_node->extra_name = alias_node;
 663   *slot = alias_node;
 664   return true;
 665 }
 666
 667 #include "gt-varpool.h"