1/* Inlining decision heuristics. 2 Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010 3 Free Software Foundation, Inc. 4 Contributed by Jan Hubicka 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 3, or (at your option) any later 11version. 12 13GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING3. If not see 20<http://www.gnu.org/licenses/>. */ 21 22/* Inlining decision heuristics 23 24 We separate inlining decisions from the inliner itself and store it 25 inside callgraph as so called inline plan. Refer to cgraph.c 26 documentation about particular representation of inline plans in the 27 callgraph. 28 29 There are three major parts of this file: 30 31 cgraph_mark_inline implementation 32 33 This function allows to mark given call inline and performs necessary 34 modifications of cgraph (production of the clones and updating overall 35 statistics) 36 37 inlining heuristics limits 38 39 These functions allow to check that particular inlining is allowed 40 by the limits specified by user (allowed function growth, overall unit 41 growth and so on). 42 43 inlining heuristics 44 45 This is implementation of IPA pass aiming to get as much of benefit 46 from inlining obeying the limits checked above. 47 48 The implementation of particular heuristics is separated from 49 the rest of code to make it easier to replace it with more complicated 50 implementation in the future. The rest of inlining code acts as a 51 library aimed to modify the callgraph and verify that the parameters 52 on code size growth fits. 53 54 To mark given call inline, use cgraph_mark_inline function, the 55 verification is performed by cgraph_default_inline_p and 56 cgraph_check_inline_limits. 57 58 The heuristics implements simple knapsack style algorithm ordering 59 all functions by their "profitability" (estimated by code size growth) 60 and inlining them in priority order. 61 62 cgraph_decide_inlining implements heuristics taking whole callgraph 63 into account, while cgraph_decide_inlining_incrementally considers 64 only one function at a time and is used by early inliner. 65 66 The inliner itself is split into several passes: 67 68 pass_inline_parameters 69 70 This pass computes local properties of functions that are used by inliner: 71 estimated function body size, whether function is inlinable at all and 72 stack frame consumption. 73 74 Before executing any of inliner passes, this local pass has to be applied 75 to each function in the callgraph (ie run as subpass of some earlier 76 IPA pass). The results are made out of date by any optimization applied 77 on the function body. 78 79 pass_early_inlining 80 81 Simple local inlining pass inlining callees into current function. This 82 pass makes no global whole compilation unit analysis and this when allowed 83 to do inlining expanding code size it might result in unbounded growth of 84 whole unit. 85 86 The pass is run during conversion into SSA form. Only functions already 87 converted into SSA form are inlined, so the conversion must happen in 88 topological order on the callgraph (that is maintained by pass manager). 89 The functions after inlining are early optimized so the early inliner sees 90 unoptimized function itself, but all considered callees are already 91 optimized allowing it to unfold abstraction penalty on C++ effectively and 92 cheaply. 93 94 pass_ipa_early_inlining 95 96 With profiling, the early inlining is also necessary to reduce 97 instrumentation costs on program with high abstraction penalty (doing 98 many redundant calls). This can't happen in parallel with early 99 optimization and profile instrumentation, because we would end up 100 re-instrumenting already instrumented function bodies we brought in via 101 inlining. 102 103 To avoid this, this pass is executed as IPA pass before profiling. It is 104 simple wrapper to pass_early_inlining and ensures first inlining. 105 106 pass_ipa_inline 107 108 This is the main pass implementing simple greedy algorithm to do inlining 109 of small functions that results in overall growth of compilation unit and 110 inlining of functions called once. The pass compute just so called inline 111 plan (representation of inlining to be done in callgraph) and unlike early 112 inlining it is not performing the inlining itself. 113 114 pass_apply_inline 115 116 This pass performs actual inlining according to pass_ipa_inline on given 117 function. Possible the function body before inlining is saved when it is 118 needed for further inlining later. 119 */ 120 121#include "config.h" 122#include "system.h" 123#include "coretypes.h" 124#include "tm.h" 125#include "tree.h" 126#include "tree-inline.h" 127#include "langhooks.h" 128#include "flags.h" 129#include "cgraph.h" 130#include "diagnostic.h" 131#include "timevar.h" 132#include "params.h" 133#include "fibheap.h" 134#include "intl.h" 135#include "tree-pass.h" 136#include "hashtab.h" 137#include "coverage.h" 138#include "ggc.h" 139#include "tree-flow.h" 140#include "rtl.h" 141#include "ipa-prop.h" 142#include "except.h" 143 144#define MAX_TIME 1000000000 145 146/* Mode incremental inliner operate on: 147 148 In ALWAYS_INLINE only functions marked 149 always_inline are inlined. This mode is used after detecting cycle during 150 flattening. 151 152 In SIZE mode, only functions that reduce function body size after inlining 153 are inlined, this is used during early inlining. 154 155 in ALL mode, everything is inlined. This is used during flattening. */ 156enum inlining_mode { 157 INLINE_NONE = 0, 158 INLINE_ALWAYS_INLINE, 159 INLINE_SIZE_NORECURSIVE, 160 INLINE_SIZE, 161 INLINE_ALL 162}; 163static bool 164cgraph_decide_inlining_incrementally (struct cgraph_node *, enum inlining_mode, 165 int); 166 167 168/* Statistics we collect about inlining algorithm. */ 169static int ncalls_inlined; 170static int nfunctions_inlined; 171static int overall_size; 172static gcov_type max_count, max_benefit; 173 174/* Holders of ipa cgraph hooks: */ 175static struct cgraph_node_hook_list *function_insertion_hook_holder; 176 177static inline struct inline_summary * 178inline_summary (struct cgraph_node *node) 179{ 180 return &node->local.inline_summary; 181} 182 183/* Estimate self time of the function after inlining WHAT into TO. */ 184 185static int 186cgraph_estimate_time_after_inlining (int frequency, struct cgraph_node *to, 187 struct cgraph_node *what) 188{ 189 gcov_type time = (((gcov_type)what->global.time 190 - inline_summary (what)->time_inlining_benefit) 191 * frequency + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE 192 + to->global.time; 193 if (time < 0) 194 time = 0; 195 if (time > MAX_TIME) 196 time = MAX_TIME; 197 return time; 198} 199 200/* Estimate self time of the function after inlining WHAT into TO. */ 201 202static int 203cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to, 204 struct cgraph_node *what) 205{ 206 int size = (what->global.size - inline_summary (what)->size_inlining_benefit) * times + to->global.size; 207 gcc_assert (size >= 0); 208 return size; 209} 210 211/* Scale frequency of NODE edges by FREQ_SCALE and increase loop nest 212 by NEST. */ 213 214static void 215update_noncloned_frequencies (struct cgraph_node *node, 216 int freq_scale, int nest) 217{ 218 struct cgraph_edge *e; 219 220 /* We do not want to ignore high loop nest after freq drops to 0. */ 221 if (!freq_scale) 222 freq_scale = 1; 223 for (e = node->callees; e; e = e->next_callee) 224 { 225 e->loop_nest += nest; 226 e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE; 227 if (e->frequency > CGRAPH_FREQ_MAX) 228 e->frequency = CGRAPH_FREQ_MAX; 229 if (!e->inline_failed) 230 update_noncloned_frequencies (e->callee, freq_scale, nest); 231 } 232} 233 234/* E is expected to be an edge being inlined. Clone destination node of 235 the edge and redirect it to the new clone. 236 DUPLICATE is used for bookkeeping on whether we are actually creating new 237 clones or re-using node originally representing out-of-line function call. 238 */ 239void 240cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate, 241 bool update_original) 242{ 243 HOST_WIDE_INT peak; 244 245 if (duplicate) 246 { 247 /* We may eliminate the need for out-of-line copy to be output. 248 In that case just go ahead and re-use it. */ 249 if (!e->callee->callers->next_caller 250 && cgraph_can_remove_if_no_direct_calls_p (e->callee) 251 /* Don't reuse if more than one function shares a comdat group. 252 If the other function(s) are needed, we need to emit even 253 this function out of line. */ 254 && !e->callee->same_comdat_group 255 && !cgraph_new_nodes) 256 { 257 gcc_assert (!e->callee->global.inlined_to); 258 if (e->callee->analyzed) 259 { 260 overall_size -= e->callee->global.size; 261 nfunctions_inlined++; 262 } 263 duplicate = false; 264 e->callee->local.externally_visible = false; 265 update_noncloned_frequencies (e->callee, e->frequency, e->loop_nest); 266 } 267 else 268 { 269 struct cgraph_node *n; 270 n = cgraph_clone_node (e->callee, e->count, e->frequency, e->loop_nest, 271 update_original, NULL); 272 cgraph_redirect_edge_callee (e, n); 273 } 274 } 275 276 if (e->caller->global.inlined_to) 277 e->callee->global.inlined_to = e->caller->global.inlined_to; 278 else 279 e->callee->global.inlined_to = e->caller; 280 e->callee->global.stack_frame_offset 281 = e->caller->global.stack_frame_offset 282 + inline_summary (e->caller)->estimated_self_stack_size; 283 peak = e->callee->global.stack_frame_offset 284 + inline_summary (e->callee)->estimated_self_stack_size; 285 if (e->callee->global.inlined_to->global.estimated_stack_size < peak) 286 e->callee->global.inlined_to->global.estimated_stack_size = peak; 287 288 /* Recursively clone all bodies. */ 289 for (e = e->callee->callees; e; e = e->next_callee) 290 if (!e->inline_failed) 291 cgraph_clone_inlined_nodes (e, duplicate, update_original); 292} 293 294/* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL 295 specify whether profile of original function should be updated. If any new 296 indirect edges are discovered in the process, add them to NEW_EDGES, unless 297 it is NULL. Return true iff any new callgraph edges were discovered as a 298 result of inlining. */ 299 300static bool 301cgraph_mark_inline_edge (struct cgraph_edge *e, bool update_original, 302 VEC (cgraph_edge_p, heap) **new_edges) 303{ 304 int old_size = 0, new_size = 0; 305 struct cgraph_node *to = NULL, *what; 306 struct cgraph_edge *curr = e; 307 int freq; 308 309 gcc_assert (e->inline_failed); 310 e->inline_failed = CIF_OK; 311 312 if (!e->callee->global.inlined) 313 DECL_POSSIBLY_INLINED (e->callee->decl) = true; 314 e->callee->global.inlined = true; 315 316 cgraph_clone_inlined_nodes (e, true, update_original); 317 318 what = e->callee; 319 320 freq = e->frequency; 321 /* Now update size of caller and all functions caller is inlined into. */ 322 for (;e && !e->inline_failed; e = e->caller->callers) 323 { 324 to = e->caller; 325 old_size = e->caller->global.size; 326 new_size = cgraph_estimate_size_after_inlining (1, to, what); 327 to->global.size = new_size; 328 to->global.time = cgraph_estimate_time_after_inlining (freq, to, what); 329 } 330 gcc_assert (what->global.inlined_to == to); 331 if (new_size > old_size) 332 overall_size += new_size - old_size; 333 ncalls_inlined++; 334 335 if (flag_indirect_inlining) 336 return ipa_propagate_indirect_call_infos (curr, new_edges); 337 else 338 return false; 339} 340 341/* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER. 342 Return following unredirected edge in the list of callers 343 of EDGE->CALLEE */ 344 345static struct cgraph_edge * 346cgraph_mark_inline (struct cgraph_edge *edge) 347{ 348 struct cgraph_node *to = edge->caller; 349 struct cgraph_node *what = edge->callee; 350 struct cgraph_edge *e, *next; 351 352 gcc_assert (!edge->call_stmt_cannot_inline_p); 353 /* Look for all calls, mark them inline and clone recursively 354 all inlined functions. */ 355 for (e = what->callers; e; e = next) 356 { 357 next = e->next_caller; 358 if (e->caller == to && e->inline_failed) 359 { 360 cgraph_mark_inline_edge (e, true, NULL); 361 if (e == edge) 362 edge = next; 363 } 364 } 365 366 return edge; 367} 368 369/* Estimate the growth caused by inlining NODE into all callees. */ 370 371static int 372cgraph_estimate_growth (struct cgraph_node *node) 373{ 374 int growth = 0; 375 struct cgraph_edge *e; 376 bool self_recursive = false; 377 378 if (node->global.estimated_growth != INT_MIN) 379 return node->global.estimated_growth; 380 381 for (e = node->callers; e; e = e->next_caller) 382 { 383 if (e->caller == node) 384 self_recursive = true; 385 if (e->inline_failed) 386 growth += (cgraph_estimate_size_after_inlining (1, e->caller, node) 387 - e->caller->global.size); 388 } 389 390 /* ??? Wrong for non-trivially self recursive functions or cases where 391 we decide to not inline for different reasons, but it is not big deal 392 as in that case we will keep the body around, but we will also avoid 393 some inlining. */ 394 if (cgraph_only_called_directly_p (node) 395 && !DECL_EXTERNAL (node->decl) && !self_recursive) 396 growth -= node->global.size; 397 398 node->global.estimated_growth = growth; 399 return growth; 400} 401 402/* Return false when inlining WHAT into TO is not good idea 403 as it would cause too large growth of function bodies. 404 When ONE_ONLY is true, assume that only one call site is going 405 to be inlined, otherwise figure out how many call sites in 406 TO calls WHAT and verify that all can be inlined. 407 */ 408 409static bool 410cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what, 411 cgraph_inline_failed_t *reason, bool one_only) 412{ 413 int times = 0; 414 struct cgraph_edge *e; 415 int newsize; 416 int limit; 417 HOST_WIDE_INT stack_size_limit, inlined_stack; 418 419 if (one_only) 420 times = 1; 421 else 422 for (e = to->callees; e; e = e->next_callee) 423 if (e->callee == what) 424 times++; 425 426 if (to->global.inlined_to) 427 to = to->global.inlined_to; 428 429 /* When inlining large function body called once into small function, 430 take the inlined function as base for limiting the growth. */ 431 if (inline_summary (to)->self_size > inline_summary(what)->self_size) 432 limit = inline_summary (to)->self_size; 433 else 434 limit = inline_summary (what)->self_size; 435 436 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100; 437 438 /* Check the size after inlining against the function limits. But allow 439 the function to shrink if it went over the limits by forced inlining. */ 440 newsize = cgraph_estimate_size_after_inlining (times, to, what); 441 if (newsize >= to->global.size 442 && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS) 443 && newsize > limit) 444 { 445 if (reason) 446 *reason = CIF_LARGE_FUNCTION_GROWTH_LIMIT; 447 return false; 448 } 449 450 stack_size_limit = inline_summary (to)->estimated_self_stack_size; 451 452 stack_size_limit += stack_size_limit * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100; 453 454 inlined_stack = (to->global.stack_frame_offset 455 + inline_summary (to)->estimated_self_stack_size 456 + what->global.estimated_stack_size); 457 if (inlined_stack > stack_size_limit 458 && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME)) 459 { 460 if (reason) 461 *reason = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT; 462 return false; 463 } 464 return true; 465} 466 467/* Return true when function N is small enough to be inlined. */ 468 469static bool 470cgraph_default_inline_p (struct cgraph_node *n, cgraph_inline_failed_t *reason) 471{ 472 tree decl = n->decl; 473 474 if (!flag_inline_small_functions && !DECL_DECLARED_INLINE_P (decl)) 475 { 476 if (reason) 477 *reason = CIF_FUNCTION_NOT_INLINE_CANDIDATE; 478 return false; 479 } 480 481 if (!n->analyzed) 482 { 483 if (reason) 484 *reason = CIF_BODY_NOT_AVAILABLE; 485 return false; 486 } 487 488 if (DECL_DECLARED_INLINE_P (decl)) 489 { 490 if (n->global.size >= MAX_INLINE_INSNS_SINGLE) 491 { 492 if (reason) 493 *reason = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT; 494 return false; 495 } 496 } 497 else 498 { 499 if (n->global.size >= MAX_INLINE_INSNS_AUTO) 500 { 501 if (reason) 502 *reason = CIF_MAX_INLINE_INSNS_AUTO_LIMIT; 503 return false; 504 } 505 } 506 507 return true; 508} 509 510/* Return true when inlining WHAT would create recursive inlining. 511 We call recursive inlining all cases where same function appears more than 512 once in the single recursion nest path in the inline graph. */ 513 514static bool 515cgraph_recursive_inlining_p (struct cgraph_node *to, 516 struct cgraph_node *what, 517 cgraph_inline_failed_t *reason) 518{ 519 bool recursive; 520 if (to->global.inlined_to) 521 recursive = what->decl == to->global.inlined_to->decl; 522 else 523 recursive = what->decl == to->decl; 524 /* Marking recursive function inline has sane semantic and thus we should 525 not warn on it. */ 526 if (recursive && reason) 527 *reason = (what->local.disregard_inline_limits 528 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED); 529 return recursive; 530} 531 532/* A cost model driving the inlining heuristics in a way so the edges with 533 smallest badness are inlined first. After each inlining is performed 534 the costs of all caller edges of nodes affected are recomputed so the 535 metrics may accurately depend on values such as number of inlinable callers 536 of the function or function body size. */ 537 538static int 539cgraph_edge_badness (struct cgraph_edge *edge, bool dump) 540{ 541 gcov_type badness; 542 int growth = 543 (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee) 544 - edge->caller->global.size); 545 546 if (edge->callee->local.disregard_inline_limits) 547 return INT_MIN; 548 549 if (dump) 550 { 551 fprintf (dump_file, " Badness calculcation for %s -> %s\n", 552 cgraph_node_name (edge->caller), 553 cgraph_node_name (edge->callee)); 554 fprintf (dump_file, " growth %i, time %i-%i, size %i-%i\n", 555 growth, 556 edge->callee->global.time, 557 inline_summary (edge->callee)->time_inlining_benefit, 558 edge->callee->global.size, 559 inline_summary (edge->callee)->size_inlining_benefit); 560 } 561 562 /* Always prefer inlining saving code size. */ 563 if (growth <= 0) 564 { 565 badness = INT_MIN - growth; 566 if (dump) 567 fprintf (dump_file, " %i: Growth %i < 0\n", (int) badness, 568 growth); 569 } 570 571 /* When profiling is available, base priorities -(#calls / growth). 572 So we optimize for overall number of "executed" inlined calls. */ 573 else if (max_count) 574 { 575 badness = 576 ((int) 577 ((double) edge->count * INT_MIN / max_count / (max_benefit + 1)) * 578 (inline_summary (edge->callee)->time_inlining_benefit + 1)) / growth; 579 if (dump) 580 { 581 fprintf (dump_file, 582 " %i (relative %f): profile info. Relative count %f" 583 " * Relative benefit %f\n", 584 (int) badness, (double) badness / INT_MIN, 585 (double) edge->count / max_count, 586 (double) (inline_summary (edge->callee)-> 587 time_inlining_benefit + 1) / (max_benefit + 1)); 588 } 589 } 590 591 /* When function local profile is available, base priorities on 592 growth / frequency, so we optimize for overall frequency of inlined 593 calls. This is not too accurate since while the call might be frequent 594 within function, the function itself is infrequent. 595 596 Other objective to optimize for is number of different calls inlined. 597 We add the estimated growth after inlining all functions to bias the 598 priorities slightly in this direction (so fewer times called functions 599 of the same size gets priority). */ 600 else if (flag_guess_branch_prob) 601 { 602 int div = edge->frequency * 100 / CGRAPH_FREQ_BASE + 1; 603 int benefitperc; 604 int growth_for_all; 605 badness = growth * 10000; 606 benefitperc = 607 MIN (100 * inline_summary (edge->callee)->time_inlining_benefit / 608 (edge->callee->global.time + 1) +1, 100); 609 div *= benefitperc; 610 611 612 /* Decrease badness if call is nested. */ 613 /* Compress the range so we don't overflow. */ 614 if (div > 10000) 615 div = 10000 + ceil_log2 (div) - 8; 616 if (div < 1) 617 div = 1; 618 if (badness > 0) 619 badness /= div; 620 growth_for_all = cgraph_estimate_growth (edge->callee); 621 badness += growth_for_all; 622 if (badness > INT_MAX) 623 badness = INT_MAX; 624 if (dump) 625 { 626 fprintf (dump_file, 627 " %i: guessed profile. frequency %i, overall growth %i," 628 " benefit %i%%, divisor %i\n", 629 (int) badness, edge->frequency, growth_for_all, benefitperc, div); 630 } 631 } 632 /* When function local profile is not available or it does not give 633 useful information (ie frequency is zero), base the cost on 634 loop nest and overall size growth, so we optimize for overall number 635 of functions fully inlined in program. */ 636 else 637 { 638 int nest = MIN (edge->loop_nest, 8); 639 badness = cgraph_estimate_growth (edge->callee) * 256; 640 641 /* Decrease badness if call is nested. */ 642 if (badness > 0) 643 badness >>= nest; 644 else 645 { 646 badness <<= nest; 647 } 648 if (dump) 649 fprintf (dump_file, " %i: no profile. nest %i\n", (int) badness, 650 nest); 651 } 652 653 /* Make recursive inlining happen always after other inlining is done. */ 654 if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL)) 655 return badness + 1; 656 else 657 return badness; 658} 659 660/* Recompute heap nodes for each of caller edge. */ 661 662static void 663update_caller_keys (fibheap_t heap, struct cgraph_node *node, 664 bitmap updated_nodes) 665{ 666 struct cgraph_edge *edge; 667 cgraph_inline_failed_t failed_reason; 668 669 if (!node->local.inlinable || node->local.disregard_inline_limits 670 || node->global.inlined_to) 671 return; 672 if (bitmap_bit_p (updated_nodes, node->uid)) 673 return; 674 bitmap_set_bit (updated_nodes, node->uid); 675 node->global.estimated_growth = INT_MIN; 676 677 if (!node->local.inlinable) 678 return; 679 /* See if there is something to do. */ 680 for (edge = node->callers; edge; edge = edge->next_caller) 681 if (edge->inline_failed) 682 break; 683 if (!edge) 684 return; 685 /* Prune out edges we won't inline into anymore. */ 686 if (!cgraph_default_inline_p (node, &failed_reason)) 687 { 688 for (; edge; edge = edge->next_caller) 689 if (edge->aux) 690 { 691 fibheap_delete_node (heap, (fibnode_t) edge->aux); 692 edge->aux = NULL; 693 if (edge->inline_failed) 694 edge->inline_failed = failed_reason; 695 } 696 return; 697 } 698 699 for (; edge; edge = edge->next_caller) 700 if (edge->inline_failed) 701 { 702 int badness = cgraph_edge_badness (edge, false); 703 if (edge->aux) 704 { 705 fibnode_t n = (fibnode_t) edge->aux; 706 gcc_assert (n->data == edge); 707 if (n->key == badness) 708 continue; 709 710 /* fibheap_replace_key only decrease the keys. 711 When we increase the key we do not update heap 712 and instead re-insert the element once it becomes 713 a minium of heap. */ 714 if (badness < n->key) 715 { 716 fibheap_replace_key (heap, n, badness); 717 gcc_assert (n->key == badness); 718 continue; 719 } 720 } 721 else 722 edge->aux = fibheap_insert (heap, badness, edge); 723 } 724} 725 726/* Recompute heap nodes for each of caller edges of each of callees. 727 Walk recursively into all inline clones. */ 728 729static void 730update_callee_keys (fibheap_t heap, struct cgraph_node *node, 731 bitmap updated_nodes) 732{ 733 struct cgraph_edge *e = node->callees; 734 node->global.estimated_growth = INT_MIN; 735 736 if (!e) 737 return; 738 while (true) 739 if (!e->inline_failed && e->callee->callees) 740 e = e->callee->callees; 741 else 742 { 743 if (e->inline_failed) 744 update_caller_keys (heap, e->callee, updated_nodes); 745 if (e->next_callee) 746 e = e->next_callee; 747 else 748 { 749 do 750 { 751 if (e->caller == node) 752 return; 753 e = e->caller->callers; 754 } 755 while (!e->next_callee); 756 e = e->next_callee; 757 } 758 } 759} 760 761/* Enqueue all recursive calls from NODE into priority queue depending on 762 how likely we want to recursively inline the call. */ 763 764static void 765lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where, 766 fibheap_t heap) 767{ 768 static int priority; 769 struct cgraph_edge *e; 770 for (e = where->callees; e; e = e->next_callee) 771 if (e->callee == node) 772 { 773 /* When profile feedback is available, prioritize by expected number 774 of calls. Without profile feedback we maintain simple queue 775 to order candidates via recursive depths. */ 776 fibheap_insert (heap, 777 !max_count ? priority++ 778 : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))), 779 e); 780 } 781 for (e = where->callees; e; e = e->next_callee) 782 if (!e->inline_failed) 783 lookup_recursive_calls (node, e->callee, heap); 784} 785 786/* Decide on recursive inlining: in the case function has recursive calls, 787 inline until body size reaches given argument. If any new indirect edges 788 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES 789 is NULL. */ 790 791static bool 792cgraph_decide_recursive_inlining (struct cgraph_node *node, 793 VEC (cgraph_edge_p, heap) **new_edges) 794{ 795 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO); 796 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO); 797 int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY); 798 fibheap_t heap; 799 struct cgraph_edge *e; 800 struct cgraph_node *master_clone, *next; 801 int depth = 0; 802 int n = 0; 803 804 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl)) 805 || (!flag_inline_functions && !DECL_DECLARED_INLINE_P (node->decl))) 806 return false; 807 808 if (DECL_DECLARED_INLINE_P (node->decl)) 809 { 810 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE); 811 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH); 812 } 813 814 /* Make sure that function is small enough to be considered for inlining. */ 815 if (!max_depth 816 || cgraph_estimate_size_after_inlining (1, node, node) >= limit) 817 return false; 818 heap = fibheap_new (); 819 lookup_recursive_calls (node, node, heap); 820 if (fibheap_empty (heap)) 821 { 822 fibheap_delete (heap); 823 return false; 824 } 825 826 if (dump_file) 827 fprintf (dump_file, 828 " Performing recursive inlining on %s\n", 829 cgraph_node_name (node)); 830 831 /* We need original clone to copy around. */ 832 master_clone = cgraph_clone_node (node, node->count, CGRAPH_FREQ_BASE, 1, 833 false, NULL); 834 master_clone->needed = true; 835 for (e = master_clone->callees; e; e = e->next_callee) 836 if (!e->inline_failed) 837 cgraph_clone_inlined_nodes (e, true, false); 838 839 /* Do the inlining and update list of recursive call during process. */ 840 while (!fibheap_empty (heap) 841 && (cgraph_estimate_size_after_inlining (1, node, master_clone) 842 <= limit)) 843 { 844 struct cgraph_edge *curr 845 = (struct cgraph_edge *) fibheap_extract_min (heap); 846 struct cgraph_node *cnode; 847 848 depth = 1; 849 for (cnode = curr->caller; 850 cnode->global.inlined_to; cnode = cnode->callers->caller) 851 if (node->decl == curr->callee->decl) 852 depth++; 853 if (depth > max_depth) 854 { 855 if (dump_file) 856 fprintf (dump_file, 857 " maximal depth reached\n"); 858 continue; 859 } 860 861 if (max_count) 862 { 863 if (!cgraph_maybe_hot_edge_p (curr)) 864 { 865 if (dump_file) 866 fprintf (dump_file, " Not inlining cold call\n"); 867 continue; 868 } 869 if (curr->count * 100 / node->count < probability) 870 { 871 if (dump_file) 872 fprintf (dump_file, 873 " Probability of edge is too small\n"); 874 continue; 875 } 876 } 877 878 if (dump_file) 879 { 880 fprintf (dump_file, 881 " Inlining call of depth %i", depth); 882 if (node->count) 883 { 884 fprintf (dump_file, " called approx. %.2f times per call", 885 (double)curr->count / node->count); 886 } 887 fprintf (dump_file, "\n"); 888 } 889 cgraph_redirect_edge_callee (curr, master_clone); 890 cgraph_mark_inline_edge (curr, false, new_edges); 891 lookup_recursive_calls (node, curr->callee, heap); 892 n++; 893 } 894 if (!fibheap_empty (heap) && dump_file) 895 fprintf (dump_file, " Recursive inlining growth limit met.\n"); 896 897 fibheap_delete (heap); 898 if (dump_file) 899 fprintf (dump_file, 900 "\n Inlined %i times, body grown from size %i to %i, time %i to %i\n", n, 901 master_clone->global.size, node->global.size, 902 master_clone->global.time, node->global.time); 903 904 /* Remove master clone we used for inlining. We rely that clones inlined 905 into master clone gets queued just before master clone so we don't 906 need recursion. */ 907 for (node = cgraph_nodes; node != master_clone; 908 node = next) 909 { 910 next = node->next; 911 if (node->global.inlined_to == master_clone) 912 cgraph_remove_node (node); 913 } 914 cgraph_remove_node (master_clone); 915 /* FIXME: Recursive inlining actually reduces number of calls of the 916 function. At this place we should probably walk the function and 917 inline clones and compensate the counts accordingly. This probably 918 doesn't matter much in practice. */ 919 return n > 0; 920} 921 922/* Set inline_failed for all callers of given function to REASON. */ 923 924static void 925cgraph_set_inline_failed (struct cgraph_node *node, 926 cgraph_inline_failed_t reason) 927{ 928 struct cgraph_edge *e; 929 930 if (dump_file) 931 fprintf (dump_file, "Inlining failed: %s\n", 932 cgraph_inline_failed_string (reason)); 933 for (e = node->callers; e; e = e->next_caller) 934 if (e->inline_failed) 935 e->inline_failed = reason; 936} 937 938/* Given whole compilation unit estimate of INSNS, compute how large we can 939 allow the unit to grow. */ 940static int 941compute_max_insns (int insns) 942{ 943 int max_insns = insns; 944 if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS)) 945 max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS); 946 947 return ((HOST_WIDEST_INT) max_insns 948 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100); 949} 950 951/* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */ 952static void 953add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges) 954{ 955 while (VEC_length (cgraph_edge_p, new_edges) > 0) 956 { 957 struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges); 958 959 gcc_assert (!edge->aux); 960 if (edge->callee->local.inlinable 961 && cgraph_default_inline_p (edge->callee, &edge->inline_failed)) 962 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge); 963 } 964} 965 966 967/* We use greedy algorithm for inlining of small functions: 968 All inline candidates are put into prioritized heap based on estimated 969 growth of the overall number of instructions and then update the estimates. 970 971 INLINED and INLINED_CALEES are just pointers to arrays large enough 972 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */ 973 974static void 975cgraph_decide_inlining_of_small_functions (void) 976{ 977 struct cgraph_node *node; 978 struct cgraph_edge *edge; 979 cgraph_inline_failed_t failed_reason; 980 fibheap_t heap = fibheap_new (); 981 bitmap updated_nodes = BITMAP_ALLOC (NULL); 982 int min_size, max_size; 983 VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL; 984 985 if (flag_indirect_inlining) 986 new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8); 987 988 if (dump_file) 989 fprintf (dump_file, "\nDeciding on smaller functions:\n"); 990 991 /* Put all inline candidates into the heap. */ 992 993 for (node = cgraph_nodes; node; node = node->next) 994 { 995 if (!node->local.inlinable || !node->callers 996 || node->local.disregard_inline_limits) 997 continue; 998 if (dump_file) 999 fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node)); 1000 1001 node->global.estimated_growth = INT_MIN; 1002 if (!cgraph_default_inline_p (node, &failed_reason)) 1003 { 1004 cgraph_set_inline_failed (node, failed_reason); 1005 continue; 1006 } 1007 1008 for (edge = node->callers; edge; edge = edge->next_caller) 1009 if (edge->inline_failed) 1010 { 1011 gcc_assert (!edge->aux); 1012 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge); 1013 } 1014 } 1015 1016 max_size = compute_max_insns (overall_size); 1017 min_size = overall_size; 1018 1019 while (overall_size <= max_size 1020 && !fibheap_empty (heap)) 1021 { 1022 int old_size = overall_size; 1023 struct cgraph_node *where, *callee; 1024 int badness = fibheap_min_key (heap); 1025 int current_badness; 1026 int growth; 1027 cgraph_inline_failed_t not_good = CIF_OK; 1028 1029 edge = (struct cgraph_edge *) fibheap_extract_min (heap); 1030 gcc_assert (edge->aux); 1031 edge->aux = NULL; 1032 if (!edge->inline_failed) 1033 continue; 1034 1035 /* When updating the edge costs, we only decrease badness in the keys. 1036 When the badness increase, we keep the heap as it is and re-insert 1037 key now. */ 1038 current_badness = cgraph_edge_badness (edge, false); 1039 gcc_assert (current_badness >= badness); 1040 if (current_badness != badness) 1041 { 1042 edge->aux = fibheap_insert (heap, current_badness, edge); 1043 continue; 1044 } 1045 1046 callee = edge->callee; 1047 1048 growth = (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee) 1049 - edge->caller->global.size); 1050 1051 if (dump_file) 1052 { 1053 fprintf (dump_file, 1054 "\nConsidering %s with %i size\n", 1055 cgraph_node_name (edge->callee), 1056 edge->callee->global.size); 1057 fprintf (dump_file, 1058 " to be inlined into %s in %s:%i\n" 1059 " Estimated growth after inlined into all callees is %+i insns.\n" 1060 " Estimated badness is %i, frequency %.2f.\n", 1061 cgraph_node_name (edge->caller), 1062 flag_wpa ? "unknown" 1063 : gimple_filename ((const_gimple) edge->call_stmt), 1064 flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt), 1065 cgraph_estimate_growth (edge->callee), 1066 badness, 1067 edge->frequency / (double)CGRAPH_FREQ_BASE); 1068 if (edge->count) 1069 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count); 1070 if (dump_flags & TDF_DETAILS) 1071 cgraph_edge_badness (edge, true); 1072 } 1073 1074 /* When not having profile info ready we don't weight by any way the 1075 position of call in procedure itself. This means if call of 1076 function A from function B seems profitable to inline, the recursive 1077 call of function A in inline copy of A in B will look profitable too 1078 and we end up inlining until reaching maximal function growth. This 1079 is not good idea so prohibit the recursive inlining. 1080 1081 ??? When the frequencies are taken into account we might not need this 1082 restriction. 1083 1084 We need to be cureful here, in some testcases, e.g. directivec.c in 1085 libcpp, we can estimate self recursive function to have negative growth 1086 for inlining completely. 1087 */ 1088 if (!edge->count) 1089 { 1090 where = edge->caller; 1091 while (where->global.inlined_to) 1092 { 1093 if (where->decl == edge->callee->decl) 1094 break; 1095 where = where->callers->caller; 1096 } 1097 if (where->global.inlined_to) 1098 { 1099 edge->inline_failed 1100 = (edge->callee->local.disregard_inline_limits 1101 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED); 1102 if (dump_file) 1103 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n"); 1104 continue; 1105 } 1106 } 1107 1108 if (!cgraph_maybe_hot_edge_p (edge)) 1109 not_good = CIF_UNLIKELY_CALL; 1110 if (!flag_inline_functions 1111 && !DECL_DECLARED_INLINE_P (edge->callee->decl)) 1112 not_good = CIF_NOT_DECLARED_INLINED; 1113 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION(edge->caller->decl))) 1114 not_good = CIF_OPTIMIZING_FOR_SIZE; 1115 if (not_good && growth > 0 && cgraph_estimate_growth (edge->callee) > 0) 1116 { 1117 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee, 1118 &edge->inline_failed)) 1119 { 1120 edge->inline_failed = not_good; 1121 if (dump_file) 1122 fprintf (dump_file, " inline_failed:%s.\n", 1123 cgraph_inline_failed_string (edge->inline_failed)); 1124 } 1125 continue; 1126 } 1127 if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed)) 1128 { 1129 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee, 1130 &edge->inline_failed)) 1131 { 1132 if (dump_file) 1133 fprintf (dump_file, " inline_failed:%s.\n", 1134 cgraph_inline_failed_string (edge->inline_failed)); 1135 } 1136 continue; 1137 } 1138 if (!tree_can_inline_p (edge)) 1139 { 1140 if (dump_file) 1141 fprintf (dump_file, " inline_failed:%s.\n", 1142 cgraph_inline_failed_string (edge->inline_failed)); 1143 continue; 1144 } 1145 if (cgraph_recursive_inlining_p (edge->caller, edge->callee, 1146 &edge->inline_failed)) 1147 { 1148 where = edge->caller; 1149 if (where->global.inlined_to) 1150 where = where->global.inlined_to; 1151 if (!cgraph_decide_recursive_inlining (where, 1152 flag_indirect_inlining 1153 ? &new_indirect_edges : NULL)) 1154 continue; 1155 if (flag_indirect_inlining) 1156 add_new_edges_to_heap (heap, new_indirect_edges); 1157 update_callee_keys (heap, where, updated_nodes); 1158 } 1159 else 1160 { 1161 struct cgraph_node *callee; 1162 if (edge->call_stmt_cannot_inline_p 1163 || !cgraph_check_inline_limits (edge->caller, edge->callee, 1164 &edge->inline_failed, true)) 1165 { 1166 if (dump_file) 1167 fprintf (dump_file, " Not inlining into %s:%s.\n", 1168 cgraph_node_name (edge->caller), 1169 cgraph_inline_failed_string (edge->inline_failed)); 1170 continue; 1171 } 1172 callee = edge->callee; 1173 cgraph_mark_inline_edge (edge, true, &new_indirect_edges); 1174 if (flag_indirect_inlining) 1175 add_new_edges_to_heap (heap, new_indirect_edges); 1176 1177 update_callee_keys (heap, callee, updated_nodes); 1178 } 1179 where = edge->caller; 1180 if (where->global.inlined_to) 1181 where = where->global.inlined_to; 1182 1183 /* Our profitability metric can depend on local properties 1184 such as number of inlinable calls and size of the function body. 1185 After inlining these properties might change for the function we 1186 inlined into (since it's body size changed) and for the functions 1187 called by function we inlined (since number of it inlinable callers 1188 might change). */ 1189 update_caller_keys (heap, where, updated_nodes); 1190 1191 /* We removed one call of the function we just inlined. If offline 1192 copy is still needed, be sure to update the keys. */ 1193 if (callee != where && !callee->global.inlined_to) 1194 update_caller_keys (heap, callee, updated_nodes); 1195 bitmap_clear (updated_nodes); 1196 1197 if (dump_file) 1198 { 1199 fprintf (dump_file, 1200 " Inlined into %s which now has size %i and self time %i," 1201 "net change of %+i.\n", 1202 cgraph_node_name (edge->caller), 1203 edge->caller->global.time, 1204 edge->caller->global.size, 1205 overall_size - old_size); 1206 } 1207 if (min_size > overall_size) 1208 { 1209 min_size = overall_size; 1210 max_size = compute_max_insns (min_size); 1211 1212 if (dump_file) 1213 fprintf (dump_file, "New minimal size reached: %i\n", min_size); 1214 } 1215 } 1216 while ((edge = (struct cgraph_edge *) fibheap_extract_min (heap)) != NULL) 1217 { 1218 gcc_assert (edge->aux); 1219 edge->aux = NULL; 1220 if (!edge->callee->local.disregard_inline_limits && edge->inline_failed 1221 && !cgraph_recursive_inlining_p (edge->caller, edge->callee, 1222 &edge->inline_failed)) 1223 edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT; 1224 } 1225 1226 if (new_indirect_edges) 1227 VEC_free (cgraph_edge_p, heap, new_indirect_edges); 1228 fibheap_delete (heap); 1229 BITMAP_FREE (updated_nodes); 1230} 1231 1232/* Decide on the inlining. We do so in the topological order to avoid 1233 expenses on updating data structures. */ 1234 1235static unsigned int 1236cgraph_decide_inlining (void) 1237{ 1238 struct cgraph_node *node; 1239 int nnodes; 1240 struct cgraph_node **order = 1241 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); 1242 int old_size = 0; 1243 int i; 1244 bool redo_always_inline = true; 1245 int initial_size = 0; 1246 1247 cgraph_remove_function_insertion_hook (function_insertion_hook_holder); 1248 if (in_lto_p && flag_indirect_inlining) 1249 ipa_update_after_lto_read (); 1250 1251 max_count = 0; 1252 max_benefit = 0; 1253 for (node = cgraph_nodes; node; node = node->next) 1254 if (node->analyzed) 1255 { 1256 struct cgraph_edge *e; 1257 1258 gcc_assert (inline_summary (node)->self_size == node->global.size); 1259 initial_size += node->global.size; 1260 for (e = node->callees; e; e = e->next_callee) 1261 if (max_count < e->count) 1262 max_count = e->count; 1263 if (max_benefit < inline_summary (node)->time_inlining_benefit) 1264 max_benefit = inline_summary (node)->time_inlining_benefit; 1265 } 1266 gcc_assert (in_lto_p 1267 || !max_count 1268 || (profile_info && flag_branch_probabilities)); 1269 overall_size = initial_size; 1270 1271 nnodes = cgraph_postorder (order); 1272 1273 if (dump_file) 1274 fprintf (dump_file, 1275 "\nDeciding on inlining. Starting with size %i.\n", 1276 initial_size); 1277 1278 for (node = cgraph_nodes; node; node = node->next) 1279 node->aux = 0; 1280 1281 if (dump_file) 1282 fprintf (dump_file, "\nInlining always_inline functions:\n"); 1283 1284 /* In the first pass mark all always_inline edges. Do this with a priority 1285 so none of our later choices will make this impossible. */ 1286 while (redo_always_inline) 1287 { 1288 redo_always_inline = false; 1289 for (i = nnodes - 1; i >= 0; i--) 1290 { 1291 struct cgraph_edge *e, *next; 1292 1293 node = order[i]; 1294 1295 /* Handle nodes to be flattened, but don't update overall unit 1296 size. */ 1297 if (lookup_attribute ("flatten", 1298 DECL_ATTRIBUTES (node->decl)) != NULL) 1299 { 1300 if (dump_file) 1301 fprintf (dump_file, 1302 "Flattening %s\n", cgraph_node_name (node)); 1303 cgraph_decide_inlining_incrementally (node, INLINE_ALL, 0); 1304 } 1305 1306 if (!node->local.disregard_inline_limits) 1307 continue; 1308 if (dump_file) 1309 fprintf (dump_file, 1310 "\nConsidering %s size:%i (always inline)\n", 1311 cgraph_node_name (node), node->global.size); 1312 old_size = overall_size; 1313 for (e = node->callers; e; e = next) 1314 { 1315 next = e->next_caller; 1316 if (!e->inline_failed || e->call_stmt_cannot_inline_p) 1317 continue; 1318 if (cgraph_recursive_inlining_p (e->caller, e->callee, 1319 &e->inline_failed)) 1320 continue; 1321 if (!tree_can_inline_p (e)) 1322 continue; 1323 if (cgraph_mark_inline_edge (e, true, NULL)) 1324 redo_always_inline = true; 1325 if (dump_file) 1326 fprintf (dump_file, 1327 " Inlined into %s which now has size %i.\n", 1328 cgraph_node_name (e->caller), 1329 e->caller->global.size); 1330 } 1331 /* Inlining self recursive function might introduce new calls to 1332 themselves we didn't see in the loop above. Fill in the proper 1333 reason why inline failed. */ 1334 for (e = node->callers; e; e = e->next_caller) 1335 if (e->inline_failed) 1336 e->inline_failed = CIF_RECURSIVE_INLINING; 1337 if (dump_file) 1338 fprintf (dump_file, 1339 " Inlined for a net change of %+i size.\n", 1340 overall_size - old_size); 1341 } 1342 } 1343 1344 cgraph_decide_inlining_of_small_functions (); 1345 1346 if (flag_inline_functions_called_once) 1347 { 1348 if (dump_file) 1349 fprintf (dump_file, "\nDeciding on functions called once:\n"); 1350 1351 /* And finally decide what functions are called once. */ 1352 for (i = nnodes - 1; i >= 0; i--) 1353 { 1354 node = order[i]; 1355 1356 if (node->callers 1357 && !node->callers->next_caller 1358 && cgraph_only_called_directly_p (node) 1359 && node->local.inlinable 1360 && node->callers->inline_failed 1361 && node->callers->caller != node 1362 && node->callers->caller->global.inlined_to != node 1363 && !node->callers->call_stmt_cannot_inline_p 1364 && !DECL_EXTERNAL (node->decl) 1365 && !DECL_COMDAT (node->decl)) 1366 { 1367 cgraph_inline_failed_t reason; 1368 old_size = overall_size; 1369 if (dump_file) 1370 { 1371 fprintf (dump_file, 1372 "\nConsidering %s size %i.\n", 1373 cgraph_node_name (node), node->global.size); 1374 fprintf (dump_file, 1375 " Called once from %s %i insns.\n", 1376 cgraph_node_name (node->callers->caller), 1377 node->callers->caller->global.size); 1378 } 1379 1380 if (cgraph_check_inline_limits (node->callers->caller, node, 1381 &reason, false)) 1382 { 1383 cgraph_mark_inline (node->callers); 1384 if (dump_file) 1385 fprintf (dump_file, 1386 " Inlined into %s which now has %i size" 1387 " for a net change of %+i size.\n", 1388 cgraph_node_name (node->callers->caller), 1389 node->callers->caller->global.size, 1390 overall_size - old_size); 1391 } 1392 else 1393 { 1394 if (dump_file) 1395 fprintf (dump_file, 1396 " Not inlining: %s.\n", 1397 cgraph_inline_failed_string (reason)); 1398 } 1399 } 1400 } 1401 } 1402 1403 /* Free ipa-prop structures if they are no longer needed. */ 1404 if (flag_indirect_inlining) 1405 free_all_ipa_structures_after_iinln (); 1406 1407 if (dump_file) 1408 fprintf (dump_file, 1409 "\nInlined %i calls, eliminated %i functions, " 1410 "size %i turned to %i size.\n\n", 1411 ncalls_inlined, nfunctions_inlined, initial_size, 1412 overall_size); 1413 free (order); 1414 return 0; 1415} 1416 1417/* Try to inline edge E from incremental inliner. MODE specifies mode 1418 of inliner. 1419 1420 We are detecting cycles by storing mode of inliner into cgraph_node last 1421 time we visited it in the recursion. In general when mode is set, we have 1422 recursive inlining, but as an special case, we want to try harder inline 1423 ALWAYS_INLINE functions: consider callgraph a->b->c->b, with a being 1424 flatten, b being always inline. Flattening 'a' will collapse 1425 a->b->c before hitting cycle. To accommodate always inline, we however 1426 need to inline a->b->c->b. 1427 1428 So after hitting cycle first time, we switch into ALWAYS_INLINE mode and 1429 stop inlining only after hitting ALWAYS_INLINE in ALWAY_INLINE mode. */ 1430static bool 1431try_inline (struct cgraph_edge *e, enum inlining_mode mode, int depth) 1432{ 1433 struct cgraph_node *callee = e->callee; 1434 enum inlining_mode callee_mode = (enum inlining_mode) (size_t) callee->aux; 1435 bool always_inline = e->callee->local.disregard_inline_limits; 1436 bool inlined = false; 1437 1438 /* We've hit cycle? */ 1439 if (callee_mode) 1440 { 1441 /* It is first time we see it and we are not in ALWAY_INLINE only 1442 mode yet. and the function in question is always_inline. */ 1443 if (always_inline && mode != INLINE_ALWAYS_INLINE) 1444 { 1445 if (dump_file) 1446 { 1447 indent_to (dump_file, depth); 1448 fprintf (dump_file, 1449 "Hit cycle in %s, switching to always inline only.\n", 1450 cgraph_node_name (callee)); 1451 } 1452 mode = INLINE_ALWAYS_INLINE; 1453 } 1454 /* Otherwise it is time to give up. */ 1455 else 1456 { 1457 if (dump_file) 1458 { 1459 indent_to (dump_file, depth); 1460 fprintf (dump_file, 1461 "Not inlining %s into %s to avoid cycle.\n", 1462 cgraph_node_name (callee), 1463 cgraph_node_name (e->caller)); 1464 } 1465 e->inline_failed = (e->callee->local.disregard_inline_limits 1466 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED); 1467 return false; 1468 } 1469 } 1470 1471 callee->aux = (void *)(size_t) mode; 1472 if (dump_file) 1473 { 1474 indent_to (dump_file, depth); 1475 fprintf (dump_file, " Inlining %s into %s.\n", 1476 cgraph_node_name (e->callee), 1477 cgraph_node_name (e->caller)); 1478 } 1479 if (e->inline_failed) 1480 { 1481 cgraph_mark_inline (e); 1482 1483 /* In order to fully inline always_inline functions, we need to 1484 recurse here, since the inlined functions might not be processed by 1485 incremental inlining at all yet. 1486 1487 Also flattening needs to be done recursively. */ 1488 1489 if (mode == INLINE_ALL || always_inline) 1490 cgraph_decide_inlining_incrementally (e->callee, mode, depth + 1); 1491 inlined = true; 1492 } 1493 callee->aux = (void *)(size_t) callee_mode; 1494 return inlined; 1495} 1496 1497/* Return true when N is leaf function. Accept cheap (pure&const) builtins 1498 in leaf functions. */ 1499static bool 1500leaf_node_p (struct cgraph_node *n) 1501{ 1502 struct cgraph_edge *e; 1503 for (e = n->callees; e; e = e->next_callee) 1504 if (!DECL_BUILT_IN (e->callee->decl) 1505 || (!TREE_READONLY (e->callee->decl) 1506 || DECL_PURE_P (e->callee->decl))) 1507 return false; 1508 return true; 1509} 1510 1511/* Decide on the inlining. We do so in the topological order to avoid 1512 expenses on updating data structures. 1513 DEPTH is depth of recursion, used only for debug output. */ 1514 1515static bool 1516cgraph_decide_inlining_incrementally (struct cgraph_node *node, 1517 enum inlining_mode mode, 1518 int depth) 1519{ 1520 struct cgraph_edge *e; 1521 bool inlined = false; 1522 cgraph_inline_failed_t failed_reason; 1523 enum inlining_mode old_mode; 1524 1525#ifdef ENABLE_CHECKING 1526 verify_cgraph_node (node); 1527#endif 1528 1529 old_mode = (enum inlining_mode) (size_t)node->aux; 1530 1531 if (mode != INLINE_ALWAYS_INLINE && mode != INLINE_SIZE_NORECURSIVE 1532 && lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL) 1533 { 1534 if (dump_file) 1535 { 1536 indent_to (dump_file, depth); 1537 fprintf (dump_file, "Flattening %s\n", cgraph_node_name (node)); 1538 } 1539 mode = INLINE_ALL; 1540 } 1541 1542 node->aux = (void *)(size_t) mode; 1543 1544 /* First of all look for always inline functions. */ 1545 if (mode != INLINE_SIZE_NORECURSIVE) 1546 for (e = node->callees; e; e = e->next_callee) 1547 { 1548 if (!e->callee->local.disregard_inline_limits 1549 && (mode != INLINE_ALL || !e->callee->local.inlinable)) 1550 continue; 1551 if (e->call_stmt_cannot_inline_p) 1552 continue; 1553 /* When the edge is already inlined, we just need to recurse into 1554 it in order to fully flatten the leaves. */ 1555 if (!e->inline_failed && mode == INLINE_ALL) 1556 { 1557 inlined |= try_inline (e, mode, depth); 1558 continue; 1559 } 1560 if (dump_file) 1561 { 1562 indent_to (dump_file, depth); 1563 fprintf (dump_file, 1564 "Considering to always inline inline candidate %s.\n", 1565 cgraph_node_name (e->callee)); 1566 } 1567 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)) 1568 { 1569 if (dump_file) 1570 { 1571 indent_to (dump_file, depth); 1572 fprintf (dump_file, "Not inlining: recursive call.\n"); 1573 } 1574 continue; 1575 } 1576 if (!tree_can_inline_p (e)) 1577 { 1578 if (dump_file) 1579 { 1580 indent_to (dump_file, depth); 1581 fprintf (dump_file, 1582 "Not inlining: %s", 1583 cgraph_inline_failed_string (e->inline_failed)); 1584 } 1585 continue; 1586 } 1587 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl)) 1588 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl))) 1589 { 1590 if (dump_file) 1591 { 1592 indent_to (dump_file, depth); 1593 fprintf (dump_file, "Not inlining: SSA form does not match.\n"); 1594 } 1595 continue; 1596 } 1597 if (!e->callee->analyzed) 1598 { 1599 if (dump_file) 1600 { 1601 indent_to (dump_file, depth); 1602 fprintf (dump_file, 1603 "Not inlining: Function body no longer available.\n"); 1604 } 1605 continue; 1606 } 1607 inlined |= try_inline (e, mode, depth); 1608 } 1609 1610 /* Now do the automatic inlining. */ 1611 if (mode != INLINE_ALL && mode != INLINE_ALWAYS_INLINE 1612 /* Never inline regular functions into always-inline functions 1613 during incremental inlining. */ 1614 && !node->local.disregard_inline_limits) 1615 { 1616 bitmap visited = BITMAP_ALLOC (NULL); 1617 for (e = node->callees; e; e = e->next_callee) 1618 { 1619 int allowed_growth = 0; 1620 if (!e->callee->local.inlinable 1621 || !e->inline_failed 1622 || e->callee->local.disregard_inline_limits) 1623 continue; 1624 /* We are inlining a function to all call-sites in node 1625 or to none. So visit each candidate only once. */ 1626 if (!bitmap_set_bit (visited, e->callee->uid)) 1627 continue; 1628 if (dump_file) 1629 fprintf (dump_file, "Considering inline candidate %s.\n", 1630 cgraph_node_name (e->callee)); 1631 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)) 1632 { 1633 if (dump_file) 1634 { 1635 indent_to (dump_file, depth); 1636 fprintf (dump_file, "Not inlining: recursive call.\n"); 1637 } 1638 continue; 1639 } 1640 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl)) 1641 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl))) 1642 { 1643 if (dump_file) 1644 { 1645 indent_to (dump_file, depth); 1646 fprintf (dump_file, 1647 "Not inlining: SSA form does not match.\n"); 1648 } 1649 continue; 1650 } 1651 1652 if (cgraph_maybe_hot_edge_p (e) && leaf_node_p (e->callee) 1653 && optimize_function_for_speed_p (cfun)) 1654 allowed_growth = PARAM_VALUE (PARAM_EARLY_INLINING_INSNS); 1655 1656 /* When the function body would grow and inlining the function 1657 won't eliminate the need for offline copy of the function, 1658 don't inline. */ 1659 if (((mode == INLINE_SIZE || mode == INLINE_SIZE_NORECURSIVE) 1660 || (!flag_inline_functions 1661 && !DECL_DECLARED_INLINE_P (e->callee->decl))) 1662 && (cgraph_estimate_size_after_inlining (1, e->caller, e->callee) 1663 > e->caller->global.size + allowed_growth) 1664 && cgraph_estimate_growth (e->callee) > allowed_growth) 1665 { 1666 if (dump_file) 1667 { 1668 indent_to (dump_file, depth); 1669 fprintf (dump_file, 1670 "Not inlining: code size would grow by %i.\n", 1671 cgraph_estimate_size_after_inlining (1, e->caller, 1672 e->callee) 1673 - e->caller->global.size); 1674 } 1675 continue; 1676 } 1677 if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed, 1678 false) 1679 || e->call_stmt_cannot_inline_p) 1680 { 1681 if (dump_file) 1682 { 1683 indent_to (dump_file, depth); 1684 fprintf (dump_file, "Not inlining: %s.\n", 1685 cgraph_inline_failed_string (e->inline_failed)); 1686 } 1687 continue; 1688 } 1689 if (!e->callee->analyzed) 1690 { 1691 if (dump_file) 1692 { 1693 indent_to (dump_file, depth); 1694 fprintf (dump_file, 1695 "Not inlining: Function body no longer available.\n"); 1696 } 1697 continue; 1698 } 1699 if (!tree_can_inline_p (e)) 1700 { 1701 if (dump_file) 1702 { 1703 indent_to (dump_file, depth); 1704 fprintf (dump_file, 1705 "Not inlining: %s.", 1706 cgraph_inline_failed_string (e->inline_failed)); 1707 } 1708 continue; 1709 } 1710 if (cgraph_default_inline_p (e->callee, &failed_reason)) 1711 inlined |= try_inline (e, mode, depth); 1712 } 1713 BITMAP_FREE (visited); 1714 } 1715 node->aux = (void *)(size_t) old_mode; 1716 return inlined; 1717} 1718 1719/* Because inlining might remove no-longer reachable nodes, we need to 1720 keep the array visible to garbage collector to avoid reading collected 1721 out nodes. */ 1722static int nnodes; 1723static GTY ((length ("nnodes"))) struct cgraph_node **order; 1724 1725/* Do inlining of small functions. Doing so early helps profiling and other 1726 passes to be somewhat more effective and avoids some code duplication in 1727 later real inlining pass for testcases with very many function calls. */ 1728static unsigned int 1729cgraph_early_inlining (void) 1730{ 1731 struct cgraph_node *node = cgraph_node (current_function_decl); 1732 unsigned int todo = 0; 1733 int iterations = 0; 1734 1735 if (sorrycount || errorcount) 1736 return 0; 1737 while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS) 1738 && cgraph_decide_inlining_incrementally (node, 1739 iterations 1740 ? INLINE_SIZE_NORECURSIVE : INLINE_SIZE, 0)) 1741 { 1742 timevar_push (TV_INTEGRATION); 1743 todo |= optimize_inline_calls (current_function_decl); 1744 iterations++; 1745 timevar_pop (TV_INTEGRATION); 1746 } 1747 if (dump_file) 1748 fprintf (dump_file, "Iterations: %i\n", iterations); 1749 cfun->always_inline_functions_inlined = true; 1750 return todo; 1751} 1752 1753/* When inlining shall be performed. */ 1754static bool 1755cgraph_gate_early_inlining (void) 1756{ 1757 return flag_early_inlining; 1758} 1759 1760struct gimple_opt_pass pass_early_inline = 1761{ 1762 { 1763 GIMPLE_PASS, 1764 "einline", /* name */ 1765 cgraph_gate_early_inlining, /* gate */ 1766 cgraph_early_inlining, /* execute */ 1767 NULL, /* sub */ 1768 NULL, /* next */ 1769 0, /* static_pass_number */ 1770 TV_INLINE_HEURISTICS, /* tv_id */ 1771 0, /* properties_required */ 1772 0, /* properties_provided */ 1773 0, /* properties_destroyed */ 1774 0, /* todo_flags_start */ 1775 TODO_dump_func /* todo_flags_finish */ 1776 } 1777}; 1778 1779/* When inlining shall be performed. */ 1780static bool 1781cgraph_gate_ipa_early_inlining (void) 1782{ 1783 return (flag_early_inlining 1784 && !in_lto_p 1785 && (flag_branch_probabilities || flag_test_coverage 1786 || profile_arc_flag)); 1787} 1788 1789/* IPA pass wrapper for early inlining pass. We need to run early inlining 1790 before tree profiling so we have stand alone IPA pass for doing so. */ 1791struct simple_ipa_opt_pass pass_ipa_early_inline = 1792{ 1793 { 1794 SIMPLE_IPA_PASS, 1795 "einline_ipa", /* name */ 1796 cgraph_gate_ipa_early_inlining, /* gate */ 1797 NULL, /* execute */ 1798 NULL, /* sub */ 1799 NULL, /* next */ 1800 0, /* static_pass_number */ 1801 TV_INLINE_HEURISTICS, /* tv_id */ 1802 0, /* properties_required */ 1803 0, /* properties_provided */ 1804 0, /* properties_destroyed */ 1805 0, /* todo_flags_start */ 1806 TODO_dump_cgraph /* todo_flags_finish */ 1807 } 1808}; 1809 1810/* See if statement might disappear after inlining. We are not terribly 1811 sophisficated, basically looking for simple abstraction penalty wrappers. */ 1812 1813static bool 1814likely_eliminated_by_inlining_p (gimple stmt) 1815{ 1816 enum gimple_code code = gimple_code (stmt); 1817 switch (code) 1818 { 1819 case GIMPLE_RETURN: 1820 return true; 1821 case GIMPLE_ASSIGN: 1822 if (gimple_num_ops (stmt) != 2) 1823 return false; 1824 1825 /* Casts of parameters, loads from parameters passed by reference 1826 and stores to return value or parameters are probably free after 1827 inlining. */ 1828 if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR 1829 || gimple_assign_rhs_code (stmt) == NOP_EXPR 1830 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR 1831 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS) 1832 { 1833 tree rhs = gimple_assign_rhs1 (stmt); 1834 tree lhs = gimple_assign_lhs (stmt); 1835 tree inner_rhs = rhs; 1836 tree inner_lhs = lhs; 1837 bool rhs_free = false; 1838 bool lhs_free = false; 1839 1840 while (handled_component_p (inner_lhs) || TREE_CODE (inner_lhs) == INDIRECT_REF) 1841 inner_lhs = TREE_OPERAND (inner_lhs, 0); 1842 while (handled_component_p (inner_rhs) 1843 || TREE_CODE (inner_rhs) == ADDR_EXPR || TREE_CODE (inner_rhs) == INDIRECT_REF) 1844 inner_rhs = TREE_OPERAND (inner_rhs, 0); 1845 1846 1847 if (TREE_CODE (inner_rhs) == PARM_DECL 1848 || (TREE_CODE (inner_rhs) == SSA_NAME 1849 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs) 1850 && TREE_CODE (SSA_NAME_VAR (inner_rhs)) == PARM_DECL)) 1851 rhs_free = true; 1852 if (rhs_free && is_gimple_reg (lhs)) 1853 lhs_free = true; 1854 if (((TREE_CODE (inner_lhs) == PARM_DECL 1855 || (TREE_CODE (inner_lhs) == SSA_NAME 1856 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs) 1857 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == PARM_DECL)) 1858 && inner_lhs != lhs) 1859 || TREE_CODE (inner_lhs) == RESULT_DECL 1860 || (TREE_CODE (inner_lhs) == SSA_NAME 1861 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == RESULT_DECL)) 1862 lhs_free = true; 1863 if (lhs_free && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs))) 1864 rhs_free = true; 1865 if (lhs_free && rhs_free) 1866 return true; 1867 } 1868 return false; 1869 default: 1870 return false; 1871 } 1872} 1873 1874/* Compute function body size parameters for NODE. */ 1875 1876static void 1877estimate_function_body_sizes (struct cgraph_node *node) 1878{ 1879 gcov_type time = 0; 1880 gcov_type time_inlining_benefit = 0; 1881 int size = 0; 1882 int size_inlining_benefit = 0; 1883 basic_block bb; 1884 gimple_stmt_iterator bsi; 1885 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl); 1886 tree arg; 1887 int freq; 1888 tree funtype = TREE_TYPE (node->decl); 1889 1890 if (dump_file) 1891 fprintf (dump_file, "Analyzing function body size: %s\n", 1892 cgraph_node_name (node)); 1893 1894 gcc_assert (my_function && my_function->cfg); 1895 FOR_EACH_BB_FN (bb, my_function) 1896 { 1897 freq = compute_call_stmt_bb_frequency (node->decl, bb); 1898 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 1899 { 1900 gimple stmt = gsi_stmt (bsi); 1901 int this_size = estimate_num_insns (stmt, &eni_size_weights); 1902 int this_time = estimate_num_insns (stmt, &eni_time_weights); 1903 1904 if (dump_file && (dump_flags & TDF_DETAILS)) 1905 { 1906 fprintf (dump_file, " freq:%6i size:%3i time:%3i ", 1907 freq, this_size, this_time); 1908 print_gimple_stmt (dump_file, stmt, 0, 0); 1909 } 1910 this_time *= freq; 1911 time += this_time; 1912 size += this_size; 1913 if (likely_eliminated_by_inlining_p (stmt)) 1914 { 1915 size_inlining_benefit += this_size; 1916 time_inlining_benefit += this_time; 1917 if (dump_file && (dump_flags & TDF_DETAILS)) 1918 fprintf (dump_file, " Likely eliminated\n"); 1919 } 1920 gcc_assert (time >= 0); 1921 gcc_assert (size >= 0); 1922 } 1923 } 1924 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE; 1925 time_inlining_benefit = ((time_inlining_benefit + CGRAPH_FREQ_BASE / 2) 1926 / CGRAPH_FREQ_BASE); 1927 if (dump_file) 1928 fprintf (dump_file, "Overall function body time: %i-%i size: %i-%i\n", 1929 (int)time, (int)time_inlining_benefit, 1930 size, size_inlining_benefit); 1931 time_inlining_benefit += eni_time_weights.call_cost; 1932 size_inlining_benefit += eni_size_weights.call_cost; 1933 if (!VOID_TYPE_P (TREE_TYPE (funtype))) 1934 { 1935 int cost = estimate_move_cost (TREE_TYPE (funtype)); 1936 time_inlining_benefit += cost; 1937 size_inlining_benefit += cost; 1938 } 1939 for (arg = DECL_ARGUMENTS (node->decl); arg; arg = TREE_CHAIN (arg)) 1940 if (!VOID_TYPE_P (TREE_TYPE (arg))) 1941 { 1942 int cost = estimate_move_cost (TREE_TYPE (arg)); 1943 time_inlining_benefit += cost; 1944 size_inlining_benefit += cost; 1945 } 1946 if (time_inlining_benefit > MAX_TIME) 1947 time_inlining_benefit = MAX_TIME; 1948 if (time > MAX_TIME) 1949 time = MAX_TIME; 1950 inline_summary (node)->self_time = time; 1951 inline_summary (node)->self_size = size; 1952 if (dump_file) 1953 fprintf (dump_file, "With function call overhead time: %i-%i size: %i-%i\n", 1954 (int)time, (int)time_inlining_benefit, 1955 size, size_inlining_benefit); 1956 inline_summary (node)->time_inlining_benefit = time_inlining_benefit; 1957 inline_summary (node)->size_inlining_benefit = size_inlining_benefit; 1958} 1959 1960/* Compute parameters of functions used by inliner. */ 1961unsigned int 1962compute_inline_parameters (struct cgraph_node *node) 1963{ 1964 HOST_WIDE_INT self_stack_size; 1965 1966 gcc_assert (!node->global.inlined_to); 1967 1968 /* Estimate the stack size for the function. But not at -O0 1969 because estimated_stack_frame_size is a quadratic problem. */ 1970 self_stack_size = optimize ? estimated_stack_frame_size () : 0; 1971 inline_summary (node)->estimated_self_stack_size = self_stack_size; 1972 node->global.estimated_stack_size = self_stack_size; 1973 node->global.stack_frame_offset = 0; 1974 1975 /* Can this function be inlined at all? */ 1976 node->local.inlinable = tree_inlinable_function_p (node->decl); 1977 if (node->local.inlinable && !node->local.disregard_inline_limits) 1978 node->local.disregard_inline_limits 1979 = DECL_DISREGARD_INLINE_LIMITS (node->decl); 1980 estimate_function_body_sizes (node); 1981 /* Inlining characteristics are maintained by the cgraph_mark_inline. */ 1982 node->global.time = inline_summary (node)->self_time; 1983 node->global.size = inline_summary (node)->self_size; 1984 return 0; 1985} 1986 1987 1988/* Compute parameters of functions used by inliner using 1989 current_function_decl. */ 1990static unsigned int 1991compute_inline_parameters_for_current (void) 1992{ 1993 compute_inline_parameters (cgraph_node (current_function_decl)); 1994 return 0; 1995} 1996 1997struct gimple_opt_pass pass_inline_parameters = 1998{ 1999 { 2000 GIMPLE_PASS, 2001 "inline_param", /* name */ 2002 NULL, /* gate */ 2003 compute_inline_parameters_for_current,/* execute */ 2004 NULL, /* sub */ 2005 NULL, /* next */ 2006 0, /* static_pass_number */ 2007 TV_INLINE_HEURISTICS, /* tv_id */ 2008 0, /* properties_required */ 2009 0, /* properties_provided */ 2010 0, /* properties_destroyed */ 2011 0, /* todo_flags_start */ 2012 0 /* todo_flags_finish */ 2013 } 2014}; 2015 2016/* This function performs intraprocedural analyzis in NODE that is required to 2017 inline indirect calls. */ 2018static void 2019inline_indirect_intraprocedural_analysis (struct cgraph_node *node) 2020{ 2021 struct cgraph_edge *cs; 2022 2023 if (!flag_ipa_cp) 2024 { 2025 ipa_initialize_node_params (node); 2026 ipa_detect_param_modifications (node); 2027 } 2028 ipa_analyze_params_uses (node); 2029 2030 if (!flag_ipa_cp) 2031 for (cs = node->callees; cs; cs = cs->next_callee) 2032 { 2033 ipa_count_arguments (cs); 2034 ipa_compute_jump_functions (cs); 2035 } 2036 2037 if (dump_file) 2038 { 2039 ipa_print_node_params (dump_file, node); 2040 ipa_print_node_jump_functions (dump_file, node); 2041 } 2042} 2043 2044/* Note function body size. */ 2045static void 2046analyze_function (struct cgraph_node *node) 2047{ 2048 push_cfun (DECL_STRUCT_FUNCTION (node->decl)); 2049 current_function_decl = node->decl; 2050 2051 compute_inline_parameters (node); 2052 if (flag_indirect_inlining) 2053 inline_indirect_intraprocedural_analysis (node); 2054 2055 current_function_decl = NULL; 2056 pop_cfun (); 2057} 2058 2059/* Called when new function is inserted to callgraph late. */ 2060static void 2061add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED) 2062{ 2063 analyze_function (node); 2064} 2065 2066/* Note function body size. */ 2067static void 2068inline_generate_summary (void) 2069{ 2070 struct cgraph_node *node; 2071 2072 function_insertion_hook_holder = 2073 cgraph_add_function_insertion_hook (&add_new_function, NULL); 2074 2075 if (flag_indirect_inlining) 2076 { 2077 ipa_register_cgraph_hooks (); 2078 ipa_check_create_node_params (); 2079 ipa_check_create_edge_args (); 2080 } 2081 2082 for (node = cgraph_nodes; node; node = node->next) 2083 if (node->analyzed) 2084 analyze_function (node); 2085 2086 return; 2087} 2088 2089/* Apply inline plan to function. */ 2090static unsigned int 2091inline_transform (struct cgraph_node *node) 2092{ 2093 unsigned int todo = 0; 2094 struct cgraph_edge *e; 2095 bool inline_p = false; 2096 2097 /* FIXME: Currently the passmanager is adding inline transform more than once to some 2098 clones. This needs revisiting after WPA cleanups. */ 2099 if (cfun->after_inlining) 2100 return 0; 2101 2102 /* We might need the body of this function so that we can expand 2103 it inline somewhere else. */ 2104 if (cgraph_preserve_function_body_p (node->decl)) 2105 save_inline_function_body (node); 2106 2107 for (e = node->callees; e; e = e->next_callee) 2108 { 2109 cgraph_redirect_edge_call_stmt_to_callee (e); 2110 if (!e->inline_failed || warn_inline) 2111 inline_p = true; 2112 } 2113 2114 if (inline_p) 2115 { 2116 timevar_push (TV_INTEGRATION); 2117 todo = optimize_inline_calls (current_function_decl); 2118 timevar_pop (TV_INTEGRATION); 2119 } 2120 cfun->always_inline_functions_inlined = true; 2121 cfun->after_inlining = true; 2122 return todo | execute_fixup_cfg (); 2123} 2124 2125/* Read inline summary. Jump functions are shared among ipa-cp 2126 and inliner, so when ipa-cp is active, we don't need to write them 2127 twice. */ 2128 2129static void 2130inline_read_summary (void) 2131{ 2132 if (flag_indirect_inlining) 2133 { 2134 ipa_register_cgraph_hooks (); 2135 if (!flag_ipa_cp) 2136 ipa_prop_read_jump_functions (); 2137 } 2138 function_insertion_hook_holder = 2139 cgraph_add_function_insertion_hook (&add_new_function, NULL); 2140} 2141 2142/* Write inline summary for node in SET. 2143 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is 2144 active, we don't need to write them twice. */ 2145 2146static void 2147inline_write_summary (cgraph_node_set set) 2148{ 2149 if (flag_indirect_inlining && !flag_ipa_cp) 2150 ipa_prop_write_jump_functions (set); 2151} 2152 2153struct ipa_opt_pass_d pass_ipa_inline = 2154{ 2155 { 2156 IPA_PASS, 2157 "inline", /* name */ 2158 NULL, /* gate */ 2159 cgraph_decide_inlining, /* execute */ 2160 NULL, /* sub */ 2161 NULL, /* next */ 2162 0, /* static_pass_number */ 2163 TV_INLINE_HEURISTICS, /* tv_id */ 2164 0, /* properties_required */ 2165 0, /* properties_provided */ 2166 0, /* properties_destroyed */ 2167 TODO_remove_functions, /* todo_flags_finish */ 2168 TODO_dump_cgraph | TODO_dump_func 2169 | TODO_remove_functions /* todo_flags_finish */ 2170 }, 2171 inline_generate_summary, /* generate_summary */ 2172 inline_write_summary, /* write_summary */ 2173 inline_read_summary, /* read_summary */ 2174 NULL, /* function_read_summary */ 2175 lto_ipa_fixup_call_notes, /* stmt_fixup */ 2176 0, /* TODOs */ 2177 inline_transform, /* function_transform */ 2178 NULL, /* variable_transform */ 2179}; 2180 2181 2182#include "gt-ipa-inline.h" 2183