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