1/* Interprocedural constant propagation 2 Copyright (C) 2005-2015 Free Software Foundation, Inc. 3 4 Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor 5 <mjambor@suse.cz> 6 7This file is part of GCC. 8 9GCC is free software; you can redistribute it and/or modify it under 10the terms of the GNU General Public License as published by the Free 11Software Foundation; either version 3, or (at your option) any later 12version. 13 14GCC is distributed in the hope that it will be useful, but WITHOUT ANY 15WARRANTY; without even the implied warranty of MERCHANTABILITY or 16FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 17for more details. 18 19You should have received a copy of the GNU General Public License 20along with GCC; see the file COPYING3. If not see 21<http://www.gnu.org/licenses/>. */ 22 23/* Interprocedural constant propagation (IPA-CP). 24 25 The goal of this transformation is to 26 27 1) discover functions which are always invoked with some arguments with the 28 same known constant values and modify the functions so that the 29 subsequent optimizations can take advantage of the knowledge, and 30 31 2) partial specialization - create specialized versions of functions 32 transformed in this way if some parameters are known constants only in 33 certain contexts but the estimated tradeoff between speedup and cost size 34 is deemed good. 35 36 The algorithm also propagates types and attempts to perform type based 37 devirtualization. Types are propagated much like constants. 38 39 The algorithm basically consists of three stages. In the first, functions 40 are analyzed one at a time and jump functions are constructed for all known 41 call-sites. In the second phase, the pass propagates information from the 42 jump functions across the call to reveal what values are available at what 43 call sites, performs estimations of effects of known values on functions and 44 their callees, and finally decides what specialized extra versions should be 45 created. In the third, the special versions materialize and appropriate 46 calls are redirected. 47 48 The algorithm used is to a certain extent based on "Interprocedural Constant 49 Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon, 50 Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D 51 Cooper, Mary W. Hall, and Ken Kennedy. 52 53 54 First stage - intraprocedural analysis 55 ======================================= 56 57 This phase computes jump_function and modification flags. 58 59 A jump function for a call-site represents the values passed as an actual 60 arguments of a given call-site. In principle, there are three types of 61 values: 62 63 Pass through - the caller's formal parameter is passed as an actual 64 argument, plus an operation on it can be performed. 65 Constant - a constant is passed as an actual argument. 66 Unknown - neither of the above. 67 68 All jump function types are described in detail in ipa-prop.h, together with 69 the data structures that represent them and methods of accessing them. 70 71 ipcp_generate_summary() is the main function of the first stage. 72 73 Second stage - interprocedural analysis 74 ======================================== 75 76 This stage is itself divided into two phases. In the first, we propagate 77 known values over the call graph, in the second, we make cloning decisions. 78 It uses a different algorithm than the original Callahan's paper. 79 80 First, we traverse the functions topologically from callers to callees and, 81 for each strongly connected component (SCC), we propagate constants 82 according to previously computed jump functions. We also record what known 83 values depend on other known values and estimate local effects. Finally, we 84 propagate cumulative information about these effects from dependent values 85 to those on which they depend. 86 87 Second, we again traverse the call graph in the same topological order and 88 make clones for functions which we know are called with the same values in 89 all contexts and decide about extra specialized clones of functions just for 90 some contexts - these decisions are based on both local estimates and 91 cumulative estimates propagated from callees. 92 93 ipcp_propagate_stage() and ipcp_decision_stage() together constitute the 94 third stage. 95 96 Third phase - materialization of clones, call statement updates. 97 ============================================ 98 99 This stage is currently performed by call graph code (mainly in cgraphunit.c 100 and tree-inline.c) according to instructions inserted to the call graph by 101 the second stage. */ 102 103#include "config.h" 104#include "system.h" 105#include "coretypes.h" 106#include "hash-set.h" 107#include "machmode.h" 108#include "vec.h" 109#include "hash-map.h" 110#include "double-int.h" 111#include "input.h" 112#include "alias.h" 113#include "symtab.h" 114#include "options.h" 115#include "wide-int.h" 116#include "inchash.h" 117#include "tree.h" 118#include "fold-const.h" 119#include "gimple-fold.h" 120#include "gimple-expr.h" 121#include "target.h" 122#include "predict.h" 123#include "basic-block.h" 124#include "is-a.h" 125#include "plugin-api.h" 126#include "tm.h" 127#include "hard-reg-set.h" 128#include "input.h" 129#include "function.h" 130#include "ipa-ref.h" 131#include "cgraph.h" 132#include "alloc-pool.h" 133#include "symbol-summary.h" 134#include "ipa-prop.h" 135#include "bitmap.h" 136#include "tree-pass.h" 137#include "flags.h" 138#include "diagnostic.h" 139#include "tree-pretty-print.h" 140#include "tree-inline.h" 141#include "params.h" 142#include "ipa-inline.h" 143#include "ipa-utils.h" 144 145template <typename valtype> class ipcp_value; 146 147/* Describes a particular source for an IPA-CP value. */ 148 149template <typename valtype> 150class ipcp_value_source 151{ 152public: 153 /* Aggregate offset of the source, negative if the source is scalar value of 154 the argument itself. */ 155 HOST_WIDE_INT offset; 156 /* The incoming edge that brought the value. */ 157 cgraph_edge *cs; 158 /* If the jump function that resulted into his value was a pass-through or an 159 ancestor, this is the ipcp_value of the caller from which the described 160 value has been derived. Otherwise it is NULL. */ 161 ipcp_value<valtype> *val; 162 /* Next pointer in a linked list of sources of a value. */ 163 ipcp_value_source *next; 164 /* If the jump function that resulted into his value was a pass-through or an 165 ancestor, this is the index of the parameter of the caller the jump 166 function references. */ 167 int index; 168}; 169 170/* Common ancestor for all ipcp_value instantiations. */ 171 172class ipcp_value_base 173{ 174public: 175 /* Time benefit and size cost that specializing the function for this value 176 would bring about in this function alone. */ 177 int local_time_benefit, local_size_cost; 178 /* Time benefit and size cost that specializing the function for this value 179 can bring about in it's callees (transitively). */ 180 int prop_time_benefit, prop_size_cost; 181}; 182 183/* Describes one particular value stored in struct ipcp_lattice. */ 184 185template <typename valtype> 186class ipcp_value : public ipcp_value_base 187{ 188public: 189 /* The actual value for the given parameter. */ 190 valtype value; 191 /* The list of sources from which this value originates. */ 192 ipcp_value_source <valtype> *sources; 193 /* Next pointers in a linked list of all values in a lattice. */ 194 ipcp_value *next; 195 /* Next pointers in a linked list of values in a strongly connected component 196 of values. */ 197 ipcp_value *scc_next; 198 /* Next pointers in a linked list of SCCs of values sorted topologically 199 according their sources. */ 200 ipcp_value *topo_next; 201 /* A specialized node created for this value, NULL if none has been (so far) 202 created. */ 203 cgraph_node *spec_node; 204 /* Depth first search number and low link for topological sorting of 205 values. */ 206 int dfs, low_link; 207 /* True if this valye is currently on the topo-sort stack. */ 208 bool on_stack; 209 210 void add_source (cgraph_edge *cs, ipcp_value *src_val, int src_idx, 211 HOST_WIDE_INT offset); 212}; 213 214/* Lattice describing potential values of a formal parameter of a function, or 215 a part of an aggreagate. TOP is represented by a lattice with zero values 216 and with contains_variable and bottom flags cleared. BOTTOM is represented 217 by a lattice with the bottom flag set. In that case, values and 218 contains_variable flag should be disregarded. */ 219 220template <typename valtype> 221class ipcp_lattice 222{ 223public: 224 /* The list of known values and types in this lattice. Note that values are 225 not deallocated if a lattice is set to bottom because there may be value 226 sources referencing them. */ 227 ipcp_value<valtype> *values; 228 /* Number of known values and types in this lattice. */ 229 int values_count; 230 /* The lattice contains a variable component (in addition to values). */ 231 bool contains_variable; 232 /* The value of the lattice is bottom (i.e. variable and unusable for any 233 propagation). */ 234 bool bottom; 235 236 inline bool is_single_const (); 237 inline bool set_to_bottom (); 238 inline bool set_contains_variable (); 239 bool add_value (valtype newval, cgraph_edge *cs, 240 ipcp_value<valtype> *src_val = NULL, 241 int src_idx = 0, HOST_WIDE_INT offset = -1); 242 void print (FILE * f, bool dump_sources, bool dump_benefits); 243}; 244 245/* Lattice of tree values with an offset to describe a part of an 246 aggregate. */ 247 248class ipcp_agg_lattice : public ipcp_lattice<tree> 249{ 250public: 251 /* Offset that is being described by this lattice. */ 252 HOST_WIDE_INT offset; 253 /* Size so that we don't have to re-compute it every time we traverse the 254 list. Must correspond to TYPE_SIZE of all lat values. */ 255 HOST_WIDE_INT size; 256 /* Next element of the linked list. */ 257 struct ipcp_agg_lattice *next; 258}; 259 260/* Structure containing lattices for a parameter itself and for pieces of 261 aggregates that are passed in the parameter or by a reference in a parameter 262 plus some other useful flags. */ 263 264class ipcp_param_lattices 265{ 266public: 267 /* Lattice describing the value of the parameter itself. */ 268 ipcp_lattice<tree> itself; 269 /* Lattice describing the the polymorphic contexts of a parameter. */ 270 ipcp_lattice<ipa_polymorphic_call_context> ctxlat; 271 /* Lattices describing aggregate parts. */ 272 ipcp_agg_lattice *aggs; 273 /* Alignment information. Very basic one value lattice where !known means 274 TOP and zero alignment bottom. */ 275 ipa_alignment alignment; 276 /* Number of aggregate lattices */ 277 int aggs_count; 278 /* True if aggregate data were passed by reference (as opposed to by 279 value). */ 280 bool aggs_by_ref; 281 /* All aggregate lattices contain a variable component (in addition to 282 values). */ 283 bool aggs_contain_variable; 284 /* The value of all aggregate lattices is bottom (i.e. variable and unusable 285 for any propagation). */ 286 bool aggs_bottom; 287 288 /* There is a virtual call based on this parameter. */ 289 bool virt_call; 290}; 291 292/* Allocation pools for values and their sources in ipa-cp. */ 293 294alloc_pool ipcp_cst_values_pool; 295alloc_pool ipcp_poly_ctx_values_pool; 296alloc_pool ipcp_sources_pool; 297alloc_pool ipcp_agg_lattice_pool; 298 299/* Maximal count found in program. */ 300 301static gcov_type max_count; 302 303/* Original overall size of the program. */ 304 305static long overall_size, max_new_size; 306 307/* Return the param lattices structure corresponding to the Ith formal 308 parameter of the function described by INFO. */ 309static inline struct ipcp_param_lattices * 310ipa_get_parm_lattices (struct ipa_node_params *info, int i) 311{ 312 gcc_assert (i >= 0 && i < ipa_get_param_count (info)); 313 gcc_checking_assert (!info->ipcp_orig_node); 314 gcc_checking_assert (info->lattices); 315 return &(info->lattices[i]); 316} 317 318/* Return the lattice corresponding to the scalar value of the Ith formal 319 parameter of the function described by INFO. */ 320static inline ipcp_lattice<tree> * 321ipa_get_scalar_lat (struct ipa_node_params *info, int i) 322{ 323 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); 324 return &plats->itself; 325} 326 327/* Return the lattice corresponding to the scalar value of the Ith formal 328 parameter of the function described by INFO. */ 329static inline ipcp_lattice<ipa_polymorphic_call_context> * 330ipa_get_poly_ctx_lat (struct ipa_node_params *info, int i) 331{ 332 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); 333 return &plats->ctxlat; 334} 335 336/* Return whether LAT is a lattice with a single constant and without an 337 undefined value. */ 338 339template <typename valtype> 340inline bool 341ipcp_lattice<valtype>::is_single_const () 342{ 343 if (bottom || contains_variable || values_count != 1) 344 return false; 345 else 346 return true; 347} 348 349/* Print V which is extracted from a value in a lattice to F. */ 350 351static void 352print_ipcp_constant_value (FILE * f, tree v) 353{ 354 if (TREE_CODE (v) == ADDR_EXPR 355 && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL) 356 { 357 fprintf (f, "& "); 358 print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)), 0); 359 } 360 else 361 print_generic_expr (f, v, 0); 362} 363 364/* Print V which is extracted from a value in a lattice to F. */ 365 366static void 367print_ipcp_constant_value (FILE * f, ipa_polymorphic_call_context v) 368{ 369 v.dump(f, false); 370} 371 372/* Print a lattice LAT to F. */ 373 374template <typename valtype> 375void 376ipcp_lattice<valtype>::print (FILE * f, bool dump_sources, bool dump_benefits) 377{ 378 ipcp_value<valtype> *val; 379 bool prev = false; 380 381 if (bottom) 382 { 383 fprintf (f, "BOTTOM\n"); 384 return; 385 } 386 387 if (!values_count && !contains_variable) 388 { 389 fprintf (f, "TOP\n"); 390 return; 391 } 392 393 if (contains_variable) 394 { 395 fprintf (f, "VARIABLE"); 396 prev = true; 397 if (dump_benefits) 398 fprintf (f, "\n"); 399 } 400 401 for (val = values; val; val = val->next) 402 { 403 if (dump_benefits && prev) 404 fprintf (f, " "); 405 else if (!dump_benefits && prev) 406 fprintf (f, ", "); 407 else 408 prev = true; 409 410 print_ipcp_constant_value (f, val->value); 411 412 if (dump_sources) 413 { 414 ipcp_value_source<valtype> *s; 415 416 fprintf (f, " [from:"); 417 for (s = val->sources; s; s = s->next) 418 fprintf (f, " %i(%i)", s->cs->caller->order, 419 s->cs->frequency); 420 fprintf (f, "]"); 421 } 422 423 if (dump_benefits) 424 fprintf (f, " [loc_time: %i, loc_size: %i, " 425 "prop_time: %i, prop_size: %i]\n", 426 val->local_time_benefit, val->local_size_cost, 427 val->prop_time_benefit, val->prop_size_cost); 428 } 429 if (!dump_benefits) 430 fprintf (f, "\n"); 431} 432 433/* Print all ipcp_lattices of all functions to F. */ 434 435static void 436print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits) 437{ 438 struct cgraph_node *node; 439 int i, count; 440 441 fprintf (f, "\nLattices:\n"); 442 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) 443 { 444 struct ipa_node_params *info; 445 446 info = IPA_NODE_REF (node); 447 fprintf (f, " Node: %s/%i:\n", node->name (), 448 node->order); 449 count = ipa_get_param_count (info); 450 for (i = 0; i < count; i++) 451 { 452 struct ipcp_agg_lattice *aglat; 453 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); 454 fprintf (f, " param [%d]: ", i); 455 plats->itself.print (f, dump_sources, dump_benefits); 456 fprintf (f, " ctxs: "); 457 plats->ctxlat.print (f, dump_sources, dump_benefits); 458 if (plats->alignment.known && plats->alignment.align > 0) 459 fprintf (f, " Alignment %u, misalignment %u\n", 460 plats->alignment.align, plats->alignment.misalign); 461 else if (plats->alignment.known) 462 fprintf (f, " Alignment unusable\n"); 463 else 464 fprintf (f, " Alignment unknown\n"); 465 if (plats->virt_call) 466 fprintf (f, " virt_call flag set\n"); 467 468 if (plats->aggs_bottom) 469 { 470 fprintf (f, " AGGS BOTTOM\n"); 471 continue; 472 } 473 if (plats->aggs_contain_variable) 474 fprintf (f, " AGGS VARIABLE\n"); 475 for (aglat = plats->aggs; aglat; aglat = aglat->next) 476 { 477 fprintf (f, " %soffset " HOST_WIDE_INT_PRINT_DEC ": ", 478 plats->aggs_by_ref ? "ref " : "", aglat->offset); 479 aglat->print (f, dump_sources, dump_benefits); 480 } 481 } 482 } 483} 484 485/* Determine whether it is at all technically possible to create clones of NODE 486 and store this information in the ipa_node_params structure associated 487 with NODE. */ 488 489static void 490determine_versionability (struct cgraph_node *node) 491{ 492 const char *reason = NULL; 493 494 /* There are a number of generic reasons functions cannot be versioned. We 495 also cannot remove parameters if there are type attributes such as fnspec 496 present. */ 497 if (node->alias || node->thunk.thunk_p) 498 reason = "alias or thunk"; 499 else if (!node->local.versionable) 500 reason = "not a tree_versionable_function"; 501 else if (node->get_availability () <= AVAIL_INTERPOSABLE) 502 reason = "insufficient body availability"; 503 else if (!opt_for_fn (node->decl, optimize) 504 || !opt_for_fn (node->decl, flag_ipa_cp)) 505 reason = "non-optimized function"; 506 else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node->decl))) 507 { 508 /* Ideally we should clone the SIMD clones themselves and create 509 vector copies of them, so IPA-cp and SIMD clones can happily 510 coexist, but that may not be worth the effort. */ 511 reason = "function has SIMD clones"; 512 } 513 /* Don't clone decls local to a comdat group; it breaks and for C++ 514 decloned constructors, inlining is always better anyway. */ 515 else if (node->comdat_local_p ()) 516 reason = "comdat-local function"; 517 518 if (reason && dump_file && !node->alias && !node->thunk.thunk_p) 519 fprintf (dump_file, "Function %s/%i is not versionable, reason: %s.\n", 520 node->name (), node->order, reason); 521 522 node->local.versionable = (reason == NULL); 523} 524 525/* Return true if it is at all technically possible to create clones of a 526 NODE. */ 527 528static bool 529ipcp_versionable_function_p (struct cgraph_node *node) 530{ 531 return node->local.versionable; 532} 533 534/* Structure holding accumulated information about callers of a node. */ 535 536struct caller_statistics 537{ 538 gcov_type count_sum; 539 int n_calls, n_hot_calls, freq_sum; 540}; 541 542/* Initialize fields of STAT to zeroes. */ 543 544static inline void 545init_caller_stats (struct caller_statistics *stats) 546{ 547 stats->count_sum = 0; 548 stats->n_calls = 0; 549 stats->n_hot_calls = 0; 550 stats->freq_sum = 0; 551} 552 553/* Worker callback of cgraph_for_node_and_aliases accumulating statistics of 554 non-thunk incoming edges to NODE. */ 555 556static bool 557gather_caller_stats (struct cgraph_node *node, void *data) 558{ 559 struct caller_statistics *stats = (struct caller_statistics *) data; 560 struct cgraph_edge *cs; 561 562 for (cs = node->callers; cs; cs = cs->next_caller) 563 if (!cs->caller->thunk.thunk_p) 564 { 565 stats->count_sum += cs->count; 566 stats->freq_sum += cs->frequency; 567 stats->n_calls++; 568 if (cs->maybe_hot_p ()) 569 stats->n_hot_calls ++; 570 } 571 return false; 572 573} 574 575/* Return true if this NODE is viable candidate for cloning. */ 576 577static bool 578ipcp_cloning_candidate_p (struct cgraph_node *node) 579{ 580 struct caller_statistics stats; 581 582 gcc_checking_assert (node->has_gimple_body_p ()); 583 584 if (!opt_for_fn (node->decl, flag_ipa_cp_clone)) 585 { 586 if (dump_file) 587 fprintf (dump_file, "Not considering %s for cloning; " 588 "-fipa-cp-clone disabled.\n", 589 node->name ()); 590 return false; 591 } 592 593 if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl))) 594 { 595 if (dump_file) 596 fprintf (dump_file, "Not considering %s for cloning; " 597 "optimizing it for size.\n", 598 node->name ()); 599 return false; 600 } 601 602 init_caller_stats (&stats); 603 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, false); 604 605 if (inline_summaries->get (node)->self_size < stats.n_calls) 606 { 607 if (dump_file) 608 fprintf (dump_file, "Considering %s for cloning; code might shrink.\n", 609 node->name ()); 610 return true; 611 } 612 613 /* When profile is available and function is hot, propagate into it even if 614 calls seems cold; constant propagation can improve function's speed 615 significantly. */ 616 if (max_count) 617 { 618 if (stats.count_sum > node->count * 90 / 100) 619 { 620 if (dump_file) 621 fprintf (dump_file, "Considering %s for cloning; " 622 "usually called directly.\n", 623 node->name ()); 624 return true; 625 } 626 } 627 if (!stats.n_hot_calls) 628 { 629 if (dump_file) 630 fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n", 631 node->name ()); 632 return false; 633 } 634 if (dump_file) 635 fprintf (dump_file, "Considering %s for cloning.\n", 636 node->name ()); 637 return true; 638} 639 640template <typename valtype> 641class value_topo_info 642{ 643public: 644 /* Head of the linked list of topologically sorted values. */ 645 ipcp_value<valtype> *values_topo; 646 /* Stack for creating SCCs, represented by a linked list too. */ 647 ipcp_value<valtype> *stack; 648 /* Counter driving the algorithm in add_val_to_toposort. */ 649 int dfs_counter; 650 651 value_topo_info () : values_topo (NULL), stack (NULL), dfs_counter (0) 652 {} 653 void add_val (ipcp_value<valtype> *cur_val); 654 void propagate_effects (); 655}; 656 657/* Arrays representing a topological ordering of call graph nodes and a stack 658 of nodes used during constant propagation and also data required to perform 659 topological sort of values and propagation of benefits in the determined 660 order. */ 661 662class ipa_topo_info 663{ 664public: 665 /* Array with obtained topological order of cgraph nodes. */ 666 struct cgraph_node **order; 667 /* Stack of cgraph nodes used during propagation within SCC until all values 668 in the SCC stabilize. */ 669 struct cgraph_node **stack; 670 int nnodes, stack_top; 671 672 value_topo_info<tree> constants; 673 value_topo_info<ipa_polymorphic_call_context> contexts; 674 675 ipa_topo_info () : order(NULL), stack(NULL), nnodes(0), stack_top(0), 676 constants () 677 {} 678}; 679 680/* Allocate the arrays in TOPO and topologically sort the nodes into order. */ 681 682static void 683build_toporder_info (struct ipa_topo_info *topo) 684{ 685 topo->order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count); 686 topo->stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count); 687 688 gcc_checking_assert (topo->stack_top == 0); 689 topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL); 690} 691 692/* Free information about strongly connected components and the arrays in 693 TOPO. */ 694 695static void 696free_toporder_info (struct ipa_topo_info *topo) 697{ 698 ipa_free_postorder_info (); 699 free (topo->order); 700 free (topo->stack); 701} 702 703/* Add NODE to the stack in TOPO, unless it is already there. */ 704 705static inline void 706push_node_to_stack (struct ipa_topo_info *topo, struct cgraph_node *node) 707{ 708 struct ipa_node_params *info = IPA_NODE_REF (node); 709 if (info->node_enqueued) 710 return; 711 info->node_enqueued = 1; 712 topo->stack[topo->stack_top++] = node; 713} 714 715/* Pop a node from the stack in TOPO and return it or return NULL if the stack 716 is empty. */ 717 718static struct cgraph_node * 719pop_node_from_stack (struct ipa_topo_info *topo) 720{ 721 if (topo->stack_top) 722 { 723 struct cgraph_node *node; 724 topo->stack_top--; 725 node = topo->stack[topo->stack_top]; 726 IPA_NODE_REF (node)->node_enqueued = 0; 727 return node; 728 } 729 else 730 return NULL; 731} 732 733/* Set lattice LAT to bottom and return true if it previously was not set as 734 such. */ 735 736template <typename valtype> 737inline bool 738ipcp_lattice<valtype>::set_to_bottom () 739{ 740 bool ret = !bottom; 741 bottom = true; 742 return ret; 743} 744 745/* Mark lattice as containing an unknown value and return true if it previously 746 was not marked as such. */ 747 748template <typename valtype> 749inline bool 750ipcp_lattice<valtype>::set_contains_variable () 751{ 752 bool ret = !contains_variable; 753 contains_variable = true; 754 return ret; 755} 756 757/* Set all aggegate lattices in PLATS to bottom and return true if they were 758 not previously set as such. */ 759 760static inline bool 761set_agg_lats_to_bottom (struct ipcp_param_lattices *plats) 762{ 763 bool ret = !plats->aggs_bottom; 764 plats->aggs_bottom = true; 765 return ret; 766} 767 768/* Mark all aggegate lattices in PLATS as containing an unknown value and 769 return true if they were not previously marked as such. */ 770 771static inline bool 772set_agg_lats_contain_variable (struct ipcp_param_lattices *plats) 773{ 774 bool ret = !plats->aggs_contain_variable; 775 plats->aggs_contain_variable = true; 776 return ret; 777} 778 779/* Return true if alignment information in PLATS is known to be unusable. */ 780 781static inline bool 782alignment_bottom_p (ipcp_param_lattices *plats) 783{ 784 return plats->alignment.known && (plats->alignment.align == 0); 785} 786 787/* Set alignment information in PLATS to unusable. Return true if it 788 previously was usable or unknown. */ 789 790static inline bool 791set_alignment_to_bottom (ipcp_param_lattices *plats) 792{ 793 if (alignment_bottom_p (plats)) 794 return false; 795 plats->alignment.known = true; 796 plats->alignment.align = 0; 797 return true; 798} 799 800/* Mark bot aggregate and scalar lattices as containing an unknown variable, 801 return true is any of them has not been marked as such so far. */ 802 803static inline bool 804set_all_contains_variable (struct ipcp_param_lattices *plats) 805{ 806 bool ret; 807 ret = plats->itself.set_contains_variable (); 808 ret |= plats->ctxlat.set_contains_variable (); 809 ret |= set_agg_lats_contain_variable (plats); 810 ret |= set_alignment_to_bottom (plats); 811 return ret; 812} 813 814/* Worker of call_for_symbol_thunks_and_aliases, increment the integer DATA 815 points to by the number of callers to NODE. */ 816 817static bool 818count_callers (cgraph_node *node, void *data) 819{ 820 int *caller_count = (int *) data; 821 822 for (cgraph_edge *cs = node->callers; cs; cs = cs->next_caller) 823 /* Local thunks can be handled transparently, but if the thunk can not 824 be optimized out, count it as a real use. */ 825 if (!cs->caller->thunk.thunk_p || !cs->caller->local.local) 826 ++*caller_count; 827 return false; 828} 829 830/* Worker of call_for_symbol_thunks_and_aliases, it is supposed to be called on 831 the one caller of some other node. Set the caller's corresponding flag. */ 832 833static bool 834set_single_call_flag (cgraph_node *node, void *) 835{ 836 cgraph_edge *cs = node->callers; 837 /* Local thunks can be handled transparently, skip them. */ 838 while (cs && cs->caller->thunk.thunk_p && cs->caller->local.local) 839 cs = cs->next_caller; 840 if (cs) 841 { 842 IPA_NODE_REF (cs->caller)->node_calling_single_call = true; 843 return true; 844 } 845 return false; 846} 847 848/* Initialize ipcp_lattices. */ 849 850static void 851initialize_node_lattices (struct cgraph_node *node) 852{ 853 struct ipa_node_params *info = IPA_NODE_REF (node); 854 struct cgraph_edge *ie; 855 bool disable = false, variable = false; 856 int i; 857 858 gcc_checking_assert (node->has_gimple_body_p ()); 859 if (cgraph_local_p (node)) 860 { 861 int caller_count = 0; 862 node->call_for_symbol_thunks_and_aliases (count_callers, &caller_count, 863 true); 864 gcc_checking_assert (caller_count > 0); 865 if (caller_count == 1) 866 node->call_for_symbol_thunks_and_aliases (set_single_call_flag, 867 NULL, true); 868 } 869 else 870 { 871 /* When cloning is allowed, we can assume that externally visible 872 functions are not called. We will compensate this by cloning 873 later. */ 874 if (ipcp_versionable_function_p (node) 875 && ipcp_cloning_candidate_p (node)) 876 variable = true; 877 else 878 disable = true; 879 } 880 881 if (disable || variable) 882 { 883 for (i = 0; i < ipa_get_param_count (info) ; i++) 884 { 885 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); 886 if (disable) 887 { 888 plats->itself.set_to_bottom (); 889 plats->ctxlat.set_to_bottom (); 890 set_agg_lats_to_bottom (plats); 891 set_alignment_to_bottom (plats); 892 } 893 else 894 set_all_contains_variable (plats); 895 } 896 if (dump_file && (dump_flags & TDF_DETAILS) 897 && !node->alias && !node->thunk.thunk_p) 898 fprintf (dump_file, "Marking all lattices of %s/%i as %s\n", 899 node->name (), node->order, 900 disable ? "BOTTOM" : "VARIABLE"); 901 } 902 903 for (ie = node->indirect_calls; ie; ie = ie->next_callee) 904 if (ie->indirect_info->polymorphic 905 && ie->indirect_info->param_index >= 0) 906 { 907 gcc_checking_assert (ie->indirect_info->param_index >= 0); 908 ipa_get_parm_lattices (info, 909 ie->indirect_info->param_index)->virt_call = 1; 910 } 911} 912 913/* Return the result of a (possibly arithmetic) pass through jump function 914 JFUNC on the constant value INPUT. Return NULL_TREE if that cannot be 915 determined or be considered an interprocedural invariant. */ 916 917static tree 918ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input) 919{ 920 tree restype, res; 921 922 gcc_checking_assert (is_gimple_ip_invariant (input)); 923 if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR) 924 return input; 925 926 if (TREE_CODE_CLASS (ipa_get_jf_pass_through_operation (jfunc)) 927 == tcc_comparison) 928 restype = boolean_type_node; 929 else 930 restype = TREE_TYPE (input); 931 res = fold_binary (ipa_get_jf_pass_through_operation (jfunc), restype, 932 input, ipa_get_jf_pass_through_operand (jfunc)); 933 934 if (res && !is_gimple_ip_invariant (res)) 935 return NULL_TREE; 936 937 return res; 938} 939 940/* Return the result of an ancestor jump function JFUNC on the constant value 941 INPUT. Return NULL_TREE if that cannot be determined. */ 942 943static tree 944ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input) 945{ 946 gcc_checking_assert (TREE_CODE (input) != TREE_BINFO); 947 if (TREE_CODE (input) == ADDR_EXPR) 948 { 949 tree t = TREE_OPERAND (input, 0); 950 t = build_ref_for_offset (EXPR_LOCATION (t), t, 951 ipa_get_jf_ancestor_offset (jfunc), 952 ptr_type_node, NULL, false); 953 return build_fold_addr_expr (t); 954 } 955 else 956 return NULL_TREE; 957} 958 959/* Determine whether JFUNC evaluates to a single known constant value and if 960 so, return it. Otherwise return NULL. INFO describes the caller node or 961 the one it is inlined to, so that pass-through jump functions can be 962 evaluated. */ 963 964tree 965ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc) 966{ 967 if (jfunc->type == IPA_JF_CONST) 968 return ipa_get_jf_constant (jfunc); 969 else if (jfunc->type == IPA_JF_PASS_THROUGH 970 || jfunc->type == IPA_JF_ANCESTOR) 971 { 972 tree input; 973 int idx; 974 975 if (jfunc->type == IPA_JF_PASS_THROUGH) 976 idx = ipa_get_jf_pass_through_formal_id (jfunc); 977 else 978 idx = ipa_get_jf_ancestor_formal_id (jfunc); 979 980 if (info->ipcp_orig_node) 981 input = info->known_csts[idx]; 982 else 983 { 984 ipcp_lattice<tree> *lat; 985 986 if (!info->lattices 987 || idx >= ipa_get_param_count (info)) 988 return NULL_TREE; 989 lat = ipa_get_scalar_lat (info, idx); 990 if (!lat->is_single_const ()) 991 return NULL_TREE; 992 input = lat->values->value; 993 } 994 995 if (!input) 996 return NULL_TREE; 997 998 if (jfunc->type == IPA_JF_PASS_THROUGH) 999 return ipa_get_jf_pass_through_result (jfunc, input); 1000 else 1001 return ipa_get_jf_ancestor_result (jfunc, input); 1002 } 1003 else 1004 return NULL_TREE; 1005} 1006 1007/* Determie whether JFUNC evaluates to single known polymorphic context, given 1008 that INFO describes the caller node or the one it is inlined to, CS is the 1009 call graph edge corresponding to JFUNC and CSIDX index of the described 1010 parameter. */ 1011 1012ipa_polymorphic_call_context 1013ipa_context_from_jfunc (ipa_node_params *info, cgraph_edge *cs, int csidx, 1014 ipa_jump_func *jfunc) 1015{ 1016 ipa_edge_args *args = IPA_EDGE_REF (cs); 1017 ipa_polymorphic_call_context ctx; 1018 ipa_polymorphic_call_context *edge_ctx 1019 = cs ? ipa_get_ith_polymorhic_call_context (args, csidx) : NULL; 1020 1021 if (edge_ctx && !edge_ctx->useless_p ()) 1022 ctx = *edge_ctx; 1023 1024 if (jfunc->type == IPA_JF_PASS_THROUGH 1025 || jfunc->type == IPA_JF_ANCESTOR) 1026 { 1027 ipa_polymorphic_call_context srcctx; 1028 int srcidx; 1029 bool type_preserved = true; 1030 if (jfunc->type == IPA_JF_PASS_THROUGH) 1031 { 1032 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR) 1033 return ctx; 1034 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc); 1035 srcidx = ipa_get_jf_pass_through_formal_id (jfunc); 1036 } 1037 else 1038 { 1039 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc); 1040 srcidx = ipa_get_jf_ancestor_formal_id (jfunc); 1041 } 1042 if (info->ipcp_orig_node) 1043 { 1044 if (info->known_contexts.exists ()) 1045 srcctx = info->known_contexts[srcidx]; 1046 } 1047 else 1048 { 1049 if (!info->lattices 1050 || srcidx >= ipa_get_param_count (info)) 1051 return ctx; 1052 ipcp_lattice<ipa_polymorphic_call_context> *lat; 1053 lat = ipa_get_poly_ctx_lat (info, srcidx); 1054 if (!lat->is_single_const ()) 1055 return ctx; 1056 srcctx = lat->values->value; 1057 } 1058 if (srcctx.useless_p ()) 1059 return ctx; 1060 if (jfunc->type == IPA_JF_ANCESTOR) 1061 srcctx.offset_by (ipa_get_jf_ancestor_offset (jfunc)); 1062 if (!type_preserved) 1063 srcctx.possible_dynamic_type_change (cs->in_polymorphic_cdtor); 1064 srcctx.combine_with (ctx); 1065 return srcctx; 1066 } 1067 1068 return ctx; 1069} 1070 1071/* If checking is enabled, verify that no lattice is in the TOP state, i.e. not 1072 bottom, not containing a variable component and without any known value at 1073 the same time. */ 1074 1075DEBUG_FUNCTION void 1076ipcp_verify_propagated_values (void) 1077{ 1078 struct cgraph_node *node; 1079 1080 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) 1081 { 1082 struct ipa_node_params *info = IPA_NODE_REF (node); 1083 int i, count = ipa_get_param_count (info); 1084 1085 for (i = 0; i < count; i++) 1086 { 1087 ipcp_lattice<tree> *lat = ipa_get_scalar_lat (info, i); 1088 1089 if (!lat->bottom 1090 && !lat->contains_variable 1091 && lat->values_count == 0) 1092 { 1093 if (dump_file) 1094 { 1095 symtab_node::dump_table (dump_file); 1096 fprintf (dump_file, "\nIPA lattices after constant " 1097 "propagation, before gcc_unreachable:\n"); 1098 print_all_lattices (dump_file, true, false); 1099 } 1100 1101 gcc_unreachable (); 1102 } 1103 } 1104 } 1105} 1106 1107/* Return true iff X and Y should be considered equal values by IPA-CP. */ 1108 1109static bool 1110values_equal_for_ipcp_p (tree x, tree y) 1111{ 1112 gcc_checking_assert (x != NULL_TREE && y != NULL_TREE); 1113 1114 if (x == y) 1115 return true; 1116 1117 if (TREE_CODE (x) == ADDR_EXPR 1118 && TREE_CODE (y) == ADDR_EXPR 1119 && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL 1120 && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL) 1121 return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)), 1122 DECL_INITIAL (TREE_OPERAND (y, 0)), 0); 1123 else 1124 return operand_equal_p (x, y, 0); 1125} 1126 1127/* Return true iff X and Y should be considered equal contexts by IPA-CP. */ 1128 1129static bool 1130values_equal_for_ipcp_p (ipa_polymorphic_call_context x, 1131 ipa_polymorphic_call_context y) 1132{ 1133 return x.equal_to (y); 1134} 1135 1136 1137/* Add a new value source to the value represented by THIS, marking that a 1138 value comes from edge CS and (if the underlying jump function is a 1139 pass-through or an ancestor one) from a caller value SRC_VAL of a caller 1140 parameter described by SRC_INDEX. OFFSET is negative if the source was the 1141 scalar value of the parameter itself or the offset within an aggregate. */ 1142 1143template <typename valtype> 1144void 1145ipcp_value<valtype>::add_source (cgraph_edge *cs, ipcp_value *src_val, 1146 int src_idx, HOST_WIDE_INT offset) 1147{ 1148 ipcp_value_source<valtype> *src; 1149 1150 src = new (pool_alloc (ipcp_sources_pool)) ipcp_value_source<valtype>; 1151 src->offset = offset; 1152 src->cs = cs; 1153 src->val = src_val; 1154 src->index = src_idx; 1155 1156 src->next = sources; 1157 sources = src; 1158} 1159 1160/* Allocate a new ipcp_value holding a tree constant, initialize its value to 1161 SOURCE and clear all other fields. */ 1162 1163static ipcp_value<tree> * 1164allocate_and_init_ipcp_value (tree source) 1165{ 1166 ipcp_value<tree> *val; 1167 1168 val = new (pool_alloc (ipcp_cst_values_pool)) ipcp_value<tree>; 1169 memset (val, 0, sizeof (*val)); 1170 val->value = source; 1171 return val; 1172} 1173 1174/* Allocate a new ipcp_value holding a polymorphic context, initialize its 1175 value to SOURCE and clear all other fields. */ 1176 1177static ipcp_value<ipa_polymorphic_call_context> * 1178allocate_and_init_ipcp_value (ipa_polymorphic_call_context source) 1179{ 1180 ipcp_value<ipa_polymorphic_call_context> *val; 1181 1182 val = new (pool_alloc (ipcp_poly_ctx_values_pool)) 1183 ipcp_value<ipa_polymorphic_call_context>; 1184 memset (val, 0, sizeof (*val)); 1185 val->value = source; 1186 return val; 1187} 1188 1189/* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS, 1190 SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same 1191 meaning. OFFSET -1 means the source is scalar and not a part of an 1192 aggregate. */ 1193 1194template <typename valtype> 1195bool 1196ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs, 1197 ipcp_value<valtype> *src_val, 1198 int src_idx, HOST_WIDE_INT offset) 1199{ 1200 ipcp_value<valtype> *val; 1201 1202 if (bottom) 1203 return false; 1204 1205 for (val = values; val; val = val->next) 1206 if (values_equal_for_ipcp_p (val->value, newval)) 1207 { 1208 if (ipa_edge_within_scc (cs)) 1209 { 1210 ipcp_value_source<valtype> *s; 1211 for (s = val->sources; s ; s = s->next) 1212 if (s->cs == cs) 1213 break; 1214 if (s) 1215 return false; 1216 } 1217 1218 val->add_source (cs, src_val, src_idx, offset); 1219 return false; 1220 } 1221 1222 if (values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE)) 1223 { 1224 /* We can only free sources, not the values themselves, because sources 1225 of other values in this this SCC might point to them. */ 1226 for (val = values; val; val = val->next) 1227 { 1228 while (val->sources) 1229 { 1230 ipcp_value_source<valtype> *src = val->sources; 1231 val->sources = src->next; 1232 pool_free (ipcp_sources_pool, src); 1233 } 1234 } 1235 1236 values = NULL; 1237 return set_to_bottom (); 1238 } 1239 1240 values_count++; 1241 val = allocate_and_init_ipcp_value (newval); 1242 val->add_source (cs, src_val, src_idx, offset); 1243 val->next = values; 1244 values = val; 1245 return true; 1246} 1247 1248/* Propagate values through a pass-through jump function JFUNC associated with 1249 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX 1250 is the index of the source parameter. */ 1251 1252static bool 1253propagate_vals_accross_pass_through (cgraph_edge *cs, 1254 ipa_jump_func *jfunc, 1255 ipcp_lattice<tree> *src_lat, 1256 ipcp_lattice<tree> *dest_lat, 1257 int src_idx) 1258{ 1259 ipcp_value<tree> *src_val; 1260 bool ret = false; 1261 1262 /* Do not create new values when propagating within an SCC because if there 1263 are arithmetic functions with circular dependencies, there is infinite 1264 number of them and we would just make lattices bottom. */ 1265 if ((ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR) 1266 && ipa_edge_within_scc (cs)) 1267 ret = dest_lat->set_contains_variable (); 1268 else 1269 for (src_val = src_lat->values; src_val; src_val = src_val->next) 1270 { 1271 tree cstval = ipa_get_jf_pass_through_result (jfunc, src_val->value); 1272 1273 if (cstval) 1274 ret |= dest_lat->add_value (cstval, cs, src_val, src_idx); 1275 else 1276 ret |= dest_lat->set_contains_variable (); 1277 } 1278 1279 return ret; 1280} 1281 1282/* Propagate values through an ancestor jump function JFUNC associated with 1283 edge CS, taking values from SRC_LAT and putting them into DEST_LAT. SRC_IDX 1284 is the index of the source parameter. */ 1285 1286static bool 1287propagate_vals_accross_ancestor (struct cgraph_edge *cs, 1288 struct ipa_jump_func *jfunc, 1289 ipcp_lattice<tree> *src_lat, 1290 ipcp_lattice<tree> *dest_lat, 1291 int src_idx) 1292{ 1293 ipcp_value<tree> *src_val; 1294 bool ret = false; 1295 1296 if (ipa_edge_within_scc (cs)) 1297 return dest_lat->set_contains_variable (); 1298 1299 for (src_val = src_lat->values; src_val; src_val = src_val->next) 1300 { 1301 tree t = ipa_get_jf_ancestor_result (jfunc, src_val->value); 1302 1303 if (t) 1304 ret |= dest_lat->add_value (t, cs, src_val, src_idx); 1305 else 1306 ret |= dest_lat->set_contains_variable (); 1307 } 1308 1309 return ret; 1310} 1311 1312/* Propagate scalar values across jump function JFUNC that is associated with 1313 edge CS and put the values into DEST_LAT. */ 1314 1315static bool 1316propagate_scalar_accross_jump_function (struct cgraph_edge *cs, 1317 struct ipa_jump_func *jfunc, 1318 ipcp_lattice<tree> *dest_lat) 1319{ 1320 if (dest_lat->bottom) 1321 return false; 1322 1323 if (jfunc->type == IPA_JF_CONST) 1324 { 1325 tree val = ipa_get_jf_constant (jfunc); 1326 return dest_lat->add_value (val, cs, NULL, 0); 1327 } 1328 else if (jfunc->type == IPA_JF_PASS_THROUGH 1329 || jfunc->type == IPA_JF_ANCESTOR) 1330 { 1331 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); 1332 ipcp_lattice<tree> *src_lat; 1333 int src_idx; 1334 bool ret; 1335 1336 if (jfunc->type == IPA_JF_PASS_THROUGH) 1337 src_idx = ipa_get_jf_pass_through_formal_id (jfunc); 1338 else 1339 src_idx = ipa_get_jf_ancestor_formal_id (jfunc); 1340 1341 src_lat = ipa_get_scalar_lat (caller_info, src_idx); 1342 if (src_lat->bottom) 1343 return dest_lat->set_contains_variable (); 1344 1345 /* If we would need to clone the caller and cannot, do not propagate. */ 1346 if (!ipcp_versionable_function_p (cs->caller) 1347 && (src_lat->contains_variable 1348 || (src_lat->values_count > 1))) 1349 return dest_lat->set_contains_variable (); 1350 1351 if (jfunc->type == IPA_JF_PASS_THROUGH) 1352 ret = propagate_vals_accross_pass_through (cs, jfunc, src_lat, 1353 dest_lat, src_idx); 1354 else 1355 ret = propagate_vals_accross_ancestor (cs, jfunc, src_lat, dest_lat, 1356 src_idx); 1357 1358 if (src_lat->contains_variable) 1359 ret |= dest_lat->set_contains_variable (); 1360 1361 return ret; 1362 } 1363 1364 /* TODO: We currently do not handle member method pointers in IPA-CP (we only 1365 use it for indirect inlining), we should propagate them too. */ 1366 return dest_lat->set_contains_variable (); 1367} 1368 1369/* Propagate scalar values across jump function JFUNC that is associated with 1370 edge CS and describes argument IDX and put the values into DEST_LAT. */ 1371 1372static bool 1373propagate_context_accross_jump_function (cgraph_edge *cs, 1374 ipa_jump_func *jfunc, int idx, 1375 ipcp_lattice<ipa_polymorphic_call_context> *dest_lat) 1376{ 1377 ipa_edge_args *args = IPA_EDGE_REF (cs); 1378 if (dest_lat->bottom) 1379 return false; 1380 bool ret = false; 1381 bool added_sth = false; 1382 bool type_preserved = true; 1383 1384 ipa_polymorphic_call_context edge_ctx, *edge_ctx_ptr 1385 = ipa_get_ith_polymorhic_call_context (args, idx); 1386 1387 if (edge_ctx_ptr) 1388 edge_ctx = *edge_ctx_ptr; 1389 1390 if (jfunc->type == IPA_JF_PASS_THROUGH 1391 || jfunc->type == IPA_JF_ANCESTOR) 1392 { 1393 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); 1394 int src_idx; 1395 ipcp_lattice<ipa_polymorphic_call_context> *src_lat; 1396 1397 /* TODO: Once we figure out how to propagate speculations, it will 1398 probably be a good idea to switch to speculation if type_preserved is 1399 not set instead of punting. */ 1400 if (jfunc->type == IPA_JF_PASS_THROUGH) 1401 { 1402 if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR) 1403 goto prop_fail; 1404 type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc); 1405 src_idx = ipa_get_jf_pass_through_formal_id (jfunc); 1406 } 1407 else 1408 { 1409 type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc); 1410 src_idx = ipa_get_jf_ancestor_formal_id (jfunc); 1411 } 1412 1413 src_lat = ipa_get_poly_ctx_lat (caller_info, src_idx); 1414 /* If we would need to clone the caller and cannot, do not propagate. */ 1415 if (!ipcp_versionable_function_p (cs->caller) 1416 && (src_lat->contains_variable 1417 || (src_lat->values_count > 1))) 1418 goto prop_fail; 1419 1420 ipcp_value<ipa_polymorphic_call_context> *src_val; 1421 for (src_val = src_lat->values; src_val; src_val = src_val->next) 1422 { 1423 ipa_polymorphic_call_context cur = src_val->value; 1424 1425 if (!type_preserved) 1426 cur.possible_dynamic_type_change (cs->in_polymorphic_cdtor); 1427 if (jfunc->type == IPA_JF_ANCESTOR) 1428 cur.offset_by (ipa_get_jf_ancestor_offset (jfunc)); 1429 /* TODO: In cases we know how the context is going to be used, 1430 we can improve the result by passing proper OTR_TYPE. */ 1431 cur.combine_with (edge_ctx); 1432 if (!cur.useless_p ()) 1433 { 1434 if (src_lat->contains_variable 1435 && !edge_ctx.equal_to (cur)) 1436 ret |= dest_lat->set_contains_variable (); 1437 ret |= dest_lat->add_value (cur, cs, src_val, src_idx); 1438 added_sth = true; 1439 } 1440 } 1441 1442 } 1443 1444 prop_fail: 1445 if (!added_sth) 1446 { 1447 if (!edge_ctx.useless_p ()) 1448 ret |= dest_lat->add_value (edge_ctx, cs); 1449 else 1450 ret |= dest_lat->set_contains_variable (); 1451 } 1452 1453 return ret; 1454} 1455 1456/* Propagate alignments across jump function JFUNC that is associated with 1457 edge CS and update DEST_LAT accordingly. */ 1458 1459static bool 1460propagate_alignment_accross_jump_function (struct cgraph_edge *cs, 1461 struct ipa_jump_func *jfunc, 1462 struct ipcp_param_lattices *dest_lat) 1463{ 1464 if (alignment_bottom_p (dest_lat)) 1465 return false; 1466 1467 ipa_alignment cur; 1468 cur.known = false; 1469 if (jfunc->alignment.known) 1470 cur = jfunc->alignment; 1471 else if (jfunc->type == IPA_JF_PASS_THROUGH 1472 || jfunc->type == IPA_JF_ANCESTOR) 1473 { 1474 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); 1475 struct ipcp_param_lattices *src_lats; 1476 HOST_WIDE_INT offset = 0; 1477 int src_idx; 1478 1479 if (jfunc->type == IPA_JF_PASS_THROUGH) 1480 { 1481 enum tree_code op = ipa_get_jf_pass_through_operation (jfunc); 1482 if (op != NOP_EXPR) 1483 { 1484 if (op != POINTER_PLUS_EXPR 1485 && op != PLUS_EXPR) 1486 goto prop_fail; 1487 tree operand = ipa_get_jf_pass_through_operand (jfunc); 1488 if (!tree_fits_shwi_p (operand)) 1489 goto prop_fail; 1490 offset = tree_to_shwi (operand); 1491 } 1492 src_idx = ipa_get_jf_pass_through_formal_id (jfunc); 1493 } 1494 else 1495 { 1496 src_idx = ipa_get_jf_ancestor_formal_id (jfunc); 1497 offset = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT;; 1498 } 1499 1500 src_lats = ipa_get_parm_lattices (caller_info, src_idx); 1501 if (!src_lats->alignment.known 1502 || alignment_bottom_p (src_lats)) 1503 goto prop_fail; 1504 1505 cur = src_lats->alignment; 1506 cur.misalign = (cur.misalign + offset) % cur.align; 1507 } 1508 1509 if (cur.known) 1510 { 1511 if (!dest_lat->alignment.known) 1512 { 1513 dest_lat->alignment = cur; 1514 return true; 1515 } 1516 else if (dest_lat->alignment.align == cur.align 1517 && dest_lat->alignment.misalign == cur.misalign) 1518 return false; 1519 } 1520 1521 prop_fail: 1522 set_alignment_to_bottom (dest_lat); 1523 return true; 1524} 1525 1526/* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches 1527 NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all 1528 other cases, return false). If there are no aggregate items, set 1529 aggs_by_ref to NEW_AGGS_BY_REF. */ 1530 1531static bool 1532set_check_aggs_by_ref (struct ipcp_param_lattices *dest_plats, 1533 bool new_aggs_by_ref) 1534{ 1535 if (dest_plats->aggs) 1536 { 1537 if (dest_plats->aggs_by_ref != new_aggs_by_ref) 1538 { 1539 set_agg_lats_to_bottom (dest_plats); 1540 return true; 1541 } 1542 } 1543 else 1544 dest_plats->aggs_by_ref = new_aggs_by_ref; 1545 return false; 1546} 1547 1548/* Walk aggregate lattices in DEST_PLATS from ***AGLAT on, until ***aglat is an 1549 already existing lattice for the given OFFSET and SIZE, marking all skipped 1550 lattices as containing variable and checking for overlaps. If there is no 1551 already existing lattice for the OFFSET and VAL_SIZE, create one, initialize 1552 it with offset, size and contains_variable to PRE_EXISTING, and return true, 1553 unless there are too many already. If there are two many, return false. If 1554 there are overlaps turn whole DEST_PLATS to bottom and return false. If any 1555 skipped lattices were newly marked as containing variable, set *CHANGE to 1556 true. */ 1557 1558static bool 1559merge_agg_lats_step (struct ipcp_param_lattices *dest_plats, 1560 HOST_WIDE_INT offset, HOST_WIDE_INT val_size, 1561 struct ipcp_agg_lattice ***aglat, 1562 bool pre_existing, bool *change) 1563{ 1564 gcc_checking_assert (offset >= 0); 1565 1566 while (**aglat && (**aglat)->offset < offset) 1567 { 1568 if ((**aglat)->offset + (**aglat)->size > offset) 1569 { 1570 set_agg_lats_to_bottom (dest_plats); 1571 return false; 1572 } 1573 *change |= (**aglat)->set_contains_variable (); 1574 *aglat = &(**aglat)->next; 1575 } 1576 1577 if (**aglat && (**aglat)->offset == offset) 1578 { 1579 if ((**aglat)->size != val_size 1580 || ((**aglat)->next 1581 && (**aglat)->next->offset < offset + val_size)) 1582 { 1583 set_agg_lats_to_bottom (dest_plats); 1584 return false; 1585 } 1586 gcc_checking_assert (!(**aglat)->next 1587 || (**aglat)->next->offset >= offset + val_size); 1588 return true; 1589 } 1590 else 1591 { 1592 struct ipcp_agg_lattice *new_al; 1593 1594 if (**aglat && (**aglat)->offset < offset + val_size) 1595 { 1596 set_agg_lats_to_bottom (dest_plats); 1597 return false; 1598 } 1599 if (dest_plats->aggs_count == PARAM_VALUE (PARAM_IPA_MAX_AGG_ITEMS)) 1600 return false; 1601 dest_plats->aggs_count++; 1602 new_al = (struct ipcp_agg_lattice *) pool_alloc (ipcp_agg_lattice_pool); 1603 memset (new_al, 0, sizeof (*new_al)); 1604 1605 new_al->offset = offset; 1606 new_al->size = val_size; 1607 new_al->contains_variable = pre_existing; 1608 1609 new_al->next = **aglat; 1610 **aglat = new_al; 1611 return true; 1612 } 1613} 1614 1615/* Set all AGLAT and all other aggregate lattices reachable by next pointers as 1616 containing an unknown value. */ 1617 1618static bool 1619set_chain_of_aglats_contains_variable (struct ipcp_agg_lattice *aglat) 1620{ 1621 bool ret = false; 1622 while (aglat) 1623 { 1624 ret |= aglat->set_contains_variable (); 1625 aglat = aglat->next; 1626 } 1627 return ret; 1628} 1629 1630/* Merge existing aggregate lattices in SRC_PLATS to DEST_PLATS, subtracting 1631 DELTA_OFFSET. CS is the call graph edge and SRC_IDX the index of the source 1632 parameter used for lattice value sources. Return true if DEST_PLATS changed 1633 in any way. */ 1634 1635static bool 1636merge_aggregate_lattices (struct cgraph_edge *cs, 1637 struct ipcp_param_lattices *dest_plats, 1638 struct ipcp_param_lattices *src_plats, 1639 int src_idx, HOST_WIDE_INT offset_delta) 1640{ 1641 bool pre_existing = dest_plats->aggs != NULL; 1642 struct ipcp_agg_lattice **dst_aglat; 1643 bool ret = false; 1644 1645 if (set_check_aggs_by_ref (dest_plats, src_plats->aggs_by_ref)) 1646 return true; 1647 if (src_plats->aggs_bottom) 1648 return set_agg_lats_contain_variable (dest_plats); 1649 if (src_plats->aggs_contain_variable) 1650 ret |= set_agg_lats_contain_variable (dest_plats); 1651 dst_aglat = &dest_plats->aggs; 1652 1653 for (struct ipcp_agg_lattice *src_aglat = src_plats->aggs; 1654 src_aglat; 1655 src_aglat = src_aglat->next) 1656 { 1657 HOST_WIDE_INT new_offset = src_aglat->offset - offset_delta; 1658 1659 if (new_offset < 0) 1660 continue; 1661 if (merge_agg_lats_step (dest_plats, new_offset, src_aglat->size, 1662 &dst_aglat, pre_existing, &ret)) 1663 { 1664 struct ipcp_agg_lattice *new_al = *dst_aglat; 1665 1666 dst_aglat = &(*dst_aglat)->next; 1667 if (src_aglat->bottom) 1668 { 1669 ret |= new_al->set_contains_variable (); 1670 continue; 1671 } 1672 if (src_aglat->contains_variable) 1673 ret |= new_al->set_contains_variable (); 1674 for (ipcp_value<tree> *val = src_aglat->values; 1675 val; 1676 val = val->next) 1677 ret |= new_al->add_value (val->value, cs, val, src_idx, 1678 src_aglat->offset); 1679 } 1680 else if (dest_plats->aggs_bottom) 1681 return true; 1682 } 1683 ret |= set_chain_of_aglats_contains_variable (*dst_aglat); 1684 return ret; 1685} 1686 1687/* Determine whether there is anything to propagate FROM SRC_PLATS through a 1688 pass-through JFUNC and if so, whether it has conform and conforms to the 1689 rules about propagating values passed by reference. */ 1690 1691static bool 1692agg_pass_through_permissible_p (struct ipcp_param_lattices *src_plats, 1693 struct ipa_jump_func *jfunc) 1694{ 1695 return src_plats->aggs 1696 && (!src_plats->aggs_by_ref 1697 || ipa_get_jf_pass_through_agg_preserved (jfunc)); 1698} 1699 1700/* Propagate scalar values across jump function JFUNC that is associated with 1701 edge CS and put the values into DEST_LAT. */ 1702 1703static bool 1704propagate_aggs_accross_jump_function (struct cgraph_edge *cs, 1705 struct ipa_jump_func *jfunc, 1706 struct ipcp_param_lattices *dest_plats) 1707{ 1708 bool ret = false; 1709 1710 if (dest_plats->aggs_bottom) 1711 return false; 1712 1713 if (jfunc->type == IPA_JF_PASS_THROUGH 1714 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR) 1715 { 1716 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); 1717 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc); 1718 struct ipcp_param_lattices *src_plats; 1719 1720 src_plats = ipa_get_parm_lattices (caller_info, src_idx); 1721 if (agg_pass_through_permissible_p (src_plats, jfunc)) 1722 { 1723 /* Currently we do not produce clobber aggregate jump 1724 functions, replace with merging when we do. */ 1725 gcc_assert (!jfunc->agg.items); 1726 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, 1727 src_idx, 0); 1728 } 1729 else 1730 ret |= set_agg_lats_contain_variable (dest_plats); 1731 } 1732 else if (jfunc->type == IPA_JF_ANCESTOR 1733 && ipa_get_jf_ancestor_agg_preserved (jfunc)) 1734 { 1735 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); 1736 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc); 1737 struct ipcp_param_lattices *src_plats; 1738 1739 src_plats = ipa_get_parm_lattices (caller_info, src_idx); 1740 if (src_plats->aggs && src_plats->aggs_by_ref) 1741 { 1742 /* Currently we do not produce clobber aggregate jump 1743 functions, replace with merging when we do. */ 1744 gcc_assert (!jfunc->agg.items); 1745 ret |= merge_aggregate_lattices (cs, dest_plats, src_plats, src_idx, 1746 ipa_get_jf_ancestor_offset (jfunc)); 1747 } 1748 else if (!src_plats->aggs_by_ref) 1749 ret |= set_agg_lats_to_bottom (dest_plats); 1750 else 1751 ret |= set_agg_lats_contain_variable (dest_plats); 1752 } 1753 else if (jfunc->agg.items) 1754 { 1755 bool pre_existing = dest_plats->aggs != NULL; 1756 struct ipcp_agg_lattice **aglat = &dest_plats->aggs; 1757 struct ipa_agg_jf_item *item; 1758 int i; 1759 1760 if (set_check_aggs_by_ref (dest_plats, jfunc->agg.by_ref)) 1761 return true; 1762 1763 FOR_EACH_VEC_ELT (*jfunc->agg.items, i, item) 1764 { 1765 HOST_WIDE_INT val_size; 1766 1767 if (item->offset < 0) 1768 continue; 1769 gcc_checking_assert (is_gimple_ip_invariant (item->value)); 1770 val_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (item->value))); 1771 1772 if (merge_agg_lats_step (dest_plats, item->offset, val_size, 1773 &aglat, pre_existing, &ret)) 1774 { 1775 ret |= (*aglat)->add_value (item->value, cs, NULL, 0, 0); 1776 aglat = &(*aglat)->next; 1777 } 1778 else if (dest_plats->aggs_bottom) 1779 return true; 1780 } 1781 1782 ret |= set_chain_of_aglats_contains_variable (*aglat); 1783 } 1784 else 1785 ret |= set_agg_lats_contain_variable (dest_plats); 1786 1787 return ret; 1788} 1789 1790/* Return true if on the way cfrom CS->caller to the final (non-alias and 1791 non-thunk) destination, the call passes through a thunk. */ 1792 1793static bool 1794call_passes_through_thunk_p (cgraph_edge *cs) 1795{ 1796 cgraph_node *alias_or_thunk = cs->callee; 1797 while (alias_or_thunk->alias) 1798 alias_or_thunk = alias_or_thunk->get_alias_target (); 1799 return alias_or_thunk->thunk.thunk_p; 1800} 1801 1802/* Propagate constants from the caller to the callee of CS. INFO describes the 1803 caller. */ 1804 1805static bool 1806propagate_constants_accross_call (struct cgraph_edge *cs) 1807{ 1808 struct ipa_node_params *callee_info; 1809 enum availability availability; 1810 cgraph_node *callee; 1811 struct ipa_edge_args *args; 1812 bool ret = false; 1813 int i, args_count, parms_count; 1814 1815 callee = cs->callee->function_symbol (&availability); 1816 if (!callee->definition) 1817 return false; 1818 gcc_checking_assert (callee->has_gimple_body_p ()); 1819 callee_info = IPA_NODE_REF (callee); 1820 1821 args = IPA_EDGE_REF (cs); 1822 args_count = ipa_get_cs_argument_count (args); 1823 parms_count = ipa_get_param_count (callee_info); 1824 if (parms_count == 0) 1825 return false; 1826 1827 /* No propagation through instrumentation thunks is available yet. 1828 It should be possible with proper mapping of call args and 1829 instrumented callee params in the propagation loop below. But 1830 this case mostly occurs when legacy code calls instrumented code 1831 and it is not a primary target for optimizations. 1832 We detect instrumentation thunks in aliases and thunks chain by 1833 checking instrumentation_clone flag for chain source and target. 1834 Going through instrumentation thunks we always have it changed 1835 from 0 to 1 and all other nodes do not change it. */ 1836 if (!cs->callee->instrumentation_clone 1837 && callee->instrumentation_clone) 1838 { 1839 for (i = 0; i < parms_count; i++) 1840 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, 1841 i)); 1842 return ret; 1843 } 1844 1845 /* If this call goes through a thunk we must not propagate to the first (0th) 1846 parameter. However, we might need to uncover a thunk from below a series 1847 of aliases first. */ 1848 if (call_passes_through_thunk_p (cs)) 1849 { 1850 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, 1851 0)); 1852 i = 1; 1853 } 1854 else 1855 i = 0; 1856 1857 for (; (i < args_count) && (i < parms_count); i++) 1858 { 1859 struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i); 1860 struct ipcp_param_lattices *dest_plats; 1861 1862 dest_plats = ipa_get_parm_lattices (callee_info, i); 1863 if (availability == AVAIL_INTERPOSABLE) 1864 ret |= set_all_contains_variable (dest_plats); 1865 else 1866 { 1867 ret |= propagate_scalar_accross_jump_function (cs, jump_func, 1868 &dest_plats->itself); 1869 ret |= propagate_context_accross_jump_function (cs, jump_func, i, 1870 &dest_plats->ctxlat); 1871 ret |= propagate_alignment_accross_jump_function (cs, jump_func, 1872 dest_plats); 1873 ret |= propagate_aggs_accross_jump_function (cs, jump_func, 1874 dest_plats); 1875 } 1876 } 1877 for (; i < parms_count; i++) 1878 ret |= set_all_contains_variable (ipa_get_parm_lattices (callee_info, i)); 1879 1880 return ret; 1881} 1882 1883/* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS 1884 KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter 1885 three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */ 1886 1887static tree 1888ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, 1889 vec<tree> known_csts, 1890 vec<ipa_polymorphic_call_context> known_contexts, 1891 vec<ipa_agg_jump_function_p> known_aggs, 1892 struct ipa_agg_replacement_value *agg_reps, 1893 bool *speculative) 1894{ 1895 int param_index = ie->indirect_info->param_index; 1896 HOST_WIDE_INT anc_offset; 1897 tree t; 1898 tree target = NULL; 1899 1900 *speculative = false; 1901 1902 if (param_index == -1 1903 || known_csts.length () <= (unsigned int) param_index) 1904 return NULL_TREE; 1905 1906 if (!ie->indirect_info->polymorphic) 1907 { 1908 tree t; 1909 1910 if (ie->indirect_info->agg_contents) 1911 { 1912 if (agg_reps) 1913 { 1914 t = NULL; 1915 while (agg_reps) 1916 { 1917 if (agg_reps->index == param_index 1918 && agg_reps->offset == ie->indirect_info->offset 1919 && agg_reps->by_ref == ie->indirect_info->by_ref) 1920 { 1921 t = agg_reps->value; 1922 break; 1923 } 1924 agg_reps = agg_reps->next; 1925 } 1926 } 1927 else if (known_aggs.length () > (unsigned int) param_index) 1928 { 1929 struct ipa_agg_jump_function *agg; 1930 agg = known_aggs[param_index]; 1931 t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset, 1932 ie->indirect_info->by_ref); 1933 } 1934 else 1935 t = NULL; 1936 } 1937 else 1938 t = known_csts[param_index]; 1939 1940 if (t && 1941 TREE_CODE (t) == ADDR_EXPR 1942 && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL) 1943 return TREE_OPERAND (t, 0); 1944 else 1945 return NULL_TREE; 1946 } 1947 1948 if (!opt_for_fn (ie->caller->decl, flag_devirtualize)) 1949 return NULL_TREE; 1950 1951 gcc_assert (!ie->indirect_info->agg_contents); 1952 anc_offset = ie->indirect_info->offset; 1953 1954 t = NULL; 1955 1956 /* Try to work out value of virtual table pointer value in replacemnets. */ 1957 if (!t && agg_reps && !ie->indirect_info->by_ref) 1958 { 1959 while (agg_reps) 1960 { 1961 if (agg_reps->index == param_index 1962 && agg_reps->offset == ie->indirect_info->offset 1963 && agg_reps->by_ref) 1964 { 1965 t = agg_reps->value; 1966 break; 1967 } 1968 agg_reps = agg_reps->next; 1969 } 1970 } 1971 1972 /* Try to work out value of virtual table pointer value in known 1973 aggregate values. */ 1974 if (!t && known_aggs.length () > (unsigned int) param_index 1975 && !ie->indirect_info->by_ref) 1976 { 1977 struct ipa_agg_jump_function *agg; 1978 agg = known_aggs[param_index]; 1979 t = ipa_find_agg_cst_for_param (agg, ie->indirect_info->offset, 1980 true); 1981 } 1982 1983 /* If we found the virtual table pointer, lookup the target. */ 1984 if (t) 1985 { 1986 tree vtable; 1987 unsigned HOST_WIDE_INT offset; 1988 if (vtable_pointer_value_to_vtable (t, &vtable, &offset)) 1989 { 1990 target = gimple_get_virt_method_for_vtable (ie->indirect_info->otr_token, 1991 vtable, offset); 1992 if (target) 1993 { 1994 if ((TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE 1995 && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE) 1996 || !possible_polymorphic_call_target_p 1997 (ie, cgraph_node::get (target))) 1998 target = ipa_impossible_devirt_target (ie, target); 1999 *speculative = ie->indirect_info->vptr_changed; 2000 if (!*speculative) 2001 return target; 2002 } 2003 } 2004 } 2005 2006 /* Do we know the constant value of pointer? */ 2007 if (!t) 2008 t = known_csts[param_index]; 2009 2010 gcc_checking_assert (!t || TREE_CODE (t) != TREE_BINFO); 2011 2012 ipa_polymorphic_call_context context; 2013 if (known_contexts.length () > (unsigned int) param_index) 2014 { 2015 context = known_contexts[param_index]; 2016 context.offset_by (anc_offset); 2017 if (ie->indirect_info->vptr_changed) 2018 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor, 2019 ie->indirect_info->otr_type); 2020 if (t) 2021 { 2022 ipa_polymorphic_call_context ctx2 = ipa_polymorphic_call_context 2023 (t, ie->indirect_info->otr_type, anc_offset); 2024 if (!ctx2.useless_p ()) 2025 context.combine_with (ctx2, ie->indirect_info->otr_type); 2026 } 2027 } 2028 else if (t) 2029 { 2030 context = ipa_polymorphic_call_context (t, ie->indirect_info->otr_type, 2031 anc_offset); 2032 if (ie->indirect_info->vptr_changed) 2033 context.possible_dynamic_type_change (ie->in_polymorphic_cdtor, 2034 ie->indirect_info->otr_type); 2035 } 2036 else 2037 return NULL_TREE; 2038 2039 vec <cgraph_node *>targets; 2040 bool final; 2041 2042 targets = possible_polymorphic_call_targets 2043 (ie->indirect_info->otr_type, 2044 ie->indirect_info->otr_token, 2045 context, &final); 2046 if (!final || targets.length () > 1) 2047 { 2048 struct cgraph_node *node; 2049 if (*speculative) 2050 return target; 2051 if (!opt_for_fn (ie->caller->decl, flag_devirtualize_speculatively) 2052 || ie->speculative || !ie->maybe_hot_p ()) 2053 return NULL; 2054 node = try_speculative_devirtualization (ie->indirect_info->otr_type, 2055 ie->indirect_info->otr_token, 2056 context); 2057 if (node) 2058 { 2059 *speculative = true; 2060 target = node->decl; 2061 } 2062 else 2063 return NULL; 2064 } 2065 else 2066 { 2067 *speculative = false; 2068 if (targets.length () == 1) 2069 target = targets[0]->decl; 2070 else 2071 target = ipa_impossible_devirt_target (ie, NULL_TREE); 2072 } 2073 2074 if (target && !possible_polymorphic_call_target_p (ie, 2075 cgraph_node::get (target))) 2076 target = ipa_impossible_devirt_target (ie, target); 2077 2078 return target; 2079} 2080 2081 2082/* If an indirect edge IE can be turned into a direct one based on KNOWN_CSTS, 2083 KNOWN_CONTEXTS (which can be vNULL) or KNOWN_AGGS (which also can be vNULL) 2084 return the destination. */ 2085 2086tree 2087ipa_get_indirect_edge_target (struct cgraph_edge *ie, 2088 vec<tree> known_csts, 2089 vec<ipa_polymorphic_call_context> known_contexts, 2090 vec<ipa_agg_jump_function_p> known_aggs, 2091 bool *speculative) 2092{ 2093 return ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts, 2094 known_aggs, NULL, speculative); 2095} 2096 2097/* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS 2098 and KNOWN_CONTEXTS. */ 2099 2100static int 2101devirtualization_time_bonus (struct cgraph_node *node, 2102 vec<tree> known_csts, 2103 vec<ipa_polymorphic_call_context> known_contexts, 2104 vec<ipa_agg_jump_function_p> known_aggs) 2105{ 2106 struct cgraph_edge *ie; 2107 int res = 0; 2108 2109 for (ie = node->indirect_calls; ie; ie = ie->next_callee) 2110 { 2111 struct cgraph_node *callee; 2112 struct inline_summary *isummary; 2113 enum availability avail; 2114 tree target; 2115 bool speculative; 2116 2117 target = ipa_get_indirect_edge_target (ie, known_csts, known_contexts, 2118 known_aggs, &speculative); 2119 if (!target) 2120 continue; 2121 2122 /* Only bare minimum benefit for clearly un-inlineable targets. */ 2123 res += 1; 2124 callee = cgraph_node::get (target); 2125 if (!callee || !callee->definition) 2126 continue; 2127 callee = callee->function_symbol (&avail); 2128 if (avail < AVAIL_AVAILABLE) 2129 continue; 2130 isummary = inline_summaries->get (callee); 2131 if (!isummary->inlinable) 2132 continue; 2133 2134 /* FIXME: The values below need re-considering and perhaps also 2135 integrating into the cost metrics, at lest in some very basic way. */ 2136 if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4) 2137 res += 31 / ((int)speculative + 1); 2138 else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2) 2139 res += 15 / ((int)speculative + 1); 2140 else if (isummary->size <= MAX_INLINE_INSNS_AUTO 2141 || DECL_DECLARED_INLINE_P (callee->decl)) 2142 res += 7 / ((int)speculative + 1); 2143 } 2144 2145 return res; 2146} 2147 2148/* Return time bonus incurred because of HINTS. */ 2149 2150static int 2151hint_time_bonus (inline_hints hints) 2152{ 2153 int result = 0; 2154 if (hints & (INLINE_HINT_loop_iterations | INLINE_HINT_loop_stride)) 2155 result += PARAM_VALUE (PARAM_IPA_CP_LOOP_HINT_BONUS); 2156 if (hints & INLINE_HINT_array_index) 2157 result += PARAM_VALUE (PARAM_IPA_CP_ARRAY_INDEX_HINT_BONUS); 2158 return result; 2159} 2160 2161/* If there is a reason to penalize the function described by INFO in the 2162 cloning goodness evaluation, do so. */ 2163 2164static inline int64_t 2165incorporate_penalties (ipa_node_params *info, int64_t evaluation) 2166{ 2167 if (info->node_within_scc) 2168 evaluation = (evaluation 2169 * (100 - PARAM_VALUE (PARAM_IPA_CP_RECURSION_PENALTY))) / 100; 2170 2171 if (info->node_calling_single_call) 2172 evaluation = (evaluation 2173 * (100 - PARAM_VALUE (PARAM_IPA_CP_SINGLE_CALL_PENALTY))) 2174 / 100; 2175 2176 return evaluation; 2177} 2178 2179/* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT 2180 and SIZE_COST and with the sum of frequencies of incoming edges to the 2181 potential new clone in FREQUENCIES. */ 2182 2183static bool 2184good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit, 2185 int freq_sum, gcov_type count_sum, int size_cost) 2186{ 2187 if (time_benefit == 0 2188 || !opt_for_fn (node->decl, flag_ipa_cp_clone) 2189 || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl))) 2190 return false; 2191 2192 gcc_assert (size_cost > 0); 2193 2194 struct ipa_node_params *info = IPA_NODE_REF (node); 2195 if (max_count) 2196 { 2197 int factor = (count_sum * 1000) / max_count; 2198 int64_t evaluation = (((int64_t) time_benefit * factor) 2199 / size_cost); 2200 evaluation = incorporate_penalties (info, evaluation); 2201 2202 if (dump_file && (dump_flags & TDF_DETAILS)) 2203 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, " 2204 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC 2205 "%s%s) -> evaluation: " "%"PRId64 2206 ", threshold: %i\n", 2207 time_benefit, size_cost, (HOST_WIDE_INT) count_sum, 2208 info->node_within_scc ? ", scc" : "", 2209 info->node_calling_single_call ? ", single_call" : "", 2210 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD)); 2211 2212 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD); 2213 } 2214 else 2215 { 2216 int64_t evaluation = (((int64_t) time_benefit * freq_sum) 2217 / size_cost); 2218 evaluation = incorporate_penalties (info, evaluation); 2219 2220 if (dump_file && (dump_flags & TDF_DETAILS)) 2221 fprintf (dump_file, " good_cloning_opportunity_p (time: %i, " 2222 "size: %i, freq_sum: %i%s%s) -> evaluation: " 2223 "%"PRId64 ", threshold: %i\n", 2224 time_benefit, size_cost, freq_sum, 2225 info->node_within_scc ? ", scc" : "", 2226 info->node_calling_single_call ? ", single_call" : "", 2227 evaluation, PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD)); 2228 2229 return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD); 2230 } 2231} 2232 2233/* Return all context independent values from aggregate lattices in PLATS in a 2234 vector. Return NULL if there are none. */ 2235 2236static vec<ipa_agg_jf_item, va_gc> * 2237context_independent_aggregate_values (struct ipcp_param_lattices *plats) 2238{ 2239 vec<ipa_agg_jf_item, va_gc> *res = NULL; 2240 2241 if (plats->aggs_bottom 2242 || plats->aggs_contain_variable 2243 || plats->aggs_count == 0) 2244 return NULL; 2245 2246 for (struct ipcp_agg_lattice *aglat = plats->aggs; 2247 aglat; 2248 aglat = aglat->next) 2249 if (aglat->is_single_const ()) 2250 { 2251 struct ipa_agg_jf_item item; 2252 item.offset = aglat->offset; 2253 item.value = aglat->values->value; 2254 vec_safe_push (res, item); 2255 } 2256 return res; 2257} 2258 2259/* Allocate KNOWN_CSTS, KNOWN_CONTEXTS and, if non-NULL, KNOWN_AGGS and 2260 populate them with values of parameters that are known independent of the 2261 context. INFO describes the function. If REMOVABLE_PARAMS_COST is 2262 non-NULL, the movement cost of all removable parameters will be stored in 2263 it. */ 2264 2265static bool 2266gather_context_independent_values (struct ipa_node_params *info, 2267 vec<tree> *known_csts, 2268 vec<ipa_polymorphic_call_context> 2269 *known_contexts, 2270 vec<ipa_agg_jump_function> *known_aggs, 2271 int *removable_params_cost) 2272{ 2273 int i, count = ipa_get_param_count (info); 2274 bool ret = false; 2275 2276 known_csts->create (0); 2277 known_contexts->create (0); 2278 known_csts->safe_grow_cleared (count); 2279 known_contexts->safe_grow_cleared (count); 2280 if (known_aggs) 2281 { 2282 known_aggs->create (0); 2283 known_aggs->safe_grow_cleared (count); 2284 } 2285 2286 if (removable_params_cost) 2287 *removable_params_cost = 0; 2288 2289 for (i = 0; i < count ; i++) 2290 { 2291 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); 2292 ipcp_lattice<tree> *lat = &plats->itself; 2293 2294 if (lat->is_single_const ()) 2295 { 2296 ipcp_value<tree> *val = lat->values; 2297 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO); 2298 (*known_csts)[i] = val->value; 2299 if (removable_params_cost) 2300 *removable_params_cost 2301 += estimate_move_cost (TREE_TYPE (val->value), false); 2302 ret = true; 2303 } 2304 else if (removable_params_cost 2305 && !ipa_is_param_used (info, i)) 2306 *removable_params_cost 2307 += ipa_get_param_move_cost (info, i); 2308 2309 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat; 2310 if (ctxlat->is_single_const ()) 2311 { 2312 (*known_contexts)[i] = ctxlat->values->value; 2313 ret = true; 2314 } 2315 2316 if (known_aggs) 2317 { 2318 vec<ipa_agg_jf_item, va_gc> *agg_items; 2319 struct ipa_agg_jump_function *ajf; 2320 2321 agg_items = context_independent_aggregate_values (plats); 2322 ajf = &(*known_aggs)[i]; 2323 ajf->items = agg_items; 2324 ajf->by_ref = plats->aggs_by_ref; 2325 ret |= agg_items != NULL; 2326 } 2327 } 2328 2329 return ret; 2330} 2331 2332/* The current interface in ipa-inline-analysis requires a pointer vector. 2333 Create it. 2334 2335 FIXME: That interface should be re-worked, this is slightly silly. Still, 2336 I'd like to discuss how to change it first and this demonstrates the 2337 issue. */ 2338 2339static vec<ipa_agg_jump_function_p> 2340agg_jmp_p_vec_for_t_vec (vec<ipa_agg_jump_function> known_aggs) 2341{ 2342 vec<ipa_agg_jump_function_p> ret; 2343 struct ipa_agg_jump_function *ajf; 2344 int i; 2345 2346 ret.create (known_aggs.length ()); 2347 FOR_EACH_VEC_ELT (known_aggs, i, ajf) 2348 ret.quick_push (ajf); 2349 return ret; 2350} 2351 2352/* Perform time and size measurement of NODE with the context given in 2353 KNOWN_CSTS, KNOWN_CONTEXTS and KNOWN_AGGS, calculate the benefit and cost 2354 given BASE_TIME of the node without specialization, REMOVABLE_PARAMS_COST of 2355 all context-independent removable parameters and EST_MOVE_COST of estimated 2356 movement of the considered parameter and store it into VAL. */ 2357 2358static void 2359perform_estimation_of_a_value (cgraph_node *node, vec<tree> known_csts, 2360 vec<ipa_polymorphic_call_context> known_contexts, 2361 vec<ipa_agg_jump_function_p> known_aggs_ptrs, 2362 int base_time, int removable_params_cost, 2363 int est_move_cost, ipcp_value_base *val) 2364{ 2365 int time, size, time_benefit; 2366 inline_hints hints; 2367 2368 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts, 2369 known_aggs_ptrs, &size, &time, 2370 &hints); 2371 time_benefit = base_time - time 2372 + devirtualization_time_bonus (node, known_csts, known_contexts, 2373 known_aggs_ptrs) 2374 + hint_time_bonus (hints) 2375 + removable_params_cost + est_move_cost; 2376 2377 gcc_checking_assert (size >=0); 2378 /* The inliner-heuristics based estimates may think that in certain 2379 contexts some functions do not have any size at all but we want 2380 all specializations to have at least a tiny cost, not least not to 2381 divide by zero. */ 2382 if (size == 0) 2383 size = 1; 2384 2385 val->local_time_benefit = time_benefit; 2386 val->local_size_cost = size; 2387} 2388 2389/* Iterate over known values of parameters of NODE and estimate the local 2390 effects in terms of time and size they have. */ 2391 2392static void 2393estimate_local_effects (struct cgraph_node *node) 2394{ 2395 struct ipa_node_params *info = IPA_NODE_REF (node); 2396 int i, count = ipa_get_param_count (info); 2397 vec<tree> known_csts; 2398 vec<ipa_polymorphic_call_context> known_contexts; 2399 vec<ipa_agg_jump_function> known_aggs; 2400 vec<ipa_agg_jump_function_p> known_aggs_ptrs; 2401 bool always_const; 2402 int base_time = inline_summaries->get (node)->time; 2403 int removable_params_cost; 2404 2405 if (!count || !ipcp_versionable_function_p (node)) 2406 return; 2407 2408 if (dump_file && (dump_flags & TDF_DETAILS)) 2409 fprintf (dump_file, "\nEstimating effects for %s/%i, base_time: %i.\n", 2410 node->name (), node->order, base_time); 2411 2412 always_const = gather_context_independent_values (info, &known_csts, 2413 &known_contexts, &known_aggs, 2414 &removable_params_cost); 2415 known_aggs_ptrs = agg_jmp_p_vec_for_t_vec (known_aggs); 2416 if (always_const) 2417 { 2418 struct caller_statistics stats; 2419 inline_hints hints; 2420 int time, size; 2421 2422 init_caller_stats (&stats); 2423 node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, 2424 false); 2425 estimate_ipcp_clone_size_and_time (node, known_csts, known_contexts, 2426 known_aggs_ptrs, &size, &time, &hints); 2427 time -= devirtualization_time_bonus (node, known_csts, known_contexts, 2428 known_aggs_ptrs); 2429 time -= hint_time_bonus (hints); 2430 time -= removable_params_cost; 2431 size -= stats.n_calls * removable_params_cost; 2432 2433 if (dump_file) 2434 fprintf (dump_file, " - context independent values, size: %i, " 2435 "time_benefit: %i\n", size, base_time - time); 2436 2437 if (size <= 0 2438 || node->will_be_removed_from_program_if_no_direct_calls_p ()) 2439 { 2440 info->do_clone_for_all_contexts = true; 2441 base_time = time; 2442 2443 if (dump_file) 2444 fprintf (dump_file, " Decided to specialize for all " 2445 "known contexts, code not going to grow.\n"); 2446 } 2447 else if (good_cloning_opportunity_p (node, base_time - time, 2448 stats.freq_sum, stats.count_sum, 2449 size)) 2450 { 2451 if (size + overall_size <= max_new_size) 2452 { 2453 info->do_clone_for_all_contexts = true; 2454 base_time = time; 2455 overall_size += size; 2456 2457 if (dump_file) 2458 fprintf (dump_file, " Decided to specialize for all " 2459 "known contexts, growth deemed beneficial.\n"); 2460 } 2461 else if (dump_file && (dump_flags & TDF_DETAILS)) 2462 fprintf (dump_file, " Not cloning for all contexts because " 2463 "max_new_size would be reached with %li.\n", 2464 size + overall_size); 2465 } 2466 } 2467 2468 for (i = 0; i < count ; i++) 2469 { 2470 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); 2471 ipcp_lattice<tree> *lat = &plats->itself; 2472 ipcp_value<tree> *val; 2473 2474 if (lat->bottom 2475 || !lat->values 2476 || known_csts[i]) 2477 continue; 2478 2479 for (val = lat->values; val; val = val->next) 2480 { 2481 gcc_checking_assert (TREE_CODE (val->value) != TREE_BINFO); 2482 known_csts[i] = val->value; 2483 2484 int emc = estimate_move_cost (TREE_TYPE (val->value), true); 2485 perform_estimation_of_a_value (node, known_csts, known_contexts, 2486 known_aggs_ptrs, base_time, 2487 removable_params_cost, emc, val); 2488 2489 if (dump_file && (dump_flags & TDF_DETAILS)) 2490 { 2491 fprintf (dump_file, " - estimates for value "); 2492 print_ipcp_constant_value (dump_file, val->value); 2493 fprintf (dump_file, " for "); 2494 ipa_dump_param (dump_file, info, i); 2495 fprintf (dump_file, ": time_benefit: %i, size: %i\n", 2496 val->local_time_benefit, val->local_size_cost); 2497 } 2498 } 2499 known_csts[i] = NULL_TREE; 2500 } 2501 2502 for (i = 0; i < count; i++) 2503 { 2504 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); 2505 2506 if (!plats->virt_call) 2507 continue; 2508 2509 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat; 2510 ipcp_value<ipa_polymorphic_call_context> *val; 2511 2512 if (ctxlat->bottom 2513 || !ctxlat->values 2514 || !known_contexts[i].useless_p ()) 2515 continue; 2516 2517 for (val = ctxlat->values; val; val = val->next) 2518 { 2519 known_contexts[i] = val->value; 2520 perform_estimation_of_a_value (node, known_csts, known_contexts, 2521 known_aggs_ptrs, base_time, 2522 removable_params_cost, 0, val); 2523 2524 if (dump_file && (dump_flags & TDF_DETAILS)) 2525 { 2526 fprintf (dump_file, " - estimates for polymorphic context "); 2527 print_ipcp_constant_value (dump_file, val->value); 2528 fprintf (dump_file, " for "); 2529 ipa_dump_param (dump_file, info, i); 2530 fprintf (dump_file, ": time_benefit: %i, size: %i\n", 2531 val->local_time_benefit, val->local_size_cost); 2532 } 2533 } 2534 known_contexts[i] = ipa_polymorphic_call_context (); 2535 } 2536 2537 for (i = 0; i < count ; i++) 2538 { 2539 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); 2540 struct ipa_agg_jump_function *ajf; 2541 struct ipcp_agg_lattice *aglat; 2542 2543 if (plats->aggs_bottom || !plats->aggs) 2544 continue; 2545 2546 ajf = &known_aggs[i]; 2547 for (aglat = plats->aggs; aglat; aglat = aglat->next) 2548 { 2549 ipcp_value<tree> *val; 2550 if (aglat->bottom || !aglat->values 2551 /* If the following is true, the one value is in known_aggs. */ 2552 || (!plats->aggs_contain_variable 2553 && aglat->is_single_const ())) 2554 continue; 2555 2556 for (val = aglat->values; val; val = val->next) 2557 { 2558 struct ipa_agg_jf_item item; 2559 2560 item.offset = aglat->offset; 2561 item.value = val->value; 2562 vec_safe_push (ajf->items, item); 2563 2564 perform_estimation_of_a_value (node, known_csts, known_contexts, 2565 known_aggs_ptrs, base_time, 2566 removable_params_cost, 0, val); 2567 2568 if (dump_file && (dump_flags & TDF_DETAILS)) 2569 { 2570 fprintf (dump_file, " - estimates for value "); 2571 print_ipcp_constant_value (dump_file, val->value); 2572 fprintf (dump_file, " for "); 2573 ipa_dump_param (dump_file, info, i); 2574 fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC 2575 "]: time_benefit: %i, size: %i\n", 2576 plats->aggs_by_ref ? "ref " : "", 2577 aglat->offset, 2578 val->local_time_benefit, val->local_size_cost); 2579 } 2580 2581 ajf->items->pop (); 2582 } 2583 } 2584 } 2585 2586 for (i = 0; i < count ; i++) 2587 vec_free (known_aggs[i].items); 2588 2589 known_csts.release (); 2590 known_contexts.release (); 2591 known_aggs.release (); 2592 known_aggs_ptrs.release (); 2593} 2594 2595 2596/* Add value CUR_VAL and all yet-unsorted values it is dependent on to the 2597 topological sort of values. */ 2598 2599template <typename valtype> 2600void 2601value_topo_info<valtype>::add_val (ipcp_value<valtype> *cur_val) 2602{ 2603 ipcp_value_source<valtype> *src; 2604 2605 if (cur_val->dfs) 2606 return; 2607 2608 dfs_counter++; 2609 cur_val->dfs = dfs_counter; 2610 cur_val->low_link = dfs_counter; 2611 2612 cur_val->topo_next = stack; 2613 stack = cur_val; 2614 cur_val->on_stack = true; 2615 2616 for (src = cur_val->sources; src; src = src->next) 2617 if (src->val) 2618 { 2619 if (src->val->dfs == 0) 2620 { 2621 add_val (src->val); 2622 if (src->val->low_link < cur_val->low_link) 2623 cur_val->low_link = src->val->low_link; 2624 } 2625 else if (src->val->on_stack 2626 && src->val->dfs < cur_val->low_link) 2627 cur_val->low_link = src->val->dfs; 2628 } 2629 2630 if (cur_val->dfs == cur_val->low_link) 2631 { 2632 ipcp_value<valtype> *v, *scc_list = NULL; 2633 2634 do 2635 { 2636 v = stack; 2637 stack = v->topo_next; 2638 v->on_stack = false; 2639 2640 v->scc_next = scc_list; 2641 scc_list = v; 2642 } 2643 while (v != cur_val); 2644 2645 cur_val->topo_next = values_topo; 2646 values_topo = cur_val; 2647 } 2648} 2649 2650/* Add all values in lattices associated with NODE to the topological sort if 2651 they are not there yet. */ 2652 2653static void 2654add_all_node_vals_to_toposort (cgraph_node *node, ipa_topo_info *topo) 2655{ 2656 struct ipa_node_params *info = IPA_NODE_REF (node); 2657 int i, count = ipa_get_param_count (info); 2658 2659 for (i = 0; i < count ; i++) 2660 { 2661 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); 2662 ipcp_lattice<tree> *lat = &plats->itself; 2663 struct ipcp_agg_lattice *aglat; 2664 2665 if (!lat->bottom) 2666 { 2667 ipcp_value<tree> *val; 2668 for (val = lat->values; val; val = val->next) 2669 topo->constants.add_val (val); 2670 } 2671 2672 if (!plats->aggs_bottom) 2673 for (aglat = plats->aggs; aglat; aglat = aglat->next) 2674 if (!aglat->bottom) 2675 { 2676 ipcp_value<tree> *val; 2677 for (val = aglat->values; val; val = val->next) 2678 topo->constants.add_val (val); 2679 } 2680 2681 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat; 2682 if (!ctxlat->bottom) 2683 { 2684 ipcp_value<ipa_polymorphic_call_context> *ctxval; 2685 for (ctxval = ctxlat->values; ctxval; ctxval = ctxval->next) 2686 topo->contexts.add_val (ctxval); 2687 } 2688 } 2689} 2690 2691/* One pass of constants propagation along the call graph edges, from callers 2692 to callees (requires topological ordering in TOPO), iterate over strongly 2693 connected components. */ 2694 2695static void 2696propagate_constants_topo (struct ipa_topo_info *topo) 2697{ 2698 int i; 2699 2700 for (i = topo->nnodes - 1; i >= 0; i--) 2701 { 2702 unsigned j; 2703 struct cgraph_node *v, *node = topo->order[i]; 2704 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node); 2705 2706 /* First, iteratively propagate within the strongly connected component 2707 until all lattices stabilize. */ 2708 FOR_EACH_VEC_ELT (cycle_nodes, j, v) 2709 if (v->has_gimple_body_p ()) 2710 push_node_to_stack (topo, v); 2711 2712 v = pop_node_from_stack (topo); 2713 while (v) 2714 { 2715 struct cgraph_edge *cs; 2716 2717 for (cs = v->callees; cs; cs = cs->next_callee) 2718 if (ipa_edge_within_scc (cs)) 2719 { 2720 IPA_NODE_REF (v)->node_within_scc = true; 2721 if (propagate_constants_accross_call (cs)) 2722 push_node_to_stack (topo, cs->callee->function_symbol ()); 2723 } 2724 v = pop_node_from_stack (topo); 2725 } 2726 2727 /* Afterwards, propagate along edges leading out of the SCC, calculates 2728 the local effects of the discovered constants and all valid values to 2729 their topological sort. */ 2730 FOR_EACH_VEC_ELT (cycle_nodes, j, v) 2731 if (v->has_gimple_body_p ()) 2732 { 2733 struct cgraph_edge *cs; 2734 2735 estimate_local_effects (v); 2736 add_all_node_vals_to_toposort (v, topo); 2737 for (cs = v->callees; cs; cs = cs->next_callee) 2738 if (!ipa_edge_within_scc (cs)) 2739 propagate_constants_accross_call (cs); 2740 } 2741 cycle_nodes.release (); 2742 } 2743} 2744 2745 2746/* Return the sum of A and B if none of them is bigger than INT_MAX/2, return 2747 the bigger one if otherwise. */ 2748 2749static int 2750safe_add (int a, int b) 2751{ 2752 if (a > INT_MAX/2 || b > INT_MAX/2) 2753 return a > b ? a : b; 2754 else 2755 return a + b; 2756} 2757 2758 2759/* Propagate the estimated effects of individual values along the topological 2760 from the dependent values to those they depend on. */ 2761 2762template <typename valtype> 2763void 2764value_topo_info<valtype>::propagate_effects () 2765{ 2766 ipcp_value<valtype> *base; 2767 2768 for (base = values_topo; base; base = base->topo_next) 2769 { 2770 ipcp_value_source<valtype> *src; 2771 ipcp_value<valtype> *val; 2772 int time = 0, size = 0; 2773 2774 for (val = base; val; val = val->scc_next) 2775 { 2776 time = safe_add (time, 2777 val->local_time_benefit + val->prop_time_benefit); 2778 size = safe_add (size, val->local_size_cost + val->prop_size_cost); 2779 } 2780 2781 for (val = base; val; val = val->scc_next) 2782 for (src = val->sources; src; src = src->next) 2783 if (src->val 2784 && src->cs->maybe_hot_p ()) 2785 { 2786 src->val->prop_time_benefit = safe_add (time, 2787 src->val->prop_time_benefit); 2788 src->val->prop_size_cost = safe_add (size, 2789 src->val->prop_size_cost); 2790 } 2791 } 2792} 2793 2794 2795/* Propagate constants, polymorphic contexts and their effects from the 2796 summaries interprocedurally. */ 2797 2798static void 2799ipcp_propagate_stage (struct ipa_topo_info *topo) 2800{ 2801 struct cgraph_node *node; 2802 2803 if (dump_file) 2804 fprintf (dump_file, "\n Propagating constants:\n\n"); 2805 2806 if (in_lto_p) 2807 ipa_update_after_lto_read (); 2808 2809 2810 FOR_EACH_DEFINED_FUNCTION (node) 2811 { 2812 struct ipa_node_params *info = IPA_NODE_REF (node); 2813 2814 determine_versionability (node); 2815 if (node->has_gimple_body_p ()) 2816 { 2817 info->lattices = XCNEWVEC (struct ipcp_param_lattices, 2818 ipa_get_param_count (info)); 2819 initialize_node_lattices (node); 2820 } 2821 if (node->definition && !node->alias) 2822 overall_size += inline_summaries->get (node)->self_size; 2823 if (node->count > max_count) 2824 max_count = node->count; 2825 } 2826 2827 max_new_size = overall_size; 2828 if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS)) 2829 max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS); 2830 max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1; 2831 2832 if (dump_file) 2833 fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n", 2834 overall_size, max_new_size); 2835 2836 propagate_constants_topo (topo); 2837#ifdef ENABLE_CHECKING 2838 ipcp_verify_propagated_values (); 2839#endif 2840 topo->constants.propagate_effects (); 2841 topo->contexts.propagate_effects (); 2842 2843 if (dump_file) 2844 { 2845 fprintf (dump_file, "\nIPA lattices after all propagation:\n"); 2846 print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true); 2847 } 2848} 2849 2850/* Discover newly direct outgoing edges from NODE which is a new clone with 2851 known KNOWN_CSTS and make them direct. */ 2852 2853static void 2854ipcp_discover_new_direct_edges (struct cgraph_node *node, 2855 vec<tree> known_csts, 2856 vec<ipa_polymorphic_call_context> 2857 known_contexts, 2858 struct ipa_agg_replacement_value *aggvals) 2859{ 2860 struct cgraph_edge *ie, *next_ie; 2861 bool found = false; 2862 2863 for (ie = node->indirect_calls; ie; ie = next_ie) 2864 { 2865 tree target; 2866 bool speculative; 2867 2868 next_ie = ie->next_callee; 2869 target = ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts, 2870 vNULL, aggvals, &speculative); 2871 if (target) 2872 { 2873 bool agg_contents = ie->indirect_info->agg_contents; 2874 bool polymorphic = ie->indirect_info->polymorphic; 2875 int param_index = ie->indirect_info->param_index; 2876 struct cgraph_edge *cs = ipa_make_edge_direct_to_target (ie, target, 2877 speculative); 2878 found = true; 2879 2880 if (cs && !agg_contents && !polymorphic) 2881 { 2882 struct ipa_node_params *info = IPA_NODE_REF (node); 2883 int c = ipa_get_controlled_uses (info, param_index); 2884 if (c != IPA_UNDESCRIBED_USE) 2885 { 2886 struct ipa_ref *to_del; 2887 2888 c--; 2889 ipa_set_controlled_uses (info, param_index, c); 2890 if (dump_file && (dump_flags & TDF_DETAILS)) 2891 fprintf (dump_file, " controlled uses count of param " 2892 "%i bumped down to %i\n", param_index, c); 2893 if (c == 0 2894 && (to_del = node->find_reference (cs->callee, NULL, 0))) 2895 { 2896 if (dump_file && (dump_flags & TDF_DETAILS)) 2897 fprintf (dump_file, " and even removing its " 2898 "cloning-created reference\n"); 2899 to_del->remove_reference (); 2900 } 2901 } 2902 } 2903 } 2904 } 2905 /* Turning calls to direct calls will improve overall summary. */ 2906 if (found) 2907 inline_update_overall_summary (node); 2908} 2909 2910/* Vector of pointers which for linked lists of clones of an original crgaph 2911 edge. */ 2912 2913static vec<cgraph_edge *> next_edge_clone; 2914static vec<cgraph_edge *> prev_edge_clone; 2915 2916static inline void 2917grow_edge_clone_vectors (void) 2918{ 2919 if (next_edge_clone.length () 2920 <= (unsigned) symtab->edges_max_uid) 2921 next_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1); 2922 if (prev_edge_clone.length () 2923 <= (unsigned) symtab->edges_max_uid) 2924 prev_edge_clone.safe_grow_cleared (symtab->edges_max_uid + 1); 2925} 2926 2927/* Edge duplication hook to grow the appropriate linked list in 2928 next_edge_clone. */ 2929 2930static void 2931ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst, 2932 void *) 2933{ 2934 grow_edge_clone_vectors (); 2935 2936 struct cgraph_edge *old_next = next_edge_clone[src->uid]; 2937 if (old_next) 2938 prev_edge_clone[old_next->uid] = dst; 2939 prev_edge_clone[dst->uid] = src; 2940 2941 next_edge_clone[dst->uid] = old_next; 2942 next_edge_clone[src->uid] = dst; 2943} 2944 2945/* Hook that is called by cgraph.c when an edge is removed. */ 2946 2947static void 2948ipcp_edge_removal_hook (struct cgraph_edge *cs, void *) 2949{ 2950 grow_edge_clone_vectors (); 2951 2952 struct cgraph_edge *prev = prev_edge_clone[cs->uid]; 2953 struct cgraph_edge *next = next_edge_clone[cs->uid]; 2954 if (prev) 2955 next_edge_clone[prev->uid] = next; 2956 if (next) 2957 prev_edge_clone[next->uid] = prev; 2958} 2959 2960/* See if NODE is a clone with a known aggregate value at a given OFFSET of a 2961 parameter with the given INDEX. */ 2962 2963static tree 2964get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset, 2965 int index) 2966{ 2967 struct ipa_agg_replacement_value *aggval; 2968 2969 aggval = ipa_get_agg_replacements_for_node (node); 2970 while (aggval) 2971 { 2972 if (aggval->offset == offset 2973 && aggval->index == index) 2974 return aggval->value; 2975 aggval = aggval->next; 2976 } 2977 return NULL_TREE; 2978} 2979 2980/* Return true is NODE is DEST or its clone for all contexts. */ 2981 2982static bool 2983same_node_or_its_all_contexts_clone_p (cgraph_node *node, cgraph_node *dest) 2984{ 2985 if (node == dest) 2986 return true; 2987 2988 struct ipa_node_params *info = IPA_NODE_REF (node); 2989 return info->is_all_contexts_clone && info->ipcp_orig_node == dest; 2990} 2991 2992/* Return true if edge CS does bring about the value described by SRC to node 2993 DEST or its clone for all contexts. */ 2994 2995static bool 2996cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source<tree> *src, 2997 cgraph_node *dest) 2998{ 2999 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); 3000 enum availability availability; 3001 cgraph_node *real_dest = cs->callee->function_symbol (&availability); 3002 3003 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest) 3004 || availability <= AVAIL_INTERPOSABLE 3005 || caller_info->node_dead) 3006 return false; 3007 if (!src->val) 3008 return true; 3009 3010 if (caller_info->ipcp_orig_node) 3011 { 3012 tree t; 3013 if (src->offset == -1) 3014 t = caller_info->known_csts[src->index]; 3015 else 3016 t = get_clone_agg_value (cs->caller, src->offset, src->index); 3017 return (t != NULL_TREE 3018 && values_equal_for_ipcp_p (src->val->value, t)); 3019 } 3020 else 3021 { 3022 struct ipcp_agg_lattice *aglat; 3023 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info, 3024 src->index); 3025 if (src->offset == -1) 3026 return (plats->itself.is_single_const () 3027 && values_equal_for_ipcp_p (src->val->value, 3028 plats->itself.values->value)); 3029 else 3030 { 3031 if (plats->aggs_bottom || plats->aggs_contain_variable) 3032 return false; 3033 for (aglat = plats->aggs; aglat; aglat = aglat->next) 3034 if (aglat->offset == src->offset) 3035 return (aglat->is_single_const () 3036 && values_equal_for_ipcp_p (src->val->value, 3037 aglat->values->value)); 3038 } 3039 return false; 3040 } 3041} 3042 3043/* Return true if edge CS does bring about the value described by SRC to node 3044 DEST or its clone for all contexts. */ 3045 3046static bool 3047cgraph_edge_brings_value_p (cgraph_edge *cs, 3048 ipcp_value_source<ipa_polymorphic_call_context> *src, 3049 cgraph_node *dest) 3050{ 3051 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); 3052 cgraph_node *real_dest = cs->callee->function_symbol (); 3053 3054 if (!same_node_or_its_all_contexts_clone_p (real_dest, dest) 3055 || caller_info->node_dead) 3056 return false; 3057 if (!src->val) 3058 return true; 3059 3060 if (caller_info->ipcp_orig_node) 3061 return (caller_info->known_contexts.length () > (unsigned) src->index) 3062 && values_equal_for_ipcp_p (src->val->value, 3063 caller_info->known_contexts[src->index]); 3064 3065 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (caller_info, 3066 src->index); 3067 return plats->ctxlat.is_single_const () 3068 && values_equal_for_ipcp_p (src->val->value, 3069 plats->ctxlat.values->value); 3070} 3071 3072/* Get the next clone in the linked list of clones of an edge. */ 3073 3074static inline struct cgraph_edge * 3075get_next_cgraph_edge_clone (struct cgraph_edge *cs) 3076{ 3077 return next_edge_clone[cs->uid]; 3078} 3079 3080/* Given VAL that is intended for DEST, iterate over all its sources and if 3081 they still hold, add their edge frequency and their number into *FREQUENCY 3082 and *CALLER_COUNT respectively. */ 3083 3084template <typename valtype> 3085static bool 3086get_info_about_necessary_edges (ipcp_value<valtype> *val, cgraph_node *dest, 3087 int *freq_sum, 3088 gcov_type *count_sum, int *caller_count) 3089{ 3090 ipcp_value_source<valtype> *src; 3091 int freq = 0, count = 0; 3092 gcov_type cnt = 0; 3093 bool hot = false; 3094 3095 for (src = val->sources; src; src = src->next) 3096 { 3097 struct cgraph_edge *cs = src->cs; 3098 while (cs) 3099 { 3100 if (cgraph_edge_brings_value_p (cs, src, dest)) 3101 { 3102 count++; 3103 freq += cs->frequency; 3104 cnt += cs->count; 3105 hot |= cs->maybe_hot_p (); 3106 } 3107 cs = get_next_cgraph_edge_clone (cs); 3108 } 3109 } 3110 3111 *freq_sum = freq; 3112 *count_sum = cnt; 3113 *caller_count = count; 3114 return hot; 3115} 3116 3117/* Return a vector of incoming edges that do bring value VAL to node DEST. It 3118 is assumed their number is known and equal to CALLER_COUNT. */ 3119 3120template <typename valtype> 3121static vec<cgraph_edge *> 3122gather_edges_for_value (ipcp_value<valtype> *val, cgraph_node *dest, 3123 int caller_count) 3124{ 3125 ipcp_value_source<valtype> *src; 3126 vec<cgraph_edge *> ret; 3127 3128 ret.create (caller_count); 3129 for (src = val->sources; src; src = src->next) 3130 { 3131 struct cgraph_edge *cs = src->cs; 3132 while (cs) 3133 { 3134 if (cgraph_edge_brings_value_p (cs, src, dest)) 3135 ret.quick_push (cs); 3136 cs = get_next_cgraph_edge_clone (cs); 3137 } 3138 } 3139 3140 return ret; 3141} 3142 3143/* Construct a replacement map for a know VALUE for a formal parameter PARAM. 3144 Return it or NULL if for some reason it cannot be created. */ 3145 3146static struct ipa_replace_map * 3147get_replacement_map (struct ipa_node_params *info, tree value, int parm_num) 3148{ 3149 struct ipa_replace_map *replace_map; 3150 3151 3152 replace_map = ggc_alloc<ipa_replace_map> (); 3153 if (dump_file) 3154 { 3155 fprintf (dump_file, " replacing "); 3156 ipa_dump_param (dump_file, info, parm_num); 3157 3158 fprintf (dump_file, " with const "); 3159 print_generic_expr (dump_file, value, 0); 3160 fprintf (dump_file, "\n"); 3161 } 3162 replace_map->old_tree = NULL; 3163 replace_map->parm_num = parm_num; 3164 replace_map->new_tree = value; 3165 replace_map->replace_p = true; 3166 replace_map->ref_p = false; 3167 3168 return replace_map; 3169} 3170 3171/* Dump new profiling counts */ 3172 3173static void 3174dump_profile_updates (struct cgraph_node *orig_node, 3175 struct cgraph_node *new_node) 3176{ 3177 struct cgraph_edge *cs; 3178 3179 fprintf (dump_file, " setting count of the specialized node to " 3180 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) new_node->count); 3181 for (cs = new_node->callees; cs ; cs = cs->next_callee) 3182 fprintf (dump_file, " edge to %s has count " 3183 HOST_WIDE_INT_PRINT_DEC "\n", 3184 cs->callee->name (), (HOST_WIDE_INT) cs->count); 3185 3186 fprintf (dump_file, " setting count of the original node to " 3187 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) orig_node->count); 3188 for (cs = orig_node->callees; cs ; cs = cs->next_callee) 3189 fprintf (dump_file, " edge to %s is left with " 3190 HOST_WIDE_INT_PRINT_DEC "\n", 3191 cs->callee->name (), (HOST_WIDE_INT) cs->count); 3192} 3193 3194/* After a specialized NEW_NODE version of ORIG_NODE has been created, update 3195 their profile information to reflect this. */ 3196 3197static void 3198update_profiling_info (struct cgraph_node *orig_node, 3199 struct cgraph_node *new_node) 3200{ 3201 struct cgraph_edge *cs; 3202 struct caller_statistics stats; 3203 gcov_type new_sum, orig_sum; 3204 gcov_type remainder, orig_node_count = orig_node->count; 3205 3206 if (orig_node_count == 0) 3207 return; 3208 3209 init_caller_stats (&stats); 3210 orig_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, 3211 false); 3212 orig_sum = stats.count_sum; 3213 init_caller_stats (&stats); 3214 new_node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, 3215 false); 3216 new_sum = stats.count_sum; 3217 3218 if (orig_node_count < orig_sum + new_sum) 3219 { 3220 if (dump_file) 3221 fprintf (dump_file, " Problem: node %s/%i has too low count " 3222 HOST_WIDE_INT_PRINT_DEC " while the sum of incoming " 3223 "counts is " HOST_WIDE_INT_PRINT_DEC "\n", 3224 orig_node->name (), orig_node->order, 3225 (HOST_WIDE_INT) orig_node_count, 3226 (HOST_WIDE_INT) (orig_sum + new_sum)); 3227 3228 orig_node_count = (orig_sum + new_sum) * 12 / 10; 3229 if (dump_file) 3230 fprintf (dump_file, " proceeding by pretending it was " 3231 HOST_WIDE_INT_PRINT_DEC "\n", 3232 (HOST_WIDE_INT) orig_node_count); 3233 } 3234 3235 new_node->count = new_sum; 3236 remainder = orig_node_count - new_sum; 3237 orig_node->count = remainder; 3238 3239 for (cs = new_node->callees; cs ; cs = cs->next_callee) 3240 if (cs->frequency) 3241 cs->count = apply_probability (cs->count, 3242 GCOV_COMPUTE_SCALE (new_sum, 3243 orig_node_count)); 3244 else 3245 cs->count = 0; 3246 3247 for (cs = orig_node->callees; cs ; cs = cs->next_callee) 3248 cs->count = apply_probability (cs->count, 3249 GCOV_COMPUTE_SCALE (remainder, 3250 orig_node_count)); 3251 3252 if (dump_file) 3253 dump_profile_updates (orig_node, new_node); 3254} 3255 3256/* Update the respective profile of specialized NEW_NODE and the original 3257 ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM 3258 have been redirected to the specialized version. */ 3259 3260static void 3261update_specialized_profile (struct cgraph_node *new_node, 3262 struct cgraph_node *orig_node, 3263 gcov_type redirected_sum) 3264{ 3265 struct cgraph_edge *cs; 3266 gcov_type new_node_count, orig_node_count = orig_node->count; 3267 3268 if (dump_file) 3269 fprintf (dump_file, " the sum of counts of redirected edges is " 3270 HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) redirected_sum); 3271 if (orig_node_count == 0) 3272 return; 3273 3274 gcc_assert (orig_node_count >= redirected_sum); 3275 3276 new_node_count = new_node->count; 3277 new_node->count += redirected_sum; 3278 orig_node->count -= redirected_sum; 3279 3280 for (cs = new_node->callees; cs ; cs = cs->next_callee) 3281 if (cs->frequency) 3282 cs->count += apply_probability (cs->count, 3283 GCOV_COMPUTE_SCALE (redirected_sum, 3284 new_node_count)); 3285 else 3286 cs->count = 0; 3287 3288 for (cs = orig_node->callees; cs ; cs = cs->next_callee) 3289 { 3290 gcov_type dec = apply_probability (cs->count, 3291 GCOV_COMPUTE_SCALE (redirected_sum, 3292 orig_node_count)); 3293 if (dec < cs->count) 3294 cs->count -= dec; 3295 else 3296 cs->count = 0; 3297 } 3298 3299 if (dump_file) 3300 dump_profile_updates (orig_node, new_node); 3301} 3302 3303/* Create a specialized version of NODE with known constants in KNOWN_CSTS, 3304 known contexts in KNOWN_CONTEXTS and known aggregate values in AGGVALS and 3305 redirect all edges in CALLERS to it. */ 3306 3307static struct cgraph_node * 3308create_specialized_node (struct cgraph_node *node, 3309 vec<tree> known_csts, 3310 vec<ipa_polymorphic_call_context> known_contexts, 3311 struct ipa_agg_replacement_value *aggvals, 3312 vec<cgraph_edge *> callers) 3313{ 3314 struct ipa_node_params *new_info, *info = IPA_NODE_REF (node); 3315 vec<ipa_replace_map *, va_gc> *replace_trees = NULL; 3316 struct ipa_agg_replacement_value *av; 3317 struct cgraph_node *new_node; 3318 int i, count = ipa_get_param_count (info); 3319 bitmap args_to_skip; 3320 3321 gcc_assert (!info->ipcp_orig_node); 3322 3323 if (node->local.can_change_signature) 3324 { 3325 args_to_skip = BITMAP_GGC_ALLOC (); 3326 for (i = 0; i < count; i++) 3327 { 3328 tree t = known_csts[i]; 3329 3330 if (t || !ipa_is_param_used (info, i)) 3331 bitmap_set_bit (args_to_skip, i); 3332 } 3333 } 3334 else 3335 { 3336 args_to_skip = NULL; 3337 if (dump_file && (dump_flags & TDF_DETAILS)) 3338 fprintf (dump_file, " cannot change function signature\n"); 3339 } 3340 3341 for (i = 0; i < count ; i++) 3342 { 3343 tree t = known_csts[i]; 3344 if (t) 3345 { 3346 struct ipa_replace_map *replace_map; 3347 3348 gcc_checking_assert (TREE_CODE (t) != TREE_BINFO); 3349 replace_map = get_replacement_map (info, t, i); 3350 if (replace_map) 3351 vec_safe_push (replace_trees, replace_map); 3352 } 3353 } 3354 3355 new_node = node->create_virtual_clone (callers, replace_trees, 3356 args_to_skip, "constprop"); 3357 ipa_set_node_agg_value_chain (new_node, aggvals); 3358 for (av = aggvals; av; av = av->next) 3359 new_node->maybe_create_reference (av->value, IPA_REF_ADDR, NULL); 3360 3361 if (dump_file && (dump_flags & TDF_DETAILS)) 3362 { 3363 fprintf (dump_file, " the new node is %s/%i.\n", 3364 new_node->name (), new_node->order); 3365 if (known_contexts.exists ()) 3366 { 3367 for (i = 0; i < count ; i++) 3368 if (!known_contexts[i].useless_p ()) 3369 { 3370 fprintf (dump_file, " known ctx %i is ", i); 3371 known_contexts[i].dump (dump_file); 3372 } 3373 } 3374 if (aggvals) 3375 ipa_dump_agg_replacement_values (dump_file, aggvals); 3376 } 3377 ipa_check_create_node_params (); 3378 update_profiling_info (node, new_node); 3379 new_info = IPA_NODE_REF (new_node); 3380 new_info->ipcp_orig_node = node; 3381 new_info->known_csts = known_csts; 3382 new_info->known_contexts = known_contexts; 3383 3384 ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, aggvals); 3385 3386 callers.release (); 3387 return new_node; 3388} 3389 3390/* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in 3391 KNOWN_CSTS with constants that are also known for all of the CALLERS. */ 3392 3393static void 3394find_more_scalar_values_for_callers_subset (struct cgraph_node *node, 3395 vec<tree> known_csts, 3396 vec<cgraph_edge *> callers) 3397{ 3398 struct ipa_node_params *info = IPA_NODE_REF (node); 3399 int i, count = ipa_get_param_count (info); 3400 3401 for (i = 0; i < count ; i++) 3402 { 3403 struct cgraph_edge *cs; 3404 tree newval = NULL_TREE; 3405 int j; 3406 bool first = true; 3407 3408 if (ipa_get_scalar_lat (info, i)->bottom || known_csts[i]) 3409 continue; 3410 3411 FOR_EACH_VEC_ELT (callers, j, cs) 3412 { 3413 struct ipa_jump_func *jump_func; 3414 tree t; 3415 3416 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)) 3417 || (i == 0 3418 && call_passes_through_thunk_p (cs)) 3419 || (!cs->callee->instrumentation_clone 3420 && cs->callee->function_symbol ()->instrumentation_clone)) 3421 { 3422 newval = NULL_TREE; 3423 break; 3424 } 3425 jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i); 3426 t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func); 3427 if (!t 3428 || (newval 3429 && !values_equal_for_ipcp_p (t, newval)) 3430 || (!first && !newval)) 3431 { 3432 newval = NULL_TREE; 3433 break; 3434 } 3435 else 3436 newval = t; 3437 first = false; 3438 } 3439 3440 if (newval) 3441 { 3442 if (dump_file && (dump_flags & TDF_DETAILS)) 3443 { 3444 fprintf (dump_file, " adding an extra known scalar value "); 3445 print_ipcp_constant_value (dump_file, newval); 3446 fprintf (dump_file, " for "); 3447 ipa_dump_param (dump_file, info, i); 3448 fprintf (dump_file, "\n"); 3449 } 3450 3451 known_csts[i] = newval; 3452 } 3453 } 3454} 3455 3456/* Given a NODE and a subset of its CALLERS, try to populate plank slots in 3457 KNOWN_CONTEXTS with polymorphic contexts that are also known for all of the 3458 CALLERS. */ 3459 3460static void 3461find_more_contexts_for_caller_subset (cgraph_node *node, 3462 vec<ipa_polymorphic_call_context> 3463 *known_contexts, 3464 vec<cgraph_edge *> callers) 3465{ 3466 ipa_node_params *info = IPA_NODE_REF (node); 3467 int i, count = ipa_get_param_count (info); 3468 3469 for (i = 0; i < count ; i++) 3470 { 3471 cgraph_edge *cs; 3472 3473 if (ipa_get_poly_ctx_lat (info, i)->bottom 3474 || (known_contexts->exists () 3475 && !(*known_contexts)[i].useless_p ())) 3476 continue; 3477 3478 ipa_polymorphic_call_context newval; 3479 bool first = true; 3480 int j; 3481 3482 FOR_EACH_VEC_ELT (callers, j, cs) 3483 { 3484 if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs))) 3485 return; 3486 ipa_jump_func *jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), 3487 i); 3488 ipa_polymorphic_call_context ctx; 3489 ctx = ipa_context_from_jfunc (IPA_NODE_REF (cs->caller), cs, i, 3490 jfunc); 3491 if (first) 3492 { 3493 newval = ctx; 3494 first = false; 3495 } 3496 else 3497 newval.meet_with (ctx); 3498 if (newval.useless_p ()) 3499 break; 3500 } 3501 3502 if (!newval.useless_p ()) 3503 { 3504 if (dump_file && (dump_flags & TDF_DETAILS)) 3505 { 3506 fprintf (dump_file, " adding an extra known polymorphic " 3507 "context "); 3508 print_ipcp_constant_value (dump_file, newval); 3509 fprintf (dump_file, " for "); 3510 ipa_dump_param (dump_file, info, i); 3511 fprintf (dump_file, "\n"); 3512 } 3513 3514 if (!known_contexts->exists ()) 3515 known_contexts->safe_grow_cleared (ipa_get_param_count (info)); 3516 (*known_contexts)[i] = newval; 3517 } 3518 3519 } 3520} 3521 3522/* Go through PLATS and create a vector of values consisting of values and 3523 offsets (minus OFFSET) of lattices that contain only a single value. */ 3524 3525static vec<ipa_agg_jf_item> 3526copy_plats_to_inter (struct ipcp_param_lattices *plats, HOST_WIDE_INT offset) 3527{ 3528 vec<ipa_agg_jf_item> res = vNULL; 3529 3530 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom) 3531 return vNULL; 3532 3533 for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next) 3534 if (aglat->is_single_const ()) 3535 { 3536 struct ipa_agg_jf_item ti; 3537 ti.offset = aglat->offset - offset; 3538 ti.value = aglat->values->value; 3539 res.safe_push (ti); 3540 } 3541 return res; 3542} 3543 3544/* Intersect all values in INTER with single value lattices in PLATS (while 3545 subtracting OFFSET). */ 3546 3547static void 3548intersect_with_plats (struct ipcp_param_lattices *plats, 3549 vec<ipa_agg_jf_item> *inter, 3550 HOST_WIDE_INT offset) 3551{ 3552 struct ipcp_agg_lattice *aglat; 3553 struct ipa_agg_jf_item *item; 3554 int k; 3555 3556 if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom) 3557 { 3558 inter->release (); 3559 return; 3560 } 3561 3562 aglat = plats->aggs; 3563 FOR_EACH_VEC_ELT (*inter, k, item) 3564 { 3565 bool found = false; 3566 if (!item->value) 3567 continue; 3568 while (aglat) 3569 { 3570 if (aglat->offset - offset > item->offset) 3571 break; 3572 if (aglat->offset - offset == item->offset) 3573 { 3574 gcc_checking_assert (item->value); 3575 if (values_equal_for_ipcp_p (item->value, aglat->values->value)) 3576 found = true; 3577 break; 3578 } 3579 aglat = aglat->next; 3580 } 3581 if (!found) 3582 item->value = NULL_TREE; 3583 } 3584} 3585 3586/* Copy agggregate replacement values of NODE (which is an IPA-CP clone) to the 3587 vector result while subtracting OFFSET from the individual value offsets. */ 3588 3589static vec<ipa_agg_jf_item> 3590agg_replacements_to_vector (struct cgraph_node *node, int index, 3591 HOST_WIDE_INT offset) 3592{ 3593 struct ipa_agg_replacement_value *av; 3594 vec<ipa_agg_jf_item> res = vNULL; 3595 3596 for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next) 3597 if (av->index == index 3598 && (av->offset - offset) >= 0) 3599 { 3600 struct ipa_agg_jf_item item; 3601 gcc_checking_assert (av->value); 3602 item.offset = av->offset - offset; 3603 item.value = av->value; 3604 res.safe_push (item); 3605 } 3606 3607 return res; 3608} 3609 3610/* Intersect all values in INTER with those that we have already scheduled to 3611 be replaced in parameter number INDEX of NODE, which is an IPA-CP clone 3612 (while subtracting OFFSET). */ 3613 3614static void 3615intersect_with_agg_replacements (struct cgraph_node *node, int index, 3616 vec<ipa_agg_jf_item> *inter, 3617 HOST_WIDE_INT offset) 3618{ 3619 struct ipa_agg_replacement_value *srcvals; 3620 struct ipa_agg_jf_item *item; 3621 int i; 3622 3623 srcvals = ipa_get_agg_replacements_for_node (node); 3624 if (!srcvals) 3625 { 3626 inter->release (); 3627 return; 3628 } 3629 3630 FOR_EACH_VEC_ELT (*inter, i, item) 3631 { 3632 struct ipa_agg_replacement_value *av; 3633 bool found = false; 3634 if (!item->value) 3635 continue; 3636 for (av = srcvals; av; av = av->next) 3637 { 3638 gcc_checking_assert (av->value); 3639 if (av->index == index 3640 && av->offset - offset == item->offset) 3641 { 3642 if (values_equal_for_ipcp_p (item->value, av->value)) 3643 found = true; 3644 break; 3645 } 3646 } 3647 if (!found) 3648 item->value = NULL_TREE; 3649 } 3650} 3651 3652/* Intersect values in INTER with aggregate values that come along edge CS to 3653 parameter number INDEX and return it. If INTER does not actually exist yet, 3654 copy all incoming values to it. If we determine we ended up with no values 3655 whatsoever, return a released vector. */ 3656 3657static vec<ipa_agg_jf_item> 3658intersect_aggregates_with_edge (struct cgraph_edge *cs, int index, 3659 vec<ipa_agg_jf_item> inter) 3660{ 3661 struct ipa_jump_func *jfunc; 3662 jfunc = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), index); 3663 if (jfunc->type == IPA_JF_PASS_THROUGH 3664 && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR) 3665 { 3666 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); 3667 int src_idx = ipa_get_jf_pass_through_formal_id (jfunc); 3668 3669 if (caller_info->ipcp_orig_node) 3670 { 3671 struct cgraph_node *orig_node = caller_info->ipcp_orig_node; 3672 struct ipcp_param_lattices *orig_plats; 3673 orig_plats = ipa_get_parm_lattices (IPA_NODE_REF (orig_node), 3674 src_idx); 3675 if (agg_pass_through_permissible_p (orig_plats, jfunc)) 3676 { 3677 if (!inter.exists ()) 3678 inter = agg_replacements_to_vector (cs->caller, src_idx, 0); 3679 else 3680 intersect_with_agg_replacements (cs->caller, src_idx, 3681 &inter, 0); 3682 } 3683 else 3684 { 3685 inter.release (); 3686 return vNULL; 3687 } 3688 } 3689 else 3690 { 3691 struct ipcp_param_lattices *src_plats; 3692 src_plats = ipa_get_parm_lattices (caller_info, src_idx); 3693 if (agg_pass_through_permissible_p (src_plats, jfunc)) 3694 { 3695 /* Currently we do not produce clobber aggregate jump 3696 functions, adjust when we do. */ 3697 gcc_checking_assert (!jfunc->agg.items); 3698 if (!inter.exists ()) 3699 inter = copy_plats_to_inter (src_plats, 0); 3700 else 3701 intersect_with_plats (src_plats, &inter, 0); 3702 } 3703 else 3704 { 3705 inter.release (); 3706 return vNULL; 3707 } 3708 } 3709 } 3710 else if (jfunc->type == IPA_JF_ANCESTOR 3711 && ipa_get_jf_ancestor_agg_preserved (jfunc)) 3712 { 3713 struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); 3714 int src_idx = ipa_get_jf_ancestor_formal_id (jfunc); 3715 struct ipcp_param_lattices *src_plats; 3716 HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc); 3717 3718 if (caller_info->ipcp_orig_node) 3719 { 3720 if (!inter.exists ()) 3721 inter = agg_replacements_to_vector (cs->caller, src_idx, delta); 3722 else 3723 intersect_with_agg_replacements (cs->caller, src_idx, &inter, 3724 delta); 3725 } 3726 else 3727 { 3728 src_plats = ipa_get_parm_lattices (caller_info, src_idx);; 3729 /* Currently we do not produce clobber aggregate jump 3730 functions, adjust when we do. */ 3731 gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items); 3732 if (!inter.exists ()) 3733 inter = copy_plats_to_inter (src_plats, delta); 3734 else 3735 intersect_with_plats (src_plats, &inter, delta); 3736 } 3737 } 3738 else if (jfunc->agg.items) 3739 { 3740 struct ipa_agg_jf_item *item; 3741 int k; 3742 3743 if (!inter.exists ()) 3744 for (unsigned i = 0; i < jfunc->agg.items->length (); i++) 3745 inter.safe_push ((*jfunc->agg.items)[i]); 3746 else 3747 FOR_EACH_VEC_ELT (inter, k, item) 3748 { 3749 int l = 0; 3750 bool found = false;; 3751 3752 if (!item->value) 3753 continue; 3754 3755 while ((unsigned) l < jfunc->agg.items->length ()) 3756 { 3757 struct ipa_agg_jf_item *ti; 3758 ti = &(*jfunc->agg.items)[l]; 3759 if (ti->offset > item->offset) 3760 break; 3761 if (ti->offset == item->offset) 3762 { 3763 gcc_checking_assert (ti->value); 3764 if (values_equal_for_ipcp_p (item->value, 3765 ti->value)) 3766 found = true; 3767 break; 3768 } 3769 l++; 3770 } 3771 if (!found) 3772 item->value = NULL; 3773 } 3774 } 3775 else 3776 { 3777 inter.release (); 3778 return vec<ipa_agg_jf_item>(); 3779 } 3780 return inter; 3781} 3782 3783/* Look at edges in CALLERS and collect all known aggregate values that arrive 3784 from all of them. */ 3785 3786static struct ipa_agg_replacement_value * 3787find_aggregate_values_for_callers_subset (struct cgraph_node *node, 3788 vec<cgraph_edge *> callers) 3789{ 3790 struct ipa_node_params *dest_info = IPA_NODE_REF (node); 3791 struct ipa_agg_replacement_value *res; 3792 struct ipa_agg_replacement_value **tail = &res; 3793 struct cgraph_edge *cs; 3794 int i, j, count = ipa_get_param_count (dest_info); 3795 3796 FOR_EACH_VEC_ELT (callers, j, cs) 3797 { 3798 int c = ipa_get_cs_argument_count (IPA_EDGE_REF (cs)); 3799 if (c < count) 3800 count = c; 3801 } 3802 3803 for (i = 0; i < count ; i++) 3804 { 3805 struct cgraph_edge *cs; 3806 vec<ipa_agg_jf_item> inter = vNULL; 3807 struct ipa_agg_jf_item *item; 3808 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i); 3809 int j; 3810 3811 /* Among other things, the following check should deal with all by_ref 3812 mismatches. */ 3813 if (plats->aggs_bottom) 3814 continue; 3815 3816 FOR_EACH_VEC_ELT (callers, j, cs) 3817 { 3818 inter = intersect_aggregates_with_edge (cs, i, inter); 3819 3820 if (!inter.exists ()) 3821 goto next_param; 3822 } 3823 3824 FOR_EACH_VEC_ELT (inter, j, item) 3825 { 3826 struct ipa_agg_replacement_value *v; 3827 3828 if (!item->value) 3829 continue; 3830 3831 v = ggc_alloc<ipa_agg_replacement_value> (); 3832 v->index = i; 3833 v->offset = item->offset; 3834 v->value = item->value; 3835 v->by_ref = plats->aggs_by_ref; 3836 *tail = v; 3837 tail = &v->next; 3838 } 3839 3840 next_param: 3841 if (inter.exists ()) 3842 inter.release (); 3843 } 3844 *tail = NULL; 3845 return res; 3846} 3847 3848/* Turn KNOWN_AGGS into a list of aggreate replacement values. */ 3849 3850static struct ipa_agg_replacement_value * 3851known_aggs_to_agg_replacement_list (vec<ipa_agg_jump_function> known_aggs) 3852{ 3853 struct ipa_agg_replacement_value *res; 3854 struct ipa_agg_replacement_value **tail = &res; 3855 struct ipa_agg_jump_function *aggjf; 3856 struct ipa_agg_jf_item *item; 3857 int i, j; 3858 3859 FOR_EACH_VEC_ELT (known_aggs, i, aggjf) 3860 FOR_EACH_VEC_SAFE_ELT (aggjf->items, j, item) 3861 { 3862 struct ipa_agg_replacement_value *v; 3863 v = ggc_alloc<ipa_agg_replacement_value> (); 3864 v->index = i; 3865 v->offset = item->offset; 3866 v->value = item->value; 3867 v->by_ref = aggjf->by_ref; 3868 *tail = v; 3869 tail = &v->next; 3870 } 3871 *tail = NULL; 3872 return res; 3873} 3874 3875/* Determine whether CS also brings all scalar values that the NODE is 3876 specialized for. */ 3877 3878static bool 3879cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs, 3880 struct cgraph_node *node) 3881{ 3882 struct ipa_node_params *dest_info = IPA_NODE_REF (node); 3883 int count = ipa_get_param_count (dest_info); 3884 struct ipa_node_params *caller_info; 3885 struct ipa_edge_args *args; 3886 int i; 3887 3888 caller_info = IPA_NODE_REF (cs->caller); 3889 args = IPA_EDGE_REF (cs); 3890 for (i = 0; i < count; i++) 3891 { 3892 struct ipa_jump_func *jump_func; 3893 tree val, t; 3894 3895 val = dest_info->known_csts[i]; 3896 if (!val) 3897 continue; 3898 3899 if (i >= ipa_get_cs_argument_count (args)) 3900 return false; 3901 jump_func = ipa_get_ith_jump_func (args, i); 3902 t = ipa_value_from_jfunc (caller_info, jump_func); 3903 if (!t || !values_equal_for_ipcp_p (val, t)) 3904 return false; 3905 } 3906 return true; 3907} 3908 3909/* Determine whether CS also brings all aggregate values that NODE is 3910 specialized for. */ 3911static bool 3912cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs, 3913 struct cgraph_node *node) 3914{ 3915 struct ipa_node_params *orig_caller_info = IPA_NODE_REF (cs->caller); 3916 struct ipa_node_params *orig_node_info; 3917 struct ipa_agg_replacement_value *aggval; 3918 int i, ec, count; 3919 3920 aggval = ipa_get_agg_replacements_for_node (node); 3921 if (!aggval) 3922 return true; 3923 3924 count = ipa_get_param_count (IPA_NODE_REF (node)); 3925 ec = ipa_get_cs_argument_count (IPA_EDGE_REF (cs)); 3926 if (ec < count) 3927 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) 3928 if (aggval->index >= ec) 3929 return false; 3930 3931 orig_node_info = IPA_NODE_REF (IPA_NODE_REF (node)->ipcp_orig_node); 3932 if (orig_caller_info->ipcp_orig_node) 3933 orig_caller_info = IPA_NODE_REF (orig_caller_info->ipcp_orig_node); 3934 3935 for (i = 0; i < count; i++) 3936 { 3937 static vec<ipa_agg_jf_item> values = vec<ipa_agg_jf_item>(); 3938 struct ipcp_param_lattices *plats; 3939 bool interesting = false; 3940 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) 3941 if (aggval->index == i) 3942 { 3943 interesting = true; 3944 break; 3945 } 3946 if (!interesting) 3947 continue; 3948 3949 plats = ipa_get_parm_lattices (orig_node_info, aggval->index); 3950 if (plats->aggs_bottom) 3951 return false; 3952 3953 values = intersect_aggregates_with_edge (cs, i, values); 3954 if (!values.exists ()) 3955 return false; 3956 3957 for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) 3958 if (aggval->index == i) 3959 { 3960 struct ipa_agg_jf_item *item; 3961 int j; 3962 bool found = false; 3963 FOR_EACH_VEC_ELT (values, j, item) 3964 if (item->value 3965 && item->offset == av->offset 3966 && values_equal_for_ipcp_p (item->value, av->value)) 3967 { 3968 found = true; 3969 break; 3970 } 3971 if (!found) 3972 { 3973 values.release (); 3974 return false; 3975 } 3976 } 3977 } 3978 return true; 3979} 3980 3981/* Given an original NODE and a VAL for which we have already created a 3982 specialized clone, look whether there are incoming edges that still lead 3983 into the old node but now also bring the requested value and also conform to 3984 all other criteria such that they can be redirected the the special node. 3985 This function can therefore redirect the final edge in a SCC. */ 3986 3987template <typename valtype> 3988static void 3989perhaps_add_new_callers (cgraph_node *node, ipcp_value<valtype> *val) 3990{ 3991 ipcp_value_source<valtype> *src; 3992 gcov_type redirected_sum = 0; 3993 3994 for (src = val->sources; src; src = src->next) 3995 { 3996 struct cgraph_edge *cs = src->cs; 3997 while (cs) 3998 { 3999 if (cgraph_edge_brings_value_p (cs, src, node) 4000 && cgraph_edge_brings_all_scalars_for_node (cs, val->spec_node) 4001 && cgraph_edge_brings_all_agg_vals_for_node (cs, val->spec_node)) 4002 { 4003 if (dump_file) 4004 fprintf (dump_file, " - adding an extra caller %s/%i" 4005 " of %s/%i\n", 4006 xstrdup_for_dump (cs->caller->name ()), 4007 cs->caller->order, 4008 xstrdup_for_dump (val->spec_node->name ()), 4009 val->spec_node->order); 4010 4011 cs->redirect_callee_duplicating_thunks (val->spec_node); 4012 val->spec_node->expand_all_artificial_thunks (); 4013 redirected_sum += cs->count; 4014 } 4015 cs = get_next_cgraph_edge_clone (cs); 4016 } 4017 } 4018 4019 if (redirected_sum) 4020 update_specialized_profile (val->spec_node, node, redirected_sum); 4021} 4022 4023/* Return true if KNOWN_CONTEXTS contain at least one useful context. */ 4024 4025static bool 4026known_contexts_useful_p (vec<ipa_polymorphic_call_context> known_contexts) 4027{ 4028 ipa_polymorphic_call_context *ctx; 4029 int i; 4030 4031 FOR_EACH_VEC_ELT (known_contexts, i, ctx) 4032 if (!ctx->useless_p ()) 4033 return true; 4034 return false; 4035} 4036 4037/* Return a copy of KNOWN_CSTS if it is not empty, otherwise return vNULL. */ 4038 4039static vec<ipa_polymorphic_call_context> 4040copy_useful_known_contexts (vec<ipa_polymorphic_call_context> known_contexts) 4041{ 4042 if (known_contexts_useful_p (known_contexts)) 4043 return known_contexts.copy (); 4044 else 4045 return vNULL; 4046} 4047 4048/* Copy KNOWN_CSTS and modify the copy according to VAL and INDEX. If 4049 non-empty, replace KNOWN_CONTEXTS with its copy too. */ 4050 4051static void 4052modify_known_vectors_with_val (vec<tree> *known_csts, 4053 vec<ipa_polymorphic_call_context> *known_contexts, 4054 ipcp_value<tree> *val, 4055 int index) 4056{ 4057 *known_csts = known_csts->copy (); 4058 *known_contexts = copy_useful_known_contexts (*known_contexts); 4059 (*known_csts)[index] = val->value; 4060} 4061 4062/* Replace KNOWN_CSTS with its copy. Also copy KNOWN_CONTEXTS and modify the 4063 copy according to VAL and INDEX. */ 4064 4065static void 4066modify_known_vectors_with_val (vec<tree> *known_csts, 4067 vec<ipa_polymorphic_call_context> *known_contexts, 4068 ipcp_value<ipa_polymorphic_call_context> *val, 4069 int index) 4070{ 4071 *known_csts = known_csts->copy (); 4072 *known_contexts = known_contexts->copy (); 4073 (*known_contexts)[index] = val->value; 4074} 4075 4076/* Return true if OFFSET indicates this was not an aggregate value or there is 4077 a replacement equivalent to VALUE, INDEX and OFFSET among those in the 4078 AGGVALS list. */ 4079 4080DEBUG_FUNCTION bool 4081ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *aggvals, 4082 int index, HOST_WIDE_INT offset, tree value) 4083{ 4084 if (offset == -1) 4085 return true; 4086 4087 while (aggvals) 4088 { 4089 if (aggvals->index == index 4090 && aggvals->offset == offset 4091 && values_equal_for_ipcp_p (aggvals->value, value)) 4092 return true; 4093 aggvals = aggvals->next; 4094 } 4095 return false; 4096} 4097 4098/* Return true if offset is minus one because source of a polymorphic contect 4099 cannot be an aggregate value. */ 4100 4101DEBUG_FUNCTION bool 4102ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *, 4103 int , HOST_WIDE_INT offset, 4104 ipa_polymorphic_call_context) 4105{ 4106 return offset == -1; 4107} 4108 4109/* Decide wheter to create a special version of NODE for value VAL of parameter 4110 at the given INDEX. If OFFSET is -1, the value is for the parameter itself, 4111 otherwise it is stored at the given OFFSET of the parameter. KNOWN_CSTS, 4112 KNOWN_CONTEXTS and KNOWN_AGGS describe the other already known values. */ 4113 4114template <typename valtype> 4115static bool 4116decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset, 4117 ipcp_value<valtype> *val, vec<tree> known_csts, 4118 vec<ipa_polymorphic_call_context> known_contexts) 4119{ 4120 struct ipa_agg_replacement_value *aggvals; 4121 int freq_sum, caller_count; 4122 gcov_type count_sum; 4123 vec<cgraph_edge *> callers; 4124 4125 if (val->spec_node) 4126 { 4127 perhaps_add_new_callers (node, val); 4128 return false; 4129 } 4130 else if (val->local_size_cost + overall_size > max_new_size) 4131 { 4132 if (dump_file && (dump_flags & TDF_DETAILS)) 4133 fprintf (dump_file, " Ignoring candidate value because " 4134 "max_new_size would be reached with %li.\n", 4135 val->local_size_cost + overall_size); 4136 return false; 4137 } 4138 else if (!get_info_about_necessary_edges (val, node, &freq_sum, &count_sum, 4139 &caller_count)) 4140 return false; 4141 4142 if (dump_file && (dump_flags & TDF_DETAILS)) 4143 { 4144 fprintf (dump_file, " - considering value "); 4145 print_ipcp_constant_value (dump_file, val->value); 4146 fprintf (dump_file, " for "); 4147 ipa_dump_param (dump_file, IPA_NODE_REF (node), index); 4148 if (offset != -1) 4149 fprintf (dump_file, ", offset: " HOST_WIDE_INT_PRINT_DEC, offset); 4150 fprintf (dump_file, " (caller_count: %i)\n", caller_count); 4151 } 4152 4153 if (!good_cloning_opportunity_p (node, val->local_time_benefit, 4154 freq_sum, count_sum, 4155 val->local_size_cost) 4156 && !good_cloning_opportunity_p (node, 4157 val->local_time_benefit 4158 + val->prop_time_benefit, 4159 freq_sum, count_sum, 4160 val->local_size_cost 4161 + val->prop_size_cost)) 4162 return false; 4163 4164 if (dump_file) 4165 fprintf (dump_file, " Creating a specialized node of %s/%i.\n", 4166 node->name (), node->order); 4167 4168 callers = gather_edges_for_value (val, node, caller_count); 4169 if (offset == -1) 4170 modify_known_vectors_with_val (&known_csts, &known_contexts, val, index); 4171 else 4172 { 4173 known_csts = known_csts.copy (); 4174 known_contexts = copy_useful_known_contexts (known_contexts); 4175 } 4176 find_more_scalar_values_for_callers_subset (node, known_csts, callers); 4177 find_more_contexts_for_caller_subset (node, &known_contexts, callers); 4178 aggvals = find_aggregate_values_for_callers_subset (node, callers); 4179 gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals, index, 4180 offset, val->value)); 4181 val->spec_node = create_specialized_node (node, known_csts, known_contexts, 4182 aggvals, callers); 4183 overall_size += val->local_size_cost; 4184 4185 /* TODO: If for some lattice there is only one other known value 4186 left, make a special node for it too. */ 4187 4188 return true; 4189} 4190 4191/* Decide whether and what specialized clones of NODE should be created. */ 4192 4193static bool 4194decide_whether_version_node (struct cgraph_node *node) 4195{ 4196 struct ipa_node_params *info = IPA_NODE_REF (node); 4197 int i, count = ipa_get_param_count (info); 4198 vec<tree> known_csts; 4199 vec<ipa_polymorphic_call_context> known_contexts; 4200 vec<ipa_agg_jump_function> known_aggs = vNULL; 4201 bool ret = false; 4202 4203 if (count == 0) 4204 return false; 4205 4206 if (dump_file && (dump_flags & TDF_DETAILS)) 4207 fprintf (dump_file, "\nEvaluating opportunities for %s/%i.\n", 4208 node->name (), node->order); 4209 4210 gather_context_independent_values (info, &known_csts, &known_contexts, 4211 info->do_clone_for_all_contexts ? &known_aggs 4212 : NULL, NULL); 4213 4214 for (i = 0; i < count ;i++) 4215 { 4216 struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); 4217 ipcp_lattice<tree> *lat = &plats->itself; 4218 ipcp_lattice<ipa_polymorphic_call_context> *ctxlat = &plats->ctxlat; 4219 4220 if (!lat->bottom 4221 && !known_csts[i]) 4222 { 4223 ipcp_value<tree> *val; 4224 for (val = lat->values; val; val = val->next) 4225 ret |= decide_about_value (node, i, -1, val, known_csts, 4226 known_contexts); 4227 } 4228 4229 if (!plats->aggs_bottom) 4230 { 4231 struct ipcp_agg_lattice *aglat; 4232 ipcp_value<tree> *val; 4233 for (aglat = plats->aggs; aglat; aglat = aglat->next) 4234 if (!aglat->bottom && aglat->values 4235 /* If the following is false, the one value is in 4236 known_aggs. */ 4237 && (plats->aggs_contain_variable 4238 || !aglat->is_single_const ())) 4239 for (val = aglat->values; val; val = val->next) 4240 ret |= decide_about_value (node, i, aglat->offset, val, 4241 known_csts, known_contexts); 4242 } 4243 4244 if (!ctxlat->bottom 4245 && known_contexts[i].useless_p ()) 4246 { 4247 ipcp_value<ipa_polymorphic_call_context> *val; 4248 for (val = ctxlat->values; val; val = val->next) 4249 ret |= decide_about_value (node, i, -1, val, known_csts, 4250 known_contexts); 4251 } 4252 4253 info = IPA_NODE_REF (node); 4254 } 4255 4256 if (info->do_clone_for_all_contexts) 4257 { 4258 struct cgraph_node *clone; 4259 vec<cgraph_edge *> callers; 4260 4261 if (dump_file) 4262 fprintf (dump_file, " - Creating a specialized node of %s/%i " 4263 "for all known contexts.\n", node->name (), 4264 node->order); 4265 4266 callers = node->collect_callers (); 4267 4268 if (!known_contexts_useful_p (known_contexts)) 4269 { 4270 known_contexts.release (); 4271 known_contexts = vNULL; 4272 } 4273 clone = create_specialized_node (node, known_csts, known_contexts, 4274 known_aggs_to_agg_replacement_list (known_aggs), 4275 callers); 4276 info = IPA_NODE_REF (node); 4277 info->do_clone_for_all_contexts = false; 4278 IPA_NODE_REF (clone)->is_all_contexts_clone = true; 4279 for (i = 0; i < count ; i++) 4280 vec_free (known_aggs[i].items); 4281 known_aggs.release (); 4282 ret = true; 4283 } 4284 else 4285 { 4286 known_csts.release (); 4287 known_contexts.release (); 4288 } 4289 4290 return ret; 4291} 4292 4293/* Transitively mark all callees of NODE within the same SCC as not dead. */ 4294 4295static void 4296spread_undeadness (struct cgraph_node *node) 4297{ 4298 struct cgraph_edge *cs; 4299 4300 for (cs = node->callees; cs; cs = cs->next_callee) 4301 if (ipa_edge_within_scc (cs)) 4302 { 4303 struct cgraph_node *callee; 4304 struct ipa_node_params *info; 4305 4306 callee = cs->callee->function_symbol (NULL); 4307 info = IPA_NODE_REF (callee); 4308 4309 if (info->node_dead) 4310 { 4311 info->node_dead = 0; 4312 spread_undeadness (callee); 4313 } 4314 } 4315} 4316 4317/* Return true if NODE has a caller from outside of its SCC that is not 4318 dead. Worker callback for cgraph_for_node_and_aliases. */ 4319 4320static bool 4321has_undead_caller_from_outside_scc_p (struct cgraph_node *node, 4322 void *data ATTRIBUTE_UNUSED) 4323{ 4324 struct cgraph_edge *cs; 4325 4326 for (cs = node->callers; cs; cs = cs->next_caller) 4327 if (cs->caller->thunk.thunk_p 4328 && cs->caller->call_for_symbol_thunks_and_aliases 4329 (has_undead_caller_from_outside_scc_p, NULL, true)) 4330 return true; 4331 else if (!ipa_edge_within_scc (cs) 4332 && !IPA_NODE_REF (cs->caller)->node_dead) 4333 return true; 4334 return false; 4335} 4336 4337 4338/* Identify nodes within the same SCC as NODE which are no longer needed 4339 because of new clones and will be removed as unreachable. */ 4340 4341static void 4342identify_dead_nodes (struct cgraph_node *node) 4343{ 4344 struct cgraph_node *v; 4345 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) 4346 if (v->will_be_removed_from_program_if_no_direct_calls_p () 4347 && !v->call_for_symbol_thunks_and_aliases 4348 (has_undead_caller_from_outside_scc_p, NULL, true)) 4349 IPA_NODE_REF (v)->node_dead = 1; 4350 4351 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) 4352 if (!IPA_NODE_REF (v)->node_dead) 4353 spread_undeadness (v); 4354 4355 if (dump_file && (dump_flags & TDF_DETAILS)) 4356 { 4357 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) 4358 if (IPA_NODE_REF (v)->node_dead) 4359 fprintf (dump_file, " Marking node as dead: %s/%i.\n", 4360 v->name (), v->order); 4361 } 4362} 4363 4364/* The decision stage. Iterate over the topological order of call graph nodes 4365 TOPO and make specialized clones if deemed beneficial. */ 4366 4367static void 4368ipcp_decision_stage (struct ipa_topo_info *topo) 4369{ 4370 int i; 4371 4372 if (dump_file) 4373 fprintf (dump_file, "\nIPA decision stage:\n\n"); 4374 4375 for (i = topo->nnodes - 1; i >= 0; i--) 4376 { 4377 struct cgraph_node *node = topo->order[i]; 4378 bool change = false, iterate = true; 4379 4380 while (iterate) 4381 { 4382 struct cgraph_node *v; 4383 iterate = false; 4384 for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle) 4385 if (v->has_gimple_body_p () 4386 && ipcp_versionable_function_p (v)) 4387 iterate |= decide_whether_version_node (v); 4388 4389 change |= iterate; 4390 } 4391 if (change) 4392 identify_dead_nodes (node); 4393 } 4394} 4395 4396/* Look up all alignment information that we have discovered and copy it over 4397 to the transformation summary. */ 4398 4399static void 4400ipcp_store_alignment_results (void) 4401{ 4402 cgraph_node *node; 4403 4404 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) 4405 { 4406 ipa_node_params *info = IPA_NODE_REF (node); 4407 bool dumped_sth = false; 4408 bool found_useful_result = false; 4409 4410 if (!opt_for_fn (node->decl, flag_ipa_cp_alignment)) 4411 { 4412 if (dump_file) 4413 fprintf (dump_file, "Not considering %s for alignment discovery " 4414 "and propagate; -fipa-cp-alignment: disabled.\n", 4415 node->name ()); 4416 continue; 4417 } 4418 4419 if (info->ipcp_orig_node) 4420 info = IPA_NODE_REF (info->ipcp_orig_node); 4421 4422 unsigned count = ipa_get_param_count (info); 4423 for (unsigned i = 0; i < count ; i++) 4424 { 4425 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); 4426 if (plats->alignment.known 4427 && plats->alignment.align > 0) 4428 { 4429 found_useful_result = true; 4430 break; 4431 } 4432 } 4433 if (!found_useful_result) 4434 continue; 4435 4436 ipcp_grow_transformations_if_necessary (); 4437 ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); 4438 vec_safe_reserve_exact (ts->alignments, count); 4439 4440 for (unsigned i = 0; i < count ; i++) 4441 { 4442 ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); 4443 4444 if (plats->alignment.align == 0) 4445 plats->alignment.known = false; 4446 4447 ts->alignments->quick_push (plats->alignment); 4448 if (!dump_file || !plats->alignment.known) 4449 continue; 4450 if (!dumped_sth) 4451 { 4452 fprintf (dump_file, "Propagated alignment info for function %s/%i:\n", 4453 node->name (), node->order); 4454 dumped_sth = true; 4455 } 4456 fprintf (dump_file, " param %i: align: %u, misalign: %u\n", 4457 i, plats->alignment.align, plats->alignment.misalign); 4458 } 4459 } 4460} 4461 4462/* The IPCP driver. */ 4463 4464static unsigned int 4465ipcp_driver (void) 4466{ 4467 struct cgraph_2edge_hook_list *edge_duplication_hook_holder; 4468 struct cgraph_edge_hook_list *edge_removal_hook_holder; 4469 struct ipa_topo_info topo; 4470 4471 ipa_check_create_node_params (); 4472 ipa_check_create_edge_args (); 4473 grow_edge_clone_vectors (); 4474 edge_duplication_hook_holder = 4475 symtab->add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL); 4476 edge_removal_hook_holder = 4477 symtab->add_edge_removal_hook (&ipcp_edge_removal_hook, NULL); 4478 4479 ipcp_cst_values_pool = create_alloc_pool ("IPA-CP constant values", 4480 sizeof (ipcp_value<tree>), 32); 4481 ipcp_poly_ctx_values_pool = create_alloc_pool 4482 ("IPA-CP polymorphic contexts", 4483 sizeof (ipcp_value<ipa_polymorphic_call_context>), 32); 4484 ipcp_sources_pool = create_alloc_pool ("IPA-CP value sources", 4485 sizeof (ipcp_value_source<tree>), 64); 4486 ipcp_agg_lattice_pool = create_alloc_pool ("IPA_CP aggregate lattices", 4487 sizeof (struct ipcp_agg_lattice), 4488 32); 4489 if (dump_file) 4490 { 4491 fprintf (dump_file, "\nIPA structures before propagation:\n"); 4492 if (dump_flags & TDF_DETAILS) 4493 ipa_print_all_params (dump_file); 4494 ipa_print_all_jump_functions (dump_file); 4495 } 4496 4497 /* Topological sort. */ 4498 build_toporder_info (&topo); 4499 /* Do the interprocedural propagation. */ 4500 ipcp_propagate_stage (&topo); 4501 /* Decide what constant propagation and cloning should be performed. */ 4502 ipcp_decision_stage (&topo); 4503 /* Store results of alignment propagation. */ 4504 ipcp_store_alignment_results (); 4505 4506 /* Free all IPCP structures. */ 4507 free_toporder_info (&topo); 4508 next_edge_clone.release (); 4509 symtab->remove_edge_removal_hook (edge_removal_hook_holder); 4510 symtab->remove_edge_duplication_hook (edge_duplication_hook_holder); 4511 ipa_free_all_structures_after_ipa_cp (); 4512 if (dump_file) 4513 fprintf (dump_file, "\nIPA constant propagation end\n"); 4514 return 0; 4515} 4516 4517/* Initialization and computation of IPCP data structures. This is the initial 4518 intraprocedural analysis of functions, which gathers information to be 4519 propagated later on. */ 4520 4521static void 4522ipcp_generate_summary (void) 4523{ 4524 struct cgraph_node *node; 4525 4526 if (dump_file) 4527 fprintf (dump_file, "\nIPA constant propagation start:\n"); 4528 ipa_register_cgraph_hooks (); 4529 4530 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) 4531 { 4532 node->local.versionable 4533 = tree_versionable_function_p (node->decl); 4534 ipa_analyze_node (node); 4535 } 4536} 4537 4538/* Write ipcp summary for nodes in SET. */ 4539 4540static void 4541ipcp_write_summary (void) 4542{ 4543 ipa_prop_write_jump_functions (); 4544} 4545 4546/* Read ipcp summary. */ 4547 4548static void 4549ipcp_read_summary (void) 4550{ 4551 ipa_prop_read_jump_functions (); 4552} 4553 4554namespace { 4555 4556const pass_data pass_data_ipa_cp = 4557{ 4558 IPA_PASS, /* type */ 4559 "cp", /* name */ 4560 OPTGROUP_NONE, /* optinfo_flags */ 4561 TV_IPA_CONSTANT_PROP, /* tv_id */ 4562 0, /* properties_required */ 4563 0, /* properties_provided */ 4564 0, /* properties_destroyed */ 4565 0, /* todo_flags_start */ 4566 ( TODO_dump_symtab | TODO_remove_functions ), /* todo_flags_finish */ 4567}; 4568 4569class pass_ipa_cp : public ipa_opt_pass_d 4570{ 4571public: 4572 pass_ipa_cp (gcc::context *ctxt) 4573 : ipa_opt_pass_d (pass_data_ipa_cp, ctxt, 4574 ipcp_generate_summary, /* generate_summary */ 4575 ipcp_write_summary, /* write_summary */ 4576 ipcp_read_summary, /* read_summary */ 4577 ipcp_write_transformation_summaries, /* 4578 write_optimization_summary */ 4579 ipcp_read_transformation_summaries, /* 4580 read_optimization_summary */ 4581 NULL, /* stmt_fixup */ 4582 0, /* function_transform_todo_flags_start */ 4583 ipcp_transform_function, /* function_transform */ 4584 NULL) /* variable_transform */ 4585 {} 4586 4587 /* opt_pass methods: */ 4588 virtual bool gate (function *) 4589 { 4590 /* FIXME: We should remove the optimize check after we ensure we never run 4591 IPA passes when not optimizing. */ 4592 return (flag_ipa_cp && optimize) || in_lto_p; 4593 } 4594 4595 virtual unsigned int execute (function *) { return ipcp_driver (); } 4596 4597}; // class pass_ipa_cp 4598 4599} // anon namespace 4600 4601ipa_opt_pass_d * 4602make_pass_ipa_cp (gcc::context *ctxt) 4603{ 4604 return new pass_ipa_cp (ctxt); 4605} 4606 4607/* Reset all state within ipa-cp.c so that we can rerun the compiler 4608 within the same process. For use by toplev::finalize. */ 4609 4610void 4611ipa_cp_c_finalize (void) 4612{ 4613 max_count = 0; 4614 overall_size = 0; 4615 max_new_size = 0; 4616} 4617