1 /* Inlining decision heuristics. 2 Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010, 2011 3 Free Software Foundation, Inc. 4 Contributed by Jan Hubicka 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free 10 Software Foundation; either version 3, or (at your option) any later 11 version. 12 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16 for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 /* Analysis used by the inliner and other passes limiting code size growth. 23 24 We estimate for each function 25 - function body size 26 - average function execution time 27 - inlining size benefit (that is how much of function body size 28 and its call sequence is expected to disappear by inlining) 29 - inlining time benefit 30 - function frame size 31 For each call 32 - call statement size and time 33 34 inlinie_summary datastructures store above information locally (i.e. 35 parameters of the function itself) and globally (i.e. parameters of 36 the function created by applying all the inline decisions already 37 present in the callgraph). 38 39 We provide accestor to the inline_summary datastructure and 40 basic logic updating the parameters when inlining is performed. 41 42 The summaries are context sensitive. Context means 43 1) partial assignment of known constant values of operands 44 2) whether function is inlined into the call or not. 45 It is easy to add more variants. To represent function size and time 46 that depends on context (i.e. it is known to be optimized away when 47 context is known either by inlining or from IP-CP and clonning), 48 we use predicates. Predicates are logical formulas in 49 conjunctive-disjunctive form consisting of clauses. Clauses are bitmaps 50 specifying what conditions must be true. Conditions are simple test 51 of the form described above. 52 53 In order to make predicate (possibly) true, all of its clauses must 54 be (possibly) true. To make clause (possibly) true, one of conditions 55 it mentions must be (possibly) true. There are fixed bounds on 56 number of clauses and conditions and all the manipulation functions 57 are conservative in positive direction. I.e. we may lose precision 58 by thinking that predicate may be true even when it is not. 59 60 estimate_edge_size and estimate_edge_growth can be used to query 61 function size/time in the given context. inline_merge_summary merges 62 properties of caller and callee after inlining. 63 64 Finally pass_inline_parameters is exported. This is used to drive 65 computation of function parameters used by the early inliner. IPA 66 inlined performs analysis via its analyze_function method. */ 67 68 #include "config.h" 69 #include "system.h" 70 #include "coretypes.h" 71 #include "tm.h" 72 #include "tree.h" 73 #include "tree-inline.h" 74 #include "langhooks.h" 75 #include "flags.h" 76 #include "cgraph.h" 77 #include "diagnostic.h" 78 #include "gimple-pretty-print.h" 79 #include "timevar.h" 80 #include "params.h" 81 #include "tree-pass.h" 82 #include "coverage.h" 83 #include "ggc.h" 84 #include "tree-flow.h" 85 #include "ipa-prop.h" 86 #include "lto-streamer.h" 87 #include "data-streamer.h" 88 #include "tree-streamer.h" 89 #include "ipa-inline.h" 90 #include "alloc-pool.h" 91 92 /* Estimate runtime of function can easilly run into huge numbers with many 93 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an 94 integer. For anything larger we use gcov_type. */ 95 #define MAX_TIME 500000 96 97 /* Number of bits in integer, but we really want to be stable across different 98 hosts. */ 99 #define NUM_CONDITIONS 32 100 101 enum predicate_conditions 102 { 103 predicate_false_condition = 0, 104 predicate_not_inlined_condition = 1, 105 predicate_first_dynamic_condition = 2 106 }; 107 108 /* Special condition code we use to represent test that operand is compile time 109 constant. */ 110 #define IS_NOT_CONSTANT ERROR_MARK 111 /* Special condition code we use to represent test that operand is not changed 112 across invocation of the function. When operand IS_NOT_CONSTANT it is always 113 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage 114 of executions even when they are not compile time constants. */ 115 #define CHANGED IDENTIFIER_NODE 116 117 /* Holders of ipa cgraph hooks: */ 118 static struct cgraph_node_hook_list *function_insertion_hook_holder; 119 static struct cgraph_node_hook_list *node_removal_hook_holder; 120 static struct cgraph_2node_hook_list *node_duplication_hook_holder; 121 static struct cgraph_2edge_hook_list *edge_duplication_hook_holder; 122 static struct cgraph_edge_hook_list *edge_removal_hook_holder; 123 static void inline_node_removal_hook (struct cgraph_node *, void *); 124 static void inline_node_duplication_hook (struct cgraph_node *, 125 struct cgraph_node *, void *); 126 static void inline_edge_removal_hook (struct cgraph_edge *, void *); 127 static void inline_edge_duplication_hook (struct cgraph_edge *, 128 struct cgraph_edge *, 129 void *); 130 131 /* VECtor holding inline summaries. 132 In GGC memory because conditions might point to constant trees. */ 133 VEC(inline_summary_t,gc) *inline_summary_vec; 134 VEC(inline_edge_summary_t,heap) *inline_edge_summary_vec; 135 136 /* Cached node/edge growths. */ 137 VEC(int,heap) *node_growth_cache; 138 VEC(edge_growth_cache_entry,heap) *edge_growth_cache; 139 140 /* Edge predicates goes here. */ 141 static alloc_pool edge_predicate_pool; 142 143 /* Return true predicate (tautology). 144 We represent it by empty list of clauses. */ 145 146 static inline struct predicate 147 true_predicate (void) 148 { 149 struct predicate p; 150 p.clause[0]=0; 151 return p; 152 } 153 154 155 /* Return predicate testing single condition number COND. */ 156 157 static inline struct predicate 158 single_cond_predicate (int cond) 159 { 160 struct predicate p; 161 p.clause[0]=1 << cond; 162 p.clause[1]=0; 163 return p; 164 } 165 166 167 /* Return false predicate. First clause require false condition. */ 168 169 static inline struct predicate 170 false_predicate (void) 171 { 172 return single_cond_predicate (predicate_false_condition); 173 } 174 175 176 /* Return true if P is (false). */ 177 178 static inline bool 179 true_predicate_p (struct predicate *p) 180 { 181 return !p->clause[0]; 182 } 183 184 185 /* Return true if P is (false). */ 186 187 static inline bool 188 false_predicate_p (struct predicate *p) 189 { 190 if (p->clause[0] == (1 << predicate_false_condition)) 191 { 192 gcc_checking_assert (!p->clause[1] 193 && p->clause[0] == 1 << predicate_false_condition); 194 return true; 195 } 196 return false; 197 } 198 199 200 /* Return predicate that is set true when function is not inlined. */ 201 static inline struct predicate 202 not_inlined_predicate (void) 203 { 204 return single_cond_predicate (predicate_not_inlined_condition); 205 } 206 207 208 /* Add condition to condition list CONDS. */ 209 210 static struct predicate 211 add_condition (struct inline_summary *summary, int operand_num, 212 enum tree_code code, tree val) 213 { 214 int i; 215 struct condition *c; 216 struct condition new_cond; 217 218 for (i = 0; VEC_iterate (condition, summary->conds, i, c); i++) 219 { 220 if (c->operand_num == operand_num 221 && c->code == code 222 && c->val == val) 223 return single_cond_predicate (i + predicate_first_dynamic_condition); 224 } 225 /* Too many conditions. Give up and return constant true. */ 226 if (i == NUM_CONDITIONS - predicate_first_dynamic_condition) 227 return true_predicate (); 228 229 new_cond.operand_num = operand_num; 230 new_cond.code = code; 231 new_cond.val = val; 232 VEC_safe_push (condition, gc, summary->conds, &new_cond); 233 return single_cond_predicate (i + predicate_first_dynamic_condition); 234 } 235 236 237 /* Add clause CLAUSE into the predicate P. */ 238 239 static inline void 240 add_clause (conditions conditions, struct predicate *p, clause_t clause) 241 { 242 int i; 243 int i2; 244 int insert_here = -1; 245 int c1, c2; 246 247 /* True clause. */ 248 if (!clause) 249 return; 250 251 /* False clause makes the whole predicate false. Kill the other variants. */ 252 if (clause == (1 << predicate_false_condition)) 253 { 254 p->clause[0] = (1 << predicate_false_condition); 255 p->clause[1] = 0; 256 return; 257 } 258 if (false_predicate_p (p)) 259 return; 260 261 /* No one should be sily enough to add false into nontrivial clauses. */ 262 gcc_checking_assert (!(clause & (1 << predicate_false_condition))); 263 264 /* Look where to insert the clause. At the same time prune out 265 clauses of P that are implied by the new clause and thus 266 redundant. */ 267 for (i = 0, i2 = 0; i <= MAX_CLAUSES; i++) 268 { 269 p->clause[i2] = p->clause[i]; 270 271 if (!p->clause[i]) 272 break; 273 274 /* If p->clause[i] implies clause, there is nothing to add. */ 275 if ((p->clause[i] & clause) == p->clause[i]) 276 { 277 /* We had nothing to add, none of clauses should've become 278 redundant. */ 279 gcc_checking_assert (i == i2); 280 return; 281 } 282 283 if (p->clause[i] < clause && insert_here < 0) 284 insert_here = i2; 285 286 /* If clause implies p->clause[i], then p->clause[i] becomes redundant. 287 Otherwise the p->clause[i] has to stay. */ 288 if ((p->clause[i] & clause) != clause) 289 i2++; 290 } 291 292 /* Look for clauses that are obviously true. I.e. 293 op0 == 5 || op0 != 5. */ 294 for (c1 = predicate_first_dynamic_condition; c1 < NUM_CONDITIONS; c1++) 295 { 296 condition *cc1; 297 if (!(clause & (1 << c1))) 298 continue; 299 cc1 = VEC_index (condition, 300 conditions, 301 c1 - predicate_first_dynamic_condition); 302 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT 303 and thus there is no point for looking for them. */ 304 if (cc1->code == CHANGED 305 || cc1->code == IS_NOT_CONSTANT) 306 continue; 307 for (c2 = c1 + 1; c2 <= NUM_CONDITIONS; c2++) 308 if (clause & (1 << c2)) 309 { 310 condition *cc1 = VEC_index (condition, 311 conditions, 312 c1 - predicate_first_dynamic_condition); 313 condition *cc2 = VEC_index (condition, 314 conditions, 315 c2 - predicate_first_dynamic_condition); 316 if (cc1->operand_num == cc2->operand_num 317 && cc1->val == cc2->val 318 && cc2->code != IS_NOT_CONSTANT 319 && cc2->code != CHANGED 320 && cc1->code == invert_tree_comparison 321 (cc2->code, 322 HONOR_NANS (TYPE_MODE (TREE_TYPE (cc1->val))))) 323 return; 324 } 325 } 326 327 328 /* We run out of variants. Be conservative in positive direction. */ 329 if (i2 == MAX_CLAUSES) 330 return; 331 /* Keep clauses in decreasing order. This makes equivalence testing easy. */ 332 p->clause[i2 + 1] = 0; 333 if (insert_here >= 0) 334 for (;i2 > insert_here; i2--) 335 p->clause[i2] = p->clause[i2 - 1]; 336 else 337 insert_here = i2; 338 p->clause[insert_here] = clause; 339 } 340 341 342 /* Return P & P2. */ 343 344 static struct predicate 345 and_predicates (conditions conditions, 346 struct predicate *p, struct predicate *p2) 347 { 348 struct predicate out = *p; 349 int i; 350 351 /* Avoid busy work. */ 352 if (false_predicate_p (p2) || true_predicate_p (p)) 353 return *p2; 354 if (false_predicate_p (p) || true_predicate_p (p2)) 355 return *p; 356 357 /* See how far predicates match. */ 358 for (i = 0; p->clause[i] && p->clause[i] == p2->clause[i]; i++) 359 { 360 gcc_checking_assert (i < MAX_CLAUSES); 361 } 362 363 /* Combine the predicates rest. */ 364 for (; p2->clause[i]; i++) 365 { 366 gcc_checking_assert (i < MAX_CLAUSES); 367 add_clause (conditions, &out, p2->clause[i]); 368 } 369 return out; 370 } 371 372 373 /* Return true if predicates are obviously equal. */ 374 375 static inline bool 376 predicates_equal_p (struct predicate *p, struct predicate *p2) 377 { 378 int i; 379 for (i = 0; p->clause[i]; i++) 380 { 381 gcc_checking_assert (i < MAX_CLAUSES); 382 gcc_checking_assert (p->clause [i] > p->clause[i + 1]); 383 gcc_checking_assert (!p2->clause[i] 384 || p2->clause [i] > p2->clause[i + 1]); 385 if (p->clause[i] != p2->clause[i]) 386 return false; 387 } 388 return !p2->clause[i]; 389 } 390 391 392 /* Return P | P2. */ 393 394 static struct predicate 395 or_predicates (conditions conditions, struct predicate *p, struct predicate *p2) 396 { 397 struct predicate out = true_predicate (); 398 int i,j; 399 400 /* Avoid busy work. */ 401 if (false_predicate_p (p2) || true_predicate_p (p)) 402 return *p; 403 if (false_predicate_p (p) || true_predicate_p (p2)) 404 return *p2; 405 if (predicates_equal_p (p, p2)) 406 return *p; 407 408 /* OK, combine the predicates. */ 409 for (i = 0; p->clause[i]; i++) 410 for (j = 0; p2->clause[j]; j++) 411 { 412 gcc_checking_assert (i < MAX_CLAUSES && j < MAX_CLAUSES); 413 add_clause (conditions, &out, p->clause[i] | p2->clause[j]); 414 } 415 return out; 416 } 417 418 419 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false 420 if predicate P is known to be false. */ 421 422 static bool 423 evaluate_predicate (struct predicate *p, clause_t possible_truths) 424 { 425 int i; 426 427 /* True remains true. */ 428 if (true_predicate_p (p)) 429 return true; 430 431 gcc_assert (!(possible_truths & (1 << predicate_false_condition))); 432 433 /* See if we can find clause we can disprove. */ 434 for (i = 0; p->clause[i]; i++) 435 { 436 gcc_checking_assert (i < MAX_CLAUSES); 437 if (!(p->clause[i] & possible_truths)) 438 return false; 439 } 440 return true; 441 } 442 443 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated 444 instruction will be recomputed per invocation of the inlined call. */ 445 446 static int 447 predicate_probability (conditions conds, 448 struct predicate *p, clause_t possible_truths, 449 VEC (inline_param_summary_t, heap) *inline_param_summary) 450 { 451 int i; 452 int combined_prob = REG_BR_PROB_BASE; 453 454 /* True remains true. */ 455 if (true_predicate_p (p)) 456 return REG_BR_PROB_BASE; 457 458 if (false_predicate_p (p)) 459 return 0; 460 461 gcc_assert (!(possible_truths & (1 << predicate_false_condition))); 462 463 /* See if we can find clause we can disprove. */ 464 for (i = 0; p->clause[i]; i++) 465 { 466 gcc_checking_assert (i < MAX_CLAUSES); 467 if (!(p->clause[i] & possible_truths)) 468 return 0; 469 else 470 { 471 int this_prob = 0; 472 int i2; 473 if (!inline_param_summary) 474 return REG_BR_PROB_BASE; 475 for (i2 = 0; i2 < NUM_CONDITIONS; i2++) 476 if ((p->clause[i] & possible_truths) & (1 << i2)) 477 { 478 if (i2 >= predicate_first_dynamic_condition) 479 { 480 condition *c = VEC_index 481 (condition, conds, 482 i2 - predicate_first_dynamic_condition); 483 if (c->code == CHANGED 484 && (c->operand_num 485 < (int) VEC_length (inline_param_summary_t, 486 inline_param_summary))) 487 { 488 int iprob = VEC_index (inline_param_summary_t, 489 inline_param_summary, 490 c->operand_num)->change_prob; 491 this_prob = MAX (this_prob, iprob); 492 } 493 else 494 this_prob = REG_BR_PROB_BASE; 495 } 496 else 497 this_prob = REG_BR_PROB_BASE; 498 } 499 combined_prob = MIN (this_prob, combined_prob); 500 if (!combined_prob) 501 return 0; 502 } 503 } 504 return combined_prob; 505 } 506 507 508 /* Dump conditional COND. */ 509 510 static void 511 dump_condition (FILE *f, conditions conditions, int cond) 512 { 513 condition *c; 514 if (cond == predicate_false_condition) 515 fprintf (f, "false"); 516 else if (cond == predicate_not_inlined_condition) 517 fprintf (f, "not inlined"); 518 else 519 { 520 c = VEC_index (condition, conditions, 521 cond - predicate_first_dynamic_condition); 522 fprintf (f, "op%i", c->operand_num); 523 if (c->code == IS_NOT_CONSTANT) 524 { 525 fprintf (f, " not constant"); 526 return; 527 } 528 if (c->code == CHANGED) 529 { 530 fprintf (f, " changed"); 531 return; 532 } 533 fprintf (f, " %s ", op_symbol_code (c->code)); 534 print_generic_expr (f, c->val, 1); 535 } 536 } 537 538 539 /* Dump clause CLAUSE. */ 540 541 static void 542 dump_clause (FILE *f, conditions conds, clause_t clause) 543 { 544 int i; 545 bool found = false; 546 fprintf (f, "("); 547 if (!clause) 548 fprintf (f, "true"); 549 for (i = 0; i < NUM_CONDITIONS; i++) 550 if (clause & (1 << i)) 551 { 552 if (found) 553 fprintf (f, " || "); 554 found = true; 555 dump_condition (f, conds, i); 556 } 557 fprintf (f, ")"); 558 } 559 560 561 /* Dump predicate PREDICATE. */ 562 563 static void 564 dump_predicate (FILE *f, conditions conds, struct predicate *pred) 565 { 566 int i; 567 if (true_predicate_p (pred)) 568 dump_clause (f, conds, 0); 569 else 570 for (i = 0; pred->clause[i]; i++) 571 { 572 if (i) 573 fprintf (f, " && "); 574 dump_clause (f, conds, pred->clause[i]); 575 } 576 fprintf (f, "\n"); 577 } 578 579 580 /* Record SIZE and TIME under condition PRED into the inline summary. */ 581 582 static void 583 account_size_time (struct inline_summary *summary, int size, int time, 584 struct predicate *pred) 585 { 586 size_time_entry *e; 587 bool found = false; 588 int i; 589 590 if (false_predicate_p (pred)) 591 return; 592 593 /* We need to create initial empty unconitional clause, but otherwie 594 we don't need to account empty times and sizes. */ 595 if (!size && !time && summary->entry) 596 return; 597 598 /* Watch overflow that might result from insane profiles. */ 599 if (time > MAX_TIME * INLINE_TIME_SCALE) 600 time = MAX_TIME * INLINE_TIME_SCALE; 601 gcc_assert (time >= 0); 602 603 for (i = 0; VEC_iterate (size_time_entry, summary->entry, i, e); i++) 604 if (predicates_equal_p (&e->predicate, pred)) 605 { 606 found = true; 607 break; 608 } 609 if (i == 32) 610 { 611 i = 0; 612 found = true; 613 e = VEC_index (size_time_entry, summary->entry, 0); 614 gcc_assert (!e->predicate.clause[0]); 615 } 616 if (dump_file && (dump_flags & TDF_DETAILS) && (time || size)) 617 { 618 fprintf (dump_file, "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:", 619 ((double)size) / INLINE_SIZE_SCALE, 620 ((double)time) / INLINE_TIME_SCALE, 621 found ? "" : "new "); 622 dump_predicate (dump_file, summary->conds, pred); 623 } 624 if (!found) 625 { 626 struct size_time_entry new_entry; 627 new_entry.size = size; 628 new_entry.time = time; 629 new_entry.predicate = *pred; 630 VEC_safe_push (size_time_entry, gc, summary->entry, &new_entry); 631 } 632 else 633 { 634 e->size += size; 635 e->time += time; 636 if (e->time > MAX_TIME * INLINE_TIME_SCALE) 637 e->time = MAX_TIME * INLINE_TIME_SCALE; 638 } 639 } 640 641 /* Set predicate for edge E. */ 642 643 static void 644 edge_set_predicate (struct cgraph_edge *e, struct predicate *predicate) 645 { 646 struct inline_edge_summary *es = inline_edge_summary (e); 647 if (predicate && !true_predicate_p (predicate)) 648 { 649 if (!es->predicate) 650 es->predicate = (struct predicate *)pool_alloc (edge_predicate_pool); 651 *es->predicate = *predicate; 652 } 653 else 654 { 655 if (es->predicate) 656 pool_free (edge_predicate_pool, es->predicate); 657 es->predicate = NULL; 658 } 659 } 660 661 662 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values. 663 Return clause of possible truths. When INLINE_P is true, assume that 664 we are inlining. 665 666 ERROR_MARK means compile time invariant. */ 667 668 static clause_t 669 evaluate_conditions_for_known_args (struct cgraph_node *node, 670 bool inline_p, 671 VEC (tree, heap) *known_vals) 672 { 673 clause_t clause = inline_p ? 0 : 1 << predicate_not_inlined_condition; 674 struct inline_summary *info = inline_summary (node); 675 int i; 676 struct condition *c; 677 678 for (i = 0; VEC_iterate (condition, info->conds, i, c); i++) 679 { 680 tree val; 681 tree res; 682 683 /* We allow call stmt to have fewer arguments than the callee 684 function (especially for K&R style programs). So bound 685 check here. */ 686 if (c->operand_num < (int)VEC_length (tree, known_vals)) 687 val = VEC_index (tree, known_vals, c->operand_num); 688 else 689 val = NULL; 690 691 if (val == error_mark_node && c->code != CHANGED) 692 val = NULL; 693 694 if (!val) 695 { 696 clause |= 1 << (i + predicate_first_dynamic_condition); 697 continue; 698 } 699 if (c->code == IS_NOT_CONSTANT || c->code == CHANGED) 700 continue; 701 res = fold_binary_to_constant (c->code, boolean_type_node, val, c->val); 702 if (res 703 && integer_zerop (res)) 704 continue; 705 clause |= 1 << (i + predicate_first_dynamic_condition); 706 } 707 return clause; 708 } 709 710 711 /* Work out what conditions might be true at invocation of E. */ 712 713 static void 714 evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p, 715 clause_t *clause_ptr, 716 VEC (tree, heap) **known_vals_ptr, 717 VEC (tree, heap) **known_binfos_ptr) 718 { 719 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL); 720 struct inline_summary *info = inline_summary (callee); 721 VEC (tree, heap) *known_vals = NULL; 722 723 if (clause_ptr) 724 *clause_ptr = inline_p ? 0 : 1 << predicate_not_inlined_condition; 725 if (known_vals_ptr) 726 *known_vals_ptr = NULL; 727 if (known_binfos_ptr) 728 *known_binfos_ptr = NULL; 729 730 if (ipa_node_params_vector 731 && !e->call_stmt_cannot_inline_p 732 && ((clause_ptr && info->conds) || known_vals_ptr || known_binfos_ptr)) 733 { 734 struct ipa_node_params *parms_info; 735 struct ipa_edge_args *args = IPA_EDGE_REF (e); 736 struct inline_edge_summary *es = inline_edge_summary (e); 737 int i, count = ipa_get_cs_argument_count (args); 738 739 if (e->caller->global.inlined_to) 740 parms_info = IPA_NODE_REF (e->caller->global.inlined_to); 741 else 742 parms_info = IPA_NODE_REF (e->caller); 743 744 if (count && (info->conds || known_vals_ptr)) 745 VEC_safe_grow_cleared (tree, heap, known_vals, count); 746 if (count && known_binfos_ptr) 747 VEC_safe_grow_cleared (tree, heap, *known_binfos_ptr, count); 748 749 for (i = 0; i < count; i++) 750 { 751 tree cst = ipa_value_from_jfunc (parms_info, 752 ipa_get_ith_jump_func (args, i)); 753 if (cst) 754 { 755 if (known_vals && TREE_CODE (cst) != TREE_BINFO) 756 VEC_replace (tree, known_vals, i, cst); 757 else if (known_binfos_ptr != NULL && TREE_CODE (cst) == TREE_BINFO) 758 VEC_replace (tree, *known_binfos_ptr, i, cst); 759 } 760 else if (inline_p 761 && !VEC_index (inline_param_summary_t, 762 es->param, 763 i)->change_prob) 764 VEC_replace (tree, known_vals, i, error_mark_node); 765 } 766 } 767 768 if (clause_ptr) 769 *clause_ptr = evaluate_conditions_for_known_args (callee, inline_p, 770 known_vals); 771 772 if (known_vals_ptr) 773 *known_vals_ptr = known_vals; 774 else 775 VEC_free (tree, heap, known_vals); 776 } 777 778 779 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */ 780 781 static void 782 inline_summary_alloc (void) 783 { 784 if (!node_removal_hook_holder) 785 node_removal_hook_holder = 786 cgraph_add_node_removal_hook (&inline_node_removal_hook, NULL); 787 if (!edge_removal_hook_holder) 788 edge_removal_hook_holder = 789 cgraph_add_edge_removal_hook (&inline_edge_removal_hook, NULL); 790 if (!node_duplication_hook_holder) 791 node_duplication_hook_holder = 792 cgraph_add_node_duplication_hook (&inline_node_duplication_hook, NULL); 793 if (!edge_duplication_hook_holder) 794 edge_duplication_hook_holder = 795 cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook, NULL); 796 797 if (VEC_length (inline_summary_t, inline_summary_vec) 798 <= (unsigned) cgraph_max_uid) 799 VEC_safe_grow_cleared (inline_summary_t, gc, 800 inline_summary_vec, cgraph_max_uid + 1); 801 if (VEC_length (inline_edge_summary_t, inline_edge_summary_vec) 802 <= (unsigned) cgraph_edge_max_uid) 803 VEC_safe_grow_cleared (inline_edge_summary_t, heap, 804 inline_edge_summary_vec, cgraph_edge_max_uid + 1); 805 if (!edge_predicate_pool) 806 edge_predicate_pool = create_alloc_pool ("edge predicates", 807 sizeof (struct predicate), 808 10); 809 } 810 811 /* We are called multiple time for given function; clear 812 data from previous run so they are not cumulated. */ 813 814 static void 815 reset_inline_edge_summary (struct cgraph_edge *e) 816 { 817 if (e->uid 818 < (int)VEC_length (inline_edge_summary_t, inline_edge_summary_vec)) 819 { 820 struct inline_edge_summary *es = inline_edge_summary (e); 821 822 es->call_stmt_size = es->call_stmt_time =0; 823 if (es->predicate) 824 pool_free (edge_predicate_pool, es->predicate); 825 es->predicate = NULL; 826 VEC_free (inline_param_summary_t, heap, es->param); 827 } 828 } 829 830 /* We are called multiple time for given function; clear 831 data from previous run so they are not cumulated. */ 832 833 static void 834 reset_inline_summary (struct cgraph_node *node) 835 { 836 struct inline_summary *info = inline_summary (node); 837 struct cgraph_edge *e; 838 839 info->self_size = info->self_time = 0; 840 info->estimated_stack_size = 0; 841 info->estimated_self_stack_size = 0; 842 info->stack_frame_offset = 0; 843 info->size = 0; 844 info->time = 0; 845 VEC_free (condition, gc, info->conds); 846 VEC_free (size_time_entry,gc, info->entry); 847 for (e = node->callees; e; e = e->next_callee) 848 reset_inline_edge_summary (e); 849 for (e = node->indirect_calls; e; e = e->next_callee) 850 reset_inline_edge_summary (e); 851 } 852 853 /* Hook that is called by cgraph.c when a node is removed. */ 854 855 static void 856 inline_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED) 857 { 858 struct inline_summary *info; 859 if (VEC_length (inline_summary_t, inline_summary_vec) 860 <= (unsigned)node->uid) 861 return; 862 info = inline_summary (node); 863 reset_inline_summary (node); 864 memset (info, 0, sizeof (inline_summary_t)); 865 } 866 867 868 /* Hook that is called by cgraph.c when a node is duplicated. */ 869 870 static void 871 inline_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst, 872 ATTRIBUTE_UNUSED void *data) 873 { 874 struct inline_summary *info; 875 inline_summary_alloc (); 876 info = inline_summary (dst); 877 memcpy (info, inline_summary (src), 878 sizeof (struct inline_summary)); 879 /* TODO: as an optimization, we may avoid copying conditions 880 that are known to be false or true. */ 881 info->conds = VEC_copy (condition, gc, info->conds); 882 883 /* When there are any replacements in the function body, see if we can figure 884 out that something was optimized out. */ 885 if (ipa_node_params_vector && dst->clone.tree_map) 886 { 887 VEC(size_time_entry,gc) *entry = info->entry; 888 /* Use SRC parm info since it may not be copied yet. */ 889 struct ipa_node_params *parms_info = IPA_NODE_REF (src); 890 VEC (tree, heap) *known_vals = NULL; 891 int count = ipa_get_param_count (parms_info); 892 int i,j; 893 clause_t possible_truths; 894 struct predicate true_pred = true_predicate (); 895 size_time_entry *e; 896 int optimized_out_size = 0; 897 gcov_type optimized_out_time = 0; 898 bool inlined_to_p = false; 899 struct cgraph_edge *edge; 900 901 info->entry = 0; 902 VEC_safe_grow_cleared (tree, heap, known_vals, count); 903 for (i = 0; i < count; i++) 904 { 905 tree t = ipa_get_param (parms_info, i); 906 struct ipa_replace_map *r; 907 908 for (j = 0; 909 VEC_iterate (ipa_replace_map_p, dst->clone.tree_map, j, r); 910 j++) 911 { 912 if (r->old_tree == t 913 && r->replace_p 914 && !r->ref_p) 915 { 916 VEC_replace (tree, known_vals, i, r->new_tree); 917 break; 918 } 919 } 920 } 921 possible_truths = evaluate_conditions_for_known_args (dst, 922 false, known_vals); 923 VEC_free (tree, heap, known_vals); 924 925 account_size_time (info, 0, 0, &true_pred); 926 927 /* Remap size_time vectors. 928 Simplify the predicate by prunning out alternatives that are known 929 to be false. 930 TODO: as on optimization, we can also eliminate conditions known 931 to be true. */ 932 for (i = 0; VEC_iterate (size_time_entry, entry, i, e); i++) 933 { 934 struct predicate new_predicate = true_predicate (); 935 for (j = 0; e->predicate.clause[j]; j++) 936 if (!(possible_truths & e->predicate.clause[j])) 937 { 938 new_predicate = false_predicate (); 939 break; 940 } 941 else 942 add_clause (info->conds, &new_predicate, 943 possible_truths & e->predicate.clause[j]); 944 if (false_predicate_p (&new_predicate)) 945 { 946 optimized_out_size += e->size; 947 optimized_out_time += e->time; 948 } 949 else 950 account_size_time (info, e->size, e->time, &new_predicate); 951 } 952 953 /* Remap edge predicates with the same simplification as above. 954 Also copy constantness arrays. */ 955 for (edge = dst->callees; edge; edge = edge->next_callee) 956 { 957 struct predicate new_predicate = true_predicate (); 958 struct inline_edge_summary *es = inline_edge_summary (edge); 959 960 if (!edge->inline_failed) 961 inlined_to_p = true; 962 if (!es->predicate) 963 continue; 964 for (j = 0; es->predicate->clause[j]; j++) 965 if (!(possible_truths & es->predicate->clause[j])) 966 { 967 new_predicate = false_predicate (); 968 break; 969 } 970 else 971 add_clause (info->conds, &new_predicate, 972 possible_truths & es->predicate->clause[j]); 973 if (false_predicate_p (&new_predicate) 974 && !false_predicate_p (es->predicate)) 975 { 976 optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE; 977 optimized_out_time += (es->call_stmt_time 978 * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE) 979 * edge->frequency); 980 edge->frequency = 0; 981 } 982 *es->predicate = new_predicate; 983 } 984 985 /* Remap indirect edge predicates with the same simplificaiton as above. 986 Also copy constantness arrays. */ 987 for (edge = dst->indirect_calls; edge; edge = edge->next_callee) 988 { 989 struct predicate new_predicate = true_predicate (); 990 struct inline_edge_summary *es = inline_edge_summary (edge); 991 992 if (!edge->inline_failed) 993 inlined_to_p = true; 994 if (!es->predicate) 995 continue; 996 for (j = 0; es->predicate->clause[j]; j++) 997 if (!(possible_truths & es->predicate->clause[j])) 998 { 999 new_predicate = false_predicate (); 1000 break; 1001 } 1002 else 1003 add_clause (info->conds, &new_predicate, 1004 possible_truths & es->predicate->clause[j]); 1005 if (false_predicate_p (&new_predicate) 1006 && !false_predicate_p (es->predicate)) 1007 { 1008 optimized_out_size += es->call_stmt_size * INLINE_SIZE_SCALE; 1009 optimized_out_time += (es->call_stmt_time 1010 * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE) 1011 * edge->frequency); 1012 edge->frequency = 0; 1013 } 1014 *es->predicate = new_predicate; 1015 } 1016 1017 /* If inliner or someone after inliner will ever start producing 1018 non-trivial clones, we will get trouble with lack of information 1019 about updating self sizes, because size vectors already contains 1020 sizes of the calees. */ 1021 gcc_assert (!inlined_to_p 1022 || (!optimized_out_size && !optimized_out_time)); 1023 1024 info->size -= optimized_out_size / INLINE_SIZE_SCALE; 1025 info->self_size -= optimized_out_size / INLINE_SIZE_SCALE; 1026 gcc_assert (info->size > 0); 1027 gcc_assert (info->self_size > 0); 1028 1029 optimized_out_time /= INLINE_TIME_SCALE; 1030 if (optimized_out_time > MAX_TIME) 1031 optimized_out_time = MAX_TIME; 1032 info->time -= optimized_out_time; 1033 info->self_time -= optimized_out_time; 1034 if (info->time < 0) 1035 info->time = 0; 1036 if (info->self_time < 0) 1037 info->self_time = 0; 1038 } 1039 else 1040 info->entry = VEC_copy (size_time_entry, gc, info->entry); 1041 } 1042 1043 1044 /* Hook that is called by cgraph.c when a node is duplicated. */ 1045 1046 static void 1047 inline_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst, 1048 ATTRIBUTE_UNUSED void *data) 1049 { 1050 struct inline_edge_summary *info; 1051 struct inline_edge_summary *srcinfo; 1052 inline_summary_alloc (); 1053 info = inline_edge_summary (dst); 1054 srcinfo = inline_edge_summary (src); 1055 memcpy (info, srcinfo, 1056 sizeof (struct inline_edge_summary)); 1057 info->predicate = NULL; 1058 edge_set_predicate (dst, srcinfo->predicate); 1059 info->param = VEC_copy (inline_param_summary_t, heap, srcinfo->param); 1060 } 1061 1062 1063 /* Keep edge cache consistent across edge removal. */ 1064 1065 static void 1066 inline_edge_removal_hook (struct cgraph_edge *edge, void *data ATTRIBUTE_UNUSED) 1067 { 1068 if (edge_growth_cache) 1069 reset_edge_growth_cache (edge); 1070 reset_inline_edge_summary (edge); 1071 } 1072 1073 1074 /* Initialize growth caches. */ 1075 1076 void 1077 initialize_growth_caches (void) 1078 { 1079 if (cgraph_edge_max_uid) 1080 VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache, 1081 cgraph_edge_max_uid); 1082 if (cgraph_max_uid) 1083 VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid); 1084 } 1085 1086 1087 /* Free growth caches. */ 1088 1089 void 1090 free_growth_caches (void) 1091 { 1092 VEC_free (edge_growth_cache_entry, heap, edge_growth_cache); 1093 edge_growth_cache = 0; 1094 VEC_free (int, heap, node_growth_cache); 1095 node_growth_cache = 0; 1096 } 1097 1098 1099 /* Dump edge summaries associated to NODE and recursively to all clones. 1100 Indent by INDENT. */ 1101 1102 static void 1103 dump_inline_edge_summary (FILE * f, int indent, struct cgraph_node *node, 1104 struct inline_summary *info) 1105 { 1106 struct cgraph_edge *edge; 1107 for (edge = node->callees; edge; edge = edge->next_callee) 1108 { 1109 struct inline_edge_summary *es = inline_edge_summary (edge); 1110 struct cgraph_node *callee = cgraph_function_or_thunk_node (edge->callee, NULL); 1111 int i; 1112 1113 fprintf (f, "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i time: %2i callee size:%2i stack:%2i", 1114 indent, "", cgraph_node_name (callee), 1115 callee->uid, 1116 !edge->inline_failed ? "inlined" 1117 : cgraph_inline_failed_string (edge->inline_failed), 1118 indent, "", 1119 es->loop_depth, 1120 edge->frequency, 1121 es->call_stmt_size, 1122 es->call_stmt_time, 1123 (int)inline_summary (callee)->size / INLINE_SIZE_SCALE, 1124 (int)inline_summary (callee)->estimated_stack_size); 1125 1126 if (es->predicate) 1127 { 1128 fprintf (f, " predicate: "); 1129 dump_predicate (f, info->conds, es->predicate); 1130 } 1131 else 1132 fprintf (f, "\n"); 1133 if (es->param) 1134 for (i = 0; i < (int)VEC_length (inline_param_summary_t, es->param); 1135 i++) 1136 { 1137 int prob = VEC_index (inline_param_summary_t, 1138 es->param, i)->change_prob; 1139 1140 if (!prob) 1141 fprintf (f, "%*s op%i is compile time invariant\n", 1142 indent + 2, "", i); 1143 else if (prob != REG_BR_PROB_BASE) 1144 fprintf (f, "%*s op%i change %f%% of time\n", indent + 2, "", i, 1145 prob * 100.0 / REG_BR_PROB_BASE); 1146 } 1147 if (!edge->inline_failed) 1148 { 1149 fprintf (f, "%*sStack frame offset %i, callee self size %i," 1150 " callee size %i\n", 1151 indent+2, "", 1152 (int)inline_summary (callee)->stack_frame_offset, 1153 (int)inline_summary (callee)->estimated_self_stack_size, 1154 (int)inline_summary (callee)->estimated_stack_size); 1155 dump_inline_edge_summary (f, indent+2, callee, info); 1156 } 1157 } 1158 for (edge = node->indirect_calls; edge; edge = edge->next_callee) 1159 { 1160 struct inline_edge_summary *es = inline_edge_summary (edge); 1161 fprintf (f, "%*sindirect call loop depth:%2i freq:%4i size:%2i" 1162 " time: %2i", 1163 indent, "", 1164 es->loop_depth, 1165 edge->frequency, 1166 es->call_stmt_size, 1167 es->call_stmt_time); 1168 if (es->predicate) 1169 { 1170 fprintf (f, "predicate: "); 1171 dump_predicate (f, info->conds, es->predicate); 1172 } 1173 else 1174 fprintf (f, "\n"); 1175 } 1176 } 1177 1178 1179 void 1180 dump_inline_summary (FILE * f, struct cgraph_node *node) 1181 { 1182 if (node->analyzed) 1183 { 1184 struct inline_summary *s = inline_summary (node); 1185 size_time_entry *e; 1186 int i; 1187 fprintf (f, "Inline summary for %s/%i", cgraph_node_name (node), 1188 node->uid); 1189 if (DECL_DISREGARD_INLINE_LIMITS (node->decl)) 1190 fprintf (f, " always_inline"); 1191 if (s->inlinable) 1192 fprintf (f, " inlinable"); 1193 fprintf (f, "\n self time: %i\n", 1194 s->self_time); 1195 fprintf (f, " global time: %i\n", s->time); 1196 fprintf (f, " self size: %i\n", 1197 s->self_size); 1198 fprintf (f, " global size: %i\n", s->size); 1199 fprintf (f, " self stack: %i\n", 1200 (int) s->estimated_self_stack_size); 1201 fprintf (f, " global stack: %i\n", 1202 (int) s->estimated_stack_size); 1203 for (i = 0; 1204 VEC_iterate (size_time_entry, s->entry, i, e); 1205 i++) 1206 { 1207 fprintf (f, " size:%f, time:%f, predicate:", 1208 (double) e->size / INLINE_SIZE_SCALE, 1209 (double) e->time / INLINE_TIME_SCALE); 1210 dump_predicate (f, s->conds, &e->predicate); 1211 } 1212 fprintf (f, " calls:\n"); 1213 dump_inline_edge_summary (f, 4, node, s); 1214 fprintf (f, "\n"); 1215 } 1216 } 1217 1218 DEBUG_FUNCTION void 1219 debug_inline_summary (struct cgraph_node *node) 1220 { 1221 dump_inline_summary (stderr, node); 1222 } 1223 1224 void 1225 dump_inline_summaries (FILE *f) 1226 { 1227 struct cgraph_node *node; 1228 1229 for (node = cgraph_nodes; node; node = node->next) 1230 if (node->analyzed && !node->global.inlined_to) 1231 dump_inline_summary (f, node); 1232 } 1233 1234 /* Give initial reasons why inlining would fail on EDGE. This gets either 1235 nullified or usually overwritten by more precise reasons later. */ 1236 1237 void 1238 initialize_inline_failed (struct cgraph_edge *e) 1239 { 1240 struct cgraph_node *callee = e->callee; 1241 1242 if (e->indirect_unknown_callee) 1243 e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL; 1244 else if (!callee->analyzed) 1245 e->inline_failed = CIF_BODY_NOT_AVAILABLE; 1246 else if (callee->local.redefined_extern_inline) 1247 e->inline_failed = CIF_REDEFINED_EXTERN_INLINE; 1248 else if (e->call_stmt_cannot_inline_p) 1249 e->inline_failed = CIF_MISMATCHED_ARGUMENTS; 1250 else 1251 e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED; 1252 } 1253 1254 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the 1255 boolean variable pointed to by DATA. */ 1256 1257 static bool 1258 mark_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED, 1259 void *data) 1260 { 1261 bool *b = (bool *) data; 1262 *b = true; 1263 return true; 1264 } 1265 1266 /* If OP reffers to value of function parameter, return 1267 the corresponding parameter. */ 1268 1269 static tree 1270 unmodified_parm (gimple stmt, tree op) 1271 { 1272 /* SSA_NAME referring to parm default def? */ 1273 if (TREE_CODE (op) == SSA_NAME 1274 && SSA_NAME_IS_DEFAULT_DEF (op) 1275 && TREE_CODE (SSA_NAME_VAR (op)) == PARM_DECL) 1276 return SSA_NAME_VAR (op); 1277 /* Non-SSA parm reference? */ 1278 if (TREE_CODE (op) == PARM_DECL) 1279 { 1280 bool modified = false; 1281 1282 ao_ref refd; 1283 ao_ref_init (&refd, op); 1284 walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified, &modified, 1285 NULL); 1286 if (!modified) 1287 return op; 1288 } 1289 /* Assignment from a parameter? */ 1290 if (TREE_CODE (op) == SSA_NAME 1291 && !SSA_NAME_IS_DEFAULT_DEF (op) 1292 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op))) 1293 return unmodified_parm (SSA_NAME_DEF_STMT (op), 1294 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op))); 1295 return NULL; 1296 } 1297 1298 /* See if statement might disappear after inlining. 1299 0 - means not eliminated 1300 1 - half of statements goes away 1301 2 - for sure it is eliminated. 1302 We are not terribly sophisticated, basically looking for simple abstraction 1303 penalty wrappers. */ 1304 1305 static int 1306 eliminated_by_inlining_prob (gimple stmt) 1307 { 1308 enum gimple_code code = gimple_code (stmt); 1309 1310 if (!optimize) 1311 return 0; 1312 1313 switch (code) 1314 { 1315 case GIMPLE_RETURN: 1316 return 2; 1317 case GIMPLE_ASSIGN: 1318 if (gimple_num_ops (stmt) != 2) 1319 return 0; 1320 1321 /* Casts of parameters, loads from parameters passed by reference 1322 and stores to return value or parameters are often free after 1323 inlining dua to SRA and further combining. 1324 Assume that half of statements goes away. */ 1325 if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR 1326 || gimple_assign_rhs_code (stmt) == NOP_EXPR 1327 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR 1328 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS) 1329 { 1330 tree rhs = gimple_assign_rhs1 (stmt); 1331 tree lhs = gimple_assign_lhs (stmt); 1332 tree inner_rhs = get_base_address (rhs); 1333 tree inner_lhs = get_base_address (lhs); 1334 bool rhs_free = false; 1335 bool lhs_free = false; 1336 1337 if (!inner_rhs) 1338 inner_rhs = rhs; 1339 if (!inner_lhs) 1340 inner_lhs = lhs; 1341 1342 /* Reads of parameter are expected to be free. */ 1343 if (unmodified_parm (stmt, inner_rhs)) 1344 rhs_free = true; 1345 1346 /* When parameter is not SSA register because its address is taken 1347 and it is just copied into one, the statement will be completely 1348 free after inlining (we will copy propagate backward). */ 1349 if (rhs_free && is_gimple_reg (lhs)) 1350 return 2; 1351 1352 /* Reads of parameters passed by reference 1353 expected to be free (i.e. optimized out after inlining). */ 1354 if (TREE_CODE(inner_rhs) == MEM_REF 1355 && unmodified_parm (stmt, TREE_OPERAND (inner_rhs, 0))) 1356 rhs_free = true; 1357 1358 /* Copying parameter passed by reference into gimple register is 1359 probably also going to copy propagate, but we can't be quite 1360 sure. */ 1361 if (rhs_free && is_gimple_reg (lhs)) 1362 lhs_free = true; 1363 1364 /* Writes to parameters, parameters passed by value and return value 1365 (either dirrectly or passed via invisible reference) are free. 1366 1367 TODO: We ought to handle testcase like 1368 struct a {int a,b;}; 1369 struct a 1370 retrurnsturct (void) 1371 { 1372 struct a a ={1,2}; 1373 return a; 1374 } 1375 1376 This translate into: 1377 1378 retrurnsturct () 1379 { 1380 int a$b; 1381 int a$a; 1382 struct a a; 1383 struct a D.2739; 1384 1385 <bb 2>: 1386 D.2739.a = 1; 1387 D.2739.b = 2; 1388 return D.2739; 1389 1390 } 1391 For that we either need to copy ipa-split logic detecting writes 1392 to return value. */ 1393 if (TREE_CODE (inner_lhs) == PARM_DECL 1394 || TREE_CODE (inner_lhs) == RESULT_DECL 1395 || (TREE_CODE(inner_lhs) == MEM_REF 1396 && (unmodified_parm (stmt, TREE_OPERAND (inner_lhs, 0)) 1397 || (TREE_CODE (TREE_OPERAND (inner_lhs, 0)) == SSA_NAME 1398 && TREE_CODE (SSA_NAME_VAR 1399 (TREE_OPERAND (inner_lhs, 0))) 1400 == RESULT_DECL)))) 1401 lhs_free = true; 1402 if (lhs_free 1403 && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs))) 1404 rhs_free = true; 1405 if (lhs_free && rhs_free) 1406 return 1; 1407 } 1408 return 0; 1409 default: 1410 return 0; 1411 } 1412 } 1413 1414 1415 /* If BB ends by a conditional we can turn into predicates, attach corresponding 1416 predicates to the CFG edges. */ 1417 1418 static void 1419 set_cond_stmt_execution_predicate (struct ipa_node_params *info, 1420 struct inline_summary *summary, 1421 basic_block bb) 1422 { 1423 gimple last; 1424 tree op; 1425 int index; 1426 enum tree_code code, inverted_code; 1427 edge e; 1428 edge_iterator ei; 1429 gimple set_stmt; 1430 tree op2; 1431 tree parm; 1432 tree base; 1433 1434 last = last_stmt (bb); 1435 if (!last 1436 || gimple_code (last) != GIMPLE_COND) 1437 return; 1438 if (!is_gimple_ip_invariant (gimple_cond_rhs (last))) 1439 return; 1440 op = gimple_cond_lhs (last); 1441 /* TODO: handle conditionals like 1442 var = op0 < 4; 1443 if (var != 0). */ 1444 parm = unmodified_parm (last, op); 1445 if (parm) 1446 { 1447 index = ipa_get_param_decl_index (info, parm); 1448 if (index == -1) 1449 return; 1450 code = gimple_cond_code (last); 1451 inverted_code 1452 = invert_tree_comparison (code, 1453 HONOR_NANS (TYPE_MODE (TREE_TYPE (op)))); 1454 1455 FOR_EACH_EDGE (e, ei, bb->succs) 1456 { 1457 struct predicate p = add_condition (summary, 1458 index, 1459 e->flags & EDGE_TRUE_VALUE 1460 ? code : inverted_code, 1461 gimple_cond_rhs (last)); 1462 e->aux = pool_alloc (edge_predicate_pool); 1463 *(struct predicate *)e->aux = p; 1464 } 1465 } 1466 1467 if (TREE_CODE (op) != SSA_NAME) 1468 return; 1469 /* Special case 1470 if (builtin_constant_p (op)) 1471 constant_code 1472 else 1473 nonconstant_code. 1474 Here we can predicate nonconstant_code. We can't 1475 really handle constant_code since we have no predicate 1476 for this and also the constant code is not known to be 1477 optimized away when inliner doen't see operand is constant. 1478 Other optimizers might think otherwise. */ 1479 set_stmt = SSA_NAME_DEF_STMT (op); 1480 if (!gimple_call_builtin_p (set_stmt, BUILT_IN_CONSTANT_P) 1481 || gimple_call_num_args (set_stmt) != 1) 1482 return; 1483 op2 = gimple_call_arg (set_stmt, 0); 1484 base = get_base_address (op2); 1485 parm = unmodified_parm (set_stmt, base ? base : op2); 1486 if (!parm) 1487 return; 1488 index = ipa_get_param_decl_index (info, parm); 1489 if (index == -1) 1490 return; 1491 if (gimple_cond_code (last) != NE_EXPR 1492 || !integer_zerop (gimple_cond_rhs (last))) 1493 return; 1494 FOR_EACH_EDGE (e, ei, bb->succs) 1495 if (e->flags & EDGE_FALSE_VALUE) 1496 { 1497 struct predicate p = add_condition (summary, 1498 index, 1499 IS_NOT_CONSTANT, 1500 NULL); 1501 e->aux = pool_alloc (edge_predicate_pool); 1502 *(struct predicate *)e->aux = p; 1503 } 1504 } 1505 1506 1507 /* If BB ends by a switch we can turn into predicates, attach corresponding 1508 predicates to the CFG edges. */ 1509 1510 static void 1511 set_switch_stmt_execution_predicate (struct ipa_node_params *info, 1512 struct inline_summary *summary, 1513 basic_block bb) 1514 { 1515 gimple last; 1516 tree op; 1517 int index; 1518 edge e; 1519 edge_iterator ei; 1520 size_t n; 1521 size_t case_idx; 1522 tree parm; 1523 1524 last = last_stmt (bb); 1525 if (!last 1526 || gimple_code (last) != GIMPLE_SWITCH) 1527 return; 1528 op = gimple_switch_index (last); 1529 parm = unmodified_parm (last, op); 1530 if (!parm) 1531 return; 1532 index = ipa_get_param_decl_index (info, parm); 1533 if (index == -1) 1534 return; 1535 1536 FOR_EACH_EDGE (e, ei, bb->succs) 1537 { 1538 e->aux = pool_alloc (edge_predicate_pool); 1539 *(struct predicate *)e->aux = false_predicate (); 1540 } 1541 n = gimple_switch_num_labels(last); 1542 for (case_idx = 0; case_idx < n; ++case_idx) 1543 { 1544 tree cl = gimple_switch_label (last, case_idx); 1545 tree min, max; 1546 struct predicate p; 1547 1548 e = find_edge (bb, label_to_block (CASE_LABEL (cl))); 1549 min = CASE_LOW (cl); 1550 max = CASE_HIGH (cl); 1551 1552 /* For default we might want to construct predicate that none 1553 of cases is met, but it is bit hard to do not having negations 1554 of conditionals handy. */ 1555 if (!min && !max) 1556 p = true_predicate (); 1557 else if (!max) 1558 p = add_condition (summary, index, 1559 EQ_EXPR, 1560 min); 1561 else 1562 { 1563 struct predicate p1, p2; 1564 p1 = add_condition (summary, index, 1565 GE_EXPR, 1566 min); 1567 p2 = add_condition (summary, index, 1568 LE_EXPR, 1569 max); 1570 p = and_predicates (summary->conds, &p1, &p2); 1571 } 1572 *(struct predicate *)e->aux 1573 = or_predicates (summary->conds, &p, (struct predicate *)e->aux); 1574 } 1575 } 1576 1577 1578 /* For each BB in NODE attach to its AUX pointer predicate under 1579 which it is executable. */ 1580 1581 static void 1582 compute_bb_predicates (struct cgraph_node *node, 1583 struct ipa_node_params *parms_info, 1584 struct inline_summary *summary) 1585 { 1586 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl); 1587 bool done = false; 1588 basic_block bb; 1589 1590 FOR_EACH_BB_FN (bb, my_function) 1591 { 1592 set_cond_stmt_execution_predicate (parms_info, summary, bb); 1593 set_switch_stmt_execution_predicate (parms_info, summary, bb); 1594 } 1595 1596 /* Entry block is always executable. */ 1597 ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux 1598 = pool_alloc (edge_predicate_pool); 1599 *(struct predicate *)ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function)->aux 1600 = true_predicate (); 1601 1602 /* A simple dataflow propagation of predicates forward in the CFG. 1603 TODO: work in reverse postorder. */ 1604 while (!done) 1605 { 1606 done = true; 1607 FOR_EACH_BB_FN (bb, my_function) 1608 { 1609 struct predicate p = false_predicate (); 1610 edge e; 1611 edge_iterator ei; 1612 FOR_EACH_EDGE (e, ei, bb->preds) 1613 { 1614 if (e->src->aux) 1615 { 1616 struct predicate this_bb_predicate 1617 = *(struct predicate *)e->src->aux; 1618 if (e->aux) 1619 this_bb_predicate 1620 = and_predicates (summary->conds, &this_bb_predicate, 1621 (struct predicate *)e->aux); 1622 p = or_predicates (summary->conds, &p, &this_bb_predicate); 1623 if (true_predicate_p (&p)) 1624 break; 1625 } 1626 } 1627 if (false_predicate_p (&p)) 1628 gcc_assert (!bb->aux); 1629 else 1630 { 1631 if (!bb->aux) 1632 { 1633 done = false; 1634 bb->aux = pool_alloc (edge_predicate_pool); 1635 *((struct predicate *)bb->aux) = p; 1636 } 1637 else if (!predicates_equal_p (&p, (struct predicate *)bb->aux)) 1638 { 1639 done = false; 1640 *((struct predicate *)bb->aux) = p; 1641 } 1642 } 1643 } 1644 } 1645 } 1646 1647 1648 /* We keep info about constantness of SSA names. */ 1649 1650 typedef struct predicate predicate_t; 1651 DEF_VEC_O (predicate_t); 1652 DEF_VEC_ALLOC_O (predicate_t, heap); 1653 1654 1655 /* Return predicate specifying when the STMT might have result that is not 1656 a compile time constant. */ 1657 1658 static struct predicate 1659 will_be_nonconstant_predicate (struct ipa_node_params *info, 1660 struct inline_summary *summary, 1661 gimple stmt, 1662 VEC (predicate_t, heap) *nonconstant_names) 1663 1664 { 1665 struct predicate p = true_predicate (); 1666 ssa_op_iter iter; 1667 tree use; 1668 struct predicate op_non_const; 1669 bool is_load; 1670 1671 /* What statments might be optimized away 1672 when their arguments are constant 1673 TODO: also trivial builtins. 1674 builtin_constant_p is already handled later. */ 1675 if (gimple_code (stmt) != GIMPLE_ASSIGN 1676 && gimple_code (stmt) != GIMPLE_COND 1677 && gimple_code (stmt) != GIMPLE_SWITCH) 1678 return p; 1679 1680 /* Stores will stay anyway. */ 1681 if (gimple_vdef (stmt)) 1682 return p; 1683 1684 is_load = gimple_vuse (stmt) != NULL; 1685 1686 /* Loads can be optimized when the value is known. */ 1687 if (is_load) 1688 { 1689 tree op = gimple_assign_rhs1 (stmt); 1690 tree base = get_base_address (op); 1691 tree parm; 1692 1693 gcc_assert (gimple_assign_single_p (stmt)); 1694 if (!base) 1695 return p; 1696 parm = unmodified_parm (stmt, base); 1697 if (!parm ) 1698 return p; 1699 if (ipa_get_param_decl_index (info, parm) < 0) 1700 return p; 1701 } 1702 1703 /* See if we understand all operands before we start 1704 adding conditionals. */ 1705 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) 1706 { 1707 tree parm = unmodified_parm (stmt, use); 1708 /* For arguments we can build a condition. */ 1709 if (parm && ipa_get_param_decl_index (info, parm) >= 0) 1710 continue; 1711 if (TREE_CODE (use) != SSA_NAME) 1712 return p; 1713 /* If we know when operand is constant, 1714 we still can say something useful. */ 1715 if (!true_predicate_p (VEC_index (predicate_t, nonconstant_names, 1716 SSA_NAME_VERSION (use)))) 1717 continue; 1718 return p; 1719 } 1720 op_non_const = false_predicate (); 1721 if (is_load) 1722 { 1723 tree parm = unmodified_parm 1724 (stmt, get_base_address (gimple_assign_rhs1 (stmt))); 1725 p = add_condition (summary, 1726 ipa_get_param_decl_index (info, parm), 1727 CHANGED, NULL); 1728 op_non_const = or_predicates (summary->conds, &p, &op_non_const); 1729 } 1730 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) 1731 { 1732 tree parm = unmodified_parm (stmt, use); 1733 if (parm && ipa_get_param_decl_index (info, parm) >= 0) 1734 p = add_condition (summary, 1735 ipa_get_param_decl_index (info, parm), 1736 CHANGED, NULL); 1737 else 1738 p = *VEC_index (predicate_t, nonconstant_names, 1739 SSA_NAME_VERSION (use)); 1740 op_non_const = or_predicates (summary->conds, &p, &op_non_const); 1741 } 1742 if (gimple_code (stmt) == GIMPLE_ASSIGN 1743 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME) 1744 VEC_replace (predicate_t, nonconstant_names, 1745 SSA_NAME_VERSION (gimple_assign_lhs (stmt)), &op_non_const); 1746 return op_non_const; 1747 } 1748 1749 struct record_modified_bb_info 1750 { 1751 bitmap bb_set; 1752 gimple stmt; 1753 }; 1754 1755 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be 1756 set except for info->stmt. */ 1757 1758 static bool 1759 record_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, 1760 void *data) 1761 { 1762 struct record_modified_bb_info *info = (struct record_modified_bb_info *) data; 1763 if (SSA_NAME_DEF_STMT (vdef) == info->stmt) 1764 return false; 1765 bitmap_set_bit (info->bb_set, 1766 SSA_NAME_IS_DEFAULT_DEF (vdef) 1767 ? ENTRY_BLOCK_PTR->index : gimple_bb (SSA_NAME_DEF_STMT (vdef))->index); 1768 return false; 1769 } 1770 1771 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT 1772 will change since last invocation of STMT. 1773 1774 Value 0 is reserved for compile time invariants. 1775 For common parameters it is REG_BR_PROB_BASE. For loop invariants it 1776 ought to be REG_BR_PROB_BASE / estimated_iters. */ 1777 1778 static int 1779 param_change_prob (gimple stmt, int i) 1780 { 1781 tree op = gimple_call_arg (stmt, i); 1782 basic_block bb = gimple_bb (stmt); 1783 tree base; 1784 1785 if (is_gimple_min_invariant (op)) 1786 return 0; 1787 /* We would have to do non-trivial analysis to really work out what 1788 is the probability of value to change (i.e. when init statement 1789 is in a sibling loop of the call). 1790 1791 We do an conservative estimate: when call is executed N times more often 1792 than the statement defining value, we take the frequency 1/N. */ 1793 if (TREE_CODE (op) == SSA_NAME) 1794 { 1795 int init_freq; 1796 1797 if (!bb->frequency) 1798 return REG_BR_PROB_BASE; 1799 1800 if (SSA_NAME_IS_DEFAULT_DEF (op)) 1801 init_freq = ENTRY_BLOCK_PTR->frequency; 1802 else 1803 init_freq = gimple_bb (SSA_NAME_DEF_STMT (op))->frequency; 1804 1805 if (!init_freq) 1806 init_freq = 1; 1807 if (init_freq < bb->frequency) 1808 return MAX ((init_freq * REG_BR_PROB_BASE + 1809 bb->frequency / 2) / bb->frequency, 1); 1810 else 1811 return REG_BR_PROB_BASE; 1812 } 1813 1814 base = get_base_address (op); 1815 if (base) 1816 { 1817 ao_ref refd; 1818 int max; 1819 struct record_modified_bb_info info; 1820 bitmap_iterator bi; 1821 unsigned index; 1822 1823 if (const_value_known_p (base)) 1824 return 0; 1825 if (!bb->frequency) 1826 return REG_BR_PROB_BASE; 1827 ao_ref_init (&refd, op); 1828 info.stmt = stmt; 1829 info.bb_set = BITMAP_ALLOC (NULL); 1830 walk_aliased_vdefs (&refd, gimple_vuse (stmt), record_modified, &info, 1831 NULL); 1832 if (bitmap_bit_p (info.bb_set, bb->index)) 1833 { 1834 BITMAP_FREE (info.bb_set); 1835 return REG_BR_PROB_BASE; 1836 } 1837 1838 /* Assume that every memory is initialized at entry. 1839 TODO: Can we easilly determine if value is always defined 1840 and thus we may skip entry block? */ 1841 if (ENTRY_BLOCK_PTR->frequency) 1842 max = ENTRY_BLOCK_PTR->frequency; 1843 else 1844 max = 1; 1845 1846 EXECUTE_IF_SET_IN_BITMAP (info.bb_set, 0, index, bi) 1847 max = MIN (max, BASIC_BLOCK (index)->frequency); 1848 1849 BITMAP_FREE (info.bb_set); 1850 if (max < bb->frequency) 1851 return MAX ((max * REG_BR_PROB_BASE + 1852 bb->frequency / 2) / bb->frequency, 1); 1853 else 1854 return REG_BR_PROB_BASE; 1855 } 1856 return REG_BR_PROB_BASE; 1857 } 1858 1859 1860 /* Compute function body size parameters for NODE. 1861 When EARLY is true, we compute only simple summaries without 1862 non-trivial predicates to drive the early inliner. */ 1863 1864 static void 1865 estimate_function_body_sizes (struct cgraph_node *node, bool early) 1866 { 1867 gcov_type time = 0; 1868 /* Estimate static overhead for function prologue/epilogue and alignment. */ 1869 int size = 2; 1870 /* Benefits are scaled by probability of elimination that is in range 1871 <0,2>. */ 1872 basic_block bb; 1873 gimple_stmt_iterator bsi; 1874 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl); 1875 int freq; 1876 struct inline_summary *info = inline_summary (node); 1877 struct predicate bb_predicate; 1878 struct ipa_node_params *parms_info = NULL; 1879 VEC (predicate_t, heap) *nonconstant_names = NULL; 1880 1881 if (ipa_node_params_vector && !early && optimize) 1882 { 1883 parms_info = IPA_NODE_REF (node); 1884 VEC_safe_grow_cleared (predicate_t, heap, nonconstant_names, 1885 VEC_length (tree, SSANAMES (my_function))); 1886 } 1887 1888 info->conds = 0; 1889 info->entry = 0; 1890 1891 1892 if (dump_file) 1893 fprintf (dump_file, "\nAnalyzing function body size: %s\n", 1894 cgraph_node_name (node)); 1895 1896 /* When we run into maximal number of entries, we assign everything to the 1897 constant truth case. Be sure to have it in list. */ 1898 bb_predicate = true_predicate (); 1899 account_size_time (info, 0, 0, &bb_predicate); 1900 1901 bb_predicate = not_inlined_predicate (); 1902 account_size_time (info, 2 * INLINE_SIZE_SCALE, 0, &bb_predicate); 1903 1904 gcc_assert (my_function && my_function->cfg); 1905 if (parms_info) 1906 compute_bb_predicates (node, parms_info, info); 1907 FOR_EACH_BB_FN (bb, my_function) 1908 { 1909 freq = compute_call_stmt_bb_frequency (node->decl, bb); 1910 1911 /* TODO: Obviously predicates can be propagated down across CFG. */ 1912 if (parms_info) 1913 { 1914 if (bb->aux) 1915 bb_predicate = *(struct predicate *)bb->aux; 1916 else 1917 bb_predicate = false_predicate (); 1918 } 1919 else 1920 bb_predicate = true_predicate (); 1921 1922 if (dump_file && (dump_flags & TDF_DETAILS)) 1923 { 1924 fprintf (dump_file, "\n BB %i predicate:", bb->index); 1925 dump_predicate (dump_file, info->conds, &bb_predicate); 1926 } 1927 1928 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 1929 { 1930 gimple stmt = gsi_stmt (bsi); 1931 int this_size = estimate_num_insns (stmt, &eni_size_weights); 1932 int this_time = estimate_num_insns (stmt, &eni_time_weights); 1933 int prob; 1934 struct predicate will_be_nonconstant; 1935 1936 if (dump_file && (dump_flags & TDF_DETAILS)) 1937 { 1938 fprintf (dump_file, " "); 1939 print_gimple_stmt (dump_file, stmt, 0, 0); 1940 fprintf (dump_file, "\t\tfreq:%3.2f size:%3i time:%3i\n", 1941 ((double)freq)/CGRAPH_FREQ_BASE, this_size, this_time); 1942 } 1943 1944 if (is_gimple_call (stmt)) 1945 { 1946 struct cgraph_edge *edge = cgraph_edge (node, stmt); 1947 struct inline_edge_summary *es = inline_edge_summary (edge); 1948 1949 /* Special case: results of BUILT_IN_CONSTANT_P will be always 1950 resolved as constant. We however don't want to optimize 1951 out the cgraph edges. */ 1952 if (nonconstant_names 1953 && gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P) 1954 && gimple_call_lhs (stmt) 1955 && TREE_CODE (gimple_call_lhs (stmt)) == SSA_NAME) 1956 { 1957 struct predicate false_p = false_predicate (); 1958 VEC_replace (predicate_t, nonconstant_names, 1959 SSA_NAME_VERSION (gimple_call_lhs (stmt)), 1960 &false_p); 1961 } 1962 if (ipa_node_params_vector) 1963 { 1964 int count = gimple_call_num_args (stmt); 1965 int i; 1966 1967 if (count) 1968 VEC_safe_grow_cleared (inline_param_summary_t, heap, 1969 es->param, count); 1970 for (i = 0; i < count; i++) 1971 { 1972 int prob = param_change_prob (stmt, i); 1973 gcc_assert (prob >= 0 && prob <= REG_BR_PROB_BASE); 1974 VEC_index (inline_param_summary_t, 1975 es->param, i)->change_prob = prob; 1976 } 1977 } 1978 1979 es->call_stmt_size = this_size; 1980 es->call_stmt_time = this_time; 1981 es->loop_depth = bb->loop_depth; 1982 edge_set_predicate (edge, &bb_predicate); 1983 } 1984 1985 /* TODO: When conditional jump or swithc is known to be constant, but 1986 we did not translate it into the predicates, we really can account 1987 just maximum of the possible paths. */ 1988 if (parms_info) 1989 will_be_nonconstant 1990 = will_be_nonconstant_predicate (parms_info, info, 1991 stmt, nonconstant_names); 1992 if (this_time || this_size) 1993 { 1994 struct predicate p; 1995 1996 this_time *= freq; 1997 time += this_time; 1998 size += this_size; 1999 2000 prob = eliminated_by_inlining_prob (stmt); 2001 if (prob == 1 && dump_file && (dump_flags & TDF_DETAILS)) 2002 fprintf (dump_file, "\t\t50%% will be eliminated by inlining\n"); 2003 if (prob == 2 && dump_file && (dump_flags & TDF_DETAILS)) 2004 fprintf (dump_file, "\t\tWill be eliminated by inlining\n"); 2005 2006 if (parms_info) 2007 p = and_predicates (info->conds, &bb_predicate, 2008 &will_be_nonconstant); 2009 else 2010 p = true_predicate (); 2011 2012 /* We account everything but the calls. Calls have their own 2013 size/time info attached to cgraph edges. This is neccesary 2014 in order to make the cost disappear after inlining. */ 2015 if (!is_gimple_call (stmt)) 2016 { 2017 if (prob) 2018 { 2019 struct predicate ip = not_inlined_predicate (); 2020 ip = and_predicates (info->conds, &ip, &p); 2021 account_size_time (info, this_size * prob, 2022 this_time * prob, &ip); 2023 } 2024 if (prob != 2) 2025 account_size_time (info, this_size * (2 - prob), 2026 this_time * (2 - prob), &p); 2027 } 2028 2029 gcc_assert (time >= 0); 2030 gcc_assert (size >= 0); 2031 } 2032 } 2033 } 2034 FOR_ALL_BB_FN (bb, my_function) 2035 { 2036 edge e; 2037 edge_iterator ei; 2038 2039 if (bb->aux) 2040 pool_free (edge_predicate_pool, bb->aux); 2041 bb->aux = NULL; 2042 FOR_EACH_EDGE (e, ei, bb->succs) 2043 { 2044 if (e->aux) 2045 pool_free (edge_predicate_pool, e->aux); 2046 e->aux = NULL; 2047 } 2048 } 2049 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE; 2050 if (time > MAX_TIME) 2051 time = MAX_TIME; 2052 inline_summary (node)->self_time = time; 2053 inline_summary (node)->self_size = size; 2054 VEC_free (predicate_t, heap, nonconstant_names); 2055 if (dump_file) 2056 { 2057 fprintf (dump_file, "\n"); 2058 dump_inline_summary (dump_file, node); 2059 } 2060 } 2061 2062 2063 /* Compute parameters of functions used by inliner. 2064 EARLY is true when we compute parameters for the early inliner */ 2065 2066 void 2067 compute_inline_parameters (struct cgraph_node *node, bool early) 2068 { 2069 HOST_WIDE_INT self_stack_size; 2070 struct cgraph_edge *e; 2071 struct inline_summary *info; 2072 tree old_decl = current_function_decl; 2073 2074 gcc_assert (!node->global.inlined_to); 2075 2076 inline_summary_alloc (); 2077 2078 info = inline_summary (node); 2079 reset_inline_summary (node); 2080 2081 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that. 2082 Once this happen, we will need to more curefully predict call 2083 statement size. */ 2084 if (node->thunk.thunk_p) 2085 { 2086 struct inline_edge_summary *es = inline_edge_summary (node->callees); 2087 struct predicate t = true_predicate (); 2088 2089 info->inlinable = 0; 2090 node->callees->call_stmt_cannot_inline_p = true; 2091 node->local.can_change_signature = false; 2092 es->call_stmt_time = 1; 2093 es->call_stmt_size = 1; 2094 account_size_time (info, 0, 0, &t); 2095 return; 2096 } 2097 2098 /* Even is_gimple_min_invariant rely on current_function_decl. */ 2099 current_function_decl = node->decl; 2100 push_cfun (DECL_STRUCT_FUNCTION (node->decl)); 2101 2102 /* Estimate the stack size for the function if we're optimizing. */ 2103 self_stack_size = optimize ? estimated_stack_frame_size (node) : 0; 2104 info->estimated_self_stack_size = self_stack_size; 2105 info->estimated_stack_size = self_stack_size; 2106 info->stack_frame_offset = 0; 2107 2108 /* Can this function be inlined at all? */ 2109 info->inlinable = tree_inlinable_function_p (node->decl); 2110 2111 /* Type attributes can use parameter indices to describe them. */ 2112 if (TYPE_ATTRIBUTES (TREE_TYPE (node->decl))) 2113 node->local.can_change_signature = false; 2114 else 2115 { 2116 /* Otherwise, inlinable functions always can change signature. */ 2117 if (info->inlinable) 2118 node->local.can_change_signature = true; 2119 else 2120 { 2121 /* Functions calling builtin_apply can not change signature. */ 2122 for (e = node->callees; e; e = e->next_callee) 2123 { 2124 tree cdecl = e->callee->decl; 2125 if (DECL_BUILT_IN (cdecl) 2126 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL 2127 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS 2128 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START)) 2129 break; 2130 } 2131 node->local.can_change_signature = !e; 2132 } 2133 } 2134 estimate_function_body_sizes (node, early); 2135 2136 /* Inlining characteristics are maintained by the cgraph_mark_inline. */ 2137 info->time = info->self_time; 2138 info->size = info->self_size; 2139 info->stack_frame_offset = 0; 2140 info->estimated_stack_size = info->estimated_self_stack_size; 2141 current_function_decl = old_decl; 2142 pop_cfun (); 2143 } 2144 2145 2146 /* Compute parameters of functions used by inliner using 2147 current_function_decl. */ 2148 2149 static unsigned int 2150 compute_inline_parameters_for_current (void) 2151 { 2152 compute_inline_parameters (cgraph_get_node (current_function_decl), true); 2153 return 0; 2154 } 2155 2156 struct gimple_opt_pass pass_inline_parameters = 2157 { 2158 { 2159 GIMPLE_PASS, 2160 "inline_param", /* name */ 2161 NULL, /* gate */ 2162 compute_inline_parameters_for_current,/* execute */ 2163 NULL, /* sub */ 2164 NULL, /* next */ 2165 0, /* static_pass_number */ 2166 TV_INLINE_HEURISTICS, /* tv_id */ 2167 0, /* properties_required */ 2168 0, /* properties_provided */ 2169 0, /* properties_destroyed */ 2170 0, /* todo_flags_start */ 2171 0 /* todo_flags_finish */ 2172 } 2173 }; 2174 2175 2176 /* Increase SIZE and TIME for size and time needed to handle edge E. */ 2177 2178 static void 2179 estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time, 2180 int prob) 2181 { 2182 struct inline_edge_summary *es = inline_edge_summary (e); 2183 *size += es->call_stmt_size * INLINE_SIZE_SCALE; 2184 *time += (es->call_stmt_time * prob / REG_BR_PROB_BASE 2185 * e->frequency * (INLINE_TIME_SCALE / CGRAPH_FREQ_BASE)); 2186 if (*time > MAX_TIME * INLINE_TIME_SCALE) 2187 *time = MAX_TIME * INLINE_TIME_SCALE; 2188 } 2189 2190 2191 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS and 2192 KNOWN_BINFOS. */ 2193 2194 static void 2195 estimate_edge_devirt_benefit (struct cgraph_edge *ie, 2196 int *size, int *time, int prob, 2197 VEC (tree, heap) *known_vals, 2198 VEC (tree, heap) *known_binfos) 2199 { 2200 tree target; 2201 int time_diff, size_diff; 2202 2203 if (!known_vals && !known_binfos) 2204 return; 2205 2206 target = ipa_get_indirect_edge_target (ie, known_vals, known_binfos); 2207 if (!target) 2208 return; 2209 2210 /* Account for difference in cost between indirect and direct calls. */ 2211 size_diff = ((eni_size_weights.indirect_call_cost - eni_size_weights.call_cost) 2212 * INLINE_SIZE_SCALE); 2213 *size -= size_diff; 2214 time_diff = ((eni_time_weights.indirect_call_cost - eni_time_weights.call_cost) 2215 * INLINE_TIME_SCALE * prob / REG_BR_PROB_BASE); 2216 *time -= time_diff; 2217 2218 /* TODO: This code is trying to benefit indirect calls that will be inlined later. 2219 The logic however do not belong into local size/time estimates and can not be 2220 done here, or the accounting of changes will get wrong and we result with 2221 negative function body sizes. We need to introduce infrastructure for independent 2222 benefits to the inliner. */ 2223 #if 0 2224 struct cgraph_node *callee; 2225 struct inline_summary *isummary; 2226 int edge_size, edge_time, time_diff, size_diff; 2227 2228 callee = cgraph_get_node (target); 2229 if (!callee || !callee->analyzed) 2230 return; 2231 isummary = inline_summary (callee); 2232 if (!isummary->inlinable) 2233 return; 2234 2235 estimate_edge_size_and_time (ie, &edge_size, &edge_time, prob); 2236 2237 /* Count benefit only from functions that definitely will be inlined 2238 if additional context from NODE's caller were available. 2239 2240 We just account overall size change by inlining. TODO: 2241 we really need to add sort of benefit metrics for these kind of 2242 cases. */ 2243 if (edge_size - size_diff >= isummary->size * INLINE_SIZE_SCALE) 2244 { 2245 /* Subtract size and time that we added for edge IE. */ 2246 *size -= edge_size - size_diff; 2247 2248 /* Account inlined call. */ 2249 *size += isummary->size * INLINE_SIZE_SCALE; 2250 } 2251 #endif 2252 } 2253 2254 2255 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE. 2256 POSSIBLE_TRUTHS, KNOWN_VALS and KNOWN_BINFOS describe context of the call 2257 site. */ 2258 2259 static void 2260 estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time, 2261 clause_t possible_truths, 2262 VEC (tree, heap) *known_vals, 2263 VEC (tree, heap) *known_binfos) 2264 { 2265 struct cgraph_edge *e; 2266 for (e = node->callees; e; e = e->next_callee) 2267 { 2268 struct inline_edge_summary *es = inline_edge_summary (e); 2269 if (!es->predicate || evaluate_predicate (es->predicate, possible_truths)) 2270 { 2271 if (e->inline_failed) 2272 { 2273 /* Predicates of calls shall not use NOT_CHANGED codes, 2274 sowe do not need to compute probabilities. */ 2275 estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE); 2276 } 2277 else 2278 estimate_calls_size_and_time (e->callee, size, time, 2279 possible_truths, 2280 known_vals, known_binfos); 2281 } 2282 } 2283 for (e = node->indirect_calls; e; e = e->next_callee) 2284 { 2285 struct inline_edge_summary *es = inline_edge_summary (e); 2286 if (!es->predicate || evaluate_predicate (es->predicate, possible_truths)) 2287 { 2288 estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE); 2289 estimate_edge_devirt_benefit (e, size, time, REG_BR_PROB_BASE, 2290 known_vals, known_binfos); 2291 } 2292 } 2293 } 2294 2295 2296 /* Estimate size and time needed to execute NODE assuming 2297 POSSIBLE_TRUTHS clause, and KNOWN_VALS and KNOWN_BINFOS information 2298 about NODE's arguments. */ 2299 2300 static void 2301 estimate_node_size_and_time (struct cgraph_node *node, 2302 clause_t possible_truths, 2303 VEC (tree, heap) *known_vals, 2304 VEC (tree, heap) *known_binfos, 2305 int *ret_size, int *ret_time, 2306 VEC (inline_param_summary_t, heap) 2307 *inline_param_summary) 2308 { 2309 struct inline_summary *info = inline_summary (node); 2310 size_time_entry *e; 2311 int size = 0, time = 0; 2312 int i; 2313 2314 if (dump_file 2315 && (dump_flags & TDF_DETAILS)) 2316 { 2317 bool found = false; 2318 fprintf (dump_file, " Estimating body: %s/%i\n" 2319 " Known to be false: ", 2320 cgraph_node_name (node), 2321 node->uid); 2322 2323 for (i = predicate_not_inlined_condition; 2324 i < (predicate_first_dynamic_condition 2325 + (int)VEC_length (condition, info->conds)); i++) 2326 if (!(possible_truths & (1 << i))) 2327 { 2328 if (found) 2329 fprintf (dump_file, ", "); 2330 found = true; 2331 dump_condition (dump_file, info->conds, i); 2332 } 2333 } 2334 2335 for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++) 2336 if (evaluate_predicate (&e->predicate, possible_truths)) 2337 { 2338 size += e->size; 2339 if (!inline_param_summary) 2340 time += e->time; 2341 else 2342 { 2343 int prob = predicate_probability (info->conds, 2344 &e->predicate, 2345 possible_truths, 2346 inline_param_summary); 2347 time += e->time * prob / REG_BR_PROB_BASE; 2348 } 2349 2350 } 2351 2352 if (time > MAX_TIME * INLINE_TIME_SCALE) 2353 time = MAX_TIME * INLINE_TIME_SCALE; 2354 2355 estimate_calls_size_and_time (node, &size, &time, possible_truths, 2356 known_vals, known_binfos); 2357 time = (time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE; 2358 size = (size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE; 2359 2360 2361 if (dump_file 2362 && (dump_flags & TDF_DETAILS)) 2363 fprintf (dump_file, "\n size:%i time:%i\n", size, time); 2364 if (ret_time) 2365 *ret_time = time; 2366 if (ret_size) 2367 *ret_size = size; 2368 return; 2369 } 2370 2371 2372 /* Estimate size and time needed to execute callee of EDGE assuming that 2373 parameters known to be constant at caller of EDGE are propagated. 2374 KNOWN_VALS and KNOWN_BINFOS are vectors of assumed known constant values 2375 and types for parameters. */ 2376 2377 void 2378 estimate_ipcp_clone_size_and_time (struct cgraph_node *node, 2379 VEC (tree, heap) *known_vals, 2380 VEC (tree, heap) *known_binfos, 2381 int *ret_size, int *ret_time) 2382 { 2383 clause_t clause; 2384 2385 clause = evaluate_conditions_for_known_args (node, false, known_vals); 2386 estimate_node_size_and_time (node, clause, known_vals, known_binfos, 2387 ret_size, ret_time, 2388 NULL); 2389 } 2390 2391 2392 /* Translate all conditions from callee representation into caller 2393 representation and symbolically evaluate predicate P into new predicate. 2394 2395 INFO is inline_summary of function we are adding predicate into, 2396 CALLEE_INFO is summary of function predicate P is from. OPERAND_MAP is 2397 array giving callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is 2398 clausule of all callee conditions that may be true in caller context. 2399 TOPLEV_PREDICATE is predicate under which callee is executed. */ 2400 2401 static struct predicate 2402 remap_predicate (struct inline_summary *info, 2403 struct inline_summary *callee_info, 2404 struct predicate *p, 2405 VEC (int, heap) *operand_map, 2406 clause_t possible_truths, 2407 struct predicate *toplev_predicate) 2408 { 2409 int i; 2410 struct predicate out = true_predicate (); 2411 2412 /* True predicate is easy. */ 2413 if (true_predicate_p (p)) 2414 return *toplev_predicate; 2415 for (i = 0; p->clause[i]; i++) 2416 { 2417 clause_t clause = p->clause[i]; 2418 int cond; 2419 struct predicate clause_predicate = false_predicate (); 2420 2421 gcc_assert (i < MAX_CLAUSES); 2422 2423 for (cond = 0; cond < NUM_CONDITIONS; cond ++) 2424 /* Do we have condition we can't disprove? */ 2425 if (clause & possible_truths & (1 << cond)) 2426 { 2427 struct predicate cond_predicate; 2428 /* Work out if the condition can translate to predicate in the 2429 inlined function. */ 2430 if (cond >= predicate_first_dynamic_condition) 2431 { 2432 struct condition *c; 2433 2434 c = VEC_index (condition, callee_info->conds, 2435 cond - predicate_first_dynamic_condition); 2436 /* See if we can remap condition operand to caller's operand. 2437 Otherwise give up. */ 2438 if (!operand_map 2439 || (int)VEC_length (int, operand_map) <= c->operand_num 2440 || VEC_index (int, operand_map, c->operand_num) == -1) 2441 cond_predicate = true_predicate (); 2442 else 2443 cond_predicate = add_condition (info, 2444 VEC_index (int, operand_map, 2445 c->operand_num), 2446 c->code, c->val); 2447 } 2448 /* Fixed conditions remains same, construct single 2449 condition predicate. */ 2450 else 2451 { 2452 cond_predicate.clause[0] = 1 << cond; 2453 cond_predicate.clause[1] = 0; 2454 } 2455 clause_predicate = or_predicates (info->conds, &clause_predicate, 2456 &cond_predicate); 2457 } 2458 out = and_predicates (info->conds, &out, &clause_predicate); 2459 } 2460 return and_predicates (info->conds, &out, toplev_predicate); 2461 } 2462 2463 2464 /* Update summary information of inline clones after inlining. 2465 Compute peak stack usage. */ 2466 2467 static void 2468 inline_update_callee_summaries (struct cgraph_node *node, 2469 int depth) 2470 { 2471 struct cgraph_edge *e; 2472 struct inline_summary *callee_info = inline_summary (node); 2473 struct inline_summary *caller_info = inline_summary (node->callers->caller); 2474 HOST_WIDE_INT peak; 2475 2476 callee_info->stack_frame_offset 2477 = caller_info->stack_frame_offset 2478 + caller_info->estimated_self_stack_size; 2479 peak = callee_info->stack_frame_offset 2480 + callee_info->estimated_self_stack_size; 2481 if (inline_summary (node->global.inlined_to)->estimated_stack_size 2482 < peak) 2483 inline_summary (node->global.inlined_to)->estimated_stack_size = peak; 2484 cgraph_propagate_frequency (node); 2485 for (e = node->callees; e; e = e->next_callee) 2486 { 2487 if (!e->inline_failed) 2488 inline_update_callee_summaries (e->callee, depth); 2489 inline_edge_summary (e)->loop_depth += depth; 2490 } 2491 for (e = node->indirect_calls; e; e = e->next_callee) 2492 inline_edge_summary (e)->loop_depth += depth; 2493 } 2494 2495 /* Update change_prob of EDGE after INLINED_EDGE has been inlined. 2496 When functoin A is inlined in B and A calls C with parameter that 2497 changes with probability PROB1 and C is known to be passthroug 2498 of argument if B that change with probability PROB2, the probability 2499 of change is now PROB1*PROB2. */ 2500 2501 static void 2502 remap_edge_change_prob (struct cgraph_edge *inlined_edge, 2503 struct cgraph_edge *edge) 2504 { 2505 if (ipa_node_params_vector) 2506 { 2507 int i; 2508 struct ipa_edge_args *args = IPA_EDGE_REF (edge); 2509 struct inline_edge_summary *es = inline_edge_summary (edge); 2510 struct inline_edge_summary *inlined_es 2511 = inline_edge_summary (inlined_edge); 2512 2513 for (i = 0; i < ipa_get_cs_argument_count (args); i++) 2514 { 2515 struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i); 2516 if (jfunc->type == IPA_JF_PASS_THROUGH 2517 && (jfunc->value.pass_through.formal_id 2518 < (int) VEC_length (inline_param_summary_t, 2519 inlined_es->param))) 2520 { 2521 int prob1 = VEC_index (inline_param_summary_t, 2522 es->param, i)->change_prob; 2523 int prob2 = VEC_index 2524 (inline_param_summary_t, 2525 inlined_es->param, 2526 jfunc->value.pass_through.formal_id)->change_prob; 2527 int prob = ((prob1 * prob2 + REG_BR_PROB_BASE / 2) 2528 / REG_BR_PROB_BASE); 2529 2530 if (prob1 && prob2 && !prob) 2531 prob = 1; 2532 2533 VEC_index (inline_param_summary_t, 2534 es->param, i)->change_prob = prob; 2535 } 2536 } 2537 } 2538 } 2539 2540 /* Update edge summaries of NODE after INLINED_EDGE has been inlined. 2541 2542 Remap predicates of callees of NODE. Rest of arguments match 2543 remap_predicate. 2544 2545 Also update change probabilities. */ 2546 2547 static void 2548 remap_edge_summaries (struct cgraph_edge *inlined_edge, 2549 struct cgraph_node *node, 2550 struct inline_summary *info, 2551 struct inline_summary *callee_info, 2552 VEC (int, heap) *operand_map, 2553 clause_t possible_truths, 2554 struct predicate *toplev_predicate) 2555 { 2556 struct cgraph_edge *e; 2557 for (e = node->callees; e; e = e->next_callee) 2558 { 2559 struct inline_edge_summary *es = inline_edge_summary (e); 2560 struct predicate p; 2561 2562 if (e->inline_failed) 2563 { 2564 remap_edge_change_prob (inlined_edge, e); 2565 2566 if (es->predicate) 2567 { 2568 p = remap_predicate (info, callee_info, 2569 es->predicate, operand_map, possible_truths, 2570 toplev_predicate); 2571 edge_set_predicate (e, &p); 2572 /* TODO: We should remove the edge for code that will be 2573 optimized out, but we need to keep verifiers and tree-inline 2574 happy. Make it cold for now. */ 2575 if (false_predicate_p (&p)) 2576 { 2577 e->count = 0; 2578 e->frequency = 0; 2579 } 2580 } 2581 else 2582 edge_set_predicate (e, toplev_predicate); 2583 } 2584 else 2585 remap_edge_summaries (inlined_edge, e->callee, info, callee_info, 2586 operand_map, possible_truths, toplev_predicate); 2587 } 2588 for (e = node->indirect_calls; e; e = e->next_callee) 2589 { 2590 struct inline_edge_summary *es = inline_edge_summary (e); 2591 struct predicate p; 2592 2593 remap_edge_change_prob (inlined_edge, e); 2594 if (es->predicate) 2595 { 2596 p = remap_predicate (info, callee_info, 2597 es->predicate, operand_map, possible_truths, 2598 toplev_predicate); 2599 edge_set_predicate (e, &p); 2600 /* TODO: We should remove the edge for code that will be optimized 2601 out, but we need to keep verifiers and tree-inline happy. 2602 Make it cold for now. */ 2603 if (false_predicate_p (&p)) 2604 { 2605 e->count = 0; 2606 e->frequency = 0; 2607 } 2608 } 2609 else 2610 edge_set_predicate (e, toplev_predicate); 2611 } 2612 } 2613 2614 2615 /* We inlined EDGE. Update summary of the function we inlined into. */ 2616 2617 void 2618 inline_merge_summary (struct cgraph_edge *edge) 2619 { 2620 struct inline_summary *callee_info = inline_summary (edge->callee); 2621 struct cgraph_node *to = (edge->caller->global.inlined_to 2622 ? edge->caller->global.inlined_to : edge->caller); 2623 struct inline_summary *info = inline_summary (to); 2624 clause_t clause = 0; /* not_inline is known to be false. */ 2625 size_time_entry *e; 2626 VEC (int, heap) *operand_map = NULL; 2627 int i; 2628 struct predicate toplev_predicate; 2629 struct predicate true_p = true_predicate (); 2630 struct inline_edge_summary *es = inline_edge_summary (edge); 2631 2632 if (es->predicate) 2633 toplev_predicate = *es->predicate; 2634 else 2635 toplev_predicate = true_predicate (); 2636 2637 if (ipa_node_params_vector && callee_info->conds) 2638 { 2639 struct ipa_edge_args *args = IPA_EDGE_REF (edge); 2640 int count = ipa_get_cs_argument_count (args); 2641 int i; 2642 2643 evaluate_properties_for_edge (edge, true, &clause, NULL, NULL); 2644 if (count) 2645 VEC_safe_grow_cleared (int, heap, operand_map, count); 2646 for (i = 0; i < count; i++) 2647 { 2648 struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i); 2649 int map = -1; 2650 /* TODO: handle non-NOPs when merging. */ 2651 if (jfunc->type == IPA_JF_PASS_THROUGH 2652 && jfunc->value.pass_through.operation == NOP_EXPR) 2653 map = jfunc->value.pass_through.formal_id; 2654 VEC_replace (int, operand_map, i, map); 2655 gcc_assert (map < ipa_get_param_count (IPA_NODE_REF (to))); 2656 } 2657 } 2658 for (i = 0; VEC_iterate (size_time_entry, callee_info->entry, i, e); i++) 2659 { 2660 struct predicate p = remap_predicate (info, callee_info, 2661 &e->predicate, operand_map, clause, 2662 &toplev_predicate); 2663 if (!false_predicate_p (&p)) 2664 { 2665 gcov_type add_time = ((gcov_type)e->time * edge->frequency 2666 + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE; 2667 int prob = predicate_probability (callee_info->conds, 2668 &e->predicate, 2669 clause, es->param); 2670 add_time = add_time * prob / REG_BR_PROB_BASE; 2671 if (add_time > MAX_TIME * INLINE_TIME_SCALE) 2672 add_time = MAX_TIME * INLINE_TIME_SCALE; 2673 if (prob != REG_BR_PROB_BASE 2674 && dump_file && (dump_flags & TDF_DETAILS)) 2675 { 2676 fprintf (dump_file, "\t\tScaling time by probability:%f\n", 2677 (double)prob / REG_BR_PROB_BASE); 2678 } 2679 account_size_time (info, e->size, add_time, &p); 2680 } 2681 } 2682 remap_edge_summaries (edge, edge->callee, info, callee_info, operand_map, 2683 clause, &toplev_predicate); 2684 info->size = 0; 2685 info->time = 0; 2686 for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++) 2687 info->size += e->size, info->time += e->time; 2688 estimate_calls_size_and_time (to, &info->size, &info->time, 2689 ~(clause_t)(1 << predicate_false_condition), 2690 NULL, NULL); 2691 2692 inline_update_callee_summaries (edge->callee, 2693 inline_edge_summary (edge)->loop_depth); 2694 2695 /* We do not maintain predicates of inlined edges, free it. */ 2696 edge_set_predicate (edge, &true_p); 2697 /* Similarly remove param summaries. */ 2698 VEC_free (inline_param_summary_t, heap, es->param); 2699 VEC_free (int, heap, operand_map); 2700 2701 info->time = (info->time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE; 2702 info->size = (info->size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE; 2703 } 2704 2705 2706 /* Estimate the time cost for the caller when inlining EDGE. 2707 Only to be called via estimate_edge_time, that handles the 2708 caching mechanism. 2709 2710 When caching, also update the cache entry. Compute both time and 2711 size, since we always need both metrics eventually. */ 2712 2713 int 2714 do_estimate_edge_time (struct cgraph_edge *edge) 2715 { 2716 int time; 2717 int size; 2718 gcov_type ret; 2719 struct cgraph_node *callee; 2720 clause_t clause; 2721 VEC (tree, heap) *known_vals; 2722 VEC (tree, heap) *known_binfos; 2723 struct inline_edge_summary *es = inline_edge_summary (edge); 2724 2725 callee = cgraph_function_or_thunk_node (edge->callee, NULL); 2726 2727 gcc_checking_assert (edge->inline_failed); 2728 evaluate_properties_for_edge (edge, true, 2729 &clause, &known_vals, &known_binfos); 2730 estimate_node_size_and_time (callee, clause, known_vals, known_binfos, 2731 &size, &time, es->param); 2732 VEC_free (tree, heap, known_vals); 2733 VEC_free (tree, heap, known_binfos); 2734 2735 ret = (((gcov_type)time 2736 - es->call_stmt_time) * edge->frequency 2737 + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE; 2738 2739 /* When caching, update the cache entry. */ 2740 if (edge_growth_cache) 2741 { 2742 int ret_size; 2743 if ((int)VEC_length (edge_growth_cache_entry, edge_growth_cache) 2744 <= edge->uid) 2745 VEC_safe_grow_cleared (edge_growth_cache_entry, heap, edge_growth_cache, 2746 cgraph_edge_max_uid); 2747 VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->time 2748 = ret + (ret >= 0); 2749 2750 ret_size = size - es->call_stmt_size; 2751 gcc_checking_assert (es->call_stmt_size); 2752 VEC_index (edge_growth_cache_entry, edge_growth_cache, edge->uid)->size 2753 = ret_size + (ret_size >= 0); 2754 } 2755 return ret; 2756 } 2757 2758 2759 /* Estimate the growth of the caller when inlining EDGE. 2760 Only to be called via estimate_edge_size. */ 2761 2762 int 2763 do_estimate_edge_growth (struct cgraph_edge *edge) 2764 { 2765 int size; 2766 struct cgraph_node *callee; 2767 clause_t clause; 2768 VEC (tree, heap) *known_vals; 2769 VEC (tree, heap) *known_binfos; 2770 2771 /* When we do caching, use do_estimate_edge_time to populate the entry. */ 2772 2773 if (edge_growth_cache) 2774 { 2775 do_estimate_edge_time (edge); 2776 size = VEC_index (edge_growth_cache_entry, 2777 edge_growth_cache, 2778 edge->uid)->size; 2779 gcc_checking_assert (size); 2780 return size - (size > 0); 2781 } 2782 2783 callee = cgraph_function_or_thunk_node (edge->callee, NULL); 2784 2785 /* Early inliner runs without caching, go ahead and do the dirty work. */ 2786 gcc_checking_assert (edge->inline_failed); 2787 evaluate_properties_for_edge (edge, true, 2788 &clause, &known_vals, &known_binfos); 2789 estimate_node_size_and_time (callee, clause, known_vals, known_binfos, 2790 &size, NULL, NULL); 2791 VEC_free (tree, heap, known_vals); 2792 VEC_free (tree, heap, known_binfos); 2793 gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size); 2794 return size - inline_edge_summary (edge)->call_stmt_size; 2795 } 2796 2797 2798 /* Estimate self time of the function NODE after inlining EDGE. */ 2799 2800 int 2801 estimate_time_after_inlining (struct cgraph_node *node, 2802 struct cgraph_edge *edge) 2803 { 2804 struct inline_edge_summary *es = inline_edge_summary (edge); 2805 if (!es->predicate || !false_predicate_p (es->predicate)) 2806 { 2807 gcov_type time = inline_summary (node)->time + estimate_edge_time (edge); 2808 if (time < 0) 2809 time = 0; 2810 if (time > MAX_TIME) 2811 time = MAX_TIME; 2812 return time; 2813 } 2814 return inline_summary (node)->time; 2815 } 2816 2817 2818 /* Estimate the size of NODE after inlining EDGE which should be an 2819 edge to either NODE or a call inlined into NODE. */ 2820 2821 int 2822 estimate_size_after_inlining (struct cgraph_node *node, 2823 struct cgraph_edge *edge) 2824 { 2825 struct inline_edge_summary *es = inline_edge_summary (edge); 2826 if (!es->predicate || !false_predicate_p (es->predicate)) 2827 { 2828 int size = inline_summary (node)->size + estimate_edge_growth (edge); 2829 gcc_assert (size >= 0); 2830 return size; 2831 } 2832 return inline_summary (node)->size; 2833 } 2834 2835 2836 struct growth_data 2837 { 2838 bool self_recursive; 2839 int growth; 2840 }; 2841 2842 2843 /* Worker for do_estimate_growth. Collect growth for all callers. */ 2844 2845 static bool 2846 do_estimate_growth_1 (struct cgraph_node *node, void *data) 2847 { 2848 struct cgraph_edge *e; 2849 struct growth_data *d = (struct growth_data *) data; 2850 2851 for (e = node->callers; e; e = e->next_caller) 2852 { 2853 gcc_checking_assert (e->inline_failed); 2854 2855 if (e->caller == node 2856 || (e->caller->global.inlined_to 2857 && e->caller->global.inlined_to == node)) 2858 d->self_recursive = true; 2859 d->growth += estimate_edge_growth (e); 2860 } 2861 return false; 2862 } 2863 2864 2865 /* Estimate the growth caused by inlining NODE into all callees. */ 2866 2867 int 2868 do_estimate_growth (struct cgraph_node *node) 2869 { 2870 struct growth_data d = {0, false}; 2871 struct inline_summary *info = inline_summary (node); 2872 2873 cgraph_for_node_and_aliases (node, do_estimate_growth_1, &d, true); 2874 2875 /* For self recursive functions the growth estimation really should be 2876 infinity. We don't want to return very large values because the growth 2877 plays various roles in badness computation fractions. Be sure to not 2878 return zero or negative growths. */ 2879 if (d.self_recursive) 2880 d.growth = d.growth < info->size ? info->size : d.growth; 2881 else 2882 { 2883 if (!DECL_EXTERNAL (node->decl) 2884 && cgraph_will_be_removed_from_program_if_no_direct_calls (node)) 2885 d.growth -= info->size; 2886 /* COMDAT functions are very often not shared across multiple units 2887 since they come from various template instantiations. 2888 Take this into account. */ 2889 else if (DECL_COMDAT (node->decl) 2890 && cgraph_can_remove_if_no_direct_calls_p (node)) 2891 d.growth -= (info->size 2892 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY)) 2893 + 50) / 100; 2894 } 2895 2896 if (node_growth_cache) 2897 { 2898 if ((int)VEC_length (int, node_growth_cache) <= node->uid) 2899 VEC_safe_grow_cleared (int, heap, node_growth_cache, cgraph_max_uid); 2900 VEC_replace (int, node_growth_cache, node->uid, 2901 d.growth + (d.growth >= 0)); 2902 } 2903 return d.growth; 2904 } 2905 2906 2907 /* This function performs intraprocedural analysis in NODE that is required to 2908 inline indirect calls. */ 2909 2910 static void 2911 inline_indirect_intraprocedural_analysis (struct cgraph_node *node) 2912 { 2913 ipa_analyze_node (node); 2914 if (dump_file && (dump_flags & TDF_DETAILS)) 2915 { 2916 ipa_print_node_params (dump_file, node); 2917 ipa_print_node_jump_functions (dump_file, node); 2918 } 2919 } 2920 2921 2922 /* Note function body size. */ 2923 2924 static void 2925 inline_analyze_function (struct cgraph_node *node) 2926 { 2927 push_cfun (DECL_STRUCT_FUNCTION (node->decl)); 2928 current_function_decl = node->decl; 2929 2930 if (dump_file) 2931 fprintf (dump_file, "\nAnalyzing function: %s/%u\n", 2932 cgraph_node_name (node), node->uid); 2933 if (optimize && !node->thunk.thunk_p) 2934 inline_indirect_intraprocedural_analysis (node); 2935 compute_inline_parameters (node, false); 2936 2937 current_function_decl = NULL; 2938 pop_cfun (); 2939 } 2940 2941 2942 /* Called when new function is inserted to callgraph late. */ 2943 2944 static void 2945 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED) 2946 { 2947 inline_analyze_function (node); 2948 } 2949 2950 2951 /* Note function body size. */ 2952 2953 void 2954 inline_generate_summary (void) 2955 { 2956 struct cgraph_node *node; 2957 2958 function_insertion_hook_holder = 2959 cgraph_add_function_insertion_hook (&add_new_function, NULL); 2960 2961 ipa_register_cgraph_hooks (); 2962 inline_free_summary (); 2963 2964 FOR_EACH_DEFINED_FUNCTION (node) 2965 if (!node->alias) 2966 inline_analyze_function (node); 2967 } 2968 2969 2970 /* Read predicate from IB. */ 2971 2972 static struct predicate 2973 read_predicate (struct lto_input_block *ib) 2974 { 2975 struct predicate out; 2976 clause_t clause; 2977 int k = 0; 2978 2979 do 2980 { 2981 gcc_assert (k <= MAX_CLAUSES); 2982 clause = out.clause[k++] = streamer_read_uhwi (ib); 2983 } 2984 while (clause); 2985 2986 /* Zero-initialize the remaining clauses in OUT. */ 2987 while (k <= MAX_CLAUSES) 2988 out.clause[k++] = 0; 2989 2990 return out; 2991 } 2992 2993 2994 /* Write inline summary for edge E to OB. */ 2995 2996 static void 2997 read_inline_edge_summary (struct lto_input_block *ib, struct cgraph_edge *e) 2998 { 2999 struct inline_edge_summary *es = inline_edge_summary (e); 3000 struct predicate p; 3001 int length, i; 3002 3003 es->call_stmt_size = streamer_read_uhwi (ib); 3004 es->call_stmt_time = streamer_read_uhwi (ib); 3005 es->loop_depth = streamer_read_uhwi (ib); 3006 p = read_predicate (ib); 3007 edge_set_predicate (e, &p); 3008 length = streamer_read_uhwi (ib); 3009 if (length) 3010 { 3011 VEC_safe_grow_cleared (inline_param_summary_t, heap, es->param, length); 3012 for (i = 0; i < length; i++) 3013 VEC_index (inline_param_summary_t, es->param, i)->change_prob 3014 = streamer_read_uhwi (ib); 3015 } 3016 } 3017 3018 3019 /* Stream in inline summaries from the section. */ 3020 3021 static void 3022 inline_read_section (struct lto_file_decl_data *file_data, const char *data, 3023 size_t len) 3024 { 3025 const struct lto_function_header *header = 3026 (const struct lto_function_header *) data; 3027 const int cfg_offset = sizeof (struct lto_function_header); 3028 const int main_offset = cfg_offset + header->cfg_size; 3029 const int string_offset = main_offset + header->main_size; 3030 struct data_in *data_in; 3031 struct lto_input_block ib; 3032 unsigned int i, count2, j; 3033 unsigned int f_count; 3034 3035 LTO_INIT_INPUT_BLOCK (ib, (const char *) data + main_offset, 0, 3036 header->main_size); 3037 3038 data_in = 3039 lto_data_in_create (file_data, (const char *) data + string_offset, 3040 header->string_size, NULL); 3041 f_count = streamer_read_uhwi (&ib); 3042 for (i = 0; i < f_count; i++) 3043 { 3044 unsigned int index; 3045 struct cgraph_node *node; 3046 struct inline_summary *info; 3047 lto_cgraph_encoder_t encoder; 3048 struct bitpack_d bp; 3049 struct cgraph_edge *e; 3050 3051 index = streamer_read_uhwi (&ib); 3052 encoder = file_data->cgraph_node_encoder; 3053 node = lto_cgraph_encoder_deref (encoder, index); 3054 info = inline_summary (node); 3055 3056 info->estimated_stack_size 3057 = info->estimated_self_stack_size = streamer_read_uhwi (&ib); 3058 info->size = info->self_size = streamer_read_uhwi (&ib); 3059 info->time = info->self_time = streamer_read_uhwi (&ib); 3060 3061 bp = streamer_read_bitpack (&ib); 3062 info->inlinable = bp_unpack_value (&bp, 1); 3063 3064 count2 = streamer_read_uhwi (&ib); 3065 gcc_assert (!info->conds); 3066 for (j = 0; j < count2; j++) 3067 { 3068 struct condition c; 3069 c.operand_num = streamer_read_uhwi (&ib); 3070 c.code = (enum tree_code) streamer_read_uhwi (&ib); 3071 c.val = stream_read_tree (&ib, data_in); 3072 VEC_safe_push (condition, gc, info->conds, &c); 3073 } 3074 count2 = streamer_read_uhwi (&ib); 3075 gcc_assert (!info->entry); 3076 for (j = 0; j < count2; j++) 3077 { 3078 struct size_time_entry e; 3079 3080 e.size = streamer_read_uhwi (&ib); 3081 e.time = streamer_read_uhwi (&ib); 3082 e.predicate = read_predicate (&ib); 3083 3084 VEC_safe_push (size_time_entry, gc, info->entry, &e); 3085 } 3086 for (e = node->callees; e; e = e->next_callee) 3087 read_inline_edge_summary (&ib, e); 3088 for (e = node->indirect_calls; e; e = e->next_callee) 3089 read_inline_edge_summary (&ib, e); 3090 } 3091 3092 lto_free_section_data (file_data, LTO_section_inline_summary, NULL, data, 3093 len); 3094 lto_data_in_delete (data_in); 3095 } 3096 3097 3098 /* Read inline summary. Jump functions are shared among ipa-cp 3099 and inliner, so when ipa-cp is active, we don't need to write them 3100 twice. */ 3101 3102 void 3103 inline_read_summary (void) 3104 { 3105 struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data (); 3106 struct lto_file_decl_data *file_data; 3107 unsigned int j = 0; 3108 3109 inline_summary_alloc (); 3110 3111 while ((file_data = file_data_vec[j++])) 3112 { 3113 size_t len; 3114 const char *data = lto_get_section_data (file_data, 3115 LTO_section_inline_summary, 3116 NULL, &len); 3117 if (data) 3118 inline_read_section (file_data, data, len); 3119 else 3120 /* Fatal error here. We do not want to support compiling ltrans units 3121 with different version of compiler or different flags than the WPA 3122 unit, so this should never happen. */ 3123 fatal_error ("ipa inline summary is missing in input file"); 3124 } 3125 if (optimize) 3126 { 3127 ipa_register_cgraph_hooks (); 3128 if (!flag_ipa_cp) 3129 ipa_prop_read_jump_functions (); 3130 } 3131 function_insertion_hook_holder = 3132 cgraph_add_function_insertion_hook (&add_new_function, NULL); 3133 } 3134 3135 3136 /* Write predicate P to OB. */ 3137 3138 static void 3139 write_predicate (struct output_block *ob, struct predicate *p) 3140 { 3141 int j; 3142 if (p) 3143 for (j = 0; p->clause[j]; j++) 3144 { 3145 gcc_assert (j < MAX_CLAUSES); 3146 streamer_write_uhwi (ob, p->clause[j]); 3147 } 3148 streamer_write_uhwi (ob, 0); 3149 } 3150 3151 3152 /* Write inline summary for edge E to OB. */ 3153 3154 static void 3155 write_inline_edge_summary (struct output_block *ob, struct cgraph_edge *e) 3156 { 3157 struct inline_edge_summary *es = inline_edge_summary (e); 3158 int i; 3159 3160 streamer_write_uhwi (ob, es->call_stmt_size); 3161 streamer_write_uhwi (ob, es->call_stmt_time); 3162 streamer_write_uhwi (ob, es->loop_depth); 3163 write_predicate (ob, es->predicate); 3164 streamer_write_uhwi (ob, VEC_length (inline_param_summary_t, es->param)); 3165 for (i = 0; i < (int)VEC_length (inline_param_summary_t, es->param); i++) 3166 streamer_write_uhwi (ob, VEC_index (inline_param_summary_t, 3167 es->param, i)->change_prob); 3168 } 3169 3170 3171 /* Write inline summary for node in SET. 3172 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is 3173 active, we don't need to write them twice. */ 3174 3175 void 3176 inline_write_summary (cgraph_node_set set, 3177 varpool_node_set vset ATTRIBUTE_UNUSED) 3178 { 3179 struct cgraph_node *node; 3180 struct output_block *ob = create_output_block (LTO_section_inline_summary); 3181 lto_cgraph_encoder_t encoder = ob->decl_state->cgraph_node_encoder; 3182 unsigned int count = 0; 3183 int i; 3184 3185 for (i = 0; i < lto_cgraph_encoder_size (encoder); i++) 3186 if (lto_cgraph_encoder_deref (encoder, i)->analyzed) 3187 count++; 3188 streamer_write_uhwi (ob, count); 3189 3190 for (i = 0; i < lto_cgraph_encoder_size (encoder); i++) 3191 { 3192 node = lto_cgraph_encoder_deref (encoder, i); 3193 if (node->analyzed) 3194 { 3195 struct inline_summary *info = inline_summary (node); 3196 struct bitpack_d bp; 3197 struct cgraph_edge *edge; 3198 int i; 3199 size_time_entry *e; 3200 struct condition *c; 3201 3202 streamer_write_uhwi (ob, lto_cgraph_encoder_encode (encoder, node)); 3203 streamer_write_hwi (ob, info->estimated_self_stack_size); 3204 streamer_write_hwi (ob, info->self_size); 3205 streamer_write_hwi (ob, info->self_time); 3206 bp = bitpack_create (ob->main_stream); 3207 bp_pack_value (&bp, info->inlinable, 1); 3208 streamer_write_bitpack (&bp); 3209 streamer_write_uhwi (ob, VEC_length (condition, info->conds)); 3210 for (i = 0; VEC_iterate (condition, info->conds, i, c); i++) 3211 { 3212 streamer_write_uhwi (ob, c->operand_num); 3213 streamer_write_uhwi (ob, c->code); 3214 stream_write_tree (ob, c->val, true); 3215 } 3216 streamer_write_uhwi (ob, VEC_length (size_time_entry, info->entry)); 3217 for (i = 0; 3218 VEC_iterate (size_time_entry, info->entry, i, e); 3219 i++) 3220 { 3221 streamer_write_uhwi (ob, e->size); 3222 streamer_write_uhwi (ob, e->time); 3223 write_predicate (ob, &e->predicate); 3224 } 3225 for (edge = node->callees; edge; edge = edge->next_callee) 3226 write_inline_edge_summary (ob, edge); 3227 for (edge = node->indirect_calls; edge; edge = edge->next_callee) 3228 write_inline_edge_summary (ob, edge); 3229 } 3230 } 3231 streamer_write_char_stream (ob->main_stream, 0); 3232 produce_asm (ob, NULL); 3233 destroy_output_block (ob); 3234 3235 if (optimize && !flag_ipa_cp) 3236 ipa_prop_write_jump_functions (set); 3237 } 3238 3239 3240 /* Release inline summary. */ 3241 3242 void 3243 inline_free_summary (void) 3244 { 3245 struct cgraph_node *node; 3246 FOR_EACH_DEFINED_FUNCTION (node) 3247 reset_inline_summary (node); 3248 if (function_insertion_hook_holder) 3249 cgraph_remove_function_insertion_hook (function_insertion_hook_holder); 3250 function_insertion_hook_holder = NULL; 3251 if (node_removal_hook_holder) 3252 cgraph_remove_node_removal_hook (node_removal_hook_holder); 3253 node_removal_hook_holder = NULL; 3254 if (edge_removal_hook_holder) 3255 cgraph_remove_edge_removal_hook (edge_removal_hook_holder); 3256 edge_removal_hook_holder = NULL; 3257 if (node_duplication_hook_holder) 3258 cgraph_remove_node_duplication_hook (node_duplication_hook_holder); 3259 node_duplication_hook_holder = NULL; 3260 if (edge_duplication_hook_holder) 3261 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder); 3262 edge_duplication_hook_holder = NULL; 3263 VEC_free (inline_summary_t, gc, inline_summary_vec); 3264 inline_summary_vec = NULL; 3265 VEC_free (inline_edge_summary_t, heap, inline_edge_summary_vec); 3266 inline_edge_summary_vec = NULL; 3267 if (edge_predicate_pool) 3268 free_alloc_pool (edge_predicate_pool); 3269 edge_predicate_pool = 0; 3270 } 3271