1/* Analysis used by inlining decision heuristics. 2 Copyright (C) 2003-2020 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#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "backend.h" 25#include "tree.h" 26#include "gimple.h" 27#include "alloc-pool.h" 28#include "tree-pass.h" 29#include "ssa.h" 30#include "tree-streamer.h" 31#include "cgraph.h" 32#include "diagnostic.h" 33#include "fold-const.h" 34#include "print-tree.h" 35#include "tree-inline.h" 36#include "gimple-pretty-print.h" 37#include "cfganal.h" 38#include "gimple-iterator.h" 39#include "tree-cfg.h" 40#include "tree-ssa-loop-niter.h" 41#include "tree-ssa-loop.h" 42#include "symbol-summary.h" 43#include "ipa-prop.h" 44#include "ipa-fnsummary.h" 45#include "ipa-inline.h" 46#include "cfgloop.h" 47#include "tree-scalar-evolution.h" 48#include "ipa-utils.h" 49#include "cfgexpand.h" 50#include "gimplify.h" 51 52/* Cached node/edge growths. */ 53fast_call_summary<edge_growth_cache_entry *, va_heap> *edge_growth_cache = NULL; 54 55/* The context cache remembers estimated time/size and hints for given 56 ipa_call_context of a call. */ 57class node_context_cache_entry 58{ 59public: 60 ipa_call_context ctx; 61 sreal time, nonspec_time; 62 int size; 63 ipa_hints hints; 64 65 node_context_cache_entry () 66 : ctx () 67 { 68 } 69 ~node_context_cache_entry () 70 { 71 ctx.release (); 72 } 73}; 74 75/* At the moment we implement primitive single entry LRU cache. */ 76class node_context_summary 77{ 78public: 79 node_context_cache_entry entry; 80 81 node_context_summary () 82 : entry () 83 { 84 } 85 ~node_context_summary () 86 { 87 } 88}; 89 90/* Summary holding the context cache. */ 91static fast_function_summary <node_context_summary *, va_heap> 92 *node_context_cache = NULL; 93/* Statistics about the context cache effectivity. */ 94static long node_context_cache_hit, node_context_cache_miss, 95 node_context_cache_clear; 96 97/* Give initial reasons why inlining would fail on EDGE. This gets either 98 nullified or usually overwritten by more precise reasons later. */ 99 100void 101initialize_inline_failed (struct cgraph_edge *e) 102{ 103 struct cgraph_node *callee = e->callee; 104 105 if (e->inline_failed && e->inline_failed != CIF_BODY_NOT_AVAILABLE 106 && cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR) 107 ; 108 else if (e->indirect_unknown_callee) 109 e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL; 110 else if (!callee->definition) 111 e->inline_failed = CIF_BODY_NOT_AVAILABLE; 112 else if (callee->redefined_extern_inline) 113 e->inline_failed = CIF_REDEFINED_EXTERN_INLINE; 114 else 115 e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED; 116 gcc_checking_assert (!e->call_stmt_cannot_inline_p 117 || cgraph_inline_failed_type (e->inline_failed) 118 == CIF_FINAL_ERROR); 119} 120 121/* Allocate edge growth caches. */ 122 123void 124initialize_growth_caches () 125{ 126 edge_growth_cache 127 = new fast_call_summary<edge_growth_cache_entry *, va_heap> (symtab); 128 node_context_cache 129 = new fast_function_summary<node_context_summary *, va_heap> (symtab); 130} 131 132/* Free growth caches. */ 133 134void 135free_growth_caches (void) 136{ 137 delete edge_growth_cache; 138 delete node_context_cache; 139 edge_growth_cache = NULL; 140 node_context_cache = NULL; 141 if (dump_file) 142 fprintf (dump_file, "node context cache: %li hits, %li misses," 143 " %li initializations\n", 144 node_context_cache_hit, node_context_cache_miss, 145 node_context_cache_clear); 146 node_context_cache_hit = 0; 147 node_context_cache_miss = 0; 148 node_context_cache_clear = 0; 149} 150 151/* Return hints derived from EDGE. */ 152 153int 154simple_edge_hints (struct cgraph_edge *edge) 155{ 156 int hints = 0; 157 struct cgraph_node *to = (edge->caller->inlined_to 158 ? edge->caller->inlined_to : edge->caller); 159 struct cgraph_node *callee = edge->callee->ultimate_alias_target (); 160 int to_scc_no = ipa_fn_summaries->get (to)->scc_no; 161 int callee_scc_no = ipa_fn_summaries->get (callee)->scc_no; 162 163 if (to_scc_no && to_scc_no == callee_scc_no && !edge->recursive_p ()) 164 hints |= INLINE_HINT_same_scc; 165 166 if (cross_module_call_p (edge)) 167 hints |= INLINE_HINT_cross_module; 168 169 return hints; 170} 171 172/* Estimate the time cost for the caller when inlining EDGE. 173 Only to be called via estimate_edge_time, that handles the 174 caching mechanism. 175 176 When caching, also update the cache entry. Compute both time and 177 size, since we always need both metrics eventually. */ 178 179sreal 180do_estimate_edge_time (struct cgraph_edge *edge, sreal *ret_nonspec_time) 181{ 182 sreal time, nonspec_time; 183 int size; 184 ipa_hints hints; 185 struct cgraph_node *callee; 186 clause_t clause, nonspec_clause; 187 auto_vec<tree, 32> known_vals; 188 auto_vec<ipa_polymorphic_call_context, 32> known_contexts; 189 auto_vec<ipa_agg_value_set, 32> known_aggs; 190 class ipa_call_summary *es = ipa_call_summaries->get (edge); 191 int min_size = -1; 192 193 callee = edge->callee->ultimate_alias_target (); 194 195 gcc_checking_assert (edge->inline_failed); 196 evaluate_properties_for_edge (edge, true, 197 &clause, &nonspec_clause, &known_vals, 198 &known_contexts, &known_aggs); 199 ipa_call_context ctx (callee, clause, nonspec_clause, known_vals, 200 known_contexts, known_aggs, es->param); 201 if (node_context_cache != NULL) 202 { 203 node_context_summary *e = node_context_cache->get_create (callee); 204 if (e->entry.ctx.equal_to (ctx)) 205 { 206 node_context_cache_hit++; 207 size = e->entry.size; 208 time = e->entry.time; 209 nonspec_time = e->entry.nonspec_time; 210 hints = e->entry.hints; 211 if (flag_checking 212 && !opt_for_fn (callee->decl, flag_profile_partial_training) 213 && !callee->count.ipa_p ()) 214 { 215 sreal chk_time, chk_nonspec_time; 216 int chk_size, chk_min_size; 217 218 ipa_hints chk_hints; 219 ctx.estimate_size_and_time (&chk_size, &chk_min_size, 220 &chk_time, &chk_nonspec_time, 221 &chk_hints); 222 gcc_assert (chk_size == size && chk_time == time 223 && chk_nonspec_time == nonspec_time 224 && chk_hints == hints); 225 } 226 } 227 else 228 { 229 if (e->entry.ctx.exists_p ()) 230 node_context_cache_miss++; 231 else 232 node_context_cache_clear++; 233 e->entry.ctx.release (true); 234 ctx.estimate_size_and_time (&size, &min_size, 235 &time, &nonspec_time, &hints); 236 e->entry.size = size; 237 e->entry.time = time; 238 e->entry.nonspec_time = nonspec_time; 239 e->entry.hints = hints; 240 e->entry.ctx.duplicate_from (ctx); 241 } 242 } 243 else 244 ctx.estimate_size_and_time (&size, &min_size, 245 &time, &nonspec_time, &hints); 246 247 /* When we have profile feedback, we can quite safely identify hot 248 edges and for those we disable size limits. Don't do that when 249 probability that caller will call the callee is low however, since it 250 may hurt optimization of the caller's hot path. */ 251 if (edge->count.ipa ().initialized_p () && edge->maybe_hot_p () 252 && (edge->count.ipa ().apply_scale (2, 1) 253 > (edge->caller->inlined_to 254 ? edge->caller->inlined_to->count.ipa () 255 : edge->caller->count.ipa ()))) 256 hints |= INLINE_HINT_known_hot; 257 258 ctx.release (); 259 gcc_checking_assert (size >= 0); 260 gcc_checking_assert (time >= 0); 261 262 /* When caching, update the cache entry. */ 263 if (edge_growth_cache != NULL) 264 { 265 if (min_size >= 0) 266 ipa_fn_summaries->get (edge->callee->function_symbol ())->min_size 267 = min_size; 268 edge_growth_cache_entry *entry 269 = edge_growth_cache->get_create (edge); 270 entry->time = time; 271 entry->nonspec_time = nonspec_time; 272 273 entry->size = size + (size >= 0); 274 hints |= simple_edge_hints (edge); 275 entry->hints = hints + 1; 276 } 277 if (ret_nonspec_time) 278 *ret_nonspec_time = nonspec_time; 279 return time; 280} 281 282/* Reset cache for NODE. 283 This must be done each time NODE body is modified. */ 284void 285reset_node_cache (struct cgraph_node *node) 286{ 287 if (node_context_cache) 288 node_context_cache->remove (node); 289} 290 291/* Remove EDGE from caches once it was inlined. */ 292void 293ipa_remove_from_growth_caches (struct cgraph_edge *edge) 294{ 295 if (node_context_cache) 296 node_context_cache->remove (edge->callee); 297 if (edge_growth_cache) 298 edge_growth_cache->remove (edge); 299} 300 301/* Return estimated callee growth after inlining EDGE. 302 Only to be called via estimate_edge_size. */ 303 304int 305do_estimate_edge_size (struct cgraph_edge *edge) 306{ 307 int size; 308 struct cgraph_node *callee; 309 clause_t clause, nonspec_clause; 310 auto_vec<tree, 32> known_vals; 311 auto_vec<ipa_polymorphic_call_context, 32> known_contexts; 312 auto_vec<ipa_agg_value_set, 32> known_aggs; 313 314 /* When we do caching, use do_estimate_edge_time to populate the entry. */ 315 316 if (edge_growth_cache != NULL) 317 { 318 do_estimate_edge_time (edge); 319 size = edge_growth_cache->get (edge)->size; 320 gcc_checking_assert (size); 321 return size - (size > 0); 322 } 323 324 callee = edge->callee->ultimate_alias_target (); 325 326 /* Early inliner runs without caching, go ahead and do the dirty work. */ 327 gcc_checking_assert (edge->inline_failed); 328 evaluate_properties_for_edge (edge, true, 329 &clause, &nonspec_clause, 330 &known_vals, &known_contexts, 331 &known_aggs); 332 ipa_call_context ctx (callee, clause, nonspec_clause, known_vals, 333 known_contexts, known_aggs, vNULL); 334 ctx.estimate_size_and_time (&size, NULL, NULL, NULL, NULL); 335 ctx.release (); 336 return size; 337} 338 339 340/* Estimate the growth of the caller when inlining EDGE. 341 Only to be called via estimate_edge_size. */ 342 343ipa_hints 344do_estimate_edge_hints (struct cgraph_edge *edge) 345{ 346 ipa_hints hints; 347 struct cgraph_node *callee; 348 clause_t clause, nonspec_clause; 349 auto_vec<tree, 32> known_vals; 350 auto_vec<ipa_polymorphic_call_context, 32> known_contexts; 351 auto_vec<ipa_agg_value_set, 32> known_aggs; 352 353 /* When we do caching, use do_estimate_edge_time to populate the entry. */ 354 355 if (edge_growth_cache != NULL) 356 { 357 do_estimate_edge_time (edge); 358 hints = edge_growth_cache->get (edge)->hints; 359 gcc_checking_assert (hints); 360 return hints - 1; 361 } 362 363 callee = edge->callee->ultimate_alias_target (); 364 365 /* Early inliner runs without caching, go ahead and do the dirty work. */ 366 gcc_checking_assert (edge->inline_failed); 367 evaluate_properties_for_edge (edge, true, 368 &clause, &nonspec_clause, 369 &known_vals, &known_contexts, 370 &known_aggs); 371 ipa_call_context ctx (callee, clause, nonspec_clause, known_vals, 372 known_contexts, known_aggs, vNULL); 373 ctx.estimate_size_and_time (NULL, NULL, NULL, NULL, &hints); 374 ctx.release (); 375 hints |= simple_edge_hints (edge); 376 return hints; 377} 378 379/* Estimate the size of NODE after inlining EDGE which should be an 380 edge to either NODE or a call inlined into NODE. */ 381 382int 383estimate_size_after_inlining (struct cgraph_node *node, 384 struct cgraph_edge *edge) 385{ 386 class ipa_call_summary *es = ipa_call_summaries->get (edge); 387 ipa_size_summary *s = ipa_size_summaries->get (node); 388 if (!es->predicate || *es->predicate != false) 389 { 390 int size = s->size + estimate_edge_growth (edge); 391 gcc_assert (size >= 0); 392 return size; 393 } 394 return s->size; 395} 396 397 398struct growth_data 399{ 400 struct cgraph_node *node; 401 bool self_recursive; 402 bool uninlinable; 403 int growth; 404 int cap; 405}; 406 407 408/* Worker for do_estimate_growth. Collect growth for all callers. */ 409 410static bool 411do_estimate_growth_1 (struct cgraph_node *node, void *data) 412{ 413 struct cgraph_edge *e; 414 struct growth_data *d = (struct growth_data *) data; 415 416 for (e = node->callers; e; e = e->next_caller) 417 { 418 gcc_checking_assert (e->inline_failed); 419 420 if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR 421 || !opt_for_fn (e->caller->decl, optimize)) 422 { 423 d->uninlinable = true; 424 if (d->cap < INT_MAX) 425 return true; 426 continue; 427 } 428 429 if (e->recursive_p ()) 430 { 431 d->self_recursive = true; 432 if (d->cap < INT_MAX) 433 return true; 434 continue; 435 } 436 d->growth += estimate_edge_growth (e); 437 if (d->growth > d->cap) 438 return true; 439 } 440 return false; 441} 442 443/* Return estimated savings for eliminating offline copy of NODE by inlining 444 it everywhere. */ 445 446static int 447offline_size (struct cgraph_node *node, ipa_size_summary *info) 448{ 449 if (!DECL_EXTERNAL (node->decl)) 450 { 451 if (node->will_be_removed_from_program_if_no_direct_calls_p ()) 452 return info->size; 453 /* COMDAT functions are very often not shared across multiple units 454 since they come from various template instantiations. 455 Take this into account. */ 456 else if (DECL_COMDAT (node->decl) 457 && node->can_remove_if_no_direct_calls_p ()) 458 { 459 int prob = opt_for_fn (node->decl, param_comdat_sharing_probability); 460 return (info->size * (100 - prob) + 50) / 100; 461 } 462 } 463 return 0; 464} 465 466/* Estimate the growth caused by inlining NODE into all callers. */ 467 468int 469estimate_growth (struct cgraph_node *node) 470{ 471 struct growth_data d = { node, false, false, 0, INT_MAX }; 472 ipa_size_summary *info = ipa_size_summaries->get (node); 473 474 if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true)) 475 return 1; 476 477 /* For self recursive functions the growth estimation really should be 478 infinity. We don't want to return very large values because the growth 479 plays various roles in badness computation fractions. Be sure to not 480 return zero or negative growths. */ 481 if (d.self_recursive) 482 d.growth = d.growth < info->size ? info->size : d.growth; 483 else if (!d.uninlinable) 484 d.growth -= offline_size (node, info); 485 486 return d.growth; 487} 488 489/* Verify if there are fewer than MAX_CALLERS. */ 490 491static bool 492check_callers (cgraph_node *node, int *growth, int *n, int offline, 493 int min_size, struct cgraph_edge *known_edge) 494{ 495 ipa_ref *ref; 496 497 if (!node->can_remove_if_no_direct_calls_and_refs_p ()) 498 return true; 499 500 for (cgraph_edge *e = node->callers; e; e = e->next_caller) 501 { 502 edge_growth_cache_entry *entry; 503 504 if (e == known_edge) 505 continue; 506 if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR) 507 return true; 508 if (edge_growth_cache != NULL 509 && (entry = edge_growth_cache->get (e)) != NULL 510 && entry->size != 0) 511 *growth += entry->size - (entry->size > 0); 512 else 513 { 514 class ipa_call_summary *es = ipa_call_summaries->get (e); 515 if (!es) 516 return true; 517 *growth += min_size - es->call_stmt_size; 518 if (--(*n) < 0) 519 return false; 520 } 521 if (*growth > offline) 522 return true; 523 } 524 525 if (*n > 0) 526 FOR_EACH_ALIAS (node, ref) 527 if (check_callers (dyn_cast <cgraph_node *> (ref->referring), growth, n, 528 offline, min_size, known_edge)) 529 return true; 530 531 return false; 532} 533 534 535/* Decide if growth of NODE is positive. This is cheaper than calculating 536 actual growth. If edge growth of KNOWN_EDGE is known 537 it is passed by EDGE_GROWTH. */ 538 539bool 540growth_positive_p (struct cgraph_node *node, 541 struct cgraph_edge * known_edge, int edge_growth) 542{ 543 struct cgraph_edge *e; 544 545 ipa_size_summary *s = ipa_size_summaries->get (node); 546 547 /* First quickly check if NODE is removable at all. */ 548 int offline = offline_size (node, s); 549 if (offline <= 0 && known_edge && edge_growth > 0) 550 return true; 551 552 int min_size = ipa_fn_summaries->get (node)->min_size; 553 int n = 10; 554 555 int min_growth = known_edge ? edge_growth : 0; 556 for (e = node->callers; e; e = e->next_caller) 557 { 558 edge_growth_cache_entry *entry; 559 560 if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR) 561 return true; 562 if (e == known_edge) 563 continue; 564 if (edge_growth_cache != NULL 565 && (entry = edge_growth_cache->get (e)) != NULL 566 && entry->size != 0) 567 min_growth += entry->size - (entry->size > 0); 568 else 569 { 570 class ipa_call_summary *es = ipa_call_summaries->get (e); 571 if (!es) 572 return true; 573 min_growth += min_size - es->call_stmt_size; 574 if (--n <= 0) 575 break; 576 } 577 if (min_growth > offline) 578 return true; 579 } 580 581 ipa_ref *ref; 582 if (n > 0) 583 FOR_EACH_ALIAS (node, ref) 584 if (check_callers (dyn_cast <cgraph_node *> (ref->referring), 585 &min_growth, &n, offline, min_size, known_edge)) 586 return true; 587 588 struct growth_data d = { node, false, false, 0, offline }; 589 if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true)) 590 return true; 591 if (d.self_recursive || d.uninlinable) 592 return true; 593 return (d.growth > offline); 594} 595