gcc/cgraphunit.c

   1 /* Callgraph based intraprocedural optimizations.
   2    Copyright (C) 2003 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 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "tree-inline.h"
  28 #include "langhooks.h"
  29 #include "hashtab.h"
  30 #include "toplev.h"
  31 #include "flags.h"
  32 #include "ggc.h"
  33 #include "debug.h"
  34 #include "target.h"
  35 #include "cgraph.h"
  36 #include "diagnostic.h"
  37 #include "timevar.h"
  38 #include "params.h"
  39 #include "fibheap.h"
  40 #include "c-common.h"
  41
  42 #define INSNS_PER_CALL 10
  43
  44 static void cgraph_expand_functions (void);
  45 static void cgraph_mark_functions_to_output (void);
  46 static void cgraph_expand_function (struct cgraph_node *);
  47 static tree record_call_1 (tree *, int *, void *);
  48 static void cgraph_mark_local_functions (void);
  49 static void cgraph_optimize_function (struct cgraph_node *);
  50 static bool cgraph_default_inline_p (struct cgraph_node *n);
  51 static void cgraph_analyze_function (struct cgraph_node *node);
  52
  53 /* Statistics we collect about inlining algorithm.  */
  54 static int ncalls_inlined;
  55 static int nfunctions_inlined;
  56 static int initial_insns;
  57 static int overall_insns;
  58
  59 /* Records tree nodes seen in cgraph_create_edges.  Simply using
  60    walk_tree_without_duplicates doesn't guarantee each node is visited
  61    once because it gets a new htab upon each recursive call from
  62    record_calls_1.  */
  63 static htab_t visited_nodes;
  64
  65 /* Determine if function DECL is needed.  That is, visible to something
  66    either outside this translation unit, something magic in the system
  67    configury, or (if not doing unit-at-a-time) to something we havn't
  68    seen yet.  */
  69
  70 static bool
  71 decide_is_function_needed (struct cgraph_node *node, tree decl)
  72 {
  73   /* If we decided it was needed before, but at the time we didn't have
  74      the body of the function available, then it's still needed.  We have
  75      to go back and re-check its dependencies now.  */
  76   if (node->needed)
  77     return true;
  78
  79   /* Externally visible functions must be output.  The exception is
  80      COMDAT functions that must be output only when they are needed.  */
  81   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
  82     return true;
  83
  84   /* Constructors and destructors are reachable from the runtime by
  85      some mechanism.  */
  86   if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
  87     return true;
  88
  89   /* If the user told us it is used, then it must be so.  */
  90   if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
  91     return true;
  92
  93   /* ??? If the assembler name is set by hand, it is possible to assemble
  94      the name later after finalizing the function and the fact is noticed
  95      in assemble_name then.  This is arguably a bug.  */
  96   if (DECL_ASSEMBLER_NAME_SET_P (decl)
  97       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
  98     return true;
  99
 100   if (flag_unit_at_a_time)
 101     return false;
 102
 103   /* If not doing unit at a time, then we'll only defer this function
 104      if its marked for inlining.  Otherwise we want to emit it now.  */
 105
 106   /* "extern inline" functions are never output locally.  */
 107   if (DECL_EXTERNAL (decl))
 108     return false;
 109   /* We want to emit COMDAT functions only when absolutely neccesary.  */
 110   if (DECL_COMDAT (decl))
 111     return false;
 112   if (!DECL_INLINE (decl)
 113       || (!node->local.disregard_inline_limits
 114           /* When declared inline, defer even the uninlinable functions.
 115              This allows them to be elliminated when unused.  */
 116           && !DECL_DECLARED_INLINE_P (decl)
 117           && (node->local.inlinable || !cgraph_default_inline_p (node))))
 118     return true;
 119
 120   return false;
 121 }
 122
 123 /* When not doing unit-at-a-time, output all functions enqueued.
 124    Return true when such a functions were found.  */
 125
 126 bool
 127 cgraph_assemble_pending_functions (void)
 128 {
 129   bool output = false;
 130
 131   if (flag_unit_at_a_time)
 132     return false;
 133
 134   while (cgraph_nodes_queue)
 135     {
 136       struct cgraph_node *n = cgraph_nodes_queue;
 137
 138       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
 139       if (!n->origin && !DECL_EXTERNAL (n->decl))
 140         {
 141           cgraph_expand_function (n);
 142           output = true;
 143         }
 144     }
 145
 146   return output;
 147 }
 148
 149 /* DECL has been parsed.  Take it, queue it, compile it at the whim of the
 150    logic in effect.  If NESTED is true, then our caller cannot stand to have
 151    the garbage collector run at the moment.  We would need to either create
 152    a new GC context, or just not compile right now.  */
 153
 154 void
 155 cgraph_finalize_function (tree decl, bool nested)
 156 {
 157   struct cgraph_node *node = cgraph_node (decl);
 158
 159   if (node->local.finalized)
 160     {
 161       /* As an GCC extension we allow redefinition of the function.  The
 162          semantics when both copies of bodies differ is not well defined.
 163          We replace the old body with new body so in unit at a time mode
 164          we always use new body, while in normal mode we may end up with
 165          old body inlined into some functions and new body expanded and
 166          inlined in others.
 167
 168          ??? It may make more sense to use one body for inlining and other
 169          body for expanding the function but this is dificult to do.  */
 170
 171       /* If node->output is set, then this is a unit-at-a-time compilation
 172          and we have already begun whole-unit analysis.  This is *not*
 173          testing for whether we've already emitted the function.  That
 174          case can be sort-of legitimately seen with real function
 175          redefinition errors.  I would argue that the front end should
 176          never present us with such a case, but don't enforce that for now.  */
 177       if (node->output)
 178         abort ();
 179
 180       /* Reset our datastructures so we can analyze the function again.  */
 181       memset (&node->local, 0, sizeof (node->local));
 182       memset (&node->global, 0, sizeof (node->global));
 183       memset (&node->rtl, 0, sizeof (node->rtl));
 184       node->analyzed = false;
 185       while (node->callees)
 186         cgraph_remove_call (node->decl, node->callees->callee->decl);
 187
 188       /* We may need to re-queue the node for assembling in case
 189          we already proceeded it and ignored as not needed.  */
 190       if (node->reachable && !flag_unit_at_a_time)
 191         {
 192           struct cgraph_node *n;
 193
 194           for (n = cgraph_nodes_queue; n; n = n->next_needed)
 195             if (n == node)
 196               break;
 197           if (!n)
 198             node->reachable = 0;
 199         }
 200     }
 201
 202   notice_global_symbol (decl);
 203   node->decl = decl;
 204   node->local.finalized = true;
 205
 206   /* If not unit at a time, then we need to create the call graph
 207      now, so that called functions can be queued and emitted now.  */
 208   if (!flag_unit_at_a_time)
 209     cgraph_analyze_function (node);
 210
 211   if (decide_is_function_needed (node, decl))
 212     cgraph_mark_needed_node (node);
 213
 214   /* If not unit at a time, go ahead and emit everything we've found
 215      to be reachable at this time.  */
 216   if (!nested)
 217     cgraph_assemble_pending_functions ();
 218
 219   /* If we've not yet emitted decl, tell the debug info about it.  */
 220   if (!TREE_ASM_WRITTEN (decl))
 221     (*debug_hooks->deferred_inline_function) (decl);
 222 }
 223
 224 /* Walk tree and record all calls.  Called via walk_tree.  */
 225 static tree
 226 record_call_1 (tree *tp, int *walk_subtrees, void *data)
 227 {
 228   tree t = *tp;
 229
 230   switch (TREE_CODE (t))
 231     {
 232     case VAR_DECL:
 233       /* ??? Really, we should mark this decl as *potentially* referenced
 234          by this function and re-examine whether the decl is actually used
 235          after rtl has been generated.  */
 236       if (TREE_STATIC (t))
 237         cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));
 238       break;
 239
 240     case ADDR_EXPR:
 241       if (flag_unit_at_a_time)
 242         {
 243           /* Record dereferences to the functions.  This makes the
 244              functions reachable unconditionally.  */
 245           tree decl = TREE_OPERAND (*tp, 0);
 246           if (TREE_CODE (decl) == FUNCTION_DECL)
 247             cgraph_mark_needed_node (cgraph_node (decl));
 248         }
 249       break;
 250
 251     case CALL_EXPR:
 252       {
 253         tree decl = get_callee_fndecl (*tp);
 254         if (decl && TREE_CODE (decl) == FUNCTION_DECL)
 255           {
 256             if (DECL_BUILT_IN (decl))
 257               return NULL;
 258             cgraph_record_call (data, decl);
 259
 260             /* When we see a function call, we don't want to look at the
 261                function reference in the ADDR_EXPR that is hanging from
 262                the CALL_EXPR we're examining here, because we would
 263                conclude incorrectly that the function's address could be
 264                taken by something that is not a function call.  So only
 265                walk the function parameter list, skip the other subtrees.  */
 266
 267             walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data,
 268                        visited_nodes);
 269             *walk_subtrees = 0;
 270           }
 271         break;
 272       }
 273
 274     default:
 275       /* Save some cycles by not walking types and declaration as we
 276          won't find anything useful there anyway.  */
 277       if (DECL_P (*tp) || TYPE_P (*tp))
 278         {
 279           *walk_subtrees = 0;
 280           break;
 281         }
 282
 283       if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
 284         return (*lang_hooks.callgraph.analyze_expr) (tp, walk_subtrees, data);
 285       break;
 286     }
 287
 288   return NULL;
 289 }
 290
 291 /* Create cgraph edges for function calls inside BODY from DECL.  */
 292
 293 void
 294 cgraph_create_edges (tree decl, tree body)
 295 {
 296   /* The nodes we're interested in are never shared, so walk
 297      the tree ignoring duplicates.  */
 298   visited_nodes = htab_create (37, htab_hash_pointer,
 299                                     htab_eq_pointer, NULL);
 300   walk_tree (&body, record_call_1, decl, visited_nodes);
 301   htab_delete (visited_nodes);
 302   visited_nodes = NULL;
 303 }
 304
 305 /* Analyze the function scheduled to be output.  */
 306 static void
 307 cgraph_analyze_function (struct cgraph_node *node)
 308 {
 309   tree decl = node->decl;
 310
 311   current_function_decl = decl;
 312
 313   /* First kill forward declaration so reverse inlining works properly.  */
 314   cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
 315
 316   node->local.inlinable = tree_inlinable_function_p (decl);
 317   if (!DECL_ESTIMATED_INSNS (decl))
 318     DECL_ESTIMATED_INSNS (decl)
 319       = (*lang_hooks.tree_inlining.estimate_num_insns) (decl);
 320   node->local.self_insns = DECL_ESTIMATED_INSNS (decl);
 321   if (node->local.inlinable)
 322     node->local.disregard_inline_limits
 323       = (*lang_hooks.tree_inlining.disregard_inline_limits) (decl);
 324
 325   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
 326   node->global.insns = node->local.self_insns;
 327   if (!DECL_EXTERNAL (decl))
 328     {
 329       node->global.cloned_times = 1;
 330       node->global.will_be_output = true;
 331     }
 332
 333   node->analyzed = true;
 334   current_function_decl = NULL;
 335 }
 336
 337 /* Analyze the whole compilation unit once it is parsed completely.  */
 338
 339 void
 340 cgraph_finalize_compilation_unit (void)
 341 {
 342   struct cgraph_node *node;
 343
 344   if (!flag_unit_at_a_time)
 345     {
 346       cgraph_assemble_pending_functions ();
 347       return;
 348     }
 349
 350   cgraph_varpool_assemble_pending_decls ();
 351   if (!quiet_flag)
 352     fprintf (stderr, "\nAnalyzing compilation unit\n");
 353
 354   timevar_push (TV_CGRAPH);
 355   if (cgraph_dump_file)
 356     {
 357       fprintf (cgraph_dump_file, "\nInitial entry points:");
 358       for (node = cgraph_nodes; node; node = node->next)
 359         if (node->needed && DECL_SAVED_TREE (node->decl))
 360           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 361       fprintf (cgraph_dump_file, "\n");
 362     }
 363
 364   /* Propagate reachability flag and lower representation of all reachable
 365      functions.  In the future, lowering will introduce new functions and
 366      new entry points on the way (by template instantiation and virtual
 367      method table generation for instance).  */
 368   while (cgraph_nodes_queue)
 369     {
 370       struct cgraph_edge *edge;
 371       tree decl = cgraph_nodes_queue->decl;
 372
 373       node = cgraph_nodes_queue;
 374       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
 375
 376       /* ??? It is possible to create extern inline function and later using
 377          weak alas attribute to kill it's body. See
 378          gcc.c-torture/compile/20011119-1.c  */
 379       if (!DECL_SAVED_TREE (decl))
 380         continue;
 381
 382       if (node->analyzed || !node->reachable || !DECL_SAVED_TREE (decl))
 383         abort ();
 384
 385       cgraph_analyze_function (node);
 386
 387       for (edge = node->callees; edge; edge = edge->next_callee)
 388         if (!edge->callee->reachable)
 389           cgraph_mark_reachable_node (edge->callee);
 390
 391       cgraph_varpool_assemble_pending_decls ();
 392     }
 393
 394   /* Collect entry points to the unit.  */
 395
 396   if (cgraph_dump_file)
 397     {
 398       fprintf (cgraph_dump_file, "\nUnit entry points:");
 399       for (node = cgraph_nodes; node; node = node->next)
 400         if (node->needed && DECL_SAVED_TREE (node->decl))
 401           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 402       fprintf (cgraph_dump_file, "\n");
 403       dump_cgraph (cgraph_dump_file);
 404     }
 405
 406   if (cgraph_dump_file)
 407     fprintf (cgraph_dump_file, "\nReclaiming functions:");
 408
 409   for (node = cgraph_nodes; node; node = node->next)
 410     {
 411       tree decl = node->decl;
 412
 413       if (!node->reachable && DECL_SAVED_TREE (decl))
 414         {
 415           cgraph_remove_node (node);
 416           if (cgraph_dump_file)
 417             fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 418         }
 419     }
 420   if (cgraph_dump_file)
 421     fprintf (cgraph_dump_file, "\n");
 422   ggc_collect ();
 423   timevar_pop (TV_CGRAPH);
 424 }
 425
 426 /* Figure out what functions we want to assemble.  */
 427
 428 static void
 429 cgraph_mark_functions_to_output (void)
 430 {
 431   struct cgraph_node *node;
 432
 433   for (node = cgraph_nodes; node; node = node->next)
 434     {
 435       tree decl = node->decl;
 436       struct cgraph_edge *e;
 437       if (node->output)
 438         abort ();
 439
 440       for (e = node->callers; e; e = e->next_caller)
 441         if (!e->inline_call)
 442           break;
 443
 444       /* We need to output all local functions that are used and not
 445          always inlined, as well as those that are reachable from
 446          outside the current compilation unit.  */
 447       if (DECL_SAVED_TREE (decl)
 448           && (node->needed
 449               || (e && node->reachable))
 450           && !TREE_ASM_WRITTEN (decl) && !node->origin
 451           && !DECL_EXTERNAL (decl))
 452         node->output = 1;
 453     }
 454 }
 455
 456 /* Optimize the function before expansion.  */
 457
 458 static void
 459 cgraph_optimize_function (struct cgraph_node *node)
 460 {
 461   tree decl = node->decl;
 462
 463   timevar_push (TV_INTEGRATION);
 464   /* optimize_inline_calls avoids inlining of current_function_decl.  */
 465   current_function_decl = decl;
 466   if (flag_inline_trees)
 467     optimize_inline_calls (decl);
 468   if (node->nested)
 469     {
 470       for (node = node->nested; node; node = node->next_nested)
 471         cgraph_optimize_function (node);
 472     }
 473   timevar_pop (TV_INTEGRATION);
 474 }
 475
 476 /* Expand function specified by NODE.  */
 477
 478 static void
 479 cgraph_expand_function (struct cgraph_node *node)
 480 {
 481   tree decl = node->decl;
 482   struct cgraph_edge *e;
 483
 484   if (flag_unit_at_a_time)
 485     announce_function (decl);
 486
 487   cgraph_optimize_function (node);
 488
 489   /* Generate RTL for the body of DECL.  Nested functions are expanded
 490      via lang_expand_decl_stmt.  */
 491   (*lang_hooks.callgraph.expand_function) (decl);
 492
 493   if (!flag_unit_at_a_time)
 494     {
 495        if (!node->local.inlinable
 496            || (!node->local.disregard_inline_limits
 497                && !cgraph_default_inline_p (node)))
 498          DECL_SAVED_TREE (node->decl) = NULL;
 499     }
 500   else
 501     {
 502       for (e = node->callers; e; e = e->next_caller)
 503         if (e->inline_call)
 504           break;
 505       if (!e)
 506         DECL_SAVED_TREE (decl) = NULL;
 507     }
 508   current_function_decl = NULL;
 509 }
 510
 511 /* Fill array order with all nodes with output flag set in the reverse
 512    topological order.  */
 513 static int
 514 cgraph_postorder (struct cgraph_node **order)
 515 {
 516   struct cgraph_node *node, *node2;
 517   int stack_size = 0;
 518   int order_pos = 0;
 519   struct cgraph_edge *edge, last;
 520
 521   struct cgraph_node **stack =
 522     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
 523
 524   /* We have to deal with cycles nicely, so use a depth first traversal
 525      output algorithm.  Ignore the fact that some functions won't need
 526      to be output and put them into order as well, so we get dependencies
 527      right through intline functions.  */
 528   for (node = cgraph_nodes; node; node = node->next)
 529     node->aux = NULL;
 530   for (node = cgraph_nodes; node; node = node->next)
 531     if (!node->aux)
 532       {
 533         node2 = node;
 534         if (!node->callers)
 535           node->aux = &last;
 536         else
 537           node->aux = node->callers;
 538         while (node2)
 539           {
 540             while (node2->aux != &last)
 541               {
 542                 edge = node2->aux;
 543                 if (edge->next_caller)
 544                   node2->aux = edge->next_caller;
 545                 else
 546                   node2->aux = &last;
 547                 if (!edge->caller->aux)
 548                   {
 549                     if (!edge->caller->callers)
 550                       edge->caller->aux = &last;
 551                     else
 552                       edge->caller->aux = edge->caller->callers;
 553                     stack[stack_size++] = node2;
 554                     node2 = edge->caller;
 555                     break;
 556                   }
 557               }
 558             if (node2->aux == &last)
 559               {
 560                 order[order_pos++] = node2;
 561                 if (stack_size)
 562                   node2 = stack[--stack_size];
 563                 else
 564                   node2 = NULL;
 565               }
 566           }
 567       }
 568   free (stack);
 569   return order_pos;
 570 }
 571
 572 #define INLINED_TIMES(node) ((size_t)(node)->aux)
 573 #define SET_INLINED_TIMES(node,times) ((node)->aux = (void *)(times))
 574
 575 /* Return list of nodes we decided to inline NODE into, set their output
 576    flag and compute INLINED_TIMES.
 577
 578    We do simple backtracing to get INLINED_TIMES right.  This should not be
 579    expensive as we limit the amount of inlining.  Alternatively we may first
 580    discover set of nodes, topologically sort these and propagate
 581    INLINED_TIMES  */
 582
 583 static int
 584 cgraph_inlined_into (struct cgraph_node *node, struct cgraph_node **array)
 585 {
 586   int nfound = 0;
 587   struct cgraph_edge **stack;
 588   struct cgraph_edge *e, *e1;
 589   int sp;
 590   int i;
 591
 592   /* Fast path: since we traverse in mostly topological order, we will likely
 593      find no edges.  */
 594   for (e = node->callers; e; e = e->next_caller)
 595     if (e->inline_call)
 596       break;
 597
 598   if (!e)
 599     return 0;
 600
 601   /* Allocate stack for back-tracking up callgraph.  */
 602   stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge));
 603   sp = 0;
 604
 605   /* Push the first edge on to the stack.  */
 606   stack[sp++] = e;
 607
 608   while (sp)
 609     {
 610       struct cgraph_node *caller;
 611
 612       /* Look at the edge on the top of the stack.  */
 613       e = stack[sp - 1];
 614       caller = e->caller;
 615
 616       /* Check if the caller destination has been visited yet.  */
 617       if (!caller->output)
 618         {
 619           array[nfound++] = e->caller;
 620           /* Mark that we have visited the destination.  */
 621           caller->output = true;
 622           SET_INLINED_TIMES (caller, 0);
 623         }
 624       SET_INLINED_TIMES (caller, INLINED_TIMES (caller) + 1);
 625
 626       for (e1 = caller->callers; e1; e1 = e1->next_caller)
 627         if (e1->inline_call)
 628           break;
 629       if (e1)
 630         stack[sp++] = e1;
 631       else
 632         {
 633           while (true)
 634             {
 635               for (e1 = e->next_caller; e1; e1 = e1->next_caller)
 636                 if (e1->inline_call)
 637                   break;
 638
 639               if (e1)
 640                 {
 641                   stack[sp - 1] = e1;
 642                   break;
 643                 }
 644               else
 645                 {
 646                   sp--;
 647                   if (!sp)
 648                     break;
 649                   e = stack[sp - 1];
 650                 }
 651             }
 652         }
 653     }
 654
 655   free (stack);
 656
 657
 658   if (cgraph_dump_file)
 659     {
 660       fprintf (cgraph_dump_file, "Found inline predecesors of %s:",
 661                cgraph_node_name (node));
 662       for (i = 0; i < nfound; i++)
 663         {
 664           fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i]));
 665           if (INLINED_TIMES (array[i]) != 1)
 666             fprintf (cgraph_dump_file, " (%i times)",
 667                      (int)INLINED_TIMES (array[i]));
 668         }
 669       fprintf (cgraph_dump_file, "\n");
 670     }
 671
 672   return nfound;
 673 }
 674
 675 /* Return list of nodes we decided to inline into NODE, set their output
 676    flag and compute INLINED_TIMES.
 677
 678    This function is identical to cgraph_inlined_into with callers and callees
 679    nodes swapped.  */
 680
 681 static int
 682 cgraph_inlined_callees (struct cgraph_node *node, struct cgraph_node **array)
 683 {
 684   int nfound = 0;
 685   struct cgraph_edge **stack;
 686   struct cgraph_edge *e, *e1;
 687   int sp;
 688   int i;
 689
 690   /* Fast path: since we traverse in mostly topological order, we will likely
 691      find no edges.  */
 692   for (e = node->callees; e; e = e->next_callee)
 693     if (e->inline_call)
 694       break;
 695
 696   if (!e)
 697     return 0;
 698
 699   /* Allocate stack for back-tracking up callgraph.  */
 700   stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge));
 701   sp = 0;
 702
 703   /* Push the first edge on to the stack.  */
 704   stack[sp++] = e;
 705
 706   while (sp)
 707     {
 708       struct cgraph_node *callee;
 709
 710       /* Look at the edge on the top of the stack.  */
 711       e = stack[sp - 1];
 712       callee = e->callee;
 713
 714       /* Check if the callee destination has been visited yet.  */
 715       if (!callee->output)
 716         {
 717           array[nfound++] = e->callee;
 718           /* Mark that we have visited the destination.  */
 719           callee->output = true;
 720           SET_INLINED_TIMES (callee, 0);
 721         }
 722       SET_INLINED_TIMES (callee, INLINED_TIMES (callee) + 1);
 723
 724       for (e1 = callee->callees; e1; e1 = e1->next_callee)
 725         if (e1->inline_call)
 726           break;
 727       if (e1)
 728         stack[sp++] = e1;
 729       else
 730         {
 731           while (true)
 732             {
 733               for (e1 = e->next_callee; e1; e1 = e1->next_callee)
 734                 if (e1->inline_call)
 735                   break;
 736
 737               if (e1)
 738                 {
 739                   stack[sp - 1] = e1;
 740                   break;
 741                 }
 742               else
 743                 {
 744                   sp--;
 745                   if (!sp)
 746                     break;
 747                   e = stack[sp - 1];
 748                 }
 749             }
 750         }
 751     }
 752
 753   free (stack);
 754
 755   if (cgraph_dump_file)
 756     {
 757       fprintf (cgraph_dump_file, "Found inline successors of %s:",
 758                cgraph_node_name (node));
 759       for (i = 0; i < nfound; i++)
 760         {
 761           fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i]));
 762           if (INLINED_TIMES (array[i]) != 1)
 763             fprintf (cgraph_dump_file, " (%i times)",
 764                      (int)INLINED_TIMES (array[i]));
 765         }
 766       fprintf (cgraph_dump_file, "\n");
 767     }
 768
 769   return nfound;
 770 }
 771
 772 /* Estimate size of the function after inlining WHAT into TO.  */
 773
 774 static int
 775 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
 776                                      struct cgraph_node *what)
 777 {
 778   return (what->global.insns - INSNS_PER_CALL) *times + to->global.insns;
 779 }
 780
 781 /* Estimate the growth caused by inlining NODE into all callees.  */
 782
 783 static int
 784 cgraph_estimate_growth (struct cgraph_node *node)
 785 {
 786   int growth = 0;
 787   int calls_saved = 0;
 788   int clones_added = 0;
 789   struct cgraph_edge *e;
 790
 791   for (e = node->callers; e; e = e->next_caller)
 792     if (!e->inline_call)
 793       {
 794         growth += ((cgraph_estimate_size_after_inlining (1, e->caller, node)
 795                     -
 796                     e->caller->global.insns) *e->caller->global.cloned_times);
 797         calls_saved += e->caller->global.cloned_times;
 798         clones_added += e->caller->global.cloned_times;
 799       }
 800
 801   /* ??? Wrong for self recursive functions or cases where we decide to not
 802      inline for different reasons, but it is not big deal as in that case
 803      we will keep the body around, but we will also avoid some inlining.  */
 804   if (!node->needed && !node->origin && !DECL_EXTERNAL (node->decl))
 805     growth -= node->global.insns, clones_added--;
 806
 807   if (!calls_saved)
 808     calls_saved = 1;
 809
 810   return growth;
 811 }
 812
 813 /* Update insn sizes after inlining WHAT into TO that is already inlined into
 814    all nodes in INLINED array.  */
 815
 816 static void
 817 cgraph_mark_inline (struct cgraph_node *to, struct cgraph_node *what,
 818                     struct cgraph_node **inlined, int ninlined,
 819                     struct cgraph_node **inlined_callees,
 820                     int ninlined_callees)
 821 {
 822   int i;
 823   int times = 0;
 824   int clones = 0;
 825   struct cgraph_edge *e;
 826   bool called = false;
 827   int new_insns;
 828
 829   for (e = what->callers; e; e = e->next_caller)
 830     {
 831       if (e->caller == to)
 832         {
 833           if (e->inline_call)
 834             abort ();
 835           e->inline_call = true;
 836           times++;
 837           clones += e->caller->global.cloned_times;
 838         }
 839       else if (!e->inline_call)
 840         called = true;
 841     }
 842   if (!times)
 843     abort ();
 844   ncalls_inlined += times;
 845
 846   new_insns = cgraph_estimate_size_after_inlining (times, to, what);
 847   if (to->global.will_be_output)
 848     overall_insns += new_insns - to->global.insns;
 849   to->global.insns = new_insns;
 850
 851   if (!called && !what->needed && !what->origin
 852       && !DECL_EXTERNAL (what->decl))
 853     {
 854       if (!what->global.will_be_output)
 855         abort ();
 856       clones--;
 857       nfunctions_inlined++;
 858       what->global.will_be_output = 0;
 859       overall_insns -= what->global.insns;
 860     }
 861   what->global.cloned_times += clones;
 862   for (i = 0; i < ninlined; i++)
 863     {
 864       new_insns =
 865         cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) *
 866                                              times, inlined[i], what);
 867       if (inlined[i]->global.will_be_output)
 868         overall_insns += new_insns - inlined[i]->global.insns;
 869       inlined[i]->global.insns = new_insns;
 870     }
 871   for (i = 0; i < ninlined_callees; i++)
 872     {
 873       inlined_callees[i]->global.cloned_times +=
 874         INLINED_TIMES (inlined_callees[i]) * clones;
 875     }
 876 }
 877
 878 /* Return false when inlining WHAT into TO is not good idea as it would cause
 879    too large growth of function bodies.  */
 880
 881 static bool
 882 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
 883                             struct cgraph_node **inlined, int ninlined)
 884 {
 885   int i;
 886   int times = 0;
 887   struct cgraph_edge *e;
 888   int newsize;
 889   int limit;
 890
 891   for (e = to->callees; e; e = e->next_callee)
 892     if (e->callee == what)
 893       times++;
 894
 895   /* When inlining large function body called once into small function,
 896      take the inlined function as base for limiting the growth.  */
 897   if (to->local.self_insns > what->local.self_insns)
 898     limit = to->local.self_insns;
 899   else
 900     limit = what->local.self_insns;
 901
 902   limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
 903
 904   newsize = cgraph_estimate_size_after_inlining (times, to, what);
 905   if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
 906       && newsize > limit)
 907     return false;
 908   for (i = 0; i < ninlined; i++)
 909     {
 910       newsize =
 911         cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) *
 912                                              times, inlined[i], what);
 913       if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
 914           && newsize >
 915           inlined[i]->local.self_insns *
 916           (100 + PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH)) / 100)
 917         return false;
 918     }
 919   return true;
 920 }
 921
 922 /* Return true when function N is small enought to be inlined.  */
 923
 924 static bool
 925 cgraph_default_inline_p (struct cgraph_node *n)
 926 {
 927   if (!DECL_INLINE (n->decl) || !DECL_SAVED_TREE (n->decl))
 928     return false;
 929   if (DECL_DECLARED_INLINE_P (n->decl))
 930     return n->global.insns < MAX_INLINE_INSNS_SINGLE;
 931   else
 932     return n->global.insns < MAX_INLINE_INSNS_AUTO;
 933 }
 934
 935 /* We use greedy algorithm for inlining of small functions:
 936    All inline candidates are put into prioritized heap based on estimated
 937    growth of the overall number of instructions and then update the estimates.
 938
 939    INLINED and INLINED_CALEES are just pointers to arrays large enought
 940    to be passed to cgraph_inlined_into and cgraph_inlined_callees.  */
 941
 942 static void
 943 cgraph_decide_inlining_of_small_functions (struct cgraph_node **inlined,
 944                                            struct cgraph_node **inlined_callees)
 945 {
 946   int i;
 947   struct cgraph_node *node;
 948   fibheap_t heap = fibheap_new ();
 949   struct fibnode **heap_node =
 950     xcalloc (cgraph_max_uid, sizeof (struct fibnode *));
 951   int ninlined, ninlined_callees;
 952   int max_insns = ((HOST_WIDEST_INT) initial_insns
 953                    * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
 954
 955   /* Put all inline candidates into the heap.  */
 956
 957   for (node = cgraph_nodes; node; node = node->next)
 958     {
 959       struct cgraph_edge *e;
 960
 961       if (!node->local.inlinable || !node->callers
 962           || !cgraph_default_inline_p (node))
 963         continue;
 964
 965       /* Rule out always_inline functions we dealt with earlier.  */
 966       for (e = node->callers; e; e = e->next_caller)
 967         if (e->inline_call)
 968           break;
 969       if (e)
 970         continue;
 971       heap_node[node->uid] =
 972         fibheap_insert (heap, cgraph_estimate_growth (node), node);
 973     }
 974
 975   if (cgraph_dump_file)
 976     fprintf (cgraph_dump_file, "\n\nDeciding on inlining: ");
 977   while ((node = fibheap_extract_min (heap)) && overall_insns <= max_insns)
 978     {
 979       struct cgraph_edge *e;
 980       int old_insns = overall_insns;
 981
 982       heap_node[node->uid] = NULL;
 983       if (cgraph_dump_file)
 984         fprintf (cgraph_dump_file, "Considering %s %i insns, growth %i.\n",
 985                  cgraph_node_name (node), node->global.insns,
 986                  cgraph_estimate_growth (node));
 987       if (!cgraph_default_inline_p (node))
 988         {
 989           if (cgraph_dump_file)
 990             fprintf (cgraph_dump_file, "Function too large.\n");
 991           continue;
 992         }
 993       ninlined_callees = cgraph_inlined_callees (node, inlined_callees);
 994       for (e = node->callers; e; e = e->next_caller)
 995         if (!e->inline_call && e->caller != node)
 996           {
 997             ninlined = cgraph_inlined_into (e->caller, inlined);
 998             if (e->callee->output
 999                 || !cgraph_check_inline_limits (e->caller, node, inlined,
1000                                                 ninlined))
1001               {
1002                 for (i = 0; i < ninlined; i++)
1003                   inlined[i]->output = 0, node->aux = 0;
1004                 if (cgraph_dump_file)
1005                   fprintf (cgraph_dump_file, "Not inlining into %s\n",
1006                            cgraph_node_name (e->caller));
1007                 continue;
1008               }
1009             cgraph_mark_inline (e->caller, node, inlined, ninlined,
1010                                 inlined_callees, ninlined_callees);
1011             if (heap_node[e->caller->uid])
1012               fibheap_replace_key (heap, heap_node[e->caller->uid],
1013                                    cgraph_estimate_growth (e->caller));
1014
1015             /* Size of the functions we updated into has changed, so update
1016                the keys.  */
1017             for (i = 0; i < ninlined; i++)
1018               {
1019                 inlined[i]->output = 0, node->aux = 0;
1020                 if (heap_node[inlined[i]->uid])
1021                   fibheap_replace_key (heap, heap_node[inlined[i]->uid],
1022                                        cgraph_estimate_growth (inlined[i]));
1023               }
1024           }
1025
1026       /* Similarly all functions called by function we just inlined
1027          are now called more times; update keys.  */
1028
1029       for (e = node->callees; e; e = e->next_callee)
1030         if (!e->inline_call && heap_node[e->callee->uid])
1031           fibheap_replace_key (heap, heap_node[e->callee->uid],
1032                                cgraph_estimate_growth (e->callee));
1033
1034       for (i = 0; i < ninlined_callees; i++)
1035         {
1036           struct cgraph_edge *e;
1037
1038           for (e = inlined_callees[i]->callees; e; e = e->next_callee)
1039             if (!e->inline_call && heap_node[e->callee->uid])
1040               fibheap_replace_key (heap, heap_node[e->callee->uid],
1041                                    cgraph_estimate_growth (e->callee));
1042
1043           inlined_callees[i]->output = 0, node->aux = 0;
1044         }
1045       if (cgraph_dump_file)
1046         fprintf (cgraph_dump_file,
1047                  "Created %i clones, Num insns:%i (%+i), %.2f%%.\n\n",
1048                  node->global.cloned_times - 1,
1049                  overall_insns, overall_insns - old_insns,
1050                  overall_insns * 100.0 / initial_insns);
1051     }
1052   if (cgraph_dump_file && !fibheap_empty (heap))
1053     fprintf (cgraph_dump_file, "inline-unit-growth limit reached.\n");
1054   fibheap_delete (heap);
1055   free (heap_node);
1056 }
1057
1058 /* Decide on the inlining.  We do so in the topological order to avoid
1059    expenses on updating datastructures.  */
1060
1061 static void
1062 cgraph_decide_inlining (void)
1063 {
1064   struct cgraph_node *node;
1065   int nnodes;
1066   struct cgraph_node **order =
1067     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1068   struct cgraph_node **inlined =
1069     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1070   struct cgraph_node **inlined_callees =
1071     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1072   int ninlined;
1073   int ninlined_callees;
1074   int i, y;
1075
1076   for (node = cgraph_nodes; node; node = node->next)
1077     initial_insns += node->local.self_insns;
1078   overall_insns = initial_insns;
1079
1080   nnodes = cgraph_postorder (order);
1081
1082   for (node = cgraph_nodes; node; node = node->next)
1083     node->aux = 0;
1084
1085   if (cgraph_dump_file)
1086     fprintf (cgraph_dump_file, "\n\nDeciding on always_inline functions:\n");
1087
1088   /* In the first pass mark all always_inline edges.  Do this with a priority
1089      so no our decisions makes this impossible.  */
1090   for (i = nnodes - 1; i >= 0; i--)
1091     {
1092       struct cgraph_edge *e;
1093
1094       node = order[i];
1095
1096       for (e = node->callees; e; e = e->next_callee)
1097         if (e->callee->local.disregard_inline_limits)
1098           break;
1099       if (!e)
1100         continue;
1101       if (cgraph_dump_file)
1102         fprintf (cgraph_dump_file,
1103                  "Considering %s %i insns (always inline)\n",
1104                  cgraph_node_name (node), node->global.insns);
1105       ninlined = cgraph_inlined_into (order[i], inlined);
1106       for (; e; e = e->next_callee)
1107         {
1108           if (e->inline_call || !e->callee->local.disregard_inline_limits)
1109             continue;
1110           if (e->callee->output || e->callee == node)
1111             continue;
1112           ninlined_callees =
1113             cgraph_inlined_callees (e->callee, inlined_callees);
1114           cgraph_mark_inline (node, e->callee, inlined, ninlined,
1115                               inlined_callees, ninlined_callees);
1116           for (y = 0; y < ninlined_callees; y++)
1117             inlined_callees[y]->output = 0, node->aux = 0;
1118           if (cgraph_dump_file)
1119             fprintf (cgraph_dump_file, "Inlined %i times. Now %i insns\n\n",
1120                      node->global.cloned_times, overall_insns);
1121         }
1122       for (y = 0; y < ninlined; y++)
1123         inlined[y]->output = 0, node->aux = 0;
1124     }
1125
1126   cgraph_decide_inlining_of_small_functions (inlined, inlined_callees);
1127
1128   if (cgraph_dump_file)
1129     fprintf (cgraph_dump_file, "\n\nFunctions to inline once:\n");
1130
1131   /* And finally decide what functions are called once.  */
1132
1133   for (i = nnodes - 1; i >= 0; i--)
1134     {
1135       node = order[i];
1136
1137       if (node->callers && !node->callers->next_caller && !node->needed
1138           && node->local.inlinable && !node->callers->inline_call
1139           && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
1140         {
1141           bool ok = true;
1142           struct cgraph_node *node1;
1143
1144           /* Verify that we won't duplicate the caller.  */
1145           for (node1 = node->callers->caller;
1146                node1->callers && node1->callers->inline_call
1147                && ok; node1 = node1->callers->caller)
1148             if (node1->callers->next_caller || node1->needed)
1149               ok = false;
1150           if (ok)
1151             {
1152               if (cgraph_dump_file)
1153                 fprintf (cgraph_dump_file,
1154                          "Considering %s %i insns (called once)\n",
1155                          cgraph_node_name (node), node->global.insns);
1156               ninlined = cgraph_inlined_into (node->callers->caller, inlined);
1157               if (cgraph_check_inline_limits
1158                   (node->callers->caller, node, inlined, ninlined))
1159                 {
1160                   ninlined_callees =
1161                     cgraph_inlined_callees (node, inlined_callees);
1162                   cgraph_mark_inline (node->callers->caller, node, inlined,
1163                                       ninlined, inlined_callees,
1164                                       ninlined_callees);
1165                   for (y = 0; y < ninlined_callees; y++)
1166                     inlined_callees[y]->output = 0, node->aux = 0;
1167                   if (cgraph_dump_file)
1168                     fprintf (cgraph_dump_file, "Inlined. Now %i insns\n\n", overall_insns);
1169                 }
1170               for (y = 0; y < ninlined; y++)
1171                 inlined[y]->output = 0, node->aux = 0;
1172             }
1173         }
1174     }
1175
1176   if (cgraph_dump_file)
1177     fprintf (cgraph_dump_file,
1178              "\nInlined %i calls, elliminated %i functions, %i insns turned to %i insns.\n",
1179              ncalls_inlined, nfunctions_inlined, initial_insns,
1180              overall_insns);
1181   free (order);
1182   free (inlined);
1183   free (inlined_callees);
1184 }
1185
1186 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL.  */
1187
1188 bool
1189 cgraph_inline_p (tree caller_decl, tree callee_decl)
1190 {
1191   struct cgraph_node *caller = cgraph_node (caller_decl);
1192   struct cgraph_node *callee = cgraph_node (callee_decl);
1193   struct cgraph_edge *e;
1194
1195   for (e = caller->callees; e; e = e->next_callee)
1196     if (e->callee == callee)
1197       return e->inline_call;
1198   /* We do not record builtins in the callgraph.  Perhaps it would make more
1199      sense to do so and then prune out those not overwritten by explicit
1200      function body.  */
1201   return false;
1202 }
1203 /* Expand all functions that must be output.
1204
1205    Attempt to topologically sort the nodes so function is output when
1206    all called functions are already assembled to allow data to be
1207    propagated across the callgraph.  Use a stack to get smaller distance
1208    between a function and it's callees (later we may choose to use a more
1209    sophisticated algorithm for function reordering; we will likely want
1210    to use subsections to make the output functions appear in top-down
1211    order).  */
1212
1213 static void
1214 cgraph_expand_functions (void)
1215 {
1216   struct cgraph_node *node;
1217   struct cgraph_node **order =
1218     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1219   int order_pos = 0;
1220   int i;
1221
1222   cgraph_mark_functions_to_output ();
1223
1224   order_pos = cgraph_postorder (order);
1225
1226   for (i = order_pos - 1; i >= 0; i--)
1227     {
1228       node = order[i];
1229       if (node->output)
1230         {
1231           if (!node->reachable)
1232             abort ();
1233           node->output = 0;
1234           cgraph_expand_function (node);
1235         }
1236     }
1237   free (order);
1238 }
1239
1240 /* Mark all local functions.
1241
1242    A local function is one whose calls can occur only in the
1243    current compilation unit, so we change its calling convention.
1244    We simply mark all static functions whose address is not taken
1245    as local.  */
1246
1247 static void
1248 cgraph_mark_local_functions (void)
1249 {
1250   struct cgraph_node *node;
1251
1252   if (cgraph_dump_file)
1253     fprintf (cgraph_dump_file, "Marking local functions:");
1254
1255   /* Figure out functions we want to assemble.  */
1256   for (node = cgraph_nodes; node; node = node->next)
1257     {
1258       node->local.local = (!node->needed
1259                            && DECL_SAVED_TREE (node->decl)
1260                            && !TREE_PUBLIC (node->decl));
1261       if (cgraph_dump_file && node->local.local)
1262         fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1263     }
1264   if (cgraph_dump_file)
1265     fprintf (cgraph_dump_file, "\n");
1266 }
1267
1268 /* Perform simple optimizations based on callgraph.  */
1269
1270 void
1271 cgraph_optimize (void)
1272 {
1273   if (!flag_unit_at_a_time)
1274     return;
1275   timevar_push (TV_CGRAPHOPT);
1276   if (!quiet_flag)
1277     fprintf (stderr, "Performing intraprocedural optimizations\n");
1278   if (cgraph_dump_file)
1279     {
1280       fprintf (cgraph_dump_file, "Initial callgraph:");
1281       dump_cgraph (cgraph_dump_file);
1282     }
1283   cgraph_mark_local_functions ();
1284
1285   cgraph_decide_inlining ();
1286
1287   cgraph_global_info_ready = true;
1288   if (cgraph_dump_file)
1289     {
1290       fprintf (cgraph_dump_file, "Optimized callgraph:");
1291       dump_cgraph (cgraph_dump_file);
1292     }
1293   timevar_pop (TV_CGRAPHOPT);
1294   if (!quiet_flag)
1295     fprintf (stderr, "Assembling functions:");
1296
1297   /* Output everything.  */
1298   cgraph_expand_functions ();
1299   if (cgraph_dump_file)
1300     {
1301       fprintf (cgraph_dump_file, "Final callgraph:");
1302       dump_cgraph (cgraph_dump_file);
1303     }
1304 }