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