1 /* Inlining decision heuristics. 2 Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010, 2011 3 Free Software Foundation, Inc. 4 Contributed by Jan Hubicka 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free 10 Software Foundation; either version 3, or (at your option) any later 11 version. 12 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16 for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 /* Inlining decision heuristics 23 24 The implementation of inliner is organized as follows: 25 26 inlining heuristics limits 27 28 can_inline_edge_p allow to check that particular inlining is allowed 29 by the limits specified by user (allowed function growth, growth and so 30 on). 31 32 Functions are inlined when it is obvious the result is profitable (such 33 as functions called once or when inlining reduce code size). 34 In addition to that we perform inlining of small functions and recursive 35 inlining. 36 37 inlining heuristics 38 39 The inliner itself is split into two passes: 40 41 pass_early_inlining 42 43 Simple local inlining pass inlining callees into current function. 44 This pass makes no use of whole unit analysis and thus it can do only 45 very simple decisions based on local properties. 46 47 The strength of the pass is that it is run in topological order 48 (reverse postorder) on the callgraph. Functions are converted into SSA 49 form just before this pass and optimized subsequently. As a result, the 50 callees of the function seen by the early inliner was already optimized 51 and results of early inlining adds a lot of optimization opportunities 52 for the local optimization. 53 54 The pass handle the obvious inlining decisions within the compilation 55 unit - inlining auto inline functions, inlining for size and 56 flattening. 57 58 main strength of the pass is the ability to eliminate abstraction 59 penalty in C++ code (via combination of inlining and early 60 optimization) and thus improve quality of analysis done by real IPA 61 optimizers. 62 63 Because of lack of whole unit knowledge, the pass can not really make 64 good code size/performance tradeoffs. It however does very simple 65 speculative inlining allowing code size to grow by 66 EARLY_INLINING_INSNS when callee is leaf function. In this case the 67 optimizations performed later are very likely to eliminate the cost. 68 69 pass_ipa_inline 70 71 This is the real inliner able to handle inlining with whole program 72 knowledge. It performs following steps: 73 74 1) inlining of small functions. This is implemented by greedy 75 algorithm ordering all inlinable cgraph edges by their badness and 76 inlining them in this order as long as inline limits allows doing so. 77 78 This heuristics is not very good on inlining recursive calls. Recursive 79 calls can be inlined with results similar to loop unrolling. To do so, 80 special purpose recursive inliner is executed on function when 81 recursive edge is met as viable candidate. 82 83 2) Unreachable functions are removed from callgraph. Inlining leads 84 to devirtualization and other modification of callgraph so functions 85 may become unreachable during the process. Also functions declared as 86 extern inline or virtual functions are removed, since after inlining 87 we no longer need the offline bodies. 88 89 3) Functions called once and not exported from the unit are inlined. 90 This should almost always lead to reduction of code size by eliminating 91 the need for offline copy of the function. */ 92 93 #include "config.h" 94 #include "system.h" 95 #include "coretypes.h" 96 #include "tm.h" 97 #include "tree.h" 98 #include "tree-inline.h" 99 #include "langhooks.h" 100 #include "flags.h" 101 #include "cgraph.h" 102 #include "diagnostic.h" 103 #include "gimple-pretty-print.h" 104 #include "timevar.h" 105 #include "params.h" 106 #include "fibheap.h" 107 #include "intl.h" 108 #include "tree-pass.h" 109 #include "coverage.h" 110 #include "ggc.h" 111 #include "rtl.h" 112 #include "tree-flow.h" 113 #include "ipa-prop.h" 114 #include "except.h" 115 #include "target.h" 116 #include "ipa-inline.h" 117 #include "ipa-utils.h" 118 119 /* Statistics we collect about inlining algorithm. */ 120 static int overall_size; 121 static gcov_type max_count; 122 123 /* Return false when inlining edge E would lead to violating 124 limits on function unit growth or stack usage growth. 125 126 The relative function body growth limit is present generally 127 to avoid problems with non-linear behavior of the compiler. 128 To allow inlining huge functions into tiny wrapper, the limit 129 is always based on the bigger of the two functions considered. 130 131 For stack growth limits we always base the growth in stack usage 132 of the callers. We want to prevent applications from segfaulting 133 on stack overflow when functions with huge stack frames gets 134 inlined. */ 135 136 static bool 137 caller_growth_limits (struct cgraph_edge *e) 138 { 139 struct cgraph_node *to = e->caller; 140 struct cgraph_node *what = cgraph_function_or_thunk_node (e->callee, NULL); 141 int newsize; 142 int limit = 0; 143 HOST_WIDE_INT stack_size_limit = 0, inlined_stack; 144 struct inline_summary *info, *what_info, *outer_info = inline_summary (to); 145 146 /* Look for function e->caller is inlined to. While doing 147 so work out the largest function body on the way. As 148 described above, we want to base our function growth 149 limits based on that. Not on the self size of the 150 outer function, not on the self size of inline code 151 we immediately inline to. This is the most relaxed 152 interpretation of the rule "do not grow large functions 153 too much in order to prevent compiler from exploding". */ 154 while (true) 155 { 156 info = inline_summary (to); 157 if (limit < info->self_size) 158 limit = info->self_size; 159 if (stack_size_limit < info->estimated_self_stack_size) 160 stack_size_limit = info->estimated_self_stack_size; 161 if (to->global.inlined_to) 162 to = to->callers->caller; 163 else 164 break; 165 } 166 167 what_info = inline_summary (what); 168 169 if (limit < what_info->self_size) 170 limit = what_info->self_size; 171 172 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100; 173 174 /* Check the size after inlining against the function limits. But allow 175 the function to shrink if it went over the limits by forced inlining. */ 176 newsize = estimate_size_after_inlining (to, e); 177 if (newsize >= info->size 178 && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS) 179 && newsize > limit) 180 { 181 e->inline_failed = CIF_LARGE_FUNCTION_GROWTH_LIMIT; 182 return false; 183 } 184 185 if (!what_info->estimated_stack_size) 186 return true; 187 188 /* FIXME: Stack size limit often prevents inlining in Fortran programs 189 due to large i/o datastructures used by the Fortran front-end. 190 We ought to ignore this limit when we know that the edge is executed 191 on every invocation of the caller (i.e. its call statement dominates 192 exit block). We do not track this information, yet. */ 193 stack_size_limit += ((gcov_type)stack_size_limit 194 * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100); 195 196 inlined_stack = (outer_info->stack_frame_offset 197 + outer_info->estimated_self_stack_size 198 + what_info->estimated_stack_size); 199 /* Check new stack consumption with stack consumption at the place 200 stack is used. */ 201 if (inlined_stack > stack_size_limit 202 /* If function already has large stack usage from sibling 203 inline call, we can inline, too. 204 This bit overoptimistically assume that we are good at stack 205 packing. */ 206 && inlined_stack > info->estimated_stack_size 207 && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME)) 208 { 209 e->inline_failed = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT; 210 return false; 211 } 212 return true; 213 } 214 215 /* Dump info about why inlining has failed. */ 216 217 static void 218 report_inline_failed_reason (struct cgraph_edge *e) 219 { 220 if (dump_file) 221 { 222 fprintf (dump_file, " not inlinable: %s/%i -> %s/%i, %s\n", 223 xstrdup (cgraph_node_name (e->caller)), e->caller->uid, 224 xstrdup (cgraph_node_name (e->callee)), e->callee->uid, 225 cgraph_inline_failed_string (e->inline_failed)); 226 } 227 } 228 229 /* Decide if we can inline the edge and possibly update 230 inline_failed reason. 231 We check whether inlining is possible at all and whether 232 caller growth limits allow doing so. 233 234 if REPORT is true, output reason to the dump file. */ 235 236 static bool 237 can_inline_edge_p (struct cgraph_edge *e, bool report) 238 { 239 bool inlinable = true; 240 enum availability avail; 241 struct cgraph_node *callee 242 = cgraph_function_or_thunk_node (e->callee, &avail); 243 tree caller_tree = DECL_FUNCTION_SPECIFIC_OPTIMIZATION (e->caller->decl); 244 tree callee_tree 245 = callee ? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee->decl) : NULL; 246 struct function *caller_cfun = DECL_STRUCT_FUNCTION (e->caller->decl); 247 struct function *callee_cfun 248 = callee ? DECL_STRUCT_FUNCTION (callee->decl) : NULL; 249 250 if (!caller_cfun && e->caller->clone_of) 251 caller_cfun = DECL_STRUCT_FUNCTION (e->caller->clone_of->decl); 252 253 if (!callee_cfun && callee && callee->clone_of) 254 callee_cfun = DECL_STRUCT_FUNCTION (callee->clone_of->decl); 255 256 gcc_assert (e->inline_failed); 257 258 if (!callee || !callee->analyzed) 259 { 260 e->inline_failed = CIF_BODY_NOT_AVAILABLE; 261 inlinable = false; 262 } 263 else if (!inline_summary (callee)->inlinable) 264 { 265 e->inline_failed = CIF_FUNCTION_NOT_INLINABLE; 266 inlinable = false; 267 } 268 else if (avail <= AVAIL_OVERWRITABLE) 269 { 270 e->inline_failed = CIF_OVERWRITABLE; 271 return false; 272 } 273 else if (e->call_stmt_cannot_inline_p) 274 { 275 e->inline_failed = CIF_MISMATCHED_ARGUMENTS; 276 inlinable = false; 277 } 278 /* Don't inline if the functions have different EH personalities. */ 279 else if (DECL_FUNCTION_PERSONALITY (e->caller->decl) 280 && DECL_FUNCTION_PERSONALITY (callee->decl) 281 && (DECL_FUNCTION_PERSONALITY (e->caller->decl) 282 != DECL_FUNCTION_PERSONALITY (callee->decl))) 283 { 284 e->inline_failed = CIF_EH_PERSONALITY; 285 inlinable = false; 286 } 287 /* TM pure functions should not be inlined into non-TM_pure 288 functions. */ 289 else if (is_tm_pure (callee->decl) 290 && !is_tm_pure (e->caller->decl)) 291 { 292 e->inline_failed = CIF_UNSPECIFIED; 293 inlinable = false; 294 } 295 /* Don't inline if the callee can throw non-call exceptions but the 296 caller cannot. 297 FIXME: this is obviously wrong for LTO where STRUCT_FUNCTION is missing. 298 Move the flag into cgraph node or mirror it in the inline summary. */ 299 else if (callee_cfun && callee_cfun->can_throw_non_call_exceptions 300 && !(caller_cfun && caller_cfun->can_throw_non_call_exceptions)) 301 { 302 e->inline_failed = CIF_NON_CALL_EXCEPTIONS; 303 inlinable = false; 304 } 305 /* Check compatibility of target optimization options. */ 306 else if (!targetm.target_option.can_inline_p (e->caller->decl, 307 callee->decl)) 308 { 309 e->inline_failed = CIF_TARGET_OPTION_MISMATCH; 310 inlinable = false; 311 } 312 /* Check if caller growth allows the inlining. */ 313 else if (!DECL_DISREGARD_INLINE_LIMITS (callee->decl) 314 && !lookup_attribute ("flatten", 315 DECL_ATTRIBUTES 316 (e->caller->global.inlined_to 317 ? e->caller->global.inlined_to->decl 318 : e->caller->decl)) 319 && !caller_growth_limits (e)) 320 inlinable = false; 321 /* Don't inline a function with a higher optimization level than the 322 caller. FIXME: this is really just tip of iceberg of handling 323 optimization attribute. */ 324 else if (caller_tree != callee_tree) 325 { 326 struct cl_optimization *caller_opt 327 = TREE_OPTIMIZATION ((caller_tree) 328 ? caller_tree 329 : optimization_default_node); 330 331 struct cl_optimization *callee_opt 332 = TREE_OPTIMIZATION ((callee_tree) 333 ? callee_tree 334 : optimization_default_node); 335 336 if (((caller_opt->x_optimize > callee_opt->x_optimize) 337 || (caller_opt->x_optimize_size != callee_opt->x_optimize_size)) 338 /* gcc.dg/pr43564.c. Look at forced inline even in -O0. */ 339 && !DECL_DISREGARD_INLINE_LIMITS (e->callee->decl)) 340 { 341 e->inline_failed = CIF_OPTIMIZATION_MISMATCH; 342 inlinable = false; 343 } 344 } 345 346 if (!inlinable && report) 347 report_inline_failed_reason (e); 348 return inlinable; 349 } 350 351 352 /* Return true if the edge E is inlinable during early inlining. */ 353 354 static bool 355 can_early_inline_edge_p (struct cgraph_edge *e) 356 { 357 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, 358 NULL); 359 /* Early inliner might get called at WPA stage when IPA pass adds new 360 function. In this case we can not really do any of early inlining 361 because function bodies are missing. */ 362 if (!gimple_has_body_p (callee->decl)) 363 { 364 e->inline_failed = CIF_BODY_NOT_AVAILABLE; 365 return false; 366 } 367 /* In early inliner some of callees may not be in SSA form yet 368 (i.e. the callgraph is cyclic and we did not process 369 the callee by early inliner, yet). We don't have CIF code for this 370 case; later we will re-do the decision in the real inliner. */ 371 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->caller->decl)) 372 || !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl))) 373 { 374 if (dump_file) 375 fprintf (dump_file, " edge not inlinable: not in SSA form\n"); 376 return false; 377 } 378 if (!can_inline_edge_p (e, true)) 379 return false; 380 return true; 381 } 382 383 384 /* Return true when N is leaf function. Accept cheap builtins 385 in leaf functions. */ 386 387 static bool 388 leaf_node_p (struct cgraph_node *n) 389 { 390 struct cgraph_edge *e; 391 for (e = n->callees; e; e = e->next_callee) 392 if (!is_inexpensive_builtin (e->callee->decl)) 393 return false; 394 return true; 395 } 396 397 398 /* Return true if we are interested in inlining small function. */ 399 400 static bool 401 want_early_inline_function_p (struct cgraph_edge *e) 402 { 403 bool want_inline = true; 404 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL); 405 406 if (DECL_DISREGARD_INLINE_LIMITS (callee->decl)) 407 ; 408 else if (!DECL_DECLARED_INLINE_P (callee->decl) 409 && !flag_inline_small_functions) 410 { 411 e->inline_failed = CIF_FUNCTION_NOT_INLINE_CANDIDATE; 412 report_inline_failed_reason (e); 413 want_inline = false; 414 } 415 else 416 { 417 int growth = estimate_edge_growth (e); 418 if (growth <= 0) 419 ; 420 else if (!cgraph_maybe_hot_edge_p (e) 421 && growth > 0) 422 { 423 if (dump_file) 424 fprintf (dump_file, " will not early inline: %s/%i->%s/%i, " 425 "call is cold and code would grow by %i\n", 426 xstrdup (cgraph_node_name (e->caller)), e->caller->uid, 427 xstrdup (cgraph_node_name (callee)), callee->uid, 428 growth); 429 want_inline = false; 430 } 431 else if (!leaf_node_p (callee) 432 && growth > 0) 433 { 434 if (dump_file) 435 fprintf (dump_file, " will not early inline: %s/%i->%s/%i, " 436 "callee is not leaf and code would grow by %i\n", 437 xstrdup (cgraph_node_name (e->caller)), e->caller->uid, 438 xstrdup (cgraph_node_name (callee)), callee->uid, 439 growth); 440 want_inline = false; 441 } 442 else if (growth > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS)) 443 { 444 if (dump_file) 445 fprintf (dump_file, " will not early inline: %s/%i->%s/%i, " 446 "growth %i exceeds --param early-inlining-insns\n", 447 xstrdup (cgraph_node_name (e->caller)), e->caller->uid, 448 xstrdup (cgraph_node_name (callee)), callee->uid, 449 growth); 450 want_inline = false; 451 } 452 } 453 return want_inline; 454 } 455 456 /* Return true if we are interested in inlining small function. 457 When REPORT is true, report reason to dump file. */ 458 459 static bool 460 want_inline_small_function_p (struct cgraph_edge *e, bool report) 461 { 462 bool want_inline = true; 463 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL); 464 465 if (DECL_DISREGARD_INLINE_LIMITS (callee->decl)) 466 ; 467 else if (!DECL_DECLARED_INLINE_P (callee->decl) 468 && !flag_inline_small_functions) 469 { 470 e->inline_failed = CIF_FUNCTION_NOT_INLINE_CANDIDATE; 471 want_inline = false; 472 } 473 else 474 { 475 int growth = estimate_edge_growth (e); 476 477 if (growth <= 0) 478 ; 479 else if (DECL_DECLARED_INLINE_P (callee->decl) 480 && growth >= MAX_INLINE_INSNS_SINGLE) 481 { 482 e->inline_failed = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT; 483 want_inline = false; 484 } 485 /* Before giving up based on fact that caller size will grow, allow 486 functions that are called few times and eliminating the offline 487 copy will lead to overall code size reduction. 488 Not all of these will be handled by subsequent inlining of functions 489 called once: in particular weak functions are not handled or funcitons 490 that inline to multiple calls but a lot of bodies is optimized out. 491 Finally we want to inline earlier to allow inlining of callbacks. 492 493 This is slightly wrong on aggressive side: it is entirely possible 494 that function is called many times with a context where inlining 495 reduces code size and few times with a context where inlining increase 496 code size. Resoluting growth estimate will be negative even if it 497 would make more sense to keep offline copy and do not inline into the 498 call sites that makes the code size grow. 499 500 When badness orders the calls in a way that code reducing calls come 501 first, this situation is not a problem at all: after inlining all 502 "good" calls, we will realize that keeping the function around is 503 better. */ 504 else if (growth <= MAX_INLINE_INSNS_SINGLE 505 /* Unlike for functions called once, we play unsafe with 506 COMDATs. We can allow that since we know functions 507 in consideration are small (and thus risk is small) and 508 moreover grow estimates already accounts that COMDAT 509 functions may or may not disappear when eliminated from 510 current unit. With good probability making aggressive 511 choice in all units is going to make overall program 512 smaller. 513 514 Consequently we ask cgraph_can_remove_if_no_direct_calls_p 515 instead of 516 cgraph_will_be_removed_from_program_if_no_direct_calls */ 517 && !DECL_EXTERNAL (callee->decl) 518 && cgraph_can_remove_if_no_direct_calls_p (callee) 519 && estimate_growth (callee) <= 0) 520 ; 521 else if (!DECL_DECLARED_INLINE_P (callee->decl) 522 && !flag_inline_functions) 523 { 524 e->inline_failed = CIF_NOT_DECLARED_INLINED; 525 want_inline = false; 526 } 527 else if (!DECL_DECLARED_INLINE_P (callee->decl) 528 && growth >= MAX_INLINE_INSNS_AUTO) 529 { 530 e->inline_failed = CIF_MAX_INLINE_INSNS_AUTO_LIMIT; 531 want_inline = false; 532 } 533 /* If call is cold, do not inline when function body would grow. */ 534 else if (!cgraph_maybe_hot_edge_p (e)) 535 { 536 e->inline_failed = CIF_UNLIKELY_CALL; 537 want_inline = false; 538 } 539 } 540 if (!want_inline && report) 541 report_inline_failed_reason (e); 542 return want_inline; 543 } 544 545 /* EDGE is self recursive edge. 546 We hand two cases - when function A is inlining into itself 547 or when function A is being inlined into another inliner copy of function 548 A within function B. 549 550 In first case OUTER_NODE points to the toplevel copy of A, while 551 in the second case OUTER_NODE points to the outermost copy of A in B. 552 553 In both cases we want to be extra selective since 554 inlining the call will just introduce new recursive calls to appear. */ 555 556 static bool 557 want_inline_self_recursive_call_p (struct cgraph_edge *edge, 558 struct cgraph_node *outer_node, 559 bool peeling, 560 int depth) 561 { 562 char const *reason = NULL; 563 bool want_inline = true; 564 int caller_freq = CGRAPH_FREQ_BASE; 565 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO); 566 567 if (DECL_DECLARED_INLINE_P (edge->caller->decl)) 568 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH); 569 570 if (!cgraph_maybe_hot_edge_p (edge)) 571 { 572 reason = "recursive call is cold"; 573 want_inline = false; 574 } 575 else if (max_count && !outer_node->count) 576 { 577 reason = "not executed in profile"; 578 want_inline = false; 579 } 580 else if (depth > max_depth) 581 { 582 reason = "--param max-inline-recursive-depth exceeded."; 583 want_inline = false; 584 } 585 586 if (outer_node->global.inlined_to) 587 caller_freq = outer_node->callers->frequency; 588 589 if (!want_inline) 590 ; 591 /* Inlining of self recursive function into copy of itself within other function 592 is transformation similar to loop peeling. 593 594 Peeling is profitable if we can inline enough copies to make probability 595 of actual call to the self recursive function very small. Be sure that 596 the probability of recursion is small. 597 598 We ensure that the frequency of recursing is at most 1 - (1/max_depth). 599 This way the expected number of recision is at most max_depth. */ 600 else if (peeling) 601 { 602 int max_prob = CGRAPH_FREQ_BASE - ((CGRAPH_FREQ_BASE + max_depth - 1) 603 / max_depth); 604 int i; 605 for (i = 1; i < depth; i++) 606 max_prob = max_prob * max_prob / CGRAPH_FREQ_BASE; 607 if (max_count 608 && (edge->count * CGRAPH_FREQ_BASE / outer_node->count 609 >= max_prob)) 610 { 611 reason = "profile of recursive call is too large"; 612 want_inline = false; 613 } 614 if (!max_count 615 && (edge->frequency * CGRAPH_FREQ_BASE / caller_freq 616 >= max_prob)) 617 { 618 reason = "frequency of recursive call is too large"; 619 want_inline = false; 620 } 621 } 622 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion 623 depth is large. We reduce function call overhead and increase chances that 624 things fit in hardware return predictor. 625 626 Recursive inlining might however increase cost of stack frame setup 627 actually slowing down functions whose recursion tree is wide rather than 628 deep. 629 630 Deciding reliably on when to do recursive inlining without profile feedback 631 is tricky. For now we disable recursive inlining when probability of self 632 recursion is low. 633 634 Recursive inlining of self recursive call within loop also results in large loop 635 depths that generally optimize badly. We may want to throttle down inlining 636 in those cases. In particular this seems to happen in one of libstdc++ rb tree 637 methods. */ 638 else 639 { 640 if (max_count 641 && (edge->count * 100 / outer_node->count 642 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY))) 643 { 644 reason = "profile of recursive call is too small"; 645 want_inline = false; 646 } 647 else if (!max_count 648 && (edge->frequency * 100 / caller_freq 649 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY))) 650 { 651 reason = "frequency of recursive call is too small"; 652 want_inline = false; 653 } 654 } 655 if (!want_inline && dump_file) 656 fprintf (dump_file, " not inlining recursively: %s\n", reason); 657 return want_inline; 658 } 659 660 /* Return true when NODE has caller other than EDGE. 661 Worker for cgraph_for_node_and_aliases. */ 662 663 static bool 664 check_caller_edge (struct cgraph_node *node, void *edge) 665 { 666 return (node->callers 667 && node->callers != edge); 668 } 669 670 671 /* Decide if NODE is called once inlining it would eliminate need 672 for the offline copy of function. */ 673 674 static bool 675 want_inline_function_called_once_p (struct cgraph_node *node) 676 { 677 struct cgraph_node *function = cgraph_function_or_thunk_node (node, NULL); 678 /* Already inlined? */ 679 if (function->global.inlined_to) 680 return false; 681 /* Zero or more then one callers? */ 682 if (!node->callers 683 || node->callers->next_caller) 684 return false; 685 /* Maybe other aliases has more direct calls. */ 686 if (cgraph_for_node_and_aliases (node, check_caller_edge, node->callers, true)) 687 return false; 688 /* Recursive call makes no sense to inline. */ 689 if (cgraph_edge_recursive_p (node->callers)) 690 return false; 691 /* External functions are not really in the unit, so inlining 692 them when called once would just increase the program size. */ 693 if (DECL_EXTERNAL (function->decl)) 694 return false; 695 /* Offline body must be optimized out. */ 696 if (!cgraph_will_be_removed_from_program_if_no_direct_calls (function)) 697 return false; 698 if (!can_inline_edge_p (node->callers, true)) 699 return false; 700 return true; 701 } 702 703 704 /* Return relative time improvement for inlining EDGE in range 705 1...2^9. */ 706 707 static inline int 708 relative_time_benefit (struct inline_summary *callee_info, 709 struct cgraph_edge *edge, 710 int time_growth) 711 { 712 int relbenefit; 713 gcov_type uninlined_call_time; 714 715 uninlined_call_time = 716 ((gcov_type) 717 (callee_info->time 718 + inline_edge_summary (edge)->call_stmt_time) * edge->frequency 719 + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE; 720 /* Compute relative time benefit, i.e. how much the call becomes faster. 721 ??? perhaps computing how much the caller+calle together become faster 722 would lead to more realistic results. */ 723 if (!uninlined_call_time) 724 uninlined_call_time = 1; 725 relbenefit = 726 (uninlined_call_time - time_growth) * 256 / (uninlined_call_time); 727 relbenefit = MIN (relbenefit, 512); 728 relbenefit = MAX (relbenefit, 1); 729 return relbenefit; 730 } 731 732 733 /* A cost model driving the inlining heuristics in a way so the edges with 734 smallest badness are inlined first. After each inlining is performed 735 the costs of all caller edges of nodes affected are recomputed so the 736 metrics may accurately depend on values such as number of inlinable callers 737 of the function or function body size. */ 738 739 static int 740 edge_badness (struct cgraph_edge *edge, bool dump) 741 { 742 gcov_type badness; 743 int growth, time_growth; 744 struct cgraph_node *callee = cgraph_function_or_thunk_node (edge->callee, 745 NULL); 746 struct inline_summary *callee_info = inline_summary (callee); 747 748 if (DECL_DISREGARD_INLINE_LIMITS (callee->decl)) 749 return INT_MIN; 750 751 growth = estimate_edge_growth (edge); 752 time_growth = estimate_edge_time (edge); 753 754 if (dump) 755 { 756 fprintf (dump_file, " Badness calculation for %s -> %s\n", 757 xstrdup (cgraph_node_name (edge->caller)), 758 xstrdup (cgraph_node_name (callee))); 759 fprintf (dump_file, " size growth %i, time growth %i\n", 760 growth, 761 time_growth); 762 } 763 764 /* Always prefer inlining saving code size. */ 765 if (growth <= 0) 766 { 767 badness = INT_MIN / 2 + growth; 768 if (dump) 769 fprintf (dump_file, " %i: Growth %i <= 0\n", (int) badness, 770 growth); 771 } 772 773 /* When profiling is available, compute badness as: 774 775 relative_edge_count * relative_time_benefit 776 goodness = ------------------------------------------- 777 edge_growth 778 badness = -goodness 779 780 The fraction is upside down, becuase on edge counts and time beneits 781 the bounds are known. Edge growth is essentially unlimited. */ 782 783 else if (max_count) 784 { 785 int relbenefit = relative_time_benefit (callee_info, edge, time_growth); 786 badness = 787 ((int) 788 ((double) edge->count * INT_MIN / 2 / max_count / 512) * 789 relative_time_benefit (callee_info, edge, time_growth)) / growth; 790 791 /* Be sure that insanity of the profile won't lead to increasing counts 792 in the scalling and thus to overflow in the computation above. */ 793 gcc_assert (max_count >= edge->count); 794 if (dump) 795 { 796 fprintf (dump_file, 797 " %i (relative %f): profile info. Relative count %f" 798 " * Relative benefit %f\n", 799 (int) badness, (double) badness / INT_MIN, 800 (double) edge->count / max_count, 801 relbenefit * 100 / 256.0); 802 } 803 } 804 805 /* When function local profile is available. Compute badness as: 806 807 808 growth_of_callee 809 badness = -------------------------------------- + growth_for-all 810 relative_time_benefit * edge_frequency 811 812 */ 813 else if (flag_guess_branch_prob) 814 { 815 int div = edge->frequency * (1<<10) / CGRAPH_FREQ_MAX; 816 817 div = MAX (div, 1); 818 gcc_checking_assert (edge->frequency <= CGRAPH_FREQ_MAX); 819 div *= relative_time_benefit (callee_info, edge, time_growth); 820 821 /* frequency is normalized in range 1...2^10. 822 relbenefit in range 1...2^9 823 DIV should be in range 1....2^19. */ 824 gcc_checking_assert (div >= 1 && div <= (1<<19)); 825 826 /* Result must be integer in range 0...INT_MAX. 827 Set the base of fixed point calculation so we don't lose much of 828 precision for small bandesses (those are interesting) yet we don't 829 overflow for growths that are still in interesting range. 830 831 Fixed point arithmetic with point at 8th bit. */ 832 badness = ((gcov_type)growth) * (1<<(19+8)); 833 badness = (badness + div / 2) / div; 834 835 /* Overall growth of inlining all calls of function matters: we want to 836 inline so offline copy of function is no longer needed. 837 838 Additionally functions that can be fully inlined without much of 839 effort are better inline candidates than functions that can be fully 840 inlined only after noticeable overall unit growths. The latter 841 are better in a sense compressing of code size by factoring out common 842 code into separate function shared by multiple code paths. 843 844 We might mix the valud into the fraction by taking into account 845 relative growth of the unit, but for now just add the number 846 into resulting fraction. */ 847 if (badness > INT_MAX / 2) 848 { 849 badness = INT_MAX / 2; 850 if (dump) 851 fprintf (dump_file, "Badness overflow\n"); 852 } 853 if (dump) 854 { 855 fprintf (dump_file, 856 " %i: guessed profile. frequency %f," 857 " benefit %f%%, divisor %i\n", 858 (int) badness, (double)edge->frequency / CGRAPH_FREQ_BASE, 859 relative_time_benefit (callee_info, edge, time_growth) * 100 / 256.0, div); 860 } 861 } 862 /* When function local profile is not available or it does not give 863 useful information (ie frequency is zero), base the cost on 864 loop nest and overall size growth, so we optimize for overall number 865 of functions fully inlined in program. */ 866 else 867 { 868 int nest = MIN (inline_edge_summary (edge)->loop_depth, 8); 869 badness = growth * 256; 870 871 /* Decrease badness if call is nested. */ 872 if (badness > 0) 873 badness >>= nest; 874 else 875 { 876 badness <<= nest; 877 } 878 if (dump) 879 fprintf (dump_file, " %i: no profile. nest %i\n", (int) badness, 880 nest); 881 } 882 883 /* Ensure that we did not overflow in all the fixed point math above. */ 884 gcc_assert (badness >= INT_MIN); 885 gcc_assert (badness <= INT_MAX - 1); 886 /* Make recursive inlining happen always after other inlining is done. */ 887 if (cgraph_edge_recursive_p (edge)) 888 return badness + 1; 889 else 890 return badness; 891 } 892 893 /* Recompute badness of EDGE and update its key in HEAP if needed. */ 894 static inline void 895 update_edge_key (fibheap_t heap, struct cgraph_edge *edge) 896 { 897 int badness = edge_badness (edge, false); 898 if (edge->aux) 899 { 900 fibnode_t n = (fibnode_t) edge->aux; 901 gcc_checking_assert (n->data == edge); 902 903 /* fibheap_replace_key only decrease the keys. 904 When we increase the key we do not update heap 905 and instead re-insert the element once it becomes 906 a minimum of heap. */ 907 if (badness < n->key) 908 { 909 if (dump_file && (dump_flags & TDF_DETAILS)) 910 { 911 fprintf (dump_file, 912 " decreasing badness %s/%i -> %s/%i, %i to %i\n", 913 xstrdup (cgraph_node_name (edge->caller)), 914 edge->caller->uid, 915 xstrdup (cgraph_node_name (edge->callee)), 916 edge->callee->uid, 917 (int)n->key, 918 badness); 919 } 920 fibheap_replace_key (heap, n, badness); 921 gcc_checking_assert (n->key == badness); 922 } 923 } 924 else 925 { 926 if (dump_file && (dump_flags & TDF_DETAILS)) 927 { 928 fprintf (dump_file, 929 " enqueuing call %s/%i -> %s/%i, badness %i\n", 930 xstrdup (cgraph_node_name (edge->caller)), 931 edge->caller->uid, 932 xstrdup (cgraph_node_name (edge->callee)), 933 edge->callee->uid, 934 badness); 935 } 936 edge->aux = fibheap_insert (heap, badness, edge); 937 } 938 } 939 940 941 /* NODE was inlined. 942 All caller edges needs to be resetted because 943 size estimates change. Similarly callees needs reset 944 because better context may be known. */ 945 946 static void 947 reset_edge_caches (struct cgraph_node *node) 948 { 949 struct cgraph_edge *edge; 950 struct cgraph_edge *e = node->callees; 951 struct cgraph_node *where = node; 952 int i; 953 struct ipa_ref *ref; 954 955 if (where->global.inlined_to) 956 where = where->global.inlined_to; 957 958 /* WHERE body size has changed, the cached growth is invalid. */ 959 reset_node_growth_cache (where); 960 961 for (edge = where->callers; edge; edge = edge->next_caller) 962 if (edge->inline_failed) 963 reset_edge_growth_cache (edge); 964 for (i = 0; ipa_ref_list_refering_iterate (&where->ref_list, i, ref); i++) 965 if (ref->use == IPA_REF_ALIAS) 966 reset_edge_caches (ipa_ref_refering_node (ref)); 967 968 if (!e) 969 return; 970 971 while (true) 972 if (!e->inline_failed && e->callee->callees) 973 e = e->callee->callees; 974 else 975 { 976 if (e->inline_failed) 977 reset_edge_growth_cache (e); 978 if (e->next_callee) 979 e = e->next_callee; 980 else 981 { 982 do 983 { 984 if (e->caller == node) 985 return; 986 e = e->caller->callers; 987 } 988 while (!e->next_callee); 989 e = e->next_callee; 990 } 991 } 992 } 993 994 /* Recompute HEAP nodes for each of caller of NODE. 995 UPDATED_NODES track nodes we already visited, to avoid redundant work. 996 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that 997 it is inlinable. Otherwise check all edges. */ 998 999 static void 1000 update_caller_keys (fibheap_t heap, struct cgraph_node *node, 1001 bitmap updated_nodes, 1002 struct cgraph_edge *check_inlinablity_for) 1003 { 1004 struct cgraph_edge *edge; 1005 int i; 1006 struct ipa_ref *ref; 1007 1008 if ((!node->alias && !inline_summary (node)->inlinable) 1009 || cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE 1010 || node->global.inlined_to) 1011 return; 1012 if (!bitmap_set_bit (updated_nodes, node->uid)) 1013 return; 1014 1015 for (i = 0; ipa_ref_list_refering_iterate (&node->ref_list, i, ref); i++) 1016 if (ref->use == IPA_REF_ALIAS) 1017 { 1018 struct cgraph_node *alias = ipa_ref_refering_node (ref); 1019 update_caller_keys (heap, alias, updated_nodes, check_inlinablity_for); 1020 } 1021 1022 for (edge = node->callers; edge; edge = edge->next_caller) 1023 if (edge->inline_failed) 1024 { 1025 if (!check_inlinablity_for 1026 || check_inlinablity_for == edge) 1027 { 1028 if (can_inline_edge_p (edge, false) 1029 && want_inline_small_function_p (edge, false)) 1030 update_edge_key (heap, edge); 1031 else if (edge->aux) 1032 { 1033 report_inline_failed_reason (edge); 1034 fibheap_delete_node (heap, (fibnode_t) edge->aux); 1035 edge->aux = NULL; 1036 } 1037 } 1038 else if (edge->aux) 1039 update_edge_key (heap, edge); 1040 } 1041 } 1042 1043 /* Recompute HEAP nodes for each uninlined call in NODE. 1044 This is used when we know that edge badnesses are going only to increase 1045 (we introduced new call site) and thus all we need is to insert newly 1046 created edges into heap. */ 1047 1048 static void 1049 update_callee_keys (fibheap_t heap, struct cgraph_node *node, 1050 bitmap updated_nodes) 1051 { 1052 struct cgraph_edge *e = node->callees; 1053 1054 if (!e) 1055 return; 1056 while (true) 1057 if (!e->inline_failed && e->callee->callees) 1058 e = e->callee->callees; 1059 else 1060 { 1061 enum availability avail; 1062 struct cgraph_node *callee; 1063 /* We do not reset callee growth cache here. Since we added a new call, 1064 growth chould have just increased and consequentely badness metric 1065 don't need updating. */ 1066 if (e->inline_failed 1067 && (callee = cgraph_function_or_thunk_node (e->callee, &avail)) 1068 && inline_summary (callee)->inlinable 1069 && cgraph_function_body_availability (callee) >= AVAIL_AVAILABLE 1070 && !bitmap_bit_p (updated_nodes, callee->uid)) 1071 { 1072 if (can_inline_edge_p (e, false) 1073 && want_inline_small_function_p (e, false)) 1074 update_edge_key (heap, e); 1075 else if (e->aux) 1076 { 1077 report_inline_failed_reason (e); 1078 fibheap_delete_node (heap, (fibnode_t) e->aux); 1079 e->aux = NULL; 1080 } 1081 } 1082 if (e->next_callee) 1083 e = e->next_callee; 1084 else 1085 { 1086 do 1087 { 1088 if (e->caller == node) 1089 return; 1090 e = e->caller->callers; 1091 } 1092 while (!e->next_callee); 1093 e = e->next_callee; 1094 } 1095 } 1096 } 1097 1098 /* Recompute heap nodes for each of caller edges of each of callees. 1099 Walk recursively into all inline clones. */ 1100 1101 static void 1102 update_all_callee_keys (fibheap_t heap, struct cgraph_node *node, 1103 bitmap updated_nodes) 1104 { 1105 struct cgraph_edge *e = node->callees; 1106 if (!e) 1107 return; 1108 while (true) 1109 if (!e->inline_failed && e->callee->callees) 1110 e = e->callee->callees; 1111 else 1112 { 1113 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, 1114 NULL); 1115 1116 /* We inlined and thus callees might have different number of calls. 1117 Reset their caches */ 1118 reset_node_growth_cache (callee); 1119 if (e->inline_failed) 1120 update_caller_keys (heap, callee, updated_nodes, e); 1121 if (e->next_callee) 1122 e = e->next_callee; 1123 else 1124 { 1125 do 1126 { 1127 if (e->caller == node) 1128 return; 1129 e = e->caller->callers; 1130 } 1131 while (!e->next_callee); 1132 e = e->next_callee; 1133 } 1134 } 1135 } 1136 1137 /* Enqueue all recursive calls from NODE into priority queue depending on 1138 how likely we want to recursively inline the call. */ 1139 1140 static void 1141 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where, 1142 fibheap_t heap) 1143 { 1144 struct cgraph_edge *e; 1145 enum availability avail; 1146 1147 for (e = where->callees; e; e = e->next_callee) 1148 if (e->callee == node 1149 || (cgraph_function_or_thunk_node (e->callee, &avail) == node 1150 && avail > AVAIL_OVERWRITABLE)) 1151 { 1152 /* When profile feedback is available, prioritize by expected number 1153 of calls. */ 1154 fibheap_insert (heap, 1155 !max_count ? -e->frequency 1156 : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))), 1157 e); 1158 } 1159 for (e = where->callees; e; e = e->next_callee) 1160 if (!e->inline_failed) 1161 lookup_recursive_calls (node, e->callee, heap); 1162 } 1163 1164 /* Decide on recursive inlining: in the case function has recursive calls, 1165 inline until body size reaches given argument. If any new indirect edges 1166 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES 1167 is NULL. */ 1168 1169 static bool 1170 recursive_inlining (struct cgraph_edge *edge, 1171 VEC (cgraph_edge_p, heap) **new_edges) 1172 { 1173 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO); 1174 fibheap_t heap; 1175 struct cgraph_node *node; 1176 struct cgraph_edge *e; 1177 struct cgraph_node *master_clone = NULL, *next; 1178 int depth = 0; 1179 int n = 0; 1180 1181 node = edge->caller; 1182 if (node->global.inlined_to) 1183 node = node->global.inlined_to; 1184 1185 if (DECL_DECLARED_INLINE_P (node->decl)) 1186 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE); 1187 1188 /* Make sure that function is small enough to be considered for inlining. */ 1189 if (estimate_size_after_inlining (node, edge) >= limit) 1190 return false; 1191 heap = fibheap_new (); 1192 lookup_recursive_calls (node, node, heap); 1193 if (fibheap_empty (heap)) 1194 { 1195 fibheap_delete (heap); 1196 return false; 1197 } 1198 1199 if (dump_file) 1200 fprintf (dump_file, 1201 " Performing recursive inlining on %s\n", 1202 cgraph_node_name (node)); 1203 1204 /* Do the inlining and update list of recursive call during process. */ 1205 while (!fibheap_empty (heap)) 1206 { 1207 struct cgraph_edge *curr 1208 = (struct cgraph_edge *) fibheap_extract_min (heap); 1209 struct cgraph_node *cnode; 1210 1211 if (estimate_size_after_inlining (node, curr) > limit) 1212 break; 1213 1214 if (!can_inline_edge_p (curr, true)) 1215 continue; 1216 1217 depth = 1; 1218 for (cnode = curr->caller; 1219 cnode->global.inlined_to; cnode = cnode->callers->caller) 1220 if (node->decl 1221 == cgraph_function_or_thunk_node (curr->callee, NULL)->decl) 1222 depth++; 1223 1224 if (!want_inline_self_recursive_call_p (curr, node, false, depth)) 1225 continue; 1226 1227 if (dump_file) 1228 { 1229 fprintf (dump_file, 1230 " Inlining call of depth %i", depth); 1231 if (node->count) 1232 { 1233 fprintf (dump_file, " called approx. %.2f times per call", 1234 (double)curr->count / node->count); 1235 } 1236 fprintf (dump_file, "\n"); 1237 } 1238 if (!master_clone) 1239 { 1240 /* We need original clone to copy around. */ 1241 master_clone = cgraph_clone_node (node, node->decl, 1242 node->count, CGRAPH_FREQ_BASE, 1243 false, NULL, true); 1244 for (e = master_clone->callees; e; e = e->next_callee) 1245 if (!e->inline_failed) 1246 clone_inlined_nodes (e, true, false, NULL); 1247 } 1248 1249 cgraph_redirect_edge_callee (curr, master_clone); 1250 inline_call (curr, false, new_edges, &overall_size); 1251 lookup_recursive_calls (node, curr->callee, heap); 1252 n++; 1253 } 1254 1255 if (!fibheap_empty (heap) && dump_file) 1256 fprintf (dump_file, " Recursive inlining growth limit met.\n"); 1257 fibheap_delete (heap); 1258 1259 if (!master_clone) 1260 return false; 1261 1262 if (dump_file) 1263 fprintf (dump_file, 1264 "\n Inlined %i times, " 1265 "body grown from size %i to %i, time %i to %i\n", n, 1266 inline_summary (master_clone)->size, inline_summary (node)->size, 1267 inline_summary (master_clone)->time, inline_summary (node)->time); 1268 1269 /* Remove master clone we used for inlining. We rely that clones inlined 1270 into master clone gets queued just before master clone so we don't 1271 need recursion. */ 1272 for (node = cgraph_nodes; node != master_clone; 1273 node = next) 1274 { 1275 next = node->next; 1276 if (node->global.inlined_to == master_clone) 1277 cgraph_remove_node (node); 1278 } 1279 cgraph_remove_node (master_clone); 1280 return true; 1281 } 1282 1283 1284 /* Given whole compilation unit estimate of INSNS, compute how large we can 1285 allow the unit to grow. */ 1286 1287 static int 1288 compute_max_insns (int insns) 1289 { 1290 int max_insns = insns; 1291 if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS)) 1292 max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS); 1293 1294 return ((HOST_WIDEST_INT) max_insns 1295 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100); 1296 } 1297 1298 1299 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */ 1300 1301 static void 1302 add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges) 1303 { 1304 while (VEC_length (cgraph_edge_p, new_edges) > 0) 1305 { 1306 struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges); 1307 1308 gcc_assert (!edge->aux); 1309 if (edge->inline_failed 1310 && can_inline_edge_p (edge, true) 1311 && want_inline_small_function_p (edge, true)) 1312 edge->aux = fibheap_insert (heap, edge_badness (edge, false), edge); 1313 } 1314 } 1315 1316 1317 /* We use greedy algorithm for inlining of small functions: 1318 All inline candidates are put into prioritized heap ordered in 1319 increasing badness. 1320 1321 The inlining of small functions is bounded by unit growth parameters. */ 1322 1323 static void 1324 inline_small_functions (void) 1325 { 1326 struct cgraph_node *node; 1327 struct cgraph_edge *edge; 1328 fibheap_t heap = fibheap_new (); 1329 bitmap updated_nodes = BITMAP_ALLOC (NULL); 1330 int min_size, max_size; 1331 VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL; 1332 int initial_size = 0; 1333 1334 if (flag_indirect_inlining) 1335 new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8); 1336 1337 if (dump_file) 1338 fprintf (dump_file, 1339 "\nDeciding on inlining of small functions. Starting with size %i.\n", 1340 initial_size); 1341 1342 /* Compute overall unit size and other global parameters used by badness 1343 metrics. */ 1344 1345 max_count = 0; 1346 initialize_growth_caches (); 1347 1348 FOR_EACH_DEFINED_FUNCTION (node) 1349 if (!node->global.inlined_to) 1350 { 1351 if (cgraph_function_with_gimple_body_p (node) 1352 || node->thunk.thunk_p) 1353 { 1354 struct inline_summary *info = inline_summary (node); 1355 1356 if (!DECL_EXTERNAL (node->decl)) 1357 initial_size += info->size; 1358 } 1359 1360 for (edge = node->callers; edge; edge = edge->next_caller) 1361 if (max_count < edge->count) 1362 max_count = edge->count; 1363 } 1364 1365 overall_size = initial_size; 1366 max_size = compute_max_insns (overall_size); 1367 min_size = overall_size; 1368 1369 /* Populate the heeap with all edges we might inline. */ 1370 1371 FOR_EACH_DEFINED_FUNCTION (node) 1372 if (!node->global.inlined_to) 1373 { 1374 if (dump_file) 1375 fprintf (dump_file, "Enqueueing calls of %s/%i.\n", 1376 cgraph_node_name (node), node->uid); 1377 1378 for (edge = node->callers; edge; edge = edge->next_caller) 1379 if (edge->inline_failed 1380 && can_inline_edge_p (edge, true) 1381 && want_inline_small_function_p (edge, true) 1382 && edge->inline_failed) 1383 { 1384 gcc_assert (!edge->aux); 1385 update_edge_key (heap, edge); 1386 } 1387 } 1388 1389 gcc_assert (in_lto_p 1390 || !max_count 1391 || (profile_info && flag_branch_probabilities)); 1392 1393 while (!fibheap_empty (heap)) 1394 { 1395 int old_size = overall_size; 1396 struct cgraph_node *where, *callee; 1397 int badness = fibheap_min_key (heap); 1398 int current_badness; 1399 int cached_badness; 1400 int growth; 1401 1402 edge = (struct cgraph_edge *) fibheap_extract_min (heap); 1403 gcc_assert (edge->aux); 1404 edge->aux = NULL; 1405 if (!edge->inline_failed) 1406 continue; 1407 1408 /* Be sure that caches are maintained consistent. 1409 We can not make this ENABLE_CHECKING only because it cause differnt 1410 updates of the fibheap queue. */ 1411 cached_badness = edge_badness (edge, false); 1412 reset_edge_growth_cache (edge); 1413 reset_node_growth_cache (edge->callee); 1414 1415 /* When updating the edge costs, we only decrease badness in the keys. 1416 Increases of badness are handled lazilly; when we see key with out 1417 of date value on it, we re-insert it now. */ 1418 current_badness = edge_badness (edge, false); 1419 gcc_assert (cached_badness == current_badness); 1420 gcc_assert (current_badness >= badness); 1421 if (current_badness != badness) 1422 { 1423 edge->aux = fibheap_insert (heap, current_badness, edge); 1424 continue; 1425 } 1426 1427 if (!can_inline_edge_p (edge, true)) 1428 continue; 1429 1430 callee = cgraph_function_or_thunk_node (edge->callee, NULL); 1431 growth = estimate_edge_growth (edge); 1432 if (dump_file) 1433 { 1434 fprintf (dump_file, 1435 "\nConsidering %s with %i size\n", 1436 cgraph_node_name (callee), 1437 inline_summary (callee)->size); 1438 fprintf (dump_file, 1439 " to be inlined into %s in %s:%i\n" 1440 " Estimated growth after inlined into all is %+i insns.\n" 1441 " Estimated badness is %i, frequency %.2f.\n", 1442 cgraph_node_name (edge->caller), 1443 flag_wpa ? "unknown" 1444 : gimple_filename ((const_gimple) edge->call_stmt), 1445 flag_wpa ? -1 1446 : gimple_lineno ((const_gimple) edge->call_stmt), 1447 estimate_growth (callee), 1448 badness, 1449 edge->frequency / (double)CGRAPH_FREQ_BASE); 1450 if (edge->count) 1451 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", 1452 edge->count); 1453 if (dump_flags & TDF_DETAILS) 1454 edge_badness (edge, true); 1455 } 1456 1457 if (overall_size + growth > max_size 1458 && !DECL_DISREGARD_INLINE_LIMITS (callee->decl)) 1459 { 1460 edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT; 1461 report_inline_failed_reason (edge); 1462 continue; 1463 } 1464 1465 if (!want_inline_small_function_p (edge, true)) 1466 continue; 1467 1468 /* Heuristics for inlining small functions works poorly for 1469 recursive calls where we do efect similar to loop unrolling. 1470 When inliing such edge seems profitable, leave decision on 1471 specific inliner. */ 1472 if (cgraph_edge_recursive_p (edge)) 1473 { 1474 where = edge->caller; 1475 if (where->global.inlined_to) 1476 where = where->global.inlined_to; 1477 if (!recursive_inlining (edge, 1478 flag_indirect_inlining 1479 ? &new_indirect_edges : NULL)) 1480 { 1481 edge->inline_failed = CIF_RECURSIVE_INLINING; 1482 continue; 1483 } 1484 reset_edge_caches (where); 1485 /* Recursive inliner inlines all recursive calls of the function 1486 at once. Consequently we need to update all callee keys. */ 1487 if (flag_indirect_inlining) 1488 add_new_edges_to_heap (heap, new_indirect_edges); 1489 update_all_callee_keys (heap, where, updated_nodes); 1490 } 1491 else 1492 { 1493 struct cgraph_node *outer_node = NULL; 1494 int depth = 0; 1495 1496 /* Consider the case where self recursive function A is inlined into B. 1497 This is desired optimization in some cases, since it leads to effect 1498 similar of loop peeling and we might completely optimize out the 1499 recursive call. However we must be extra selective. */ 1500 1501 where = edge->caller; 1502 while (where->global.inlined_to) 1503 { 1504 if (where->decl == callee->decl) 1505 outer_node = where, depth++; 1506 where = where->callers->caller; 1507 } 1508 if (outer_node 1509 && !want_inline_self_recursive_call_p (edge, outer_node, 1510 true, depth)) 1511 { 1512 edge->inline_failed 1513 = (DECL_DISREGARD_INLINE_LIMITS (edge->callee->decl) 1514 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED); 1515 continue; 1516 } 1517 else if (depth && dump_file) 1518 fprintf (dump_file, " Peeling recursion with depth %i\n", depth); 1519 1520 gcc_checking_assert (!callee->global.inlined_to); 1521 inline_call (edge, true, &new_indirect_edges, &overall_size); 1522 if (flag_indirect_inlining) 1523 add_new_edges_to_heap (heap, new_indirect_edges); 1524 1525 reset_edge_caches (edge->callee); 1526 reset_node_growth_cache (callee); 1527 1528 /* We inlined last offline copy to the body. This might lead 1529 to callees of function having fewer call sites and thus they 1530 may need updating. 1531 1532 FIXME: the callee size could also shrink because more information 1533 is propagated from caller. We don't track when this happen and 1534 thus we need to recompute everything all the time. Once this is 1535 solved, "|| 1" should go away. */ 1536 if (callee->global.inlined_to || 1) 1537 update_all_callee_keys (heap, callee, updated_nodes); 1538 else 1539 update_callee_keys (heap, edge->callee, updated_nodes); 1540 } 1541 where = edge->caller; 1542 if (where->global.inlined_to) 1543 where = where->global.inlined_to; 1544 1545 /* Our profitability metric can depend on local properties 1546 such as number of inlinable calls and size of the function body. 1547 After inlining these properties might change for the function we 1548 inlined into (since it's body size changed) and for the functions 1549 called by function we inlined (since number of it inlinable callers 1550 might change). */ 1551 update_caller_keys (heap, where, updated_nodes, NULL); 1552 1553 /* We removed one call of the function we just inlined. If offline 1554 copy is still needed, be sure to update the keys. */ 1555 if (callee != where && !callee->global.inlined_to) 1556 update_caller_keys (heap, callee, updated_nodes, NULL); 1557 bitmap_clear (updated_nodes); 1558 1559 if (dump_file) 1560 { 1561 fprintf (dump_file, 1562 " Inlined into %s which now has time %i and size %i," 1563 "net change of %+i.\n", 1564 cgraph_node_name (edge->caller), 1565 inline_summary (edge->caller)->time, 1566 inline_summary (edge->caller)->size, 1567 overall_size - old_size); 1568 } 1569 if (min_size > overall_size) 1570 { 1571 min_size = overall_size; 1572 max_size = compute_max_insns (min_size); 1573 1574 if (dump_file) 1575 fprintf (dump_file, "New minimal size reached: %i\n", min_size); 1576 } 1577 } 1578 1579 free_growth_caches (); 1580 if (new_indirect_edges) 1581 VEC_free (cgraph_edge_p, heap, new_indirect_edges); 1582 fibheap_delete (heap); 1583 if (dump_file) 1584 fprintf (dump_file, 1585 "Unit growth for small function inlining: %i->%i (%i%%)\n", 1586 initial_size, overall_size, 1587 initial_size ? overall_size * 100 / (initial_size) - 100: 0); 1588 BITMAP_FREE (updated_nodes); 1589 } 1590 1591 /* Flatten NODE. Performed both during early inlining and 1592 at IPA inlining time. */ 1593 1594 static void 1595 flatten_function (struct cgraph_node *node, bool early) 1596 { 1597 struct cgraph_edge *e; 1598 1599 /* We shouldn't be called recursively when we are being processed. */ 1600 gcc_assert (node->aux == NULL); 1601 1602 node->aux = (void *) node; 1603 1604 for (e = node->callees; e; e = e->next_callee) 1605 { 1606 struct cgraph_node *orig_callee; 1607 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL); 1608 1609 /* We've hit cycle? It is time to give up. */ 1610 if (callee->aux) 1611 { 1612 if (dump_file) 1613 fprintf (dump_file, 1614 "Not inlining %s into %s to avoid cycle.\n", 1615 xstrdup (cgraph_node_name (callee)), 1616 xstrdup (cgraph_node_name (e->caller))); 1617 e->inline_failed = CIF_RECURSIVE_INLINING; 1618 continue; 1619 } 1620 1621 /* When the edge is already inlined, we just need to recurse into 1622 it in order to fully flatten the leaves. */ 1623 if (!e->inline_failed) 1624 { 1625 flatten_function (callee, early); 1626 continue; 1627 } 1628 1629 /* Flatten attribute needs to be processed during late inlining. For 1630 extra code quality we however do flattening during early optimization, 1631 too. */ 1632 if (!early 1633 ? !can_inline_edge_p (e, true) 1634 : !can_early_inline_edge_p (e)) 1635 continue; 1636 1637 if (cgraph_edge_recursive_p (e)) 1638 { 1639 if (dump_file) 1640 fprintf (dump_file, "Not inlining: recursive call.\n"); 1641 continue; 1642 } 1643 1644 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl)) 1645 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl))) 1646 { 1647 if (dump_file) 1648 fprintf (dump_file, "Not inlining: SSA form does not match.\n"); 1649 continue; 1650 } 1651 1652 /* Inline the edge and flatten the inline clone. Avoid 1653 recursing through the original node if the node was cloned. */ 1654 if (dump_file) 1655 fprintf (dump_file, " Inlining %s into %s.\n", 1656 xstrdup (cgraph_node_name (callee)), 1657 xstrdup (cgraph_node_name (e->caller))); 1658 orig_callee = callee; 1659 inline_call (e, true, NULL, NULL); 1660 if (e->callee != orig_callee) 1661 orig_callee->aux = (void *) node; 1662 flatten_function (e->callee, early); 1663 if (e->callee != orig_callee) 1664 orig_callee->aux = NULL; 1665 } 1666 1667 node->aux = NULL; 1668 } 1669 1670 /* Decide on the inlining. We do so in the topological order to avoid 1671 expenses on updating data structures. */ 1672 1673 static unsigned int 1674 ipa_inline (void) 1675 { 1676 struct cgraph_node *node; 1677 int nnodes; 1678 struct cgraph_node **order = 1679 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); 1680 int i; 1681 1682 if (in_lto_p && optimize) 1683 ipa_update_after_lto_read (); 1684 1685 if (dump_file) 1686 dump_inline_summaries (dump_file); 1687 1688 nnodes = ipa_reverse_postorder (order); 1689 1690 for (node = cgraph_nodes; node; node = node->next) 1691 node->aux = 0; 1692 1693 if (dump_file) 1694 fprintf (dump_file, "\nFlattening functions:\n"); 1695 1696 /* In the first pass handle functions to be flattened. Do this with 1697 a priority so none of our later choices will make this impossible. */ 1698 for (i = nnodes - 1; i >= 0; i--) 1699 { 1700 node = order[i]; 1701 1702 /* Handle nodes to be flattened. 1703 Ideally when processing callees we stop inlining at the 1704 entry of cycles, possibly cloning that entry point and 1705 try to flatten itself turning it into a self-recursive 1706 function. */ 1707 if (lookup_attribute ("flatten", 1708 DECL_ATTRIBUTES (node->decl)) != NULL) 1709 { 1710 if (dump_file) 1711 fprintf (dump_file, 1712 "Flattening %s\n", cgraph_node_name (node)); 1713 flatten_function (node, false); 1714 } 1715 } 1716 1717 inline_small_functions (); 1718 cgraph_remove_unreachable_nodes (true, dump_file); 1719 free (order); 1720 1721 /* We already perform some inlining of functions called once during 1722 inlining small functions above. After unreachable nodes are removed, 1723 we still might do a quick check that nothing new is found. */ 1724 if (flag_inline_functions_called_once) 1725 { 1726 int cold; 1727 if (dump_file) 1728 fprintf (dump_file, "\nDeciding on functions called once:\n"); 1729 1730 /* Inlining one function called once has good chance of preventing 1731 inlining other function into the same callee. Ideally we should 1732 work in priority order, but probably inlining hot functions first 1733 is good cut without the extra pain of maintaining the queue. 1734 1735 ??? this is not really fitting the bill perfectly: inlining function 1736 into callee often leads to better optimization of callee due to 1737 increased context for optimization. 1738 For example if main() function calls a function that outputs help 1739 and then function that does the main optmization, we should inline 1740 the second with priority even if both calls are cold by themselves. 1741 1742 We probably want to implement new predicate replacing our use of 1743 maybe_hot_edge interpreted as maybe_hot_edge || callee is known 1744 to be hot. */ 1745 for (cold = 0; cold <= 1; cold ++) 1746 { 1747 for (node = cgraph_nodes; node; node = node->next) 1748 { 1749 if (want_inline_function_called_once_p (node) 1750 && (cold 1751 || cgraph_maybe_hot_edge_p (node->callers))) 1752 { 1753 struct cgraph_node *caller = node->callers->caller; 1754 1755 if (dump_file) 1756 { 1757 fprintf (dump_file, 1758 "\nInlining %s size %i.\n", 1759 cgraph_node_name (node), 1760 inline_summary (node)->size); 1761 fprintf (dump_file, 1762 " Called once from %s %i insns.\n", 1763 cgraph_node_name (node->callers->caller), 1764 inline_summary (node->callers->caller)->size); 1765 } 1766 1767 inline_call (node->callers, true, NULL, NULL); 1768 if (dump_file) 1769 fprintf (dump_file, 1770 " Inlined into %s which now has %i size\n", 1771 cgraph_node_name (caller), 1772 inline_summary (caller)->size); 1773 } 1774 } 1775 } 1776 } 1777 1778 /* Free ipa-prop structures if they are no longer needed. */ 1779 if (optimize) 1780 ipa_free_all_structures_after_iinln (); 1781 1782 if (dump_file) 1783 fprintf (dump_file, 1784 "\nInlined %i calls, eliminated %i functions\n\n", 1785 ncalls_inlined, nfunctions_inlined); 1786 1787 if (dump_file) 1788 dump_inline_summaries (dump_file); 1789 /* In WPA we use inline summaries for partitioning process. */ 1790 if (!flag_wpa) 1791 inline_free_summary (); 1792 return 0; 1793 } 1794 1795 /* Inline always-inline function calls in NODE. */ 1796 1797 static bool 1798 inline_always_inline_functions (struct cgraph_node *node) 1799 { 1800 struct cgraph_edge *e; 1801 bool inlined = false; 1802 1803 for (e = node->callees; e; e = e->next_callee) 1804 { 1805 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL); 1806 if (!DECL_DISREGARD_INLINE_LIMITS (callee->decl)) 1807 continue; 1808 1809 if (cgraph_edge_recursive_p (e)) 1810 { 1811 if (dump_file) 1812 fprintf (dump_file, " Not inlining recursive call to %s.\n", 1813 cgraph_node_name (e->callee)); 1814 e->inline_failed = CIF_RECURSIVE_INLINING; 1815 continue; 1816 } 1817 1818 if (!can_early_inline_edge_p (e)) 1819 continue; 1820 1821 if (dump_file) 1822 fprintf (dump_file, " Inlining %s into %s (always_inline).\n", 1823 xstrdup (cgraph_node_name (e->callee)), 1824 xstrdup (cgraph_node_name (e->caller))); 1825 inline_call (e, true, NULL, NULL); 1826 inlined = true; 1827 } 1828 1829 return inlined; 1830 } 1831 1832 /* Decide on the inlining. We do so in the topological order to avoid 1833 expenses on updating data structures. */ 1834 1835 static bool 1836 early_inline_small_functions (struct cgraph_node *node) 1837 { 1838 struct cgraph_edge *e; 1839 bool inlined = false; 1840 1841 for (e = node->callees; e; e = e->next_callee) 1842 { 1843 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL); 1844 if (!inline_summary (callee)->inlinable 1845 || !e->inline_failed) 1846 continue; 1847 1848 /* Do not consider functions not declared inline. */ 1849 if (!DECL_DECLARED_INLINE_P (callee->decl) 1850 && !flag_inline_small_functions 1851 && !flag_inline_functions) 1852 continue; 1853 1854 if (dump_file) 1855 fprintf (dump_file, "Considering inline candidate %s.\n", 1856 cgraph_node_name (callee)); 1857 1858 if (!can_early_inline_edge_p (e)) 1859 continue; 1860 1861 if (cgraph_edge_recursive_p (e)) 1862 { 1863 if (dump_file) 1864 fprintf (dump_file, " Not inlining: recursive call.\n"); 1865 continue; 1866 } 1867 1868 if (!want_early_inline_function_p (e)) 1869 continue; 1870 1871 if (dump_file) 1872 fprintf (dump_file, " Inlining %s into %s.\n", 1873 xstrdup (cgraph_node_name (callee)), 1874 xstrdup (cgraph_node_name (e->caller))); 1875 inline_call (e, true, NULL, NULL); 1876 inlined = true; 1877 } 1878 1879 return inlined; 1880 } 1881 1882 /* Do inlining of small functions. Doing so early helps profiling and other 1883 passes to be somewhat more effective and avoids some code duplication in 1884 later real inlining pass for testcases with very many function calls. */ 1885 static unsigned int 1886 early_inliner (void) 1887 { 1888 struct cgraph_node *node = cgraph_get_node (current_function_decl); 1889 struct cgraph_edge *edge; 1890 unsigned int todo = 0; 1891 int iterations = 0; 1892 bool inlined = false; 1893 1894 if (seen_error ()) 1895 return 0; 1896 1897 /* Do nothing if datastructures for ipa-inliner are already computed. This 1898 happens when some pass decides to construct new function and 1899 cgraph_add_new_function calls lowering passes and early optimization on 1900 it. This may confuse ourself when early inliner decide to inline call to 1901 function clone, because function clones don't have parameter list in 1902 ipa-prop matching their signature. */ 1903 if (ipa_node_params_vector) 1904 return 0; 1905 1906 #ifdef ENABLE_CHECKING 1907 verify_cgraph_node (node); 1908 #endif 1909 1910 /* Even when not optimizing or not inlining inline always-inline 1911 functions. */ 1912 inlined = inline_always_inline_functions (node); 1913 1914 if (!optimize 1915 || flag_no_inline 1916 || !flag_early_inlining 1917 /* Never inline regular functions into always-inline functions 1918 during incremental inlining. This sucks as functions calling 1919 always inline functions will get less optimized, but at the 1920 same time inlining of functions calling always inline 1921 function into an always inline function might introduce 1922 cycles of edges to be always inlined in the callgraph. 1923 1924 We might want to be smarter and just avoid this type of inlining. */ 1925 || DECL_DISREGARD_INLINE_LIMITS (node->decl)) 1926 ; 1927 else if (lookup_attribute ("flatten", 1928 DECL_ATTRIBUTES (node->decl)) != NULL) 1929 { 1930 /* When the function is marked to be flattened, recursively inline 1931 all calls in it. */ 1932 if (dump_file) 1933 fprintf (dump_file, 1934 "Flattening %s\n", cgraph_node_name (node)); 1935 flatten_function (node, true); 1936 inlined = true; 1937 } 1938 else 1939 { 1940 /* We iterate incremental inlining to get trivial cases of indirect 1941 inlining. */ 1942 while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS) 1943 && early_inline_small_functions (node)) 1944 { 1945 timevar_push (TV_INTEGRATION); 1946 todo |= optimize_inline_calls (current_function_decl); 1947 1948 /* Technically we ought to recompute inline parameters so the new 1949 iteration of early inliner works as expected. We however have 1950 values approximately right and thus we only need to update edge 1951 info that might be cleared out for newly discovered edges. */ 1952 for (edge = node->callees; edge; edge = edge->next_callee) 1953 { 1954 struct inline_edge_summary *es = inline_edge_summary (edge); 1955 es->call_stmt_size 1956 = estimate_num_insns (edge->call_stmt, &eni_size_weights); 1957 es->call_stmt_time 1958 = estimate_num_insns (edge->call_stmt, &eni_time_weights); 1959 if (edge->callee->decl 1960 && !gimple_check_call_matching_types (edge->call_stmt, 1961 edge->callee->decl)) 1962 edge->call_stmt_cannot_inline_p = true; 1963 } 1964 timevar_pop (TV_INTEGRATION); 1965 iterations++; 1966 inlined = false; 1967 } 1968 if (dump_file) 1969 fprintf (dump_file, "Iterations: %i\n", iterations); 1970 } 1971 1972 if (inlined) 1973 { 1974 timevar_push (TV_INTEGRATION); 1975 todo |= optimize_inline_calls (current_function_decl); 1976 timevar_pop (TV_INTEGRATION); 1977 } 1978 1979 cfun->always_inline_functions_inlined = true; 1980 1981 return todo; 1982 } 1983 1984 struct gimple_opt_pass pass_early_inline = 1985 { 1986 { 1987 GIMPLE_PASS, 1988 "einline", /* name */ 1989 NULL, /* gate */ 1990 early_inliner, /* execute */ 1991 NULL, /* sub */ 1992 NULL, /* next */ 1993 0, /* static_pass_number */ 1994 TV_INLINE_HEURISTICS, /* tv_id */ 1995 PROP_ssa, /* properties_required */ 1996 0, /* properties_provided */ 1997 0, /* properties_destroyed */ 1998 0, /* todo_flags_start */ 1999 0 /* todo_flags_finish */ 2000 } 2001 }; 2002 2003 2004 /* When to run IPA inlining. Inlining of always-inline functions 2005 happens during early inlining. 2006 2007 Enable inlining unconditoinally at -flto. We need size estimates to 2008 drive partitioning. */ 2009 2010 static bool 2011 gate_ipa_inline (void) 2012 { 2013 return optimize || flag_lto || flag_wpa; 2014 } 2015 2016 struct ipa_opt_pass_d pass_ipa_inline = 2017 { 2018 { 2019 IPA_PASS, 2020 "inline", /* name */ 2021 gate_ipa_inline, /* gate */ 2022 ipa_inline, /* execute */ 2023 NULL, /* sub */ 2024 NULL, /* next */ 2025 0, /* static_pass_number */ 2026 TV_INLINE_HEURISTICS, /* tv_id */ 2027 0, /* properties_required */ 2028 0, /* properties_provided */ 2029 0, /* properties_destroyed */ 2030 TODO_remove_functions, /* todo_flags_finish */ 2031 TODO_dump_cgraph 2032 | TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */ 2033 }, 2034 inline_generate_summary, /* generate_summary */ 2035 inline_write_summary, /* write_summary */ 2036 inline_read_summary, /* read_summary */ 2037 NULL, /* write_optimization_summary */ 2038 NULL, /* read_optimization_summary */ 2039 NULL, /* stmt_fixup */ 2040 0, /* TODOs */ 2041 inline_transform, /* function_transform */ 2042 NULL, /* variable_transform */ 2043 }; 2044