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