1/* Inlining decision heuristics. 2 Copyright (C) 2003, 2004 Free Software Foundation, Inc. 3 Contributed by Jan Hubicka 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22/* Inlining decision heuristics 23 24 We separate inlining decisions from the inliner itself and store it 25 inside callgraph as so called inline plan. Refer to cgraph.c 26 documentation about particular representation of inline plans in the 27 callgraph. 28 29 There are three major parts of this file: 30 31 cgraph_mark_inline implementation 32 33 This function allows to mark given call inline and performs necessary 34 modifications of cgraph (production of the clones and updating overall 35 statistics) 36 37 inlining heuristics limits 38 39 These functions allow to check that particular inlining is allowed 40 by the limits specified by user (allowed function growth, overall unit 41 growth and so on). 42 43 inlining heuristics 44 45 This is implementation of IPA pass aiming to get as much of benefit 46 from inlining obeying the limits checked above. 47 48 The implementation of particular heuristics is separated from 49 the rest of code to make it easier to replace it with more complicated 50 implementation in the future. The rest of inlining code acts as a 51 library aimed to modify the callgraph and verify that the parameters 52 on code size growth fits. 53 54 To mark given call inline, use cgraph_mark_inline function, the 55 verification is performed by cgraph_default_inline_p and 56 cgraph_check_inline_limits. 57 58 The heuristics implements simple knapsack style algorithm ordering 59 all functions by their "profitability" (estimated by code size growth) 60 and inlining them in priority order. 61 62 cgraph_decide_inlining implements heuristics taking whole callgraph 63 into account, while cgraph_decide_inlining_incrementally considers 64 only one function at a time and is used in non-unit-at-a-time mode. */ 65 66#include "config.h" 67#include "system.h" 68#include "coretypes.h" 69#include "tm.h" 70#include "tree.h" 71#include "tree-inline.h" 72#include "langhooks.h" 73#include "flags.h" 74#include "cgraph.h" 75#include "diagnostic.h" 76#include "timevar.h" 77#include "params.h" 78#include "fibheap.h" 79#include "intl.h" 80#include "tree-pass.h" 81#include "hashtab.h" 82#include "coverage.h" 83#include "ggc.h" 84 85/* Statistics we collect about inlining algorithm. */ 86static int ncalls_inlined; 87static int nfunctions_inlined; 88static int initial_insns; 89static int overall_insns; 90static int max_insns; 91static gcov_type max_count; 92 93/* Estimate size of the function after inlining WHAT into TO. */ 94 95static int 96cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to, 97 struct cgraph_node *what) 98{ 99 int size; 100 tree fndecl = what->decl, arg; 101 int call_insns = PARAM_VALUE (PARAM_INLINE_CALL_COST); 102 103 for (arg = DECL_ARGUMENTS (fndecl); arg; arg = TREE_CHAIN (arg)) 104 call_insns += estimate_move_cost (TREE_TYPE (arg)); 105 size = (what->global.insns - call_insns) * times + to->global.insns; 106 gcc_assert (size >= 0); 107 return size; 108} 109 110/* E is expected to be an edge being inlined. Clone destination node of 111 the edge and redirect it to the new clone. 112 DUPLICATE is used for bookkeeping on whether we are actually creating new 113 clones or re-using node originally representing out-of-line function call. 114 */ 115void 116cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate, bool update_original) 117{ 118 if (duplicate) 119 { 120 /* We may eliminate the need for out-of-line copy to be output. 121 In that case just go ahead and re-use it. */ 122 if (!e->callee->callers->next_caller 123 && !e->callee->needed 124 && flag_unit_at_a_time) 125 { 126 gcc_assert (!e->callee->global.inlined_to); 127 if (DECL_SAVED_TREE (e->callee->decl)) 128 overall_insns -= e->callee->global.insns, nfunctions_inlined++; 129 duplicate = false; 130 } 131 else 132 { 133 struct cgraph_node *n; 134 n = cgraph_clone_node (e->callee, e->count, e->loop_nest, 135 update_original); 136 cgraph_redirect_edge_callee (e, n); 137 } 138 } 139 140 if (e->caller->global.inlined_to) 141 e->callee->global.inlined_to = e->caller->global.inlined_to; 142 else 143 e->callee->global.inlined_to = e->caller; 144 145 /* Recursively clone all bodies. */ 146 for (e = e->callee->callees; e; e = e->next_callee) 147 if (!e->inline_failed) 148 cgraph_clone_inlined_nodes (e, duplicate, update_original); 149} 150 151/* Mark edge E as inlined and update callgraph accordingly. 152 UPDATE_ORIGINAL specify whether profile of original function should be 153 updated. */ 154 155void 156cgraph_mark_inline_edge (struct cgraph_edge *e, bool update_original) 157{ 158 int old_insns = 0, new_insns = 0; 159 struct cgraph_node *to = NULL, *what; 160 161 gcc_assert (e->inline_failed); 162 e->inline_failed = NULL; 163 164 if (!e->callee->global.inlined && flag_unit_at_a_time) 165 DECL_POSSIBLY_INLINED (e->callee->decl) = true; 166 e->callee->global.inlined = true; 167 168 cgraph_clone_inlined_nodes (e, true, update_original); 169 170 what = e->callee; 171 172 /* Now update size of caller and all functions caller is inlined into. */ 173 for (;e && !e->inline_failed; e = e->caller->callers) 174 { 175 old_insns = e->caller->global.insns; 176 new_insns = cgraph_estimate_size_after_inlining (1, e->caller, 177 what); 178 gcc_assert (new_insns >= 0); 179 to = e->caller; 180 to->global.insns = new_insns; 181 } 182 gcc_assert (what->global.inlined_to == to); 183 if (new_insns > old_insns) 184 overall_insns += new_insns - old_insns; 185 ncalls_inlined++; 186} 187 188/* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER. 189 Return following unredirected edge in the list of callers 190 of EDGE->CALLEE */ 191 192static struct cgraph_edge * 193cgraph_mark_inline (struct cgraph_edge *edge) 194{ 195 struct cgraph_node *to = edge->caller; 196 struct cgraph_node *what = edge->callee; 197 struct cgraph_edge *e, *next; 198 int times = 0; 199 200 /* Look for all calls, mark them inline and clone recursively 201 all inlined functions. */ 202 for (e = what->callers; e; e = next) 203 { 204 next = e->next_caller; 205 if (e->caller == to && e->inline_failed) 206 { 207 cgraph_mark_inline_edge (e, true); 208 if (e == edge) 209 edge = next; 210 times++; 211 } 212 } 213 gcc_assert (times); 214 return edge; 215} 216 217/* Estimate the growth caused by inlining NODE into all callees. */ 218 219static int 220cgraph_estimate_growth (struct cgraph_node *node) 221{ 222 int growth = 0; 223 struct cgraph_edge *e; 224 if (node->global.estimated_growth != INT_MIN) 225 return node->global.estimated_growth; 226 227 for (e = node->callers; e; e = e->next_caller) 228 if (e->inline_failed) 229 growth += (cgraph_estimate_size_after_inlining (1, e->caller, node) 230 - e->caller->global.insns); 231 232 /* ??? Wrong for self recursive functions or cases where we decide to not 233 inline for different reasons, but it is not big deal as in that case 234 we will keep the body around, but we will also avoid some inlining. */ 235 if (!node->needed && !DECL_EXTERNAL (node->decl)) 236 growth -= node->global.insns; 237 238 node->global.estimated_growth = growth; 239 return growth; 240} 241 242/* Return false when inlining WHAT into TO is not good idea 243 as it would cause too large growth of function bodies. */ 244 245static bool 246cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what, 247 const char **reason) 248{ 249 int times = 0; 250 struct cgraph_edge *e; 251 int newsize; 252 int limit; 253 254 if (to->global.inlined_to) 255 to = to->global.inlined_to; 256 257 for (e = to->callees; e; e = e->next_callee) 258 if (e->callee == what) 259 times++; 260 261 /* When inlining large function body called once into small function, 262 take the inlined function as base for limiting the growth. */ 263 if (to->local.self_insns > what->local.self_insns) 264 limit = to->local.self_insns; 265 else 266 limit = what->local.self_insns; 267 268 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100; 269 270 newsize = cgraph_estimate_size_after_inlining (times, to, what); 271 if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS) 272 && newsize > limit) 273 { 274 if (reason) 275 *reason = N_("--param large-function-growth limit reached"); 276 return false; 277 } 278 return true; 279} 280 281/* Return true when function N is small enough to be inlined. */ 282 283bool 284cgraph_default_inline_p (struct cgraph_node *n, const char **reason) 285{ 286 if (!DECL_INLINE (n->decl)) 287 { 288 if (reason) 289 *reason = N_("function not inlinable"); 290 return false; 291 } 292 293 if (!DECL_SAVED_TREE (n->decl)) 294 { 295 if (reason) 296 *reason = N_("function body not available"); 297 return false; 298 } 299 300 if (DECL_DECLARED_INLINE_P (n->decl)) 301 { 302 if (n->global.insns >= MAX_INLINE_INSNS_SINGLE) 303 { 304 if (reason) 305 *reason = N_("--param max-inline-insns-single limit reached"); 306 return false; 307 } 308 } 309 else 310 { 311 if (n->global.insns >= MAX_INLINE_INSNS_AUTO) 312 { 313 if (reason) 314 *reason = N_("--param max-inline-insns-auto limit reached"); 315 return false; 316 } 317 } 318 319 return true; 320} 321 322/* Return true when inlining WHAT would create recursive inlining. 323 We call recursive inlining all cases where same function appears more than 324 once in the single recursion nest path in the inline graph. */ 325 326static bool 327cgraph_recursive_inlining_p (struct cgraph_node *to, 328 struct cgraph_node *what, 329 const char **reason) 330{ 331 bool recursive; 332 if (to->global.inlined_to) 333 recursive = what->decl == to->global.inlined_to->decl; 334 else 335 recursive = what->decl == to->decl; 336 /* Marking recursive function inline has sane semantic and thus we should 337 not warn on it. */ 338 if (recursive && reason) 339 *reason = (what->local.disregard_inline_limits 340 ? N_("recursive inlining") : ""); 341 return recursive; 342} 343 344/* Return true if the call can be hot. */ 345static bool 346cgraph_maybe_hot_edge_p (struct cgraph_edge *edge) 347{ 348 if (profile_info && flag_branch_probabilities 349 && (edge->count 350 <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION))) 351 return false; 352 return true; 353} 354 355/* A cost model driving the inlining heuristics in a way so the edges with 356 smallest badness are inlined first. After each inlining is performed 357 the costs of all caller edges of nodes affected are recomputed so the 358 metrics may accurately depend on values such as number of inlinable callers 359 of the function or function body size. 360 361 With profiling we use number of executions of each edge to drive the cost. 362 We also should distinguish hot and cold calls where the cold calls are 363 inlined into only when code size is overall improved. 364 */ 365 366static int 367cgraph_edge_badness (struct cgraph_edge *edge) 368{ 369 if (max_count) 370 { 371 int growth = 372 cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee); 373 growth -= edge->caller->global.insns; 374 375 /* Always prefer inlining saving code size. */ 376 if (growth <= 0) 377 return INT_MIN - growth; 378 return ((int)((double)edge->count * INT_MIN / max_count)) / growth; 379 } 380 else 381 { 382 int nest = MIN (edge->loop_nest, 8); 383 int badness = cgraph_estimate_growth (edge->callee) * 256; 384 385 /* Decrease badness if call is nested. */ 386 if (badness > 0) 387 badness >>= nest; 388 else 389 badness <<= nest; 390 391 /* Make recursive inlining happen always after other inlining is done. */ 392 if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL)) 393 return badness + 1; 394 else 395 return badness; 396 } 397} 398 399/* Recompute heap nodes for each of caller edge. */ 400 401static void 402update_caller_keys (fibheap_t heap, struct cgraph_node *node, 403 bitmap updated_nodes) 404{ 405 struct cgraph_edge *edge; 406 407 if (!node->local.inlinable || node->local.disregard_inline_limits 408 || node->global.inlined_to) 409 return; 410 if (bitmap_bit_p (updated_nodes, node->uid)) 411 return; 412 bitmap_set_bit (updated_nodes, node->uid); 413 node->global.estimated_growth = INT_MIN; 414 415 for (edge = node->callers; edge; edge = edge->next_caller) 416 if (edge->inline_failed) 417 { 418 int badness = cgraph_edge_badness (edge); 419 if (edge->aux) 420 { 421 fibnode_t n = edge->aux; 422 gcc_assert (n->data == edge); 423 if (n->key == badness) 424 continue; 425 426 /* fibheap_replace_key only increase the keys. */ 427 if (fibheap_replace_key (heap, n, badness)) 428 continue; 429 fibheap_delete_node (heap, edge->aux); 430 } 431 edge->aux = fibheap_insert (heap, badness, edge); 432 } 433} 434 435/* Recompute heap nodes for each of caller edges of each of callees. */ 436 437static void 438update_callee_keys (fibheap_t heap, struct cgraph_node *node, 439 bitmap updated_nodes) 440{ 441 struct cgraph_edge *e; 442 node->global.estimated_growth = INT_MIN; 443 444 for (e = node->callees; e; e = e->next_callee) 445 if (e->inline_failed) 446 update_caller_keys (heap, e->callee, updated_nodes); 447 else if (!e->inline_failed) 448 update_callee_keys (heap, e->callee, updated_nodes); 449} 450 451/* Enqueue all recursive calls from NODE into priority queue depending on 452 how likely we want to recursively inline the call. */ 453 454static void 455lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where, 456 fibheap_t heap) 457{ 458 static int priority; 459 struct cgraph_edge *e; 460 for (e = where->callees; e; e = e->next_callee) 461 if (e->callee == node) 462 { 463 /* When profile feedback is available, prioritize by expected number 464 of calls. Without profile feedback we maintain simple queue 465 to order candidates via recursive depths. */ 466 fibheap_insert (heap, 467 !max_count ? priority++ 468 : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))), 469 e); 470 } 471 for (e = where->callees; e; e = e->next_callee) 472 if (!e->inline_failed) 473 lookup_recursive_calls (node, e->callee, heap); 474} 475 476/* Find callgraph nodes closing a circle in the graph. The 477 resulting hashtab can be used to avoid walking the circles. 478 Uses the cgraph nodes ->aux field which needs to be zero 479 before and will be zero after operation. */ 480 481static void 482cgraph_find_cycles (struct cgraph_node *node, htab_t cycles) 483{ 484 struct cgraph_edge *e; 485 486 if (node->aux) 487 { 488 void **slot; 489 slot = htab_find_slot (cycles, node, INSERT); 490 if (!*slot) 491 { 492 if (dump_file) 493 fprintf (dump_file, "Cycle contains %s\n", cgraph_node_name (node)); 494 *slot = node; 495 } 496 return; 497 } 498 499 node->aux = node; 500 for (e = node->callees; e; e = e->next_callee) 501 cgraph_find_cycles (e->callee, cycles); 502 node->aux = 0; 503} 504 505/* Leafify the cgraph node. We have to be careful in recursing 506 as to not run endlessly in circles of the callgraph. 507 We do so by using a hashtab of cycle entering nodes as generated 508 by cgraph_find_cycles. */ 509 510static void 511cgraph_flatten_node (struct cgraph_node *node, htab_t cycles) 512{ 513 struct cgraph_edge *e; 514 515 for (e = node->callees; e; e = e->next_callee) 516 { 517 /* Inline call, if possible, and recurse. Be sure we are not 518 entering callgraph circles here. */ 519 if (e->inline_failed 520 && e->callee->local.inlinable 521 && !cgraph_recursive_inlining_p (node, e->callee, 522 &e->inline_failed) 523 && !htab_find (cycles, e->callee)) 524 { 525 if (dump_file) 526 fprintf (dump_file, " inlining %s", cgraph_node_name (e->callee)); 527 cgraph_mark_inline_edge (e, true); 528 cgraph_flatten_node (e->callee, cycles); 529 } 530 else if (dump_file) 531 fprintf (dump_file, " !inlining %s", cgraph_node_name (e->callee)); 532 } 533} 534 535/* Decide on recursive inlining: in the case function has recursive calls, 536 inline until body size reaches given argument. */ 537 538static bool 539cgraph_decide_recursive_inlining (struct cgraph_node *node) 540{ 541 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO); 542 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO); 543 int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY); 544 fibheap_t heap; 545 struct cgraph_edge *e; 546 struct cgraph_node *master_clone; 547 int depth = 0; 548 int n = 0; 549 550 if (DECL_DECLARED_INLINE_P (node->decl)) 551 { 552 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE); 553 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH); 554 } 555 556 /* Make sure that function is small enough to be considered for inlining. */ 557 if (!max_depth 558 || cgraph_estimate_size_after_inlining (1, node, node) >= limit) 559 return false; 560 heap = fibheap_new (); 561 lookup_recursive_calls (node, node, heap); 562 if (fibheap_empty (heap)) 563 { 564 fibheap_delete (heap); 565 return false; 566 } 567 568 if (dump_file) 569 fprintf (dump_file, 570 " Performing recursive inlining on %s\n", 571 cgraph_node_name (node)); 572 573 /* We need original clone to copy around. */ 574 master_clone = cgraph_clone_node (node, node->count, 1, false); 575 master_clone->needed = true; 576 for (e = master_clone->callees; e; e = e->next_callee) 577 if (!e->inline_failed) 578 cgraph_clone_inlined_nodes (e, true, false); 579 580 /* Do the inlining and update list of recursive call during process. */ 581 while (!fibheap_empty (heap) 582 && (cgraph_estimate_size_after_inlining (1, node, master_clone) 583 <= limit)) 584 { 585 struct cgraph_edge *curr = fibheap_extract_min (heap); 586 struct cgraph_node *cnode; 587 588 depth = 1; 589 for (cnode = curr->caller; 590 cnode->global.inlined_to; cnode = cnode->callers->caller) 591 if (node->decl == curr->callee->decl) 592 depth++; 593 if (depth > max_depth) 594 { 595 if (dump_file) 596 fprintf (dump_file, 597 " maxmal depth reached\n"); 598 continue; 599 } 600 601 if (max_count) 602 { 603 if (!cgraph_maybe_hot_edge_p (curr)) 604 { 605 if (dump_file) 606 fprintf (dump_file, " Not inlining cold call\n"); 607 continue; 608 } 609 if (curr->count * 100 / node->count < probability) 610 { 611 if (dump_file) 612 fprintf (dump_file, 613 " Probability of edge is too small\n"); 614 continue; 615 } 616 } 617 618 if (dump_file) 619 { 620 fprintf (dump_file, 621 " Inlining call of depth %i", depth); 622 if (node->count) 623 { 624 fprintf (dump_file, " called approx. %.2f times per call", 625 (double)curr->count / node->count); 626 } 627 fprintf (dump_file, "\n"); 628 } 629 cgraph_redirect_edge_callee (curr, master_clone); 630 cgraph_mark_inline_edge (curr, false); 631 lookup_recursive_calls (node, curr->callee, heap); 632 n++; 633 } 634 if (!fibheap_empty (heap) && dump_file) 635 fprintf (dump_file, " Recursive inlining growth limit met.\n"); 636 637 fibheap_delete (heap); 638 if (dump_file) 639 fprintf (dump_file, 640 "\n Inlined %i times, body grown from %i to %i insns\n", n, 641 master_clone->global.insns, node->global.insns); 642 643 /* Remove master clone we used for inlining. We rely that clones inlined 644 into master clone gets queued just before master clone so we don't 645 need recursion. */ 646 for (node = cgraph_nodes; node != master_clone; 647 node = node->next) 648 if (node->global.inlined_to == master_clone) 649 cgraph_remove_node (node); 650 cgraph_remove_node (master_clone); 651 /* FIXME: Recursive inlining actually reduces number of calls of the 652 function. At this place we should probably walk the function and 653 inline clones and compensate the counts accordingly. This probably 654 doesn't matter much in practice. */ 655 return n > 0; 656} 657 658/* Set inline_failed for all callers of given function to REASON. */ 659 660static void 661cgraph_set_inline_failed (struct cgraph_node *node, const char *reason) 662{ 663 struct cgraph_edge *e; 664 665 if (dump_file) 666 fprintf (dump_file, "Inlining failed: %s\n", reason); 667 for (e = node->callers; e; e = e->next_caller) 668 if (e->inline_failed) 669 e->inline_failed = reason; 670} 671 672/* We use greedy algorithm for inlining of small functions: 673 All inline candidates are put into prioritized heap based on estimated 674 growth of the overall number of instructions and then update the estimates. 675 676 INLINED and INLINED_CALEES are just pointers to arrays large enough 677 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */ 678 679static void 680cgraph_decide_inlining_of_small_functions (void) 681{ 682 struct cgraph_node *node; 683 struct cgraph_edge *edge; 684 const char *failed_reason; 685 fibheap_t heap = fibheap_new (); 686 bitmap updated_nodes = BITMAP_ALLOC (NULL); 687 688 if (dump_file) 689 fprintf (dump_file, "\nDeciding on smaller functions:\n"); 690 691 /* Put all inline candidates into the heap. */ 692 693 for (node = cgraph_nodes; node; node = node->next) 694 { 695 if (!node->local.inlinable || !node->callers 696 || node->local.disregard_inline_limits) 697 continue; 698 if (dump_file) 699 fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node)); 700 701 node->global.estimated_growth = INT_MIN; 702 if (!cgraph_default_inline_p (node, &failed_reason)) 703 { 704 cgraph_set_inline_failed (node, failed_reason); 705 continue; 706 } 707 708 for (edge = node->callers; edge; edge = edge->next_caller) 709 if (edge->inline_failed) 710 { 711 gcc_assert (!edge->aux); 712 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge); 713 } 714 } 715 while (overall_insns <= max_insns && (edge = fibheap_extract_min (heap))) 716 { 717 int old_insns = overall_insns; 718 struct cgraph_node *where; 719 int growth = 720 cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee); 721 722 growth -= edge->caller->global.insns; 723 724 if (dump_file) 725 { 726 fprintf (dump_file, 727 "\nConsidering %s with %i insns\n", 728 cgraph_node_name (edge->callee), 729 edge->callee->global.insns); 730 fprintf (dump_file, 731 " to be inlined into %s\n" 732 " Estimated growth after inlined into all callees is %+i insns.\n" 733 " Estimated badness is %i.\n", 734 cgraph_node_name (edge->caller), 735 cgraph_estimate_growth (edge->callee), 736 cgraph_edge_badness (edge)); 737 if (edge->count) 738 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count); 739 } 740 gcc_assert (edge->aux); 741 edge->aux = NULL; 742 if (!edge->inline_failed) 743 continue; 744 745 /* When not having profile info ready we don't weight by any way the 746 position of call in procedure itself. This means if call of 747 function A from function B seems profitable to inline, the recursive 748 call of function A in inline copy of A in B will look profitable too 749 and we end up inlining until reaching maximal function growth. This 750 is not good idea so prohibit the recursive inlining. 751 752 ??? When the frequencies are taken into account we might not need this 753 restriction. */ 754 if (!max_count) 755 { 756 where = edge->caller; 757 while (where->global.inlined_to) 758 { 759 if (where->decl == edge->callee->decl) 760 break; 761 where = where->callers->caller; 762 } 763 if (where->global.inlined_to) 764 { 765 edge->inline_failed 766 = (edge->callee->local.disregard_inline_limits ? N_("recursive inlining") : ""); 767 if (dump_file) 768 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n"); 769 continue; 770 } 771 } 772 773 if (!cgraph_maybe_hot_edge_p (edge) && growth > 0) 774 { 775 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee, 776 &edge->inline_failed)) 777 { 778 edge->inline_failed = 779 N_("call is unlikely"); 780 if (dump_file) 781 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed); 782 } 783 continue; 784 } 785 if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed)) 786 { 787 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee, 788 &edge->inline_failed)) 789 { 790 if (dump_file) 791 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed); 792 } 793 continue; 794 } 795 if (cgraph_recursive_inlining_p (edge->caller, edge->callee, 796 &edge->inline_failed)) 797 { 798 where = edge->caller; 799 if (where->global.inlined_to) 800 where = where->global.inlined_to; 801 if (!cgraph_decide_recursive_inlining (where)) 802 continue; 803 update_callee_keys (heap, where, updated_nodes); 804 } 805 else 806 { 807 struct cgraph_node *callee; 808 if (!cgraph_check_inline_limits (edge->caller, edge->callee, 809 &edge->inline_failed)) 810 { 811 if (dump_file) 812 fprintf (dump_file, " Not inlining into %s:%s.\n", 813 cgraph_node_name (edge->caller), edge->inline_failed); 814 continue; 815 } 816 callee = edge->callee; 817 cgraph_mark_inline_edge (edge, true); 818 update_callee_keys (heap, callee, updated_nodes); 819 } 820 where = edge->caller; 821 if (where->global.inlined_to) 822 where = where->global.inlined_to; 823 824 /* Our profitability metric can depend on local properties 825 such as number of inlinable calls and size of the function body. 826 After inlining these properties might change for the function we 827 inlined into (since it's body size changed) and for the functions 828 called by function we inlined (since number of it inlinable callers 829 might change). */ 830 update_caller_keys (heap, where, updated_nodes); 831 bitmap_clear (updated_nodes); 832 833 if (dump_file) 834 { 835 fprintf (dump_file, 836 " Inlined into %s which now has %i insns," 837 "net change of %+i insns.\n", 838 cgraph_node_name (edge->caller), 839 edge->caller->global.insns, 840 overall_insns - old_insns); 841 } 842 } 843 while ((edge = fibheap_extract_min (heap)) != NULL) 844 { 845 gcc_assert (edge->aux); 846 edge->aux = NULL; 847 if (!edge->callee->local.disregard_inline_limits && edge->inline_failed 848 && !cgraph_recursive_inlining_p (edge->caller, edge->callee, 849 &edge->inline_failed)) 850 edge->inline_failed = N_("--param inline-unit-growth limit reached"); 851 } 852 fibheap_delete (heap); 853 BITMAP_FREE (updated_nodes); 854} 855 856/* Decide on the inlining. We do so in the topological order to avoid 857 expenses on updating data structures. */ 858 859static void 860cgraph_decide_inlining (void) 861{ 862 struct cgraph_node *node; 863 int nnodes; 864 struct cgraph_node **order = 865 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); 866 int old_insns = 0; 867 int i; 868 869 timevar_push (TV_INLINE_HEURISTICS); 870 max_count = 0; 871 for (node = cgraph_nodes; node; node = node->next) 872 { 873 struct cgraph_edge *e; 874 initial_insns += node->local.self_insns; 875 for (e = node->callees; e; e = e->next_callee) 876 if (max_count < e->count) 877 max_count = e->count; 878 } 879 overall_insns = initial_insns; 880 gcc_assert (!max_count || (profile_info && flag_branch_probabilities)); 881 882 max_insns = overall_insns; 883 if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS)) 884 max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS); 885 886 max_insns = ((HOST_WIDEST_INT) max_insns 887 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100); 888 889 nnodes = cgraph_postorder (order); 890 891 if (dump_file) 892 fprintf (dump_file, 893 "\nDeciding on inlining. Starting with %i insns.\n", 894 initial_insns); 895 896 for (node = cgraph_nodes; node; node = node->next) 897 node->aux = 0; 898 899 if (dump_file) 900 fprintf (dump_file, "\nInlining always_inline functions:\n"); 901 902 /* In the first pass mark all always_inline edges. Do this with a priority 903 so none of our later choices will make this impossible. */ 904 for (i = nnodes - 1; i >= 0; i--) 905 { 906 struct cgraph_edge *e, *next; 907 908 node = order[i]; 909 910 /* Handle nodes to be flattened, but don't update overall unit size. */ 911 if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL) 912 { 913 int old_overall_insns = overall_insns; 914 htab_t cycles; 915 if (dump_file) 916 fprintf (dump_file, 917 "Leafifying %s\n", cgraph_node_name (node)); 918 cycles = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL); 919 cgraph_find_cycles (node, cycles); 920 cgraph_flatten_node (node, cycles); 921 htab_delete (cycles); 922 overall_insns = old_overall_insns; 923 /* We don't need to consider always_inline functions inside the flattened 924 function anymore. */ 925 continue; 926 } 927 928 if (!node->local.disregard_inline_limits) 929 continue; 930 if (dump_file) 931 fprintf (dump_file, 932 "\nConsidering %s %i insns (always inline)\n", 933 cgraph_node_name (node), node->global.insns); 934 old_insns = overall_insns; 935 for (e = node->callers; e; e = next) 936 { 937 next = e->next_caller; 938 if (!e->inline_failed) 939 continue; 940 if (cgraph_recursive_inlining_p (e->caller, e->callee, 941 &e->inline_failed)) 942 continue; 943 cgraph_mark_inline_edge (e, true); 944 if (dump_file) 945 fprintf (dump_file, 946 " Inlined into %s which now has %i insns.\n", 947 cgraph_node_name (e->caller), 948 e->caller->global.insns); 949 } 950 if (dump_file) 951 fprintf (dump_file, 952 " Inlined for a net change of %+i insns.\n", 953 overall_insns - old_insns); 954 } 955 956 if (!flag_really_no_inline) 957 cgraph_decide_inlining_of_small_functions (); 958 959 if (!flag_really_no_inline 960 && flag_inline_functions_called_once) 961 { 962 if (dump_file) 963 fprintf (dump_file, "\nDeciding on functions called once:\n"); 964 965 /* And finally decide what functions are called once. */ 966 967 for (i = nnodes - 1; i >= 0; i--) 968 { 969 node = order[i]; 970 971 if (node->callers && !node->callers->next_caller && !node->needed 972 && node->local.inlinable && node->callers->inline_failed 973 && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl)) 974 { 975 bool ok = true; 976 struct cgraph_node *node1; 977 978 /* Verify that we won't duplicate the caller. */ 979 for (node1 = node->callers->caller; 980 node1->callers && !node1->callers->inline_failed 981 && ok; node1 = node1->callers->caller) 982 if (node1->callers->next_caller || node1->needed) 983 ok = false; 984 if (ok) 985 { 986 if (dump_file) 987 { 988 fprintf (dump_file, 989 "\nConsidering %s %i insns.\n", 990 cgraph_node_name (node), node->global.insns); 991 fprintf (dump_file, 992 " Called once from %s %i insns.\n", 993 cgraph_node_name (node->callers->caller), 994 node->callers->caller->global.insns); 995 } 996 997 old_insns = overall_insns; 998 999 if (cgraph_check_inline_limits (node->callers->caller, node, 1000 NULL)) 1001 { 1002 cgraph_mark_inline (node->callers); 1003 if (dump_file) 1004 fprintf (dump_file, 1005 " Inlined into %s which now has %i insns" 1006 " for a net change of %+i insns.\n", 1007 cgraph_node_name (node->callers->caller), 1008 node->callers->caller->global.insns, 1009 overall_insns - old_insns); 1010 } 1011 else 1012 { 1013 if (dump_file) 1014 fprintf (dump_file, 1015 " Inline limit reached, not inlined.\n"); 1016 } 1017 } 1018 } 1019 } 1020 } 1021 1022 if (dump_file) 1023 fprintf (dump_file, 1024 "\nInlined %i calls, eliminated %i functions, " 1025 "%i insns turned to %i insns.\n\n", 1026 ncalls_inlined, nfunctions_inlined, initial_insns, 1027 overall_insns); 1028 free (order); 1029 timevar_pop (TV_INLINE_HEURISTICS); 1030} 1031 1032/* Decide on the inlining. We do so in the topological order to avoid 1033 expenses on updating data structures. */ 1034 1035bool 1036cgraph_decide_inlining_incrementally (struct cgraph_node *node, bool early) 1037{ 1038 struct cgraph_edge *e; 1039 bool inlined = false; 1040 const char *failed_reason; 1041 1042 /* First of all look for always inline functions. */ 1043 for (e = node->callees; e; e = e->next_callee) 1044 if (e->callee->local.disregard_inline_limits 1045 && e->inline_failed 1046 && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed) 1047 /* ??? It is possible that renaming variable removed the function body 1048 in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */ 1049 && DECL_SAVED_TREE (e->callee->decl)) 1050 { 1051 if (dump_file && early) 1052 { 1053 fprintf (dump_file, " Early inlining %s", 1054 cgraph_node_name (e->callee)); 1055 fprintf (dump_file, " into %s\n", cgraph_node_name (node)); 1056 } 1057 cgraph_mark_inline (e); 1058 inlined = true; 1059 } 1060 1061 /* Now do the automatic inlining. */ 1062 if (!flag_really_no_inline) 1063 for (e = node->callees; e; e = e->next_callee) 1064 if (e->callee->local.inlinable 1065 && e->inline_failed 1066 && !e->callee->local.disregard_inline_limits 1067 && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed) 1068 && (!early 1069 || (cgraph_estimate_size_after_inlining (1, e->caller, e->callee) 1070 <= e->caller->global.insns)) 1071 && cgraph_check_inline_limits (node, e->callee, &e->inline_failed) 1072 && DECL_SAVED_TREE (e->callee->decl)) 1073 { 1074 if (cgraph_default_inline_p (e->callee, &failed_reason)) 1075 { 1076 if (dump_file && early) 1077 { 1078 fprintf (dump_file, " Early inlining %s", 1079 cgraph_node_name (e->callee)); 1080 fprintf (dump_file, " into %s\n", cgraph_node_name (node)); 1081 } 1082 cgraph_mark_inline (e); 1083 inlined = true; 1084 } 1085 else if (!early) 1086 e->inline_failed = failed_reason; 1087 } 1088 if (early && inlined) 1089 { 1090 push_cfun (DECL_STRUCT_FUNCTION (node->decl)); 1091 tree_register_cfg_hooks (); 1092 current_function_decl = node->decl; 1093 optimize_inline_calls (current_function_decl); 1094 node->local.self_insns = node->global.insns; 1095 current_function_decl = NULL; 1096 pop_cfun (); 1097 } 1098 return inlined; 1099} 1100 1101/* When inlining shall be performed. */ 1102static bool 1103cgraph_gate_inlining (void) 1104{ 1105 return flag_inline_trees; 1106} 1107 1108struct tree_opt_pass pass_ipa_inline = 1109{ 1110 "inline", /* name */ 1111 cgraph_gate_inlining, /* gate */ 1112 cgraph_decide_inlining, /* execute */ 1113 NULL, /* sub */ 1114 NULL, /* next */ 1115 0, /* static_pass_number */ 1116 TV_INTEGRATION, /* tv_id */ 1117 0, /* properties_required */ 1118 PROP_cfg, /* properties_provided */ 1119 0, /* properties_destroyed */ 1120 0, /* todo_flags_start */ 1121 TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */ 1122 0 /* letter */ 1123}; 1124 1125/* Do inlining of small functions. Doing so early helps profiling and other 1126 passes to be somewhat more effective and avoids some code duplication in 1127 later real inlining pass for testcases with very many function calls. */ 1128static void 1129cgraph_early_inlining (void) 1130{ 1131 struct cgraph_node *node; 1132 int nnodes; 1133 struct cgraph_node **order = 1134 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); 1135 int i; 1136 1137 if (sorrycount || errorcount) 1138 return; 1139#ifdef ENABLE_CHECKING 1140 for (node = cgraph_nodes; node; node = node->next) 1141 gcc_assert (!node->aux); 1142#endif 1143 1144 nnodes = cgraph_postorder (order); 1145 for (i = nnodes - 1; i >= 0; i--) 1146 { 1147 node = order[i]; 1148 if (node->analyzed && node->local.inlinable 1149 && (node->needed || node->reachable) 1150 && node->callers) 1151 { 1152 if (cgraph_decide_inlining_incrementally (node, true)) 1153 ggc_collect (); 1154 } 1155 } 1156 cgraph_remove_unreachable_nodes (true, dump_file); 1157#ifdef ENABLE_CHECKING 1158 for (node = cgraph_nodes; node; node = node->next) 1159 gcc_assert (!node->global.inlined_to); 1160#endif 1161 free (order); 1162} 1163 1164/* When inlining shall be performed. */ 1165static bool 1166cgraph_gate_early_inlining (void) 1167{ 1168 return flag_inline_trees && flag_early_inlining; 1169} 1170 1171struct tree_opt_pass pass_early_ipa_inline = 1172{ 1173 "einline", /* name */ 1174 cgraph_gate_early_inlining, /* gate */ 1175 cgraph_early_inlining, /* execute */ 1176 NULL, /* sub */ 1177 NULL, /* next */ 1178 0, /* static_pass_number */ 1179 TV_INTEGRATION, /* tv_id */ 1180 0, /* properties_required */ 1181 PROP_cfg, /* properties_provided */ 1182 0, /* properties_destroyed */ 1183 0, /* todo_flags_start */ 1184 TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */ 1185 0 /* letter */ 1186}; 1187