gcc/cgraphunit.c

   1 /* Callgraph based intraprocedural optimizations.
   2    Copyright (C) 2003, 2004 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 behaviour 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 it's 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      Inlining decision heuristics
 142         ??? Move this to separate file after tree-ssa merge.
 143
 144         We separate inlining decisions from the inliner itself and store it
 145         inside callgraph as so called inline plan.  Reffer to cgraph.c
 146         documentation about particular representation of inline plans in the
 147         callgraph
 148
 149         The implementation of particular heuristics is separated from
 150         the rest of code to make it easier to replace it with more complicated
 151         implementation in the future.  The rest of inlining code acts as a
 152         library aimed to modify the callgraph and verify that the parameters
 153         on code size growth fits.
 154
 155         To mark given call inline, use cgraph_mark_inline function, the
 156         verification is performed by cgraph_default_inline_p and
 157         cgraph_check_inline_limits.
 158
 159         The heuristics implements simple knapsack style algorithm ordering
 160         all functions by their "profitability" (estimated by code size growth)
 161         and inlining them in priority order.
 162
 163         cgraph_decide_inlining implements heuristics taking whole callgraph
 164         into account, while cgraph_decide_inlining_incrementally considers
 165         only one function at a time and is used in non-unit-at-a-time mode.  */
 166 #include "config.h"
 167 #include "system.h"
 168 #include "coretypes.h"
 169 #include "tm.h"
 170 #include "tree.h"
 171 #include "tree-inline.h"
 172 #include "langhooks.h"
 173 #include "hashtab.h"
 174 #include "toplev.h"
 175 #include "flags.h"
 176 #include "ggc.h"
 177 #include "debug.h"
 178 #include "target.h"
 179 #include "cgraph.h"
 180 #include "diagnostic.h"
 181 #include "timevar.h"
 182 #include "params.h"
 183 #include "fibheap.h"
 184 #include "c-common.h"
 185 #include "intl.h"
 186
 187 #define INSNS_PER_CALL 10
 188
 189 static void cgraph_expand_all_functions (void);
 190 static void cgraph_mark_functions_to_output (void);
 191 static void cgraph_expand_function (struct cgraph_node *);
 192 static tree record_call_1 (tree *, int *, void *);
 193 static void cgraph_mark_local_functions (void);
 194 static bool cgraph_default_inline_p (struct cgraph_node *n);
 195 static void cgraph_analyze_function (struct cgraph_node *node);
 196 static void cgraph_decide_inlining_incrementally (struct cgraph_node *);
 197
 198 /* Statistics we collect about inlining algorithm.  */
 199 static int ncalls_inlined;
 200 static int nfunctions_inlined;
 201 static int initial_insns;
 202 static int overall_insns;
 203
 204 /* Records tree nodes seen in cgraph_create_edges.  Simply using
 205    walk_tree_without_duplicates doesn't guarantee each node is visited
 206    once because it gets a new htab upon each recursive call from
 207    record_calls_1.  */
 208 static htab_t visited_nodes;
 209
 210 /* Determine if function DECL is needed.  That is, visible to something
 211    either outside this translation unit, something magic in the system
 212    configury, or (if not doing unit-at-a-time) to something we havn't
 213    seen yet.  */
 214
 215 static bool
 216 decide_is_function_needed (struct cgraph_node *node, tree decl)
 217 {
 218   /* If we decided it was needed before, but at the time we didn't have
 219      the body of the function available, then it's still needed.  We have
 220      to go back and re-check its dependencies now.  */
 221   if (node->needed)
 222     return true;
 223
 224   /* Externally visible functions must be output.  The exception is
 225      COMDAT functions that must be output only when they are needed.  */
 226   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 227     return true;
 228
 229   /* Constructors and destructors are reachable from the runtime by
 230      some mechanism.  */
 231   if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
 232     return true;
 233
 234   /* If the user told us it is used, then it must be so.  */
 235   if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
 236     return true;
 237
 238   /* ??? If the assembler name is set by hand, it is possible to assemble
 239      the name later after finalizing the function and the fact is noticed
 240      in assemble_name then.  This is arguably a bug.  */
 241   if (DECL_ASSEMBLER_NAME_SET_P (decl)
 242       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 243     return true;
 244
 245   if (flag_unit_at_a_time)
 246     return false;
 247
 248   /* If not doing unit at a time, then we'll only defer this function
 249      if its marked for inlining.  Otherwise we want to emit it now.  */
 250
 251   /* "extern inline" functions are never output locally.  */
 252   if (DECL_EXTERNAL (decl))
 253     return false;
 254   /* We want to emit COMDAT functions only when absolutely necessary.  */
 255   if (DECL_COMDAT (decl))
 256     return false;
 257   if (!DECL_INLINE (decl)
 258       || (!node->local.disregard_inline_limits
 259           /* When declared inline, defer even the uninlinable functions.
 260              This allows them to be eliminated when unused.  */
 261           && !DECL_DECLARED_INLINE_P (decl)
 262           && (!node->local.inlinable || !cgraph_default_inline_p (node))))
 263     return true;
 264
 265   return false;
 266 }
 267
 268 /* When not doing unit-at-a-time, output all functions enqueued.
 269    Return true when such a functions were found.  */
 270
 271 bool
 272 cgraph_assemble_pending_functions (void)
 273 {
 274   bool output = false;
 275
 276   if (flag_unit_at_a_time)
 277     return false;
 278
 279   while (cgraph_nodes_queue)
 280     {
 281       struct cgraph_node *n = cgraph_nodes_queue;
 282
 283       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
 284       n->next_needed = NULL;
 285       if (!n->origin && !n->global.inlined_to && !DECL_EXTERNAL (n->decl))
 286         {
 287           cgraph_expand_function (n);
 288           output = true;
 289         }
 290     }
 291
 292   return output;
 293 }
 294
 295 /* DECL has been parsed.  Take it, queue it, compile it at the whim of the
 296    logic in effect.  If NESTED is true, then our caller cannot stand to have
 297    the garbage collector run at the moment.  We would need to either create
 298    a new GC context, or just not compile right now.  */
 299
 300 void
 301 cgraph_finalize_function (tree decl, bool nested)
 302 {
 303   struct cgraph_node *node = cgraph_node (decl);
 304
 305   if (node->local.finalized)
 306     {
 307       /* As an GCC extension we allow redefinition of the function.  The
 308          semantics when both copies of bodies differ is not well defined.
 309          We replace the old body with new body so in unit at a time mode
 310          we always use new body, while in normal mode we may end up with
 311          old body inlined into some functions and new body expanded and
 312          inlined in others.
 313
 314          ??? It may make more sense to use one body for inlining and other
 315          body for expanding the function but this is difficult to do.  */
 316
 317       /* If node->output is set, then this is a unit-at-a-time compilation
 318          and we have already begun whole-unit analysis.  This is *not*
 319          testing for whether we've already emitted the function.  That
 320          case can be sort-of legitimately seen with real function
 321          redefinition errors.  I would argue that the front end should
 322          never present us with such a case, but don't enforce that for now.  */
 323       if (node->output)
 324         abort ();
 325
 326       /* Reset our datastructures so we can analyze the function again.  */
 327       memset (&node->local, 0, sizeof (node->local));
 328       memset (&node->global, 0, sizeof (node->global));
 329       memset (&node->rtl, 0, sizeof (node->rtl));
 330       node->analyzed = false;
 331       node->local.redefined_extern_inline = true;
 332       while (node->callees)
 333         cgraph_remove_edge (node->callees);
 334
 335       /* We may need to re-queue the node for assembling in case
 336          we already proceeded it and ignored as not needed.  */
 337       if (node->reachable && !flag_unit_at_a_time)
 338         {
 339           struct cgraph_node *n;
 340
 341           for (n = cgraph_nodes_queue; n; n = n->next_needed)
 342             if (n == node)
 343               break;
 344           if (!n)
 345             node->reachable = 0;
 346         }
 347     }
 348
 349   notice_global_symbol (decl);
 350   node->decl = decl;
 351   node->local.finalized = true;
 352
 353   /* If not unit at a time, then we need to create the call graph
 354      now, so that called functions can be queued and emitted now.  */
 355   if (!flag_unit_at_a_time)
 356     {
 357       cgraph_analyze_function (node);
 358       cgraph_decide_inlining_incrementally (node);
 359     }
 360
 361   if (decide_is_function_needed (node, decl))
 362     cgraph_mark_needed_node (node);
 363
 364   /* If not unit at a time, go ahead and emit everything we've found
 365      to be reachable at this time.  */
 366   if (!nested)
 367     {
 368       if (!cgraph_assemble_pending_functions ())
 369         ggc_collect ();
 370     }
 371
 372   /* If we've not yet emitted decl, tell the debug info about it.  */
 373   if (!TREE_ASM_WRITTEN (decl))
 374     (*debug_hooks->deferred_inline_function) (decl);
 375
 376   /* We will never really output the function body, clear the STRUCT_FUNCTION array
 377      early then.  */
 378   if (DECL_EXTERNAL (decl))
 379     DECL_STRUCT_FUNCTION (decl) = NULL;
 380 }
 381
 382 /* Walk tree and record all calls.  Called via walk_tree.  */
 383 static tree
 384 record_call_1 (tree *tp, int *walk_subtrees, void *data)
 385 {
 386   tree t = *tp;
 387
 388   switch (TREE_CODE (t))
 389     {
 390     case VAR_DECL:
 391       /* ??? Really, we should mark this decl as *potentially* referenced
 392          by this function and re-examine whether the decl is actually used
 393          after rtl has been generated.  */
 394       if (TREE_STATIC (t))
 395         cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));
 396       break;
 397
 398     case ADDR_EXPR:
 399       if (flag_unit_at_a_time)
 400         {
 401           /* Record dereferences to the functions.  This makes the
 402              functions reachable unconditionally.  */
 403           tree decl = TREE_OPERAND (*tp, 0);
 404           if (TREE_CODE (decl) == FUNCTION_DECL)
 405             cgraph_mark_needed_node (cgraph_node (decl));
 406         }
 407       break;
 408
 409     case CALL_EXPR:
 410       {
 411         tree decl = get_callee_fndecl (*tp);
 412         if (decl && TREE_CODE (decl) == FUNCTION_DECL)
 413           {
 414             cgraph_create_edge (data, cgraph_node (decl), *tp);
 415
 416             /* When we see a function call, we don't want to look at the
 417                function reference in the ADDR_EXPR that is hanging from
 418                the CALL_EXPR we're examining here, because we would
 419                conclude incorrectly that the function's address could be
 420                taken by something that is not a function call.  So only
 421                walk the function parameter list, skip the other subtrees.  */
 422
 423             walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data,
 424                        visited_nodes);
 425             *walk_subtrees = 0;
 426           }
 427         break;
 428       }
 429
 430     default:
 431       /* Save some cycles by not walking types and declaration as we
 432          won't find anything useful there anyway.  */
 433       if (DECL_P (*tp) || TYPE_P (*tp))
 434         {
 435           *walk_subtrees = 0;
 436           break;
 437         }
 438
 439       if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
 440         return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees, data);
 441       break;
 442     }
 443
 444   return NULL;
 445 }
 446
 447 /* Create cgraph edges for function calls inside BODY from NODE.  */
 448
 449 void
 450 cgraph_create_edges (struct cgraph_node *node, tree body)
 451 {
 452   /* The nodes we're interested in are never shared, so walk
 453      the tree ignoring duplicates.  */
 454   visited_nodes = htab_create (37, htab_hash_pointer,
 455                                     htab_eq_pointer, NULL);
 456   walk_tree (&body, record_call_1, node, visited_nodes);
 457   htab_delete (visited_nodes);
 458   visited_nodes = NULL;
 459 }
 460
 461 static bool error_found;
 462
 463 /* Callbrack of verify_cgraph_node.  Check that all call_exprs have cgraph nodes.  */
 464 static tree
 465 verify_cgraph_node_1 (tree *tp, int *walk_subtrees, void *data)
 466 {
 467   tree t = *tp;
 468   tree decl;
 469
 470   if (TREE_CODE (t) == CALL_EXPR && (decl = get_callee_fndecl (t)))
 471     {
 472       struct cgraph_edge *e = cgraph_edge (data, t);
 473       if (e)
 474         {
 475           if (e->aux)
 476             {
 477               error ("Shared call_expr:");
 478               debug_tree (t);
 479               error_found = true;
 480             }
 481           if (e->callee->decl != cgraph_node (decl)->decl)
 482             {
 483               error ("Edge points to wrong declaration:");
 484               debug_tree (e->callee->decl);
 485               fprintf (stderr," Instead of:");
 486               debug_tree (decl);
 487             }
 488           e->aux = (void *)1;
 489         }
 490       else
 491         {
 492           error ("Missing callgraph edge for call expr:");
 493           debug_tree (t);
 494           error_found = true;
 495         }
 496     }
 497   /* Save some cycles by not walking types and declaration as we
 498      won't find anything useful there anyway.  */
 499   if (DECL_P (*tp) || TYPE_P (*tp))
 500     {
 501       *walk_subtrees = 0;
 502     }
 503   return NULL_TREE;
 504 }
 505
 506 /* Verify cgraph nodes of given cgraph node.  */
 507 void
 508 verify_cgraph_node (struct cgraph_node *node)
 509 {
 510   struct cgraph_edge *e;
 511   struct cgraph_node *main_clone;
 512
 513   timevar_push (TV_CGRAPH_VERIFY);
 514   error_found = false;
 515   for (e = node->callees; e; e = e->next_callee)
 516     if (e->aux)
 517       {
 518         error ("Aux field set for edge %s->%s",
 519                cgraph_node_name (e->caller), cgraph_node_name (e->callee));
 520         error_found = true;
 521       }
 522   for (e = node->callers; e; e = e->next_caller)
 523     {
 524       if (!e->inline_failed)
 525         {
 526           if (node->global.inlined_to
 527               != (e->caller->global.inlined_to
 528                   ? e->caller->global.inlined_to : e->caller))
 529             {
 530               error ("Inlined_to pointer is wrong");
 531               error_found = true;
 532             }
 533           if (node->callers->next_caller)
 534             {
 535               error ("Multiple inline callers");
 536               error_found = true;
 537             }
 538         }
 539       else
 540         if (node->global.inlined_to)
 541           {
 542             error ("Inlined_to pointer set for noninline callers");
 543             error_found = true;
 544           }
 545     }
 546   if (!node->callers && node->global.inlined_to)
 547     {
 548       error ("Inlined_to pointer is set but no predecesors found");
 549       error_found = true;
 550     }
 551   if (node->global.inlined_to == node)
 552     {
 553       error ("Inlined_to pointer reffers to itself");
 554       error_found = true;
 555     }
 556
 557   for (main_clone = cgraph_node (node->decl); main_clone;
 558        main_clone = main_clone->next_clone)
 559     if (main_clone == node)
 560       break;
 561   if (!node)
 562     {
 563       error ("Node not found in DECL_ASSEMBLER_NAME hash");
 564       error_found = true;
 565     }
 566
 567   if (node->analyzed
 568       && DECL_SAVED_TREE (node->decl) && !TREE_ASM_WRITTEN (node->decl)
 569       && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to))
 570     {
 571       walk_tree_without_duplicates (&DECL_SAVED_TREE (node->decl),
 572                                     verify_cgraph_node_1, node);
 573       for (e = node->callees; e; e = e->next_callee)
 574         {
 575           if (!e->aux)
 576             {
 577               error ("Edge %s->%s has no corresponding call_expr",
 578                      cgraph_node_name (e->caller),
 579                      cgraph_node_name (e->callee));
 580               error_found = true;
 581             }
 582           e->aux = 0;
 583         }
 584     }
 585   if (error_found)
 586     {
 587       dump_cgraph_node (stderr, node);
 588       internal_error ("verify_cgraph_node failed.");
 589     }
 590   timevar_pop (TV_CGRAPH_VERIFY);
 591 }
 592
 593 /* Verify whole cgraph structure.  */
 594 void
 595 verify_cgraph (void)
 596 {
 597   struct cgraph_node *node;
 598
 599   for (node = cgraph_nodes; node; node = node->next)
 600     verify_cgraph_node (node);
 601 }
 602
 603 /* Analyze the function scheduled to be output.  */
 604 static void
 605 cgraph_analyze_function (struct cgraph_node *node)
 606 {
 607   tree decl = node->decl;
 608   struct cgraph_edge *e;
 609
 610   current_function_decl = decl;
 611
 612   /* First kill forward declaration so reverse inlining works properly.  */
 613   cgraph_create_edges (node, DECL_SAVED_TREE (decl));
 614
 615   node->local.inlinable = tree_inlinable_function_p (decl);
 616   if (!node->local.self_insns)
 617     node->local.self_insns
 618       = lang_hooks.tree_inlining.estimate_num_insns (decl);
 619   if (node->local.inlinable)
 620     node->local.disregard_inline_limits
 621       = lang_hooks.tree_inlining.disregard_inline_limits (decl);
 622   for (e = node->callers; e; e = e->next_caller)
 623     {
 624       if (node->local.redefined_extern_inline)
 625         e->inline_failed = N_("redefined extern inline functions are not "
 626                            "considered for inlining");
 627       else if (!node->local.inlinable)
 628         e->inline_failed = N_("function not inlinable");
 629       else
 630         e->inline_failed = N_("function not considered for inlining");
 631     }
 632   if (flag_really_no_inline && !node->local.disregard_inline_limits)
 633     node->local.inlinable = 0;
 634   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
 635   node->global.insns = node->local.self_insns;
 636
 637   node->analyzed = true;
 638   current_function_decl = NULL;
 639 }
 640
 641 /* Analyze the whole compilation unit once it is parsed completely.  */
 642
 643 void
 644 cgraph_finalize_compilation_unit (void)
 645 {
 646   struct cgraph_node *node;
 647
 648   if (!flag_unit_at_a_time)
 649     {
 650       cgraph_assemble_pending_functions ();
 651       return;
 652     }
 653
 654   cgraph_varpool_assemble_pending_decls ();
 655   if (!quiet_flag)
 656     fprintf (stderr, "\nAnalyzing compilation unit\n");
 657
 658   timevar_push (TV_CGRAPH);
 659   if (cgraph_dump_file)
 660     {
 661       fprintf (cgraph_dump_file, "Initial entry points:");
 662       for (node = cgraph_nodes; node; node = node->next)
 663         if (node->needed && DECL_SAVED_TREE (node->decl))
 664           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 665       fprintf (cgraph_dump_file, "\n");
 666     }
 667
 668   /* Propagate reachability flag and lower representation of all reachable
 669      functions.  In the future, lowering will introduce new functions and
 670      new entry points on the way (by template instantiation and virtual
 671      method table generation for instance).  */
 672   while (cgraph_nodes_queue)
 673     {
 674       struct cgraph_edge *edge;
 675       tree decl = cgraph_nodes_queue->decl;
 676
 677       node = cgraph_nodes_queue;
 678       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
 679       node->next_needed = NULL;
 680
 681       /* ??? It is possible to create extern inline function and later using
 682          weak alas attribute to kill its body. See
 683          gcc.c-torture/compile/20011119-1.c  */
 684       if (!DECL_SAVED_TREE (decl))
 685         continue;
 686
 687       if (node->analyzed || !node->reachable || !DECL_SAVED_TREE (decl))
 688         abort ();
 689
 690       cgraph_analyze_function (node);
 691
 692       for (edge = node->callees; edge; edge = edge->next_callee)
 693         if (!edge->callee->reachable)
 694           cgraph_mark_reachable_node (edge->callee);
 695
 696       cgraph_varpool_assemble_pending_decls ();
 697     }
 698
 699   /* Collect entry points to the unit.  */
 700
 701   if (cgraph_dump_file)
 702     {
 703       fprintf (cgraph_dump_file, "Unit entry points:");
 704       for (node = cgraph_nodes; node; node = node->next)
 705         if (node->needed && DECL_SAVED_TREE (node->decl))
 706           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 707       fprintf (cgraph_dump_file, "\n\nInitial ");
 708       dump_cgraph (cgraph_dump_file);
 709     }
 710
 711   if (cgraph_dump_file)
 712     fprintf (cgraph_dump_file, "\nReclaiming functions:");
 713
 714   for (node = cgraph_nodes; node; node = node->next)
 715     {
 716       tree decl = node->decl;
 717
 718       if (!node->reachable && DECL_SAVED_TREE (decl))
 719         {
 720           if (cgraph_dump_file)
 721             fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 722           cgraph_remove_node (node);
 723         }
 724       else
 725         node->next_needed = NULL;
 726     }
 727   if (cgraph_dump_file)
 728     {
 729       fprintf (cgraph_dump_file, "\n\nReclaimed ");
 730       dump_cgraph (cgraph_dump_file);
 731     }
 732   ggc_collect ();
 733   timevar_pop (TV_CGRAPH);
 734 }
 735
 736 /* Figure out what functions we want to assemble.  */
 737
 738 static void
 739 cgraph_mark_functions_to_output (void)
 740 {
 741   struct cgraph_node *node;
 742
 743   for (node = cgraph_nodes; node; node = node->next)
 744     {
 745       tree decl = node->decl;
 746       struct cgraph_edge *e;
 747
 748       if (node->output)
 749         abort ();
 750
 751       for (e = node->callers; e; e = e->next_caller)
 752         if (e->inline_failed)
 753           break;
 754
 755       /* We need to output all local functions that are used and not
 756          always inlined, as well as those that are reachable from
 757          outside the current compilation unit.  */
 758       if (DECL_SAVED_TREE (decl)
 759           && !node->global.inlined_to
 760           && (node->needed
 761               || (e && node->reachable))
 762           && !TREE_ASM_WRITTEN (decl) && !node->origin
 763           && !DECL_EXTERNAL (decl))
 764         node->output = 1;
 765       /* We should've reclaimed all functions that are not needed.  */
 766       else if (!node->global.inlined_to && DECL_SAVED_TREE (decl)
 767                && !node->origin && !DECL_EXTERNAL (decl))
 768         {
 769           dump_cgraph_node (stderr, node);
 770           abort ();
 771         }
 772     }
 773 }
 774
 775 /* Expand function specified by NODE.  */
 776
 777 static void
 778 cgraph_expand_function (struct cgraph_node *node)
 779 {
 780   tree decl = node->decl;
 781
 782   /* We ought to not compile any inline clones.  */
 783   if (node->global.inlined_to)
 784     abort ();
 785
 786   if (flag_unit_at_a_time)
 787     announce_function (decl);
 788
 789   /* Generate RTL for the body of DECL.  Nested functions are expanded
 790      via lang_expand_decl_stmt.  */
 791   lang_hooks.callgraph.expand_function (decl);
 792   if (DECL_DEFER_OUTPUT (decl))
 793     abort ();
 794
 795   /* Make sure that BE didn't gave up on compiling.  */
 796   if (!TREE_ASM_WRITTEN (node->decl)
 797       && !(sorrycount || errorcount))
 798     abort ();
 799
 800   current_function_decl = NULL;
 801 }
 802
 803 /* Fill array order with all nodes with output flag set in the reverse
 804    topological order.  */
 805
 806 static int
 807 cgraph_postorder (struct cgraph_node **order)
 808 {
 809   struct cgraph_node *node, *node2;
 810   int stack_size = 0;
 811   int order_pos = 0;
 812   struct cgraph_edge *edge, last;
 813
 814   struct cgraph_node **stack =
 815     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
 816
 817   /* We have to deal with cycles nicely, so use a depth first traversal
 818      output algorithm.  Ignore the fact that some functions won't need
 819      to be output and put them into order as well, so we get dependencies
 820      right throughout inline functions.  */
 821   for (node = cgraph_nodes; node; node = node->next)
 822     node->aux = NULL;
 823   for (node = cgraph_nodes; node; node = node->next)
 824     if (!node->aux)
 825       {
 826         node2 = node;
 827         if (!node->callers)
 828           node->aux = &last;
 829         else
 830           node->aux = node->callers;
 831         while (node2)
 832           {
 833             while (node2->aux != &last)
 834               {
 835                 edge = node2->aux;
 836                 if (edge->next_caller)
 837                   node2->aux = edge->next_caller;
 838                 else
 839                   node2->aux = &last;
 840                 if (!edge->caller->aux)
 841                   {
 842                     if (!edge->caller->callers)
 843                       edge->caller->aux = &last;
 844                     else
 845                       edge->caller->aux = edge->caller->callers;
 846                     stack[stack_size++] = node2;
 847                     node2 = edge->caller;
 848                     break;
 849                   }
 850               }
 851             if (node2->aux == &last)
 852               {
 853                 order[order_pos++] = node2;
 854                 if (stack_size)
 855                   node2 = stack[--stack_size];
 856                 else
 857                   node2 = NULL;
 858               }
 859           }
 860       }
 861   free (stack);
 862   return order_pos;
 863 }
 864
 865 /* Perform reachability analysis and reclaim all unreachable nodes.
 866    This function also remove unneeded bodies of extern inline functions
 867    and thus needs to be done only after inlining decisions has been made.  */
 868 static bool
 869 cgraph_remove_unreachable_nodes (void)
 870 {
 871   struct cgraph_node *first = (void *) 1;
 872   struct cgraph_node *node;
 873   bool changed = false;
 874   int insns = 0;
 875
 876 #ifdef ENABLE_CHECKING
 877   verify_cgraph ();
 878 #endif
 879   if (cgraph_dump_file)
 880     fprintf (cgraph_dump_file, "\nReclaiming functions:");
 881 #ifdef ENABLE_CHECKING
 882   for (node = cgraph_nodes; node; node = node->next)
 883     if (node->aux)
 884       abort ();
 885 #endif
 886   for (node = cgraph_nodes; node; node = node->next)
 887     if (node->needed && (!DECL_EXTERNAL (node->decl) || !node->analyzed))
 888       {
 889         node->aux = first;
 890         first = node;
 891       }
 892     else if (node->aux)
 893       abort ();
 894
 895   /* Perform reachability analysis.  As a special case do not consider
 896      extern inline functions not inlined as live because we won't output
 897      them at all.  */
 898   while (first != (void *) 1)
 899     {
 900       struct cgraph_edge *e;
 901       node = first;
 902       first = first->aux;
 903
 904       for (e = node->callees; e; e = e->next_callee)
 905         if (!e->callee->aux
 906             && node->analyzed
 907             && (!e->inline_failed || !e->callee->analyzed
 908                 || !DECL_EXTERNAL (e->callee->decl)))
 909           {
 910             e->callee->aux = first;
 911             first = e->callee;
 912           }
 913     }
 914
 915   /* Remove unreachable nodes.  Extern inline functions need special care;
 916      Unreachable extern inline functions shall be removed.
 917      Reachable extern inline functions we never inlined shall get their bodies
 918      eliminated
 919      Reachable extern inline functions we sometimes inlined will be turned into
 920      unanalyzed nodes so they look like for true extern functions to the rest
 921      of code.  Body of such functions is relased via remove_node once the
 922      inline clones are eliminated.  */
 923   for (node = cgraph_nodes; node; node = node->next)
 924     {
 925       if (!node->aux)
 926         {
 927           int local_insns;
 928           tree decl = node->decl;
 929
 930           if (DECL_STRUCT_FUNCTION (decl))
 931             local_insns = node->local.self_insns;
 932           else
 933             local_insns = 0;
 934           if (cgraph_dump_file)
 935             fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 936           if (!node->analyzed || !DECL_EXTERNAL (node->decl))
 937             cgraph_remove_node (node);
 938           else
 939             {
 940               struct cgraph_edge *e;
 941
 942               for (e = node->callers; e; e = e->next_caller)
 943                 if (e->caller->aux)
 944                   break;
 945               if (e || node->needed)
 946                 {
 947                   struct cgraph_node *clone;
 948
 949                   for (clone = node->next_clone; clone;
 950                        clone = clone->next_clone)
 951                     if (clone->aux)
 952                       break;
 953                   if (!clone)
 954                     {
 955                       DECL_SAVED_TREE (node->decl) = NULL;
 956                       DECL_STRUCT_FUNCTION (node->decl) = NULL;
 957                       DECL_ARGUMENTS (node->decl) = NULL;
 958                       DECL_INITIAL (node->decl) = error_mark_node;
 959                     }
 960                   while (node->callees)
 961                     cgraph_remove_edge (node->callees);
 962                   node->analyzed = false;
 963                 }
 964               else
 965                 cgraph_remove_node (node);
 966             }
 967           if (!DECL_SAVED_TREE (decl))
 968             insns += local_insns;
 969           changed = true;
 970         }
 971     }
 972   for (node = cgraph_nodes; node; node = node->next)
 973     node->aux = NULL;
 974   if (cgraph_dump_file)
 975     fprintf (cgraph_dump_file, "\nReclaimed %i insns", insns);
 976   return changed;
 977 }
 978
 979 /* Estimate size of the function after inlining WHAT into TO.  */
 980
 981 static int
 982 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
 983                                      struct cgraph_node *what)
 984 {
 985   return (what->global.insns - INSNS_PER_CALL) * times + to->global.insns;
 986 }
 987
 988 /* Estimate the growth caused by inlining NODE into all callees.  */
 989
 990 static int
 991 cgraph_estimate_growth (struct cgraph_node *node)
 992 {
 993   int growth = 0;
 994   struct cgraph_edge *e;
 995
 996   for (e = node->callers; e; e = e->next_caller)
 997     if (e->inline_failed)
 998       growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
 999                  - e->caller->global.insns);
