1 /* Inlining decision heuristics. 2 Copyright (C) 2003-2015 Free Software Foundation, Inc. 3 Contributed by Jan Hubicka 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 /* Inlining decision heuristics 22 23 The implementation of inliner is organized as follows: 24 25 inlining heuristics limits 26 27 can_inline_edge_p allow to check that particular inlining is allowed 28 by the limits specified by user (allowed function growth, growth and so 29 on). 30 31 Functions are inlined when it is obvious the result is profitable (such 32 as functions called once or when inlining reduce code size). 33 In addition to that we perform inlining of small functions and recursive 34 inlining. 35 36 inlining heuristics 37 38 The inliner itself is split into two passes: 39 40 pass_early_inlining 41 42 Simple local inlining pass inlining callees into current function. 43 This pass makes no use of whole unit analysis and thus it can do only 44 very simple decisions based on local properties. 45 46 The strength of the pass is that it is run in topological order 47 (reverse postorder) on the callgraph. Functions are converted into SSA 48 form just before this pass and optimized subsequently. As a result, the 49 callees of the function seen by the early inliner was already optimized 50 and results of early inlining adds a lot of optimization opportunities 51 for the local optimization. 52 53 The pass handle the obvious inlining decisions within the compilation 54 unit - inlining auto inline functions, inlining for size and 55 flattening. 56 57 main strength of the pass is the ability to eliminate abstraction 58 penalty in C++ code (via combination of inlining and early 59 optimization) and thus improve quality of analysis done by real IPA 60 optimizers. 61 62 Because of lack of whole unit knowledge, the pass can not really make 63 good code size/performance tradeoffs. It however does very simple 64 speculative inlining allowing code size to grow by 65 EARLY_INLINING_INSNS when callee is leaf function. In this case the 66 optimizations performed later are very likely to eliminate the cost. 67 68 pass_ipa_inline 69 70 This is the real inliner able to handle inlining with whole program 71 knowledge. It performs following steps: 72 73 1) inlining of small functions. This is implemented by greedy 74 algorithm ordering all inlinable cgraph edges by their badness and 75 inlining them in this order as long as inline limits allows doing so. 76 77 This heuristics is not very good on inlining recursive calls. Recursive 78 calls can be inlined with results similar to loop unrolling. To do so, 79 special purpose recursive inliner is executed on function when 80 recursive edge is met as viable candidate. 81 82 2) Unreachable functions are removed from callgraph. Inlining leads 83 to devirtualization and other modification of callgraph so functions 84 may become unreachable during the process. Also functions declared as 85 extern inline or virtual functions are removed, since after inlining 86 we no longer need the offline bodies. 87 88 3) Functions called once and not exported from the unit are inlined. 89 This should almost always lead to reduction of code size by eliminating 90 the need for offline copy of the function. */ 91 92 #include "config.h" 93 #include "system.h" 94 #include "coretypes.h" 95 #include "tm.h" 96 #include "hash-set.h" 97 #include "machmode.h" 98 #include "vec.h" 99 #include "double-int.h" 100 #include "input.h" 101 #include "alias.h" 102 #include "symtab.h" 103 #include "wide-int.h" 104 #include "inchash.h" 105 #include "tree.h" 106 #include "fold-const.h" 107 #include "trans-mem.h" 108 #include "calls.h" 109 #include "tree-inline.h" 110 #include "langhooks.h" 111 #include "flags.h" 112 #include "diagnostic.h" 113 #include "gimple-pretty-print.h" 114 #include "params.h" 115 #include "intl.h" 116 #include "tree-pass.h" 117 #include "coverage.h" 118 #include "rtl.h" 119 #include "bitmap.h" 120 #include "profile.h" 121 #include "predict.h" 122 #include "hard-reg-set.h" 123 #include "input.h" 124 #include "function.h" 125 #include "basic-block.h" 126 #include "tree-ssa-alias.h" 127 #include "internal-fn.h" 128 #include "gimple-expr.h" 129 #include "is-a.h" 130 #include "gimple.h" 131 #include "gimple-ssa.h" 132 #include "hash-map.h" 133 #include "plugin-api.h" 134 #include "ipa-ref.h" 135 #include "cgraph.h" 136 #include "alloc-pool.h" 137 #include "symbol-summary.h" 138 #include "ipa-prop.h" 139 #include "except.h" 140 #include "target.h" 141 #include "ipa-inline.h" 142 #include "ipa-utils.h" 143 #include "sreal.h" 144 #include "auto-profile.h" 145 #include "builtins.h" 146 #include "fibonacci_heap.h" 147 #include "lto-streamer.h" 148 149 typedef fibonacci_heap <sreal, cgraph_edge> edge_heap_t; 150 typedef fibonacci_node <sreal, cgraph_edge> edge_heap_node_t; 151 152 /* Statistics we collect about inlining algorithm. */ 153 static int overall_size; 154 static gcov_type max_count; 155 static gcov_type spec_rem; 156 157 /* Pre-computed constants 1/CGRAPH_FREQ_BASE and 1/100. */ 158 static sreal cgraph_freq_base_rec, percent_rec; 159 160 /* Return false when inlining edge E would lead to violating 161 limits on function unit growth or stack usage growth. 162 163 The relative function body growth limit is present generally 164 to avoid problems with non-linear behavior of the compiler. 165 To allow inlining huge functions into tiny wrapper, the limit 166 is always based on the bigger of the two functions considered. 167 168 For stack growth limits we always base the growth in stack usage 169 of the callers. We want to prevent applications from segfaulting 170 on stack overflow when functions with huge stack frames gets 171 inlined. */ 172 173 static bool 174 caller_growth_limits (struct cgraph_edge *e) 175 { 176 struct cgraph_node *to = e->caller; 177 struct cgraph_node *what = e->callee->ultimate_alias_target (); 178 int newsize; 179 int limit = 0; 180 HOST_WIDE_INT stack_size_limit = 0, inlined_stack; 181 inline_summary *info, *what_info, *outer_info = inline_summaries->get (to); 182 183 /* Look for function e->caller is inlined to. While doing 184 so work out the largest function body on the way. As 185 described above, we want to base our function growth 186 limits based on that. Not on the self size of the 187 outer function, not on the self size of inline code 188 we immediately inline to. This is the most relaxed 189 interpretation of the rule "do not grow large functions 190 too much in order to prevent compiler from exploding". */ 191 while (true) 192 { 193 info = inline_summaries->get (to); 194 if (limit < info->self_size) 195 limit = info->self_size; 196 if (stack_size_limit < info->estimated_self_stack_size) 197 stack_size_limit = info->estimated_self_stack_size; 198 if (to->global.inlined_to) 199 to = to->callers->caller; 200 else 201 break; 202 } 203 204 what_info = inline_summaries->get (what); 205 206 if (limit < what_info->self_size) 207 limit = what_info->self_size; 208 209 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100; 210 211 /* Check the size after inlining against the function limits. But allow 212 the function to shrink if it went over the limits by forced inlining. */ 213 newsize = estimate_size_after_inlining (to, e); 214 if (newsize >= info->size 215 && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS) 216 && newsize > limit) 217 { 218 e->inline_failed = CIF_LARGE_FUNCTION_GROWTH_LIMIT; 219 return false; 220 } 221 222 if (!what_info->estimated_stack_size) 223 return true; 224 225 /* FIXME: Stack size limit often prevents inlining in Fortran programs 226 due to large i/o datastructures used by the Fortran front-end. 227 We ought to ignore this limit when we know that the edge is executed 228 on every invocation of the caller (i.e. its call statement dominates 229 exit block). We do not track this information, yet. */ 230 stack_size_limit += ((gcov_type)stack_size_limit 231 * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100); 232 233 inlined_stack = (outer_info->stack_frame_offset 234 + outer_info->estimated_self_stack_size 235 + what_info->estimated_stack_size); 236 /* Check new stack consumption with stack consumption at the place 237 stack is used. */ 238 if (inlined_stack > stack_size_limit 239 /* If function already has large stack usage from sibling 240 inline call, we can inline, too. 241 This bit overoptimistically assume that we are good at stack 242 packing. */ 243 && inlined_stack > info->estimated_stack_size 244 && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME)) 245 { 246 e->inline_failed = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT; 247 return false; 248 } 249 return true; 250 } 251 252 /* Dump info about why inlining has failed. */ 253 254 static void 255 report_inline_failed_reason (struct cgraph_edge *e) 256 { 257 if (dump_file) 258 { 259 fprintf (dump_file, " not inlinable: %s/%i -> %s/%i, %s\n", 260 xstrdup_for_dump (e->caller->name ()), e->caller->order, 261 xstrdup_for_dump (e->callee->name ()), e->callee->order, 262 cgraph_inline_failed_string (e->inline_failed)); 263 if ((e->inline_failed == CIF_TARGET_OPTION_MISMATCH 264 || e->inline_failed == CIF_OPTIMIZATION_MISMATCH) 265 && e->caller->lto_file_data 266 && e->callee->function_symbol ()->lto_file_data) 267 { 268 fprintf (dump_file, " LTO objects: %s, %s\n", 269 e->caller->lto_file_data->file_name, 270 e->callee->function_symbol ()->lto_file_data->file_name); 271 } 272 if (e->inline_failed == CIF_TARGET_OPTION_MISMATCH) 273 cl_target_option_print_diff 274 (dump_file, 2, target_opts_for_fn (e->caller->decl), 275 target_opts_for_fn (e->callee->ultimate_alias_target ()->decl)); 276 if (e->inline_failed == CIF_OPTIMIZATION_MISMATCH) 277 cl_optimization_print_diff 278 (dump_file, 2, opts_for_fn (e->caller->decl), 279 opts_for_fn (e->callee->ultimate_alias_target ()->decl)); 280 } 281 } 282 283 /* Decide whether sanitizer-related attributes allow inlining. */ 284 285 static bool 286 sanitize_attrs_match_for_inline_p (const_tree caller, const_tree callee) 287 { 288 /* Don't care if sanitizer is disabled */ 289 if (!(flag_sanitize & SANITIZE_ADDRESS)) 290 return true; 291 292 if (!caller || !callee) 293 return true; 294 295 return !!lookup_attribute ("no_sanitize_address", 296 DECL_ATTRIBUTES (caller)) == 297 !!lookup_attribute ("no_sanitize_address", 298 DECL_ATTRIBUTES (callee)); 299 } 300 301 /* Used for flags where it is safe to inline when caller's value is 302 grater than callee's. */ 303 #define check_maybe_up(flag) \ 304 (opts_for_fn (caller->decl)->x_##flag \ 305 != opts_for_fn (callee->decl)->x_##flag \ 306 && (!always_inline \ 307 || opts_for_fn (caller->decl)->x_##flag \ 308 < opts_for_fn (callee->decl)->x_##flag)) 309 /* Used for flags where it is safe to inline when caller's value is 310 smaller than callee's. */ 311 #define check_maybe_down(flag) \ 312 (opts_for_fn (caller->decl)->x_##flag \ 313 != opts_for_fn (callee->decl)->x_##flag \ 314 && (!always_inline \ 315 || opts_for_fn (caller->decl)->x_##flag \ 316 > opts_for_fn (callee->decl)->x_##flag)) 317 /* Used for flags where exact match is needed for correctness. */ 318 #define check_match(flag) \ 319 (opts_for_fn (caller->decl)->x_##flag \ 320 != opts_for_fn (callee->decl)->x_##flag) 321 322 /* Decide if we can inline the edge and possibly update 323 inline_failed reason. 324 We check whether inlining is possible at all and whether 325 caller growth limits allow doing so. 326 327 if REPORT is true, output reason to the dump file. 328 329 if DISREGARD_LIMITS is true, ignore size limits.*/ 330 331 static bool 332 can_inline_edge_p (struct cgraph_edge *e, bool report, 333 bool disregard_limits = false, bool early = false) 334 { 335 gcc_checking_assert (e->inline_failed); 336 337 if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR) 338 { 339 if (report) 340 report_inline_failed_reason (e); 341 return false; 342 } 343 344 bool inlinable = true; 345 enum availability avail; 346 cgraph_node *callee = e->callee->ultimate_alias_target (&avail); 347 cgraph_node *caller = e->caller->global.inlined_to 348 ? e->caller->global.inlined_to : e->caller; 349 tree caller_tree = DECL_FUNCTION_SPECIFIC_OPTIMIZATION (caller->decl); 350 tree callee_tree 351 = callee ? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee->decl) : NULL; 352 353 if (!callee->definition) 354 { 355 e->inline_failed = CIF_BODY_NOT_AVAILABLE; 356 inlinable = false; 357 } 358 else if (callee->calls_comdat_local) 359 { 360 e->inline_failed = CIF_USES_COMDAT_LOCAL; 361 inlinable = false; 362 } 363 else if (avail <= AVAIL_INTERPOSABLE) 364 { 365 e->inline_failed = CIF_OVERWRITABLE; 366 inlinable = false; 367 } 368 else if (e->call_stmt_cannot_inline_p) 369 { 370 if (e->inline_failed != CIF_FUNCTION_NOT_OPTIMIZED) 371 e->inline_failed = CIF_MISMATCHED_ARGUMENTS; 372 inlinable = false; 373 } 374 /* Don't inline if the functions have different EH personalities. */ 375 else if (DECL_FUNCTION_PERSONALITY (caller->decl) 376 && DECL_FUNCTION_PERSONALITY (callee->decl) 377 && (DECL_FUNCTION_PERSONALITY (caller->decl) 378 != DECL_FUNCTION_PERSONALITY (callee->decl))) 379 { 380 e->inline_failed = CIF_EH_PERSONALITY; 381 inlinable = false; 382 } 383 /* TM pure functions should not be inlined into non-TM_pure 384 functions. */ 385 else if (is_tm_pure (callee->decl) && !is_tm_pure (caller->decl)) 386 { 387 e->inline_failed = CIF_UNSPECIFIED; 388 inlinable = false; 389 } 390 /* Check compatibility of target optimization options. */ 391 else if (!targetm.target_option.can_inline_p (caller->decl, 392 callee->decl)) 393 { 394 e->inline_failed = CIF_TARGET_OPTION_MISMATCH; 395 inlinable = false; 396 } 397 else if (!inline_summaries->get (callee)->inlinable) 398 { 399 e->inline_failed = CIF_FUNCTION_NOT_INLINABLE; 400 inlinable = false; 401 } 402 else if (inline_summaries->get (caller)->contains_cilk_spawn) 403 { 404 e->inline_failed = CIF_CILK_SPAWN; 405 inlinable = false; 406 } 407 /* Don't inline a function with mismatched sanitization attributes. */ 408 else if (!sanitize_attrs_match_for_inline_p (caller->decl, callee->decl)) 409 { 410 e->inline_failed = CIF_ATTRIBUTE_MISMATCH; 411 inlinable = false; 412 } 413 /* Check if caller growth allows the inlining. */ 414 else if (!DECL_DISREGARD_INLINE_LIMITS (callee->decl) 415 && !disregard_limits 416 && !lookup_attribute ("flatten", 417 DECL_ATTRIBUTES (caller->decl)) 418 && !caller_growth_limits (e)) 419 inlinable = false; 420 /* Don't inline a function with a higher optimization level than the 421 caller. FIXME: this is really just tip of iceberg of handling 422 optimization attribute. */ 423 else if (caller_tree != callee_tree) 424 { 425 bool always_inline = 426 (DECL_DISREGARD_INLINE_LIMITS (callee->decl) 427 && lookup_attribute ("always_inline", 428 DECL_ATTRIBUTES (callee->decl))); 429 430 /* Until GCC 4.9 we did not check the semantics alterning flags 431 bellow and inline across optimization boundry. 432 Enabling checks bellow breaks several packages by refusing 433 to inline library always_inline functions. See PR65873. 434 Disable the check for early inlining for now until better solution 435 is found. */ 436 if (always_inline && early) 437 ; 438 /* There are some options that change IL semantics which means 439 we cannot inline in these cases for correctness reason. 440 Not even for always_inline declared functions. */ 441 /* Strictly speaking only when the callee contains signed integer 442 math where overflow is undefined. */ 443 else if ((check_maybe_up (flag_strict_overflow) 444 /* this flag is set by optimize. Allow inlining across 445 optimize boundary. */ 446 && (!opt_for_fn (caller->decl, optimize) 447 == !opt_for_fn (callee->decl, optimize) || !always_inline)) 448 || check_match (flag_wrapv) 449 || check_match (flag_trapv) 450 /* Strictly speaking only when the callee uses FP math. */ 451 || check_maybe_up (flag_rounding_math) 452 || check_maybe_up (flag_trapping_math) 453 || check_maybe_down (flag_unsafe_math_optimizations) 454 || check_maybe_down (flag_finite_math_only) 455 || check_maybe_up (flag_signaling_nans) 456 || check_maybe_down (flag_cx_limited_range) 457 || check_maybe_up (flag_signed_zeros) 458 || check_maybe_down (flag_associative_math) 459 || check_maybe_down (flag_reciprocal_math) 460 /* We do not want to make code compiled with exceptions to be 461 brought into a non-EH function unless we know that the callee 462 does not throw. 463 This is tracked by DECL_FUNCTION_PERSONALITY. */ 464 || (check_match (flag_non_call_exceptions) 465 /* TODO: We also may allow bringing !flag_non_call_exceptions 466 to flag_non_call_exceptions function, but that may need 467 extra work in tree-inline to add the extra EH edges. */ 468 && (!opt_for_fn (callee->decl, flag_non_call_exceptions) 469 || DECL_FUNCTION_PERSONALITY (callee->decl))) 470 || (check_maybe_up (flag_exceptions) 471 && DECL_FUNCTION_PERSONALITY (callee->decl)) 472 /* Strictly speaking only when the callee contains function 473 calls that may end up setting errno. */ 474 || check_maybe_up (flag_errno_math) 475 /* When devirtualization is diabled for callee, it is not safe 476 to inline it as we possibly mangled the type info. 477 Allow early inlining of always inlines. */ 478 || (!early && check_maybe_down (flag_devirtualize))) 479 { 480 e->inline_failed = CIF_OPTIMIZATION_MISMATCH; 481 inlinable = false; 482 } 483 /* gcc.dg/pr43564.c. Apply user-forced inline even at -O0. */ 484 else if (always_inline) 485 ; 486 /* When user added an attribute to the callee honor it. */ 487 else if (lookup_attribute ("optimize", DECL_ATTRIBUTES (callee->decl)) 488 && opts_for_fn (caller->decl) != opts_for_fn (callee->decl)) 489 { 490 e->inline_failed = CIF_OPTIMIZATION_MISMATCH; 491 inlinable = false; 492 } 493 /* If explicit optimize attribute are not used, the mismatch is caused 494 by different command line options used to build different units. 495 Do not care about COMDAT functions - those are intended to be 496 optimized with the optimization flags of module they are used in. 497 Also do not care about mixing up size/speed optimization when 498 DECL_DISREGARD_INLINE_LIMITS is set. */ 499 else if ((callee->merged 500 && !lookup_attribute ("optimize", 501 DECL_ATTRIBUTES (caller->decl))) 502 || DECL_DISREGARD_INLINE_LIMITS (callee->decl)) 503 ; 504 /* If mismatch is caused by merging two LTO units with different 505 optimizationflags we want to be bit nicer. However never inline 506 if one of functions is not optimized at all. */ 507 else if (!opt_for_fn (callee->decl, optimize) 508 || !opt_for_fn (caller->decl, optimize)) 509 { 510 e->inline_failed = CIF_OPTIMIZATION_MISMATCH; 511 inlinable = false; 512 } 513 /* If callee is optimized for size and caller is not, allow inlining if 514 code shrinks or we are in MAX_INLINE_INSNS_SINGLE limit and callee 515 is inline (and thus likely an unified comdat). This will allow caller 516 to run faster. */ 517 else if (opt_for_fn (callee->decl, optimize_size) 518 > opt_for_fn (caller->decl, optimize_size)) 519 { 520 int growth = estimate_edge_growth (e); 521 if (growth > 0 522 && (!DECL_DECLARED_INLINE_P (callee->decl) 523 && growth >= MAX (MAX_INLINE_INSNS_SINGLE, 524 MAX_INLINE_INSNS_AUTO))) 525 { 526 e->inline_failed = CIF_OPTIMIZATION_MISMATCH; 527 inlinable = false; 528 } 529 } 530 /* If callee is more aggressively optimized for performance than caller, 531 we generally want to inline only cheap (runtime wise) functions. */ 532 else if (opt_for_fn (callee->decl, optimize_size) 533 < opt_for_fn (caller->decl, optimize_size) 534 || (opt_for_fn (callee->decl, optimize) 535 > opt_for_fn (caller->decl, optimize))) 536 { 537 if (estimate_edge_time (e) 538 >= 20 + inline_edge_summary (e)->call_stmt_time) 539 { 540 e->inline_failed = CIF_OPTIMIZATION_MISMATCH; 541 inlinable = false; 542 } 543 } 544 545 } 546 547 if (!inlinable && report) 548 report_inline_failed_reason (e); 549 return inlinable; 550 } 551 552 553 /* Return true if the edge E is inlinable during early inlining. */ 554 555 static bool 556 can_early_inline_edge_p (struct cgraph_edge *e) 557 { 558 struct cgraph_node *callee = e->callee->ultimate_alias_target (); 559 /* Early inliner might get called at WPA stage when IPA pass adds new 560 function. In this case we can not really do any of early inlining 561 because function bodies are missing. */ 562 if (!gimple_has_body_p (callee->decl)) 563 { 564 e->inline_failed = CIF_BODY_NOT_AVAILABLE; 565 return false; 566 } 567 /* In early inliner some of callees may not be in SSA form yet 568 (i.e. the callgraph is cyclic and we did not process 569 the callee by early inliner, yet). We don't have CIF code for this 570 case; later we will re-do the decision in the real inliner. */ 571 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->caller->decl)) 572 || !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl))) 573 { 574 if (dump_file) 575 fprintf (dump_file, " edge not inlinable: not in SSA form\n"); 576 return false; 577 } 578 if (!can_inline_edge_p (e, true, false, true)) 579 return false; 580 return true; 581 } 582 583 584 /* Return number of calls in N. Ignore cheap builtins. */ 585 586 static int 587 num_calls (struct cgraph_node *n) 588 { 589 struct cgraph_edge *e; 590 int num = 0; 591 592 for (e = n->callees; e; e = e->next_callee) 593 if (!is_inexpensive_builtin (e->callee->decl)) 594 num++; 595 return num; 596 } 597 598 599 /* Return true if we are interested in inlining small function. */ 600 601 static bool 602 want_early_inline_function_p (struct cgraph_edge *e) 603 { 604 bool want_inline = true; 605 struct cgraph_node *callee = e->callee->ultimate_alias_target (); 606 607 if (DECL_DISREGARD_INLINE_LIMITS (callee->decl)) 608 ; 609 /* For AutoFDO, we need to make sure that before profile summary, all 610 hot paths' IR look exactly the same as profiled binary. As a result, 611 in einliner, we will disregard size limit and inline those callsites 612 that are: 613 * inlined in the profiled binary, and 614 * the cloned callee has enough samples to be considered "hot". */ 615 else if (flag_auto_profile && afdo_callsite_hot_enough_for_early_inline (e)) 616 ; 617 else if (!DECL_DECLARED_INLINE_P (callee->decl) 618 && !opt_for_fn (e->caller->decl, flag_inline_small_functions)) 619 { 620 e->inline_failed = CIF_FUNCTION_NOT_INLINE_CANDIDATE; 621 report_inline_failed_reason (e); 622 want_inline = false; 623 } 624 else 625 { 626 int growth = estimate_edge_growth (e); 627 int n; 628 629 if (growth <= 0) 630 ; 631 else if (!e->maybe_hot_p () 632 && growth > 0) 633 { 634 if (dump_file) 635 fprintf (dump_file, " will not early inline: %s/%i->%s/%i, " 636 "call is cold and code would grow by %i\n", 637 xstrdup_for_dump (e->caller->name ()), 638 e->caller->order, 639 xstrdup_for_dump (callee->name ()), callee->order, 640 growth); 641 want_inline = false; 642 } 643 else if (growth > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS)) 644 { 645 if (dump_file) 646 fprintf (dump_file, " will not early inline: %s/%i->%s/%i, " 647 "growth %i exceeds --param early-inlining-insns\n", 648 xstrdup_for_dump (e->caller->name ()), 649 e->caller->order, 650 xstrdup_for_dump (callee->name ()), callee->order, 651 growth); 652 want_inline = false; 653 } 654 else if ((n = num_calls (callee)) != 0 655 && growth * (n + 1) > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS)) 656 { 657 if (dump_file) 658 fprintf (dump_file, " will not early inline: %s/%i->%s/%i, " 659 "growth %i exceeds --param early-inlining-insns " 660 "divided by number of calls\n", 661 xstrdup_for_dump (e->caller->name ()), 662 e->caller->order, 663 xstrdup_for_dump (callee->name ()), callee->order, 664 growth); 665 want_inline = false; 666 } 667 } 668 return want_inline; 669 } 670 671 /* Compute time of the edge->caller + edge->callee execution when inlining 672 does not happen. */ 673 674 inline sreal 675 compute_uninlined_call_time (struct inline_summary *callee_info, 676 struct cgraph_edge *edge) 677 { 678 sreal uninlined_call_time = (sreal)callee_info->time; 679 cgraph_node *caller = (edge->caller->global.inlined_to 680 ? edge->caller->global.inlined_to 681 : edge->caller); 682 683 if (edge->count && caller->count) 684 uninlined_call_time *= (sreal)edge->count / caller->count; 685 if (edge->frequency) 686 uninlined_call_time *= cgraph_freq_base_rec * edge->frequency; 687 else 688 uninlined_call_time = uninlined_call_time >> 11; 689 690 int caller_time = inline_summaries->get (caller)->time; 691 return uninlined_call_time + caller_time; 692 } 693 694 /* Same as compute_uinlined_call_time but compute time when inlining 695 does happen. */ 696 697 inline sreal 698 compute_inlined_call_time (struct cgraph_edge *edge, 699 int edge_time) 700 { 701 cgraph_node *caller = (edge->caller->global.inlined_to 702 ? edge->caller->global.inlined_to 703 : edge->caller); 704 int caller_time = inline_summaries->get (caller)->time; 705 sreal time = edge_time; 706 707 if (edge->count && caller->count) 708 time *= (sreal)edge->count / caller->count; 709 if (edge->frequency) 710 time *= cgraph_freq_base_rec * edge->frequency; 711 else 712 time = time >> 11; 713 714 /* This calculation should match one in ipa-inline-analysis. 715 FIXME: Once ipa-inline-analysis is converted to sreal this can be 716 simplified. */ 717 time -= (sreal) ((gcov_type) edge->frequency 718 * inline_edge_summary (edge)->call_stmt_time 719 * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE)) / INLINE_TIME_SCALE; 720 time += caller_time; 721 if (time <= 0) 722 time = ((sreal) 1) >> 8; 723 gcc_checking_assert (time >= 0); 724 return time; 725 } 726 727 /* Return true if the speedup for inlining E is bigger than 728 PARAM_MAX_INLINE_MIN_SPEEDUP. */ 729 730 static bool 731 big_speedup_p (struct cgraph_edge *e) 732 { 733 sreal time = compute_uninlined_call_time (inline_summaries->get (e->callee), 734 e); 735 sreal inlined_time = compute_inlined_call_time (e, estimate_edge_time (e)); 736 737 if (time - inlined_time 738 > (sreal) time * PARAM_VALUE (PARAM_INLINE_MIN_SPEEDUP) 739 * percent_rec) 740 return true; 741 return false; 742 } 743 744 /* Return true if we are interested in inlining small function. 745 When REPORT is true, report reason to dump file. */ 746 747 static bool 748 want_inline_small_function_p (struct cgraph_edge *e, bool report) 749 { 750 bool want_inline = true; 751 struct cgraph_node *callee = e->callee->ultimate_alias_target (); 752 753 if (DECL_DISREGARD_INLINE_LIMITS (callee->decl)) 754 ; 755 else if (!DECL_DECLARED_INLINE_P (callee->decl) 756 && !opt_for_fn (e->caller->decl, flag_inline_small_functions)) 757 { 758 e->inline_failed = CIF_FUNCTION_NOT_INLINE_CANDIDATE; 759 want_inline = false; 760 } 761 /* Do fast and conservative check if the function can be good 762 inline candidate. At the moment we allow inline hints to 763 promote non-inline functions to inline and we increase 764 MAX_INLINE_INSNS_SINGLE 16-fold for inline functions. */ 765 else if ((!DECL_DECLARED_INLINE_P (callee->decl) 766 && (!e->count || !e->maybe_hot_p ())) 767 && inline_summaries->get (callee)->min_size 768 - inline_edge_summary (e)->call_stmt_size 769 > MAX (MAX_INLINE_INSNS_SINGLE, MAX_INLINE_INSNS_AUTO)) 770 { 771 e->inline_failed = CIF_MAX_INLINE_INSNS_AUTO_LIMIT; 772 want_inline = false; 773 } 774 else if ((DECL_DECLARED_INLINE_P (callee->decl) || e->count) 775 && inline_summaries->get (callee)->min_size 776 - inline_edge_summary (e)->call_stmt_size 777 > 16 * MAX_INLINE_INSNS_SINGLE) 778 { 779 e->inline_failed = (DECL_DECLARED_INLINE_P (callee->decl) 780 ? CIF_MAX_INLINE_INSNS_SINGLE_LIMIT 781 : CIF_MAX_INLINE_INSNS_AUTO_LIMIT); 782 want_inline = false; 783 } 784 else 785 { 786 int growth = estimate_edge_growth (e); 787 inline_hints hints = estimate_edge_hints (e); 788 bool big_speedup = big_speedup_p (e); 789 790 if (growth <= 0) 791 ; 792 /* Apply MAX_INLINE_INSNS_SINGLE limit. Do not do so when 793 hints suggests that inlining given function is very profitable. */ 794 else if (DECL_DECLARED_INLINE_P (callee->decl) 795 && growth >= MAX_INLINE_INSNS_SINGLE 796 && ((!big_speedup 797 && !(hints & (INLINE_HINT_indirect_call 798 | INLINE_HINT_known_hot 799 | INLINE_HINT_loop_iterations 800 | INLINE_HINT_array_index 801 | INLINE_HINT_loop_stride))) 802 || growth >= MAX_INLINE_INSNS_SINGLE * 16)) 803 { 804 e->inline_failed = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT; 805 want_inline = false; 806 } 807 else if (!DECL_DECLARED_INLINE_P (callee->decl) 808 && !opt_for_fn (e->caller->decl, flag_inline_functions)) 809 { 810 /* growth_likely_positive is expensive, always test it last. */ 811 if (growth >= MAX_INLINE_INSNS_SINGLE 812 || growth_likely_positive (callee, growth)) 813 { 814 e->inline_failed = CIF_NOT_DECLARED_INLINED; 815 want_inline = false; 816 } 817 } 818 /* Apply MAX_INLINE_INSNS_AUTO limit for functions not declared inline 819 Upgrade it to MAX_INLINE_INSNS_SINGLE when hints suggests that 820 inlining given function is very profitable. */ 821 else if (!DECL_DECLARED_INLINE_P (callee->decl) 822 && !big_speedup 823 && !(hints & INLINE_HINT_known_hot) 824 && growth >= ((hints & (INLINE_HINT_indirect_call 825 | INLINE_HINT_loop_iterations 826 | INLINE_HINT_array_index 827 | INLINE_HINT_loop_stride)) 828 ? MAX (MAX_INLINE_INSNS_AUTO, 829 MAX_INLINE_INSNS_SINGLE) 830 : MAX_INLINE_INSNS_AUTO)) 831 { 832 /* growth_likely_positive is expensive, always test it last. */ 833 if (growth >= MAX_INLINE_INSNS_SINGLE 834 || growth_likely_positive (callee, growth)) 835 { 836 e->inline_failed = CIF_MAX_INLINE_INSNS_AUTO_LIMIT; 837 want_inline = false; 838 } 839 } 840 /* If call is cold, do not inline when function body would grow. */ 841 else if (!e->maybe_hot_p () 842 && (growth >= MAX_INLINE_INSNS_SINGLE 843 || growth_likely_positive (callee, growth))) 844 { 845 e->inline_failed = CIF_UNLIKELY_CALL; 846 want_inline = false; 847 } 848 } 849 if (!want_inline && report) 850 report_inline_failed_reason (e); 851 return want_inline; 852 } 853 854 /* EDGE is self recursive edge. 855 We hand two cases - when function A is inlining into itself 856 or when function A is being inlined into another inliner copy of function 857 A within function B. 858 859 In first case OUTER_NODE points to the toplevel copy of A, while 860 in the second case OUTER_NODE points to the outermost copy of A in B. 861 862 In both cases we want to be extra selective since 863 inlining the call will just introduce new recursive calls to appear. */ 864 865 static bool 866 want_inline_self_recursive_call_p (struct cgraph_edge *edge, 867 struct cgraph_node *outer_node, 868 bool peeling, 869 int depth) 870 { 871 char const *reason = NULL; 872 bool want_inline = true; 873 int caller_freq = CGRAPH_FREQ_BASE; 874 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO); 875 876 if (DECL_DECLARED_INLINE_P (edge->caller->decl)) 877 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH); 878 879 if (!edge->maybe_hot_p ()) 880 { 881 reason = "recursive call is cold"; 882 want_inline = false; 883 } 884 else if (max_count && !outer_node->count) 885 { 886 reason = "not executed in profile"; 887 want_inline = false; 888 } 889 else if (depth > max_depth) 890 { 891 reason = "--param max-inline-recursive-depth exceeded."; 892 want_inline = false; 893 } 894 895 if (outer_node->global.inlined_to) 896 caller_freq = outer_node->callers->frequency; 897 898 if (!caller_freq) 899 { 900 reason = "function is inlined and unlikely"; 901 want_inline = false; 902 } 903 904 if (!want_inline) 905 ; 906 /* Inlining of self recursive function into copy of itself within other function 907 is transformation similar to loop peeling. 908 909 Peeling is profitable if we can inline enough copies to make probability 910 of actual call to the self recursive function very small. Be sure that 911 the probability of recursion is small. 912 913 We ensure that the frequency of recursing is at most 1 - (1/max_depth). 914 This way the expected number of recision is at most max_depth. */ 915 else if (peeling) 916 { 917 int max_prob = CGRAPH_FREQ_BASE - ((CGRAPH_FREQ_BASE + max_depth - 1) 918 / max_depth); 919 int i; 920 for (i = 1; i < depth; i++) 921 max_prob = max_prob * max_prob / CGRAPH_FREQ_BASE; 922 if (max_count 923 && (edge->count * CGRAPH_FREQ_BASE / outer_node->count 924 >= max_prob)) 925 { 926 reason = "profile of recursive call is too large"; 927 want_inline = false; 928 } 929 if (!max_count 930 && (edge->frequency * CGRAPH_FREQ_BASE / caller_freq 931 >= max_prob)) 932 { 933 reason = "frequency of recursive call is too large"; 934 want_inline = false; 935 } 936 } 937 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion 938 depth is large. We reduce function call overhead and increase chances that 939 things fit in hardware return predictor. 940 941 Recursive inlining might however increase cost of stack frame setup 942 actually slowing down functions whose recursion tree is wide rather than 943 deep. 944 945 Deciding reliably on when to do recursive inlining without profile feedback 946 is tricky. For now we disable recursive inlining when probability of self 947 recursion is low. 948 949 Recursive inlining of self recursive call within loop also results in large loop 950 depths that generally optimize badly. We may want to throttle down inlining 951 in those cases. In particular this seems to happen in one of libstdc++ rb tree 952 methods. */ 953 else 954 { 955 if (max_count 956 && (edge->count * 100 / outer_node->count 957 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY))) 958 { 959 reason = "profile of recursive call is too small"; 960 want_inline = false; 961 } 962 else if (!max_count 963 && (edge->frequency * 100 / caller_freq 964 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY))) 965 { 966 reason = "frequency of recursive call is too small"; 967 want_inline = false; 968 } 969 } 970 if (!want_inline && dump_file) 971 fprintf (dump_file, " not inlining recursively: %s\n", reason); 972 return want_inline; 973 } 974 975 /* Return true when NODE has uninlinable caller; 976 set HAS_HOT_CALL if it has hot call. 977 Worker for cgraph_for_node_and_aliases. */ 978 979 static bool 980 check_callers (struct cgraph_node *node, void *has_hot_call) 981 { 982 struct cgraph_edge *e; 983 for (e = node->callers; e; e = e->next_caller) 984 { 985 if (!opt_for_fn (e->caller->decl, flag_inline_functions_called_once)) 986 return true; 987 if (!can_inline_edge_p (e, true)) 988 return true; 989 if (e->recursive_p ()) 990 return true; 991 if (!(*(bool *)has_hot_call) && e->maybe_hot_p ()) 992 *(bool *)has_hot_call = true; 993 } 994 return false; 995 } 996 997 /* If NODE has a caller, return true. */ 998 999 static bool 1000 has_caller_p (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED) 1001 { 1002 if (node->callers) 1003 return true; 1004 return false; 1005 } 1006 1007 /* Decide if inlining NODE would reduce unit size by eliminating 1008 the offline copy of function. 1009 When COLD is true the cold calls are considered, too. */ 1010 1011 static bool 1012 want_inline_function_to_all_callers_p (struct cgraph_node *node, bool cold) 1013 { 1014 bool has_hot_call = false; 1015 1016 /* Aliases gets inlined along with the function they alias. */ 1017 if (node->alias) 1018 return false; 1019 /* Already inlined? */ 1020 if (node->global.inlined_to) 1021 return false; 1022 /* Does it have callers? */ 1023 if (!node->call_for_symbol_and_aliases (has_caller_p, NULL, true)) 1024 return false; 1025 /* Inlining into all callers would increase size? */ 1026 if (estimate_growth (node) > 0) 1027 return false; 1028 /* All inlines must be possible. */ 1029 if (node->call_for_symbol_and_aliases (check_callers, &has_hot_call, 1030 true)) 1031 return false; 1032 if (!cold && !has_hot_call) 1033 return false; 1034 return true; 1035 } 1036 1037 /* A cost model driving the inlining heuristics in a way so the edges with 1038 smallest badness are inlined first. After each inlining is performed 1039 the costs of all caller edges of nodes affected are recomputed so the 1040 metrics may accurately depend on values such as number of inlinable callers 1041 of the function or function body size. */ 1042 1043 static sreal 1044 edge_badness (struct cgraph_edge *edge, bool dump) 1045 { 1046 sreal badness; 1047 int growth, edge_time; 1048 struct cgraph_node *callee = edge->callee->ultimate_alias_target (); 1049 struct inline_summary *callee_info = inline_summaries->get (callee); 1050 inline_hints hints; 1051 cgraph_node *caller = (edge->caller->global.inlined_to 1052 ? edge->caller->global.inlined_to 1053 : edge->caller); 1054 1055 growth = estimate_edge_growth (edge); 1056 edge_time = estimate_edge_time (edge); 1057 hints = estimate_edge_hints (edge); 1058 gcc_checking_assert (edge_time >= 0); 1059 gcc_checking_assert (edge_time <= callee_info->time); 1060 gcc_checking_assert (growth <= callee_info->size); 1061 1062 if (dump) 1063 { 1064 fprintf (dump_file, " Badness calculation for %s/%i -> %s/%i\n", 1065 xstrdup_for_dump (edge->caller->name ()), 1066 edge->caller->order, 1067 xstrdup_for_dump (callee->name ()), 1068 edge->callee->order); 1069 fprintf (dump_file, " size growth %i, time %i ", 1070 growth, 1071 edge_time); 1072 dump_inline_hints (dump_file, hints); 1073 if (big_speedup_p (edge)) 1074 fprintf (dump_file, " big_speedup"); 1075 fprintf (dump_file, "\n"); 1076 } 1077 1078 /* Always prefer inlining saving code size. */ 1079 if (growth <= 0) 1080 { 1081 badness = (sreal) (-SREAL_MIN_SIG + growth) << (SREAL_MAX_EXP / 256); 1082 if (dump) 1083 fprintf (dump_file, " %f: Growth %d <= 0\n", badness.to_double (), 1084 growth); 1085 } 1086 /* Inlining into EXTERNAL functions is not going to change anything unless 1087 they are themselves inlined. */ 1088 else if (DECL_EXTERNAL (caller->decl)) 1089 { 1090 if (dump) 1091 fprintf (dump_file, " max: function is external\n"); 1092 return sreal::max (); 1093 } 1094 /* When profile is available. Compute badness as: 1095 1096 time_saved * caller_count 1097 goodness = ------------------------------------------------- 1098 growth_of_caller * overall_growth * combined_size 1099 1100 badness = - goodness 1101 1102 Again use negative value to make calls with profile appear hotter 1103 then calls without. 1104 */ 1105 else if (opt_for_fn (caller->decl, flag_guess_branch_prob) || caller->count) 1106 { 1107 sreal numerator, denominator; 1108 int overall_growth; 1109 1110 numerator = (compute_uninlined_call_time (callee_info, edge) 1111 - compute_inlined_call_time (edge, edge_time)); 1112 if (numerator == 0) 1113 numerator = ((sreal) 1 >> 8); 1114 if (caller->count) 1115 numerator *= caller->count; 1116 else if (opt_for_fn (caller->decl, flag_branch_probabilities)) 1117 numerator = numerator >> 11; 1118 denominator = growth; 1119 1120 overall_growth = callee_info->growth; 1121 1122 /* Look for inliner wrappers of the form: 1123 1124 inline_caller () 1125 { 1126 do_fast_job... 1127 if (need_more_work) 1128 noninline_callee (); 1129 } 1130 Withhout panilizing this case, we usually inline noninline_callee 1131 into the inline_caller because overall_growth is small preventing 1132 further inlining of inline_caller. 1133 1134 Penalize only callgraph edges to functions with small overall 1135 growth ... 1136 */ 1137 if (growth > overall_growth 1138 /* ... and having only one caller which is not inlined ... */ 1139 && callee_info->single_caller 1140 && !edge->caller->global.inlined_to 1141 /* ... and edges executed only conditionally ... */ 1142 && edge->frequency < CGRAPH_FREQ_BASE 1143 /* ... consider case where callee is not inline but caller is ... */ 1144 && ((!DECL_DECLARED_INLINE_P (edge->callee->decl) 1145 && DECL_DECLARED_INLINE_P (caller->decl)) 1146 /* ... or when early optimizers decided to split and edge 1147 frequency still indicates splitting is a win ... */ 1148 || (callee->split_part && !caller->split_part 1149 && edge->frequency 1150 < CGRAPH_FREQ_BASE 1151 * PARAM_VALUE 1152 (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY) / 100 1153 /* ... and do not overwrite user specified hints. */ 1154 && (!DECL_DECLARED_INLINE_P (edge->callee->decl) 1155 || DECL_DECLARED_INLINE_P (caller->decl))))) 1156 { 1157 struct inline_summary *caller_info = inline_summaries->get (caller); 1158 int caller_growth = caller_info->growth; 1159 1160 /* Only apply the penalty when caller looks like inline candidate, 1161 and it is not called once and. */ 1162 if (!caller_info->single_caller && overall_growth < caller_growth 1163 && caller_info->inlinable 1164 && caller_info->size 1165 < (DECL_DECLARED_INLINE_P (caller->decl) 1166 ? MAX_INLINE_INSNS_SINGLE : MAX_INLINE_INSNS_AUTO)) 1167 { 1168 if (dump) 1169 fprintf (dump_file, 1170 " Wrapper penalty. Increasing growth %i to %i\n", 1171 overall_growth, caller_growth); 1172 overall_growth = caller_growth; 1173 } 1174 } 1175 if (overall_growth > 0) 1176 { 1177 /* Strongly preffer functions with few callers that can be inlined 1178 fully. The square root here leads to smaller binaries at average. 1179 Watch however for extreme cases and return to linear function 1180 when growth is large. */ 1181 if (overall_growth < 256) 1182 overall_growth *= overall_growth; 1183 else 1184 overall_growth += 256 * 256 - 256; 1185 denominator *= overall_growth; 1186 } 1187 denominator *= inline_summaries->get (caller)->self_size + growth; 1188 1189 badness = - numerator / denominator; 1190 1191 if (dump) 1192 { 1193 fprintf (dump_file, 1194 " %f: guessed profile. frequency %f, count %"PRId64 1195 " caller count %"PRId64 1196 " time w/o inlining %f, time w inlining %f" 1197 " overall growth %i (current) %i (original)" 1198 " %i (compensated)\n", 1199 badness.to_double (), 1200 (double)edge->frequency / CGRAPH_FREQ_BASE, 1201 edge->count, caller->count, 1202 compute_uninlined_call_time (callee_info, edge).to_double (), 1203 compute_inlined_call_time (edge, edge_time).to_double (), 1204 estimate_growth (callee), 1205 callee_info->growth, overall_growth); 1206 } 1207 } 1208 /* When function local profile is not available or it does not give 1209 useful information (ie frequency is zero), base the cost on 1210 loop nest and overall size growth, so we optimize for overall number 1211 of functions fully inlined in program. */ 1212 else 1213 { 1214 int nest = MIN (inline_edge_summary (edge)->loop_depth, 8); 1215 badness = growth; 1216 1217 /* Decrease badness if call is nested. */ 1218 if (badness > 0) 1219 badness = badness >> nest; 1220 else 1221 badness = badness << nest; 1222 if (dump) 1223 fprintf (dump_file, " %f: no profile. nest %i\n", 1224 badness.to_double (), nest); 1225 } 1226 gcc_checking_assert (badness != 0); 1227 1228 if (edge->recursive_p ()) 1229 badness = badness.shift (badness > 0 ? 4 : -4); 1230 if ((hints & (INLINE_HINT_indirect_call 1231 | INLINE_HINT_loop_iterations 1232 | INLINE_HINT_array_index 1233 | INLINE_HINT_loop_stride)) 1234 || callee_info->growth <= 0) 1235 badness = badness.shift (badness > 0 ? -2 : 2); 1236 if (hints & (INLINE_HINT_same_scc)) 1237 badness = badness.shift (badness > 0 ? 3 : -3); 1238 else if (hints & (INLINE_HINT_in_scc)) 1239 badness = badness.shift (badness > 0 ? 2 : -2); 1240 else if (hints & (INLINE_HINT_cross_module)) 1241 badness = badness.shift (badness > 0 ? 1 : -1); 1242 if (DECL_DISREGARD_INLINE_LIMITS (callee->decl)) 1243 badness = badness.shift (badness > 0 ? -4 : 4); 1244 else if ((hints & INLINE_HINT_declared_inline)) 1245 badness = badness.shift (badness > 0 ? -3 : 3); 1246 if (dump) 1247 fprintf (dump_file, " Adjusted by hints %f\n", badness.to_double ()); 1248 return badness; 1249 } 1250 1251 /* Recompute badness of EDGE and update its key in HEAP if needed. */ 1252 static inline void 1253 update_edge_key (edge_heap_t *heap, struct cgraph_edge *edge) 1254 { 1255 sreal badness = edge_badness (edge, false); 1256 if (edge->aux) 1257 { 1258 edge_heap_node_t *n = (edge_heap_node_t *) edge->aux; 1259 gcc_checking_assert (n->get_data () == edge); 1260 1261 /* fibonacci_heap::replace_key does busy updating of the 1262 heap that is unnecesarily expensive. 1263 We do lazy increases: after extracting minimum if the key 1264 turns out to be out of date, it is re-inserted into heap 1265 with correct value. */ 1266 if (badness < n->get_key ()) 1267 { 1268 if (dump_file && (dump_flags & TDF_DETAILS)) 1269 { 1270 fprintf (dump_file, 1271 " decreasing badness %s/%i -> %s/%i, %f" 1272 " to %f\n", 1273 xstrdup_for_dump (edge->caller->name ()), 1274 edge->caller->order, 1275 xstrdup_for_dump (edge->callee->name ()), 1276 edge->callee->order, 1277 n->get_key ().to_double (), 1278 badness.to_double ()); 1279 } 1280 heap->decrease_key (n, badness); 1281 } 1282 } 1283 else 1284 { 1285 if (dump_file && (dump_flags & TDF_DETAILS)) 1286 { 1287 fprintf (dump_file, 1288 " enqueuing call %s/%i -> %s/%i, badness %f\n", 1289 xstrdup_for_dump (edge->caller->name ()), 1290 edge->caller->order, 1291 xstrdup_for_dump (edge->callee->name ()), 1292 edge->callee->order, 1293 badness.to_double ()); 1294 } 1295 edge->aux = heap->insert (badness, edge); 1296 } 1297 } 1298 1299 1300 /* NODE was inlined. 1301 All caller edges needs to be resetted because 1302 size estimates change. Similarly callees needs reset 1303 because better context may be known. */ 1304 1305 static void 1306 reset_edge_caches (struct cgraph_node *node) 1307 { 1308 struct cgraph_edge *edge; 1309 struct cgraph_edge *e = node->callees; 1310 struct cgraph_node *where = node; 1311 struct ipa_ref *ref; 1312 1313 if (where->global.inlined_to) 1314 where = where->global.inlined_to; 1315 1316 for (edge = where->callers; edge; edge = edge->next_caller) 1317 if (edge->inline_failed) 1318 reset_edge_growth_cache (edge); 1319 1320 FOR_EACH_ALIAS (where, ref) 1321 reset_edge_caches (dyn_cast <cgraph_node *> (ref->referring)); 1322 1323 if (!e) 1324 return; 1325 1326 while (true) 1327 if (!e->inline_failed && e->callee->callees) 1328 e = e->callee->callees; 1329 else 1330 { 1331 if (e->inline_failed) 1332 reset_edge_growth_cache (e); 1333 if (e->next_callee) 1334 e = e->next_callee; 1335 else 1336 { 1337 do 1338 { 1339 if (e->caller == node) 1340 return; 1341 e = e->caller->callers; 1342 } 1343 while (!e->next_callee); 1344 e = e->next_callee; 1345 } 1346 } 1347 } 1348 1349 /* Recompute HEAP nodes for each of caller of NODE. 1350 UPDATED_NODES track nodes we already visited, to avoid redundant work. 1351 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that 1352 it is inlinable. Otherwise check all edges. */ 1353 1354 static void 1355 update_caller_keys (edge_heap_t *heap, struct cgraph_node *node, 1356 bitmap updated_nodes, 1357 struct cgraph_edge *check_inlinablity_for) 1358 { 1359 struct cgraph_edge *edge; 1360 struct ipa_ref *ref; 1361 1362 if ((!node->alias && !inline_summaries->get (node)->inlinable) 1363 || node->global.inlined_to) 1364 return; 1365 if (!bitmap_set_bit (updated_nodes, node->uid)) 1366 return; 1367 1368 FOR_EACH_ALIAS (node, ref) 1369 { 1370 struct cgraph_node *alias = dyn_cast <cgraph_node *> (ref->referring); 1371 update_caller_keys (heap, alias, updated_nodes, check_inlinablity_for); 1372 } 1373 1374 for (edge = node->callers; edge; edge = edge->next_caller) 1375 if (edge->inline_failed) 1376 { 1377 if (!check_inlinablity_for 1378 || check_inlinablity_for == edge) 1379 { 1380 if (can_inline_edge_p (edge, false) 1381 && want_inline_small_function_p (edge, false)) 1382 update_edge_key (heap, edge); 1383 else if (edge->aux) 1384 { 1385 report_inline_failed_reason (edge); 1386 heap->delete_node ((edge_heap_node_t *) edge->aux); 1387 edge->aux = NULL; 1388 } 1389 } 1390 else if (edge->aux) 1391 update_edge_key (heap, edge); 1392 } 1393 } 1394 1395 /* Recompute HEAP nodes for each uninlined call in NODE. 1396 This is used when we know that edge badnesses are going only to increase 1397 (we introduced new call site) and thus all we need is to insert newly 1398 created edges into heap. */ 1399 1400 static void 1401 update_callee_keys (edge_heap_t *heap, struct cgraph_node *node, 1402 bitmap updated_nodes) 1403 { 1404 struct cgraph_edge *e = node->callees; 1405 1406 if (!e) 1407 return; 1408 while (true) 1409 if (!e->inline_failed && e->callee->callees) 1410 e = e->callee->callees; 1411 else 1412 { 1413 enum availability avail; 1414 struct cgraph_node *callee; 1415 /* We do not reset callee growth cache here. Since we added a new call, 1416 growth chould have just increased and consequentely badness metric 1417 don't need updating. */ 1418 if (e->inline_failed 1419 && (callee = e->callee->ultimate_alias_target (&avail)) 1420 && inline_summaries->get (callee)->inlinable 1421 && avail >= AVAIL_AVAILABLE 1422 && !bitmap_bit_p (updated_nodes, callee->uid)) 1423 { 1424 if (can_inline_edge_p (e, false) 1425 && want_inline_small_function_p (e, false)) 1426 update_edge_key (heap, e); 1427 else if (e->aux) 1428 { 1429 report_inline_failed_reason (e); 1430 heap->delete_node ((edge_heap_node_t *) e->aux); 1431 e->aux = NULL; 1432 } 1433 } 1434 if (e->next_callee) 1435 e = e->next_callee; 1436 else 1437 { 1438 do 1439 { 1440 if (e->caller == node) 1441 return; 1442 e = e->caller->callers; 1443 } 1444 while (!e->next_callee); 1445 e = e->next_callee; 1446 } 1447 } 1448 } 1449 1450 /* Enqueue all recursive calls from NODE into priority queue depending on 1451 how likely we want to recursively inline the call. */ 1452 1453 static void 1454 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where, 1455 edge_heap_t *heap) 1456 { 1457 struct cgraph_edge *e; 1458 enum availability avail; 1459 1460 for (e = where->callees; e; e = e->next_callee) 1461 if (e->callee == node 1462 || (e->callee->ultimate_alias_target (&avail) == node 1463 && avail > AVAIL_INTERPOSABLE)) 1464 { 1465 /* When profile feedback is available, prioritize by expected number 1466 of calls. */ 1467 heap->insert (!max_count ? -e->frequency 1468 : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))), 1469 e); 1470 } 1471 for (e = where->callees; e; e = e->next_callee) 1472 if (!e->inline_failed) 1473 lookup_recursive_calls (node, e->callee, heap); 1474 } 1475 1476 /* Decide on recursive inlining: in the case function has recursive calls, 1477 inline until body size reaches given argument. If any new indirect edges 1478 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES 1479 is NULL. */ 1480 1481 static bool 1482 recursive_inlining (struct cgraph_edge *edge, 1483 vec<cgraph_edge *> *new_edges) 1484 { 1485 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO); 1486 edge_heap_t heap (sreal::min ()); 1487 struct cgraph_node *node; 1488 struct cgraph_edge *e; 1489 struct cgraph_node *master_clone = NULL, *next; 1490 int depth = 0; 1491 int n = 0; 1492 1493 node = edge->caller; 1494 if (node->global.inlined_to) 1495 node = node->global.inlined_to; 1496 1497 if (DECL_DECLARED_INLINE_P (node->decl)) 1498 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE); 1499 1500 /* Make sure that function is small enough to be considered for inlining. */ 1501 if (estimate_size_after_inlining (node, edge) >= limit) 1502 return false; 1503 lookup_recursive_calls (node, node, &heap); 1504 if (heap.empty ()) 1505 return false; 1506 1507 if (dump_file) 1508 fprintf (dump_file, 1509 " Performing recursive inlining on %s\n", 1510 node->name ()); 1511 1512 /* Do the inlining and update list of recursive call during process. */ 1513 while (!heap.empty ()) 1514 { 1515 struct cgraph_edge *curr = heap.extract_min (); 1516 struct cgraph_node *cnode, *dest = curr->callee; 1517 1518 if (!can_inline_edge_p (curr, true)) 1519 continue; 1520 1521 /* MASTER_CLONE is produced in the case we already started modified 1522 the function. Be sure to redirect edge to the original body before 1523 estimating growths otherwise we will be seeing growths after inlining 1524 the already modified body. */ 1525 if (master_clone) 1526 { 1527 curr->redirect_callee (master_clone); 1528 reset_edge_growth_cache (curr); 1529 } 1530 1531 if (estimate_size_after_inlining (node, curr) > limit) 1532 { 1533 curr->redirect_callee (dest); 1534 reset_edge_growth_cache (curr); 1535 break; 1536 } 1537 1538 depth = 1; 1539 for (cnode = curr->caller; 1540 cnode->global.inlined_to; cnode = cnode->callers->caller) 1541 if (node->decl 1542 == curr->callee->ultimate_alias_target ()->decl) 1543 depth++; 1544 1545 if (!want_inline_self_recursive_call_p (curr, node, false, depth)) 1546 { 1547 curr->redirect_callee (dest); 1548 reset_edge_growth_cache (curr); 1549 continue; 1550 } 1551 1552 if (dump_file) 1553 { 1554 fprintf (dump_file, 1555 " Inlining call of depth %i", depth); 1556 if (node->count) 1557 { 1558 fprintf (dump_file, " called approx. %.2f times per call", 1559 (double)curr->count / node->count); 1560 } 1561 fprintf (dump_file, "\n"); 1562 } 1563 if (!master_clone) 1564 { 1565 /* We need original clone to copy around. */ 1566 master_clone = node->create_clone (node->decl, node->count, 1567 CGRAPH_FREQ_BASE, false, vNULL, 1568 true, NULL, NULL); 1569 for (e = master_clone->callees; e; e = e->next_callee) 1570 if (!e->inline_failed) 1571 clone_inlined_nodes (e, true, false, NULL, CGRAPH_FREQ_BASE); 1572 curr->redirect_callee (master_clone); 1573 reset_edge_growth_cache (curr); 1574 } 1575 1576 inline_call (curr, false, new_edges, &overall_size, true); 1577 lookup_recursive_calls (node, curr->callee, &heap); 1578 n++; 1579 } 1580 1581 if (!heap.empty () && dump_file) 1582 fprintf (dump_file, " Recursive inlining growth limit met.\n"); 1583 1584 if (!master_clone) 1585 return false; 1586 1587 if (dump_file) 1588 fprintf (dump_file, 1589 "\n Inlined %i times, " 1590 "body grown from size %i to %i, time %i to %i\n", n, 1591 inline_summaries->get (master_clone)->size, inline_summaries->get (node)->size, 1592 inline_summaries->get (master_clone)->time, inline_summaries->get (node)->time); 1593 1594 /* Remove master clone we used for inlining. We rely that clones inlined 1595 into master clone gets queued just before master clone so we don't 1596 need recursion. */ 1597 for (node = symtab->first_function (); node != master_clone; 1598 node = next) 1599 { 1600 next = symtab->next_function (node); 1601 if (node->global.inlined_to == master_clone) 1602 node->remove (); 1603 } 1604 master_clone->remove (); 1605 return true; 1606 } 1607 1608 1609 /* Given whole compilation unit estimate of INSNS, compute how large we can 1610 allow the unit to grow. */ 1611 1612 static int 1613 compute_max_insns (int insns) 1614 { 1615 int max_insns = insns; 1616 if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS)) 1617 max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS); 1618 1619 return ((int64_t) max_insns 1620 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100); 1621 } 1622 1623 1624 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */ 1625 1626 static void 1627 add_new_edges_to_heap (edge_heap_t *heap, vec<cgraph_edge *> new_edges) 1628 { 1629 while (new_edges.length () > 0) 1630 { 1631 struct cgraph_edge *edge = new_edges.pop (); 1632 1633 gcc_assert (!edge->aux); 1634 if (edge->inline_failed 1635 && can_inline_edge_p (edge, true) 1636 && want_inline_small_function_p (edge, true)) 1637 edge->aux = heap->insert (edge_badness (edge, false), edge); 1638 } 1639 } 1640 1641 /* Remove EDGE from the fibheap. */ 1642 1643 static void 1644 heap_edge_removal_hook (struct cgraph_edge *e, void *data) 1645 { 1646 if (e->aux) 1647 { 1648 ((edge_heap_t *)data)->delete_node ((edge_heap_node_t *)e->aux); 1649 e->aux = NULL; 1650 } 1651 } 1652 1653 /* Return true if speculation of edge E seems useful. 1654 If ANTICIPATE_INLINING is true, be conservative and hope that E 1655 may get inlined. */ 1656 1657 bool 1658 speculation_useful_p (struct cgraph_edge *e, bool anticipate_inlining) 1659 { 1660 enum availability avail; 1661 struct cgraph_node *target = e->callee->ultimate_alias_target (&avail); 1662 struct cgraph_edge *direct, *indirect; 1663 struct ipa_ref *ref; 1664 1665 gcc_assert (e->speculative && !e->indirect_unknown_callee); 1666 1667 if (!e->maybe_hot_p ()) 1668 return false; 1669 1670 /* See if IP optimizations found something potentially useful about the 1671 function. For now we look only for CONST/PURE flags. Almost everything 1672 else we propagate is useless. */ 1673 if (avail >= AVAIL_AVAILABLE) 1674 { 1675 int ecf_flags = flags_from_decl_or_type (target->decl); 1676 if (ecf_flags & ECF_CONST) 1677 { 1678 e->speculative_call_info (direct, indirect, ref); 1679 if (!(indirect->indirect_info->ecf_flags & ECF_CONST)) 1680 return true; 1681 } 1682 else if (ecf_flags & ECF_PURE) 1683 { 1684 e->speculative_call_info (direct, indirect, ref); 1685 if (!(indirect->indirect_info->ecf_flags & ECF_PURE)) 1686 return true; 1687 } 1688 } 1689 /* If we did not managed to inline the function nor redirect 1690 to an ipa-cp clone (that are seen by having local flag set), 1691 it is probably pointless to inline it unless hardware is missing 1692 indirect call predictor. */ 1693 if (!anticipate_inlining && e->inline_failed && !target->local.local) 1694 return false; 1695 /* For overwritable targets there is not much to do. */ 1696 if (e->inline_failed && !can_inline_edge_p (e, false, true)) 1697 return false; 1698 /* OK, speculation seems interesting. */ 1699 return true; 1700 } 1701 1702 /* We know that EDGE is not going to be inlined. 1703 See if we can remove speculation. */ 1704 1705 static void 1706 resolve_noninline_speculation (edge_heap_t *edge_heap, struct cgraph_edge *edge) 1707 { 1708 if (edge->speculative && !speculation_useful_p (edge, false)) 1709 { 1710 struct cgraph_node *node = edge->caller; 1711 struct cgraph_node *where = node->global.inlined_to 1712 ? node->global.inlined_to : node; 1713 bitmap updated_nodes = BITMAP_ALLOC (NULL); 1714 1715 spec_rem += edge->count; 1716 edge->resolve_speculation (); 1717 reset_edge_caches (where); 1718 inline_update_overall_summary (where); 1719 update_caller_keys (edge_heap, where, 1720 updated_nodes, NULL); 1721 update_callee_keys (edge_heap, where, 1722 updated_nodes); 1723 BITMAP_FREE (updated_nodes); 1724 } 1725 } 1726 1727 /* Return true if NODE should be accounted for overall size estimate. 1728 Skip all nodes optimized for size so we can measure the growth of hot 1729 part of program no matter of the padding. */ 1730 1731 bool 1732 inline_account_function_p (struct cgraph_node *node) 1733 { 1734 return (!DECL_EXTERNAL (node->decl) 1735 && !opt_for_fn (node->decl, optimize_size) 1736 && node->frequency != NODE_FREQUENCY_UNLIKELY_EXECUTED); 1737 } 1738 1739 /* Count number of callers of NODE and store it into DATA (that 1740 points to int. Worker for cgraph_for_node_and_aliases. */ 1741 1742 static bool 1743 sum_callers (struct cgraph_node *node, void *data) 1744 { 1745 struct cgraph_edge *e; 1746 int *num_calls = (int *)data; 1747 1748 for (e = node->callers; e; e = e->next_caller) 1749 (*num_calls)++; 1750 return false; 1751 } 1752 1753 /* We use greedy algorithm for inlining of small functions: 1754 All inline candidates are put into prioritized heap ordered in 1755 increasing badness. 1756 1757 The inlining of small functions is bounded by unit growth parameters. */ 1758 1759 static void 1760 inline_small_functions (void) 1761 { 1762 struct cgraph_node *node; 1763 struct cgraph_edge *edge; 1764 edge_heap_t edge_heap (sreal::min ()); 1765 bitmap updated_nodes = BITMAP_ALLOC (NULL); 1766 int min_size, max_size; 1767 auto_vec<cgraph_edge *> new_indirect_edges; 1768 int initial_size = 0; 1769 struct cgraph_node **order = XCNEWVEC (cgraph_node *, symtab->cgraph_count); 1770 struct cgraph_edge_hook_list *edge_removal_hook_holder; 1771 new_indirect_edges.create (8); 1772 1773 edge_removal_hook_holder 1774 = symtab->add_edge_removal_hook (&heap_edge_removal_hook, &edge_heap); 1775 1776 /* Compute overall unit size and other global parameters used by badness 1777 metrics. */ 1778 1779 max_count = 0; 1780 ipa_reduced_postorder (order, true, true, NULL); 1781 free (order); 1782 1783 FOR_EACH_DEFINED_FUNCTION (node) 1784 if (!node->global.inlined_to) 1785 { 1786 if (!node->alias && node->analyzed 1787 && (node->has_gimple_body_p () || node->thunk.thunk_p)) 1788 { 1789 struct inline_summary *info = inline_summaries->get (node); 1790 struct ipa_dfs_info *dfs = (struct ipa_dfs_info *) node->aux; 1791 1792 /* Do not account external functions, they will be optimized out 1793 if not inlined. Also only count the non-cold portion of program. */ 1794 if (inline_account_function_p (node)) 1795 initial_size += info->size; 1796 info->growth = estimate_growth (node); 1797 1798 int num_calls = 0; 1799 node->call_for_symbol_and_aliases (sum_callers, &num_calls, 1800 true); 1801 if (num_calls == 1) 1802 info->single_caller = true; 1803 if (dfs && dfs->next_cycle) 1804 { 1805 struct cgraph_node *n2; 1806 int id = dfs->scc_no + 1; 1807 for (n2 = node; n2; 1808 n2 = ((struct ipa_dfs_info *) node->aux)->next_cycle) 1809 { 1810 struct inline_summary *info2 = inline_summaries->get (n2); 1811 if (info2->scc_no) 1812 break; 1813 info2->scc_no = id; 1814 } 1815 } 1816 } 1817 1818 for (edge = node->callers; edge; edge = edge->next_caller) 1819 if (max_count < edge->count) 1820 max_count = edge->count; 1821 } 1822 ipa_free_postorder_info (); 1823 initialize_growth_caches (); 1824 1825 if (dump_file) 1826 fprintf (dump_file, 1827 "\nDeciding on inlining of small functions. Starting with size %i.\n", 1828 initial_size); 1829 1830 overall_size = initial_size; 1831 max_size = compute_max_insns (overall_size); 1832 min_size = overall_size; 1833 1834 /* Populate the heap with all edges we might inline. */ 1835 1836 FOR_EACH_DEFINED_FUNCTION (node) 1837 { 1838 bool update = false; 1839 struct cgraph_edge *next = NULL; 1840 bool has_speculative = false; 1841 1842 if (dump_file) 1843 fprintf (dump_file, "Enqueueing calls in %s/%i.\n", 1844 node->name (), node->order); 1845 1846 for (edge = node->callees; edge; edge = next) 1847 { 1848 next = edge->next_callee; 1849 if (edge->inline_failed 1850 && !edge->aux 1851 && can_inline_edge_p (edge, true) 1852 && want_inline_small_function_p (edge, true) 1853 && edge->inline_failed) 1854 { 1855 gcc_assert (!edge->aux); 1856 update_edge_key (&edge_heap, edge); 1857 } 1858 if (edge->speculative) 1859 has_speculative = true; 1860 } 1861 if (has_speculative) 1862 for (edge = node->callees; edge; edge = next) 1863 if (edge->speculative && !speculation_useful_p (edge, 1864 edge->aux != NULL)) 1865 { 1866 edge->resolve_speculation (); 1867 update = true; 1868 } 1869 if (update) 1870 { 1871 struct cgraph_node *where = node->global.inlined_to 1872 ? node->global.inlined_to : node; 1873 inline_update_overall_summary (where); 1874 reset_edge_caches (where); 1875 update_caller_keys (&edge_heap, where, 1876 updated_nodes, NULL); 1877 update_callee_keys (&edge_heap, where, 1878 updated_nodes); 1879 bitmap_clear (updated_nodes); 1880 } 1881 } 1882 1883 gcc_assert (in_lto_p 1884 || !max_count 1885 || (profile_info && flag_branch_probabilities)); 1886 1887 while (!edge_heap.empty ()) 1888 { 1889 int old_size = overall_size; 1890 struct cgraph_node *where, *callee; 1891 sreal badness = edge_heap.min_key (); 1892 sreal current_badness; 1893 int growth; 1894 1895 edge = edge_heap.extract_min (); 1896 gcc_assert (edge->aux); 1897 edge->aux = NULL; 1898 if (!edge->inline_failed || !edge->callee->analyzed) 1899 continue; 1900 1901 #ifdef ENABLE_CHECKING 1902 /* Be sure that caches are maintained consistent. */ 1903 sreal cached_badness = edge_badness (edge, false); 1904 1905 int old_size_est = estimate_edge_size (edge); 1906 int old_time_est = estimate_edge_time (edge); 1907 int old_hints_est = estimate_edge_hints (edge); 1908 1909 reset_edge_growth_cache (edge); 1910 gcc_assert (old_size_est == estimate_edge_size (edge)); 1911 gcc_assert (old_time_est == estimate_edge_time (edge)); 1912 /* FIXME: 1913 1914 gcc_assert (old_hints_est == estimate_edge_hints (edge)); 1915 1916 fails with profile feedback because some hints depends on 1917 maybe_hot_edge_p predicate and because callee gets inlined to other 1918 calls, the edge may become cold. 1919 This ought to be fixed by computing relative probabilities 1920 for given invocation but that will be better done once whole 1921 code is converted to sreals. Disable for now and revert to "wrong" 1922 value so enable/disable checking paths agree. */ 1923 edge_growth_cache[edge->uid].hints = old_hints_est + 1; 1924 1925 /* When updating the edge costs, we only decrease badness in the keys. 1926 Increases of badness are handled lazilly; when we see key with out 1927 of date value on it, we re-insert it now. */ 1928 current_badness = edge_badness (edge, false); 1929 /* Disable checking for profile because roundoff errors may cause slight 1930 deviations in the order. */ 1931 gcc_assert (max_count || cached_badness == current_badness); 1932 gcc_assert (current_badness >= badness); 1933 #else 1934 current_badness = edge_badness (edge, false); 1935 #endif 1936 if (current_badness != badness) 1937 { 1938 if (edge_heap.min () && current_badness > edge_heap.min_key ()) 1939 { 1940 edge->aux = edge_heap.insert (current_badness, edge); 1941 continue; 1942 } 1943 else 1944 badness = current_badness; 1945 } 1946 1947 if (!can_inline_edge_p (edge, true)) 1948 { 1949 resolve_noninline_speculation (&edge_heap, edge); 1950 continue; 1951 } 1952 1953 callee = edge->callee->ultimate_alias_target (); 1954 growth = estimate_edge_growth (edge); 1955 if (dump_file) 1956 { 1957 fprintf (dump_file, 1958 "\nConsidering %s/%i with %i size\n", 1959 callee->name (), callee->order, 1960 inline_summaries->get (callee)->size); 1961 fprintf (dump_file, 1962 " to be inlined into %s/%i in %s:%i\n" 1963 " Estimated badness is %f, frequency %.2f.\n", 1964 edge->caller->name (), edge->caller->order, 1965 edge->call_stmt 1966 && (LOCATION_LOCUS (gimple_location ((const_gimple) 1967 edge->call_stmt)) 1968 > BUILTINS_LOCATION) 1969 ? gimple_filename ((const_gimple) edge->call_stmt) 1970 : "unknown", 1971 edge->call_stmt 1972 ? gimple_lineno ((const_gimple) edge->call_stmt) 1973 : -1, 1974 badness.to_double (), 1975 edge->frequency / (double)CGRAPH_FREQ_BASE); 1976 if (edge->count) 1977 fprintf (dump_file," Called %"PRId64"x\n", 1978 edge->count); 1979 if (dump_flags & TDF_DETAILS) 1980 edge_badness (edge, true); 1981 } 1982 1983 if (overall_size + growth > max_size 1984 && !DECL_DISREGARD_INLINE_LIMITS (callee->decl)) 1985 { 1986 edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT; 1987 report_inline_failed_reason (edge); 1988 resolve_noninline_speculation (&edge_heap, edge); 1989 continue; 1990 } 1991 1992 if (!want_inline_small_function_p (edge, true)) 1993 { 1994 resolve_noninline_speculation (&edge_heap, edge); 1995 continue; 1996 } 1997 1998 /* Heuristics for inlining small functions work poorly for 1999 recursive calls where we do effects similar to loop unrolling. 2000 When inlining such edge seems profitable, leave decision on 2001 specific inliner. */ 2002 if (edge->recursive_p ()) 2003 { 2004 where = edge->caller; 2005 if (where->global.inlined_to) 2006 where = where->global.inlined_to; 2007 if (!recursive_inlining (edge, 2008 opt_for_fn (edge->caller->decl, 2009 flag_indirect_inlining) 2010 ? &new_indirect_edges : NULL)) 2011 { 2012 edge->inline_failed = CIF_RECURSIVE_INLINING; 2013 resolve_noninline_speculation (&edge_heap, edge); 2014 continue; 2015 } 2016 reset_edge_caches (where); 2017 /* Recursive inliner inlines all recursive calls of the function 2018 at once. Consequently we need to update all callee keys. */ 2019 if (opt_for_fn (edge->caller->decl, flag_indirect_inlining)) 2020 add_new_edges_to_heap (&edge_heap, new_indirect_edges); 2021 update_callee_keys (&edge_heap, where, updated_nodes); 2022 bitmap_clear (updated_nodes); 2023 } 2024 else 2025 { 2026 struct cgraph_node *outer_node = NULL; 2027 int depth = 0; 2028 2029 /* Consider the case where self recursive function A is inlined 2030 into B. This is desired optimization in some cases, since it 2031 leads to effect similar of loop peeling and we might completely 2032 optimize out the recursive call. However we must be extra 2033 selective. */ 2034 2035 where = edge->caller; 2036 while (where->global.inlined_to) 2037 { 2038 if (where->decl == callee->decl) 2039 outer_node = where, depth++; 2040 where = where->callers->caller; 2041 } 2042 if (outer_node 2043 && !want_inline_self_recursive_call_p (edge, outer_node, 2044 true, depth)) 2045 { 2046 edge->inline_failed 2047 = (DECL_DISREGARD_INLINE_LIMITS (edge->callee->decl) 2048 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED); 2049 resolve_noninline_speculation (&edge_heap, edge); 2050 continue; 2051 } 2052 else if (depth && dump_file) 2053 fprintf (dump_file, " Peeling recursion with depth %i\n", depth); 2054 2055 gcc_checking_assert (!callee->global.inlined_to); 2056 inline_call (edge, true, &new_indirect_edges, &overall_size, true); 2057 add_new_edges_to_heap (&edge_heap, new_indirect_edges); 2058 2059 reset_edge_caches (edge->callee->function_symbol ()); 2060 2061 update_callee_keys (&edge_heap, where, updated_nodes); 2062 } 2063 where = edge->caller; 2064 if (where->global.inlined_to) 2065 where = where->global.inlined_to; 2066 2067 /* Our profitability metric can depend on local properties 2068 such as number of inlinable calls and size of the function body. 2069 After inlining these properties might change for the function we 2070 inlined into (since it's body size changed) and for the functions 2071 called by function we inlined (since number of it inlinable callers 2072 might change). */ 2073 update_caller_keys (&edge_heap, where, updated_nodes, NULL); 2074 /* Offline copy count has possibly changed, recompute if profile is 2075 available. */ 2076 if (max_count) 2077 { 2078 struct cgraph_node *n = cgraph_node::get (edge->callee->decl); 2079 if (n != edge->callee && n->analyzed) 2080 update_callee_keys (&edge_heap, n, updated_nodes); 2081 } 2082 bitmap_clear (updated_nodes); 2083 2084 if (dump_file) 2085 { 2086 fprintf (dump_file, 2087 " Inlined into %s which now has time %i and size %i," 2088 "net change of %+i.\n", 2089 edge->caller->name (), 2090 inline_summaries->get (edge->caller)->time, 2091 inline_summaries->get (edge->caller)->size, 2092 overall_size - old_size); 2093 } 2094 if (min_size > overall_size) 2095 { 2096 min_size = overall_size; 2097 max_size = compute_max_insns (min_size); 2098 2099 if (dump_file) 2100 fprintf (dump_file, "New minimal size reached: %i\n", min_size); 2101 } 2102 } 2103 2104 free_growth_caches (); 2105 if (dump_file) 2106 fprintf (dump_file, 2107 "Unit growth for small function inlining: %i->%i (%i%%)\n", 2108 initial_size, overall_size, 2109 initial_size ? overall_size * 100 / (initial_size) - 100: 0); 2110 BITMAP_FREE (updated_nodes); 2111 symtab->remove_edge_removal_hook (edge_removal_hook_holder); 2112 } 2113 2114 /* Flatten NODE. Performed both during early inlining and 2115 at IPA inlining time. */ 2116 2117 static void 2118 flatten_function (struct cgraph_node *node, bool early) 2119 { 2120 struct cgraph_edge *e; 2121 2122 /* We shouldn't be called recursively when we are being processed. */ 2123 gcc_assert (node->aux == NULL); 2124 2125 node->aux = (void *) node; 2126 2127 for (e = node->callees; e; e = e->next_callee) 2128 { 2129 struct cgraph_node *orig_callee; 2130 struct cgraph_node *callee = e->callee->ultimate_alias_target (); 2131 2132 /* We've hit cycle? It is time to give up. */ 2133 if (callee->aux) 2134 { 2135 if (dump_file) 2136 fprintf (dump_file, 2137 "Not inlining %s into %s to avoid cycle.\n", 2138 xstrdup_for_dump (callee->name ()), 2139 xstrdup_for_dump (e->caller->name ())); 2140 e->inline_failed = CIF_RECURSIVE_INLINING; 2141 continue; 2142 } 2143 2144 /* When the edge is already inlined, we just need to recurse into 2145 it in order to fully flatten the leaves. */ 2146 if (!e->inline_failed) 2147 { 2148 flatten_function (callee, early); 2149 continue; 2150 } 2151 2152 /* Flatten attribute needs to be processed during late inlining. For 2153 extra code quality we however do flattening during early optimization, 2154 too. */ 2155 if (!early 2156 ? !can_inline_edge_p (e, true) 2157 : !can_early_inline_edge_p (e)) 2158 continue; 2159 2160 if (e->recursive_p ()) 2161 { 2162 if (dump_file) 2163 fprintf (dump_file, "Not inlining: recursive call.\n"); 2164 continue; 2165 } 2166 2167 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl)) 2168 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl))) 2169 { 2170 if (dump_file) 2171 fprintf (dump_file, "Not inlining: SSA form does not match.\n"); 2172 continue; 2173 } 2174 2175 /* Inline the edge and flatten the inline clone. Avoid 2176 recursing through the original node if the node was cloned. */ 2177 if (dump_file) 2178 fprintf (dump_file, " Inlining %s into %s.\n", 2179 xstrdup_for_dump (callee->name ()), 2180 xstrdup_for_dump (e->caller->name ())); 2181 orig_callee = callee; 2182 inline_call (e, true, NULL, NULL, false); 2183 if (e->callee != orig_callee) 2184 orig_callee->aux = (void *) node; 2185 flatten_function (e->callee, early); 2186 if (e->callee != orig_callee) 2187 orig_callee->aux = NULL; 2188 } 2189 2190 node->aux = NULL; 2191 if (!node->global.inlined_to) 2192 inline_update_overall_summary (node); 2193 } 2194 2195 /* Inline NODE to all callers. Worker for cgraph_for_node_and_aliases. 2196 DATA points to number of calls originally found so we avoid infinite 2197 recursion. */ 2198 2199 static bool 2200 inline_to_all_callers (struct cgraph_node *node, void *data) 2201 { 2202 int *num_calls = (int *)data; 2203 bool callee_removed = false; 2204 2205 while (node->callers && !node->global.inlined_to) 2206 { 2207 struct cgraph_node *caller = node->callers->caller; 2208 2209 if (!can_inline_edge_p (node->callers, true) 2210 || node->callers->recursive_p ()) 2211 { 2212 if (dump_file) 2213 fprintf (dump_file, "Uninlinable call found; giving up.\n"); 2214 *num_calls = 0; 2215 return false; 2216 } 2217 2218 if (dump_file) 2219 { 2220 fprintf (dump_file, 2221 "\nInlining %s size %i.\n", 2222 node->name (), 2223 inline_summaries->get (node)->size); 2224 fprintf (dump_file, 2225 " Called once from %s %i insns.\n", 2226 node->callers->caller->name (), 2227 inline_summaries->get (node->callers->caller)->size); 2228 } 2229 2230 inline_call (node->callers, true, NULL, NULL, true, &callee_removed); 2231 if (dump_file) 2232 fprintf (dump_file, 2233 " Inlined into %s which now has %i size\n", 2234 caller->name (), 2235 inline_summaries->get (caller)->size); 2236 if (!(*num_calls)--) 2237 { 2238 if (dump_file) 2239 fprintf (dump_file, "New calls found; giving up.\n"); 2240 return callee_removed; 2241 } 2242 if (callee_removed) 2243 return true; 2244 } 2245 return false; 2246 } 2247 2248 /* Output overall time estimate. */ 2249 static void 2250 dump_overall_stats (void) 2251 { 2252 int64_t sum_weighted = 0, sum = 0; 2253 struct cgraph_node *node; 2254 2255 FOR_EACH_DEFINED_FUNCTION (node) 2256 if (!node->global.inlined_to 2257 && !node->alias) 2258 { 2259 int time = inline_summaries->get (node)->time; 2260 sum += time; 2261 sum_weighted += time * node->count; 2262 } 2263 fprintf (dump_file, "Overall time estimate: " 2264 "%"PRId64" weighted by profile: " 2265 "%"PRId64"\n", sum, sum_weighted); 2266 } 2267 2268 /* Output some useful stats about inlining. */ 2269 2270 static void 2271 dump_inline_stats (void) 2272 { 2273 int64_t inlined_cnt = 0, inlined_indir_cnt = 0; 2274 int64_t inlined_virt_cnt = 0, inlined_virt_indir_cnt = 0; 2275 int64_t noninlined_cnt = 0, noninlined_indir_cnt = 0; 2276 int64_t noninlined_virt_cnt = 0, noninlined_virt_indir_cnt = 0; 2277 int64_t inlined_speculative = 0, inlined_speculative_ply = 0; 2278 int64_t indirect_poly_cnt = 0, indirect_cnt = 0; 2279 int64_t reason[CIF_N_REASONS][3]; 2280 int i; 2281 struct cgraph_node *node; 2282 2283 memset (reason, 0, sizeof (reason)); 2284 FOR_EACH_DEFINED_FUNCTION (node) 2285 { 2286 struct cgraph_edge *e; 2287 for (e = node->callees; e; e = e->next_callee) 2288 { 2289 if (e->inline_failed) 2290 { 2291 reason[(int) e->inline_failed][0] += e->count; 2292 reason[(int) e->inline_failed][1] += e->frequency; 2293 reason[(int) e->inline_failed][2] ++; 2294 if (DECL_VIRTUAL_P (e->callee->decl)) 2295 { 2296 if (e->indirect_inlining_edge) 2297 noninlined_virt_indir_cnt += e->count; 2298 else 2299 noninlined_virt_cnt += e->count; 2300 } 2301 else 2302 { 2303 if (e->indirect_inlining_edge) 2304 noninlined_indir_cnt += e->count; 2305 else 2306 noninlined_cnt += e->count; 2307 } 2308 } 2309 else 2310 { 2311 if (e->speculative) 2312 { 2313 if (DECL_VIRTUAL_P (e->callee->decl)) 2314 inlined_speculative_ply += e->count; 2315 else 2316 inlined_speculative += e->count; 2317 } 2318 else if (DECL_VIRTUAL_P (e->callee->decl)) 2319 { 2320 if (e->indirect_inlining_edge) 2321 inlined_virt_indir_cnt += e->count; 2322 else 2323 inlined_virt_cnt += e->count; 2324 } 2325 else 2326 { 2327 if (e->indirect_inlining_edge) 2328 inlined_indir_cnt += e->count; 2329 else 2330 inlined_cnt += e->count; 2331 } 2332 } 2333 } 2334 for (e = node->indirect_calls; e; e = e->next_callee) 2335 if (e->indirect_info->polymorphic) 2336 indirect_poly_cnt += e->count; 2337 else 2338 indirect_cnt += e->count; 2339 } 2340 if (max_count) 2341 { 2342 fprintf (dump_file, 2343 "Inlined %"PRId64 " + speculative " 2344 "%"PRId64 " + speculative polymorphic " 2345 "%"PRId64 " + previously indirect " 2346 "%"PRId64 " + virtual " 2347 "%"PRId64 " + virtual and previously indirect " 2348 "%"PRId64 "\n" "Not inlined " 2349 "%"PRId64 " + previously indirect " 2350 "%"PRId64 " + virtual " 2351 "%"PRId64 " + virtual and previously indirect " 2352 "%"PRId64 " + stil indirect " 2353 "%"PRId64 " + still indirect polymorphic " 2354 "%"PRId64 "\n", inlined_cnt, 2355 inlined_speculative, inlined_speculative_ply, 2356 inlined_indir_cnt, inlined_virt_cnt, inlined_virt_indir_cnt, 2357 noninlined_cnt, noninlined_indir_cnt, noninlined_virt_cnt, 2358 noninlined_virt_indir_cnt, indirect_cnt, indirect_poly_cnt); 2359 fprintf (dump_file, 2360 "Removed speculations %"PRId64 "\n", 2361 spec_rem); 2362 } 2363 dump_overall_stats (); 2364 fprintf (dump_file, "\nWhy inlining failed?\n"); 2365 for (i = 0; i < CIF_N_REASONS; i++) 2366 if (reason[i][2]) 2367 fprintf (dump_file, "%-50s: %8i calls, %8i freq, %"PRId64" count\n", 2368 cgraph_inline_failed_string ((cgraph_inline_failed_t) i), 2369 (int) reason[i][2], (int) reason[i][1], reason[i][0]); 2370 } 2371 2372 /* Decide on the inlining. We do so in the topological order to avoid 2373 expenses on updating data structures. */ 2374 2375 static unsigned int 2376 ipa_inline (void) 2377 { 2378 struct cgraph_node *node; 2379 int nnodes; 2380 struct cgraph_node **order; 2381 int i; 2382 int cold; 2383 bool remove_functions = false; 2384 2385 if (!optimize) 2386 return 0; 2387 2388 cgraph_freq_base_rec = (sreal) 1 / (sreal) CGRAPH_FREQ_BASE; 2389 percent_rec = (sreal) 1 / (sreal) 100; 2390 2391 order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count); 2392 2393 if (in_lto_p && optimize) 2394 ipa_update_after_lto_read (); 2395 2396 if (dump_file) 2397 dump_inline_summaries (dump_file); 2398 2399 nnodes = ipa_reverse_postorder (order); 2400 2401 FOR_EACH_FUNCTION (node) 2402 { 2403 node->aux = 0; 2404 2405 /* Recompute the default reasons for inlining because they may have 2406 changed during merging. */ 2407 if (in_lto_p) 2408 { 2409 for (cgraph_edge *e = node->callees; e; e = e->next_callee) 2410 { 2411 gcc_assert (e->inline_failed); 2412 initialize_inline_failed (e); 2413 } 2414 for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee) 2415 initialize_inline_failed (e); 2416 } 2417 } 2418 2419 if (dump_file) 2420 fprintf (dump_file, "\nFlattening functions:\n"); 2421 2422 /* In the first pass handle functions to be flattened. Do this with 2423 a priority so none of our later choices will make this impossible. */ 2424 for (i = nnodes - 1; i >= 0; i--) 2425 { 2426 node = order[i]; 2427 2428 /* Handle nodes to be flattened. 2429 Ideally when processing callees we stop inlining at the 2430 entry of cycles, possibly cloning that entry point and 2431 try to flatten itself turning it into a self-recursive 2432 function. */ 2433 if (lookup_attribute ("flatten", 2434 DECL_ATTRIBUTES (node->decl)) != NULL) 2435 { 2436 if (dump_file) 2437 fprintf (dump_file, 2438 "Flattening %s\n", node->name ()); 2439 flatten_function (node, false); 2440 } 2441 } 2442 if (dump_file) 2443 dump_overall_stats (); 2444 2445 inline_small_functions (); 2446 2447 gcc_assert (symtab->state == IPA_SSA); 2448 symtab->state = IPA_SSA_AFTER_INLINING; 2449 /* Do first after-inlining removal. We want to remove all "stale" extern 2450 inline functions and virtual functions so we really know what is called 2451 once. */ 2452 symtab->remove_unreachable_nodes (dump_file); 2453 free (order); 2454 2455 /* Inline functions with a property that after inlining into all callers the 2456 code size will shrink because the out-of-line copy is eliminated. 2457 We do this regardless on the callee size as long as function growth limits 2458 are met. */ 2459 if (dump_file) 2460 fprintf (dump_file, 2461 "\nDeciding on functions to be inlined into all callers and " 2462 "removing useless speculations:\n"); 2463 2464 /* Inlining one function called once has good chance of preventing 2465 inlining other function into the same callee. Ideally we should 2466 work in priority order, but probably inlining hot functions first 2467 is good cut without the extra pain of maintaining the queue. 2468 2469 ??? this is not really fitting the bill perfectly: inlining function 2470 into callee often leads to better optimization of callee due to 2471 increased context for optimization. 2472 For example if main() function calls a function that outputs help 2473 and then function that does the main optmization, we should inline 2474 the second with priority even if both calls are cold by themselves. 2475 2476 We probably want to implement new predicate replacing our use of 2477 maybe_hot_edge interpreted as maybe_hot_edge || callee is known 2478 to be hot. */ 2479 for (cold = 0; cold <= 1; cold ++) 2480 { 2481 FOR_EACH_DEFINED_FUNCTION (node) 2482 { 2483 struct cgraph_edge *edge, *next; 2484 bool update=false; 2485 2486 for (edge = node->callees; edge; edge = next) 2487 { 2488 next = edge->next_callee; 2489 if (edge->speculative && !speculation_useful_p (edge, false)) 2490 { 2491 edge->resolve_speculation (); 2492 spec_rem += edge->count; 2493 update = true; 2494 remove_functions = true; 2495 } 2496 } 2497 if (update) 2498 { 2499 struct cgraph_node *where = node->global.inlined_to 2500 ? node->global.inlined_to : node; 2501 reset_edge_caches (where); 2502 inline_update_overall_summary (where); 2503 } 2504 if (want_inline_function_to_all_callers_p (node, cold)) 2505 { 2506 int num_calls = 0; 2507 node->call_for_symbol_and_aliases (sum_callers, &num_calls, 2508 true); 2509 while (node->call_for_symbol_and_aliases 2510 (inline_to_all_callers, &num_calls, true)) 2511 ; 2512 remove_functions = true; 2513 } 2514 } 2515 } 2516 2517 /* Free ipa-prop structures if they are no longer needed. */ 2518 if (optimize) 2519 ipa_free_all_structures_after_iinln (); 2520 2521 if (dump_file) 2522 { 2523 fprintf (dump_file, 2524 "\nInlined %i calls, eliminated %i functions\n\n", 2525 ncalls_inlined, nfunctions_inlined); 2526 dump_inline_stats (); 2527 } 2528 2529 if (dump_file) 2530 dump_inline_summaries (dump_file); 2531 /* In WPA we use inline summaries for partitioning process. */ 2532 if (!flag_wpa) 2533 inline_free_summary (); 2534 return remove_functions ? TODO_remove_functions : 0; 2535 } 2536 2537 /* Inline always-inline function calls in NODE. */ 2538 2539 static bool 2540 inline_always_inline_functions (struct cgraph_node *node) 2541 { 2542 struct cgraph_edge *e; 2543 bool inlined = false; 2544 2545 for (e = node->callees; e; e = e->next_callee) 2546 { 2547 struct cgraph_node *callee = e->callee->ultimate_alias_target (); 2548 if (!DECL_DISREGARD_INLINE_LIMITS (callee->decl)) 2549 continue; 2550 2551 if (e->recursive_p ()) 2552 { 2553 if (dump_file) 2554 fprintf (dump_file, " Not inlining recursive call to %s.\n", 2555 e->callee->name ()); 2556 e->inline_failed = CIF_RECURSIVE_INLINING; 2557 continue; 2558 } 2559 2560 if (!can_early_inline_edge_p (e)) 2561 { 2562 /* Set inlined to true if the callee is marked "always_inline" but 2563 is not inlinable. This will allow flagging an error later in 2564 expand_call_inline in tree-inline.c. */ 2565 if (lookup_attribute ("always_inline", 2566 DECL_ATTRIBUTES (callee->decl)) != NULL) 2567 inlined = true; 2568 continue; 2569 } 2570 2571 if (dump_file) 2572 fprintf (dump_file, " Inlining %s into %s (always_inline).\n", 2573 xstrdup_for_dump (e->callee->name ()), 2574 xstrdup_for_dump (e->caller->name ())); 2575 inline_call (e, true, NULL, NULL, false); 2576 inlined = true; 2577 } 2578 if (inlined) 2579 inline_update_overall_summary (node); 2580 2581 return inlined; 2582 } 2583 2584 /* Decide on the inlining. We do so in the topological order to avoid 2585 expenses on updating data structures. */ 2586 2587 static bool 2588 early_inline_small_functions (struct cgraph_node *node) 2589 { 2590 struct cgraph_edge *e; 2591 bool inlined = false; 2592 2593 for (e = node->callees; e; e = e->next_callee) 2594 { 2595 struct cgraph_node *callee = e->callee->ultimate_alias_target (); 2596 if (!inline_summaries->get (callee)->inlinable 2597 || !e->inline_failed) 2598 continue; 2599 2600 /* Do not consider functions not declared inline. */ 2601 if (!DECL_DECLARED_INLINE_P (callee->decl) 2602 && !opt_for_fn (node->decl, flag_inline_small_functions) 2603 && !opt_for_fn (node->decl, flag_inline_functions)) 2604 continue; 2605 2606 if (dump_file) 2607 fprintf (dump_file, "Considering inline candidate %s.\n", 2608 callee->name ()); 2609 2610 if (!can_early_inline_edge_p (e)) 2611 continue; 2612 2613 if (e->recursive_p ()) 2614 { 2615 if (dump_file) 2616 fprintf (dump_file, " Not inlining: recursive call.\n"); 2617 continue; 2618 } 2619 2620 if (!want_early_inline_function_p (e)) 2621 continue; 2622 2623 if (dump_file) 2624 fprintf (dump_file, " Inlining %s into %s.\n", 2625 xstrdup_for_dump (callee->name ()), 2626 xstrdup_for_dump (e->caller->name ())); 2627 inline_call (e, true, NULL, NULL, true); 2628 inlined = true; 2629 } 2630 2631 return inlined; 2632 } 2633 2634 unsigned int 2635 early_inliner (function *fun) 2636 { 2637 struct cgraph_node *node = cgraph_node::get (current_function_decl); 2638 struct cgraph_edge *edge; 2639 unsigned int todo = 0; 2640 int iterations = 0; 2641 bool inlined = false; 2642 2643 if (seen_error ()) 2644 return 0; 2645 2646 /* Do nothing if datastructures for ipa-inliner are already computed. This 2647 happens when some pass decides to construct new function and 2648 cgraph_add_new_function calls lowering passes and early optimization on 2649 it. This may confuse ourself when early inliner decide to inline call to 2650 function clone, because function clones don't have parameter list in 2651 ipa-prop matching their signature. */ 2652 if (ipa_node_params_sum) 2653 return 0; 2654 2655 #ifdef ENABLE_CHECKING 2656 node->verify (); 2657 #endif 2658 node->remove_all_references (); 2659 2660 /* Rebuild this reference because it dosn't depend on 2661 function's body and it's required to pass cgraph_node 2662 verification. */ 2663 if (node->instrumented_version 2664 && !node->instrumentation_clone) 2665 node->create_reference (node->instrumented_version, IPA_REF_CHKP, NULL); 2666 2667 /* Even when not optimizing or not inlining inline always-inline 2668 functions. */ 2669 inlined = inline_always_inline_functions (node); 2670 2671 if (!optimize 2672 || flag_no_inline 2673 || !flag_early_inlining 2674 /* Never inline regular functions into always-inline functions 2675 during incremental inlining. This sucks as functions calling 2676 always inline functions will get less optimized, but at the 2677 same time inlining of functions calling always inline 2678 function into an always inline function might introduce 2679 cycles of edges to be always inlined in the callgraph. 2680 2681 We might want to be smarter and just avoid this type of inlining. */ 2682 || (DECL_DISREGARD_INLINE_LIMITS (node->decl) 2683 && lookup_attribute ("always_inline", 2684 DECL_ATTRIBUTES (node->decl)))) 2685 ; 2686 else if (lookup_attribute ("flatten", 2687 DECL_ATTRIBUTES (node->decl)) != NULL) 2688 { 2689 /* When the function is marked to be flattened, recursively inline 2690 all calls in it. */ 2691 if (dump_file) 2692 fprintf (dump_file, 2693 "Flattening %s\n", node->name ()); 2694 flatten_function (node, true); 2695 inlined = true; 2696 } 2697 else 2698 { 2699 /* If some always_inline functions was inlined, apply the changes. 2700 This way we will not account always inline into growth limits and 2701 moreover we will inline calls from always inlines that we skipped 2702 previously becuase of conditional above. */ 2703 if (inlined) 2704 { 2705 timevar_push (TV_INTEGRATION); 2706 todo |= optimize_inline_calls (current_function_decl); 2707 /* optimize_inline_calls call above might have introduced new 2708 statements that don't have inline parameters computed. */ 2709 for (edge = node->callees; edge; edge = edge->next_callee) 2710 { 2711 if (inline_edge_summary_vec.length () > (unsigned) edge->uid) 2712 { 2713 struct inline_edge_summary *es = inline_edge_summary (edge); 2714 es->call_stmt_size 2715 = estimate_num_insns (edge->call_stmt, &eni_size_weights); 2716 es->call_stmt_time 2717 = estimate_num_insns (edge->call_stmt, &eni_time_weights); 2718 } 2719 } 2720 inline_update_overall_summary (node); 2721 inlined = false; 2722 timevar_pop (TV_INTEGRATION); 2723 } 2724 /* We iterate incremental inlining to get trivial cases of indirect 2725 inlining. */ 2726 while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS) 2727 && early_inline_small_functions (node)) 2728 { 2729 timevar_push (TV_INTEGRATION); 2730 todo |= optimize_inline_calls (current_function_decl); 2731 2732 /* Technically we ought to recompute inline parameters so the new 2733 iteration of early inliner works as expected. We however have 2734 values approximately right and thus we only need to update edge 2735 info that might be cleared out for newly discovered edges. */ 2736 for (edge = node->callees; edge; edge = edge->next_callee) 2737 { 2738 /* We have no summary for new bound store calls yet. */ 2739 if (inline_edge_summary_vec.length () > (unsigned)edge->uid) 2740 { 2741 struct inline_edge_summary *es = inline_edge_summary (edge); 2742 es->call_stmt_size 2743 = estimate_num_insns (edge->call_stmt, &eni_size_weights); 2744 es->call_stmt_time 2745 = estimate_num_insns (edge->call_stmt, &eni_time_weights); 2746 } 2747 if (edge->callee->decl 2748 && !gimple_check_call_matching_types ( 2749 edge->call_stmt, edge->callee->decl, false)) 2750 edge->call_stmt_cannot_inline_p = true; 2751 } 2752 if (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS) - 1) 2753 inline_update_overall_summary (node); 2754 timevar_pop (TV_INTEGRATION); 2755 iterations++; 2756 inlined = false; 2757 } 2758 if (dump_file) 2759 fprintf (dump_file, "Iterations: %i\n", iterations); 2760 } 2761 2762 if (inlined) 2763 { 2764 timevar_push (TV_INTEGRATION); 2765 todo |= optimize_inline_calls (current_function_decl); 2766 timevar_pop (TV_INTEGRATION); 2767 } 2768 2769 fun->always_inline_functions_inlined = true; 2770 2771 return todo; 2772 } 2773 2774 /* Do inlining of small functions. Doing so early helps profiling and other 2775 passes to be somewhat more effective and avoids some code duplication in 2776 later real inlining pass for testcases with very many function calls. */ 2777 2778 namespace { 2779 2780 const pass_data pass_data_early_inline = 2781 { 2782 GIMPLE_PASS, /* type */ 2783 "einline", /* name */ 2784 OPTGROUP_INLINE, /* optinfo_flags */ 2785 TV_EARLY_INLINING, /* tv_id */ 2786 PROP_ssa, /* properties_required */ 2787 0, /* properties_provided */ 2788 0, /* properties_destroyed */ 2789 0, /* todo_flags_start */ 2790 0, /* todo_flags_finish */ 2791 }; 2792 2793 class pass_early_inline : public gimple_opt_pass 2794 { 2795 public: 2796 pass_early_inline (gcc::context *ctxt) 2797 : gimple_opt_pass (pass_data_early_inline, ctxt) 2798 {} 2799 2800 /* opt_pass methods: */ 2801 virtual unsigned int execute (function *); 2802 2803 }; // class pass_early_inline 2804 2805 unsigned int 2806 pass_early_inline::execute (function *fun) 2807 { 2808 return early_inliner (fun); 2809 } 2810 2811 } // anon namespace 2812 2813 gimple_opt_pass * 2814 make_pass_early_inline (gcc::context *ctxt) 2815 { 2816 return new pass_early_inline (ctxt); 2817 } 2818 2819 namespace { 2820 2821 const pass_data pass_data_ipa_inline = 2822 { 2823 IPA_PASS, /* type */ 2824 "inline", /* name */ 2825 OPTGROUP_INLINE, /* optinfo_flags */ 2826 TV_IPA_INLINING, /* tv_id */ 2827 0, /* properties_required */ 2828 0, /* properties_provided */ 2829 0, /* properties_destroyed */ 2830 0, /* todo_flags_start */ 2831 ( TODO_dump_symtab ), /* todo_flags_finish */ 2832 }; 2833 2834 class pass_ipa_inline : public ipa_opt_pass_d 2835 { 2836 public: 2837 pass_ipa_inline (gcc::context *ctxt) 2838 : ipa_opt_pass_d (pass_data_ipa_inline, ctxt, 2839 inline_generate_summary, /* generate_summary */ 2840 inline_write_summary, /* write_summary */ 2841 inline_read_summary, /* read_summary */ 2842 NULL, /* write_optimization_summary */ 2843 NULL, /* read_optimization_summary */ 2844 NULL, /* stmt_fixup */ 2845 0, /* function_transform_todo_flags_start */ 2846 inline_transform, /* function_transform */ 2847 NULL) /* variable_transform */ 2848 {} 2849 2850 /* opt_pass methods: */ 2851 virtual unsigned int execute (function *) { return ipa_inline (); } 2852 2853 }; // class pass_ipa_inline 2854 2855 } // anon namespace 2856 2857 ipa_opt_pass_d * 2858 make_pass_ipa_inline (gcc::context *ctxt) 2859 { 2860 return new pass_ipa_inline (ctxt); 2861 } 2862