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 if (e->callee->inline_decl) 162 cgraph_redirect_edge_callee (e, cgraph_node (e->callee->inline_decl)); 163 164 gcc_assert (e->inline_failed); 165 e->inline_failed = NULL; 166 167 if (!e->callee->global.inlined && flag_unit_at_a_time) 168 DECL_POSSIBLY_INLINED (e->callee->decl) = true; 169 e->callee->global.inlined = true; 170 171 cgraph_clone_inlined_nodes (e, true, update_original); 172 173 what = e->callee; 174 175 /* Now update size of caller and all functions caller is inlined into. */ 176 for (;e && !e->inline_failed; e = e->caller->callers) 177 { 178 old_insns = e->caller->global.insns; 179 new_insns = cgraph_estimate_size_after_inlining (1, e->caller, 180 what); 181 gcc_assert (new_insns >= 0); 182 to = e->caller; 183 to->global.insns = new_insns; 184 } 185 gcc_assert (what->global.inlined_to == to); 186 if (new_insns > old_insns) 187 overall_insns += new_insns - old_insns; 188 ncalls_inlined++; 189} 190 191/* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER. 192 Return following unredirected edge in the list of callers 193 of EDGE->CALLEE */ 194 195static struct cgraph_edge * 196cgraph_mark_inline (struct cgraph_edge *edge) 197{ 198 struct cgraph_node *to = edge->caller; 199 struct cgraph_node *what = edge->callee; 200 struct cgraph_edge *e, *next; 201 int times = 0; 202 203 /* Look for all calls, mark them inline and clone recursively 204 all inlined functions. */ 205 for (e = what->callers; e; e = next) 206 { 207 next = e->next_caller; 208 if (e->caller == to && e->inline_failed) 209 { 210 cgraph_mark_inline_edge (e, true); 211 if (e == edge) 212 edge = next; 213 times++; 214 } 215 } 216 gcc_assert (times); 217 return edge; 218} 219 220/* Estimate the growth caused by inlining NODE into all callees. */ 221 222static int 223cgraph_estimate_growth (struct cgraph_node *node) 224{ 225 int growth = 0; 226 struct cgraph_edge *e; 227 if (node->global.estimated_growth != INT_MIN) 228 return node->global.estimated_growth; 229 230 for (e = node->callers; e; e = e->next_caller) 231 if (e->inline_failed) 232 growth += (cgraph_estimate_size_after_inlining (1, e->caller, node) 233 - e->caller->global.insns); 234 235 /* ??? Wrong for self recursive functions or cases where we decide to not 236 inline for different reasons, but it is not big deal as in that case 237 we will keep the body around, but we will also avoid some inlining. */ 238 if (!node->needed && !DECL_EXTERNAL (node->decl)) 239 growth -= node->global.insns; 240 241 node->global.estimated_growth = growth; 242 return growth; 243} 244 245/* Return false when inlining WHAT into TO is not good idea 246 as it would cause too large growth of function bodies. 247 When ONE_ONLY is true, assume that only one call site is going 248 to be inlined, otherwise figure out how many call sites in 249 TO calls WHAT and verify that all can be inlined. 250 */ 251 252static bool 253cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what, 254 const char **reason, bool one_only) 255{ 256 int times = 0; 257 struct cgraph_edge *e; 258 int newsize; 259 int limit; 260 261 if (one_only) 262 times = 1; 263 else 264 for (e = to->callees; e; e = e->next_callee) 265 if (e->callee == what) 266 times++; 267 268 if (to->global.inlined_to) 269 to = to->global.inlined_to; 270 271 /* When inlining large function body called once into small function, 272 take the inlined function as base for limiting the growth. */ 273 if (to->local.self_insns > what->local.self_insns) 274 limit = to->local.self_insns; 275 else 276 limit = what->local.self_insns; 277 278 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100; 279 280 /* Check the size after inlining against the function limits. But allow 281 the function to shrink if it went over the limits by forced inlining. */ 282 newsize = cgraph_estimate_size_after_inlining (times, to, what); 283 if (newsize >= to->global.insns 284 && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS) 285 && newsize > limit) 286 { 287 if (reason) 288 *reason = N_("--param large-function-growth limit reached"); 289 return false; 290 } 291 return true; 292} 293 294/* Return true when function N is small enough to be inlined. */ 295 296bool 297cgraph_default_inline_p (struct cgraph_node *n, const char **reason) 298{ 299 tree decl = n->decl; 300 301 if (n->inline_decl) 302 decl = n->inline_decl; 303 if (!DECL_INLINE (decl)) 304 { 305 if (reason) 306 *reason = N_("function not inlinable"); 307 return false; 308 } 309 310 if (!DECL_STRUCT_FUNCTION (decl)->cfg) 311 { 312 if (reason) 313 *reason = N_("function body not available"); 314 return false; 315 } 316 317 if (DECL_DECLARED_INLINE_P (decl)) 318 { 319 if (n->global.insns >= MAX_INLINE_INSNS_SINGLE) 320 { 321 if (reason) 322 *reason = N_("--param max-inline-insns-single limit reached"); 323 return false; 324 } 325 } 326 else 327 { 328 if (n->global.insns >= MAX_INLINE_INSNS_AUTO) 329 { 330 if (reason) 331 *reason = N_("--param max-inline-insns-auto limit reached"); 332 return false; 333 } 334 } 335 336 return true; 337} 338 339/* Return true when inlining WHAT would create recursive inlining. 340 We call recursive inlining all cases where same function appears more than 341 once in the single recursion nest path in the inline graph. */ 342 343static bool 344cgraph_recursive_inlining_p (struct cgraph_node *to, 345 struct cgraph_node *what, 346 const char **reason) 347{ 348 bool recursive; 349 if (to->global.inlined_to) 350 recursive = what->decl == to->global.inlined_to->decl; 351 else 352 recursive = what->decl == to->decl; 353 /* Marking recursive function inline has sane semantic and thus we should 354 not warn on it. */ 355 if (recursive && reason) 356 *reason = (what->local.disregard_inline_limits 357 ? N_("recursive inlining") : ""); 358 return recursive; 359} 360 361/* Return true if the call can be hot. */ 362static bool 363cgraph_maybe_hot_edge_p (struct cgraph_edge *edge) 364{ 365 if (profile_info && flag_branch_probabilities 366 && (edge->count 367 <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION))) 368 return false; 369 return true; 370} 371 372/* A cost model driving the inlining heuristics in a way so the edges with 373 smallest badness are inlined first. After each inlining is performed 374 the costs of all caller edges of nodes affected are recomputed so the 375 metrics may accurately depend on values such as number of inlinable callers 376 of the function or function body size. 377 378 With profiling we use number of executions of each edge to drive the cost. 379 We also should distinguish hot and cold calls where the cold calls are 380 inlined into only when code size is overall improved. 381 */ 382 383static int 384cgraph_edge_badness (struct cgraph_edge *edge) 385{ 386 if (max_count) 387 { 388 int growth = 389 cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee); 390 growth -= edge->caller->global.insns; 391 392 /* Always prefer inlining saving code size. */ 393 if (growth <= 0) 394 return INT_MIN - growth; 395 return ((int)((double)edge->count * INT_MIN / max_count)) / growth; 396 } 397 else 398 { 399 int nest = MIN (edge->loop_nest, 8); 400 int badness = cgraph_estimate_growth (edge->callee) * 256; 401 402 /* Decrease badness if call is nested. */ 403 if (badness > 0) 404 badness >>= nest; 405 else 406 badness <<= nest; 407 408 /* Make recursive inlining happen always after other inlining is done. */ 409 if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL)) 410 return badness + 1; 411 else 412 return badness; 413 } 414} 415 416/* Recompute heap nodes for each of caller edge. */ 417 418static void 419update_caller_keys (fibheap_t heap, struct cgraph_node *node, 420 bitmap updated_nodes) 421{ 422 struct cgraph_edge *edge; 423 const char *failed_reason; 424 425 if (!node->local.inlinable || node->local.disregard_inline_limits 426 || node->global.inlined_to) 427 return; 428 if (bitmap_bit_p (updated_nodes, node->uid)) 429 return; 430 bitmap_set_bit (updated_nodes, node->uid); 431 node->global.estimated_growth = INT_MIN; 432 433 if (!node->local.inlinable) 434 return; 435 /* Prune out edges we won't inline into anymore. */ 436 if (!cgraph_default_inline_p (node, &failed_reason)) 437 { 438 for (edge = node->callers; edge; edge = edge->next_caller) 439 if (edge->aux) 440 { 441 fibheap_delete_node (heap, edge->aux); 442 edge->aux = NULL; 443 if (edge->inline_failed) 444 edge->inline_failed = failed_reason; 445 } 446 return; 447 } 448 449 for (edge = node->callers; edge; edge = edge->next_caller) 450 if (edge->inline_failed) 451 { 452 int badness = cgraph_edge_badness (edge); 453 if (edge->aux) 454 { 455 fibnode_t n = edge->aux; 456 gcc_assert (n->data == edge); 457 if (n->key == badness) 458 continue; 459 460 /* fibheap_replace_key only increase the keys. */ 461 if (fibheap_replace_key (heap, n, badness)) 462 continue; 463 fibheap_delete_node (heap, edge->aux); 464 } 465 edge->aux = fibheap_insert (heap, badness, edge); 466 } 467} 468 469/* Recompute heap nodes for each of caller edges of each of callees. */ 470 471static void 472update_callee_keys (fibheap_t heap, struct cgraph_node *node, 473 bitmap updated_nodes) 474{ 475 struct cgraph_edge *e; 476 node->global.estimated_growth = INT_MIN; 477 478 for (e = node->callees; e; e = e->next_callee) 479 if (e->inline_failed) 480 update_caller_keys (heap, e->callee, updated_nodes); 481 else if (!e->inline_failed) 482 update_callee_keys (heap, e->callee, updated_nodes); 483} 484 485/* Enqueue all recursive calls from NODE into priority queue depending on 486 how likely we want to recursively inline the call. */ 487 488static void 489lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where, 490 fibheap_t heap) 491{ 492 static int priority; 493 struct cgraph_edge *e; 494 for (e = where->callees; e; e = e->next_callee) 495 if (e->callee == node) 496 { 497 /* When profile feedback is available, prioritize by expected number 498 of calls. Without profile feedback we maintain simple queue 499 to order candidates via recursive depths. */ 500 fibheap_insert (heap, 501 !max_count ? priority++ 502 : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))), 503 e); 504 } 505 for (e = where->callees; e; e = e->next_callee) 506 if (!e->inline_failed) 507 lookup_recursive_calls (node, e->callee, heap); 508} 509 510/* Find callgraph nodes closing a circle in the graph. The 511 resulting hashtab can be used to avoid walking the circles. 512 Uses the cgraph nodes ->aux field which needs to be zero 513 before and will be zero after operation. */ 514 515static void 516cgraph_find_cycles (struct cgraph_node *node, htab_t cycles) 517{ 518 struct cgraph_edge *e; 519 520 if (node->aux) 521 { 522 void **slot; 523 slot = htab_find_slot (cycles, node, INSERT); 524 if (!*slot) 525 { 526 if (dump_file) 527 fprintf (dump_file, "Cycle contains %s\n", cgraph_node_name (node)); 528 *slot = node; 529 } 530 return; 531 } 532 533 node->aux = node; 534 for (e = node->callees; e; e = e->next_callee) 535 cgraph_find_cycles (e->callee, cycles); 536 node->aux = 0; 537} 538 539/* Flatten the cgraph node. We have to be careful in recursing 540 as to not run endlessly in circles of the callgraph. 541 We do so by using a hashtab of cycle entering nodes as generated 542 by cgraph_find_cycles. */ 543 544static void 545cgraph_flatten_node (struct cgraph_node *node, htab_t cycles) 546{ 547 struct cgraph_edge *e; 548 549 for (e = node->callees; e; e = e->next_callee) 550 { 551 /* Inline call, if possible, and recurse. Be sure we are not 552 entering callgraph circles here. */ 553 if (e->inline_failed 554 && e->callee->local.inlinable 555 && !cgraph_recursive_inlining_p (node, e->callee, 556 &e->inline_failed) 557 && !htab_find (cycles, e->callee)) 558 { 559 if (dump_file) 560 fprintf (dump_file, " inlining %s", cgraph_node_name (e->callee)); 561 cgraph_mark_inline_edge (e, true); 562 cgraph_flatten_node (e->callee, cycles); 563 } 564 else if (dump_file) 565 fprintf (dump_file, " !inlining %s", cgraph_node_name (e->callee)); 566 } 567} 568 569/* Decide on recursive inlining: in the case function has recursive calls, 570 inline until body size reaches given argument. */ 571 572static bool 573cgraph_decide_recursive_inlining (struct cgraph_node *node) 574{ 575 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO); 576 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO); 577 int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY); 578 fibheap_t heap; 579 struct cgraph_edge *e; 580 struct cgraph_node *master_clone, *next; 581 int depth = 0; 582 int n = 0; 583 584 if (DECL_DECLARED_INLINE_P (node->decl)) 585 { 586 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE); 587 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH); 588 } 589 590 /* Make sure that function is small enough to be considered for inlining. */ 591 if (!max_depth 592 || cgraph_estimate_size_after_inlining (1, node, node) >= limit) 593 return false; 594 heap = fibheap_new (); 595 lookup_recursive_calls (node, node, heap); 596 if (fibheap_empty (heap)) 597 { 598 fibheap_delete (heap); 599 return false; 600 } 601 602 if (dump_file) 603 fprintf (dump_file, 604 " Performing recursive inlining on %s\n", 605 cgraph_node_name (node)); 606 607 /* We need original clone to copy around. */ 608 master_clone = cgraph_clone_node (node, node->count, 1, false); 609 master_clone->needed = true; 610 for (e = master_clone->callees; e; e = e->next_callee) 611 if (!e->inline_failed) 612 cgraph_clone_inlined_nodes (e, true, false); 613 614 /* Do the inlining and update list of recursive call during process. */ 615 while (!fibheap_empty (heap) 616 && (cgraph_estimate_size_after_inlining (1, node, master_clone) 617 <= limit)) 618 { 619 struct cgraph_edge *curr = fibheap_extract_min (heap); 620 struct cgraph_node *cnode; 621 622 depth = 1; 623 for (cnode = curr->caller; 624 cnode->global.inlined_to; cnode = cnode->callers->caller) 625 if (node->decl == curr->callee->decl) 626 depth++; 627 if (depth > max_depth) 628 { 629 if (dump_file) 630 fprintf (dump_file, 631 " maxmal depth reached\n"); 632 continue; 633 } 634 635 if (max_count) 636 { 637 if (!cgraph_maybe_hot_edge_p (curr)) 638 { 639 if (dump_file) 640 fprintf (dump_file, " Not inlining cold call\n"); 641 continue; 642 } 643 if (curr->count * 100 / node->count < probability) 644 { 645 if (dump_file) 646 fprintf (dump_file, 647 " Probability of edge is too small\n"); 648 continue; 649 } 650 } 651 652 if (dump_file) 653 { 654 fprintf (dump_file, 655 " Inlining call of depth %i", depth); 656 if (node->count) 657 { 658 fprintf (dump_file, " called approx. %.2f times per call", 659 (double)curr->count / node->count); 660 } 661 fprintf (dump_file, "\n"); 662 } 663 cgraph_redirect_edge_callee (curr, master_clone); 664 cgraph_mark_inline_edge (curr, false); 665 lookup_recursive_calls (node, curr->callee, heap); 666 n++; 667 } 668 if (!fibheap_empty (heap) && dump_file) 669 fprintf (dump_file, " Recursive inlining growth limit met.\n"); 670 671 fibheap_delete (heap); 672 if (dump_file) 673 fprintf (dump_file, 674 "\n Inlined %i times, body grown from %i to %i insns\n", n, 675 master_clone->global.insns, node->global.insns); 676 677 /* Remove master clone we used for inlining. We rely that clones inlined 678 into master clone gets queued just before master clone so we don't 679 need recursion. */ 680 for (node = cgraph_nodes; node != master_clone; 681 node = next) 682 { 683 next = node->next; 684 if (node->global.inlined_to == master_clone) 685 cgraph_remove_node (node); 686 } 687 cgraph_remove_node (master_clone); 688 /* FIXME: Recursive inlining actually reduces number of calls of the 689 function. At this place we should probably walk the function and 690 inline clones and compensate the counts accordingly. This probably 691 doesn't matter much in practice. */ 692 return n > 0; 693} 694 695/* Set inline_failed for all callers of given function to REASON. */ 696 697static void 698cgraph_set_inline_failed (struct cgraph_node *node, const char *reason) 699{ 700 struct cgraph_edge *e; 701 702 if (dump_file) 703 fprintf (dump_file, "Inlining failed: %s\n", reason); 704 for (e = node->callers; e; e = e->next_caller) 705 if (e->inline_failed) 706 e->inline_failed = reason; 707} 708 709/* We use greedy algorithm for inlining of small functions: 710 All inline candidates are put into prioritized heap based on estimated 711 growth of the overall number of instructions and then update the estimates. 712 713 INLINED and INLINED_CALEES are just pointers to arrays large enough 714 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */ 715 716static void 717cgraph_decide_inlining_of_small_functions (void) 718{ 719 struct cgraph_node *node; 720 struct cgraph_edge *edge; 721 const char *failed_reason; 722 fibheap_t heap = fibheap_new (); 723 bitmap updated_nodes = BITMAP_ALLOC (NULL); 724 725 if (dump_file) 726 fprintf (dump_file, "\nDeciding on smaller functions:\n"); 727 728 /* Put all inline candidates into the heap. */ 729 730 for (node = cgraph_nodes; node; node = node->next) 731 { 732 if (!node->local.inlinable || !node->callers 733 || node->local.disregard_inline_limits) 734 continue; 735 if (dump_file) 736 fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node)); 737 738 node->global.estimated_growth = INT_MIN; 739 if (!cgraph_default_inline_p (node, &failed_reason)) 740 { 741 cgraph_set_inline_failed (node, failed_reason); 742 continue; 743 } 744 745 for (edge = node->callers; edge; edge = edge->next_caller) 746 if (edge->inline_failed) 747 { 748 gcc_assert (!edge->aux); 749 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge); 750 } 751 } 752 while (overall_insns <= max_insns && (edge = fibheap_extract_min (heap))) 753 { 754 int old_insns = overall_insns; 755 struct cgraph_node *where; 756 int growth = 757 cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee); 758 759 growth -= edge->caller->global.insns; 760 761 if (dump_file) 762 { 763 fprintf (dump_file, 764 "\nConsidering %s with %i insns\n", 765 cgraph_node_name (edge->callee), 766 edge->callee->global.insns); 767 fprintf (dump_file, 768 " to be inlined into %s\n" 769 " Estimated growth after inlined into all callees is %+i insns.\n" 770 " Estimated badness is %i.\n", 771 cgraph_node_name (edge->caller), 772 cgraph_estimate_growth (edge->callee), 773 cgraph_edge_badness (edge)); 774 if (edge->count) 775 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count); 776 } 777 gcc_assert (edge->aux); 778 edge->aux = NULL; 779 if (!edge->inline_failed) 780 continue; 781 782 /* When not having profile info ready we don't weight by any way the 783 position of call in procedure itself. This means if call of 784 function A from function B seems profitable to inline, the recursive 785 call of function A in inline copy of A in B will look profitable too 786 and we end up inlining until reaching maximal function growth. This 787 is not good idea so prohibit the recursive inlining. 788 789 ??? When the frequencies are taken into account we might not need this 790 restriction. */ 791 if (!max_count) 792 { 793 where = edge->caller; 794 while (where->global.inlined_to) 795 { 796 if (where->decl == edge->callee->decl) 797 break; 798 where = where->callers->caller; 799 } 800 if (where->global.inlined_to) 801 { 802 edge->inline_failed 803 = (edge->callee->local.disregard_inline_limits ? N_("recursive inlining") : ""); 804 if (dump_file) 805 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n"); 806 continue; 807 } 808 } 809 810 if (!cgraph_maybe_hot_edge_p (edge) && growth > 0) 811 { 812 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee, 813 &edge->inline_failed)) 814 { 815 edge->inline_failed = 816 N_("call is unlikely"); 817 if (dump_file) 818 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed); 819 } 820 continue; 821 } 822 if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed)) 823 { 824 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee, 825 &edge->inline_failed)) 826 { 827 if (dump_file) 828 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed); 829 } 830 continue; 831 } 832 if (cgraph_recursive_inlining_p (edge->caller, edge->callee, 833 &edge->inline_failed)) 834 { 835 where = edge->caller; 836 if (where->global.inlined_to) 837 where = where->global.inlined_to; 838 if (!cgraph_decide_recursive_inlining (where)) 839 continue; 840 update_callee_keys (heap, where, updated_nodes); 841 } 842 else 843 { 844 struct cgraph_node *callee; 845 if (!cgraph_check_inline_limits (edge->caller, edge->callee, 846 &edge->inline_failed, true)) 847 { 848 if (dump_file) 849 fprintf (dump_file, " Not inlining into %s:%s.\n", 850 cgraph_node_name (edge->caller), edge->inline_failed); 851 continue; 852 } 853 callee = edge->callee; 854 cgraph_mark_inline_edge (edge, true); 855 update_callee_keys (heap, callee, updated_nodes); 856 } 857 where = edge->caller; 858 if (where->global.inlined_to) 859 where = where->global.inlined_to; 860 861 /* Our profitability metric can depend on local properties 862 such as number of inlinable calls and size of the function body. 863 After inlining these properties might change for the function we 864 inlined into (since it's body size changed) and for the functions 865 called by function we inlined (since number of it inlinable callers 866 might change). */ 867 update_caller_keys (heap, where, updated_nodes); 868 bitmap_clear (updated_nodes); 869 870 if (dump_file) 871 { 872 fprintf (dump_file, 873 " Inlined into %s which now has %i insns," 874 "net change of %+i insns.\n", 875 cgraph_node_name (edge->caller), 876 edge->caller->global.insns, 877 overall_insns - old_insns); 878 } 879 } 880 while ((edge = fibheap_extract_min (heap)) != NULL) 881 { 882 gcc_assert (edge->aux); 883 edge->aux = NULL; 884 if (!edge->callee->local.disregard_inline_limits && edge->inline_failed 885 && !cgraph_recursive_inlining_p (edge->caller, edge->callee, 886 &edge->inline_failed)) 887 edge->inline_failed = N_("--param inline-unit-growth limit reached"); 888 } 889 fibheap_delete (heap); 890 BITMAP_FREE (updated_nodes); 891} 892 893/* Decide on the inlining. We do so in the topological order to avoid 894 expenses on updating data structures. */ 895 896static unsigned int 897cgraph_decide_inlining (void) 898{ 899 struct cgraph_node *node; 900 int nnodes; 901 struct cgraph_node **order = 902 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); 903 int old_insns = 0; 904 int i; 905 906 timevar_push (TV_INLINE_HEURISTICS); 907 max_count = 0; 908 for (node = cgraph_nodes; node; node = node->next) 909 if (node->analyzed && (node->needed || node->reachable)) 910 { 911 struct cgraph_edge *e; 912 913 /* At the moment, no IPA passes change function bodies before inlining. 914 Save some time by not recomputing function body sizes if early inlining 915 already did so. */ 916 if (!flag_early_inlining) 917 node->local.self_insns = node->global.insns 918 = estimate_num_insns (node->decl); 919 920 initial_insns += node->local.self_insns; 921 gcc_assert (node->local.self_insns == node->global.insns); 922 for (e = node->callees; e; e = e->next_callee) 923 if (max_count < e->count) 924 max_count = e->count; 925 } 926 overall_insns = initial_insns; 927 gcc_assert (!max_count || (profile_info && flag_branch_probabilities)); 928 929 max_insns = overall_insns; 930 if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS)) 931 max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS); 932 933 max_insns = ((HOST_WIDEST_INT) max_insns 934 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100); 935 936 nnodes = cgraph_postorder (order); 937 938 if (dump_file) 939 fprintf (dump_file, 940 "\nDeciding on inlining. Starting with %i insns.\n", 941 initial_insns); 942 943 for (node = cgraph_nodes; node; node = node->next) 944 node->aux = 0; 945 946 if (dump_file) 947 fprintf (dump_file, "\nInlining always_inline functions:\n"); 948 949 /* In the first pass mark all always_inline edges. Do this with a priority 950 so none of our later choices will make this impossible. */ 951 for (i = nnodes - 1; i >= 0; i--) 952 { 953 struct cgraph_edge *e, *next; 954 955 node = order[i]; 956 957 /* Handle nodes to be flattened, but don't update overall unit size. */ 958 if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL) 959 { 960 int old_overall_insns = overall_insns; 961 htab_t cycles; 962 if (dump_file) 963 fprintf (dump_file, 964 "Flattening %s\n", cgraph_node_name (node)); 965 cycles = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL); 966 cgraph_find_cycles (node, cycles); 967 cgraph_flatten_node (node, cycles); 968 htab_delete (cycles); 969 overall_insns = old_overall_insns; 970 /* We don't need to consider always_inline functions inside the flattened 971 function anymore. */ 972 continue; 973 } 974 975 if (!node->local.disregard_inline_limits) 976 continue; 977 if (dump_file) 978 fprintf (dump_file, 979 "\nConsidering %s %i insns (always inline)\n", 980 cgraph_node_name (node), node->global.insns); 981 old_insns = overall_insns; 982 for (e = node->callers; e; e = next) 983 { 984 next = e->next_caller; 985 if (!e->inline_failed) 986 continue; 987 if (cgraph_recursive_inlining_p (e->caller, e->callee, 988 &e->inline_failed)) 989 continue; 990 cgraph_mark_inline_edge (e, true); 991 if (dump_file) 992 fprintf (dump_file, 993 " Inlined into %s which now has %i insns.\n", 994 cgraph_node_name (e->caller), 995 e->caller->global.insns); 996 } 997 if (dump_file) 998 fprintf (dump_file, 999 " Inlined for a net change of %+i insns.\n", 1000 overall_insns - old_insns); 1001 } 1002 1003 if (!flag_really_no_inline) 1004 cgraph_decide_inlining_of_small_functions (); 1005 1006 if (!flag_really_no_inline 1007 && flag_inline_functions_called_once) 1008 { 1009 if (dump_file) 1010 fprintf (dump_file, "\nDeciding on functions called once:\n"); 1011 1012 /* And finally decide what functions are called once. */ 1013 1014 for (i = nnodes - 1; i >= 0; i--) 1015 { 1016 node = order[i]; 1017 1018 if (node->callers && !node->callers->next_caller && !node->needed 1019 && node->local.inlinable && node->callers->inline_failed 1020 && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl)) 1021 { 1022 bool ok = true; 1023 struct cgraph_node *node1; 1024 1025 /* Verify that we won't duplicate the caller. */ 1026 for (node1 = node->callers->caller; 1027 node1->callers && !node1->callers->inline_failed 1028 && ok; node1 = node1->callers->caller) 1029 if (node1->callers->next_caller || node1->needed) 1030 ok = false; 1031 if (ok) 1032 { 1033 if (dump_file) 1034 { 1035 fprintf (dump_file, 1036 "\nConsidering %s %i insns.\n", 1037 cgraph_node_name (node), node->global.insns); 1038 fprintf (dump_file, 1039 " Called once from %s %i insns.\n", 1040 cgraph_node_name (node->callers->caller), 1041 node->callers->caller->global.insns); 1042 } 1043 1044 old_insns = overall_insns; 1045 1046 if (cgraph_check_inline_limits (node->callers->caller, node, 1047 NULL, false)) 1048 { 1049 cgraph_mark_inline (node->callers); 1050 if (dump_file) 1051 fprintf (dump_file, 1052 " Inlined into %s which now has %i insns" 1053 " for a net change of %+i insns.\n", 1054 cgraph_node_name (node->callers->caller), 1055 node->callers->caller->global.insns, 1056 overall_insns - old_insns); 1057 } 1058 else 1059 { 1060 if (dump_file) 1061 fprintf (dump_file, 1062 " Inline limit reached, not inlined.\n"); 1063 } 1064 } 1065 } 1066 } 1067 } 1068 1069 if (dump_file) 1070 fprintf (dump_file, 1071 "\nInlined %i calls, eliminated %i functions, " 1072 "%i insns turned to %i insns.\n\n", 1073 ncalls_inlined, nfunctions_inlined, initial_insns, 1074 overall_insns); 1075 free (order); 1076 timevar_pop (TV_INLINE_HEURISTICS); 1077 return 0; 1078} 1079 1080/* Decide on the inlining. We do so in the topological order to avoid 1081 expenses on updating data structures. */ 1082 1083bool 1084cgraph_decide_inlining_incrementally (struct cgraph_node *node, bool early) 1085{ 1086 struct cgraph_edge *e; 1087 bool inlined = false; 1088 const char *failed_reason; 1089 1090 /* First of all look for always inline functions. */ 1091 for (e = node->callees; e; e = e->next_callee) 1092 if (e->callee->local.disregard_inline_limits 1093 && e->inline_failed 1094 && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed) 1095 /* ??? It is possible that renaming variable removed the function body 1096 in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */ 1097 && (DECL_SAVED_TREE (e->callee->decl) || e->callee->inline_decl)) 1098 { 1099 if (dump_file && early) 1100 { 1101 fprintf (dump_file, " Early inlining %s", 1102 cgraph_node_name (e->callee)); 1103 fprintf (dump_file, " into %s\n", cgraph_node_name (node)); 1104 } 1105 cgraph_mark_inline (e); 1106 inlined = true; 1107 } 1108 1109 /* Now do the automatic inlining. */ 1110 if (!flag_really_no_inline) 1111 for (e = node->callees; e; e = e->next_callee) 1112 if (e->callee->local.inlinable 1113 && e->inline_failed 1114 && !e->callee->local.disregard_inline_limits 1115 && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed) 1116 && (!early 1117 || (cgraph_estimate_size_after_inlining (1, e->caller, e->callee) 1118 <= e->caller->global.insns)) 1119 && cgraph_check_inline_limits (node, e->callee, &e->inline_failed, 1120 false) 1121 && (DECL_SAVED_TREE (e->callee->decl) || e->callee->inline_decl)) 1122 { 1123 if (cgraph_default_inline_p (e->callee, &failed_reason)) 1124 { 1125 if (dump_file && early) 1126 { 1127 fprintf (dump_file, " Early inlining %s", 1128 cgraph_node_name (e->callee)); 1129 fprintf (dump_file, " into %s\n", cgraph_node_name (node)); 1130 } 1131 cgraph_mark_inline (e); 1132 inlined = true; 1133 } 1134 else if (!early) 1135 e->inline_failed = failed_reason; 1136 } 1137 if (early && inlined) 1138 { 1139 push_cfun (DECL_STRUCT_FUNCTION (node->decl)); 1140 tree_register_cfg_hooks (); 1141 current_function_decl = node->decl; 1142 optimize_inline_calls (current_function_decl); 1143 node->local.self_insns = node->global.insns; 1144 current_function_decl = NULL; 1145 pop_cfun (); 1146 } 1147 return inlined; 1148} 1149 1150/* When inlining shall be performed. */ 1151static bool 1152cgraph_gate_inlining (void) 1153{ 1154 return flag_inline_trees; 1155} 1156 1157struct tree_opt_pass pass_ipa_inline = 1158{ 1159 "inline", /* name */ 1160 cgraph_gate_inlining, /* gate */ 1161 cgraph_decide_inlining, /* execute */ 1162 NULL, /* sub */ 1163 NULL, /* next */ 1164 0, /* static_pass_number */ 1165 TV_INTEGRATION, /* tv_id */ 1166 0, /* properties_required */ 1167 PROP_cfg, /* properties_provided */ 1168 0, /* properties_destroyed */ 1169 0, /* todo_flags_start */ 1170 TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */ 1171 0 /* letter */ 1172}; 1173 1174/* Because inlining might remove no-longer reachable nodes, we need to 1175 keep the array visible to garbage collector to avoid reading collected 1176 out nodes. */ 1177static int nnodes; 1178static GTY ((length ("nnodes"))) struct cgraph_node **order; 1179 1180/* Do inlining of small functions. Doing so early helps profiling and other 1181 passes to be somewhat more effective and avoids some code duplication in 1182 later real inlining pass for testcases with very many function calls. */ 1183static unsigned int 1184cgraph_early_inlining (void) 1185{ 1186 struct cgraph_node *node; 1187 int i; 1188 1189 if (sorrycount || errorcount) 1190 return 0; 1191#ifdef ENABLE_CHECKING 1192 for (node = cgraph_nodes; node; node = node->next) 1193 gcc_assert (!node->aux); 1194#endif 1195 1196 order = ggc_alloc (sizeof (*order) * cgraph_n_nodes); 1197 nnodes = cgraph_postorder (order); 1198 for (i = nnodes - 1; i >= 0; i--) 1199 { 1200 node = order[i]; 1201 if (node->analyzed && (node->needed || node->reachable)) 1202 node->local.self_insns = node->global.insns 1203 = estimate_num_insns (node->decl); 1204 } 1205 for (i = nnodes - 1; i >= 0; i--) 1206 { 1207 node = order[i]; 1208 if (node->analyzed && node->local.inlinable 1209 && (node->needed || node->reachable) 1210 && node->callers) 1211 { 1212 if (cgraph_decide_inlining_incrementally (node, true)) 1213 ggc_collect (); 1214 } 1215 } 1216 cgraph_remove_unreachable_nodes (true, dump_file); 1217#ifdef ENABLE_CHECKING 1218 for (node = cgraph_nodes; node; node = node->next) 1219 gcc_assert (!node->global.inlined_to); 1220#endif 1221 ggc_free (order); 1222 order = NULL; 1223 nnodes = 0; 1224 return 0; 1225} 1226 1227/* When inlining shall be performed. */ 1228static bool 1229cgraph_gate_early_inlining (void) 1230{ 1231 return flag_inline_trees && flag_early_inlining; 1232} 1233 1234struct tree_opt_pass pass_early_ipa_inline = 1235{ 1236 "einline", /* name */ 1237 cgraph_gate_early_inlining, /* gate */ 1238 cgraph_early_inlining, /* execute */ 1239 NULL, /* sub */ 1240 NULL, /* next */ 1241 0, /* static_pass_number */ 1242 TV_INTEGRATION, /* tv_id */ 1243 0, /* properties_required */ 1244 PROP_cfg, /* properties_provided */ 1245 0, /* properties_destroyed */ 1246 0, /* todo_flags_start */ 1247 TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */ 1248 0 /* letter */ 1249}; 1250 1251#include "gt-ipa-inline.h" 1252