1000
1001   /* ??? Wrong for self recursive functions or cases where we decide to not
1002      inline for different reasons, but it is not big deal as in that case
1003      we will keep the body around, but we will also avoid some inlining.  */
1004   if (!node->needed && !node->origin && !DECL_EXTERNAL (node->decl))
1005     growth -= node->global.insns;
1006
1007   return growth;
1008 }
1009
1010 /* E is expected to be an edge being inlined.  Clone destination node of
1011    the edge and redirect it to the new clone.
1012    DUPLICATE is used for bookeeping on whether we are actually creating new
1013    clones or re-using node originally representing out-of-line function call.
1014    */
1015 void
1016 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate)
1017 {
1018   struct cgraph_node *n;
1019
1020   /* We may elliminate the need for out-of-line copy to be output.  In that
1021      case just go ahead and re-use it.  */
1022   if (!e->callee->callers->next_caller
1023       && (!e->callee->needed || DECL_EXTERNAL (e->callee->decl))
1024       && !e->callee->origin
1025       && duplicate
1026       && flag_unit_at_a_time)
1027     {
1028       if (e->callee->global.inlined_to)
1029         abort ();
1030       if (!DECL_EXTERNAL (e->callee->decl))
1031         overall_insns -= e->callee->global.insns, nfunctions_inlined++;
1032       duplicate = 0;
1033     }
1034    else if (duplicate)
1035     {
1036       n = cgraph_clone_node (e->callee);
1037       cgraph_redirect_edge_callee (e, n);
1038     }
1039
1040   if (e->caller->global.inlined_to)
1041     e->callee->global.inlined_to = e->caller->global.inlined_to;
1042   else
1043     e->callee->global.inlined_to = e->caller;
1044
1045   /* Recursivly clone all bodies.  */
1046   for (e = e->callee->callees; e; e = e->next_callee)
1047     if (!e->inline_failed)
1048       cgraph_clone_inlined_nodes (e, duplicate);
1049 }
1050
1051 /* Mark edge E as inlined and update callgraph accordingly.  */
1052
1053 void
1054 cgraph_mark_inline_edge (struct cgraph_edge *e)
1055 {
1056   int old_insns = 0, new_insns = 0;
1057   struct cgraph_node *to = NULL, *what;
1058
1059   if (!e->inline_failed)
1060     abort ();
1061   e->inline_failed = NULL;
1062
1063   if (!e->callee->global.inlined && flag_unit_at_a_time)
1064     {
1065       void **slot;
1066       if (!cgraph_inline_hash)
1067         cgraph_inline_hash = htab_create_ggc (42, htab_hash_pointer,
1068                                               htab_eq_pointer, NULL);
1069       slot = htab_find_slot (cgraph_inline_hash,
1070                              DECL_ASSEMBLER_NAME (e->callee->decl), INSERT);
1071       *slot = DECL_ASSEMBLER_NAME (e->callee->decl);
1072     }
1073   e->callee->global.inlined = true;
1074
1075   cgraph_clone_inlined_nodes (e, true);
1076
1077   what = e->callee;
1078
1079   /* Now update size of caller and all functions caller is inlined into. */
1080   for (;e && !e->inline_failed; e = e->caller->callers)
1081     {
1082       old_insns = e->caller->global.insns;
1083       new_insns = cgraph_estimate_size_after_inlining (1, e->caller,
1084                                                        what);
1085       if (new_insns < 0)
1086         abort ();
1087       to = e->caller;
1088       to->global.insns = new_insns;
1089     }
1090   if (what->global.inlined_to != to)
1091     abort ();
1092   overall_insns += new_insns - old_insns;
1093   ncalls_inlined++;
1094 }
1095
1096 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
1097    Return following unredirected edge in the list of callers
1098    of EDGE->CALLEE  */
1099
1100 static struct cgraph_edge *
1101 cgraph_mark_inline (struct cgraph_edge *edge)
1102 {
1103   struct cgraph_node *to = edge->caller;
1104   struct cgraph_node *what = edge->callee;
1105   struct cgraph_edge *e, *next;
1106   int times = 0;
1107
1108   /* Look for all calls, mark them inline and clone recursivly
1109      all inlined functions.  */
1110   for (e = what->callers; e; e = next)
1111     {
1112       next = e->next_caller;
1113       if (e->caller == to && e->inline_failed)
1114         {
1115           cgraph_mark_inline_edge (e);
1116           if (e == edge)
1117             edge = next;
1118           times ++;
1119         }
1120     }
1121   if (!times)
1122     abort ();
1123   return edge;
1124 }
1125
1126 /* Return false when inlining WHAT into TO is not good idea
1127    as it would cause too large growth of function bodies.  */
1128
1129 static bool
1130 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
1131                             const char **reason)
1132 {
1133   int times = 0;
1134   struct cgraph_edge *e;
1135   int newsize;
1136   int limit;
1137
1138   if (to->global.inlined_to)
1139     to = to->global.inlined_to;
1140
1141   for (e = to->callees; e; e = e->next_callee)
1142     if (e->callee == what)
1143       times++;
1144
1145   /* When inlining large function body called once into small function,
1146      take the inlined function as base for limiting the growth.  */
1147   if (to->local.self_insns > what->local.self_insns)
1148     limit = to->local.self_insns;
1149   else
1150     limit = what->local.self_insns;
1151
1152   limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
1153
1154   newsize = cgraph_estimate_size_after_inlining (times, to, what);
1155   if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
1156       && newsize > limit)
1157     {
1158       if (reason)
1159         *reason = N_("--param large-function-growth limit reached");
1160       return false;
1161     }
1162   return true;
1163 }
1164
1165 /* Return true when function N is small enough to be inlined.  */
1166
1167 static bool
1168 cgraph_default_inline_p (struct cgraph_node *n)
1169 {
1170   if (!DECL_INLINE (n->decl) || !DECL_SAVED_TREE (n->decl))
1171     return false;
1172   if (DECL_DECLARED_INLINE_P (n->decl))
1173     return n->global.insns < MAX_INLINE_INSNS_SINGLE;
1174   else
1175     return n->global.insns < MAX_INLINE_INSNS_AUTO;
1176 }
1177
1178 /* Return true when inlining WHAT would create recursive inlining.
1179    We call recursive inlining all cases where same function appears more than
1180    once in the single recusion nest path in the inline graph.  */
1181
1182 static bool
1183 cgraph_recursive_inlining_p (struct cgraph_node *to,
1184                              struct cgraph_node *what,
1185                              const char **reason)
1186 {
1187   struct cgraph_node *node;
1188
1189   /* Walk TO and all functions TO is inlined in.  */
1190   while (1)
1191     {
1192       /* We create recursive inlining either by inlining WHAT into something
1193          already inlined in possibly different clone of WHAT.  */
1194       if (what->decl == to->decl)
1195         goto recursive;
1196       /* Or by inlining WHAT into something that is already inlined in WHAT.  */
1197       for (node = cgraph_node (to->decl); node; node = node->next_clone)
1198         if (node->global.inlined_to == what)
1199           goto recursive;
1200       if (!to->callers || to->callers->inline_failed)
1201         return false;
1202       to = to->callers->caller;
1203     }
1204 recursive:
1205   if (reason)
1206     *reason = (what->local.disregard_inline_limits
1207                ? N_("recursive inlining") : "");
1208   return true;
1209 }
1210
1211 /* Recompute heap nodes for each of callees.  */
1212 static void
1213 update_callee_keys (fibheap_t heap, struct fibnode **heap_node,
1214                     struct cgraph_node *node)
1215 {
1216   struct cgraph_edge *e;
1217
1218   for (e = node->callees; e; e = e->next_callee)
1219     if (e->inline_failed && heap_node[e->callee->uid])
1220       fibheap_replace_key (heap, heap_node[e->callee->uid],
1221                            cgraph_estimate_growth (e->callee));
1222     else if (!e->inline_failed)
1223       update_callee_keys (heap, heap_node, e->callee);
1224 }
1225
1226 /* Set inline_failed for all callers of given function to REASON.  */
1227
1228 static void
1229 cgraph_set_inline_failed (struct cgraph_node *node, const char *reason)
1230 {
1231   struct cgraph_edge *e;
1232
1233   if (cgraph_dump_file)
1234     fprintf (cgraph_dump_file, "Inlining failed: %s\n", reason);
1235   for (e = node->callers; e; e = e->next_caller)
1236     if (e->inline_failed)
1237       e->inline_failed = reason;
1238 }
1239
1240 /* We use greedy algorithm for inlining of small functions:
1241    All inline candidates are put into prioritized heap based on estimated
1242    growth of the overall number of instructions and then update the estimates.
1243
1244    INLINED and INLINED_CALEES are just pointers to arrays large enough
1245    to be passed to cgraph_inlined_into and cgraph_inlined_callees.  */
1246
1247 static void
1248 cgraph_decide_inlining_of_small_functions (void)
1249 {
1250   struct cgraph_node *node;
1251   fibheap_t heap = fibheap_new ();
1252   struct fibnode **heap_node =
1253     xcalloc (cgraph_max_uid, sizeof (struct fibnode *));
1254   int max_insns = ((HOST_WIDEST_INT) initial_insns
1255                    * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
1256
1257   /* Put all inline candidates into the heap.  */
1258
1259   for (node = cgraph_nodes; node; node = node->next)
1260     {
1261       if (!node->local.inlinable || !node->callers
1262           || node->local.disregard_inline_limits)
1263         continue;
1264
1265       if (!cgraph_default_inline_p (node))
1266         {
1267           cgraph_set_inline_failed (node,
1268             N_("--param max-inline-insns-single limit reached"));
1269           continue;
1270         }
1271       heap_node[node->uid] =
1272         fibheap_insert (heap, cgraph_estimate_growth (node), node);
1273     }
1274
1275   if (cgraph_dump_file)
1276     fprintf (cgraph_dump_file, "\nDeciding on smaller functions:\n");
1277   while (overall_insns <= max_insns && (node = fibheap_extract_min (heap)))
1278     {
1279       struct cgraph_edge *e, *next;
1280       int old_insns = overall_insns;
1281
1282       heap_node[node->uid] = NULL;
1283       if (cgraph_dump_file)
1284         fprintf (cgraph_dump_file,
1285                  "\nConsidering %s with %i insns\n"
1286                  " Estimated growth is %+i insns.\n",
1287                  cgraph_node_name (node), node->global.insns,
1288                  cgraph_estimate_growth (node));
1289       if (!cgraph_default_inline_p (node))
1290         {
1291           cgraph_set_inline_failed (node,
1292             N_("--param max-inline-insns-single limit reached after inlining into the callee"));
1293           continue;
1294         }
1295       for (e = node->callers; e; e = next)
1296         {
1297           next = e->next_caller;
1298           if (e->inline_failed)
1299             {
1300               struct cgraph_node *where;
1301
1302               if (cgraph_recursive_inlining_p (e->caller, e->callee,
1303                                                &e->inline_failed)
1304                   || !cgraph_check_inline_limits (e->caller, e->callee,
1305                                                   &e->inline_failed))
1306                 {
1307                   if (cgraph_dump_file)
1308                     fprintf (cgraph_dump_file, " Not inlining into %s:%s.\n",
1309                              cgraph_node_name (e->caller), e->inline_failed);
1310                   continue;
1311                 }
1312               next = cgraph_mark_inline (e);
1313               where = e->caller;
1314               if (where->global.inlined_to)
1315                 where = where->global.inlined_to;
1316
1317               if (heap_node[where->uid])
1318                 fibheap_replace_key (heap, heap_node[where->uid],
1319                                      cgraph_estimate_growth (where));
1320
1321               if (cgraph_dump_file)
1322                 fprintf (cgraph_dump_file,
1323                          " Inlined into %s which now has %i insns.\n",
1324                          cgraph_node_name (e->caller),
1325                          e->caller->global.insns);
1326             }
1327         }
1328
1329       /* Similarly all functions called by the function we just inlined
1330          are now called more times; update keys.  */
1331       update_callee_keys (heap, heap_node, node);
1332
1333       if (cgraph_dump_file)
1334         fprintf (cgraph_dump_file,
1335                  " Inlined for a net change of %+i insns.\n",
1336                  overall_insns - old_insns);
1337     }
1338   while ((node = fibheap_extract_min (heap)) != NULL)
1339     if (!node->local.disregard_inline_limits)
1340       cgraph_set_inline_failed (node, N_("--param inline-unit-growth limit reached"));
1341   fibheap_delete (heap);
1342   free (heap_node);
1343 }
1344
1345 /* Decide on the inlining.  We do so in the topological order to avoid
1346    expenses on updating datastructures.  */
1347
1348 static void
1349 cgraph_decide_inlining (void)
1350 {
1351   struct cgraph_node *node;
1352   int nnodes;
1353   struct cgraph_node **order =
1354     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1355   int old_insns = 0;
1356   int i;
1357
1358   for (node = cgraph_nodes; node; node = node->next)
1359     initial_insns += node->local.self_insns;
1360   overall_insns = initial_insns;
1361
1362   nnodes = cgraph_postorder (order);
1363
1364   if (cgraph_dump_file)
1365     fprintf (cgraph_dump_file,
1366              "\nDeciding on inlining.  Starting with %i insns.\n",
1367              initial_insns);
1368
1369   for (node = cgraph_nodes; node; node = node->next)
1370     node->aux = 0;
1371
1372   if (cgraph_dump_file)
1373     fprintf (cgraph_dump_file, "\nInlining always_inline functions:\n");
1374
1375   /* In the first pass mark all always_inline edges.  Do this with a priority
1376      so none of our later choices will make this impossible.  */
1377   for (i = nnodes - 1; i >= 0; i--)
1378     {
1379       struct cgraph_edge *e;
1380
1381       node = order[i];
1382
1383       for (e = node->callees; e; e = e->next_callee)
1384         if (e->callee->local.disregard_inline_limits)
1385           break;
1386       if (!e)
1387         continue;
1388       if (cgraph_dump_file)
1389         fprintf (cgraph_dump_file,
1390                  "\nConsidering %s %i insns (always inline)\n",
1391                  cgraph_node_name (e->callee), e->callee->global.insns);
1392       for (; e; e = e->next_callee)
1393         {
1394           old_insns = overall_insns;
1395           if (!e->inline_failed || !e->callee->local.disregard_inline_limits)
1396             continue;
1397           if (cgraph_recursive_inlining_p (order[i], e->callee,
1398                                            &e->inline_failed))
1399             continue;
1400           cgraph_mark_inline (e);
1401           if (cgraph_dump_file)
1402             fprintf (cgraph_dump_file,
1403                      " Inlined into %s which now has %i insns.\n",
1404                      cgraph_node_name (node->callees->caller),
1405                      node->callees->caller->global.insns);
1406         }
1407         if (cgraph_dump_file)
1408           fprintf (cgraph_dump_file,
1409                    " Inlined for a net change of %+i insns.\n",
1410                    overall_insns - old_insns);
1411     }
1412
1413   if (!flag_really_no_inline)
1414     {
1415       cgraph_decide_inlining_of_small_functions ();
1416
1417       if (cgraph_dump_file)
1418         fprintf (cgraph_dump_file, "\nDeciding on functions called once:\n");
1419
1420       /* And finally decide what functions are called once.  */
1421
1422       for (i = nnodes - 1; i >= 0; i--)
1423         {
1424           node = order[i];
1425
1426           if (node->callers && !node->callers->next_caller && !node->needed
1427               && node->local.inlinable && node->callers->inline_failed
1428               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
1429             {
1430               bool ok = true;
1431               struct cgraph_node *node1;
1432
1433               /* Verify that we won't duplicate the caller.  */
1434               for (node1 = node->callers->caller;
1435                    node1->callers && !node1->callers->inline_failed
1436                    && ok; node1 = node1->callers->caller)
1437                 if (node1->callers->next_caller || node1->needed)
1438                   ok = false;
1439               if (ok)
1440                 {
1441                   if (cgraph_dump_file)
1442                     fprintf (cgraph_dump_file,
1443                              "\nConsidering %s %i insns.\n"
1444                              " Called once from %s %i insns.\n",
1445                              cgraph_node_name (node), node->global.insns,
1446                              cgraph_node_name (node->callers->caller),
1447                              node->callers->caller->global.insns);
1448
1449                   old_insns = overall_insns;
1450
1451                   if (cgraph_check_inline_limits (node->callers->caller, node,
1452                                                   NULL))
1453                     {
1454                       cgraph_mark_inline (node->callers);
1455                       if (cgraph_dump_file)
1456                         fprintf (cgraph_dump_file,
1457                                  " Inlined into %s which now has %i insns"
1458                                  " for a net change of %+i insns.\n",
1459                                  cgraph_node_name (node->callers->caller),
1460                                  node->callers->caller->global.insns,
1461                                  overall_insns - old_insns);
1462                     }
1463                   else
1464                     {
1465                       if (cgraph_dump_file)
1466                         fprintf (cgraph_dump_file,
1467                                  " Inline limit reached, not inlined.\n");
1468                     }
1469                 }
1470             }
1471         }
1472     }
1473
1474   /* We will never output extern functions we didn't inline.
1475      ??? Perhaps we can prevent accounting of growth of external
1476      inline functions.  */
1477   cgraph_remove_unreachable_nodes ();
1478
1479   if (cgraph_dump_file)
1480     fprintf (cgraph_dump_file,
1481              "\nInlined %i calls, eliminated %i functions, "
1482              "%i insns turned to %i insns.\n\n",
1483              ncalls_inlined, nfunctions_inlined, initial_insns,
1484              overall_insns);
1485   free (order);
1486 }
1487
1488 /* Decide on the inlining.  We do so in the topological order to avoid
1489    expenses on updating datastructures.  */
1490
1491 static void
1492 cgraph_decide_inlining_incrementally (struct cgraph_node *node)
1493 {
1494   struct cgraph_edge *e;
1495
1496   /* First of all look for always inline functions.  */
1497   for (e = node->callees; e; e = e->next_callee)
1498     if (e->callee->local.disregard_inline_limits
1499         && e->inline_failed
1500         && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
1501         /* ??? It is possible that renaming variable removed the function body
1502            in duplicate_decls. See gcc.c-torture/compile/20011119-2.c  */
1503         && DECL_SAVED_TREE (e->callee->decl))
1504       cgraph_mark_inline (e);
1505
1506   /* Now do the automatic inlining.  */
1507   if (!flag_really_no_inline)
1508     for (e = node->callees; e; e = e->next_callee)
1509       if (e->callee->local.inlinable
1510           && e->inline_failed
1511           && !e->callee->local.disregard_inline_limits
1512           && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
1513           && cgraph_check_inline_limits (node, e->callee, &e->inline_failed)
1514           && DECL_SAVED_TREE (e->callee->decl))
1515         {
1516           if (cgraph_default_inline_p (e->callee))
1517             cgraph_mark_inline (e);
1518           else
1519             e->inline_failed
1520               = N_("--param max-inline-insns-single limit reached");
1521         }
1522 }
1523
1524
1525 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL.  */
1526
1527 bool
1528 cgraph_inline_p (struct cgraph_edge *e, const char **reason)
1529 {
1530   *reason = e->inline_failed;
1531   return !e->inline_failed;
1532 }
1533
1534 /* Expand all functions that must be output.
1535
1536    Attempt to topologically sort the nodes so function is output when
1537    all called functions are already assembled to allow data to be
1538    propagated across the callgraph.  Use a stack to get smaller distance
1539    between a function and its callees (later we may choose to use a more
1540    sophisticated algorithm for function reordering; we will likely want
1541    to use subsections to make the output functions appear in top-down
1542    order).  */
1543
1544 static void
1545 cgraph_expand_all_functions (void)
1546 {
1547   struct cgraph_node *node;
1548   struct cgraph_node **order =
1549     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1550   int order_pos = 0, new_order_pos = 0;
1551   int i;
1552
1553   cgraph_mark_functions_to_output ();
1554
1555   order_pos = cgraph_postorder (order);
1556   if (order_pos != cgraph_n_nodes)
1557     abort ();
1558
1559   /* Garbage collector may remove inline clones we elliminate during
1560      optimization.  So we must be sure to not reference them.  */
1561   for (i = 0; i < order_pos; i++)
1562     if (order[i]->output)
1563       order[new_order_pos++] = order[i];
1564
1565   for (i = new_order_pos - 1; i >= 0; i--)
1566     {
1567       node = order[i];
1568       if (node->output)
1569         {
1570           if (!node->reachable)
1571             abort ();
1572           node->output = 0;
1573           cgraph_expand_function (node);
1574         }
1575     }
1576   free (order);
1577 }
1578
1579 /* Mark all local functions.
1580
1581    A local function is one whose calls can occur only in the
1582    current compilation unit and all its calls are explicit,
1583    so we can change its calling convention.
1584    We simply mark all static functions whose address is not taken
1585    as local.  */
1586
1587 static void
1588 cgraph_mark_local_functions (void)
1589 {
1590   struct cgraph_node *node;
1591
1592   if (cgraph_dump_file)
1593     fprintf (cgraph_dump_file, "\nMarking local functions:");
1594
1595   /* Figure out functions we want to assemble.  */
1596   for (node = cgraph_nodes; node; node = node->next)
1597     {
1598       node->local.local = (!node->needed
1599                            && DECL_SAVED_TREE (node->decl)
1600                            && !TREE_PUBLIC (node->decl));
1601       if (cgraph_dump_file && node->local.local)
1602         fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1603     }
1604   if (cgraph_dump_file)
1605     fprintf (cgraph_dump_file, "\n\n");
1606 }
1607
1608 /* Return true when function body of DECL still needs to be kept around
1609    for later re-use.  */
1610 bool
1611 cgraph_preserve_function_body_p (tree decl)
1612 {
1613   struct cgraph_node *node;
1614   /* Keep the body; we're going to dump it.  */
1615   if (dump_enabled_p (TDI_all))
1616     return true;
1617   if (!cgraph_global_info_ready)
1618     return (DECL_INLINE (decl) && !flag_really_no_inline);
1619   /* Look if there is any clone around.  */
1620   for (node = cgraph_node (decl); node; node = node->next_clone)
1621     if (node->global.inlined_to)
1622       return true;
1623   return false;
1624 }
1625
1626 /* Perform simple optimizations based on callgraph.  */
1627
1628 void
1629 cgraph_optimize (void)
1630 {
1631 #ifdef ENABLE_CHECKING
1632   verify_cgraph ();
1633 #endif
1634   if (!flag_unit_at_a_time)
1635     return;
1636   timevar_push (TV_CGRAPHOPT);
1637   if (!quiet_flag)
1638     fprintf (stderr, "Performing intraprocedural optimizations\n");
1639
1640   cgraph_mark_local_functions ();
1641   if (cgraph_dump_file)
1642     {
1643       fprintf (cgraph_dump_file, "Marked ");
1644       dump_cgraph (cgraph_dump_file);
1645     }
1646
1647   if (flag_inline_trees)
1648     cgraph_decide_inlining ();
1649   cgraph_global_info_ready = true;
1650   if (cgraph_dump_file)
1651     {
1652       fprintf (cgraph_dump_file, "Optimized ");
1653       dump_cgraph (cgraph_dump_file);
1654     }
1655   timevar_pop (TV_CGRAPHOPT);
1656
1657   /* Output everything.  */
1658   if (!quiet_flag)
1659     fprintf (stderr, "Assembling functions:\n");
1660 #ifdef ENABLE_CHECKING
1661   verify_cgraph ();
1662 #endif
1663   cgraph_expand_all_functions ();
1664   if (cgraph_dump_file)
1665     {
1666       fprintf (cgraph_dump_file, "\nFinal ");
1667       dump_cgraph (cgraph_dump_file);
1668     }
1669 #ifdef ENABLE_CHECKING
1670   verify_cgraph ();
1671 #endif
1672 }