1169689Skan/* Inlining decision heuristics. 2169689Skan Copyright (C) 2003, 2004 Free Software Foundation, Inc. 3169689Skan Contributed by Jan Hubicka 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify it under 8169689Skanthe terms of the GNU General Public License as published by the Free 9169689SkanSoftware Foundation; either version 2, or (at your option) any later 10169689Skanversion. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skanfor more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21169689Skan 22169689Skan/* Inlining decision heuristics 23169689Skan 24169689Skan We separate inlining decisions from the inliner itself and store it 25169689Skan inside callgraph as so called inline plan. Refer to cgraph.c 26169689Skan documentation about particular representation of inline plans in the 27169689Skan callgraph. 28169689Skan 29169689Skan There are three major parts of this file: 30169689Skan 31169689Skan cgraph_mark_inline implementation 32169689Skan 33169689Skan This function allows to mark given call inline and performs necessary 34169689Skan modifications of cgraph (production of the clones and updating overall 35169689Skan statistics) 36169689Skan 37169689Skan inlining heuristics limits 38169689Skan 39169689Skan These functions allow to check that particular inlining is allowed 40169689Skan by the limits specified by user (allowed function growth, overall unit 41169689Skan growth and so on). 42169689Skan 43169689Skan inlining heuristics 44169689Skan 45169689Skan This is implementation of IPA pass aiming to get as much of benefit 46169689Skan from inlining obeying the limits checked above. 47169689Skan 48169689Skan The implementation of particular heuristics is separated from 49169689Skan the rest of code to make it easier to replace it with more complicated 50169689Skan implementation in the future. The rest of inlining code acts as a 51169689Skan library aimed to modify the callgraph and verify that the parameters 52169689Skan on code size growth fits. 53169689Skan 54169689Skan To mark given call inline, use cgraph_mark_inline function, the 55169689Skan verification is performed by cgraph_default_inline_p and 56169689Skan cgraph_check_inline_limits. 57169689Skan 58169689Skan The heuristics implements simple knapsack style algorithm ordering 59169689Skan all functions by their "profitability" (estimated by code size growth) 60169689Skan and inlining them in priority order. 61169689Skan 62169689Skan cgraph_decide_inlining implements heuristics taking whole callgraph 63169689Skan into account, while cgraph_decide_inlining_incrementally considers 64169689Skan only one function at a time and is used in non-unit-at-a-time mode. */ 65169689Skan 66169689Skan#include "config.h" 67169689Skan#include "system.h" 68169689Skan#include "coretypes.h" 69169689Skan#include "tm.h" 70169689Skan#include "tree.h" 71169689Skan#include "tree-inline.h" 72169689Skan#include "langhooks.h" 73169689Skan#include "flags.h" 74169689Skan#include "cgraph.h" 75169689Skan#include "diagnostic.h" 76169689Skan#include "timevar.h" 77169689Skan#include "params.h" 78169689Skan#include "fibheap.h" 79169689Skan#include "intl.h" 80169689Skan#include "tree-pass.h" 81169689Skan#include "hashtab.h" 82169689Skan#include "coverage.h" 83169689Skan#include "ggc.h" 84169689Skan 85169689Skan/* Statistics we collect about inlining algorithm. */ 86169689Skanstatic int ncalls_inlined; 87169689Skanstatic int nfunctions_inlined; 88169689Skanstatic int initial_insns; 89169689Skanstatic int overall_insns; 90169689Skanstatic int max_insns; 91169689Skanstatic gcov_type max_count; 92169689Skan 93169689Skan/* Estimate size of the function after inlining WHAT into TO. */ 94169689Skan 95169689Skanstatic int 96169689Skancgraph_estimate_size_after_inlining (int times, struct cgraph_node *to, 97169689Skan struct cgraph_node *what) 98169689Skan{ 99169689Skan int size; 100169689Skan tree fndecl = what->decl, arg; 101169689Skan int call_insns = PARAM_VALUE (PARAM_INLINE_CALL_COST); 102169689Skan 103169689Skan for (arg = DECL_ARGUMENTS (fndecl); arg; arg = TREE_CHAIN (arg)) 104169689Skan call_insns += estimate_move_cost (TREE_TYPE (arg)); 105169689Skan size = (what->global.insns - call_insns) * times + to->global.insns; 106169689Skan gcc_assert (size >= 0); 107169689Skan return size; 108169689Skan} 109169689Skan 110169689Skan/* E is expected to be an edge being inlined. Clone destination node of 111169689Skan the edge and redirect it to the new clone. 112169689Skan DUPLICATE is used for bookkeeping on whether we are actually creating new 113169689Skan clones or re-using node originally representing out-of-line function call. 114169689Skan */ 115169689Skanvoid 116169689Skancgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate, bool update_original) 117169689Skan{ 118169689Skan if (duplicate) 119169689Skan { 120169689Skan /* We may eliminate the need for out-of-line copy to be output. 121169689Skan In that case just go ahead and re-use it. */ 122169689Skan if (!e->callee->callers->next_caller 123169689Skan && !e->callee->needed 124169689Skan && flag_unit_at_a_time) 125169689Skan { 126169689Skan gcc_assert (!e->callee->global.inlined_to); 127169689Skan if (DECL_SAVED_TREE (e->callee->decl)) 128169689Skan overall_insns -= e->callee->global.insns, nfunctions_inlined++; 129169689Skan duplicate = false; 130169689Skan } 131169689Skan else 132169689Skan { 133169689Skan struct cgraph_node *n; 134169689Skan n = cgraph_clone_node (e->callee, e->count, e->loop_nest, 135169689Skan update_original); 136169689Skan cgraph_redirect_edge_callee (e, n); 137169689Skan } 138169689Skan } 139169689Skan 140169689Skan if (e->caller->global.inlined_to) 141169689Skan e->callee->global.inlined_to = e->caller->global.inlined_to; 142169689Skan else 143169689Skan e->callee->global.inlined_to = e->caller; 144169689Skan 145169689Skan /* Recursively clone all bodies. */ 146169689Skan for (e = e->callee->callees; e; e = e->next_callee) 147169689Skan if (!e->inline_failed) 148169689Skan cgraph_clone_inlined_nodes (e, duplicate, update_original); 149169689Skan} 150169689Skan 151169689Skan/* Mark edge E as inlined and update callgraph accordingly. 152169689Skan UPDATE_ORIGINAL specify whether profile of original function should be 153169689Skan updated. */ 154169689Skan 155169689Skanvoid 156169689Skancgraph_mark_inline_edge (struct cgraph_edge *e, bool update_original) 157169689Skan{ 158169689Skan int old_insns = 0, new_insns = 0; 159169689Skan struct cgraph_node *to = NULL, *what; 160169689Skan 161169689Skan if (e->callee->inline_decl) 162169689Skan cgraph_redirect_edge_callee (e, cgraph_node (e->callee->inline_decl)); 163169689Skan 164169689Skan gcc_assert (e->inline_failed); 165169689Skan e->inline_failed = NULL; 166169689Skan 167169689Skan if (!e->callee->global.inlined && flag_unit_at_a_time) 168169689Skan DECL_POSSIBLY_INLINED (e->callee->decl) = true; 169169689Skan e->callee->global.inlined = true; 170169689Skan 171169689Skan cgraph_clone_inlined_nodes (e, true, update_original); 172169689Skan 173169689Skan what = e->callee; 174169689Skan 175169689Skan /* Now update size of caller and all functions caller is inlined into. */ 176169689Skan for (;e && !e->inline_failed; e = e->caller->callers) 177169689Skan { 178169689Skan old_insns = e->caller->global.insns; 179169689Skan new_insns = cgraph_estimate_size_after_inlining (1, e->caller, 180169689Skan what); 181169689Skan gcc_assert (new_insns >= 0); 182169689Skan to = e->caller; 183169689Skan to->global.insns = new_insns; 184169689Skan } 185169689Skan gcc_assert (what->global.inlined_to == to); 186169689Skan if (new_insns > old_insns) 187169689Skan overall_insns += new_insns - old_insns; 188169689Skan ncalls_inlined++; 189169689Skan} 190169689Skan 191169689Skan/* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER. 192169689Skan Return following unredirected edge in the list of callers 193169689Skan of EDGE->CALLEE */ 194169689Skan 195169689Skanstatic struct cgraph_edge * 196169689Skancgraph_mark_inline (struct cgraph_edge *edge) 197169689Skan{ 198169689Skan struct cgraph_node *to = edge->caller; 199169689Skan struct cgraph_node *what = edge->callee; 200169689Skan struct cgraph_edge *e, *next; 201169689Skan int times = 0; 202169689Skan 203169689Skan /* Look for all calls, mark them inline and clone recursively 204169689Skan all inlined functions. */ 205169689Skan for (e = what->callers; e; e = next) 206169689Skan { 207169689Skan next = e->next_caller; 208169689Skan if (e->caller == to && e->inline_failed) 209169689Skan { 210169689Skan cgraph_mark_inline_edge (e, true); 211169689Skan if (e == edge) 212169689Skan edge = next; 213169689Skan times++; 214169689Skan } 215169689Skan } 216169689Skan gcc_assert (times); 217169689Skan return edge; 218169689Skan} 219169689Skan 220169689Skan/* Estimate the growth caused by inlining NODE into all callees. */ 221169689Skan 222169689Skanstatic int 223169689Skancgraph_estimate_growth (struct cgraph_node *node) 224169689Skan{ 225169689Skan int growth = 0; 226169689Skan struct cgraph_edge *e; 227169689Skan if (node->global.estimated_growth != INT_MIN) 228169689Skan return node->global.estimated_growth; 229169689Skan 230169689Skan for (e = node->callers; e; e = e->next_caller) 231169689Skan if (e->inline_failed) 232169689Skan growth += (cgraph_estimate_size_after_inlining (1, e->caller, node) 233169689Skan - e->caller->global.insns); 234169689Skan 235169689Skan /* ??? Wrong for self recursive functions or cases where we decide to not 236169689Skan inline for different reasons, but it is not big deal as in that case 237169689Skan we will keep the body around, but we will also avoid some inlining. */ 238169689Skan if (!node->needed && !DECL_EXTERNAL (node->decl)) 239169689Skan growth -= node->global.insns; 240169689Skan 241169689Skan node->global.estimated_growth = growth; 242169689Skan return growth; 243169689Skan} 244169689Skan 245169689Skan/* Return false when inlining WHAT into TO is not good idea 246169689Skan as it would cause too large growth of function bodies. 247169689Skan When ONE_ONLY is true, assume that only one call site is going 248169689Skan to be inlined, otherwise figure out how many call sites in 249169689Skan TO calls WHAT and verify that all can be inlined. 250169689Skan */ 251169689Skan 252169689Skanstatic bool 253169689Skancgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what, 254169689Skan const char **reason, bool one_only) 255169689Skan{ 256169689Skan int times = 0; 257169689Skan struct cgraph_edge *e; 258169689Skan int newsize; 259169689Skan int limit; 260169689Skan 261169689Skan if (one_only) 262169689Skan times = 1; 263169689Skan else 264169689Skan for (e = to->callees; e; e = e->next_callee) 265169689Skan if (e->callee == what) 266169689Skan times++; 267169689Skan 268169689Skan if (to->global.inlined_to) 269169689Skan to = to->global.inlined_to; 270169689Skan 271169689Skan /* When inlining large function body called once into small function, 272169689Skan take the inlined function as base for limiting the growth. */ 273169689Skan if (to->local.self_insns > what->local.self_insns) 274169689Skan limit = to->local.self_insns; 275169689Skan else 276169689Skan limit = what->local.self_insns; 277169689Skan 278169689Skan limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100; 279169689Skan 280169689Skan /* Check the size after inlining against the function limits. But allow 281169689Skan the function to shrink if it went over the limits by forced inlining. */ 282169689Skan newsize = cgraph_estimate_size_after_inlining (times, to, what); 283169689Skan if (newsize >= to->global.insns 284169689Skan && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS) 285169689Skan && newsize > limit) 286169689Skan { 287169689Skan if (reason) 288169689Skan *reason = N_("--param large-function-growth limit reached"); 289169689Skan return false; 290169689Skan } 291169689Skan return true; 292169689Skan} 293169689Skan 294169689Skan/* Return true when function N is small enough to be inlined. */ 295169689Skan 296169689Skanbool 297169689Skancgraph_default_inline_p (struct cgraph_node *n, const char **reason) 298169689Skan{ 299169689Skan tree decl = n->decl; 300169689Skan 301169689Skan if (n->inline_decl) 302169689Skan decl = n->inline_decl; 303169689Skan if (!DECL_INLINE (decl)) 304169689Skan { 305169689Skan if (reason) 306169689Skan *reason = N_("function not inlinable"); 307169689Skan return false; 308169689Skan } 309169689Skan 310169689Skan if (!DECL_STRUCT_FUNCTION (decl)->cfg) 311169689Skan { 312169689Skan if (reason) 313169689Skan *reason = N_("function body not available"); 314169689Skan return false; 315169689Skan } 316169689Skan 317169689Skan if (DECL_DECLARED_INLINE_P (decl)) 318169689Skan { 319169689Skan if (n->global.insns >= MAX_INLINE_INSNS_SINGLE) 320169689Skan { 321169689Skan if (reason) 322169689Skan *reason = N_("--param max-inline-insns-single limit reached"); 323169689Skan return false; 324169689Skan } 325169689Skan } 326169689Skan else 327169689Skan { 328169689Skan if (n->global.insns >= MAX_INLINE_INSNS_AUTO) 329169689Skan { 330169689Skan if (reason) 331169689Skan *reason = N_("--param max-inline-insns-auto limit reached"); 332169689Skan return false; 333169689Skan } 334169689Skan } 335169689Skan 336169689Skan return true; 337169689Skan} 338169689Skan 339169689Skan/* Return true when inlining WHAT would create recursive inlining. 340169689Skan We call recursive inlining all cases where same function appears more than 341169689Skan once in the single recursion nest path in the inline graph. */ 342169689Skan 343169689Skanstatic bool 344169689Skancgraph_recursive_inlining_p (struct cgraph_node *to, 345169689Skan struct cgraph_node *what, 346169689Skan const char **reason) 347169689Skan{ 348169689Skan bool recursive; 349169689Skan if (to->global.inlined_to) 350169689Skan recursive = what->decl == to->global.inlined_to->decl; 351169689Skan else 352169689Skan recursive = what->decl == to->decl; 353169689Skan /* Marking recursive function inline has sane semantic and thus we should 354169689Skan not warn on it. */ 355169689Skan if (recursive && reason) 356169689Skan *reason = (what->local.disregard_inline_limits 357169689Skan ? N_("recursive inlining") : ""); 358169689Skan return recursive; 359169689Skan} 360169689Skan 361169689Skan/* Return true if the call can be hot. */ 362169689Skanstatic bool 363169689Skancgraph_maybe_hot_edge_p (struct cgraph_edge *edge) 364169689Skan{ 365169689Skan if (profile_info && flag_branch_probabilities 366169689Skan && (edge->count 367169689Skan <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION))) 368169689Skan return false; 369169689Skan return true; 370169689Skan} 371169689Skan 372169689Skan/* A cost model driving the inlining heuristics in a way so the edges with 373169689Skan smallest badness are inlined first. After each inlining is performed 374169689Skan the costs of all caller edges of nodes affected are recomputed so the 375169689Skan metrics may accurately depend on values such as number of inlinable callers 376169689Skan of the function or function body size. 377169689Skan 378169689Skan With profiling we use number of executions of each edge to drive the cost. 379169689Skan We also should distinguish hot and cold calls where the cold calls are 380169689Skan inlined into only when code size is overall improved. 381169689Skan */ 382169689Skan 383169689Skanstatic int 384169689Skancgraph_edge_badness (struct cgraph_edge *edge) 385169689Skan{ 386169689Skan if (max_count) 387169689Skan { 388169689Skan int growth = 389169689Skan cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee); 390169689Skan growth -= edge->caller->global.insns; 391169689Skan 392169689Skan /* Always prefer inlining saving code size. */ 393169689Skan if (growth <= 0) 394169689Skan return INT_MIN - growth; 395169689Skan return ((int)((double)edge->count * INT_MIN / max_count)) / growth; 396169689Skan } 397169689Skan else 398169689Skan { 399169689Skan int nest = MIN (edge->loop_nest, 8); 400169689Skan int badness = cgraph_estimate_growth (edge->callee) * 256; 401169689Skan 402169689Skan /* Decrease badness if call is nested. */ 403169689Skan if (badness > 0) 404169689Skan badness >>= nest; 405169689Skan else 406169689Skan badness <<= nest; 407169689Skan 408169689Skan /* Make recursive inlining happen always after other inlining is done. */ 409169689Skan if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL)) 410169689Skan return badness + 1; 411169689Skan else 412169689Skan return badness; 413169689Skan } 414169689Skan} 415169689Skan 416169689Skan/* Recompute heap nodes for each of caller edge. */ 417169689Skan 418169689Skanstatic void 419169689Skanupdate_caller_keys (fibheap_t heap, struct cgraph_node *node, 420169689Skan bitmap updated_nodes) 421169689Skan{ 422169689Skan struct cgraph_edge *edge; 423169689Skan const char *failed_reason; 424169689Skan 425169689Skan if (!node->local.inlinable || node->local.disregard_inline_limits 426169689Skan || node->global.inlined_to) 427169689Skan return; 428169689Skan if (bitmap_bit_p (updated_nodes, node->uid)) 429169689Skan return; 430169689Skan bitmap_set_bit (updated_nodes, node->uid); 431169689Skan node->global.estimated_growth = INT_MIN; 432169689Skan 433169689Skan if (!node->local.inlinable) 434169689Skan return; 435169689Skan /* Prune out edges we won't inline into anymore. */ 436169689Skan if (!cgraph_default_inline_p (node, &failed_reason)) 437169689Skan { 438169689Skan for (edge = node->callers; edge; edge = edge->next_caller) 439169689Skan if (edge->aux) 440169689Skan { 441169689Skan fibheap_delete_node (heap, edge->aux); 442169689Skan edge->aux = NULL; 443169689Skan if (edge->inline_failed) 444169689Skan edge->inline_failed = failed_reason; 445169689Skan } 446169689Skan return; 447169689Skan } 448169689Skan 449169689Skan for (edge = node->callers; edge; edge = edge->next_caller) 450169689Skan if (edge->inline_failed) 451169689Skan { 452169689Skan int badness = cgraph_edge_badness (edge); 453169689Skan if (edge->aux) 454169689Skan { 455169689Skan fibnode_t n = edge->aux; 456169689Skan gcc_assert (n->data == edge); 457169689Skan if (n->key == badness) 458169689Skan continue; 459169689Skan 460169689Skan /* fibheap_replace_key only increase the keys. */ 461169689Skan if (fibheap_replace_key (heap, n, badness)) 462169689Skan continue; 463169689Skan fibheap_delete_node (heap, edge->aux); 464169689Skan } 465169689Skan edge->aux = fibheap_insert (heap, badness, edge); 466169689Skan } 467169689Skan} 468169689Skan 469169689Skan/* Recompute heap nodes for each of caller edges of each of callees. */ 470169689Skan 471169689Skanstatic void 472169689Skanupdate_callee_keys (fibheap_t heap, struct cgraph_node *node, 473169689Skan bitmap updated_nodes) 474169689Skan{ 475169689Skan struct cgraph_edge *e; 476169689Skan node->global.estimated_growth = INT_MIN; 477169689Skan 478169689Skan for (e = node->callees; e; e = e->next_callee) 479169689Skan if (e->inline_failed) 480169689Skan update_caller_keys (heap, e->callee, updated_nodes); 481169689Skan else if (!e->inline_failed) 482169689Skan update_callee_keys (heap, e->callee, updated_nodes); 483169689Skan} 484169689Skan 485169689Skan/* Enqueue all recursive calls from NODE into priority queue depending on 486169689Skan how likely we want to recursively inline the call. */ 487169689Skan 488169689Skanstatic void 489169689Skanlookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where, 490169689Skan fibheap_t heap) 491169689Skan{ 492169689Skan static int priority; 493169689Skan struct cgraph_edge *e; 494169689Skan for (e = where->callees; e; e = e->next_callee) 495169689Skan if (e->callee == node) 496169689Skan { 497169689Skan /* When profile feedback is available, prioritize by expected number 498169689Skan of calls. Without profile feedback we maintain simple queue 499169689Skan to order candidates via recursive depths. */ 500169689Skan fibheap_insert (heap, 501169689Skan !max_count ? priority++ 502169689Skan : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))), 503169689Skan e); 504169689Skan } 505169689Skan for (e = where->callees; e; e = e->next_callee) 506169689Skan if (!e->inline_failed) 507169689Skan lookup_recursive_calls (node, e->callee, heap); 508169689Skan} 509169689Skan 510169689Skan/* Find callgraph nodes closing a circle in the graph. The 511169689Skan resulting hashtab can be used to avoid walking the circles. 512169689Skan Uses the cgraph nodes ->aux field which needs to be zero 513169689Skan before and will be zero after operation. */ 514169689Skan 515169689Skanstatic void 516169689Skancgraph_find_cycles (struct cgraph_node *node, htab_t cycles) 517169689Skan{ 518169689Skan struct cgraph_edge *e; 519169689Skan 520169689Skan if (node->aux) 521169689Skan { 522169689Skan void **slot; 523169689Skan slot = htab_find_slot (cycles, node, INSERT); 524169689Skan if (!*slot) 525169689Skan { 526169689Skan if (dump_file) 527169689Skan fprintf (dump_file, "Cycle contains %s\n", cgraph_node_name (node)); 528169689Skan *slot = node; 529169689Skan } 530169689Skan return; 531169689Skan } 532169689Skan 533169689Skan node->aux = node; 534169689Skan for (e = node->callees; e; e = e->next_callee) 535169689Skan cgraph_find_cycles (e->callee, cycles); 536169689Skan node->aux = 0; 537169689Skan} 538169689Skan 539169689Skan/* Flatten the cgraph node. We have to be careful in recursing 540169689Skan as to not run endlessly in circles of the callgraph. 541169689Skan We do so by using a hashtab of cycle entering nodes as generated 542169689Skan by cgraph_find_cycles. */ 543169689Skan 544169689Skanstatic void 545169689Skancgraph_flatten_node (struct cgraph_node *node, htab_t cycles) 546169689Skan{ 547169689Skan struct cgraph_edge *e; 548169689Skan 549169689Skan for (e = node->callees; e; e = e->next_callee) 550169689Skan { 551169689Skan /* Inline call, if possible, and recurse. Be sure we are not 552169689Skan entering callgraph circles here. */ 553169689Skan if (e->inline_failed 554169689Skan && e->callee->local.inlinable 555169689Skan && !cgraph_recursive_inlining_p (node, e->callee, 556169689Skan &e->inline_failed) 557169689Skan && !htab_find (cycles, e->callee)) 558169689Skan { 559169689Skan if (dump_file) 560169689Skan fprintf (dump_file, " inlining %s", cgraph_node_name (e->callee)); 561169689Skan cgraph_mark_inline_edge (e, true); 562169689Skan cgraph_flatten_node (e->callee, cycles); 563169689Skan } 564169689Skan else if (dump_file) 565169689Skan fprintf (dump_file, " !inlining %s", cgraph_node_name (e->callee)); 566169689Skan } 567169689Skan} 568169689Skan 569169689Skan/* Decide on recursive inlining: in the case function has recursive calls, 570169689Skan inline until body size reaches given argument. */ 571169689Skan 572169689Skanstatic bool 573169689Skancgraph_decide_recursive_inlining (struct cgraph_node *node) 574169689Skan{ 575169689Skan int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO); 576169689Skan int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO); 577169689Skan int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY); 578169689Skan fibheap_t heap; 579169689Skan struct cgraph_edge *e; 580169689Skan struct cgraph_node *master_clone, *next; 581169689Skan int depth = 0; 582169689Skan int n = 0; 583169689Skan 584169689Skan if (DECL_DECLARED_INLINE_P (node->decl)) 585169689Skan { 586169689Skan limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE); 587169689Skan max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH); 588169689Skan } 589169689Skan 590169689Skan /* Make sure that function is small enough to be considered for inlining. */ 591169689Skan if (!max_depth 592169689Skan || cgraph_estimate_size_after_inlining (1, node, node) >= limit) 593169689Skan return false; 594169689Skan heap = fibheap_new (); 595169689Skan lookup_recursive_calls (node, node, heap); 596169689Skan if (fibheap_empty (heap)) 597169689Skan { 598169689Skan fibheap_delete (heap); 599169689Skan return false; 600169689Skan } 601169689Skan 602169689Skan if (dump_file) 603169689Skan fprintf (dump_file, 604169689Skan " Performing recursive inlining on %s\n", 605169689Skan cgraph_node_name (node)); 606169689Skan 607169689Skan /* We need original clone to copy around. */ 608169689Skan master_clone = cgraph_clone_node (node, node->count, 1, false); 609169689Skan master_clone->needed = true; 610169689Skan for (e = master_clone->callees; e; e = e->next_callee) 611169689Skan if (!e->inline_failed) 612169689Skan cgraph_clone_inlined_nodes (e, true, false); 613169689Skan 614169689Skan /* Do the inlining and update list of recursive call during process. */ 615169689Skan while (!fibheap_empty (heap) 616169689Skan && (cgraph_estimate_size_after_inlining (1, node, master_clone) 617169689Skan <= limit)) 618169689Skan { 619169689Skan struct cgraph_edge *curr = fibheap_extract_min (heap); 620169689Skan struct cgraph_node *cnode; 621169689Skan 622169689Skan depth = 1; 623169689Skan for (cnode = curr->caller; 624169689Skan cnode->global.inlined_to; cnode = cnode->callers->caller) 625169689Skan if (node->decl == curr->callee->decl) 626169689Skan depth++; 627169689Skan if (depth > max_depth) 628169689Skan { 629169689Skan if (dump_file) 630169689Skan fprintf (dump_file, 631169689Skan " maxmal depth reached\n"); 632169689Skan continue; 633169689Skan } 634169689Skan 635169689Skan if (max_count) 636169689Skan { 637169689Skan if (!cgraph_maybe_hot_edge_p (curr)) 638169689Skan { 639169689Skan if (dump_file) 640169689Skan fprintf (dump_file, " Not inlining cold call\n"); 641169689Skan continue; 642169689Skan } 643169689Skan if (curr->count * 100 / node->count < probability) 644169689Skan { 645169689Skan if (dump_file) 646169689Skan fprintf (dump_file, 647169689Skan " Probability of edge is too small\n"); 648169689Skan continue; 649169689Skan } 650169689Skan } 651169689Skan 652169689Skan if (dump_file) 653169689Skan { 654169689Skan fprintf (dump_file, 655169689Skan " Inlining call of depth %i", depth); 656169689Skan if (node->count) 657169689Skan { 658169689Skan fprintf (dump_file, " called approx. %.2f times per call", 659169689Skan (double)curr->count / node->count); 660169689Skan } 661169689Skan fprintf (dump_file, "\n"); 662169689Skan } 663169689Skan cgraph_redirect_edge_callee (curr, master_clone); 664169689Skan cgraph_mark_inline_edge (curr, false); 665169689Skan lookup_recursive_calls (node, curr->callee, heap); 666169689Skan n++; 667169689Skan } 668169689Skan if (!fibheap_empty (heap) && dump_file) 669169689Skan fprintf (dump_file, " Recursive inlining growth limit met.\n"); 670169689Skan 671169689Skan fibheap_delete (heap); 672169689Skan if (dump_file) 673169689Skan fprintf (dump_file, 674169689Skan "\n Inlined %i times, body grown from %i to %i insns\n", n, 675169689Skan master_clone->global.insns, node->global.insns); 676169689Skan 677169689Skan /* Remove master clone we used for inlining. We rely that clones inlined 678169689Skan into master clone gets queued just before master clone so we don't 679169689Skan need recursion. */ 680169689Skan for (node = cgraph_nodes; node != master_clone; 681169689Skan node = next) 682169689Skan { 683169689Skan next = node->next; 684169689Skan if (node->global.inlined_to == master_clone) 685169689Skan cgraph_remove_node (node); 686169689Skan } 687169689Skan cgraph_remove_node (master_clone); 688169689Skan /* FIXME: Recursive inlining actually reduces number of calls of the 689169689Skan function. At this place we should probably walk the function and 690169689Skan inline clones and compensate the counts accordingly. This probably 691169689Skan doesn't matter much in practice. */ 692169689Skan return n > 0; 693169689Skan} 694169689Skan 695169689Skan/* Set inline_failed for all callers of given function to REASON. */ 696169689Skan 697169689Skanstatic void 698169689Skancgraph_set_inline_failed (struct cgraph_node *node, const char *reason) 699169689Skan{ 700169689Skan struct cgraph_edge *e; 701169689Skan 702169689Skan if (dump_file) 703169689Skan fprintf (dump_file, "Inlining failed: %s\n", reason); 704169689Skan for (e = node->callers; e; e = e->next_caller) 705169689Skan if (e->inline_failed) 706169689Skan e->inline_failed = reason; 707169689Skan} 708169689Skan 709169689Skan/* We use greedy algorithm for inlining of small functions: 710169689Skan All inline candidates are put into prioritized heap based on estimated 711169689Skan growth of the overall number of instructions and then update the estimates. 712169689Skan 713169689Skan INLINED and INLINED_CALEES are just pointers to arrays large enough 714169689Skan to be passed to cgraph_inlined_into and cgraph_inlined_callees. */ 715169689Skan 716169689Skanstatic void 717169689Skancgraph_decide_inlining_of_small_functions (void) 718169689Skan{ 719169689Skan struct cgraph_node *node; 720169689Skan struct cgraph_edge *edge; 721169689Skan const char *failed_reason; 722169689Skan fibheap_t heap = fibheap_new (); 723169689Skan bitmap updated_nodes = BITMAP_ALLOC (NULL); 724169689Skan 725169689Skan if (dump_file) 726169689Skan fprintf (dump_file, "\nDeciding on smaller functions:\n"); 727169689Skan 728169689Skan /* Put all inline candidates into the heap. */ 729169689Skan 730169689Skan for (node = cgraph_nodes; node; node = node->next) 731169689Skan { 732169689Skan if (!node->local.inlinable || !node->callers 733169689Skan || node->local.disregard_inline_limits) 734169689Skan continue; 735169689Skan if (dump_file) 736169689Skan fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node)); 737169689Skan 738169689Skan node->global.estimated_growth = INT_MIN; 739169689Skan if (!cgraph_default_inline_p (node, &failed_reason)) 740169689Skan { 741169689Skan cgraph_set_inline_failed (node, failed_reason); 742169689Skan continue; 743169689Skan } 744169689Skan 745169689Skan for (edge = node->callers; edge; edge = edge->next_caller) 746169689Skan if (edge->inline_failed) 747169689Skan { 748169689Skan gcc_assert (!edge->aux); 749169689Skan edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge); 750169689Skan } 751169689Skan } 752169689Skan while (overall_insns <= max_insns && (edge = fibheap_extract_min (heap))) 753169689Skan { 754169689Skan int old_insns = overall_insns; 755169689Skan struct cgraph_node *where; 756169689Skan int growth = 757169689Skan cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee); 758169689Skan 759169689Skan growth -= edge->caller->global.insns; 760169689Skan 761169689Skan if (dump_file) 762169689Skan { 763169689Skan fprintf (dump_file, 764169689Skan "\nConsidering %s with %i insns\n", 765169689Skan cgraph_node_name (edge->callee), 766169689Skan edge->callee->global.insns); 767169689Skan fprintf (dump_file, 768169689Skan " to be inlined into %s\n" 769169689Skan " Estimated growth after inlined into all callees is %+i insns.\n" 770169689Skan " Estimated badness is %i.\n", 771169689Skan cgraph_node_name (edge->caller), 772169689Skan cgraph_estimate_growth (edge->callee), 773169689Skan cgraph_edge_badness (edge)); 774169689Skan if (edge->count) 775169689Skan fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count); 776169689Skan } 777169689Skan gcc_assert (edge->aux); 778169689Skan edge->aux = NULL; 779169689Skan if (!edge->inline_failed) 780169689Skan continue; 781169689Skan 782169689Skan /* When not having profile info ready we don't weight by any way the 783169689Skan position of call in procedure itself. This means if call of 784169689Skan function A from function B seems profitable to inline, the recursive 785169689Skan call of function A in inline copy of A in B will look profitable too 786169689Skan and we end up inlining until reaching maximal function growth. This 787169689Skan is not good idea so prohibit the recursive inlining. 788169689Skan 789169689Skan ??? When the frequencies are taken into account we might not need this 790169689Skan restriction. */ 791169689Skan if (!max_count) 792169689Skan { 793169689Skan where = edge->caller; 794169689Skan while (where->global.inlined_to) 795169689Skan { 796169689Skan if (where->decl == edge->callee->decl) 797169689Skan break; 798169689Skan where = where->callers->caller; 799169689Skan } 800169689Skan if (where->global.inlined_to) 801169689Skan { 802169689Skan edge->inline_failed 803169689Skan = (edge->callee->local.disregard_inline_limits ? N_("recursive inlining") : ""); 804169689Skan if (dump_file) 805169689Skan fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n"); 806169689Skan continue; 807169689Skan } 808169689Skan } 809169689Skan 810169689Skan if (!cgraph_maybe_hot_edge_p (edge) && growth > 0) 811169689Skan { 812169689Skan if (!cgraph_recursive_inlining_p (edge->caller, edge->callee, 813169689Skan &edge->inline_failed)) 814169689Skan { 815169689Skan edge->inline_failed = 816169689Skan N_("call is unlikely"); 817169689Skan if (dump_file) 818169689Skan fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed); 819169689Skan } 820169689Skan continue; 821169689Skan } 822169689Skan if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed)) 823169689Skan { 824169689Skan if (!cgraph_recursive_inlining_p (edge->caller, edge->callee, 825169689Skan &edge->inline_failed)) 826169689Skan { 827169689Skan if (dump_file) 828169689Skan fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed); 829169689Skan } 830169689Skan continue; 831169689Skan } 832169689Skan if (cgraph_recursive_inlining_p (edge->caller, edge->callee, 833169689Skan &edge->inline_failed)) 834169689Skan { 835169689Skan where = edge->caller; 836169689Skan if (where->global.inlined_to) 837169689Skan where = where->global.inlined_to; 838169689Skan if (!cgraph_decide_recursive_inlining (where)) 839169689Skan continue; 840169689Skan update_callee_keys (heap, where, updated_nodes); 841169689Skan } 842169689Skan else 843169689Skan { 844169689Skan struct cgraph_node *callee; 845169689Skan if (!cgraph_check_inline_limits (edge->caller, edge->callee, 846169689Skan &edge->inline_failed, true)) 847169689Skan { 848169689Skan if (dump_file) 849169689Skan fprintf (dump_file, " Not inlining into %s:%s.\n", 850169689Skan cgraph_node_name (edge->caller), edge->inline_failed); 851169689Skan continue; 852169689Skan } 853169689Skan callee = edge->callee; 854169689Skan cgraph_mark_inline_edge (edge, true); 855169689Skan update_callee_keys (heap, callee, updated_nodes); 856169689Skan } 857169689Skan where = edge->caller; 858169689Skan if (where->global.inlined_to) 859169689Skan where = where->global.inlined_to; 860169689Skan 861169689Skan /* Our profitability metric can depend on local properties 862169689Skan such as number of inlinable calls and size of the function body. 863169689Skan After inlining these properties might change for the function we 864169689Skan inlined into (since it's body size changed) and for the functions 865169689Skan called by function we inlined (since number of it inlinable callers 866169689Skan might change). */ 867169689Skan update_caller_keys (heap, where, updated_nodes); 868169689Skan bitmap_clear (updated_nodes); 869169689Skan 870169689Skan if (dump_file) 871169689Skan { 872169689Skan fprintf (dump_file, 873169689Skan " Inlined into %s which now has %i insns," 874169689Skan "net change of %+i insns.\n", 875169689Skan cgraph_node_name (edge->caller), 876169689Skan edge->caller->global.insns, 877169689Skan overall_insns - old_insns); 878169689Skan } 879169689Skan } 880169689Skan while ((edge = fibheap_extract_min (heap)) != NULL) 881169689Skan { 882169689Skan gcc_assert (edge->aux); 883169689Skan edge->aux = NULL; 884169689Skan if (!edge->callee->local.disregard_inline_limits && edge->inline_failed 885169689Skan && !cgraph_recursive_inlining_p (edge->caller, edge->callee, 886169689Skan &edge->inline_failed)) 887169689Skan edge->inline_failed = N_("--param inline-unit-growth limit reached"); 888169689Skan } 889169689Skan fibheap_delete (heap); 890169689Skan BITMAP_FREE (updated_nodes); 891169689Skan} 892169689Skan 893169689Skan/* Decide on the inlining. We do so in the topological order to avoid 894169689Skan expenses on updating data structures. */ 895169689Skan 896169689Skanstatic unsigned int 897169689Skancgraph_decide_inlining (void) 898169689Skan{ 899169689Skan struct cgraph_node *node; 900169689Skan int nnodes; 901169689Skan struct cgraph_node **order = 902169689Skan XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); 903169689Skan int old_insns = 0; 904169689Skan int i; 905169689Skan 906169689Skan timevar_push (TV_INLINE_HEURISTICS); 907169689Skan max_count = 0; 908169689Skan for (node = cgraph_nodes; node; node = node->next) 909169689Skan if (node->analyzed && (node->needed || node->reachable)) 910169689Skan { 911169689Skan struct cgraph_edge *e; 912169689Skan 913169689Skan /* At the moment, no IPA passes change function bodies before inlining. 914169689Skan Save some time by not recomputing function body sizes if early inlining 915169689Skan already did so. */ 916169689Skan if (!flag_early_inlining) 917169689Skan node->local.self_insns = node->global.insns 918169689Skan = estimate_num_insns (node->decl); 919169689Skan 920169689Skan initial_insns += node->local.self_insns; 921169689Skan gcc_assert (node->local.self_insns == node->global.insns); 922169689Skan for (e = node->callees; e; e = e->next_callee) 923169689Skan if (max_count < e->count) 924169689Skan max_count = e->count; 925169689Skan } 926169689Skan overall_insns = initial_insns; 927169689Skan gcc_assert (!max_count || (profile_info && flag_branch_probabilities)); 928169689Skan 929169689Skan max_insns = overall_insns; 930169689Skan if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS)) 931169689Skan max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS); 932169689Skan 933169689Skan max_insns = ((HOST_WIDEST_INT) max_insns 934169689Skan * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100); 935169689Skan 936169689Skan nnodes = cgraph_postorder (order); 937169689Skan 938169689Skan if (dump_file) 939169689Skan fprintf (dump_file, 940169689Skan "\nDeciding on inlining. Starting with %i insns.\n", 941169689Skan initial_insns); 942169689Skan 943169689Skan for (node = cgraph_nodes; node; node = node->next) 944169689Skan node->aux = 0; 945169689Skan 946169689Skan if (dump_file) 947169689Skan fprintf (dump_file, "\nInlining always_inline functions:\n"); 948169689Skan 949169689Skan /* In the first pass mark all always_inline edges. Do this with a priority 950169689Skan so none of our later choices will make this impossible. */ 951169689Skan for (i = nnodes - 1; i >= 0; i--) 952169689Skan { 953169689Skan struct cgraph_edge *e, *next; 954169689Skan 955169689Skan node = order[i]; 956169689Skan 957169689Skan /* Handle nodes to be flattened, but don't update overall unit size. */ 958169689Skan if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL) 959169689Skan { 960169689Skan int old_overall_insns = overall_insns; 961169689Skan htab_t cycles; 962169689Skan if (dump_file) 963169689Skan fprintf (dump_file, 964169689Skan "Flattening %s\n", cgraph_node_name (node)); 965169689Skan cycles = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL); 966169689Skan cgraph_find_cycles (node, cycles); 967169689Skan cgraph_flatten_node (node, cycles); 968169689Skan htab_delete (cycles); 969169689Skan overall_insns = old_overall_insns; 970169689Skan /* We don't need to consider always_inline functions inside the flattened 971169689Skan function anymore. */ 972169689Skan continue; 973169689Skan } 974169689Skan 975169689Skan if (!node->local.disregard_inline_limits) 976169689Skan continue; 977169689Skan if (dump_file) 978169689Skan fprintf (dump_file, 979169689Skan "\nConsidering %s %i insns (always inline)\n", 980169689Skan cgraph_node_name (node), node->global.insns); 981169689Skan old_insns = overall_insns; 982169689Skan for (e = node->callers; e; e = next) 983169689Skan { 984169689Skan next = e->next_caller; 985169689Skan if (!e->inline_failed) 986169689Skan continue; 987169689Skan if (cgraph_recursive_inlining_p (e->caller, e->callee, 988169689Skan &e->inline_failed)) 989169689Skan continue; 990169689Skan cgraph_mark_inline_edge (e, true); 991169689Skan if (dump_file) 992169689Skan fprintf (dump_file, 993169689Skan " Inlined into %s which now has %i insns.\n", 994169689Skan cgraph_node_name (e->caller), 995169689Skan e->caller->global.insns); 996169689Skan } 997169689Skan if (dump_file) 998169689Skan fprintf (dump_file, 999169689Skan " Inlined for a net change of %+i insns.\n", 1000169689Skan overall_insns - old_insns); 1001169689Skan } 1002169689Skan 1003169689Skan if (!flag_really_no_inline) 1004169689Skan cgraph_decide_inlining_of_small_functions (); 1005169689Skan 1006169689Skan if (!flag_really_no_inline 1007169689Skan && flag_inline_functions_called_once) 1008169689Skan { 1009169689Skan if (dump_file) 1010169689Skan fprintf (dump_file, "\nDeciding on functions called once:\n"); 1011169689Skan 1012169689Skan /* And finally decide what functions are called once. */ 1013169689Skan 1014169689Skan for (i = nnodes - 1; i >= 0; i--) 1015169689Skan { 1016169689Skan node = order[i]; 1017169689Skan 1018169689Skan if (node->callers && !node->callers->next_caller && !node->needed 1019169689Skan && node->local.inlinable && node->callers->inline_failed 1020169689Skan && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl)) 1021169689Skan { 1022169689Skan bool ok = true; 1023169689Skan struct cgraph_node *node1; 1024169689Skan 1025169689Skan /* Verify that we won't duplicate the caller. */ 1026169689Skan for (node1 = node->callers->caller; 1027169689Skan node1->callers && !node1->callers->inline_failed 1028169689Skan && ok; node1 = node1->callers->caller) 1029169689Skan if (node1->callers->next_caller || node1->needed) 1030169689Skan ok = false; 1031169689Skan if (ok) 1032169689Skan { 1033169689Skan if (dump_file) 1034169689Skan { 1035169689Skan fprintf (dump_file, 1036169689Skan "\nConsidering %s %i insns.\n", 1037169689Skan cgraph_node_name (node), node->global.insns); 1038169689Skan fprintf (dump_file, 1039169689Skan " Called once from %s %i insns.\n", 1040169689Skan cgraph_node_name (node->callers->caller), 1041169689Skan node->callers->caller->global.insns); 1042169689Skan } 1043169689Skan 1044169689Skan old_insns = overall_insns; 1045169689Skan 1046169689Skan if (cgraph_check_inline_limits (node->callers->caller, node, 1047169689Skan NULL, false)) 1048169689Skan { 1049169689Skan cgraph_mark_inline (node->callers); 1050169689Skan if (dump_file) 1051169689Skan fprintf (dump_file, 1052169689Skan " Inlined into %s which now has %i insns" 1053169689Skan " for a net change of %+i insns.\n", 1054169689Skan cgraph_node_name (node->callers->caller), 1055169689Skan node->callers->caller->global.insns, 1056169689Skan overall_insns - old_insns); 1057169689Skan } 1058169689Skan else 1059169689Skan { 1060169689Skan if (dump_file) 1061169689Skan fprintf (dump_file, 1062169689Skan " Inline limit reached, not inlined.\n"); 1063169689Skan } 1064169689Skan } 1065169689Skan } 1066169689Skan } 1067169689Skan } 1068169689Skan 1069169689Skan if (dump_file) 1070169689Skan fprintf (dump_file, 1071169689Skan "\nInlined %i calls, eliminated %i functions, " 1072169689Skan "%i insns turned to %i insns.\n\n", 1073169689Skan ncalls_inlined, nfunctions_inlined, initial_insns, 1074169689Skan overall_insns); 1075169689Skan free (order); 1076169689Skan timevar_pop (TV_INLINE_HEURISTICS); 1077169689Skan return 0; 1078169689Skan} 1079169689Skan 1080169689Skan/* Decide on the inlining. We do so in the topological order to avoid 1081169689Skan expenses on updating data structures. */ 1082169689Skan 1083169689Skanbool 1084169689Skancgraph_decide_inlining_incrementally (struct cgraph_node *node, bool early) 1085169689Skan{ 1086169689Skan struct cgraph_edge *e; 1087169689Skan bool inlined = false; 1088169689Skan const char *failed_reason; 1089169689Skan 1090169689Skan /* First of all look for always inline functions. */ 1091169689Skan for (e = node->callees; e; e = e->next_callee) 1092169689Skan if (e->callee->local.disregard_inline_limits 1093169689Skan && e->inline_failed 1094169689Skan && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed) 1095169689Skan /* ??? It is possible that renaming variable removed the function body 1096169689Skan in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */ 1097169689Skan && (DECL_SAVED_TREE (e->callee->decl) || e->callee->inline_decl)) 1098169689Skan { 1099169689Skan if (dump_file && early) 1100169689Skan { 1101169689Skan fprintf (dump_file, " Early inlining %s", 1102169689Skan cgraph_node_name (e->callee)); 1103169689Skan fprintf (dump_file, " into %s\n", cgraph_node_name (node)); 1104169689Skan } 1105169689Skan cgraph_mark_inline (e); 1106169689Skan inlined = true; 1107169689Skan } 1108169689Skan 1109169689Skan /* Now do the automatic inlining. */ 1110169689Skan if (!flag_really_no_inline) 1111169689Skan for (e = node->callees; e; e = e->next_callee) 1112169689Skan if (e->callee->local.inlinable 1113169689Skan && e->inline_failed 1114169689Skan && !e->callee->local.disregard_inline_limits 1115169689Skan && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed) 1116169689Skan && (!early 1117169689Skan || (cgraph_estimate_size_after_inlining (1, e->caller, e->callee) 1118169689Skan <= e->caller->global.insns)) 1119169689Skan && cgraph_check_inline_limits (node, e->callee, &e->inline_failed, 1120169689Skan false) 1121169689Skan && (DECL_SAVED_TREE (e->callee->decl) || e->callee->inline_decl)) 1122169689Skan { 1123169689Skan if (cgraph_default_inline_p (e->callee, &failed_reason)) 1124169689Skan { 1125169689Skan if (dump_file && early) 1126169689Skan { 1127169689Skan fprintf (dump_file, " Early inlining %s", 1128169689Skan cgraph_node_name (e->callee)); 1129169689Skan fprintf (dump_file, " into %s\n", cgraph_node_name (node)); 1130169689Skan } 1131169689Skan cgraph_mark_inline (e); 1132169689Skan inlined = true; 1133169689Skan } 1134169689Skan else if (!early) 1135169689Skan e->inline_failed = failed_reason; 1136169689Skan } 1137169689Skan if (early && inlined) 1138169689Skan { 1139169689Skan push_cfun (DECL_STRUCT_FUNCTION (node->decl)); 1140169689Skan tree_register_cfg_hooks (); 1141169689Skan current_function_decl = node->decl; 1142169689Skan optimize_inline_calls (current_function_decl); 1143169689Skan node->local.self_insns = node->global.insns; 1144169689Skan current_function_decl = NULL; 1145169689Skan pop_cfun (); 1146169689Skan } 1147169689Skan return inlined; 1148169689Skan} 1149169689Skan 1150169689Skan/* When inlining shall be performed. */ 1151169689Skanstatic bool 1152169689Skancgraph_gate_inlining (void) 1153169689Skan{ 1154169689Skan return flag_inline_trees; 1155169689Skan} 1156169689Skan 1157169689Skanstruct tree_opt_pass pass_ipa_inline = 1158169689Skan{ 1159169689Skan "inline", /* name */ 1160169689Skan cgraph_gate_inlining, /* gate */ 1161169689Skan cgraph_decide_inlining, /* execute */ 1162169689Skan NULL, /* sub */ 1163169689Skan NULL, /* next */ 1164169689Skan 0, /* static_pass_number */ 1165169689Skan TV_INTEGRATION, /* tv_id */ 1166169689Skan 0, /* properties_required */ 1167169689Skan PROP_cfg, /* properties_provided */ 1168169689Skan 0, /* properties_destroyed */ 1169169689Skan 0, /* todo_flags_start */ 1170169689Skan TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */ 1171169689Skan 0 /* letter */ 1172169689Skan}; 1173169689Skan 1174169689Skan/* Because inlining might remove no-longer reachable nodes, we need to 1175169689Skan keep the array visible to garbage collector to avoid reading collected 1176169689Skan out nodes. */ 1177169689Skanstatic int nnodes; 1178169689Skanstatic GTY ((length ("nnodes"))) struct cgraph_node **order; 1179169689Skan 1180169689Skan/* Do inlining of small functions. Doing so early helps profiling and other 1181169689Skan passes to be somewhat more effective and avoids some code duplication in 1182169689Skan later real inlining pass for testcases with very many function calls. */ 1183169689Skanstatic unsigned int 1184169689Skancgraph_early_inlining (void) 1185169689Skan{ 1186169689Skan struct cgraph_node *node; 1187169689Skan int i; 1188169689Skan 1189169689Skan if (sorrycount || errorcount) 1190169689Skan return 0; 1191169689Skan#ifdef ENABLE_CHECKING 1192169689Skan for (node = cgraph_nodes; node; node = node->next) 1193169689Skan gcc_assert (!node->aux); 1194169689Skan#endif 1195169689Skan 1196169689Skan order = ggc_alloc (sizeof (*order) * cgraph_n_nodes); 1197169689Skan nnodes = cgraph_postorder (order); 1198169689Skan for (i = nnodes - 1; i >= 0; i--) 1199169689Skan { 1200169689Skan node = order[i]; 1201169689Skan if (node->analyzed && (node->needed || node->reachable)) 1202169689Skan node->local.self_insns = node->global.insns 1203169689Skan = estimate_num_insns (node->decl); 1204169689Skan } 1205169689Skan for (i = nnodes - 1; i >= 0; i--) 1206169689Skan { 1207169689Skan node = order[i]; 1208169689Skan if (node->analyzed && node->local.inlinable 1209169689Skan && (node->needed || node->reachable) 1210169689Skan && node->callers) 1211169689Skan { 1212169689Skan if (cgraph_decide_inlining_incrementally (node, true)) 1213169689Skan ggc_collect (); 1214169689Skan } 1215169689Skan } 1216169689Skan cgraph_remove_unreachable_nodes (true, dump_file); 1217169689Skan#ifdef ENABLE_CHECKING 1218169689Skan for (node = cgraph_nodes; node; node = node->next) 1219169689Skan gcc_assert (!node->global.inlined_to); 1220169689Skan#endif 1221169689Skan ggc_free (order); 1222169689Skan order = NULL; 1223169689Skan nnodes = 0; 1224169689Skan return 0; 1225169689Skan} 1226169689Skan 1227169689Skan/* When inlining shall be performed. */ 1228169689Skanstatic bool 1229169689Skancgraph_gate_early_inlining (void) 1230169689Skan{ 1231169689Skan return flag_inline_trees && flag_early_inlining; 1232169689Skan} 1233169689Skan 1234169689Skanstruct tree_opt_pass pass_early_ipa_inline = 1235169689Skan{ 1236169689Skan "einline", /* name */ 1237169689Skan cgraph_gate_early_inlining, /* gate */ 1238169689Skan cgraph_early_inlining, /* execute */ 1239169689Skan NULL, /* sub */ 1240169689Skan NULL, /* next */ 1241169689Skan 0, /* static_pass_number */ 1242169689Skan TV_INTEGRATION, /* tv_id */ 1243169689Skan 0, /* properties_required */ 1244169689Skan PROP_cfg, /* properties_provided */ 1245169689Skan 0, /* properties_destroyed */ 1246169689Skan 0, /* todo_flags_start */ 1247169689Skan TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */ 1248169689Skan 0 /* letter */ 1249169689Skan}; 1250169689Skan 1251169689Skan#include "gt-ipa-inline.h" 1252