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