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