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