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