1/* Callgraph transformations to handle inlining 2 Copyright (C) 2003-2015 Free Software Foundation, Inc. 3 Contributed by Jan Hubicka 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21/* The inline decisions are stored in callgraph in "inline plan" and 22 applied later. 23 24 To mark given call inline, use inline_call function. 25 The function marks the edge inlinable and, if necessary, produces 26 virtual clone in the callgraph representing the new copy of callee's 27 function body. 28 29 The inline plan is applied on given function body by inline_transform. */ 30 31#include "config.h" 32#include "system.h" 33#include "coretypes.h" 34#include "tm.h" 35#include "hash-set.h" 36#include "machmode.h" 37#include "vec.h" 38#include "double-int.h" 39#include "input.h" 40#include "alias.h" 41#include "symtab.h" 42#include "wide-int.h" 43#include "inchash.h" 44#include "tree.h" 45#include "langhooks.h" 46#include "intl.h" 47#include "coverage.h" 48#include "ggc.h" 49#include "tree-cfg.h" 50#include "hash-map.h" 51#include "is-a.h" 52#include "plugin-api.h" 53#include "hard-reg-set.h" 54#include "input.h" 55#include "function.h" 56#include "ipa-ref.h" 57#include "cgraph.h" 58#include "alloc-pool.h" 59#include "symbol-summary.h" 60#include "ipa-prop.h" 61#include "ipa-inline.h" 62#include "tree-inline.h" 63#include "tree-pass.h" 64 65int ncalls_inlined; 66int nfunctions_inlined; 67 68/* Scale frequency of NODE edges by FREQ_SCALE. */ 69 70static void 71update_noncloned_frequencies (struct cgraph_node *node, 72 int freq_scale) 73{ 74 struct cgraph_edge *e; 75 76 /* We do not want to ignore high loop nest after freq drops to 0. */ 77 if (!freq_scale) 78 freq_scale = 1; 79 for (e = node->callees; e; e = e->next_callee) 80 { 81 e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE; 82 if (e->frequency > CGRAPH_FREQ_MAX) 83 e->frequency = CGRAPH_FREQ_MAX; 84 if (!e->inline_failed) 85 update_noncloned_frequencies (e->callee, freq_scale); 86 } 87 for (e = node->indirect_calls; e; e = e->next_callee) 88 { 89 e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE; 90 if (e->frequency > CGRAPH_FREQ_MAX) 91 e->frequency = CGRAPH_FREQ_MAX; 92 } 93} 94 95/* We removed or are going to remove the last call to NODE. 96 Return true if we can and want proactively remove the NODE now. 97 This is important to do, since we want inliner to know when offline 98 copy of function was removed. */ 99 100static bool 101can_remove_node_now_p_1 (struct cgraph_node *node, struct cgraph_edge *e) 102{ 103 ipa_ref *ref; 104 105 FOR_EACH_ALIAS (node, ref) 106 { 107 cgraph_node *alias = dyn_cast <cgraph_node *> (ref->referring); 108 if ((alias->callers && alias->callers != e) 109 || !can_remove_node_now_p_1 (alias, e)) 110 return false; 111 } 112 /* FIXME: When address is taken of DECL_EXTERNAL function we still 113 can remove its offline copy, but we would need to keep unanalyzed node in 114 the callgraph so references can point to it. 115 116 Also for comdat group we can ignore references inside a group as we 117 want to prove the group as a whole to be dead. */ 118 return (!node->address_taken 119 && node->can_remove_if_no_direct_calls_and_refs_p () 120 /* Inlining might enable more devirtualizing, so we want to remove 121 those only after all devirtualizable virtual calls are processed. 122 Lacking may edges in callgraph we just preserve them post 123 inlining. */ 124 && (!DECL_VIRTUAL_P (node->decl) 125 || !opt_for_fn (node->decl, flag_devirtualize)) 126 /* During early inlining some unanalyzed cgraph nodes might be in the 127 callgraph and they might reffer the function in question. */ 128 && !cgraph_new_nodes.exists ()); 129} 130 131/* We are going to eliminate last direct call to NODE (or alias of it) via edge E. 132 Verify that the NODE can be removed from unit and if it is contained in comdat 133 group that the whole comdat group is removable. */ 134 135static bool 136can_remove_node_now_p (struct cgraph_node *node, struct cgraph_edge *e) 137{ 138 struct cgraph_node *next; 139 if (!can_remove_node_now_p_1 (node, e)) 140 return false; 141 142 /* When we see same comdat group, we need to be sure that all 143 items can be removed. */ 144 if (!node->same_comdat_group || !node->externally_visible) 145 return true; 146 for (next = dyn_cast<cgraph_node *> (node->same_comdat_group); 147 next != node; next = dyn_cast<cgraph_node *> (next->same_comdat_group)) 148 { 149 if (next->alias) 150 continue; 151 if ((next->callers && next->callers != e) 152 || !can_remove_node_now_p_1 (next, e)) 153 return false; 154 } 155 return true; 156} 157 158/* Return true if NODE is a master clone with non-inline clones. */ 159 160static bool 161master_clone_with_noninline_clones_p (struct cgraph_node *node) 162{ 163 if (node->clone_of) 164 return false; 165 166 for (struct cgraph_node *n = node->clones; n; n = n->next_sibling_clone) 167 if (n->decl != node->decl) 168 return true; 169 170 return false; 171} 172 173/* E is expected to be an edge being inlined. Clone destination node of 174 the edge and redirect it to the new clone. 175 DUPLICATE is used for bookkeeping on whether we are actually creating new 176 clones or re-using node originally representing out-of-line function call. 177 By default the offline copy is removed, when it appears dead after inlining. 178 UPDATE_ORIGINAL prevents this transformation. 179 If OVERALL_SIZE is non-NULL, the size is updated to reflect the 180 transformation. 181 FREQ_SCALE specify the scaling of frequencies of call sites. */ 182 183void 184clone_inlined_nodes (struct cgraph_edge *e, bool duplicate, 185 bool update_original, int *overall_size, int freq_scale) 186{ 187 struct cgraph_node *inlining_into; 188 struct cgraph_edge *next; 189 190 if (e->caller->global.inlined_to) 191 inlining_into = e->caller->global.inlined_to; 192 else 193 inlining_into = e->caller; 194 195 if (duplicate) 196 { 197 /* We may eliminate the need for out-of-line copy to be output. 198 In that case just go ahead and re-use it. This is not just an 199 memory optimization. Making offline copy of fuction disappear 200 from the program will improve future decisions on inlining. */ 201 if (!e->callee->callers->next_caller 202 /* Recursive inlining never wants the master clone to 203 be overwritten. */ 204 && update_original 205 && can_remove_node_now_p (e->callee, e) 206 /* We cannot overwrite a master clone with non-inline clones 207 until after these clones are materialized. */ 208 && !master_clone_with_noninline_clones_p (e->callee)) 209 { 210 /* TODO: When callee is in a comdat group, we could remove all of it, 211 including all inline clones inlined into it. That would however 212 need small function inlining to register edge removal hook to 213 maintain the priority queue. 214 215 For now we keep the ohter functions in the group in program until 216 cgraph_remove_unreachable_functions gets rid of them. */ 217 gcc_assert (!e->callee->global.inlined_to); 218 e->callee->remove_from_same_comdat_group (); 219 if (e->callee->definition 220 && inline_account_function_p (e->callee)) 221 { 222 gcc_assert (!e->callee->alias); 223 if (overall_size) 224 *overall_size -= inline_summaries->get (e->callee)->size; 225 nfunctions_inlined++; 226 } 227 duplicate = false; 228 e->callee->externally_visible = false; 229 update_noncloned_frequencies (e->callee, e->frequency); 230 } 231 else 232 { 233 struct cgraph_node *n; 234 235 if (freq_scale == -1) 236 freq_scale = e->frequency; 237 n = e->callee->create_clone (e->callee->decl, 238 MIN (e->count, e->callee->count), 239 freq_scale, 240 update_original, vNULL, true, 241 inlining_into, 242 NULL); 243 n->used_as_abstract_origin = e->callee->used_as_abstract_origin; 244 e->redirect_callee (n); 245 } 246 } 247 else 248 e->callee->remove_from_same_comdat_group (); 249 250 e->callee->global.inlined_to = inlining_into; 251 252 /* Recursively clone all bodies. */ 253 for (e = e->callee->callees; e; e = next) 254 { 255 next = e->next_callee; 256 if (!e->inline_failed) 257 clone_inlined_nodes (e, duplicate, update_original, overall_size, freq_scale); 258 } 259} 260 261/* Check all speculations in N and resolve them if they seems useless. */ 262 263static bool 264check_speculations (cgraph_node *n) 265{ 266 bool speculation_removed = false; 267 cgraph_edge *next; 268 269 for (cgraph_edge *e = n->callees; e; e = next) 270 { 271 next = e->next_callee; 272 if (e->speculative && !speculation_useful_p (e, true)) 273 { 274 e->resolve_speculation (NULL); 275 speculation_removed = true; 276 } 277 else if (!e->inline_failed) 278 speculation_removed |= check_speculations (e->callee); 279 } 280 return speculation_removed; 281} 282 283/* Mark all call graph edges coming out of NODE and all nodes that have been 284 inlined to it as in_polymorphic_cdtor. */ 285 286static void 287mark_all_inlined_calls_cdtor (cgraph_node *node) 288{ 289 for (cgraph_edge *cs = node->callees; cs; cs = cs->next_callee) 290 { 291 cs->in_polymorphic_cdtor = true; 292 if (!cs->inline_failed) 293 mark_all_inlined_calls_cdtor (cs->callee); 294 } 295 for (cgraph_edge *cs = node->indirect_calls; cs; cs = cs->next_callee) 296 cs->in_polymorphic_cdtor = true; 297} 298 299 300/* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL 301 specify whether profile of original function should be updated. If any new 302 indirect edges are discovered in the process, add them to NEW_EDGES, unless 303 it is NULL. If UPDATE_OVERALL_SUMMARY is false, do not bother to recompute overall 304 size of caller after inlining. Caller is required to eventually do it via 305 inline_update_overall_summary. 306 If callee_removed is non-NULL, set it to true if we removed callee node. 307 308 Return true iff any new callgraph edges were discovered as a 309 result of inlining. */ 310 311bool 312inline_call (struct cgraph_edge *e, bool update_original, 313 vec<cgraph_edge *> *new_edges, 314 int *overall_size, bool update_overall_summary, 315 bool *callee_removed) 316{ 317 int old_size = 0, new_size = 0; 318 struct cgraph_node *to = NULL; 319 struct cgraph_edge *curr = e; 320 struct cgraph_node *callee = e->callee->ultimate_alias_target (); 321 bool new_edges_found = false; 322 323 /* This is used only for assert bellow. */ 324#if 0 325 int estimated_growth = estimate_edge_growth (e); 326 bool predicated = inline_edge_summary (e)->predicate != NULL; 327#endif 328 329 /* Don't inline inlined edges. */ 330 gcc_assert (e->inline_failed); 331 /* Don't even think of inlining inline clone. */ 332 gcc_assert (!callee->global.inlined_to); 333 334 e->inline_failed = CIF_OK; 335 DECL_POSSIBLY_INLINED (callee->decl) = true; 336 337 to = e->caller; 338 if (to->global.inlined_to) 339 to = to->global.inlined_to; 340 341 if (DECL_FUNCTION_PERSONALITY (callee->decl)) 342 DECL_FUNCTION_PERSONALITY (to->decl) 343 = DECL_FUNCTION_PERSONALITY (callee->decl); 344 345 /* If aliases are involved, redirect edge to the actual destination and 346 possibly remove the aliases. */ 347 if (e->callee != callee) 348 { 349 struct cgraph_node *alias = e->callee, *next_alias; 350 e->redirect_callee (callee); 351 while (alias && alias != callee) 352 { 353 if (!alias->callers 354 && can_remove_node_now_p (alias, 355 !e->next_caller && !e->prev_caller ? e : NULL)) 356 { 357 next_alias = alias->get_alias_target (); 358 alias->remove (); 359 if (callee_removed) 360 *callee_removed = true; 361 alias = next_alias; 362 } 363 else 364 break; 365 } 366 } 367 368 clone_inlined_nodes (e, true, update_original, overall_size, e->frequency); 369 370 gcc_assert (curr->callee->global.inlined_to == to); 371 372 old_size = inline_summaries->get (to)->size; 373 inline_merge_summary (e); 374 if (e->in_polymorphic_cdtor) 375 mark_all_inlined_calls_cdtor (e->callee); 376 if (opt_for_fn (e->caller->decl, optimize)) 377 new_edges_found = ipa_propagate_indirect_call_infos (curr, new_edges); 378 check_speculations (e->callee); 379 if (update_overall_summary) 380 inline_update_overall_summary (to); 381 new_size = inline_summaries->get (to)->size; 382 383 if (callee->calls_comdat_local) 384 to->calls_comdat_local = true; 385 else if (to->calls_comdat_local && callee->comdat_local_p ()) 386 { 387 struct cgraph_edge *se = to->callees; 388 for (; se; se = se->next_callee) 389 if (se->inline_failed && se->callee->comdat_local_p ()) 390 break; 391 if (se == NULL) 392 to->calls_comdat_local = false; 393 } 394 395 /* FIXME: This assert suffers from roundoff errors, disable it for GCC 5 396 and revisit it after conversion to sreals in GCC 6. 397 See PR 65654. */ 398#if 0 399 /* Verify that estimated growth match real growth. Allow off-by-one 400 error due to INLINE_SIZE_SCALE roudoff errors. */ 401 gcc_assert (!update_overall_summary || !overall_size || new_edges_found 402 || abs (estimated_growth - (new_size - old_size)) <= 1 403 || speculation_removed 404 /* FIXME: a hack. Edges with false predicate are accounted 405 wrong, we should remove them from callgraph. */ 406 || predicated); 407#endif 408 409 /* Account the change of overall unit size; external functions will be 410 removed and are thus not accounted. */ 411 if (overall_size && inline_account_function_p (to)) 412 *overall_size += new_size - old_size; 413 ncalls_inlined++; 414 415 /* This must happen after inline_merge_summary that rely on jump 416 functions of callee to not be updated. */ 417 return new_edges_found; 418} 419 420 421/* Copy function body of NODE and redirect all inline clones to it. 422 This is done before inline plan is applied to NODE when there are 423 still some inline clones if it. 424 425 This is necessary because inline decisions are not really transitive 426 and the other inline clones may have different bodies. */ 427 428static struct cgraph_node * 429save_inline_function_body (struct cgraph_node *node) 430{ 431 struct cgraph_node *first_clone, *n; 432 433 if (dump_file) 434 fprintf (dump_file, "\nSaving body of %s for later reuse\n", 435 node->name ()); 436 437 gcc_assert (node == cgraph_node::get (node->decl)); 438 439 /* first_clone will be turned into real function. */ 440 first_clone = node->clones; 441 first_clone->decl = copy_node (node->decl); 442 first_clone->decl->decl_with_vis.symtab_node = first_clone; 443 gcc_assert (first_clone == cgraph_node::get (first_clone->decl)); 444 445 /* Now reshape the clone tree, so all other clones descends from 446 first_clone. */ 447 if (first_clone->next_sibling_clone) 448 { 449 for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone) 450 n->clone_of = first_clone; 451 n->clone_of = first_clone; 452 n->next_sibling_clone = first_clone->clones; 453 if (first_clone->clones) 454 first_clone->clones->prev_sibling_clone = n; 455 first_clone->clones = first_clone->next_sibling_clone; 456 first_clone->next_sibling_clone->prev_sibling_clone = NULL; 457 first_clone->next_sibling_clone = NULL; 458 gcc_assert (!first_clone->prev_sibling_clone); 459 } 460 first_clone->clone_of = NULL; 461 462 /* Now node in question has no clones. */ 463 node->clones = NULL; 464 465 /* Inline clones share decl with the function they are cloned 466 from. Walk the whole clone tree and redirect them all to the 467 new decl. */ 468 if (first_clone->clones) 469 for (n = first_clone->clones; n != first_clone;) 470 { 471 gcc_assert (n->decl == node->decl); 472 n->decl = first_clone->decl; 473 if (n->clones) 474 n = n->clones; 475 else if (n->next_sibling_clone) 476 n = n->next_sibling_clone; 477 else 478 { 479 while (n != first_clone && !n->next_sibling_clone) 480 n = n->clone_of; 481 if (n != first_clone) 482 n = n->next_sibling_clone; 483 } 484 } 485 486 /* Copy the OLD_VERSION_NODE function tree to the new version. */ 487 tree_function_versioning (node->decl, first_clone->decl, 488 NULL, true, NULL, false, 489 NULL, NULL); 490 491 /* The function will be short lived and removed after we inline all the clones, 492 but make it internal so we won't confuse ourself. */ 493 DECL_EXTERNAL (first_clone->decl) = 0; 494 TREE_PUBLIC (first_clone->decl) = 0; 495 DECL_COMDAT (first_clone->decl) = 0; 496 first_clone->ipa_transforms_to_apply.release (); 497 498 /* When doing recursive inlining, the clone may become unnecessary. 499 This is possible i.e. in the case when the recursive function is proved to be 500 non-throwing and the recursion happens only in the EH landing pad. 501 We can not remove the clone until we are done with saving the body. 502 Remove it now. */ 503 if (!first_clone->callers) 504 { 505 first_clone->remove_symbol_and_inline_clones (); 506 first_clone = NULL; 507 } 508#ifdef ENABLE_CHECKING 509 else 510 first_clone->verify (); 511#endif 512 return first_clone; 513} 514 515/* Return true when function body of DECL still needs to be kept around 516 for later re-use. */ 517static bool 518preserve_function_body_p (struct cgraph_node *node) 519{ 520 gcc_assert (symtab->global_info_ready); 521 gcc_assert (!node->alias && !node->thunk.thunk_p); 522 523 /* Look if there is any clone around. */ 524 if (node->clones) 525 return true; 526 return false; 527} 528 529/* Apply inline plan to function. */ 530 531unsigned int 532inline_transform (struct cgraph_node *node) 533{ 534 unsigned int todo = 0; 535 struct cgraph_edge *e, *next; 536 bool has_inline = false; 537 538 /* FIXME: Currently the pass manager is adding inline transform more than 539 once to some clones. This needs revisiting after WPA cleanups. */ 540 if (cfun->after_inlining) 541 return 0; 542 543 /* We might need the body of this function so that we can expand 544 it inline somewhere else. */ 545 if (preserve_function_body_p (node)) 546 save_inline_function_body (node); 547 548 for (e = node->callees; e; e = next) 549 { 550 if (!e->inline_failed) 551 has_inline = true; 552 next = e->next_callee; 553 e->redirect_call_stmt_to_callee (); 554 } 555 node->remove_all_references (); 556 557 timevar_push (TV_INTEGRATION); 558 if (node->callees && (opt_for_fn (node->decl, optimize) || has_inline)) 559 todo = optimize_inline_calls (current_function_decl); 560 timevar_pop (TV_INTEGRATION); 561 562 cfun->always_inline_functions_inlined = true; 563 cfun->after_inlining = true; 564 todo |= execute_fixup_cfg (); 565 566 if (!(todo & TODO_update_ssa_any)) 567 /* Redirecting edges might lead to a need for vops to be recomputed. */ 568 todo |= TODO_update_ssa_only_virtuals; 569 570 return todo; 571} 572