gcc/cgraphunit.c

   1 /* Callgraph based intraprocedural optimizations.
   2    Copyright (C) 2003, 2004, 2005 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, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* This module implements main driver of compilation process as well as
  23    few basic intraprocedural optimizers.
  24
  25    The main scope of this file is to act as an interface in between
  26    tree based frontends and the backend (and middle end)
  27
  28    The front-end is supposed to use following functionality:
  29
  30     - cgraph_finalize_function
  31
  32       This function is called once front-end has parsed whole body of function
  33       and it is certain that the function body nor the declaration will change.
  34
  35       (There is one exception needed for implementing GCC extern inline function.)
  36
  37     - cgraph_varpool_finalize_variable
  38
  39       This function has same behavior as the above but is used for static
  40       variables.
  41
  42     - cgraph_finalize_compilation_unit
  43
  44       This function is called once compilation unit is finalized and it will
  45       no longer change.
  46
  47       In the unit-at-a-time the call-graph construction and local function
  48       analysis takes place here.  Bodies of unreachable functions are released
  49       to conserve memory usage.
  50
  51       ???  The compilation unit in this point of view should be compilation
  52       unit as defined by the language - for instance C frontend allows multiple
  53       compilation units to be parsed at once and it should call function each
  54       time parsing is done so we save memory.
  55
  56     - cgraph_optimize
  57
  58       In this unit-at-a-time compilation the intra procedural analysis takes
  59       place here.  In particular the static functions whose address is never
  60       taken are marked as local.  Backend can then use this information to
  61       modify calling conventions, do better inlining or similar optimizations.
  62
  63     - cgraph_assemble_pending_functions
  64     - cgraph_varpool_assemble_pending_variables
  65
  66       In non-unit-at-a-time mode these functions can be used to force compilation
  67       of functions or variables that are known to be needed at given stage
  68       of compilation
  69
  70     - cgraph_mark_needed_node
  71     - cgraph_varpool_mark_needed_node
  72
  73       When function or variable is referenced by some hidden way (for instance
  74       via assembly code and marked by attribute "used"), the call-graph data structure
  75       must be updated accordingly by this function.
  76
  77     - analyze_expr callback
  78
  79       This function is responsible for lowering tree nodes not understood by
  80       generic code into understandable ones or alternatively marking
  81       callgraph and varpool nodes referenced by the as needed.
  82
  83       ??? On the tree-ssa genericizing should take place here and we will avoid
  84       need for these hooks (replacing them by genericizing hook)
  85
  86     - expand_function callback
  87
  88       This function is used to expand function and pass it into RTL back-end.
  89       Front-end should not make any assumptions about when this function can be
  90       called.  In particular cgraph_assemble_pending_functions,
  91       cgraph_varpool_assemble_pending_variables, cgraph_finalize_function,
  92       cgraph_varpool_finalize_function, cgraph_optimize can cause arbitrarily
  93       previously finalized functions to be expanded.
  94
  95     We implement two compilation modes.
  96
  97       - unit-at-a-time:  In this mode analyzing of all functions is deferred
  98         to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.
  99
 100         In cgraph_finalize_compilation_unit the reachable functions are
 101         analyzed.  During analysis the call-graph edges from reachable
 102         functions are constructed and their destinations are marked as
 103         reachable.  References to functions and variables are discovered too
 104         and variables found to be needed output to the assembly file.  Via
 105         mark_referenced call in assemble_variable functions referenced by
 106         static variables are noticed too.
 107
 108         The intra-procedural information is produced and its existence
 109         indicated by global_info_ready.  Once this flag is set it is impossible
 110         to change function from !reachable to reachable and thus
 111         assemble_variable no longer call mark_referenced.
 112
 113         Finally the call-graph is topologically sorted and all reachable functions
 114         that has not been completely inlined or are not external are output.
 115
 116         ??? It is possible that reference to function or variable is optimized
 117         out.  We can not deal with this nicely because topological order is not
 118         suitable for it.  For tree-ssa we may consider another pass doing
 119         optimization and re-discovering reachable functions.
 120
 121         ??? Reorganize code so variables are output very last and only if they
 122         really has been referenced by produced code, so we catch more cases
 123         where reference has been optimized out.
 124
 125       - non-unit-at-a-time
 126
 127         All functions are variables are output as early as possible to conserve
 128         memory consumption.  This may or may not result in less memory used but
 129         it is still needed for some legacy code that rely on particular ordering
 130         of things output from the compiler.
 131
 132         Varpool data structures are not used and variables are output directly.
 133
 134         Functions are output early using call of
 135         cgraph_assemble_pending_function from cgraph_finalize_function.  The
 136         decision on whether function is needed is made more conservative so
 137         uninlininable static functions are needed too.  During the call-graph
 138         construction the edge destinations are not marked as reachable and it
 139         is completely relied upn assemble_variable to mark them.  */
 140
 141
 142 #include "config.h"
 143 #include "system.h"
 144 #include "coretypes.h"
 145 #include "tm.h"
 146 #include "tree.h"
 147 #include "rtl.h"
 148 #include "tree-flow.h"
 149 #include "tree-inline.h"
 150 #include "langhooks.h"
 151 #include "pointer-set.h"
 152 #include "toplev.h"
 153 #include "flags.h"
 154 #include "ggc.h"
 155 #include "debug.h"
 156 #include "target.h"
 157 #include "cgraph.h"
 158 #include "diagnostic.h"
 159 #include "timevar.h"
 160 #include "params.h"
 161 #include "fibheap.h"
 162 #include "c-common.h"
 163 #include "intl.h"
 164 #include "function.h"
 165 #include "tree-gimple.h"
 166 #include "tree-pass.h"
 167 #include "output.h"
 168
 169 static void cgraph_expand_all_functions (void);
 170 static void cgraph_mark_functions_to_output (void);
 171 static void cgraph_expand_function (struct cgraph_node *);
 172 static tree record_reference (tree *, int *, void *);
 173 static void cgraph_analyze_function (struct cgraph_node *node);
 174
 175 /* Records tree nodes seen in record_reference.  Simply using
 176    walk_tree_without_duplicates doesn't guarantee each node is visited
 177    once because it gets a new htab upon each recursive call from
 178    record_reference itself.  */
 179 static struct pointer_set_t *visited_nodes;
 180
 181 static FILE *cgraph_dump_file;
 182
 183 /* Determine if function DECL is needed.  That is, visible to something
 184    either outside this translation unit, something magic in the system
 185    configury, or (if not doing unit-at-a-time) to something we havn't
 186    seen yet.  */
 187
 188 static bool
 189 decide_is_function_needed (struct cgraph_node *node, tree decl)
 190 {
 191   tree origin;
 192
 193   /* If the user told us it is used, then it must be so.  */
 194   if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
 195     return true;
 196
 197   /* ??? If the assembler name is set by hand, it is possible to assemble
 198      the name later after finalizing the function and the fact is noticed
 199      in assemble_name then.  This is arguably a bug.  */
 200   if (DECL_ASSEMBLER_NAME_SET_P (decl)
 201       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 202     return true;
 203
 204   /* If we decided it was needed before, but at the time we didn't have
 205      the body of the function available, then it's still needed.  We have
 206      to go back and re-check its dependencies now.  */
 207   if (node->needed)
 208     return true;
 209
 210   /* Externally visible functions must be output.  The exception is
 211      COMDAT functions that must be output only when they are needed.  */
 212   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 213     return true;
 214
 215   /* Constructors and destructors are reachable from the runtime by
 216      some mechanism.  */
 217   if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
 218     return true;
 219
 220   if (flag_unit_at_a_time)
 221     return false;
 222
 223   /* If not doing unit at a time, then we'll only defer this function
 224      if its marked for inlining.  Otherwise we want to emit it now.  */
 225
 226   /* "extern inline" functions are never output locally.  */
 227   if (DECL_EXTERNAL (decl))
 228     return false;
 229   /* Nested functions of extern inline function shall not be emit unless
 230      we inlined the origin.  */
 231   for (origin = decl_function_context (decl); origin;
 232        origin = decl_function_context (origin))
 233     if (DECL_EXTERNAL (origin))
 234       return false;
 235   /* We want to emit COMDAT functions only when absolutely necessary.  */
 236   if (DECL_COMDAT (decl))
 237     return false;
 238   if (!DECL_INLINE (decl)
 239       || (!node->local.disregard_inline_limits
 240           /* When declared inline, defer even the uninlinable functions.
 241              This allows them to be eliminated when unused.  */
 242           && !DECL_DECLARED_INLINE_P (decl)
 243           && (!node->local.inlinable || !cgraph_default_inline_p (node))))
 244     return true;
 245
 246   return false;
 247 }
 248
 249 /* Walk the decls we marked as necessary and see if they reference new
 250    variables or functions and add them into the worklists.  */
 251 static bool
 252 cgraph_varpool_analyze_pending_decls (void)
 253 {
 254   bool changed = false;
 255   timevar_push (TV_CGRAPH);
 256
 257   while (cgraph_varpool_first_unanalyzed_node)
 258     {
 259       tree decl = cgraph_varpool_first_unanalyzed_node->decl;
 260
 261       cgraph_varpool_first_unanalyzed_node->analyzed = true;
 262
 263       cgraph_varpool_first_unanalyzed_node = cgraph_varpool_first_unanalyzed_node->next_needed;
 264
 265       if (DECL_INITIAL (decl))
 266         {
 267           visited_nodes = pointer_set_create ();
 268           walk_tree (&DECL_INITIAL (decl), record_reference, NULL, visited_nodes);
 269           pointer_set_destroy (visited_nodes);
 270           visited_nodes = NULL;
 271         }
 272       changed = true;
 273     }
 274   timevar_pop (TV_CGRAPH);
 275   return changed;
 276 }
 277
 278 /* Optimization of function bodies might've rendered some variables as
 279    unnecessary so we want to avoid these from being compiled.
 280
 281    This is done by pruning the queue and keeping only the variables that
 282    really appear needed (ie they are either externally visible or referenced
 283    by compiled function). Re-doing the reachability analysis on variables
 284    brings back the remaining variables referenced by these.  */
 285 static void
 286 cgraph_varpool_remove_unreferenced_decls (void)
 287 {
 288   struct cgraph_varpool_node *next, *node = cgraph_varpool_nodes_queue;
 289
 290   cgraph_varpool_reset_queue ();
 291
 292   if (errorcount || sorrycount)
 293     return;
 294
 295   while (node)
 296     {
 297       tree decl = node->decl;
 298       next = node->next_needed;
 299       node->needed = 0;
 300
 301       if (node->finalized
 302           && ((DECL_ASSEMBLER_NAME_SET_P (decl)
 303                && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 304               || node->force_output
 305               || decide_is_variable_needed (node, decl)))
 306         cgraph_varpool_mark_needed_node (node);
 307
 308       node = next;
 309     }
 310   cgraph_varpool_analyze_pending_decls ();
 311 }
 312
 313
 314 /* When not doing unit-at-a-time, output all functions enqueued.
 315    Return true when such a functions were found.  */
 316
 317 bool
 318 cgraph_assemble_pending_functions (void)
 319 {
 320   bool output = false;
 321
 322   if (flag_unit_at_a_time)
 323     return false;
 324
 325   while (cgraph_nodes_queue)
 326     {
 327       struct cgraph_node *n = cgraph_nodes_queue;
 328
 329       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
 330       n->next_needed = NULL;
 331       if (!n->global.inlined_to
 332           && !n->alias
 333           && !DECL_EXTERNAL (n->decl))
 334         {
 335           cgraph_expand_function (n);
 336           output = true;
 337         }
 338     }
 339
 340   return output;
 341 }
 342 /* As an GCC extension we allow redefinition of the function.  The
 343    semantics when both copies of bodies differ is not well defined.
 344    We replace the old body with new body so in unit at a time mode
 345    we always use new body, while in normal mode we may end up with
 346    old body inlined into some functions and new body expanded and
 347    inlined in others.
 348
 349    ??? It may make more sense to use one body for inlining and other
 350    body for expanding the function but this is difficult to do.  */
 351
 352 static void
 353 cgraph_reset_node (struct cgraph_node *node)
 354 {
 355   /* If node->output is set, then this is a unit-at-a-time compilation
 356      and we have already begun whole-unit analysis.  This is *not*
 357      testing for whether we've already emitted the function.  That
 358      case can be sort-of legitimately seen with real function
 359      redefinition errors.  I would argue that the front end should
 360      never present us with such a case, but don't enforce that for now.  */
 361   gcc_assert (!node->output);
 362
 363   /* Reset our data structures so we can analyze the function again.  */
 364   memset (&node->local, 0, sizeof (node->local));
 365   memset (&node->global, 0, sizeof (node->global));
 366   memset (&node->rtl, 0, sizeof (node->rtl));
 367   node->analyzed = false;
 368   node->local.redefined_extern_inline = true;
 369   node->local.finalized = false;
 370
 371   if (!flag_unit_at_a_time)
 372     {
 373       struct cgraph_node *n;
 374
 375       for (n = cgraph_nodes; n; n = n->next)
 376         if (n->global.inlined_to == node)
 377           cgraph_remove_node (n);
 378     }
 379
 380   cgraph_node_remove_callees (node);
 381
 382   /* We may need to re-queue the node for assembling in case
 383      we already proceeded it and ignored as not needed.  */
 384   if (node->reachable && !flag_unit_at_a_time)
 385     {
 386       struct cgraph_node *n;
 387
 388       for (n = cgraph_nodes_queue; n; n = n->next_needed)
 389         if (n == node)
 390           break;
 391       if (!n)
 392         node->reachable = 0;
 393     }
 394 }
 395
 396 /* DECL has been parsed.  Take it, queue it, compile it at the whim of the
 397    logic in effect.  If NESTED is true, then our caller cannot stand to have
 398    the garbage collector run at the moment.  We would need to either create
 399    a new GC context, or just not compile right now.  */
 400
 401 void
 402 cgraph_finalize_function (tree decl, bool nested)
 403 {
 404   struct cgraph_node *node = cgraph_node (decl);
 405
 406   if (node->local.finalized)
 407     cgraph_reset_node (node);
 408
 409   notice_global_symbol (decl);
 410   node->decl = decl;
 411   node->local.finalized = true;
 412   node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;
 413   if (node->nested)
 414     lower_nested_functions (decl);
 415   gcc_assert (!node->nested);
 416
 417   /* If not unit at a time, then we need to create the call graph
 418      now, so that called functions can be queued and emitted now.  */
 419   if (!flag_unit_at_a_time)
 420     {
 421       cgraph_analyze_function (node);
 422       cgraph_decide_inlining_incrementally (node);
 423     }
 424
 425   if (decide_is_function_needed (node, decl))
 426     cgraph_mark_needed_node (node);
 427
 428   /* Since we reclaim unreachable nodes at the end of every language
 429      level unit, we need to be conservative about possible entry points
 430      there.  */
 431   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 432     cgraph_mark_reachable_node (node);
 433
 434   /* If not unit at a time, go ahead and emit everything we've found
 435      to be reachable at this time.  */
 436   if (!nested)
 437     {
 438       if (!cgraph_assemble_pending_functions ())
 439         ggc_collect ();
 440     }
 441
 442   /* If we've not yet emitted decl, tell the debug info about it.  */
 443   if (!TREE_ASM_WRITTEN (decl))
 444     (*debug_hooks->deferred_inline_function) (decl);
 445
 446   /* Possibly warn about unused parameters.  */
 447   if (warn_unused_parameter)
 448     do_warn_unused_parameter (decl);
 449 }
 450
 451 void
 452 cgraph_lower_function (struct cgraph_node *node)
 453 {
 454   if (node->lowered)
 455     return;
 456   tree_lowering_passes (node->decl);
 457   node->lowered = true;
 458 }
 459
 460 /* Walk tree and record all calls.  Called via walk_tree.  */
 461 static tree
 462 record_reference (tree *tp, int *walk_subtrees, void *data)
 463 {
 464   tree t = *tp;
 465
 466   switch (TREE_CODE (t))
 467     {
 468     case VAR_DECL:
 469       /* ??? Really, we should mark this decl as *potentially* referenced
 470          by this function and re-examine whether the decl is actually used
 471          after rtl has been generated.  */
 472       if (TREE_STATIC (t) || DECL_EXTERNAL (t))
 473         {
 474           cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));
 475           if (lang_hooks.callgraph.analyze_expr)
 476             return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees,
 477                                                       data);
 478         }
 479       break;
 480
 481     case FDESC_EXPR:
 482     case ADDR_EXPR:
 483       if (flag_unit_at_a_time)
 484         {
 485           /* Record dereferences to the functions.  This makes the
 486              functions reachable unconditionally.  */
 487           tree decl = TREE_OPERAND (*tp, 0);
 488           if (TREE_CODE (decl) == FUNCTION_DECL)
 489             cgraph_mark_needed_node (cgraph_node (decl));
 490         }
 491       break;
 492
 493     default:
 494       /* Save some cycles by not walking types and declaration as we
 495          won't find anything useful there anyway.  */
 496       if (IS_TYPE_OR_DECL_P (*tp))
 497         {
 498           *walk_subtrees = 0;
 499           break;
 500         }
 501
 502       if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
 503         return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees, data);
 504       break;
 505     }
 506
 507   return NULL;
 508 }
 509
 510 /* Create cgraph edges for function calls inside BODY from NODE.  */
 511
 512 static void
 513 cgraph_create_edges (struct cgraph_node *node, tree body)
 514 {
 515   basic_block bb;
 516
 517   struct function *this_cfun = DECL_STRUCT_FUNCTION (body);
 518   block_stmt_iterator bsi;
 519   tree step;
 520   visited_nodes = pointer_set_create ();
 521
 522   /* Reach the trees by walking over the CFG, and note the
 523      enclosing basic-blocks in the call edges.  */
 524   FOR_EACH_BB_FN (bb, this_cfun)
 525     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 526       {
 527         tree stmt = bsi_stmt (bsi);
 528         tree call = get_call_expr_in (stmt);
 529         tree decl;
 530
 531         if (call && (decl = get_callee_fndecl (call)))
 532           {
 533             cgraph_create_edge (node, cgraph_node (decl), stmt,
 534                                 bb->count,
 535                                 bb->loop_depth);
 536             walk_tree (&TREE_OPERAND (call, 1),
 537                        record_reference, node, visited_nodes);
 538             if (TREE_CODE (stmt) == MODIFY_EXPR)
 539               walk_tree (&TREE_OPERAND (stmt, 0),
 540                          record_reference, node, visited_nodes);
 541           }
 542         else
 543           walk_tree (bsi_stmt_ptr (bsi), record_reference, node, visited_nodes);
 544       }
 545
 546   /* Walk over any private statics that may take addresses of functions.  */
 547   if (TREE_CODE (DECL_INITIAL (body)) == BLOCK)
 548     {
 549       for (step = BLOCK_VARS (DECL_INITIAL (body));
 550            step;
 551            step = TREE_CHAIN (step))
 552         if (DECL_INITIAL (step))
 553           walk_tree (&DECL_INITIAL (step), record_reference, node, visited_nodes);
 554     }
 555
 556   /* Also look here for private statics.  */
 557   if (DECL_STRUCT_FUNCTION (body))
 558     for (step = DECL_STRUCT_FUNCTION (body)->unexpanded_var_list;
 559          step;
 560          step = TREE_CHAIN (step))
 561       {
 562         tree decl = TREE_VALUE (step);
 563         if (DECL_INITIAL (decl) && TREE_STATIC (decl))
 564           walk_tree (&DECL_INITIAL (decl), record_reference, node, visited_nodes);
 565       }
 566
 567   pointer_set_destroy (visited_nodes);
 568   visited_nodes = NULL;
 569 }
 570
 571
 572 /* Verify cgraph nodes of given cgraph node.  */
 573 void
 574 verify_cgraph_node (struct cgraph_node *node)
 575 {
 576   struct cgraph_edge *e;
 577   struct cgraph_node *main_clone;
 578   struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
 579   basic_block this_block;
 580   block_stmt_iterator bsi;
 581   bool error_found = false;
 582
 583   timevar_push (TV_CGRAPH_VERIFY);
 584   for (e = node->callees; e; e = e->next_callee)
 585     if (e->aux)
 586       {
 587         error ("Aux field set for edge %s->%s",
 588                cgraph_node_name (e->caller), cgraph_node_name (e->callee));
 589         error_found = true;
 590       }
 591   for (e = node->callers; e; e = e->next_caller)
 592     {
 593       if (!e->inline_failed)
 594         {
 595           if (node->global.inlined_to
 596               != (e->caller->global.inlined_to
 597                   ? e->caller->global.inlined_to : e->caller))
 598             {
 599               error ("Inlined_to pointer is wrong");
 600               error_found = true;
 601             }
 602           if (node->callers->next_caller)
 603             {
 604               error ("Multiple inline callers");
 605               error_found = true;
 606             }
 607         }
 608       else
 609         if (node->global.inlined_to)
 610           {
 611             error ("Inlined_to pointer set for noninline callers");
 612             error_found = true;
 613           }
 614     }
 615   if (!node->callers && node->global.inlined_to)
 616     {
 617       error ("Inlined_to pointer is set but no predecesors found");
 618       error_found = true;
 619     }
 620   if (node->global.inlined_to == node)
 621     {
 622       error ("Inlined_to pointer refers to itself");
 623       error_found = true;
 624     }
 625
 626   for (main_clone = cgraph_node (node->decl); main_clone;
 627        main_clone = main_clone->next_clone)
 628     if (main_clone == node)
 629       break;
 630   if (!node)
 631     {
 632       error ("Node not found in DECL_ASSEMBLER_NAME hash");
 633       error_found = true;
 634     }
 635
 636   if (node->analyzed
 637       && DECL_SAVED_TREE (node->decl) && !TREE_ASM_WRITTEN (node->decl)
 638       && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to))
 639     {
 640       if (this_cfun->cfg)
 641         {
 642           /* The nodes we're interested in are never shared, so walk
 643              the tree ignoring duplicates.  */
 644           visited_nodes = pointer_set_create ();
 645           /* Reach the trees by walking over the CFG, and note the
 646              enclosing basic-blocks in the call edges.  */
 647           FOR_EACH_BB_FN (this_block, this_cfun)
 648             for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
 649               {
 650                 tree stmt = bsi_stmt (bsi);
 651                 tree call = get_call_expr_in (stmt);
 652                 tree decl;
 653                 if (call && (decl = get_callee_fndecl (call)))
 654                   {
 655                     struct cgraph_edge *e = cgraph_edge (node, stmt);
 656                     if (e)
 657                       {
 658                         if (e->aux)
 659                           {
 660                             error ("Shared call_stmt:");
 661                             debug_generic_stmt (stmt);
 662                             error_found = true;
 663                           }
 664                         if (e->callee->decl != cgraph_node (decl)->decl)
 665                           {
 666                             error ("Edge points to wrong declaration:");
 667                             debug_tree (e->callee->decl);
 668                             fprintf (stderr," Instead of:");
 669                             debug_tree (decl);
 670                           }
 671                         e->aux = (void *)1;
 672                       }
 673                     else
 674                       {
 675                         error ("Missing callgraph edge for call stmt:");
 676                         debug_generic_stmt (stmt);
 677                         error_found = true;
 678                       }
 679                   }
 680               }
 681           pointer_set_destroy (visited_nodes);
 682           visited_nodes = NULL;
 683         }
 684       else
 685         /* No CFG available?!  */
 686         gcc_unreachable ();
 687
 688       for (e = node->callees; e; e = e->next_callee)
 689         {
 690           if (!e->aux)
 691             {
 692               error ("Edge %s->%s has no corresponding call_stmt",
 693                      cgraph_node_name (e->caller),
 694                      cgraph_node_name (e->callee));
 695               debug_generic_stmt (e->call_stmt);
 696               error_found = true;
 697             }
 698           e->aux = 0;
 699         }
 700     }
 701   if (error_found)
 702     {
 703       dump_cgraph_node (stderr, node);
 704       internal_error ("verify_cgraph_node failed.");
 705     }
 706   timevar_pop (TV_CGRAPH_VERIFY);
 707 }
 708
 709 /* Verify whole cgraph structure.  */
 710 void
 711 verify_cgraph (void)
 712 {
 713   struct cgraph_node *node;
 714
 715   if (sorrycount || errorcount)
 716     return;
 717
 718   for (node = cgraph_nodes; node; node = node->next)
 719     verify_cgraph_node (node);
 720 }
 721
 722
 723 /* Output all variables enqueued to be assembled.  */
 724 bool
 725 cgraph_varpool_assemble_pending_decls (void)
 726 {
 727   bool changed = false;
 728
 729   if (errorcount || sorrycount)
 730     return false;
 731
 732   /* EH might mark decls as needed during expansion.  This should be safe since
 733      we don't create references to new function, but it should not be used
 734      elsewhere.  */
 735   cgraph_varpool_analyze_pending_decls ();
 736
 737   while (cgraph_varpool_nodes_queue)
 738     {
 739       tree decl = cgraph_varpool_nodes_queue->decl;
 740       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
 741
 742       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
 743       if (!TREE_ASM_WRITTEN (decl) && !node->alias && !DECL_EXTERNAL (decl))
 744         {
 745           assemble_variable (decl, 0, 1, 0);
 746           changed = true;
 747         }
 748       node->next_needed = NULL;
 749     }
 750   return changed;
 751 }
 752
 753 /* Analyze the function scheduled to be output.  */
 754 static void
 755 cgraph_analyze_function (struct cgraph_node *node)
 756 {
 757   tree decl = node->decl;
 758   struct cgraph_edge *e;
 759
 760   current_function_decl = decl;
 761   push_cfun (DECL_STRUCT_FUNCTION (decl));
 762   cgraph_lower_function (node);
 763
 764   /* First kill forward declaration so reverse inlining works properly.  */
 765   cgraph_create_edges (node, decl);
 766
 767   node->local.inlinable = tree_inlinable_function_p (decl);
 768   node->local.self_insns = estimate_num_insns (decl);
 769   if (node->local.inlinable)
 770     node->local.disregard_inline_limits
 771       = lang_hooks.tree_inlining.disregard_inline_limits (decl);
 772   for (e = node->callers; e; e = e->next_caller)
 773     {
 774       if (node->local.redefined_extern_inline)
 775         e->inline_failed = N_("redefined extern inline functions are not "
 776                            "considered for inlining");
 777       else if (!node->local.inlinable)
 778         e->inline_failed = N_("function not inlinable");
 779       else
 780         e->inline_failed = N_("function not considered for inlining");
 781     }
 782   if (flag_really_no_inline && !node->local.disregard_inline_limits)
 783     node->local.inlinable = 0;
 784   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
 785   node->global.insns = node->local.self_insns;
 786
 787   node->analyzed = true;
 788   pop_cfun ();
 789   current_function_decl = NULL;
 790 }
 791
 792 /* Analyze the whole compilation unit once it is parsed completely.  */
 793
 794 void
 795 cgraph_finalize_compilation_unit (void)
 796 {
 797   struct cgraph_node *node;
 798   /* Keep track of already processed nodes when called multiple times for
 799      intermodule optimization.  */
 800   static struct cgraph_node *first_analyzed;
 801
 802   finish_aliases_1 ();
 803
 804   if (!flag_unit_at_a_time)
 805     {
 806       cgraph_assemble_pending_functions ();
 807       return;
 808     }
 809
 810   if (!quiet_flag)
 811     {
 812       fprintf (stderr, "\nAnalyzing compilation unit");
 813       fflush (stderr);
 814     }
 815
 816   timevar_push (TV_CGRAPH);
 817   cgraph_varpool_analyze_pending_decls ();
 818   if (cgraph_dump_file)
 819     {
 820       fprintf (cgraph_dump_file, "Initial entry points:");
 821       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
 822         if (node->needed && DECL_SAVED_TREE (node->decl))
 823           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 824       fprintf (cgraph_dump_file, "\n");
 825     }
 826
 827   /* Propagate reachability flag and lower representation of all reachable
 828      functions.  In the future, lowering will introduce new functions and
 829      new entry points on the way (by template instantiation and virtual
 830      method table generation for instance).  */
 831   while (cgraph_nodes_queue)
 832     {
 833       struct cgraph_edge *edge;
 834       tree decl = cgraph_nodes_queue->decl;
 835
 836       node = cgraph_nodes_queue;
 837       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
 838       node->next_needed = NULL;
 839
 840       /* ??? It is possible to create extern inline function and later using
 841          weak alias attribute to kill its body. See
 842          gcc.c-torture/compile/20011119-1.c  */
 843       if (!DECL_SAVED_TREE (decl))
 844         {
 845           cgraph_reset_node (node);
 846           continue;
 847         }
 848
 849       gcc_assert (!node->analyzed && node->reachable);
 850       gcc_assert (DECL_SAVED_TREE (decl));
 851
 852       cgraph_analyze_function (node);
 853
 854       for (edge = node->callees; edge; edge = edge->next_callee)
 855         if (!edge->callee->reachable)
 856           cgraph_mark_reachable_node (edge->callee);
 857
 858       cgraph_varpool_analyze_pending_decls ();
 859     }
 860
 861   /* Collect entry points to the unit.  */
 862
 863   if (cgraph_dump_file)
 864     {
 865       fprintf (cgraph_dump_file, "Unit entry points:");
 866       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
 867         if (node->needed && DECL_SAVED_TREE (node->decl))
 868           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 869       fprintf (cgraph_dump_file, "\n\nInitial ");
 870       dump_cgraph (cgraph_dump_file);
 871     }
 872
 873   if (cgraph_dump_file)
 874     fprintf (cgraph_dump_file, "\nReclaiming functions:");
 875
 876   for (node = cgraph_nodes; node != first_analyzed; node = node->next)
 877     {
 878       tree decl = node->decl;
 879
 880       if (node->local.finalized && !DECL_SAVED_TREE (decl))
 881         cgraph_reset_node (node);
 882
 883       if (!node->reachable && DECL_SAVED_TREE (decl))
 884         {
 885           if (cgraph_dump_file)
 886             fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 887           cgraph_remove_node (node);
 888           continue;
 889         }
 890       else
 891         node->next_needed = NULL;
 892       gcc_assert (!node->local.finalized || DECL_SAVED_TREE (decl));
 893       gcc_assert (node->analyzed == node->local.finalized);
 894     }
 895   if (cgraph_dump_file)
 896     {
 897       fprintf (cgraph_dump_file, "\n\nReclaimed ");
 898       dump_cgraph (cgraph_dump_file);
 899     }
 900   first_analyzed = cgraph_nodes;
 901   ggc_collect ();
 902   timevar_pop (TV_CGRAPH);
 903 }
 904 /* Figure out what functions we want to assemble.  */
 905
 906 static void
 907 cgraph_mark_functions_to_output (void)
 908 {
 909   struct cgraph_node *node;
 910
 911   for (node = cgraph_nodes; node; node = node->next)
 912     {
 913       tree decl = node->decl;
 914       struct cgraph_edge *e;
 915
 916       gcc_assert (!node->output);
 917
 918       for (e = node->callers; e; e = e->next_caller)
 919         if (e->inline_failed)
 920           break;
 921
 922       /* We need to output all local functions that are used and not
 923          always inlined, as well as those that are reachable from
 924          outside the current compilation unit.  */
 925       if (DECL_SAVED_TREE (decl)
 926           && !node->global.inlined_to
 927           && (node->needed
 928               || (e && node->reachable))
 929           && !TREE_ASM_WRITTEN (decl)
 930           && !DECL_EXTERNAL (decl))
 931         node->output = 1;
 932       else
 933         {
 934           /* We should've reclaimed all functions that are not needed.  */
 935 #ifdef ENABLE_CHECKING
 936           if (!node->global.inlined_to && DECL_SAVED_TREE (decl)
 937               && !DECL_EXTERNAL (decl))
 938             {
 939               dump_cgraph_node (stderr, node);
 940               internal_error ("failed to reclaim unneeded function");
 941             }
 942 #endif
 943           gcc_assert (node->global.inlined_to || !DECL_SAVED_TREE (decl)
 944                       || DECL_EXTERNAL (decl));
 945
 946         }
 947
 948     }
 949 }
 950
 951 /* Expand function specified by NODE.  */
 952
 953 static void
 954 cgraph_expand_function (struct cgraph_node *node)
 955 {
 956   tree decl = node->decl;
 957
 958   /* We ought to not compile any inline clones.  */
 959   gcc_assert (!node->global.inlined_to);
 960
 961   if (flag_unit_at_a_time)
 962     announce_function (decl);
 963
 964   cgraph_lower_function (node);
 965
 966   /* Generate RTL for the body of DECL.  */
 967   lang_hooks.callgraph.expand_function (decl);
 968
 969   /* Make sure that BE didn't give up on compiling.  */
 970   /* ??? Can happen with nested function of extern inline.  */
 971   gcc_assert (TREE_ASM_WRITTEN (node->decl));
 972
 973   current_function_decl = NULL;
 974   if (!cgraph_preserve_function_body_p (node->decl))
 975     {
 976       DECL_SAVED_TREE (node->decl) = NULL;
 977       DECL_STRUCT_FUNCTION (node->decl) = NULL;
 978       DECL_INITIAL (node->decl) = error_mark_node;
 979       /* Eliminate all call edges.  This is important so the call_expr no longer
 980          points to the dead function body.  */
 981       cgraph_node_remove_callees (node);
 982     }
 983
 984   cgraph_function_flags_ready = true;
 985 }
 986
 987 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL.  */
 988
 989 bool
 990 cgraph_inline_p (struct cgraph_edge *e, const char **reason)
 991 {
 992   *reason = e->inline_failed;
 993   return !e->inline_failed;
 994 }
 995
 996
 997
 998 /* Expand all functions that must be output.
 999
1000    Attempt to topologically sort the nodes so function is output when
1001    all called functions are already assembled to allow data to be
1002    propagated across the callgraph.  Use a stack to get smaller distance
1003    between a function and its callees (later we may choose to use a more
1004    sophisticated algorithm for function reordering; we will likely want
1005    to use subsections to make the output functions appear in top-down
1006    order).  */
1007
1008 static void
1009 cgraph_expand_all_functions (void)
1010 {
1011   struct cgraph_node *node;
1012   struct cgraph_node **order =
1013     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1014   int order_pos = 0, new_order_pos = 0;
1015   int i;
1016
1017   order_pos = cgraph_postorder (order);
1018   gcc_assert (order_pos == cgraph_n_nodes);
1019
1020   /* Garbage collector may remove inline clones we eliminate during
1021      optimization.  So we must be sure to not reference them.  */
1022   for (i = 0; i < order_pos; i++)
1023     if (order[i]->output)
1024       order[new_order_pos++] = order[i];
1025
1026   for (i = new_order_pos - 1; i >= 0; i--)
1027     {
1028       node = order[i];
1029       if (node->output)
1030         {
1031           gcc_assert (node->reachable);
1032           node->output = 0;
1033           cgraph_expand_function (node);
1034         }
1035     }
1036   free (order);
1037 }
1038
1039 /* Mark visibility of all functions.
1040
1041    A local function is one whose calls can occur only in the current
1042    compilation unit and all its calls are explicit, so we can change
1043    its calling convention.  We simply mark all static functions whose
1044    address is not taken as local.
1045
1046    We also change the TREE_PUBLIC flag of all declarations that are public
1047    in language point of view but we want to overwrite this default
1048    via visibilities for the backend point of view.  */
1049
1050 static void
1051 cgraph_function_and_variable_visibility (void)
1052 {
1053   struct cgraph_node *node;
1054   struct cgraph_varpool_node *vnode;
1055
1056   for (node = cgraph_nodes; node; node = node->next)
1057     {
1058       if (node->reachable
1059           && (DECL_COMDAT (node->decl)
1060               || (TREE_PUBLIC (node->decl) && !DECL_EXTERNAL (node->decl))))
1061         node->local.externally_visible = 1;
1062       node->local.local = (!node->needed
1063                            && node->analyzed
1064                            && !DECL_EXTERNAL (node->decl)
1065                            && !node->local.externally_visible);
1066     }
1067   for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed)
1068     {
1069       if (vnode->needed
1070           && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl)))
1071         vnode->externally_visible = 1;
1072      gcc_assert (TREE_STATIC (vnode->decl));
1073     }
1074
1075   /* Because we have to be conservative on the boundaries of source
1076      level units, it is possible that we marked some functions in
1077      reachable just because they might be used later via external
1078      linkage, but after making them local they are really unreachable
1079      now.  */
1080   cgraph_remove_unreachable_nodes (true, cgraph_dump_file);
1081
1082   if (cgraph_dump_file)
1083     {
1084       fprintf (cgraph_dump_file, "\nMarking local functions:");
1085       for (node = cgraph_nodes; node; node = node->next)
1086         if (node->local.local)
1087           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1088       fprintf (cgraph_dump_file, "\n\n");
1089       fprintf (cgraph_dump_file, "\nMarking externally visible functions:");
1090       for (node = cgraph_nodes; node; node = node->next)
1091         if (node->local.externally_visible)
1092           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1093       fprintf (cgraph_dump_file, "\n\n");
1094     }
1095   cgraph_function_flags_ready = true;
1096 }
1097
1098 /* Return true when function body of DECL still needs to be kept around
1099    for later re-use.  */
1100 bool
1101 cgraph_preserve_function_body_p (tree decl)
1102 {
1103   struct cgraph_node *node;
1104   /* Keep the body; we're going to dump it.  */
1105   if (dump_enabled_p (TDI_tree_all))
1106     return true;
1107   if (!cgraph_global_info_ready)
1108     return (DECL_INLINE (decl) && !flag_really_no_inline);
1109   /* Look if there is any clone around.  */
1110   for (node = cgraph_node (decl); node; node = node->next_clone)
1111     if (node->global.inlined_to)
1112       return true;
1113   return false;
1114 }
1115
1116 /* Perform simple optimizations based on callgraph.  */
1117
1118 void
1119 cgraph_optimize (void)
1120 {
1121 #ifdef ENABLE_CHECKING
1122   verify_cgraph ();
1123 #endif
1124   if (!flag_unit_at_a_time)
1125     {
1126       cgraph_varpool_assemble_pending_decls ();
1127       return;
1128     }
1129
1130   process_pending_assemble_externals ();
1131
1132   /* Frontend may output common variables after the unit has been finalized.
1133      It is safe to deal with them here as they are always zero initialized.  */
1134   cgraph_varpool_analyze_pending_decls ();
1135
1136   timevar_push (TV_CGRAPHOPT);
1137   if (!quiet_flag)
1138     fprintf (stderr, "Performing intraprocedural optimizations\n");
1139
1140   cgraph_function_and_variable_visibility ();
1141   if (cgraph_dump_file)
1142     {
1143       fprintf (cgraph_dump_file, "Marked ");
1144       dump_cgraph (cgraph_dump_file);
1145     }
1146   ipa_passes ();
1147   /* This pass remove bodies of extern inline functions we never inlined.
1148      Do this later so other IPA passes see what is really going on.  */
1149   cgraph_remove_unreachable_nodes (false, dump_file);
1150   cgraph_global_info_ready = true;
1151   if (cgraph_dump_file)
1152     {
1153       fprintf (cgraph_dump_file, "Optimized ");
1154       dump_cgraph (cgraph_dump_file);
1155       dump_varpool (cgraph_dump_file);
1156     }
1157   timevar_pop (TV_CGRAPHOPT);
1158
1159   /* Output everything.  */
1160   if (!quiet_flag)
1161     fprintf (stderr, "Assembling functions:\n");
1162 #ifdef ENABLE_CHECKING
1163   verify_cgraph ();
1164 #endif
1165
1166   cgraph_mark_functions_to_output ();
1167   cgraph_expand_all_functions ();
1168   cgraph_varpool_remove_unreferenced_decls ();
1169
1170   cgraph_varpool_assemble_pending_decls ();
1171
1172   if (cgraph_dump_file)
1173     {
1174       fprintf (cgraph_dump_file, "\nFinal ");
1175       dump_cgraph (cgraph_dump_file);
1176     }
1177 #ifdef ENABLE_CHECKING
1178   verify_cgraph ();
1179   /* Double check that all inline clones are gone and that all
1180      function bodies have been released from memory.  */
1181   if (flag_unit_at_a_time
1182       && !dump_enabled_p (TDI_tree_all)
1183       && !(sorrycount || errorcount))
1184     {
1185       struct cgraph_node *node;
1186       bool error_found = false;
1187
1188       for (node = cgraph_nodes; node; node = node->next)
1189         if (node->analyzed
1190             && (node->global.inlined_to
1191                 || DECL_SAVED_TREE (node->decl)))
1192           {
1193             error_found = true;
1194             dump_cgraph_node (stderr, node);
1195           }
1196       if (error_found)
1197         internal_error ("Nodes with no released memory found.");
1198     }
1199 #endif
1200 }
1201
1202 /* Generate and emit a static constructor or destructor.  WHICH must be
1203    one of 'I' or 'D'.  BODY should be a STATEMENT_LIST containing
1204    GENERIC statements.  */
1205
1206 void
1207 cgraph_build_static_cdtor (char which, tree body, int priority)
1208 {
1209   static int counter = 0;
1210   char which_buf[16];
1211   tree decl, name, resdecl;
1212
1213   sprintf (which_buf, "%c_%d", which, counter++);
1214   name = get_file_function_name_long (which_buf);
1215
1216   decl = build_decl (FUNCTION_DECL, name,
1217                      build_function_type (void_type_node, void_list_node));
1218   current_function_decl = decl;
1219
1220   resdecl = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1221   DECL_ARTIFICIAL (resdecl) = 1;
1222   DECL_IGNORED_P (resdecl) = 1;
1223   DECL_RESULT (decl) = resdecl;
1224
1225   allocate_struct_function (decl);
1226
1227   TREE_STATIC (decl) = 1;
1228   TREE_USED (decl) = 1;
1229   DECL_ARTIFICIAL (decl) = 1;
1230   DECL_IGNORED_P (decl) = 1;
1231   DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
1232   DECL_SAVED_TREE (decl) = body;
1233   TREE_PUBLIC (decl) = ! targetm.have_ctors_dtors;
1234   DECL_UNINLINABLE (decl) = 1;
1235
1236   DECL_INITIAL (decl) = make_node (BLOCK);
1237   TREE_USED (DECL_INITIAL (decl)) = 1;
1238
1239   DECL_SOURCE_LOCATION (decl) = input_location;
1240   cfun->function_end_locus = input_location;
1241
1242   switch (which)
1243     {
1244     case 'I':
1245       DECL_STATIC_CONSTRUCTOR (decl) = 1;
1246       break;
1247     case 'D':
1248       DECL_STATIC_DESTRUCTOR (decl) = 1;
1249       break;
1250     default:
1251       gcc_unreachable ();
1252     }
1253
1254   gimplify_function_tree (decl);
1255
1256   /* ??? We will get called LATE in the compilation process.  */
1257   if (cgraph_global_info_ready)
1258     {
1259       tree_lowering_passes (decl);
1260       tree_rest_of_compilation (decl);
1261     }
1262   else
1263     cgraph_finalize_function (decl, 0);
1264
1265   if (targetm.have_ctors_dtors)
1266     {
1267       void (*fn) (rtx, int);
1268
1269       if (which == 'I')
1270         fn = targetm.asm_out.constructor;
1271       else
1272         fn = targetm.asm_out.destructor;
1273       fn (XEXP (DECL_RTL (decl), 0), priority);
1274     }
1275 }
1276
1277 void
1278 init_cgraph (void)
1279 {
1280   cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
1281 }