1 /* Interprocedural constant propagation 2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 3 Free Software Foundation, Inc. 4 5 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor 6 <mjambor@suse.cz> 7 8 This file is part of GCC. 9 10 GCC is free software; you can redistribute it and/or modify it under 11 the terms of the GNU General Public License as published by the Free 12 Software Foundation; either version 3, or (at your option) any later 13 version. 14 15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 16 WARRANTY; without even the implied warranty of MERCHANTABILITY or 17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 18 for more details. 19 20 You should have received a copy of the GNU General Public License 21 along with GCC; see the file COPYING3. If not see 22 <http://www.gnu.org/licenses/>. */ 23 24 /* Interprocedural constant propagation (IPA-CP). 25 26 The goal of this transformation is to 27 28 1) discover functions which are always invoked with some arguments with the 29 same known constant values and modify the functions so that the 30 subsequent optimizations can take advantage of the knowledge, and 31 32 2) partial specialization - create specialized versions of functions 33 transformed in this way if some parameters are known constants only in 34 certain contexts but the estimated tradeoff between speedup and cost size 35 is deemed good. 36 37 The algorithm also propagates types and attempts to perform type based 38 devirtualization. Types are propagated much like constants. 39 40 The algorithm basically consists of three stages. In the first, functions 41 are analyzed one at a time and jump functions are constructed for all known 42 call-sites. In the second phase, the pass propagates information from the 43 jump functions across the call to reveal what values are available at what 44 call sites, performs estimations of effects of known values on functions and 45 their callees, and finally decides what specialized extra versions should be 46 created. In the third, the special versions materialize and appropriate 47 calls are redirected. 48 49 The algorithm used is to a certain extent based on "Interprocedural Constant 50 Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon, 51 Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D 52 Cooper, Mary W. Hall, and Ken Kennedy. 53 54 55 First stage - intraprocedural analysis 56 ======================================= 57 58 This phase computes jump_function and modification flags. 59 60 A jump function for a call-site represents the values passed as an actual 61 arguments of a given call-site. In principle, there are three types of 62 values: 63 64 Pass through - the caller's formal parameter is passed as an actual 65 argument, plus an operation on it can be performed. 66 Constant - a constant is passed as an actual argument. 67 Unknown - neither of the above. 68 69 All jump function types are described in detail in ipa-prop.h, together with 70 the data structures that represent them and methods of accessing them. 71 72 ipcp_generate_summary() is the main function of the first stage. 73 74 Second stage - interprocedural analysis 75 ======================================== 76 77 This stage is itself divided into two phases. In the first, we propagate 78 known values over the call graph, in the second, we make cloning decisions. 79 It uses a different algorithm than the original Callahan's paper. 80 81 First, we traverse the functions topologically from callers to callees and, 82 for each strongly connected component (SCC), we propagate constants 83 according to previously computed jump functions. We also record what known 84 values depend on other known values and estimate local effects. Finally, we 85 propagate cumulative information about these effects from dependant values 86 to those on which they depend. 87 88 Second, we again traverse the call graph in the same topological order and 89 make clones for functions which we know are called with the same values in 90 all contexts and decide about extra specialized clones of functions just for 91 some contexts - these decisions are based on both local estimates and 92 cumulative estimates propagated from callees. 93 94 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the 95 third stage. 96 97 Third phase - materialization of clones, call statement updates. 98 ============================================ 99 100 This stage is currently performed by call graph code (mainly in cgraphunit.c 101 and tree-inline.c) according to instructions inserted to the call graph by 102 the second stage. */ 103 104 #include "config.h" 105 #include "system.h" 106 #include "coretypes.h" 107 #include "tree.h" 108 #include "target.h" 109 #include "gimple.h" 110 #include "cgraph.h" 111 #include "ipa-prop.h" 112 #include "tree-flow.h" 113 #include "tree-pass.h" 114 #include "flags.h" 115 #include "timevar.h" 116 #include "diagnostic.h" 117 #include "tree-pretty-print.h" 118 #include "tree-dump.h" 119 #include "tree-inline.h" 120 #include "fibheap.h" 121 #include "params.h" 122 #include "ipa-inline.h" 123 #include "ipa-utils.h" 124 125 struct ipcp_value; 126 127 /* Describes a particular source for an IPA-CP value. */ 128 129 struct ipcp_value_source 130 { 131 /* The incoming edge that brought the value. */ 132 struct cgraph_edge *cs; 133 /* If the jump function that resulted into his value was a pass-through or an 134 ancestor, this is the ipcp_value of the caller from which the described 135 value has been derived. Otherwise it is NULL. */ 136 struct ipcp_value *val; 137 /* Next pointer in a linked list of sources of a value. */ 138 struct ipcp_value_source *next; 139 /* If the jump function that resulted into his value was a pass-through or an 140 ancestor, this is the index of the parameter of the caller the jump 141 function references. */ 142 int index; 143 }; 144 145 /* Describes one particular value stored in struct ipcp_lattice. */ 146 147 struct ipcp_value 148 { 149 /* The actual value for the given parameter. This is either an IPA invariant 150 or a TREE_BINFO describing a type that can be used for 151 devirtualization. */ 152 tree value; 153 /* The list of sources from which this value originates. */ 154 struct ipcp_value_source *sources; 155 /* Next pointers in a linked list of all values in a lattice. */ 156 struct ipcp_value *next; 157 /* Next pointers in a linked list of values in a strongly connected component 158 of values. */ 159 struct ipcp_value *scc_next; 160 /* Next pointers in a linked list of SCCs of values sorted topologically 161 according their sources. */ 162 struct ipcp_value *topo_next; 163 /* A specialized node created for this value, NULL if none has been (so far) 164 created. */ 165 struct cgraph_node *spec_node; 166 /* Depth first search number and low link for topological sorting of 167 values. */ 168 int dfs, low_link; 169 /* Time benefit and size cost that specializing the function for this value 170 would bring about in this function alone. */ 171 int local_time_benefit, local_size_cost; 172 /* Time benefit and size cost that specializing the function for this value 173 can bring about in it's callees (transitively). */ 174 int prop_time_benefit, prop_size_cost; 175 /* True if this valye is currently on the topo-sort stack. */ 176 bool on_stack; 177 }; 178 179 /* Allocation pools for values and their sources in ipa-cp. */ 180 181 alloc_pool ipcp_values_pool; 182 alloc_pool ipcp_sources_pool; 183 184 /* Lattice describing potential values of a formal parameter of a function and 185 some of their other properties. TOP is represented by a lattice with zero 186 values and with contains_variable and bottom flags cleared. BOTTOM is 187 represented by a lattice with the bottom flag set. In that case, values and 188 contains_variable flag should be disregarded. */ 189 190 struct ipcp_lattice 191 { 192 /* The list of known values and types in this lattice. Note that values are 193 not deallocated if a lattice is set to bottom because there may be value 194 sources referencing them. */ 195 struct ipcp_value *values; 196 /* Number of known values and types in this lattice. */ 197 int values_count; 198 /* The lattice contains a variable component (in addition to values). */ 199 bool contains_variable; 200 /* The value of the lattice is bottom (i.e. variable and unusable for any 201 propagation). */ 202 bool bottom; 203 /* There is a virtual call based on this parameter. */ 204 bool virt_call; 205 }; 206 207 /* Maximal count found in program. */ 208 209 static gcov_type max_count; 210 211 /* Original overall size of the program. */ 212 213 static long overall_size, max_new_size; 214 215 /* Head of the linked list of topologically sorted values. */ 216 217 static struct ipcp_value *values_topo; 218 219 /* Return the lattice corresponding to the Ith formal parameter of the function 220 described by INFO. */ 221 static inline struct ipcp_lattice * 222 ipa_get_lattice (struct ipa_node_params *info, int i) 223 { 224 gcc_assert (i >= 0 && i < ipa_get_param_count (info)); 225 gcc_checking_assert (!info->ipcp_orig_node); 226 gcc_checking_assert (info->lattices); 227 return &(info->lattices[i]); 228 } 229 230 /* Return whether LAT is a lattice with a single constant and without an 231 undefined value. */ 232 233 static inline bool 234 ipa_lat_is_single_const (struct ipcp_lattice *lat) 235 { 236 if (lat->bottom 237 || lat->contains_variable 238 || lat->values_count != 1) 239 return false; 240 else 241 return true; 242 } 243 244 /* Return true iff the CS is an edge within a strongly connected component as 245 computed by ipa_reduced_postorder. */ 246 247 static inline bool 248 edge_within_scc (struct cgraph_edge *cs) 249 { 250 struct ipa_dfs_info *caller_dfs = (struct ipa_dfs_info *) cs->caller->aux; 251 struct ipa_dfs_info *callee_dfs; 252 struct cgraph_node *callee = cgraph_function_node (cs->callee, NULL); 253 254 callee_dfs = (struct ipa_dfs_info *) callee->aux; 255 return (caller_dfs 256 && callee_dfs 257 && caller_dfs->scc_no == callee_dfs->scc_no); 258 } 259 260 /* Print V which is extracted from a value in a lattice to F. */ 261 262 static void 263 print_ipcp_constant_value (FILE * f, tree v) 264 { 265 if (TREE_CODE (v) == TREE_BINFO) 266 { 267 fprintf (f, "BINFO "); 268 print_generic_expr (f, BINFO_TYPE (v), 0); 269 } 270 else if (TREE_CODE (v) == ADDR_EXPR 271 && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL) 272 { 273 fprintf (f, "& "); 274 print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)), 0); 275 } 276 else 277 print_generic_expr (f, v, 0); 278 } 279 280 /* Print all ipcp_lattices of all functions to F. */ 281 282 static void 283 print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits) 284 { 285 struct cgraph_node *node; 286 int i, count; 287 288 fprintf (f, "\nLattices:\n"); 289 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) 290 { 291 struct ipa_node_params *info; 292 293 info = IPA_NODE_REF (node); 294 fprintf (f, " Node: %s/%i:\n", cgraph_node_name (node), node->uid); 295 count = ipa_get_param_count (info); 296 for (i = 0; i < count; i++) 297 { 298 struct ipcp_lattice *lat = ipa_get_lattice (info, i); 299 struct ipcp_value *val; 300 bool prev = false; 301 302 fprintf (f, " param [%d]: ", i); 303 if (lat->bottom) 304 { 305 fprintf (f, "BOTTOM\n"); 306 continue; 307 } 308 309 if (!lat->values_count && !lat->contains_variable) 310 { 311 fprintf (f, "TOP\n"); 312 continue; 313 } 314 315 if (lat->contains_variable) 316 { 317 fprintf (f, "VARIABLE"); 318 prev = true; 319 if (dump_benefits) 320 fprintf (f, "\n"); 321 } 322 323 for (val = lat->values; val; val = val->next) 324 { 325 if (dump_benefits && prev) 326 fprintf (f, " "); 327 else if (!dump_benefits && prev) 328 fprintf (f, ", "); 329 else 330 prev = true; 331 332 print_ipcp_constant_value (f, val->value); 333 334 if (dump_sources) 335 { 336 struct ipcp_value_source *s; 337 338 fprintf (f, " [from:"); 339 for (s = val->sources; s; s = s->next) 340 fprintf (f, " %i(%i)", s->cs->caller->uid,s->cs->frequency); 341 fprintf (f, "]"); 342 } 343 344 if (dump_benefits) 345 fprintf (f, " [loc_time: %i, loc_size: %i, " 346 "prop_time: %i, prop_size: %i]\n", 347 val->local_time_benefit, val->local_size_cost, 348 val->prop_time_benefit, val->prop_size_cost); 349 } 350 if (!dump_benefits) 351 fprintf (f, "\n"); 352 } 353 } 354 } 355 356 /* Determine whether it is at all technically possible to create clones of NODE 357 and store this information in the ipa_node_params structure associated 358 with NODE. */ 359 360 static void 361 determine_versionability (struct cgraph_node *node) 362 { 363 const char *reason = NULL; 364 365 /* There are a number of generic reasons functions cannot be versioned. We 366 also cannot remove parameters if there are type attributes such as fnspec 367 present. */ 368 if (node->alias || node->thunk.thunk_p) 369 reason = "alias or thunk"; 370 else if (!node->local.versionable) 371 reason = "not a tree_versionable_function"; 372 else if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE) 373 reason = "insufficient body availability"; 374 375 if (reason && dump_file && !node->alias && !node->thunk.thunk_p) 376 fprintf (dump_file, "Function %s/%i is not versionable, reason: %s.\n", 377 cgraph_node_name (node), node->uid, reason); 378 379 node->local.versionable = (reason == NULL); 380 } 381 382 /* Return true if it is at all technically possible to create clones of a 383 NODE. */ 384 385 static bool 386 ipcp_versionable_function_p (struct cgraph_node *node) 387 { 388 return node->local.versionable; 389 } 390 391 /* Structure holding accumulated information about callers of a node. */ 392 393 struct caller_statistics 394 { 395 gcov_type count_sum; 396 int n_calls, n_hot_calls, freq_sum; 397 }; 398 399 /* Initialize fields of STAT to zeroes. */ 400 401 static inline void 402 init_caller_stats (struct caller_statistics *stats) 403 { 404 stats->count_sum = 0; 405 stats->n_calls = 0; 406 stats->n_hot_calls = 0; 407 stats->freq_sum = 0; 408 } 409 410 /* Worker callback of cgraph_for_node_and_aliases accumulating statistics of 411 non-thunk incoming edges to NODE. */ 412 413 static bool 414 gather_caller_stats (struct cgraph_node *node, void *data) 415 { 416 struct caller_statistics *stats = (struct caller_statistics *) data; 417 struct cgraph_edge *cs; 418 419 for (cs = node->callers; cs; cs = cs->next_caller) 420 if (cs->caller->thunk.thunk_p) 421 cgraph_for_node_and_aliases (cs->caller, gather_caller_stats, 422 stats, false); 423 else 424 { 425 stats->count_sum += cs->count; 426 stats->freq_sum += cs->frequency; 427 stats->n_calls++; 428 if (cgraph_maybe_hot_edge_p (cs)) 429 stats->n_hot_calls ++; 430 } 431 return false; 432 433 } 434 435 /* Return true if this NODE is viable candidate for cloning. */ 436 437 static bool 438 ipcp_cloning_candidate_p (struct cgraph_node *node) 439 { 440 struct caller_statistics stats; 441 442 gcc_checking_assert (cgraph_function_with_gimple_body_p (node)); 443 444 if (!flag_ipa_cp_clone) 445 { 446 if (dump_file) 447 fprintf (dump_file, "Not considering %s for cloning; " 448 "-fipa-cp-clone disabled.\n", 449 cgraph_node_name (node)); 450 return false; 451 } 452 453 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl))) 454 { 455 if (dump_file) 456 fprintf (dump_file, "Not considering %s for cloning; " 457 "optimizing it for size.\n", 458 cgraph_node_name (node)); 459 return false; 460 } 461 462 init_caller_stats (&stats); 463 cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false); 464 465 if (inline_summary (node)->self_size < stats.n_calls) 466 { 467 if (dump_file) 468 fprintf (dump_file, "Considering %s for cloning; code might shrink.\n", 469 cgraph_node_name (node)); 470 return true; 471 } 472 473 /* When profile is available and function is hot, propagate into it even if 474 calls seems cold; constant propagation can improve function's speed 475 significantly. */ 476 if (max_count) 477 { 478 if (stats.count_sum > node->count * 90 / 100) 479 { 480 if (dump_file) 481 fprintf (dump_file, "Considering %s for cloning; " 482 "usually called directly.\n", 483 cgraph_node_name (node)); 484 return true; 485 } 486 } 487 if (!stats.n_hot_calls) 488 { 489 if (dump_file) 490 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n", 491 cgraph_node_name (node)); 492 return false; 493 } 494 if (dump_file) 495 fprintf (dump_file, "Considering %s for cloning.\n", 496 cgraph_node_name (node)); 497 return true; 498 } 499 500 /* Arrays representing a topological ordering of call graph nodes and a stack 501 of noes used during constant propagation. */ 502 503 struct topo_info 504 { 505 struct cgraph_node **order; 506 struct cgraph_node **stack; 507 int nnodes, stack_top; 508 }; 509 510 /* Allocate the arrays in TOPO and topologically sort the nodes into order. */ 511 512 static void 513 build_toporder_info (struct topo_info *topo) 514 { 515 topo->order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); 516 topo->stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); 517 topo->stack_top = 0; 518 topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL); 519 } 520 521 /* Free information about strongly connected components and the arrays in 522 TOPO. */ 523 524 static void 525 free_toporder_info (struct topo_info *topo) 526 { 527 ipa_free_postorder_info (); 528 free (topo->order); 529 free (topo->stack); 530 } 531 532 /* Add NODE to the stack in TOPO, unless it is already there. */ 533 534 static inline void 535 push_node_to_stack (struct topo_info *topo, struct cgraph_node *node) 536 { 537 struct ipa_node_params *info = IPA_NODE_REF (node); 538 if (info->node_enqueued) 539 return; 540 info->node_enqueued = 1; 541 topo->stack[topo->stack_top++] = node; 542 } 543 544 /* Pop a node from the stack in TOPO and return it or return NULL if the stack 545 is empty. */ 546 547 static struct cgraph_node * 548 pop_node_from_stack (struct topo_info *topo) 549 { 550 if (topo->stack_top) 551 { 552 struct cgraph_node *node; 553 topo->stack_top--; 554 node = topo->stack[topo->stack_top]; 555 IPA_NODE_REF (node)->node_enqueued = 0; 556 return node; 557 } 558 else 559 return NULL; 560 } 561 562 /* Set lattice LAT to bottom and return true if it previously was not set as 563 such. */ 564 565 static inline bool 566 set_lattice_to_bottom (struct ipcp_lattice *lat) 567 { 568 bool ret = !lat->bottom; 569 lat->bottom = true; 570 return ret; 571 } 572 573 /* Mark lattice as containing an unknown value and return true if it previously 574 was not marked as such. */ 575 576 static inline bool 577 set_lattice_contains_variable (struct ipcp_lattice *lat) 578 { 579 bool ret = !lat->contains_variable; 580 lat->contains_variable = true; 581 return ret; 582 } 583 584 /* Initialize ipcp_lattices. */ 585 586 static void 587 initialize_node_lattices (struct cgraph_node *node) 588 { 589 struct ipa_node_params *info = IPA_NODE_REF (node); 590 struct cgraph_edge *ie; 591 bool disable = false, variable = false; 592 int i; 593 594 gcc_checking_assert (cgraph_function_with_gimple_body_p (node)); 595 if (!node->local.local) 596 { 597 /* When cloning is allowed, we can assume that externally visible 598 functions are not called. We will compensate this by cloning 599 later. */ 600 if (ipcp_versionable_function_p (node) 601 && ipcp_cloning_candidate_p (node)) 602 variable = true; 603 else 604 disable = true; 605 } 606 607 if (disable || variable) 608 { 609 for (i = 0; i < ipa_get_param_count (info) ; i++) 610 { 611 struct ipcp_lattice *lat = ipa_get_lattice (info, i); 612 if (disable) 613 set_lattice_to_bottom (lat); 614 else 615 set_lattice_contains_variable (lat); 616 } 617 if (dump_file && (dump_flags & TDF_DETAILS) 618 && node->alias && node->thunk.thunk_p) 619 fprintf (dump_file, "Marking all lattices of %s/%i as %s\n", 620 cgraph_node_name (node), node->uid, 621 disable ? "BOTTOM" : "VARIABLE"); 622 } 623 624 for (ie = node->indirect_calls; ie; ie = ie->next_callee) 625 if (ie->indirect_info->polymorphic) 626 { 627 gcc_checking_assert (ie->indirect_info->param_index >= 0); 628 ipa_get_lattice (info, ie->indirect_info->param_index)->virt_call = 1; 629 } 630 } 631 632 /* Return the result of a (possibly arithmetic) pass through jump function 633 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be 634 determined or itself is considered an interprocedural invariant. */ 635 636 static tree 637 ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input) 638 { 639 tree restype, res; 640 641 gcc_checking_assert (is_gimple_ip_invariant (input)); 642 if (jfunc->value.pass_through.operation == NOP_EXPR) 643 return input; 644 645 if (TREE_CODE_CLASS (jfunc->value.pass_through.operation) 646 == tcc_comparison) 647 restype = boolean_type_node; 648 else 649 restype = TREE_TYPE (input); 650 res = fold_binary (jfunc->value.pass_through.operation, restype, 651 input, jfunc->value.pass_through.operand); 652 653 if (res && !is_gimple_ip_invariant (res)) 654 return NULL_TREE; 655 656 return res; 657 } 658 659 /* Return the result of an ancestor jump function JFUNC on the constant value 660 INPUT. Return NULL_TREE if that cannot be determined. */ 661 662 static tree 663 ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input) 664 { 665 if (TREE_CODE (input) == ADDR_EXPR) 666 { 667 tree t = TREE_OPERAND (input, 0); 668 t = build_ref_for_offset (EXPR_LOCATION (t), t, 669 jfunc->value.ancestor.offset, 670 jfunc->value.ancestor.type, NULL, false); 671 return build_fold_addr_expr (t); 672 } 673 else 674 return NULL_TREE; 675 } 676 677 /* Extract the acual BINFO being described by JFUNC which must be a known type 678 jump function. */ 679 680 static tree 681 ipa_value_from_known_type_jfunc (struct ipa_jump_func *jfunc) 682 { 683 tree base_binfo = TYPE_BINFO (jfunc->value.known_type.base_type); 684 if (!base_binfo) 685 return NULL_TREE; 686 return get_binfo_at_offset (base_binfo, 687 jfunc->value.known_type.offset, 688 jfunc->value.known_type.component_type); 689 } 690 691 /* Determine whether JFUNC evaluates to a known value (that is either a 692 constant or a binfo) and if so, return it. Otherwise return NULL. INFO 693 describes the caller node so that pass-through jump functions can be 694 evaluated. */ 695 696 tree 697 ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc) 698 { 699 if (jfunc->type == IPA_JF_CONST) 700 return jfunc->value.constant; 701 else if (jfunc->type == IPA_JF_KNOWN_TYPE) 702 return ipa_value_from_known_type_jfunc (jfunc); 703 else if (jfunc->type == IPA_JF_PASS_THROUGH 704 || jfunc->type == IPA_JF_ANCESTOR) 705 { 706 tree input; 707 int idx; 708 709 if (jfunc->type == IPA_JF_PASS_THROUGH) 710 idx = jfunc->value.pass_through.formal_id; 711 else 712 idx = jfunc->value.ancestor.formal_id; 713 714 if (info->ipcp_orig_node) 715 input = VEC_index (tree, info->known_vals, idx); 716 else 717 { 718 struct ipcp_lattice *lat; 719 720 if (!info->lattices) 721 { 722 gcc_checking_assert (!flag_ipa_cp); 723 return NULL_TREE; 724 } 725 lat = ipa_get_lattice (info, idx); 726 if (!ipa_lat_is_single_const (lat)) 727 return NULL_TREE; 728 input = lat->values->value; 729 } 730 731 if (!input) 732 return NULL_TREE; 733 734 if (jfunc->type == IPA_JF_PASS_THROUGH) 735 { 736 if (jfunc->value.pass_through.operation == NOP_EXPR) 737 return input; 738 else if (TREE_CODE (input) == TREE_BINFO) 739 return NULL_TREE; 740 else 741 return ipa_get_jf_pass_through_result (jfunc, input); 742 } 743 else 744 { 745 if (TREE_CODE (input) == TREE_BINFO) 746 return get_binfo_at_offset (input, jfunc->value.ancestor.offset, 747 jfunc->value.ancestor.type); 748 else 749 return ipa_get_jf_ancestor_result (jfunc, input); 750 } 751 } 752 else 753 return NULL_TREE; 754 } 755 756 757 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not 758 bottom, not containing a variable component and without any known value at 759 the same time. */ 760 761 DEBUG_FUNCTION void 762 ipcp_verify_propagated_values (void) 763 { 764 struct cgraph_node *node; 765 766 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) 767 { 768 struct ipa_node_params *info = IPA_NODE_REF (node); 769 int i, count = ipa_get_param_count (info); 770 771 for (i = 0; i < count; i++) 772 { 773 struct ipcp_lattice *lat = ipa_get_lattice (info, i); 774 775 if (!lat->bottom 776 && !lat->contains_variable 777 && lat->values_count == 0) 778 { 779 if (dump_file) 780 { 781 fprintf (dump_file, "\nIPA lattices after constant " 782 "propagation:\n"); 783 print_all_lattices (dump_file, true, false); 784 } 785 786 gcc_unreachable (); 787 } 788 } 789 } 790 } 791 792 /* Return true iff X and Y should be considered equal values by IPA-CP. */ 793 794 static bool 795 values_equal_for_ipcp_p (tree x, tree y) 796 { 797 gcc_checking_assert (x != NULL_TREE && y != NULL_TREE); 798 799 if (x == y) 800 return true; 801 802 if (TREE_CODE (x) == TREE_BINFO || TREE_CODE (y) == TREE_BINFO) 803 return false; 804 805 if (TREE_CODE (x) == ADDR_EXPR 806 && TREE_CODE (y) == ADDR_EXPR 807 && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL 808 && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL) 809 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)), 810 DECL_INITIAL (TREE_OPERAND (y, 0)), 0); 811 else 812 return operand_equal_p (x, y, 0); 813 } 814 815 /* Add a new value source to VAL, marking that a value comes from edge CS and 816 (if the underlying jump function is a pass-through or an ancestor one) from 817 a caller value SRC_VAL of a caller parameter described by SRC_INDEX. */ 818 819 static void 820 add_value_source (struct ipcp_value *val, struct cgraph_edge *cs, 821 struct ipcp_value *src_val, int src_idx) 822 { 823 struct ipcp_value_source *src; 824 825 src = (struct ipcp_value_source *) pool_alloc (ipcp_sources_pool); 826 src->cs = cs; 827 src->val = src_val; 828 src->index = src_idx; 829 830 src->next = val->sources; 831 val->sources = src; 832 } 833 834 835 /* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for 836 it. CS, SRC_VAL and SRC_INDEX are meant for add_value_source and have the 837 same meaning. */ 838 839 static bool 840 add_value_to_lattice (struct ipcp_lattice *lat, tree newval, 841 struct cgraph_edge *cs, struct ipcp_value *src_val, 842 int src_idx) 843 { 844 struct ipcp_value *val; 845 846 if (lat->bottom) 847 return false; 848 849 850 for (val = lat->values; val; val = val->next) 851 if (values_equal_for_ipcp_p (val->value, newval)) 852 { 853 if (edge_within_scc (cs)) 854 { 855 struct ipcp_value_source *s; 856 for (s = val->sources; s ; s = s->next) 857 if (s->cs == cs) 858 break; 859 if (s) 860 return false; 861 } 862 863 add_value_source (val, cs, src_val, src_idx); 864 return false; 865 } 866 867 if (lat->values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE)) 868 { 869 /* We can only free sources, not the values themselves, because sources 870 of other values in this this SCC might point to them. */ 871 for (val = lat->values; val; val = val->next) 872 { 873 while (val->sources) 874 { 875 struct ipcp_value_source *src = val->sources; 876 val->sources = src->next; 877 pool_free (ipcp_sources_pool, src); 878 } 879 } 880 881 lat->values = NULL; 882 return set_lattice_to_bottom (lat); 883 } 884 885 lat->values_count++; 886 val = (struct ipcp_value *) pool_alloc (ipcp_values_pool); 887 memset (val, 0, sizeof (*val)); 888 889 add_value_source (val, cs, src_val, src_idx); 890 val->value = newval; 891 val->next = lat->values; 892 lat->values = val; 893 return true; 894 } 895 896 /* Propagate values through a pass-through jump function JFUNC associated with 897 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX 898 is the index of the source parameter. */ 899 900 static bool 901 propagate_vals_accross_pass_through (struct cgraph_edge *cs, 902 struct ipa_jump_func *jfunc, 903 struct ipcp_lattice *src_lat, 904 struct ipcp_lattice *dest_lat, 905 int src_idx) 906 { 907 struct ipcp_value *src_val; 908 bool ret = false; 909 910 if (jfunc->value.pass_through.operation == NOP_EXPR) 911 for (src_val = src_lat->values; src_val; src_val = src_val->next) 912 ret |= add_value_to_lattice (dest_lat, src_val->value, cs, 913 src_val, src_idx); 914 /* Do not create new values when propagating within an SCC because if there 915 arithmetic functions with circular dependencies, there is infinite number 916 of them and we would just make lattices bottom. */ 917 else if (edge_within_scc (cs)) 918 ret = set_lattice_contains_variable (dest_lat); 919 else 920 for (src_val = src_lat->values; src_val; src_val = src_val->next) 921 { 922 tree cstval = src_val->value; 923 924 if (TREE_CODE (cstval) == TREE_BINFO) 925 { 926 ret |= set_lattice_contains_variable (dest_lat); 927 continue; 928 } 929 cstval = ipa_get_jf_pass_through_result (jfunc, cstval); 930 931 if (cstval) 932 ret |= add_value_to_lattice (dest_lat, cstval, cs, src_val, src_idx); 933 else 934 ret |= set_lattice_contains_variable (dest_lat); 935 } 936 937 return ret; 938 } 939 940 /* Propagate values through an ancestor jump function JFUNC associated with 941 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX 942 is the index of the source parameter. */ 943 944 static bool 945 propagate_vals_accross_ancestor (struct cgraph_edge *cs, 946 struct ipa_jump_func *jfunc, 947 struct ipcp_lattice *src_lat, 948 struct ipcp_lattice *dest_lat, 949 int src_idx) 950 { 951 struct ipcp_value *src_val; 952 bool ret = false; 953 954 if (edge_within_scc (cs)) 955 return set_lattice_contains_variable (dest_lat); 956 957 for (src_val = src_lat->values; src_val; src_val = src_val->next) 958 { 959 tree t = src_val->value; 960 961 if (TREE_CODE (t) == TREE_BINFO) 962 t = get_binfo_at_offset (t, jfunc->value.ancestor.offset, 963 jfunc->value.ancestor.type); 964 else 965 t = ipa_get_jf_ancestor_result (jfunc, t); 966 967 if (t) 968 ret |= add_value_to_lattice (dest_lat, t, cs, src_val, src_idx); 969 else 970 ret |= set_lattice_contains_variable (dest_lat); 971 } 972 973 return ret; 974 } 975 976 /* Propagate values across jump function JFUNC that is associated with edge CS 977 and put the values into DEST_LAT. */ 978 979 static bool 980 propagate_accross_jump_function (struct cgraph_edge *cs, 981 struct ipa_jump_func *jfunc, 982 struct ipcp_lattice *dest_lat) 983 { 984 if (dest_lat->bottom) 985 return false; 986 987 if (jfunc->type == IPA_JF_CONST 988 || jfunc->type == IPA_JF_KNOWN_TYPE) 989 { 990 tree val; 991 992 if (jfunc->type == IPA_JF_KNOWN_TYPE) 993 { 994 val = ipa_value_from_known_type_jfunc (jfunc); 995 if (!val) 996 return set_lattice_contains_variable (dest_lat); 997 } 998 else 999 val = jfunc->value.constant; 1000 return add_value_to_lattice (dest_lat, val, cs, NULL, 0); 1001 } 1002 else if (jfunc->type == IPA_JF_PASS_THROUGH 1003 || jfunc->type == IPA_JF_ANCESTOR) 1004 { 1005 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); 1006 struct ipcp_lattice *src_lat; 1007 int src_idx; 1008 bool ret; 1009 1010 if (jfunc->type == IPA_JF_PASS_THROUGH) 1011 src_idx = jfunc->value.pass_through.formal_id; 1012 else 1013 src_idx = jfunc->value.ancestor.formal_id; 1014 1015 src_lat = ipa_get_lattice (caller_info, src_idx); 1016 if (src_lat->bottom) 1017 return set_lattice_contains_variable (dest_lat); 1018 1019 /* If we would need to clone the caller and cannot, do not propagate. */ 1020 if (!ipcp_versionable_function_p (cs->caller) 1021 && (src_lat->contains_variable 1022 || (src_lat->values_count > 1))) 1023 return set_lattice_contains_variable (dest_lat); 1024 1025 if (jfunc->type == IPA_JF_PASS_THROUGH) 1026 ret = propagate_vals_accross_pass_through (cs, jfunc, src_lat, 1027 dest_lat, src_idx); 1028 else 1029 ret = propagate_vals_accross_ancestor (cs, jfunc, src_lat, dest_lat, 1030 src_idx); 1031 1032 if (src_lat->contains_variable) 1033 ret |= set_lattice_contains_variable (dest_lat); 1034 1035 return ret; 1036 } 1037 1038 /* TODO: We currently do not handle member method pointers in IPA-CP (we only 1039 use it for indirect inlining), we should propagate them too. */ 1040 return set_lattice_contains_variable (dest_lat); 1041 } 1042 1043 /* Propagate constants from the caller to the callee of CS. INFO describes the 1044 caller. */ 1045 1046 static bool 1047 propagate_constants_accross_call (struct cgraph_edge *cs) 1048 { 1049 struct ipa_node_params *callee_info; 1050 enum availability availability; 1051 struct cgraph_node *callee, *alias_or_thunk; 1052 struct ipa_edge_args *args; 1053 bool ret = false; 1054 int i, args_count, parms_count; 1055 1056 callee = cgraph_function_node (cs->callee, &availability); 1057 if (!callee->analyzed) 1058 return false; 1059 gcc_checking_assert (cgraph_function_with_gimple_body_p (callee)); 1060 callee_info = IPA_NODE_REF (callee); 1061 1062 args = IPA_EDGE_REF (cs); 1063 args_count = ipa_get_cs_argument_count (args); 1064 parms_count = ipa_get_param_count (callee_info); 1065 1066 /* If this call goes through a thunk we should not propagate because we 1067 cannot redirect edges to thunks. However, we might need to uncover a 1068 thunk from below a series of aliases first. */ 1069 alias_or_thunk = cs->callee; 1070 while (alias_or_thunk->alias) 1071 alias_or_thunk = cgraph_alias_aliased_node (alias_or_thunk); 1072 if (alias_or_thunk->thunk.thunk_p) 1073 { 1074 for (i = 0; i < parms_count; i++) 1075 ret |= set_lattice_contains_variable (ipa_get_lattice (callee_info, i)); 1076 1077 return ret; 1078 } 1079 1080 for (i = 0; (i < args_count) && (i < parms_count); i++) 1081 { 1082 struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i); 1083 struct ipcp_lattice *dest_lat = ipa_get_lattice (callee_info, i); 1084 1085 if (availability == AVAIL_OVERWRITABLE) 1086 ret |= set_lattice_contains_variable (dest_lat); 1087 else 1088 ret |= propagate_accross_jump_function (cs, jump_func, dest_lat); 1089 } 1090 for (; i < parms_count; i++) 1091 ret |= set_lattice_contains_variable (ipa_get_lattice (callee_info, i)); 1092 1093 return ret; 1094 } 1095 1096 /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS 1097 (which can contain both constants and binfos) or KNOWN_BINFOS (which can be 1098 NULL) return the destination. */ 1099 1100 tree 1101 ipa_get_indirect_edge_target (struct cgraph_edge *ie, 1102 VEC (tree, heap) *known_vals, 1103 VEC (tree, heap) *known_binfos) 1104 { 1105 int param_index = ie->indirect_info->param_index; 1106 HOST_WIDE_INT token, anc_offset; 1107 tree otr_type; 1108 tree t; 1109 1110 if (param_index == -1) 1111 return NULL_TREE; 1112 1113 if (!ie->indirect_info->polymorphic) 1114 { 1115 tree t = (VEC_length (tree, known_vals) > (unsigned int) param_index 1116 ? VEC_index (tree, known_vals, param_index) : NULL); 1117 if (t && 1118 TREE_CODE (t) == ADDR_EXPR 1119 && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL) 1120 return TREE_OPERAND (t, 0); 1121 else 1122 return NULL_TREE; 1123 } 1124 1125 token = ie->indirect_info->otr_token; 1126 anc_offset = ie->indirect_info->anc_offset; 1127 otr_type = ie->indirect_info->otr_type; 1128 1129 t = VEC_index (tree, known_vals, param_index); 1130 if (!t && known_binfos 1131 && VEC_length (tree, known_binfos) > (unsigned int) param_index) 1132 t = VEC_index (tree, known_binfos, param_index); 1133 if (!t) 1134 return NULL_TREE; 1135 1136 if (TREE_CODE (t) != TREE_BINFO) 1137 { 1138 tree binfo; 1139 binfo = gimple_extract_devirt_binfo_from_cst (t); 1140 if (!binfo) 1141 return NULL_TREE; 1142 binfo = get_binfo_at_offset (binfo, anc_offset, otr_type); 1143 if (!binfo) 1144 return NULL_TREE; 1145 return gimple_get_virt_method_for_binfo (token, binfo); 1146 } 1147 else 1148 { 1149 tree binfo; 1150 1151 binfo = get_binfo_at_offset (t, anc_offset, otr_type); 1152 if (!binfo) 1153 return NULL_TREE; 1154 return gimple_get_virt_method_for_binfo (token, binfo); 1155 } 1156 } 1157 1158 /* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS 1159 and KNOWN_BINFOS. */ 1160 1161 static int 1162 devirtualization_time_bonus (struct cgraph_node *node, 1163 VEC (tree, heap) *known_csts, 1164 VEC (tree, heap) *known_binfos) 1165 { 1166 struct cgraph_edge *ie; 1167 int res = 0; 1168 1169 for (ie = node->indirect_calls; ie; ie = ie->next_callee) 1170 { 1171 struct cgraph_node *callee; 1172 struct inline_summary *isummary; 1173 tree target; 1174 1175 target = ipa_get_indirect_edge_target (ie, known_csts, known_binfos); 1176 if (!target) 1177 continue; 1178 1179 /* Only bare minimum benefit for clearly un-inlineable targets. */ 1180 res += 1; 1181 callee = cgraph_get_node (target); 1182 if (!callee || !callee->analyzed) 1183 continue; 1184 isummary = inline_summary (callee); 1185 if (!isummary->inlinable) 1186 continue; 1187 1188 /* FIXME: The values below need re-considering and perhaps also 1189 integrating into the cost metrics, at lest in some very basic way. */ 1190 if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4) 1191 res += 31; 1192 else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2) 1193 res += 15; 1194 else if (isummary->size <= MAX_INLINE_INSNS_AUTO 1195 || DECL_DECLARED_INLINE_P (callee->decl)) 1196 res += 7; 1197 } 1198 1199 return res; 1200 } 1201 1202 /* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT 1203 and SIZE_COST and with the sum of frequencies of incoming edges to the 1204 potential new clone in FREQUENCIES. */ 1205 1206 static bool 1207 good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit, 1208 int freq_sum, gcov_type count_sum, int size_cost) 1209 { 1210 if (time_benefit == 0 1211 || !flag_ipa_cp_clone 1212 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl))) 1213 return false; 1214 1215 gcc_assert (size_cost > 0); 1216 1217 if (max_count) 1218 { 1219 int factor = (count_sum * 1000) / max_count; 1220 HOST_WIDEST_INT evaluation = (((HOST_WIDEST_INT) time_benefit * factor) 1221 / size_cost); 1222 1223 if (dump_file && (dump_flags & TDF_DETAILS)) 1224 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, " 1225 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC 1226 ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC 1227 ", threshold: %i\n", 1228 time_benefit, size_cost, (HOST_WIDE_INT) count_sum, 1229 evaluation, 500); 1230 1231 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD); 1232 } 1233 else 1234 { 1235 HOST_WIDEST_INT evaluation = (((HOST_WIDEST_INT) time_benefit * freq_sum) 1236 / size_cost); 1237 1238 if (dump_file && (dump_flags & TDF_DETAILS)) 1239 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, " 1240 "size: %i, freq_sum: %i) -> evaluation: " 1241 HOST_WIDEST_INT_PRINT_DEC ", threshold: %i\n", 1242 time_benefit, size_cost, freq_sum, evaluation, 1243 CGRAPH_FREQ_BASE /2); 1244 1245 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD); 1246 } 1247 } 1248 1249 1250 /* Allocate KNOWN_CSTS and KNOWN_BINFOS and populate them with values of 1251 parameters that are known independent of the context. INFO describes the 1252 function. If REMOVABLE_PARAMS_COST is non-NULL, the movement cost of all 1253 removable parameters will be stored in it. */ 1254 1255 static bool 1256 gather_context_independent_values (struct ipa_node_params *info, 1257 VEC (tree, heap) **known_csts, 1258 VEC (tree, heap) **known_binfos, 1259 int *removable_params_cost) 1260 { 1261 int i, count = ipa_get_param_count (info); 1262 bool ret = false; 1263 1264 *known_csts = NULL; 1265 *known_binfos = NULL; 1266 VEC_safe_grow_cleared (tree, heap, *known_csts, count); 1267 VEC_safe_grow_cleared (tree, heap, *known_binfos, count); 1268 1269 if (removable_params_cost) 1270 *removable_params_cost = 0; 1271 1272 for (i = 0; i < count ; i++) 1273 { 1274 struct ipcp_lattice *lat = ipa_get_lattice (info, i); 1275 1276 if (ipa_lat_is_single_const (lat)) 1277 { 1278 struct ipcp_value *val = lat->values; 1279 if (TREE_CODE (val->value) != TREE_BINFO) 1280 { 1281 VEC_replace (tree, *known_csts, i, val->value); 1282 if (removable_params_cost) 1283 *removable_params_cost 1284 += estimate_move_cost (TREE_TYPE (val->value)); 1285 ret = true; 1286 } 1287 else if (lat->virt_call) 1288 { 1289 VEC_replace (tree, *known_binfos, i, val->value); 1290 ret = true; 1291 } 1292 else if (removable_params_cost 1293 && !ipa_is_param_used (info, i)) 1294 *removable_params_cost 1295 += estimate_move_cost (TREE_TYPE (ipa_get_param (info, i))); 1296 } 1297 else if (removable_params_cost 1298 && !ipa_is_param_used (info, i)) 1299 *removable_params_cost 1300 += estimate_move_cost (TREE_TYPE (ipa_get_param (info, i))); 1301 } 1302 1303 return ret; 1304 } 1305 1306 /* Iterate over known values of parameters of NODE and estimate the local 1307 effects in terms of time and size they have. */ 1308 1309 static void 1310 estimate_local_effects (struct cgraph_node *node) 1311 { 1312 struct ipa_node_params *info = IPA_NODE_REF (node); 1313 int i, count = ipa_get_param_count (info); 1314 VEC (tree, heap) *known_csts, *known_binfos; 1315 bool always_const; 1316 int base_time = inline_summary (node)->time; 1317 int removable_params_cost; 1318 1319 if (!count || !ipcp_versionable_function_p (node)) 1320 return; 1321 1322 if (dump_file && (dump_flags & TDF_DETAILS)) 1323 fprintf (dump_file, "\nEstimating effects for %s/%i, base_time: %i.\n", 1324 cgraph_node_name (node), node->uid, base_time); 1325 1326 always_const = gather_context_independent_values (info, &known_csts, 1327 &known_binfos, 1328 &removable_params_cost); 1329 if (always_const) 1330 { 1331 struct caller_statistics stats; 1332 int time, size; 1333 1334 init_caller_stats (&stats); 1335 cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false); 1336 estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos, 1337 &size, &time); 1338 time -= devirtualization_time_bonus (node, known_csts, known_binfos); 1339 time -= removable_params_cost; 1340 size -= stats.n_calls * removable_params_cost; 1341 1342 if (dump_file) 1343 fprintf (dump_file, " - context independent values, size: %i, " 1344 "time_benefit: %i\n", size, base_time - time); 1345 1346 if (size <= 0 1347 || cgraph_will_be_removed_from_program_if_no_direct_calls (node)) 1348 { 1349 info->clone_for_all_contexts = true; 1350 base_time = time; 1351 1352 if (dump_file) 1353 fprintf (dump_file, " Decided to specialize for all " 1354 "known contexts, code not going to grow.\n"); 1355 } 1356 else if (good_cloning_opportunity_p (node, base_time - time, 1357 stats.freq_sum, stats.count_sum, 1358 size)) 1359 { 1360 if (size + overall_size <= max_new_size) 1361 { 1362 info->clone_for_all_contexts = true; 1363 base_time = time; 1364 overall_size += size; 1365 1366 if (dump_file) 1367 fprintf (dump_file, " Decided to specialize for all " 1368 "known contexts, growth deemed beneficial.\n"); 1369 } 1370 else if (dump_file && (dump_flags & TDF_DETAILS)) 1371 fprintf (dump_file, " Not cloning for all contexts because " 1372 "max_new_size would be reached with %li.\n", 1373 size + overall_size); 1374 } 1375 } 1376 1377 for (i = 0; i < count ; i++) 1378 { 1379 struct ipcp_lattice *lat = ipa_get_lattice (info, i); 1380 struct ipcp_value *val; 1381 int emc; 1382 1383 if (lat->bottom 1384 || !lat->values 1385 || VEC_index (tree, known_csts, i) 1386 || VEC_index (tree, known_binfos, i)) 1387 continue; 1388 1389 for (val = lat->values; val; val = val->next) 1390 { 1391 int time, size, time_benefit; 1392 1393 if (TREE_CODE (val->value) != TREE_BINFO) 1394 { 1395 VEC_replace (tree, known_csts, i, val->value); 1396 VEC_replace (tree, known_binfos, i, NULL_TREE); 1397 emc = estimate_move_cost (TREE_TYPE (val->value)); 1398 } 1399 else if (lat->virt_call) 1400 { 1401 VEC_replace (tree, known_csts, i, NULL_TREE); 1402 VEC_replace (tree, known_binfos, i, val->value); 1403 emc = 0; 1404 } 1405 else 1406 continue; 1407 1408 estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos, 1409 &size, &time); 1410 time_benefit = base_time - time 1411 + devirtualization_time_bonus (node, known_csts, known_binfos) 1412 + removable_params_cost + emc; 1413 1414 gcc_checking_assert (size >=0); 1415 /* The inliner-heuristics based estimates may think that in certain 1416 contexts some functions do not have any size at all but we want 1417 all specializations to have at least a tiny cost, not least not to 1418 divide by zero. */ 1419 if (size == 0) 1420 size = 1; 1421 1422 if (dump_file && (dump_flags & TDF_DETAILS)) 1423 { 1424 fprintf (dump_file, " - estimates for value "); 1425 print_ipcp_constant_value (dump_file, val->value); 1426 fprintf (dump_file, " for parameter "); 1427 print_generic_expr (dump_file, ipa_get_param (info, i), 0); 1428 fprintf (dump_file, ": time_benefit: %i, size: %i\n", 1429 time_benefit, size); 1430 } 1431 1432 val->local_time_benefit = time_benefit; 1433 val->local_size_cost = size; 1434 } 1435 } 1436 1437 VEC_free (tree, heap, known_csts); 1438 VEC_free (tree, heap, known_binfos); 1439 } 1440 1441 1442 /* Add value CUR_VAL and all yet-unsorted values it is dependent on to the 1443 topological sort of values. */ 1444 1445 static void 1446 add_val_to_toposort (struct ipcp_value *cur_val) 1447 { 1448 static int dfs_counter = 0; 1449 static struct ipcp_value *stack; 1450 struct ipcp_value_source *src; 1451 1452 if (cur_val->dfs) 1453 return; 1454 1455 dfs_counter++; 1456 cur_val->dfs = dfs_counter; 1457 cur_val->low_link = dfs_counter; 1458 1459 cur_val->topo_next = stack; 1460 stack = cur_val; 1461 cur_val->on_stack = true; 1462 1463 for (src = cur_val->sources; src; src = src->next) 1464 if (src->val) 1465 { 1466 if (src->val->dfs == 0) 1467 { 1468 add_val_to_toposort (src->val); 1469 if (src->val->low_link < cur_val->low_link) 1470 cur_val->low_link = src->val->low_link; 1471 } 1472 else if (src->val->on_stack 1473 && src->val->dfs < cur_val->low_link) 1474 cur_val->low_link = src->val->dfs; 1475 } 1476 1477 if (cur_val->dfs == cur_val->low_link) 1478 { 1479 struct ipcp_value *v, *scc_list = NULL; 1480 1481 do 1482 { 1483 v = stack; 1484 stack = v->topo_next; 1485 v->on_stack = false; 1486 1487 v->scc_next = scc_list; 1488 scc_list = v; 1489 } 1490 while (v != cur_val); 1491 1492 cur_val->topo_next = values_topo; 1493 values_topo = cur_val; 1494 } 1495 } 1496 1497 /* Add all values in lattices associated with NODE to the topological sort if 1498 they are not there yet. */ 1499 1500 static void 1501 add_all_node_vals_to_toposort (struct cgraph_node *node) 1502 { 1503 struct ipa_node_params *info = IPA_NODE_REF (node); 1504 int i, count = ipa_get_param_count (info); 1505 1506 for (i = 0; i < count ; i++) 1507 { 1508 struct ipcp_lattice *lat = ipa_get_lattice (info, i); 1509 struct ipcp_value *val; 1510 1511 if (lat->bottom || !lat->values) 1512 continue; 1513 for (val = lat->values; val; val = val->next) 1514 add_val_to_toposort (val); 1515 } 1516 } 1517 1518 /* One pass of constants propagation along the call graph edges, from callers 1519 to callees (requires topological ordering in TOPO), iterate over strongly 1520 connected components. */ 1521 1522 static void 1523 propagate_constants_topo (struct topo_info *topo) 1524 { 1525 int i; 1526 1527 for (i = topo->nnodes - 1; i >= 0; i--) 1528 { 1529 struct cgraph_node *v, *node = topo->order[i]; 1530 struct ipa_dfs_info *node_dfs_info; 1531 1532 if (!cgraph_function_with_gimple_body_p (node)) 1533 continue; 1534 1535 node_dfs_info = (struct ipa_dfs_info *) node->aux; 1536 /* First, iteratively propagate within the strongly connected component 1537 until all lattices stabilize. */ 1538 v = node_dfs_info->next_cycle; 1539 while (v) 1540 { 1541 push_node_to_stack (topo, v); 1542 v = ((struct ipa_dfs_info *) v->aux)->next_cycle; 1543 } 1544 1545 v = node; 1546 while (v) 1547 { 1548 struct cgraph_edge *cs; 1549 1550 for (cs = v->callees; cs; cs = cs->next_callee) 1551 if (edge_within_scc (cs) 1552 && propagate_constants_accross_call (cs)) 1553 push_node_to_stack (topo, cs->callee); 1554 v = pop_node_from_stack (topo); 1555 } 1556 1557 /* Afterwards, propagate along edges leading out of the SCC, calculates 1558 the local effects of the discovered constants and all valid values to 1559 their topological sort. */ 1560 v = node; 1561 while (v) 1562 { 1563 struct cgraph_edge *cs; 1564 1565 estimate_local_effects (v); 1566 add_all_node_vals_to_toposort (v); 1567 for (cs = v->callees; cs; cs = cs->next_callee) 1568 if (!edge_within_scc (cs)) 1569 propagate_constants_accross_call (cs); 1570 1571 v = ((struct ipa_dfs_info *) v->aux)->next_cycle; 1572 } 1573 } 1574 } 1575 1576 1577 /* Return the sum of A and B if none of them is bigger than INT_MAX/2, return 1578 the bigger one if otherwise. */ 1579 1580 static int 1581 safe_add (int a, int b) 1582 { 1583 if (a > INT_MAX/2 || b > INT_MAX/2) 1584 return a > b ? a : b; 1585 else 1586 return a + b; 1587 } 1588 1589 1590 /* Propagate the estimated effects of individual values along the topological 1591 from the dependant values to those they depend on. */ 1592 1593 static void 1594 propagate_effects (void) 1595 { 1596 struct ipcp_value *base; 1597 1598 for (base = values_topo; base; base = base->topo_next) 1599 { 1600 struct ipcp_value_source *src; 1601 struct ipcp_value *val; 1602 int time = 0, size = 0; 1603 1604 for (val = base; val; val = val->scc_next) 1605 { 1606 time = safe_add (time, 1607 val->local_time_benefit + val->prop_time_benefit); 1608 size = safe_add (size, val->local_size_cost + val->prop_size_cost); 1609 } 1610 1611 for (val = base; val; val = val->scc_next) 1612 for (src = val->sources; src; src = src->next) 1613 if (src->val 1614 && cgraph_maybe_hot_edge_p (src->cs)) 1615 { 1616 src->val->prop_time_benefit = safe_add (time, 1617 src->val->prop_time_benefit); 1618 src->val->prop_size_cost = safe_add (size, 1619 src->val->prop_size_cost); 1620 } 1621 } 1622 } 1623 1624 1625 /* Propagate constants, binfos and their effects from the summaries 1626 interprocedurally. */ 1627 1628 static void 1629 ipcp_propagate_stage (struct topo_info *topo) 1630 { 1631 struct cgraph_node *node; 1632 1633 if (dump_file) 1634 fprintf (dump_file, "\n Propagating constants:\n\n"); 1635 1636 if (in_lto_p) 1637 ipa_update_after_lto_read (); 1638 1639 1640 FOR_EACH_DEFINED_FUNCTION (node) 1641 { 1642 struct ipa_node_params *info = IPA_NODE_REF (node); 1643 1644 determine_versionability (node); 1645 if (cgraph_function_with_gimple_body_p (node)) 1646 { 1647 info->lattices = XCNEWVEC (struct ipcp_lattice, 1648 ipa_get_param_count (info)); 1649 initialize_node_lattices (node); 1650 } 1651 if (node->count > max_count) 1652 max_count = node->count; 1653 overall_size += inline_summary (node)->self_size; 1654 } 1655 1656 max_new_size = overall_size; 1657 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS)) 1658 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS); 1659 max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1; 1660 1661 if (dump_file) 1662 fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n", 1663 overall_size, max_new_size); 1664 1665 propagate_constants_topo (topo); 1666 #ifdef ENABLE_CHECKING 1667 ipcp_verify_propagated_values (); 1668 #endif 1669 propagate_effects (); 1670 1671 if (dump_file) 1672 { 1673 fprintf (dump_file, "\nIPA lattices after all propagation:\n"); 1674 print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true); 1675 } 1676 } 1677 1678 /* Discover newly direct outgoing edges from NODE which is a new clone with 1679 known KNOWN_VALS and make them direct. */ 1680 1681 static void 1682 ipcp_discover_new_direct_edges (struct cgraph_node *node, 1683 VEC (tree, heap) *known_vals) 1684 { 1685 struct cgraph_edge *ie, *next_ie; 1686 1687 for (ie = node->indirect_calls; ie; ie = next_ie) 1688 { 1689 tree target; 1690 1691 next_ie = ie->next_callee; 1692 target = ipa_get_indirect_edge_target (ie, known_vals, NULL); 1693 if (target) 1694 ipa_make_edge_direct_to_target (ie, target); 1695 } 1696 } 1697 1698 /* Vector of pointers which for linked lists of clones of an original crgaph 1699 edge. */ 1700 1701 static VEC (cgraph_edge_p, heap) *next_edge_clone; 1702 1703 static inline void 1704 grow_next_edge_clone_vector (void) 1705 { 1706 if (VEC_length (cgraph_edge_p, next_edge_clone) 1707 <= (unsigned) cgraph_edge_max_uid) 1708 VEC_safe_grow_cleared (cgraph_edge_p, heap, next_edge_clone, 1709 cgraph_edge_max_uid + 1); 1710 } 1711 1712 /* Edge duplication hook to grow the appropriate linked list in 1713 next_edge_clone. */ 1714 1715 static void 1716 ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst, 1717 __attribute__((unused)) void *data) 1718 { 1719 grow_next_edge_clone_vector (); 1720 VEC_replace (cgraph_edge_p, next_edge_clone, dst->uid, 1721 VEC_index (cgraph_edge_p, next_edge_clone, src->uid)); 1722 VEC_replace (cgraph_edge_p, next_edge_clone, src->uid, dst); 1723 } 1724 1725 /* Get the next clone in the linked list of clones of an edge. */ 1726 1727 static inline struct cgraph_edge * 1728 get_next_cgraph_edge_clone (struct cgraph_edge *cs) 1729 { 1730 return VEC_index (cgraph_edge_p, next_edge_clone, cs->uid); 1731 } 1732 1733 /* Return true if edge CS does bring about the value described by SRC. */ 1734 1735 static bool 1736 cgraph_edge_brings_value_p (struct cgraph_edge *cs, 1737 struct ipcp_value_source *src) 1738 { 1739 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); 1740 1741 if (IPA_NODE_REF (cs->callee)->ipcp_orig_node 1742 || caller_info->node_dead) 1743 return false; 1744 if (!src->val) 1745 return true; 1746 1747 if (caller_info->ipcp_orig_node) 1748 { 1749 tree t = VEC_index (tree, caller_info->known_vals, src->index); 1750 return (t != NULL_TREE 1751 && values_equal_for_ipcp_p (src->val->value, t)); 1752 } 1753 else 1754 { 1755 struct ipcp_lattice *lat = ipa_get_lattice (caller_info, src->index); 1756 if (ipa_lat_is_single_const (lat) 1757 && values_equal_for_ipcp_p (src->val->value, lat->values->value)) 1758 return true; 1759 else 1760 return false; 1761 } 1762 } 1763 1764 /* Given VAL, iterate over all its sources and if they still hold, add their 1765 edge frequency and their number into *FREQUENCY and *CALLER_COUNT 1766 respectively. */ 1767 1768 static bool 1769 get_info_about_necessary_edges (struct ipcp_value *val, int *freq_sum, 1770 gcov_type *count_sum, int *caller_count) 1771 { 1772 struct ipcp_value_source *src; 1773 int freq = 0, count = 0; 1774 gcov_type cnt = 0; 1775 bool hot = false; 1776 1777 for (src = val->sources; src; src = src->next) 1778 { 1779 struct cgraph_edge *cs = src->cs; 1780 while (cs) 1781 { 1782 if (cgraph_edge_brings_value_p (cs, src)) 1783 { 1784 count++; 1785 freq += cs->frequency; 1786 cnt += cs->count; 1787 hot |= cgraph_maybe_hot_edge_p (cs); 1788 } 1789 cs = get_next_cgraph_edge_clone (cs); 1790 } 1791 } 1792 1793 *freq_sum = freq; 1794 *count_sum = cnt; 1795 *caller_count = count; 1796 return hot; 1797 } 1798 1799 /* Return a vector of incoming edges that do bring value VAL. It is assumed 1800 their number is known and equal to CALLER_COUNT. */ 1801 1802 static VEC (cgraph_edge_p,heap) * 1803 gather_edges_for_value (struct ipcp_value *val, int caller_count) 1804 { 1805 struct ipcp_value_source *src; 1806 VEC (cgraph_edge_p,heap) *ret; 1807 1808 ret = VEC_alloc (cgraph_edge_p, heap, caller_count); 1809 for (src = val->sources; src; src = src->next) 1810 { 1811 struct cgraph_edge *cs = src->cs; 1812 while (cs) 1813 { 1814 if (cgraph_edge_brings_value_p (cs, src)) 1815 VEC_quick_push (cgraph_edge_p, ret, cs); 1816 cs = get_next_cgraph_edge_clone (cs); 1817 } 1818 } 1819 1820 return ret; 1821 } 1822 1823 /* Construct a replacement map for a know VALUE for a formal parameter PARAM. 1824 Return it or NULL if for some reason it cannot be created. */ 1825 1826 static struct ipa_replace_map * 1827 get_replacement_map (tree value, tree parm) 1828 { 1829 tree req_type = TREE_TYPE (parm); 1830 struct ipa_replace_map *replace_map; 1831 1832 if (!useless_type_conversion_p (req_type, TREE_TYPE (value))) 1833 { 1834 if (fold_convertible_p (req_type, value)) 1835 value = fold_build1 (NOP_EXPR, req_type, value); 1836 else if (TYPE_SIZE (req_type) == TYPE_SIZE (TREE_TYPE (value))) 1837 value = fold_build1 (VIEW_CONVERT_EXPR, req_type, value); 1838 else 1839 { 1840 if (dump_file) 1841 { 1842 fprintf (dump_file, " const "); 1843 print_generic_expr (dump_file, value, 0); 1844 fprintf (dump_file, " can't be converted to param "); 1845 print_generic_expr (dump_file, parm, 0); 1846 fprintf (dump_file, "\n"); 1847 } 1848 return NULL; 1849 } 1850 } 1851 1852 replace_map = ggc_alloc_ipa_replace_map (); 1853 if (dump_file) 1854 { 1855 fprintf (dump_file, " replacing param "); 1856 print_generic_expr (dump_file, parm, 0); 1857 fprintf (dump_file, " with const "); 1858 print_generic_expr (dump_file, value, 0); 1859 fprintf (dump_file, "\n"); 1860 } 1861 replace_map->old_tree = parm; 1862 replace_map->new_tree = value; 1863 replace_map->replace_p = true; 1864 replace_map->ref_p = false; 1865 1866 return replace_map; 1867 } 1868 1869 /* Dump new profiling counts */ 1870 1871 static void 1872 dump_profile_updates (struct cgraph_node *orig_node, 1873 struct cgraph_node *new_node) 1874 { 1875 struct cgraph_edge *cs; 1876 1877 fprintf (dump_file, " setting count of the specialized node to " 1878 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) new_node->count); 1879 for (cs = new_node->callees; cs ; cs = cs->next_callee) 1880 fprintf (dump_file, " edge to %s has count " 1881 HOST_WIDE_INT_PRINT_DEC "\n", 1882 cgraph_node_name (cs->callee), (HOST_WIDE_INT) cs->count); 1883 1884 fprintf (dump_file, " setting count of the original node to " 1885 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) orig_node->count); 1886 for (cs = orig_node->callees; cs ; cs = cs->next_callee) 1887 fprintf (dump_file, " edge to %s is left with " 1888 HOST_WIDE_INT_PRINT_DEC "\n", 1889 cgraph_node_name (cs->callee), (HOST_WIDE_INT) cs->count); 1890 } 1891 1892 /* After a specialized NEW_NODE version of ORIG_NODE has been created, update 1893 their profile information to reflect this. */ 1894 1895 static void 1896 update_profiling_info (struct cgraph_node *orig_node, 1897 struct cgraph_node *new_node) 1898 { 1899 struct cgraph_edge *cs; 1900 struct caller_statistics stats; 1901 gcov_type new_sum, orig_sum; 1902 gcov_type remainder, orig_node_count = orig_node->count; 1903 1904 if (orig_node_count == 0) 1905 return; 1906 1907 init_caller_stats (&stats); 1908 cgraph_for_node_and_aliases (orig_node, gather_caller_stats, &stats, false); 1909 orig_sum = stats.count_sum; 1910 init_caller_stats (&stats); 1911 cgraph_for_node_and_aliases (new_node, gather_caller_stats, &stats, false); 1912 new_sum = stats.count_sum; 1913 1914 if (orig_node_count < orig_sum + new_sum) 1915 { 1916 if (dump_file) 1917 fprintf (dump_file, " Problem: node %s/%i has too low count " 1918 HOST_WIDE_INT_PRINT_DEC " while the sum of incoming " 1919 "counts is " HOST_WIDE_INT_PRINT_DEC "\n", 1920 cgraph_node_name (orig_node), orig_node->uid, 1921 (HOST_WIDE_INT) orig_node_count, 1922 (HOST_WIDE_INT) (orig_sum + new_sum)); 1923 1924 orig_node_count = (orig_sum + new_sum) * 12 / 10; 1925 if (dump_file) 1926 fprintf (dump_file, " proceeding by pretending it was " 1927 HOST_WIDE_INT_PRINT_DEC "\n", 1928 (HOST_WIDE_INT) orig_node_count); 1929 } 1930 1931 new_node->count = new_sum; 1932 remainder = orig_node_count - new_sum; 1933 orig_node->count = remainder; 1934 1935 for (cs = new_node->callees; cs ; cs = cs->next_callee) 1936 if (cs->frequency) 1937 cs->count = cs->count * (new_sum * REG_BR_PROB_BASE 1938 / orig_node_count) / REG_BR_PROB_BASE; 1939 else 1940 cs->count = 0; 1941 1942 for (cs = orig_node->callees; cs ; cs = cs->next_callee) 1943 cs->count = cs->count * (remainder * REG_BR_PROB_BASE 1944 / orig_node_count) / REG_BR_PROB_BASE; 1945 1946 if (dump_file) 1947 dump_profile_updates (orig_node, new_node); 1948 } 1949 1950 /* Update the respective profile of specialized NEW_NODE and the original 1951 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM 1952 have been redirected to the specialized version. */ 1953 1954 static void 1955 update_specialized_profile (struct cgraph_node *new_node, 1956 struct cgraph_node *orig_node, 1957 gcov_type redirected_sum) 1958 { 1959 struct cgraph_edge *cs; 1960 gcov_type new_node_count, orig_node_count = orig_node->count; 1961 1962 if (dump_file) 1963 fprintf (dump_file, " the sum of counts of redirected edges is " 1964 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) redirected_sum); 1965 if (orig_node_count == 0) 1966 return; 1967 1968 gcc_assert (orig_node_count >= redirected_sum); 1969 1970 new_node_count = new_node->count; 1971 new_node->count += redirected_sum; 1972 orig_node->count -= redirected_sum; 1973 1974 for (cs = new_node->callees; cs ; cs = cs->next_callee) 1975 if (cs->frequency) 1976 cs->count += cs->count * redirected_sum / new_node_count; 1977 else 1978 cs->count = 0; 1979 1980 for (cs = orig_node->callees; cs ; cs = cs->next_callee) 1981 { 1982 gcov_type dec = cs->count * (redirected_sum * REG_BR_PROB_BASE 1983 / orig_node_count) / REG_BR_PROB_BASE; 1984 if (dec < cs->count) 1985 cs->count -= dec; 1986 else 1987 cs->count = 0; 1988 } 1989 1990 if (dump_file) 1991 dump_profile_updates (orig_node, new_node); 1992 } 1993 1994 /* Create a specialized version of NODE with known constants and types of 1995 parameters in KNOWN_VALS and redirect all edges in CALLERS to it. */ 1996 1997 static struct cgraph_node * 1998 create_specialized_node (struct cgraph_node *node, 1999 VEC (tree, heap) *known_vals, 2000 VEC (cgraph_edge_p,heap) *callers) 2001 { 2002 struct ipa_node_params *new_info, *info = IPA_NODE_REF (node); 2003 VEC (ipa_replace_map_p,gc)* replace_trees = NULL; 2004 struct cgraph_node *new_node; 2005 int i, count = ipa_get_param_count (info); 2006 bitmap args_to_skip; 2007 2008 gcc_assert (!info->ipcp_orig_node); 2009 2010 if (node->local.can_change_signature) 2011 { 2012 args_to_skip = BITMAP_GGC_ALLOC (); 2013 for (i = 0; i < count; i++) 2014 { 2015 tree t = VEC_index (tree, known_vals, i); 2016 2017 if ((t && TREE_CODE (t) != TREE_BINFO) 2018 || !ipa_is_param_used (info, i)) 2019 bitmap_set_bit (args_to_skip, i); 2020 } 2021 } 2022 else 2023 { 2024 args_to_skip = NULL; 2025 if (dump_file && (dump_flags & TDF_DETAILS)) 2026 fprintf (dump_file, " cannot change function signature\n"); 2027 } 2028 2029 for (i = 0; i < count ; i++) 2030 { 2031 tree t = VEC_index (tree, known_vals, i); 2032 if (t && TREE_CODE (t) != TREE_BINFO) 2033 { 2034 struct ipa_replace_map *replace_map; 2035 2036 replace_map = get_replacement_map (t, ipa_get_param (info, i)); 2037 if (replace_map) 2038 VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_map); 2039 } 2040 } 2041 2042 new_node = cgraph_create_virtual_clone (node, callers, replace_trees, 2043 args_to_skip, "constprop"); 2044 if (dump_file && (dump_flags & TDF_DETAILS)) 2045 fprintf (dump_file, " the new node is %s/%i.\n", 2046 cgraph_node_name (new_node), new_node->uid); 2047 gcc_checking_assert (ipa_node_params_vector 2048 && (VEC_length (ipa_node_params_t, 2049 ipa_node_params_vector) 2050 > (unsigned) cgraph_max_uid)); 2051 update_profiling_info (node, new_node); 2052 new_info = IPA_NODE_REF (new_node); 2053 new_info->ipcp_orig_node = node; 2054 new_info->known_vals = known_vals; 2055 2056 ipcp_discover_new_direct_edges (new_node, known_vals); 2057 2058 VEC_free (cgraph_edge_p, heap, callers); 2059 return new_node; 2060 } 2061 2062 /* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in 2063 KNOWN_VALS with constants and types that are also known for all of the 2064 CALLERS. */ 2065 2066 static void 2067 find_more_values_for_callers_subset (struct cgraph_node *node, 2068 VEC (tree, heap) *known_vals, 2069 VEC (cgraph_edge_p,heap) *callers) 2070 { 2071 struct ipa_node_params *info = IPA_NODE_REF (node); 2072 int i, count = ipa_get_param_count (info); 2073 2074 for (i = 0; i < count ; i++) 2075 { 2076 struct cgraph_edge *cs; 2077 tree newval = NULL_TREE; 2078 int j; 2079 2080 if (ipa_get_lattice (info, i)->bottom 2081 || VEC_index (tree, known_vals, i)) 2082 continue; 2083 2084 FOR_EACH_VEC_ELT (cgraph_edge_p, callers, j, cs) 2085 { 2086 struct ipa_jump_func *jump_func; 2087 tree t; 2088 2089 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs))) 2090 { 2091 newval = NULL_TREE; 2092 break; 2093 } 2094 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i); 2095 t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func); 2096 if (!t 2097 || (newval 2098 && !values_equal_for_ipcp_p (t, newval))) 2099 { 2100 newval = NULL_TREE; 2101 break; 2102 } 2103 else 2104 newval = t; 2105 } 2106 2107 if (newval) 2108 { 2109 if (dump_file && (dump_flags & TDF_DETAILS)) 2110 { 2111 fprintf (dump_file, " adding an extra known value "); 2112 print_ipcp_constant_value (dump_file, newval); 2113 fprintf (dump_file, " for parameter "); 2114 print_generic_expr (dump_file, ipa_get_param (info, i), 0); 2115 fprintf (dump_file, "\n"); 2116 } 2117 2118 VEC_replace (tree, known_vals, i, newval); 2119 } 2120 } 2121 } 2122 2123 /* Given an original NODE and a VAL for which we have already created a 2124 specialized clone, look whether there are incoming edges that still lead 2125 into the old node but now also bring the requested value and also conform to 2126 all other criteria such that they can be redirected the the special node. 2127 This function can therefore redirect the final edge in a SCC. */ 2128 2129 static void 2130 perhaps_add_new_callers (struct cgraph_node *node, struct ipcp_value *val) 2131 { 2132 struct ipa_node_params *dest_info = IPA_NODE_REF (val->spec_node); 2133 struct ipcp_value_source *src; 2134 int count = ipa_get_param_count (dest_info); 2135 gcov_type redirected_sum = 0; 2136 2137 for (src = val->sources; src; src = src->next) 2138 { 2139 struct cgraph_edge *cs = src->cs; 2140 while (cs) 2141 { 2142 enum availability availability; 2143 bool insufficient = false; 2144 2145 if (cgraph_function_node (cs->callee, &availability) == node 2146 && availability > AVAIL_OVERWRITABLE 2147 && cgraph_edge_brings_value_p (cs, src)) 2148 { 2149 struct ipa_node_params *caller_info; 2150 struct ipa_edge_args *args; 2151 int i; 2152 2153 caller_info = IPA_NODE_REF (cs->caller); 2154 args = IPA_EDGE_REF (cs); 2155 for (i = 0; i < count; i++) 2156 { 2157 struct ipa_jump_func *jump_func; 2158 tree val, t; 2159 2160 val = VEC_index (tree, dest_info->known_vals, i); 2161 if (!val) 2162 continue; 2163 2164 if (i >= ipa_get_cs_argument_count (args)) 2165 { 2166 insufficient = true; 2167 break; 2168 } 2169 jump_func = ipa_get_ith_jump_func (args, i); 2170 t = ipa_value_from_jfunc (caller_info, jump_func); 2171 if (!t || !values_equal_for_ipcp_p (val, t)) 2172 { 2173 insufficient = true; 2174 break; 2175 } 2176 } 2177 2178 if (!insufficient) 2179 { 2180 if (dump_file) 2181 fprintf (dump_file, " - adding an extra caller %s/%i" 2182 " of %s/%i\n", 2183 xstrdup (cgraph_node_name (cs->caller)), 2184 cs->caller->uid, 2185 xstrdup (cgraph_node_name (val->spec_node)), 2186 val->spec_node->uid); 2187 2188 cgraph_redirect_edge_callee (cs, val->spec_node); 2189 redirected_sum += cs->count; 2190 } 2191 } 2192 cs = get_next_cgraph_edge_clone (cs); 2193 } 2194 } 2195 2196 if (redirected_sum) 2197 update_specialized_profile (val->spec_node, node, redirected_sum); 2198 } 2199 2200 2201 /* Copy KNOWN_BINFOS to KNOWN_VALS. */ 2202 2203 static void 2204 move_binfos_to_values (VEC (tree, heap) *known_vals, 2205 VEC (tree, heap) *known_binfos) 2206 { 2207 tree t; 2208 int i; 2209 2210 for (i = 0; VEC_iterate (tree, known_binfos, i, t); i++) 2211 if (t) 2212 VEC_replace (tree, known_vals, i, t); 2213 } 2214 2215 2216 /* Decide whether and what specialized clones of NODE should be created. */ 2217 2218 static bool 2219 decide_whether_version_node (struct cgraph_node *node) 2220 { 2221 struct ipa_node_params *info = IPA_NODE_REF (node); 2222 int i, count = ipa_get_param_count (info); 2223 VEC (tree, heap) *known_csts, *known_binfos; 2224 bool ret = false; 2225 2226 if (count == 0) 2227 return false; 2228 2229 if (dump_file && (dump_flags & TDF_DETAILS)) 2230 fprintf (dump_file, "\nEvaluating opportunities for %s/%i.\n", 2231 cgraph_node_name (node), node->uid); 2232 2233 gather_context_independent_values (info, &known_csts, &known_binfos, 2234 NULL); 2235 2236 for (i = 0; i < count ; i++) 2237 { 2238 struct ipcp_lattice *lat = ipa_get_lattice (info, i); 2239 struct ipcp_value *val; 2240 2241 if (lat->bottom 2242 || VEC_index (tree, known_csts, i) 2243 || VEC_index (tree, known_binfos, i)) 2244 continue; 2245 2246 for (val = lat->values; val; val = val->next) 2247 { 2248 int freq_sum, caller_count; 2249 gcov_type count_sum; 2250 VEC (cgraph_edge_p, heap) *callers; 2251 VEC (tree, heap) *kv; 2252 2253 if (val->spec_node) 2254 { 2255 perhaps_add_new_callers (node, val); 2256 continue; 2257 } 2258 else if (val->local_size_cost + overall_size > max_new_size) 2259 { 2260 if (dump_file && (dump_flags & TDF_DETAILS)) 2261 fprintf (dump_file, " Ignoring candidate value because " 2262 "max_new_size would be reached with %li.\n", 2263 val->local_size_cost + overall_size); 2264 continue; 2265 } 2266 else if (!get_info_about_necessary_edges (val, &freq_sum, &count_sum, 2267 &caller_count)) 2268 continue; 2269 2270 if (dump_file && (dump_flags & TDF_DETAILS)) 2271 { 2272 fprintf (dump_file, " - considering value "); 2273 print_ipcp_constant_value (dump_file, val->value); 2274 fprintf (dump_file, " for parameter "); 2275 print_generic_expr (dump_file, ipa_get_param (info, i), 0); 2276 fprintf (dump_file, " (caller_count: %i)\n", caller_count); 2277 } 2278 2279 2280 if (!good_cloning_opportunity_p (node, val->local_time_benefit, 2281 freq_sum, count_sum, 2282 val->local_size_cost) 2283 && !good_cloning_opportunity_p (node, 2284 val->local_time_benefit 2285 + val->prop_time_benefit, 2286 freq_sum, count_sum, 2287 val->local_size_cost 2288 + val->prop_size_cost)) 2289 continue; 2290 2291 if (dump_file) 2292 fprintf (dump_file, " Creating a specialized node of %s/%i.\n", 2293 cgraph_node_name (node), node->uid); 2294 2295 callers = gather_edges_for_value (val, caller_count); 2296 kv = VEC_copy (tree, heap, known_csts); 2297 move_binfos_to_values (kv, known_binfos); 2298 VEC_replace (tree, kv, i, val->value); 2299 find_more_values_for_callers_subset (node, kv, callers); 2300 val->spec_node = create_specialized_node (node, kv, callers); 2301 overall_size += val->local_size_cost; 2302 info = IPA_NODE_REF (node); 2303 2304 /* TODO: If for some lattice there is only one other known value 2305 left, make a special node for it too. */ 2306 ret = true; 2307 2308 VEC_replace (tree, kv, i, val->value); 2309 } 2310 } 2311 2312 if (info->clone_for_all_contexts) 2313 { 2314 VEC (cgraph_edge_p, heap) *callers; 2315 2316 if (dump_file) 2317 fprintf (dump_file, " - Creating a specialized node of %s/%i " 2318 "for all known contexts.\n", cgraph_node_name (node), 2319 node->uid); 2320 2321 callers = collect_callers_of_node (node); 2322 move_binfos_to_values (known_csts, known_binfos); 2323 create_specialized_node (node, known_csts, callers); 2324 info = IPA_NODE_REF (node); 2325 info->clone_for_all_contexts = false; 2326 ret = true; 2327 } 2328 else 2329 VEC_free (tree, heap, known_csts); 2330 2331 VEC_free (tree, heap, known_binfos); 2332 return ret; 2333 } 2334 2335 /* Transitively mark all callees of NODE within the same SCC as not dead. */ 2336 2337 static void 2338 spread_undeadness (struct cgraph_node *node) 2339 { 2340 struct cgraph_edge *cs; 2341 2342 for (cs = node->callees; cs; cs = cs->next_callee) 2343 if (edge_within_scc (cs)) 2344 { 2345 struct cgraph_node *callee; 2346 struct ipa_node_params *info; 2347 2348 callee = cgraph_function_node (cs->callee, NULL); 2349 info = IPA_NODE_REF (callee); 2350 2351 if (info->node_dead) 2352 { 2353 info->node_dead = 0; 2354 spread_undeadness (callee); 2355 } 2356 } 2357 } 2358 2359 /* Return true if NODE has a caller from outside of its SCC that is not 2360 dead. Worker callback for cgraph_for_node_and_aliases. */ 2361 2362 static bool 2363 has_undead_caller_from_outside_scc_p (struct cgraph_node *node, 2364 void *data ATTRIBUTE_UNUSED) 2365 { 2366 struct cgraph_edge *cs; 2367 2368 for (cs = node->callers; cs; cs = cs->next_caller) 2369 if (cs->caller->thunk.thunk_p 2370 && cgraph_for_node_and_aliases (cs->caller, 2371 has_undead_caller_from_outside_scc_p, 2372 NULL, true)) 2373 return true; 2374 else if (!edge_within_scc (cs) 2375 && !IPA_NODE_REF (cs->caller)->node_dead) 2376 return true; 2377 return false; 2378 } 2379 2380 2381 /* Identify nodes within the same SCC as NODE which are no longer needed 2382 because of new clones and will be removed as unreachable. */ 2383 2384 static void 2385 identify_dead_nodes (struct cgraph_node *node) 2386 { 2387 struct cgraph_node *v; 2388 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) 2389 if (cgraph_will_be_removed_from_program_if_no_direct_calls (v) 2390 && !cgraph_for_node_and_aliases (v, 2391 has_undead_caller_from_outside_scc_p, 2392 NULL, true)) 2393 IPA_NODE_REF (v)->node_dead = 1; 2394 2395 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) 2396 if (!IPA_NODE_REF (v)->node_dead) 2397 spread_undeadness (v); 2398 2399 if (dump_file && (dump_flags & TDF_DETAILS)) 2400 { 2401 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) 2402 if (IPA_NODE_REF (v)->node_dead) 2403 fprintf (dump_file, " Marking node as dead: %s/%i.\n", 2404 cgraph_node_name (v), v->uid); 2405 } 2406 } 2407 2408 /* The decision stage. Iterate over the topological order of call graph nodes 2409 TOPO and make specialized clones if deemed beneficial. */ 2410 2411 static void 2412 ipcp_decision_stage (struct topo_info *topo) 2413 { 2414 int i; 2415 2416 if (dump_file) 2417 fprintf (dump_file, "\nIPA decision stage:\n\n"); 2418 2419 for (i = topo->nnodes - 1; i >= 0; i--) 2420 { 2421 struct cgraph_node *node = topo->order[i]; 2422 bool change = false, iterate = true; 2423 2424 while (iterate) 2425 { 2426 struct cgraph_node *v; 2427 iterate = false; 2428 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) 2429 if (cgraph_function_with_gimple_body_p (v) 2430 && ipcp_versionable_function_p (v)) 2431 iterate |= decide_whether_version_node (v); 2432 2433 change |= iterate; 2434 } 2435 if (change) 2436 identify_dead_nodes (node); 2437 } 2438 } 2439 2440 /* The IPCP driver. */ 2441 2442 static unsigned int 2443 ipcp_driver (void) 2444 { 2445 struct cgraph_2edge_hook_list *edge_duplication_hook_holder; 2446 struct topo_info topo; 2447 2448 cgraph_remove_unreachable_nodes (true,dump_file); 2449 ipa_check_create_node_params (); 2450 ipa_check_create_edge_args (); 2451 grow_next_edge_clone_vector (); 2452 edge_duplication_hook_holder = 2453 cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL); 2454 ipcp_values_pool = create_alloc_pool ("IPA-CP values", 2455 sizeof (struct ipcp_value), 32); 2456 ipcp_sources_pool = create_alloc_pool ("IPA-CP value sources", 2457 sizeof (struct ipcp_value_source), 64); 2458 if (dump_file) 2459 { 2460 fprintf (dump_file, "\nIPA structures before propagation:\n"); 2461 if (dump_flags & TDF_DETAILS) 2462 ipa_print_all_params (dump_file); 2463 ipa_print_all_jump_functions (dump_file); 2464 } 2465 2466 /* Topological sort. */ 2467 build_toporder_info (&topo); 2468 /* Do the interprocedural propagation. */ 2469 ipcp_propagate_stage (&topo); 2470 /* Decide what constant propagation and cloning should be performed. */ 2471 ipcp_decision_stage (&topo); 2472 2473 /* Free all IPCP structures. */ 2474 free_toporder_info (&topo); 2475 VEC_free (cgraph_edge_p, heap, next_edge_clone); 2476 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder); 2477 ipa_free_all_structures_after_ipa_cp (); 2478 if (dump_file) 2479 fprintf (dump_file, "\nIPA constant propagation end\n"); 2480 return 0; 2481 } 2482 2483 /* Initialization and computation of IPCP data structures. This is the initial 2484 intraprocedural analysis of functions, which gathers information to be 2485 propagated later on. */ 2486 2487 static void 2488 ipcp_generate_summary (void) 2489 { 2490 struct cgraph_node *node; 2491 2492 if (dump_file) 2493 fprintf (dump_file, "\nIPA constant propagation start:\n"); 2494 ipa_register_cgraph_hooks (); 2495 2496 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) 2497 { 2498 /* Unreachable nodes should have been eliminated before ipcp. */ 2499 gcc_assert (node->needed || node->reachable); 2500 node->local.versionable = tree_versionable_function_p (node->decl); 2501 ipa_analyze_node (node); 2502 } 2503 } 2504 2505 /* Write ipcp summary for nodes in SET. */ 2506 2507 static void 2508 ipcp_write_summary (cgraph_node_set set, 2509 varpool_node_set vset ATTRIBUTE_UNUSED) 2510 { 2511 ipa_prop_write_jump_functions (set); 2512 } 2513 2514 /* Read ipcp summary. */ 2515 2516 static void 2517 ipcp_read_summary (void) 2518 { 2519 ipa_prop_read_jump_functions (); 2520 } 2521 2522 /* Gate for IPCP optimization. */ 2523 2524 static bool 2525 cgraph_gate_cp (void) 2526 { 2527 /* FIXME: We should remove the optimize check after we ensure we never run 2528 IPA passes when not optimizing. */ 2529 return flag_ipa_cp && optimize; 2530 } 2531 2532 struct ipa_opt_pass_d pass_ipa_cp = 2533 { 2534 { 2535 IPA_PASS, 2536 "cp", /* name */ 2537 cgraph_gate_cp, /* gate */ 2538 ipcp_driver, /* execute */ 2539 NULL, /* sub */ 2540 NULL, /* next */ 2541 0, /* static_pass_number */ 2542 TV_IPA_CONSTANT_PROP, /* tv_id */ 2543 0, /* properties_required */ 2544 0, /* properties_provided */ 2545 0, /* properties_destroyed */ 2546 0, /* todo_flags_start */ 2547 TODO_dump_cgraph | 2548 TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */ 2549 }, 2550 ipcp_generate_summary, /* generate_summary */ 2551 ipcp_write_summary, /* write_summary */ 2552 ipcp_read_summary, /* read_summary */ 2553 NULL, /* write_optimization_summary */ 2554 NULL, /* read_optimization_summary */ 2555 NULL, /* stmt_fixup */ 2556 0, /* TODOs */ 2557 NULL, /* function_transform */ 2558 NULL, /* variable_transform */ 2559 }; 2560