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