1 /* Interprocedural Identical Code Folding pass 2 Copyright (C) 2014-2018 Free Software Foundation, Inc. 3 4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz> 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free 10 Software Foundation; either version 3, or (at your option) any later 11 version. 12 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16 for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 /* Interprocedural Identical Code Folding for functions and 23 read-only variables. 24 25 The goal of this transformation is to discover functions and read-only 26 variables which do have exactly the same semantics. 27 28 In case of functions, 29 we could either create a virtual clone or do a simple function wrapper 30 that will call equivalent function. If the function is just locally visible, 31 all function calls can be redirected. For read-only variables, we create 32 aliases if possible. 33 34 Optimization pass arranges as follows: 35 1) All functions and read-only variables are visited and internal 36 data structure, either sem_function or sem_variables is created. 37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are 38 saved and matched to corresponding sem_items. 39 3) These declaration are ignored for equality check and are solved 40 by Value Numbering algorithm published by Alpert, Zadeck in 1992. 41 4) We compute hash value for each symbol. 42 5) Congruence classes are created based on hash value. If hash value are 43 equal, equals function is called and symbols are deeply compared. 44 We must prove that all SSA names, declarations and other items 45 correspond. 46 6) Value Numbering is executed for these classes. At the end of the process 47 all symbol members in remaining classes can be merged. 48 7) Merge operation creates alias in case of read-only variables. For 49 callgraph node, we must decide if we can redirect local calls, 50 create an alias or a thunk. 51 52 */ 53 54 #include "config.h" 55 #define INCLUDE_LIST 56 #include "system.h" 57 #include "coretypes.h" 58 #include "backend.h" 59 #include "target.h" 60 #include "rtl.h" 61 #include "tree.h" 62 #include "gimple.h" 63 #include "alloc-pool.h" 64 #include "tree-pass.h" 65 #include "ssa.h" 66 #include "cgraph.h" 67 #include "coverage.h" 68 #include "gimple-pretty-print.h" 69 #include "data-streamer.h" 70 #include "fold-const.h" 71 #include "calls.h" 72 #include "varasm.h" 73 #include "gimple-iterator.h" 74 #include "tree-cfg.h" 75 #include "symbol-summary.h" 76 #include "ipa-prop.h" 77 #include "ipa-fnsummary.h" 78 #include "except.h" 79 #include "attribs.h" 80 #include "print-tree.h" 81 #include "ipa-utils.h" 82 #include "ipa-icf-gimple.h" 83 #include "ipa-icf.h" 84 #include "stor-layout.h" 85 #include "dbgcnt.h" 86 #include "tree-vector-builder.h" 87 88 using namespace ipa_icf_gimple; 89 90 namespace ipa_icf { 91 92 /* Initialization and computation of symtab node hash, there data 93 are propagated later on. */ 94 95 static sem_item_optimizer *optimizer = NULL; 96 97 /* Constructor. */ 98 99 symbol_compare_collection::symbol_compare_collection (symtab_node *node) 100 { 101 m_references.create (0); 102 m_interposables.create (0); 103 104 ipa_ref *ref; 105 106 if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl)) 107 return; 108 109 for (unsigned i = 0; node->iterate_reference (i, ref); i++) 110 { 111 if (ref->address_matters_p ()) 112 m_references.safe_push (ref->referred); 113 114 if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE) 115 { 116 if (ref->address_matters_p ()) 117 m_references.safe_push (ref->referred); 118 else 119 m_interposables.safe_push (ref->referred); 120 } 121 } 122 123 if (is_a <cgraph_node *> (node)) 124 { 125 cgraph_node *cnode = dyn_cast <cgraph_node *> (node); 126 127 for (cgraph_edge *e = cnode->callees; e; e = e->next_callee) 128 if (e->callee->get_availability () <= AVAIL_INTERPOSABLE) 129 m_interposables.safe_push (e->callee); 130 } 131 } 132 133 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */ 134 135 sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index) 136 : item (_item), index (_index) 137 { 138 } 139 140 sem_item::sem_item (sem_item_type _type, bitmap_obstack *stack) 141 : type (_type), m_hash (-1), m_hash_set (false) 142 { 143 setup (stack); 144 } 145 146 sem_item::sem_item (sem_item_type _type, symtab_node *_node, 147 bitmap_obstack *stack) 148 : type (_type), node (_node), m_hash (-1), m_hash_set (false) 149 { 150 decl = node->decl; 151 setup (stack); 152 } 153 154 /* Add reference to a semantic TARGET. */ 155 156 void 157 sem_item::add_reference (sem_item *target) 158 { 159 refs.safe_push (target); 160 unsigned index = refs.length (); 161 target->usages.safe_push (new sem_usage_pair(this, index)); 162 bitmap_set_bit (target->usage_index_bitmap, index); 163 refs_set.add (target->node); 164 } 165 166 /* Initialize internal data structures. Bitmap STACK is used for 167 bitmap memory allocation process. */ 168 169 void 170 sem_item::setup (bitmap_obstack *stack) 171 { 172 gcc_checking_assert (node); 173 174 refs.create (0); 175 tree_refs.create (0); 176 usages.create (0); 177 usage_index_bitmap = BITMAP_ALLOC (stack); 178 } 179 180 sem_item::~sem_item () 181 { 182 for (unsigned i = 0; i < usages.length (); i++) 183 delete usages[i]; 184 185 refs.release (); 186 tree_refs.release (); 187 usages.release (); 188 189 BITMAP_FREE (usage_index_bitmap); 190 } 191 192 /* Dump function for debugging purpose. */ 193 194 DEBUG_FUNCTION void 195 sem_item::dump (void) 196 { 197 if (dump_file) 198 { 199 fprintf (dump_file, "[%s] %s (tree:%p)\n", type == FUNC ? "func" : "var", 200 node->dump_name (), (void *) node->decl); 201 fprintf (dump_file, " hash: %u\n", get_hash ()); 202 fprintf (dump_file, " references: "); 203 204 for (unsigned i = 0; i < refs.length (); i++) 205 fprintf (dump_file, "%s%s ", refs[i]->node->name (), 206 i < refs.length() - 1 ? "," : ""); 207 208 fprintf (dump_file, "\n"); 209 } 210 } 211 212 /* Return true if target supports alias symbols. */ 213 214 bool 215 sem_item::target_supports_symbol_aliases_p (void) 216 { 217 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL)) 218 return false; 219 #else 220 return true; 221 #endif 222 } 223 224 void sem_item::set_hash (hashval_t hash) 225 { 226 m_hash = hash; 227 m_hash_set = true; 228 } 229 230 /* Semantic function constructor that uses STACK as bitmap memory stack. */ 231 232 sem_function::sem_function (bitmap_obstack *stack) 233 : sem_item (FUNC, stack), m_checker (NULL), m_compared_func (NULL) 234 { 235 bb_sizes.create (0); 236 bb_sorted.create (0); 237 } 238 239 sem_function::sem_function (cgraph_node *node, bitmap_obstack *stack) 240 : sem_item (FUNC, node, stack), m_checker (NULL), m_compared_func (NULL) 241 { 242 bb_sizes.create (0); 243 bb_sorted.create (0); 244 } 245 246 sem_function::~sem_function () 247 { 248 for (unsigned i = 0; i < bb_sorted.length (); i++) 249 delete (bb_sorted[i]); 250 251 bb_sizes.release (); 252 bb_sorted.release (); 253 } 254 255 /* Calculates hash value based on a BASIC_BLOCK. */ 256 257 hashval_t 258 sem_function::get_bb_hash (const sem_bb *basic_block) 259 { 260 inchash::hash hstate; 261 262 hstate.add_int (basic_block->nondbg_stmt_count); 263 hstate.add_int (basic_block->edge_count); 264 265 return hstate.end (); 266 } 267 268 /* References independent hash function. */ 269 270 hashval_t 271 sem_function::get_hash (void) 272 { 273 if (!m_hash_set) 274 { 275 inchash::hash hstate; 276 hstate.add_int (177454); /* Random number for function type. */ 277 278 hstate.add_int (arg_count); 279 hstate.add_int (cfg_checksum); 280 hstate.add_int (gcode_hash); 281 282 for (unsigned i = 0; i < bb_sorted.length (); i++) 283 hstate.merge_hash (get_bb_hash (bb_sorted[i])); 284 285 for (unsigned i = 0; i < bb_sizes.length (); i++) 286 hstate.add_int (bb_sizes[i]); 287 288 /* Add common features of declaration itself. */ 289 if (DECL_FUNCTION_SPECIFIC_TARGET (decl)) 290 hstate.add_hwi 291 (cl_target_option_hash 292 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl)))); 293 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl)) 294 hstate.add_hwi 295 (cl_optimization_hash 296 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl)))); 297 hstate.add_flag (DECL_CXX_CONSTRUCTOR_P (decl)); 298 hstate.add_flag (DECL_CXX_DESTRUCTOR_P (decl)); 299 300 set_hash (hstate.end ()); 301 } 302 303 return m_hash; 304 } 305 306 /* Return ture if A1 and A2 represent equivalent function attribute lists. 307 Based on comp_type_attributes. */ 308 309 bool 310 sem_item::compare_attributes (const_tree a1, const_tree a2) 311 { 312 const_tree a; 313 if (a1 == a2) 314 return true; 315 for (a = a1; a != NULL_TREE; a = TREE_CHAIN (a)) 316 { 317 const struct attribute_spec *as; 318 const_tree attr; 319 320 as = lookup_attribute_spec (get_attribute_name (a)); 321 /* TODO: We can introduce as->affects_decl_identity 322 and as->affects_decl_reference_identity if attribute mismatch 323 gets a common reason to give up on merging. It may not be worth 324 the effort. 325 For example returns_nonnull affects only references, while 326 optimize attribute can be ignored because it is already lowered 327 into flags representation and compared separately. */ 328 if (!as) 329 continue; 330 331 attr = lookup_attribute (as->name, CONST_CAST_TREE (a2)); 332 if (!attr || !attribute_value_equal (a, attr)) 333 break; 334 } 335 if (!a) 336 { 337 for (a = a2; a != NULL_TREE; a = TREE_CHAIN (a)) 338 { 339 const struct attribute_spec *as; 340 341 as = lookup_attribute_spec (get_attribute_name (a)); 342 if (!as) 343 continue; 344 345 if (!lookup_attribute (as->name, CONST_CAST_TREE (a1))) 346 break; 347 /* We don't need to compare trees again, as we did this 348 already in first loop. */ 349 } 350 if (!a) 351 return true; 352 } 353 /* TODO: As in comp_type_attributes we may want to introduce target hook. */ 354 return false; 355 } 356 357 /* Compare properties of symbols N1 and N2 that does not affect semantics of 358 symbol itself but affects semantics of its references from USED_BY (which 359 may be NULL if it is unknown). If comparsion is false, symbols 360 can still be merged but any symbols referring them can't. 361 362 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR. 363 364 TODO: We can also split attributes to those that determine codegen of 365 a function body/variable constructor itself and those that are used when 366 referring to it. */ 367 368 bool 369 sem_item::compare_referenced_symbol_properties (symtab_node *used_by, 370 symtab_node *n1, 371 symtab_node *n2, 372 bool address) 373 { 374 if (is_a <cgraph_node *> (n1)) 375 { 376 /* Inline properties matters: we do now want to merge uses of inline 377 function to uses of normal function because inline hint would be lost. 378 We however can merge inline function to noinline because the alias 379 will keep its DECL_DECLARED_INLINE flag. 380 381 Also ignore inline flag when optimizing for size or when function 382 is known to not be inlinable. 383 384 TODO: the optimize_size checks can also be assumed to be true if 385 unit has no !optimize_size functions. */ 386 387 if ((!used_by || address || !is_a <cgraph_node *> (used_by) 388 || !opt_for_fn (used_by->decl, optimize_size)) 389 && !opt_for_fn (n1->decl, optimize_size) 390 && n1->get_availability () > AVAIL_INTERPOSABLE 391 && (!DECL_UNINLINABLE (n1->decl) || !DECL_UNINLINABLE (n2->decl))) 392 { 393 if (DECL_DISREGARD_INLINE_LIMITS (n1->decl) 394 != DECL_DISREGARD_INLINE_LIMITS (n2->decl)) 395 return return_false_with_msg 396 ("DECL_DISREGARD_INLINE_LIMITS are different"); 397 398 if (DECL_DECLARED_INLINE_P (n1->decl) 399 != DECL_DECLARED_INLINE_P (n2->decl)) 400 return return_false_with_msg ("inline attributes are different"); 401 } 402 403 if (DECL_IS_OPERATOR_NEW (n1->decl) 404 != DECL_IS_OPERATOR_NEW (n2->decl)) 405 return return_false_with_msg ("operator new flags are different"); 406 } 407 408 /* Merging two definitions with a reference to equivalent vtables, but 409 belonging to a different type may result in ipa-polymorphic-call analysis 410 giving a wrong answer about the dynamic type of instance. */ 411 if (is_a <varpool_node *> (n1)) 412 { 413 if ((DECL_VIRTUAL_P (n1->decl) || DECL_VIRTUAL_P (n2->decl)) 414 && (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl) 415 || !types_must_be_same_for_odr (DECL_CONTEXT (n1->decl), 416 DECL_CONTEXT (n2->decl))) 417 && (!used_by || !is_a <cgraph_node *> (used_by) || address 418 || opt_for_fn (used_by->decl, flag_devirtualize))) 419 return return_false_with_msg 420 ("references to virtual tables can not be merged"); 421 422 if (address && DECL_ALIGN (n1->decl) != DECL_ALIGN (n2->decl)) 423 return return_false_with_msg ("alignment mismatch"); 424 425 /* For functions we compare attributes in equals_wpa, because we do 426 not know what attributes may cause codegen differences, but for 427 variables just compare attributes for references - the codegen 428 for constructors is affected only by those attributes that we lower 429 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */ 430 if (!compare_attributes (DECL_ATTRIBUTES (n1->decl), 431 DECL_ATTRIBUTES (n2->decl))) 432 return return_false_with_msg ("different var decl attributes"); 433 if (comp_type_attributes (TREE_TYPE (n1->decl), 434 TREE_TYPE (n2->decl)) != 1) 435 return return_false_with_msg ("different var type attributes"); 436 } 437 438 /* When matching virtual tables, be sure to also match information 439 relevant for polymorphic call analysis. */ 440 if (used_by && is_a <varpool_node *> (used_by) 441 && DECL_VIRTUAL_P (used_by->decl)) 442 { 443 if (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl)) 444 return return_false_with_msg ("virtual flag mismatch"); 445 if (DECL_VIRTUAL_P (n1->decl) && is_a <cgraph_node *> (n1) 446 && (DECL_FINAL_P (n1->decl) != DECL_FINAL_P (n2->decl))) 447 return return_false_with_msg ("final flag mismatch"); 448 } 449 return true; 450 } 451 452 /* Hash properties that are compared by compare_referenced_symbol_properties. */ 453 454 void 455 sem_item::hash_referenced_symbol_properties (symtab_node *ref, 456 inchash::hash &hstate, 457 bool address) 458 { 459 if (is_a <cgraph_node *> (ref)) 460 { 461 if ((type != FUNC || address || !opt_for_fn (decl, optimize_size)) 462 && !opt_for_fn (ref->decl, optimize_size) 463 && !DECL_UNINLINABLE (ref->decl)) 464 { 465 hstate.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref->decl)); 466 hstate.add_flag (DECL_DECLARED_INLINE_P (ref->decl)); 467 } 468 hstate.add_flag (DECL_IS_OPERATOR_NEW (ref->decl)); 469 } 470 else if (is_a <varpool_node *> (ref)) 471 { 472 hstate.add_flag (DECL_VIRTUAL_P (ref->decl)); 473 if (address) 474 hstate.add_int (DECL_ALIGN (ref->decl)); 475 } 476 } 477 478 479 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs 480 point to a same function. Comparison can be skipped if IGNORED_NODES 481 contains these nodes. ADDRESS indicate if address is taken. */ 482 483 bool 484 sem_item::compare_symbol_references ( 485 hash_map <symtab_node *, sem_item *> &ignored_nodes, 486 symtab_node *n1, symtab_node *n2, bool address) 487 { 488 enum availability avail1, avail2; 489 490 if (n1 == n2) 491 return true; 492 493 /* Never match variable and function. */ 494 if (is_a <varpool_node *> (n1) != is_a <varpool_node *> (n2)) 495 return false; 496 497 if (!compare_referenced_symbol_properties (node, n1, n2, address)) 498 return false; 499 if (address && n1->equal_address_to (n2) == 1) 500 return true; 501 if (!address && n1->semantically_equivalent_p (n2)) 502 return true; 503 504 n1 = n1->ultimate_alias_target (&avail1); 505 n2 = n2->ultimate_alias_target (&avail2); 506 507 if (avail1 > AVAIL_INTERPOSABLE && ignored_nodes.get (n1) 508 && avail2 > AVAIL_INTERPOSABLE && ignored_nodes.get (n2)) 509 return true; 510 511 return return_false_with_msg ("different references"); 512 } 513 514 /* If cgraph edges E1 and E2 are indirect calls, verify that 515 ECF flags are the same. */ 516 517 bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2) 518 { 519 if (e1->indirect_info && e2->indirect_info) 520 { 521 int e1_flags = e1->indirect_info->ecf_flags; 522 int e2_flags = e2->indirect_info->ecf_flags; 523 524 if (e1_flags != e2_flags) 525 return return_false_with_msg ("ICF flags are different"); 526 } 527 else if (e1->indirect_info || e2->indirect_info) 528 return false; 529 530 return true; 531 } 532 533 /* Return true if parameter I may be used. */ 534 535 bool 536 sem_function::param_used_p (unsigned int i) 537 { 538 if (ipa_node_params_sum == NULL) 539 return true; 540 541 struct ipa_node_params *parms_info = IPA_NODE_REF (get_node ()); 542 543 if (vec_safe_length (parms_info->descriptors) <= i) 544 return true; 545 546 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i); 547 } 548 549 /* Perform additional check needed to match types function parameters that are 550 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we 551 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */ 552 553 bool 554 sem_function::compatible_parm_types_p (tree parm1, tree parm2) 555 { 556 /* Be sure that parameters are TBAA compatible. */ 557 if (!func_checker::compatible_types_p (parm1, parm2)) 558 return return_false_with_msg ("parameter type is not compatible"); 559 560 if (POINTER_TYPE_P (parm1) 561 && (TYPE_RESTRICT (parm1) != TYPE_RESTRICT (parm2))) 562 return return_false_with_msg ("argument restrict flag mismatch"); 563 564 /* nonnull_arg_p implies non-zero range to REFERENCE types. */ 565 if (POINTER_TYPE_P (parm1) 566 && TREE_CODE (parm1) != TREE_CODE (parm2) 567 && opt_for_fn (decl, flag_delete_null_pointer_checks)) 568 return return_false_with_msg ("pointer wrt reference mismatch"); 569 570 return true; 571 } 572 573 /* Fast equality function based on knowledge known in WPA. */ 574 575 bool 576 sem_function::equals_wpa (sem_item *item, 577 hash_map <symtab_node *, sem_item *> &ignored_nodes) 578 { 579 gcc_assert (item->type == FUNC); 580 cgraph_node *cnode = dyn_cast <cgraph_node *> (node); 581 cgraph_node *cnode2 = dyn_cast <cgraph_node *> (item->node); 582 583 m_compared_func = static_cast<sem_function *> (item); 584 585 if (cnode->thunk.thunk_p != cnode2->thunk.thunk_p) 586 return return_false_with_msg ("thunk_p mismatch"); 587 588 if (cnode->thunk.thunk_p) 589 { 590 if (cnode->thunk.fixed_offset != cnode2->thunk.fixed_offset) 591 return return_false_with_msg ("thunk fixed_offset mismatch"); 592 if (cnode->thunk.virtual_value != cnode2->thunk.virtual_value) 593 return return_false_with_msg ("thunk virtual_value mismatch"); 594 if (cnode->thunk.this_adjusting != cnode2->thunk.this_adjusting) 595 return return_false_with_msg ("thunk this_adjusting mismatch"); 596 if (cnode->thunk.virtual_offset_p != cnode2->thunk.virtual_offset_p) 597 return return_false_with_msg ("thunk virtual_offset_p mismatch"); 598 if (cnode->thunk.add_pointer_bounds_args 599 != cnode2->thunk.add_pointer_bounds_args) 600 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch"); 601 } 602 603 /* Compare special function DECL attributes. */ 604 if (DECL_FUNCTION_PERSONALITY (decl) 605 != DECL_FUNCTION_PERSONALITY (item->decl)) 606 return return_false_with_msg ("function personalities are different"); 607 608 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) 609 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item->decl)) 610 return return_false_with_msg ("intrument function entry exit " 611 "attributes are different"); 612 613 if (DECL_NO_LIMIT_STACK (decl) != DECL_NO_LIMIT_STACK (item->decl)) 614 return return_false_with_msg ("no stack limit attributes are different"); 615 616 if (DECL_CXX_CONSTRUCTOR_P (decl) != DECL_CXX_CONSTRUCTOR_P (item->decl)) 617 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch"); 618 619 if (DECL_CXX_DESTRUCTOR_P (decl) != DECL_CXX_DESTRUCTOR_P (item->decl)) 620 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch"); 621 622 /* TODO: pure/const flags mostly matters only for references, except for 623 the fact that codegen takes LOOPING flag as a hint that loops are 624 finite. We may arrange the code to always pick leader that has least 625 specified flags and then this can go into comparing symbol properties. */ 626 if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl)) 627 return return_false_with_msg ("decl_or_type flags are different"); 628 629 /* Do not match polymorphic constructors of different types. They calls 630 type memory location for ipa-polymorphic-call and we do not want 631 it to get confused by wrong type. */ 632 if (DECL_CXX_CONSTRUCTOR_P (decl) 633 && TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE) 634 { 635 if (TREE_CODE (TREE_TYPE (item->decl)) != METHOD_TYPE) 636 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch"); 637 else if (!func_checker::compatible_polymorphic_types_p 638 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)), 639 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false)) 640 return return_false_with_msg ("ctor polymorphic type mismatch"); 641 } 642 643 /* Checking function TARGET and OPTIMIZATION flags. */ 644 cl_target_option *tar1 = target_opts_for_fn (decl); 645 cl_target_option *tar2 = target_opts_for_fn (item->decl); 646 647 if (tar1 != tar2 && !cl_target_option_eq (tar1, tar2)) 648 { 649 if (dump_file && (dump_flags & TDF_DETAILS)) 650 { 651 fprintf (dump_file, "target flags difference"); 652 cl_target_option_print_diff (dump_file, 2, tar1, tar2); 653 } 654 655 return return_false_with_msg ("Target flags are different"); 656 } 657 658 cl_optimization *opt1 = opts_for_fn (decl); 659 cl_optimization *opt2 = opts_for_fn (item->decl); 660 661 if (opt1 != opt2 && memcmp (opt1, opt2, sizeof(cl_optimization))) 662 { 663 if (dump_file && (dump_flags & TDF_DETAILS)) 664 { 665 fprintf (dump_file, "optimization flags difference"); 666 cl_optimization_print_diff (dump_file, 2, opt1, opt2); 667 } 668 669 return return_false_with_msg ("optimization flags are different"); 670 } 671 672 /* Result type checking. */ 673 if (!func_checker::compatible_types_p 674 (TREE_TYPE (TREE_TYPE (decl)), 675 TREE_TYPE (TREE_TYPE (m_compared_func->decl)))) 676 return return_false_with_msg ("result types are different"); 677 678 /* Checking types of arguments. */ 679 tree list1 = TYPE_ARG_TYPES (TREE_TYPE (decl)), 680 list2 = TYPE_ARG_TYPES (TREE_TYPE (m_compared_func->decl)); 681 for (unsigned i = 0; list1 && list2; 682 list1 = TREE_CHAIN (list1), list2 = TREE_CHAIN (list2), i++) 683 { 684 tree parm1 = TREE_VALUE (list1); 685 tree parm2 = TREE_VALUE (list2); 686 687 /* This guard is here for function pointer with attributes (pr59927.c). */ 688 if (!parm1 || !parm2) 689 return return_false_with_msg ("NULL argument type"); 690 691 /* Verify that types are compatible to ensure that both functions 692 have same calling conventions. */ 693 if (!types_compatible_p (parm1, parm2)) 694 return return_false_with_msg ("parameter types are not compatible"); 695 696 if (!param_used_p (i)) 697 continue; 698 699 /* Perform additional checks for used parameters. */ 700 if (!compatible_parm_types_p (parm1, parm2)) 701 return false; 702 } 703 704 if (list1 || list2) 705 return return_false_with_msg ("Mismatched number of parameters"); 706 707 if (node->num_references () != item->node->num_references ()) 708 return return_false_with_msg ("different number of references"); 709 710 /* Checking function attributes. 711 This is quadratic in number of attributes */ 712 if (comp_type_attributes (TREE_TYPE (decl), 713 TREE_TYPE (item->decl)) != 1) 714 return return_false_with_msg ("different type attributes"); 715 if (!compare_attributes (DECL_ATTRIBUTES (decl), 716 DECL_ATTRIBUTES (item->decl))) 717 return return_false_with_msg ("different decl attributes"); 718 719 /* The type of THIS pointer type memory location for 720 ipa-polymorphic-call-analysis. */ 721 if (opt_for_fn (decl, flag_devirtualize) 722 && (TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE 723 || TREE_CODE (TREE_TYPE (item->decl)) == METHOD_TYPE) 724 && param_used_p (0) 725 && compare_polymorphic_p ()) 726 { 727 if (TREE_CODE (TREE_TYPE (decl)) != TREE_CODE (TREE_TYPE (item->decl))) 728 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch"); 729 if (!func_checker::compatible_polymorphic_types_p 730 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)), 731 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false)) 732 return return_false_with_msg ("THIS pointer ODR type mismatch"); 733 } 734 735 ipa_ref *ref = NULL, *ref2 = NULL; 736 for (unsigned i = 0; node->iterate_reference (i, ref); i++) 737 { 738 item->node->iterate_reference (i, ref2); 739 740 if (ref->use != ref2->use) 741 return return_false_with_msg ("reference use mismatch"); 742 743 if (!compare_symbol_references (ignored_nodes, ref->referred, 744 ref2->referred, 745 ref->address_matters_p ())) 746 return false; 747 } 748 749 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees; 750 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees; 751 752 while (e1 && e2) 753 { 754 if (!compare_symbol_references (ignored_nodes, e1->callee, 755 e2->callee, false)) 756 return false; 757 if (!compare_edge_flags (e1, e2)) 758 return false; 759 760 e1 = e1->next_callee; 761 e2 = e2->next_callee; 762 } 763 764 if (e1 || e2) 765 return return_false_with_msg ("different number of calls"); 766 767 e1 = dyn_cast <cgraph_node *> (node)->indirect_calls; 768 e2 = dyn_cast <cgraph_node *> (item->node)->indirect_calls; 769 770 while (e1 && e2) 771 { 772 if (!compare_edge_flags (e1, e2)) 773 return false; 774 775 e1 = e1->next_callee; 776 e2 = e2->next_callee; 777 } 778 779 if (e1 || e2) 780 return return_false_with_msg ("different number of indirect calls"); 781 782 return true; 783 } 784 785 /* Update hash by address sensitive references. We iterate over all 786 sensitive references (address_matters_p) and we hash ultime alias 787 target of these nodes, which can improve a semantic item hash. 788 789 Also hash in referenced symbols properties. This can be done at any time 790 (as the properties should not change), but it is convenient to do it here 791 while we walk the references anyway. */ 792 793 void 794 sem_item::update_hash_by_addr_refs (hash_map <symtab_node *, 795 sem_item *> &m_symtab_node_map) 796 { 797 ipa_ref* ref; 798 inchash::hash hstate (get_hash ()); 799 800 for (unsigned i = 0; node->iterate_reference (i, ref); i++) 801 { 802 hstate.add_int (ref->use); 803 hash_referenced_symbol_properties (ref->referred, hstate, 804 ref->use == IPA_REF_ADDR); 805 if (ref->address_matters_p () || !m_symtab_node_map.get (ref->referred)) 806 hstate.add_int (ref->referred->ultimate_alias_target ()->order); 807 } 808 809 if (is_a <cgraph_node *> (node)) 810 { 811 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e; 812 e = e->next_caller) 813 { 814 sem_item **result = m_symtab_node_map.get (e->callee); 815 hash_referenced_symbol_properties (e->callee, hstate, false); 816 if (!result) 817 hstate.add_int (e->callee->ultimate_alias_target ()->order); 818 } 819 } 820 821 set_hash (hstate.end ()); 822 } 823 824 /* Update hash by computed local hash values taken from different 825 semantic items. 826 TODO: stronger SCC based hashing would be desirable here. */ 827 828 void 829 sem_item::update_hash_by_local_refs (hash_map <symtab_node *, 830 sem_item *> &m_symtab_node_map) 831 { 832 ipa_ref* ref; 833 inchash::hash state (get_hash ()); 834 835 for (unsigned j = 0; node->iterate_reference (j, ref); j++) 836 { 837 sem_item **result = m_symtab_node_map.get (ref->referring); 838 if (result) 839 state.merge_hash ((*result)->get_hash ()); 840 } 841 842 if (type == FUNC) 843 { 844 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e; 845 e = e->next_callee) 846 { 847 sem_item **result = m_symtab_node_map.get (e->caller); 848 if (result) 849 state.merge_hash ((*result)->get_hash ()); 850 } 851 } 852 853 global_hash = state.end (); 854 } 855 856 /* Returns true if the item equals to ITEM given as argument. */ 857 858 bool 859 sem_function::equals (sem_item *item, 860 hash_map <symtab_node *, sem_item *> &) 861 { 862 gcc_assert (item->type == FUNC); 863 bool eq = equals_private (item); 864 865 if (m_checker != NULL) 866 { 867 delete m_checker; 868 m_checker = NULL; 869 } 870 871 if (dump_file && (dump_flags & TDF_DETAILS)) 872 fprintf (dump_file, 873 "Equals called for: %s:%s with result: %s\n\n", 874 node->dump_name (), 875 item->node->dump_name (), 876 eq ? "true" : "false"); 877 878 return eq; 879 } 880 881 /* Processes function equality comparison. */ 882 883 bool 884 sem_function::equals_private (sem_item *item) 885 { 886 if (item->type != FUNC) 887 return false; 888 889 basic_block bb1, bb2; 890 edge e1, e2; 891 edge_iterator ei1, ei2; 892 bool result = true; 893 tree arg1, arg2; 894 895 m_compared_func = static_cast<sem_function *> (item); 896 897 gcc_assert (decl != item->decl); 898 899 if (bb_sorted.length () != m_compared_func->bb_sorted.length () 900 || edge_count != m_compared_func->edge_count 901 || cfg_checksum != m_compared_func->cfg_checksum) 902 return return_false (); 903 904 m_checker = new func_checker (decl, m_compared_func->decl, 905 compare_polymorphic_p (), 906 false, 907 &refs_set, 908 &m_compared_func->refs_set); 909 arg1 = DECL_ARGUMENTS (decl); 910 arg2 = DECL_ARGUMENTS (m_compared_func->decl); 911 for (unsigned i = 0; 912 arg1 && arg2; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2), i++) 913 { 914 if (!types_compatible_p (TREE_TYPE (arg1), TREE_TYPE (arg2))) 915 return return_false_with_msg ("argument types are not compatible"); 916 if (!param_used_p (i)) 917 continue; 918 /* Perform additional checks for used parameters. */ 919 if (!compatible_parm_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2))) 920 return false; 921 if (!m_checker->compare_decl (arg1, arg2)) 922 return return_false (); 923 } 924 if (arg1 || arg2) 925 return return_false_with_msg ("Mismatched number of arguments"); 926 927 if (!dyn_cast <cgraph_node *> (node)->has_gimple_body_p ()) 928 return true; 929 930 /* Fill-up label dictionary. */ 931 for (unsigned i = 0; i < bb_sorted.length (); ++i) 932 { 933 m_checker->parse_labels (bb_sorted[i]); 934 m_checker->parse_labels (m_compared_func->bb_sorted[i]); 935 } 936 937 /* Checking all basic blocks. */ 938 for (unsigned i = 0; i < bb_sorted.length (); ++i) 939 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i])) 940 return return_false(); 941 942 dump_message ("All BBs are equal\n"); 943 944 auto_vec <int> bb_dict; 945 946 /* Basic block edges check. */ 947 for (unsigned i = 0; i < bb_sorted.length (); ++i) 948 { 949 bb1 = bb_sorted[i]->bb; 950 bb2 = m_compared_func->bb_sorted[i]->bb; 951 952 ei2 = ei_start (bb2->preds); 953 954 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1)) 955 { 956 ei_cond (ei2, &e2); 957 958 if (e1->flags != e2->flags) 959 return return_false_with_msg ("flags comparison returns false"); 960 961 if (!bb_dict_test (&bb_dict, e1->src->index, e2->src->index)) 962 return return_false_with_msg ("edge comparison returns false"); 963 964 if (!bb_dict_test (&bb_dict, e1->dest->index, e2->dest->index)) 965 return return_false_with_msg ("BB comparison returns false"); 966 967 if (!m_checker->compare_edge (e1, e2)) 968 return return_false_with_msg ("edge comparison returns false"); 969 970 ei_next (&ei2); 971 } 972 } 973 974 /* Basic block PHI nodes comparison. */ 975 for (unsigned i = 0; i < bb_sorted.length (); i++) 976 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb)) 977 return return_false_with_msg ("PHI node comparison returns false"); 978 979 return result; 980 } 981 982 /* Set LOCAL_P of NODE to true if DATA is non-NULL. 983 Helper for call_for_symbol_thunks_and_aliases. */ 984 985 static bool 986 set_local (cgraph_node *node, void *data) 987 { 988 node->local.local = data != NULL; 989 return false; 990 } 991 992 /* TREE_ADDRESSABLE of NODE to true. 993 Helper for call_for_symbol_thunks_and_aliases. */ 994 995 static bool 996 set_addressable (varpool_node *node, void *) 997 { 998 TREE_ADDRESSABLE (node->decl) = 1; 999 return false; 1000 } 1001 1002 /* Clear DECL_RTL of NODE. 1003 Helper for call_for_symbol_thunks_and_aliases. */ 1004 1005 static bool 1006 clear_decl_rtl (symtab_node *node, void *) 1007 { 1008 SET_DECL_RTL (node->decl, NULL); 1009 return false; 1010 } 1011 1012 /* Redirect all callers of N and its aliases to TO. Remove aliases if 1013 possible. Return number of redirections made. */ 1014 1015 static int 1016 redirect_all_callers (cgraph_node *n, cgraph_node *to) 1017 { 1018 int nredirected = 0; 1019 ipa_ref *ref; 1020 cgraph_edge *e = n->callers; 1021 1022 while (e) 1023 { 1024 /* Redirecting thunks to interposable symbols or symbols in other sections 1025 may not be supported by target output code. Play safe for now and 1026 punt on redirection. */ 1027 if (!e->caller->thunk.thunk_p) 1028 { 1029 struct cgraph_edge *nexte = e->next_caller; 1030 e->redirect_callee (to); 1031 e = nexte; 1032 nredirected++; 1033 } 1034 else 1035 e = e->next_callee; 1036 } 1037 for (unsigned i = 0; n->iterate_direct_aliases (i, ref);) 1038 { 1039 bool removed = false; 1040 cgraph_node *n_alias = dyn_cast <cgraph_node *> (ref->referring); 1041 1042 if ((DECL_COMDAT_GROUP (n->decl) 1043 && (DECL_COMDAT_GROUP (n->decl) 1044 == DECL_COMDAT_GROUP (n_alias->decl))) 1045 || (n_alias->get_availability () > AVAIL_INTERPOSABLE 1046 && n->get_availability () > AVAIL_INTERPOSABLE)) 1047 { 1048 nredirected += redirect_all_callers (n_alias, to); 1049 if (n_alias->can_remove_if_no_direct_calls_p () 1050 && !n_alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p, 1051 NULL, true) 1052 && !n_alias->has_aliases_p ()) 1053 n_alias->remove (); 1054 } 1055 if (!removed) 1056 i++; 1057 } 1058 return nredirected; 1059 } 1060 1061 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can 1062 be applied. */ 1063 1064 bool 1065 sem_function::merge (sem_item *alias_item) 1066 { 1067 gcc_assert (alias_item->type == FUNC); 1068 1069 sem_function *alias_func = static_cast<sem_function *> (alias_item); 1070 1071 cgraph_node *original = get_node (); 1072 cgraph_node *local_original = NULL; 1073 cgraph_node *alias = alias_func->get_node (); 1074 1075 bool create_wrapper = false; 1076 bool create_alias = false; 1077 bool redirect_callers = false; 1078 bool remove = false; 1079 1080 bool original_discardable = false; 1081 bool original_discarded = false; 1082 1083 bool original_address_matters = original->address_matters_p (); 1084 bool alias_address_matters = alias->address_matters_p (); 1085 1086 if (DECL_EXTERNAL (alias->decl)) 1087 { 1088 if (dump_file) 1089 fprintf (dump_file, "Not unifying; alias is external.\n\n"); 1090 return false; 1091 } 1092 1093 if (DECL_NO_INLINE_WARNING_P (original->decl) 1094 != DECL_NO_INLINE_WARNING_P (alias->decl)) 1095 { 1096 if (dump_file) 1097 fprintf (dump_file, 1098 "Not unifying; " 1099 "DECL_NO_INLINE_WARNING mismatch.\n\n"); 1100 return false; 1101 } 1102 1103 /* Do not attempt to mix functions from different user sections; 1104 we do not know what user intends with those. */ 1105 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section) 1106 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section)) 1107 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl)) 1108 { 1109 if (dump_file) 1110 fprintf (dump_file, 1111 "Not unifying; " 1112 "original and alias are in different sections.\n\n"); 1113 return false; 1114 } 1115 1116 if (!original->in_same_comdat_group_p (alias) 1117 || original->comdat_local_p ()) 1118 { 1119 if (dump_file) 1120 fprintf (dump_file, 1121 "Not unifying; alias nor wrapper cannot be created; " 1122 "across comdat group boundary\n\n"); 1123 1124 return false; 1125 } 1126 1127 /* See if original is in a section that can be discarded if the main 1128 symbol is not used. */ 1129 1130 if (original->can_be_discarded_p ()) 1131 original_discardable = true; 1132 /* Also consider case where we have resolution info and we know that 1133 original's definition is not going to be used. In this case we can not 1134 create alias to original. */ 1135 if (node->resolution != LDPR_UNKNOWN 1136 && !decl_binds_to_current_def_p (node->decl)) 1137 original_discardable = original_discarded = true; 1138 1139 /* Creating a symtab alias is the optimal way to merge. 1140 It however can not be used in the following cases: 1141 1142 1) if ORIGINAL and ALIAS may be possibly compared for address equality. 1143 2) if ORIGINAL is in a section that may be discarded by linker or if 1144 it is an external functions where we can not create an alias 1145 (ORIGINAL_DISCARDABLE) 1146 3) if target do not support symbol aliases. 1147 4) original and alias lie in different comdat groups. 1148 1149 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL 1150 and/or redirect all callers from ALIAS to ORIGINAL. */ 1151 if ((original_address_matters && alias_address_matters) 1152 || (original_discardable 1153 && (!DECL_COMDAT_GROUP (alias->decl) 1154 || (DECL_COMDAT_GROUP (alias->decl) 1155 != DECL_COMDAT_GROUP (original->decl)))) 1156 || original_discarded 1157 || !sem_item::target_supports_symbol_aliases_p () 1158 || DECL_COMDAT_GROUP (alias->decl) != DECL_COMDAT_GROUP (original->decl)) 1159 { 1160 /* First see if we can produce wrapper. */ 1161 1162 /* Symbol properties that matter for references must be preserved. 1163 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL 1164 with proper properties. */ 1165 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias, 1166 alias->address_taken)) 1167 { 1168 if (dump_file) 1169 fprintf (dump_file, 1170 "Wrapper cannot be created because referenced symbol " 1171 "properties mismatch\n"); 1172 } 1173 /* Do not turn function in one comdat group into wrapper to another 1174 comdat group. Other compiler producing the body of the 1175 another comdat group may make opossite decision and with unfortunate 1176 linker choices this may close a loop. */ 1177 else if (DECL_COMDAT_GROUP (original->decl) 1178 && DECL_COMDAT_GROUP (alias->decl) 1179 && (DECL_COMDAT_GROUP (alias->decl) 1180 != DECL_COMDAT_GROUP (original->decl))) 1181 { 1182 if (dump_file) 1183 fprintf (dump_file, 1184 "Wrapper cannot be created because of COMDAT\n"); 1185 } 1186 else if (DECL_STATIC_CHAIN (alias->decl) 1187 || DECL_STATIC_CHAIN (original->decl)) 1188 { 1189 if (dump_file) 1190 fprintf (dump_file, 1191 "Cannot create wrapper of nested function.\n"); 1192 } 1193 /* TODO: We can also deal with variadic functions never calling 1194 VA_START. */ 1195 else if (stdarg_p (TREE_TYPE (alias->decl))) 1196 { 1197 if (dump_file) 1198 fprintf (dump_file, 1199 "can not create wrapper of stdarg function.\n"); 1200 } 1201 else if (ipa_fn_summaries 1202 && ipa_fn_summaries->get (alias)->self_size <= 2) 1203 { 1204 if (dump_file) 1205 fprintf (dump_file, "Wrapper creation is not " 1206 "profitable (function is too small).\n"); 1207 } 1208 /* If user paid attention to mark function noinline, assume it is 1209 somewhat special and do not try to turn it into a wrapper that can 1210 not be undone by inliner. */ 1211 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl))) 1212 { 1213 if (dump_file) 1214 fprintf (dump_file, "Wrappers are not created for noinline.\n"); 1215 } 1216 else 1217 create_wrapper = true; 1218 1219 /* We can redirect local calls in the case both alias and orignal 1220 are not interposable. */ 1221 redirect_callers 1222 = alias->get_availability () > AVAIL_INTERPOSABLE 1223 && original->get_availability () > AVAIL_INTERPOSABLE 1224 && !alias->instrumented_version; 1225 /* TODO: We can redirect, but we need to produce alias of ORIGINAL 1226 with proper properties. */ 1227 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias, 1228 alias->address_taken)) 1229 redirect_callers = false; 1230 1231 if (!redirect_callers && !create_wrapper) 1232 { 1233 if (dump_file) 1234 fprintf (dump_file, "Not unifying; can not redirect callers nor " 1235 "produce wrapper\n\n"); 1236 return false; 1237 } 1238 1239 /* Work out the symbol the wrapper should call. 1240 If ORIGINAL is interposable, we need to call a local alias. 1241 Also produce local alias (if possible) as an optimization. 1242 1243 Local aliases can not be created inside comdat groups because that 1244 prevents inlining. */ 1245 if (!original_discardable && !original->get_comdat_group ()) 1246 { 1247 local_original 1248 = dyn_cast <cgraph_node *> (original->noninterposable_alias ()); 1249 if (!local_original 1250 && original->get_availability () > AVAIL_INTERPOSABLE) 1251 local_original = original; 1252 } 1253 /* If we can not use local alias, fallback to the original 1254 when possible. */ 1255 else if (original->get_availability () > AVAIL_INTERPOSABLE) 1256 local_original = original; 1257 1258 /* If original is COMDAT local, we can not really redirect calls outside 1259 of its comdat group to it. */ 1260 if (original->comdat_local_p ()) 1261 redirect_callers = false; 1262 if (!local_original) 1263 { 1264 if (dump_file) 1265 fprintf (dump_file, "Not unifying; " 1266 "can not produce local alias.\n\n"); 1267 return false; 1268 } 1269 1270 if (!redirect_callers && !create_wrapper) 1271 { 1272 if (dump_file) 1273 fprintf (dump_file, "Not unifying; " 1274 "can not redirect callers nor produce a wrapper\n\n"); 1275 return false; 1276 } 1277 if (!create_wrapper 1278 && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p, 1279 NULL, true) 1280 && !alias->can_remove_if_no_direct_calls_p ()) 1281 { 1282 if (dump_file) 1283 fprintf (dump_file, "Not unifying; can not make wrapper and " 1284 "function has other uses than direct calls\n\n"); 1285 return false; 1286 } 1287 } 1288 else 1289 create_alias = true; 1290 1291 if (redirect_callers) 1292 { 1293 int nredirected = redirect_all_callers (alias, local_original); 1294 1295 if (nredirected) 1296 { 1297 alias->icf_merged = true; 1298 local_original->icf_merged = true; 1299 1300 if (dump_file && nredirected) 1301 fprintf (dump_file, "%i local calls have been " 1302 "redirected.\n", nredirected); 1303 } 1304 1305 /* If all callers was redirected, do not produce wrapper. */ 1306 if (alias->can_remove_if_no_direct_calls_p () 1307 && !DECL_VIRTUAL_P (alias->decl) 1308 && !alias->has_aliases_p ()) 1309 { 1310 create_wrapper = false; 1311 remove = true; 1312 } 1313 gcc_assert (!create_alias); 1314 } 1315 else if (create_alias) 1316 { 1317 alias->icf_merged = true; 1318 1319 /* Remove the function's body. */ 1320 ipa_merge_profiles (original, alias); 1321 alias->release_body (true); 1322 alias->reset (); 1323 /* Notice global symbol possibly produced RTL. */ 1324 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl, 1325 NULL, true); 1326 1327 /* Create the alias. */ 1328 cgraph_node::create_alias (alias_func->decl, decl); 1329 alias->resolve_alias (original); 1330 1331 original->call_for_symbol_thunks_and_aliases 1332 (set_local, (void *)(size_t) original->local_p (), true); 1333 1334 if (dump_file) 1335 fprintf (dump_file, "Unified; Function alias has been created.\n\n"); 1336 } 1337 if (create_wrapper) 1338 { 1339 gcc_assert (!create_alias); 1340 alias->icf_merged = true; 1341 local_original->icf_merged = true; 1342 1343 /* FIXME update local_original counts. */ 1344 ipa_merge_profiles (original, alias, true); 1345 alias->create_wrapper (local_original); 1346 1347 if (dump_file) 1348 fprintf (dump_file, "Unified; Wrapper has been created.\n\n"); 1349 } 1350 1351 /* It's possible that redirection can hit thunks that block 1352 redirection opportunities. */ 1353 gcc_assert (alias->icf_merged || remove || redirect_callers); 1354 original->icf_merged = true; 1355 1356 /* We use merged flag to track cases where COMDAT function is known to be 1357 compatible its callers. If we merged in non-COMDAT, we need to give up 1358 on this optimization. */ 1359 if (original->merged_comdat && !alias->merged_comdat) 1360 { 1361 if (dump_file) 1362 fprintf (dump_file, "Dropping merged_comdat flag.\n\n"); 1363 if (local_original) 1364 local_original->merged_comdat = false; 1365 original->merged_comdat = false; 1366 } 1367 1368 if (remove) 1369 { 1370 ipa_merge_profiles (original, alias); 1371 alias->release_body (); 1372 alias->reset (); 1373 alias->body_removed = true; 1374 alias->icf_merged = true; 1375 if (dump_file) 1376 fprintf (dump_file, "Unified; Function body was removed.\n"); 1377 } 1378 1379 return true; 1380 } 1381 1382 /* Semantic item initialization function. */ 1383 1384 void 1385 sem_function::init (void) 1386 { 1387 if (in_lto_p) 1388 get_node ()->get_untransformed_body (); 1389 1390 tree fndecl = node->decl; 1391 function *func = DECL_STRUCT_FUNCTION (fndecl); 1392 1393 gcc_assert (func); 1394 gcc_assert (SSANAMES (func)); 1395 1396 ssa_names_size = SSANAMES (func)->length (); 1397 node = node; 1398 1399 decl = fndecl; 1400 region_tree = func->eh->region_tree; 1401 1402 /* iterating all function arguments. */ 1403 arg_count = count_formal_params (fndecl); 1404 1405 edge_count = n_edges_for_fn (func); 1406 cgraph_node *cnode = dyn_cast <cgraph_node *> (node); 1407 if (!cnode->thunk.thunk_p) 1408 { 1409 cfg_checksum = coverage_compute_cfg_checksum (func); 1410 1411 inchash::hash hstate; 1412 1413 basic_block bb; 1414 FOR_EACH_BB_FN (bb, func) 1415 { 1416 unsigned nondbg_stmt_count = 0; 1417 1418 edge e; 1419 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e); 1420 ei_next (&ei)) 1421 cfg_checksum = iterative_hash_host_wide_int (e->flags, 1422 cfg_checksum); 1423 1424 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); 1425 gsi_next (&gsi)) 1426 { 1427 gimple *stmt = gsi_stmt (gsi); 1428 1429 if (gimple_code (stmt) != GIMPLE_DEBUG 1430 && gimple_code (stmt) != GIMPLE_PREDICT) 1431 { 1432 hash_stmt (stmt, hstate); 1433 nondbg_stmt_count++; 1434 } 1435 } 1436 1437 hstate.commit_flag (); 1438 gcode_hash = hstate.end (); 1439 bb_sizes.safe_push (nondbg_stmt_count); 1440 1441 /* Inserting basic block to hash table. */ 1442 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count, 1443 EDGE_COUNT (bb->preds) 1444 + EDGE_COUNT (bb->succs)); 1445 1446 bb_sorted.safe_push (semantic_bb); 1447 } 1448 } 1449 else 1450 { 1451 cfg_checksum = 0; 1452 inchash::hash hstate; 1453 hstate.add_hwi (cnode->thunk.fixed_offset); 1454 hstate.add_hwi (cnode->thunk.virtual_value); 1455 hstate.add_flag (cnode->thunk.this_adjusting); 1456 hstate.add_flag (cnode->thunk.virtual_offset_p); 1457 hstate.add_flag (cnode->thunk.add_pointer_bounds_args); 1458 gcode_hash = hstate.end (); 1459 } 1460 } 1461 1462 /* Accumulate to HSTATE a hash of expression EXP. 1463 Identical to inchash::add_expr, but guaranteed to be stable across LTO 1464 and DECL equality classes. */ 1465 1466 void 1467 sem_item::add_expr (const_tree exp, inchash::hash &hstate) 1468 { 1469 if (exp == NULL_TREE) 1470 { 1471 hstate.merge_hash (0); 1472 return; 1473 } 1474 1475 /* Handled component can be matched in a cureful way proving equivalence 1476 even if they syntactically differ. Just skip them. */ 1477 STRIP_NOPS (exp); 1478 while (handled_component_p (exp)) 1479 exp = TREE_OPERAND (exp, 0); 1480 1481 enum tree_code code = TREE_CODE (exp); 1482 hstate.add_int (code); 1483 1484 switch (code) 1485 { 1486 /* Use inchash::add_expr for everything that is LTO stable. */ 1487 case VOID_CST: 1488 case INTEGER_CST: 1489 case REAL_CST: 1490 case FIXED_CST: 1491 case STRING_CST: 1492 case COMPLEX_CST: 1493 case VECTOR_CST: 1494 inchash::add_expr (exp, hstate); 1495 break; 1496 case CONSTRUCTOR: 1497 { 1498 unsigned HOST_WIDE_INT idx; 1499 tree value; 1500 1501 hstate.add_hwi (int_size_in_bytes (TREE_TYPE (exp))); 1502 1503 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp), idx, value) 1504 if (value) 1505 add_expr (value, hstate); 1506 break; 1507 } 1508 case ADDR_EXPR: 1509 case FDESC_EXPR: 1510 add_expr (get_base_address (TREE_OPERAND (exp, 0)), hstate); 1511 break; 1512 case SSA_NAME: 1513 case VAR_DECL: 1514 case CONST_DECL: 1515 case PARM_DECL: 1516 hstate.add_hwi (int_size_in_bytes (TREE_TYPE (exp))); 1517 break; 1518 case MEM_REF: 1519 case POINTER_PLUS_EXPR: 1520 case MINUS_EXPR: 1521 case RANGE_EXPR: 1522 add_expr (TREE_OPERAND (exp, 0), hstate); 1523 add_expr (TREE_OPERAND (exp, 1), hstate); 1524 break; 1525 case PLUS_EXPR: 1526 { 1527 inchash::hash one, two; 1528 add_expr (TREE_OPERAND (exp, 0), one); 1529 add_expr (TREE_OPERAND (exp, 1), two); 1530 hstate.add_commutative (one, two); 1531 } 1532 break; 1533 CASE_CONVERT: 1534 hstate.add_hwi (int_size_in_bytes (TREE_TYPE (exp))); 1535 return add_expr (TREE_OPERAND (exp, 0), hstate); 1536 default: 1537 break; 1538 } 1539 } 1540 1541 /* Accumulate to HSTATE a hash of type t. 1542 TYpes that may end up being compatible after LTO type merging needs to have 1543 the same hash. */ 1544 1545 void 1546 sem_item::add_type (const_tree type, inchash::hash &hstate) 1547 { 1548 if (type == NULL_TREE) 1549 { 1550 hstate.merge_hash (0); 1551 return; 1552 } 1553 1554 type = TYPE_MAIN_VARIANT (type); 1555 1556 hstate.add_int (TYPE_MODE (type)); 1557 1558 if (TREE_CODE (type) == COMPLEX_TYPE) 1559 { 1560 hstate.add_int (COMPLEX_TYPE); 1561 sem_item::add_type (TREE_TYPE (type), hstate); 1562 } 1563 else if (INTEGRAL_TYPE_P (type)) 1564 { 1565 hstate.add_int (INTEGER_TYPE); 1566 hstate.add_flag (TYPE_UNSIGNED (type)); 1567 hstate.add_int (TYPE_PRECISION (type)); 1568 } 1569 else if (VECTOR_TYPE_P (type)) 1570 { 1571 hstate.add_int (VECTOR_TYPE); 1572 hstate.add_int (TYPE_PRECISION (type)); 1573 sem_item::add_type (TREE_TYPE (type), hstate); 1574 } 1575 else if (TREE_CODE (type) == ARRAY_TYPE) 1576 { 1577 hstate.add_int (ARRAY_TYPE); 1578 /* Do not hash size, so complete and incomplete types can match. */ 1579 sem_item::add_type (TREE_TYPE (type), hstate); 1580 } 1581 else if (RECORD_OR_UNION_TYPE_P (type)) 1582 { 1583 gcc_checking_assert (COMPLETE_TYPE_P (type)); 1584 hashval_t *val = optimizer->m_type_hash_cache.get (type); 1585 1586 if (!val) 1587 { 1588 inchash::hash hstate2; 1589 unsigned nf; 1590 tree f; 1591 hashval_t hash; 1592 1593 hstate2.add_int (RECORD_TYPE); 1594 gcc_assert (COMPLETE_TYPE_P (type)); 1595 1596 for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f)) 1597 if (TREE_CODE (f) == FIELD_DECL) 1598 { 1599 add_type (TREE_TYPE (f), hstate2); 1600 nf++; 1601 } 1602 1603 hstate2.add_int (nf); 1604 hash = hstate2.end (); 1605 hstate.add_hwi (hash); 1606 optimizer->m_type_hash_cache.put (type, hash); 1607 } 1608 else 1609 hstate.add_hwi (*val); 1610 } 1611 } 1612 1613 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */ 1614 1615 void 1616 sem_function::hash_stmt (gimple *stmt, inchash::hash &hstate) 1617 { 1618 enum gimple_code code = gimple_code (stmt); 1619 1620 hstate.add_int (code); 1621 1622 switch (code) 1623 { 1624 case GIMPLE_SWITCH: 1625 add_expr (gimple_switch_index (as_a <gswitch *> (stmt)), hstate); 1626 break; 1627 case GIMPLE_ASSIGN: 1628 hstate.add_int (gimple_assign_rhs_code (stmt)); 1629 if (commutative_tree_code (gimple_assign_rhs_code (stmt)) 1630 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt))) 1631 { 1632 inchash::hash one, two; 1633 1634 add_expr (gimple_assign_rhs1 (stmt), one); 1635 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt)), one); 1636 add_expr (gimple_assign_rhs2 (stmt), two); 1637 hstate.add_commutative (one, two); 1638 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt))) 1639 { 1640 add_expr (gimple_assign_rhs3 (stmt), hstate); 1641 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt)), hstate); 1642 } 1643 add_expr (gimple_assign_lhs (stmt), hstate); 1644 add_type (TREE_TYPE (gimple_assign_lhs (stmt)), two); 1645 break; 1646 } 1647 /* fall through */ 1648 case GIMPLE_CALL: 1649 case GIMPLE_ASM: 1650 case GIMPLE_COND: 1651 case GIMPLE_GOTO: 1652 case GIMPLE_RETURN: 1653 /* All these statements are equivalent if their operands are. */ 1654 for (unsigned i = 0; i < gimple_num_ops (stmt); ++i) 1655 { 1656 add_expr (gimple_op (stmt, i), hstate); 1657 if (gimple_op (stmt, i)) 1658 add_type (TREE_TYPE (gimple_op (stmt, i)), hstate); 1659 } 1660 /* Consider nocf_check attribute in hash as it affects code 1661 generation. */ 1662 if (code == GIMPLE_CALL 1663 && flag_cf_protection & CF_BRANCH) 1664 hstate.add_flag (gimple_call_nocf_check_p (as_a <gcall *> (stmt))); 1665 default: 1666 break; 1667 } 1668 } 1669 1670 1671 /* Return true if polymorphic comparison must be processed. */ 1672 1673 bool 1674 sem_function::compare_polymorphic_p (void) 1675 { 1676 struct cgraph_edge *e; 1677 1678 if (!opt_for_fn (get_node ()->decl, flag_devirtualize)) 1679 return false; 1680 if (get_node ()->indirect_calls != NULL) 1681 return true; 1682 /* TODO: We can do simple propagation determining what calls may lead to 1683 a polymorphic call. */ 1684 for (e = get_node ()->callees; e; e = e->next_callee) 1685 if (e->callee->definition 1686 && opt_for_fn (e->callee->decl, flag_devirtualize)) 1687 return true; 1688 return false; 1689 } 1690 1691 /* For a given call graph NODE, the function constructs new 1692 semantic function item. */ 1693 1694 sem_function * 1695 sem_function::parse (cgraph_node *node, bitmap_obstack *stack) 1696 { 1697 tree fndecl = node->decl; 1698 function *func = DECL_STRUCT_FUNCTION (fndecl); 1699 1700 if (!func || (!node->has_gimple_body_p () && !node->thunk.thunk_p)) 1701 return NULL; 1702 1703 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL) 1704 return NULL; 1705 1706 if (lookup_attribute_by_prefix ("oacc ", 1707 DECL_ATTRIBUTES (node->decl)) != NULL) 1708 return NULL; 1709 1710 /* PR ipa/70306. */ 1711 if (DECL_STATIC_CONSTRUCTOR (node->decl) 1712 || DECL_STATIC_DESTRUCTOR (node->decl)) 1713 return NULL; 1714 1715 sem_function *f = new sem_function (node, stack); 1716 1717 f->init (); 1718 1719 return f; 1720 } 1721 1722 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC), 1723 return true if phi nodes are semantically equivalent in these blocks . */ 1724 1725 bool 1726 sem_function::compare_phi_node (basic_block bb1, basic_block bb2) 1727 { 1728 gphi_iterator si1, si2; 1729 gphi *phi1, *phi2; 1730 unsigned size1, size2, i; 1731 tree t1, t2; 1732 edge e1, e2; 1733 1734 gcc_assert (bb1 != NULL); 1735 gcc_assert (bb2 != NULL); 1736 1737 si2 = gsi_start_phis (bb2); 1738 for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1); 1739 gsi_next (&si1)) 1740 { 1741 gsi_next_nonvirtual_phi (&si1); 1742 gsi_next_nonvirtual_phi (&si2); 1743 1744 if (gsi_end_p (si1) && gsi_end_p (si2)) 1745 break; 1746 1747 if (gsi_end_p (si1) || gsi_end_p (si2)) 1748 return return_false(); 1749 1750 phi1 = si1.phi (); 1751 phi2 = si2.phi (); 1752 1753 tree phi_result1 = gimple_phi_result (phi1); 1754 tree phi_result2 = gimple_phi_result (phi2); 1755 1756 if (!m_checker->compare_operand (phi_result1, phi_result2)) 1757 return return_false_with_msg ("PHI results are different"); 1758 1759 size1 = gimple_phi_num_args (phi1); 1760 size2 = gimple_phi_num_args (phi2); 1761 1762 if (size1 != size2) 1763 return return_false (); 1764 1765 for (i = 0; i < size1; ++i) 1766 { 1767 t1 = gimple_phi_arg (phi1, i)->def; 1768 t2 = gimple_phi_arg (phi2, i)->def; 1769 1770 if (!m_checker->compare_operand (t1, t2)) 1771 return return_false (); 1772 1773 e1 = gimple_phi_arg_edge (phi1, i); 1774 e2 = gimple_phi_arg_edge (phi2, i); 1775 1776 if (!m_checker->compare_edge (e1, e2)) 1777 return return_false (); 1778 } 1779 1780 gsi_next (&si2); 1781 } 1782 1783 return true; 1784 } 1785 1786 /* Returns true if tree T can be compared as a handled component. */ 1787 1788 bool 1789 sem_function::icf_handled_component_p (tree t) 1790 { 1791 tree_code tc = TREE_CODE (t); 1792 1793 return (handled_component_p (t) 1794 || tc == ADDR_EXPR || tc == MEM_REF || tc == OBJ_TYPE_REF); 1795 } 1796 1797 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB 1798 corresponds to TARGET. */ 1799 1800 bool 1801 sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target) 1802 { 1803 source++; 1804 target++; 1805 1806 if (bb_dict->length () <= (unsigned)source) 1807 bb_dict->safe_grow_cleared (source + 1); 1808 1809 if ((*bb_dict)[source] == 0) 1810 { 1811 (*bb_dict)[source] = target; 1812 return true; 1813 } 1814 else 1815 return (*bb_dict)[source] == target; 1816 } 1817 1818 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack) 1819 { 1820 } 1821 1822 sem_variable::sem_variable (varpool_node *node, bitmap_obstack *stack) 1823 : sem_item (VAR, node, stack) 1824 { 1825 gcc_checking_assert (node); 1826 gcc_checking_assert (get_node ()); 1827 } 1828 1829 /* Fast equality function based on knowledge known in WPA. */ 1830 1831 bool 1832 sem_variable::equals_wpa (sem_item *item, 1833 hash_map <symtab_node *, sem_item *> &ignored_nodes) 1834 { 1835 gcc_assert (item->type == VAR); 1836 1837 if (node->num_references () != item->node->num_references ()) 1838 return return_false_with_msg ("different number of references"); 1839 1840 if (DECL_TLS_MODEL (decl) || DECL_TLS_MODEL (item->decl)) 1841 return return_false_with_msg ("TLS model"); 1842 1843 /* DECL_ALIGN is safe to merge, because we will always chose the largest 1844 alignment out of all aliases. */ 1845 1846 if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl)) 1847 return return_false_with_msg ("Virtual flag mismatch"); 1848 1849 if (DECL_SIZE (decl) != DECL_SIZE (item->decl) 1850 && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl)) 1851 || !operand_equal_p (DECL_SIZE (decl), 1852 DECL_SIZE (item->decl), OEP_ONLY_CONST))) 1853 return return_false_with_msg ("size mismatch"); 1854 1855 /* Do not attempt to mix data from different user sections; 1856 we do not know what user intends with those. */ 1857 if (((DECL_SECTION_NAME (decl) && !node->implicit_section) 1858 || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section)) 1859 && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl)) 1860 return return_false_with_msg ("user section mismatch"); 1861 1862 if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl)) 1863 return return_false_with_msg ("text section"); 1864 1865 ipa_ref *ref = NULL, *ref2 = NULL; 1866 for (unsigned i = 0; node->iterate_reference (i, ref); i++) 1867 { 1868 item->node->iterate_reference (i, ref2); 1869 1870 if (ref->use != ref2->use) 1871 return return_false_with_msg ("reference use mismatch"); 1872 1873 if (!compare_symbol_references (ignored_nodes, 1874 ref->referred, ref2->referred, 1875 ref->address_matters_p ())) 1876 return false; 1877 } 1878 1879 return true; 1880 } 1881 1882 /* Returns true if the item equals to ITEM given as argument. */ 1883 1884 bool 1885 sem_variable::equals (sem_item *item, 1886 hash_map <symtab_node *, sem_item *> &) 1887 { 1888 gcc_assert (item->type == VAR); 1889 bool ret; 1890 1891 if (DECL_INITIAL (decl) == error_mark_node && in_lto_p) 1892 dyn_cast <varpool_node *>(node)->get_constructor (); 1893 if (DECL_INITIAL (item->decl) == error_mark_node && in_lto_p) 1894 dyn_cast <varpool_node *>(item->node)->get_constructor (); 1895 1896 /* As seen in PR ipa/65303 we have to compare variables types. */ 1897 if (!func_checker::compatible_types_p (TREE_TYPE (decl), 1898 TREE_TYPE (item->decl))) 1899 return return_false_with_msg ("variables types are different"); 1900 1901 ret = sem_variable::equals (DECL_INITIAL (decl), 1902 DECL_INITIAL (item->node->decl)); 1903 if (dump_file && (dump_flags & TDF_DETAILS)) 1904 fprintf (dump_file, 1905 "Equals called for vars: %s:%s with result: %s\n\n", 1906 node->dump_name (), item->node->dump_name (), 1907 ret ? "true" : "false"); 1908 1909 return ret; 1910 } 1911 1912 /* Compares trees T1 and T2 for semantic equality. */ 1913 1914 bool 1915 sem_variable::equals (tree t1, tree t2) 1916 { 1917 if (!t1 || !t2) 1918 return return_with_debug (t1 == t2); 1919 if (t1 == t2) 1920 return true; 1921 tree_code tc1 = TREE_CODE (t1); 1922 tree_code tc2 = TREE_CODE (t2); 1923 1924 if (tc1 != tc2) 1925 return return_false_with_msg ("TREE_CODE mismatch"); 1926 1927 switch (tc1) 1928 { 1929 case CONSTRUCTOR: 1930 { 1931 vec<constructor_elt, va_gc> *v1, *v2; 1932 unsigned HOST_WIDE_INT idx; 1933 1934 enum tree_code typecode = TREE_CODE (TREE_TYPE (t1)); 1935 if (typecode != TREE_CODE (TREE_TYPE (t2))) 1936 return return_false_with_msg ("constructor type mismatch"); 1937 1938 if (typecode == ARRAY_TYPE) 1939 { 1940 HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1)); 1941 /* For arrays, check that the sizes all match. */ 1942 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)) 1943 || size_1 == -1 1944 || size_1 != int_size_in_bytes (TREE_TYPE (t2))) 1945 return return_false_with_msg ("constructor array size mismatch"); 1946 } 1947 else if (!func_checker::compatible_types_p (TREE_TYPE (t1), 1948 TREE_TYPE (t2))) 1949 return return_false_with_msg ("constructor type incompatible"); 1950 1951 v1 = CONSTRUCTOR_ELTS (t1); 1952 v2 = CONSTRUCTOR_ELTS (t2); 1953 if (vec_safe_length (v1) != vec_safe_length (v2)) 1954 return return_false_with_msg ("constructor number of elts mismatch"); 1955 1956 for (idx = 0; idx < vec_safe_length (v1); ++idx) 1957 { 1958 constructor_elt *c1 = &(*v1)[idx]; 1959 constructor_elt *c2 = &(*v2)[idx]; 1960 1961 /* Check that each value is the same... */ 1962 if (!sem_variable::equals (c1->value, c2->value)) 1963 return false; 1964 /* ... and that they apply to the same fields! */ 1965 if (!sem_variable::equals (c1->index, c2->index)) 1966 return false; 1967 } 1968 return true; 1969 } 1970 case MEM_REF: 1971 { 1972 tree x1 = TREE_OPERAND (t1, 0); 1973 tree x2 = TREE_OPERAND (t2, 0); 1974 tree y1 = TREE_OPERAND (t1, 1); 1975 tree y2 = TREE_OPERAND (t2, 1); 1976 1977 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2))) 1978 return return_false (); 1979 1980 /* Type of the offset on MEM_REF does not matter. */ 1981 return return_with_debug (sem_variable::equals (x1, x2) 1982 && wi::to_offset (y1) 1983 == wi::to_offset (y2)); 1984 } 1985 case ADDR_EXPR: 1986 case FDESC_EXPR: 1987 { 1988 tree op1 = TREE_OPERAND (t1, 0); 1989 tree op2 = TREE_OPERAND (t2, 0); 1990 return sem_variable::equals (op1, op2); 1991 } 1992 /* References to other vars/decls are compared using ipa-ref. */ 1993 case FUNCTION_DECL: 1994 case VAR_DECL: 1995 if (decl_in_symtab_p (t1) && decl_in_symtab_p (t2)) 1996 return true; 1997 return return_false_with_msg ("Declaration mismatch"); 1998 case CONST_DECL: 1999 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we 2000 need to process its VAR/FUNCTION references without relying on ipa-ref 2001 compare. */ 2002 case FIELD_DECL: 2003 case LABEL_DECL: 2004 return return_false_with_msg ("Declaration mismatch"); 2005 case INTEGER_CST: 2006 /* Integer constants are the same only if the same width of type. */ 2007 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2))) 2008 return return_false_with_msg ("INTEGER_CST precision mismatch"); 2009 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))) 2010 return return_false_with_msg ("INTEGER_CST mode mismatch"); 2011 return return_with_debug (tree_int_cst_equal (t1, t2)); 2012 case STRING_CST: 2013 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))) 2014 return return_false_with_msg ("STRING_CST mode mismatch"); 2015 if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2)) 2016 return return_false_with_msg ("STRING_CST length mismatch"); 2017 if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2), 2018 TREE_STRING_LENGTH (t1))) 2019 return return_false_with_msg ("STRING_CST mismatch"); 2020 return true; 2021 case FIXED_CST: 2022 /* Fixed constants are the same only if the same width of type. */ 2023 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2))) 2024 return return_false_with_msg ("FIXED_CST precision mismatch"); 2025 2026 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1), 2027 TREE_FIXED_CST (t2))); 2028 case COMPLEX_CST: 2029 return (sem_variable::equals (TREE_REALPART (t1), TREE_REALPART (t2)) 2030 && sem_variable::equals (TREE_IMAGPART (t1), TREE_IMAGPART (t2))); 2031 case REAL_CST: 2032 /* Real constants are the same only if the same width of type. */ 2033 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2))) 2034 return return_false_with_msg ("REAL_CST precision mismatch"); 2035 return return_with_debug (real_identical (&TREE_REAL_CST (t1), 2036 &TREE_REAL_CST (t2))); 2037 case VECTOR_CST: 2038 { 2039 if (maybe_ne (VECTOR_CST_NELTS (t1), VECTOR_CST_NELTS (t2))) 2040 return return_false_with_msg ("VECTOR_CST nelts mismatch"); 2041 2042 unsigned int count 2043 = tree_vector_builder::binary_encoded_nelts (t1, t2); 2044 for (unsigned int i = 0; i < count; ++i) 2045 if (!sem_variable::equals (VECTOR_CST_ENCODED_ELT (t1, i), 2046 VECTOR_CST_ENCODED_ELT (t2, i))) 2047 return false; 2048 2049 return true; 2050 } 2051 case ARRAY_REF: 2052 case ARRAY_RANGE_REF: 2053 { 2054 tree x1 = TREE_OPERAND (t1, 0); 2055 tree x2 = TREE_OPERAND (t2, 0); 2056 tree y1 = TREE_OPERAND (t1, 1); 2057 tree y2 = TREE_OPERAND (t2, 1); 2058 2059 if (!sem_variable::equals (x1, x2) || !sem_variable::equals (y1, y2)) 2060 return false; 2061 if (!sem_variable::equals (array_ref_low_bound (t1), 2062 array_ref_low_bound (t2))) 2063 return false; 2064 if (!sem_variable::equals (array_ref_element_size (t1), 2065 array_ref_element_size (t2))) 2066 return false; 2067 return true; 2068 } 2069 2070 case COMPONENT_REF: 2071 case POINTER_PLUS_EXPR: 2072 case PLUS_EXPR: 2073 case MINUS_EXPR: 2074 case RANGE_EXPR: 2075 { 2076 tree x1 = TREE_OPERAND (t1, 0); 2077 tree x2 = TREE_OPERAND (t2, 0); 2078 tree y1 = TREE_OPERAND (t1, 1); 2079 tree y2 = TREE_OPERAND (t2, 1); 2080 2081 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2); 2082 } 2083 2084 CASE_CONVERT: 2085 case VIEW_CONVERT_EXPR: 2086 if (!func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2))) 2087 return return_false (); 2088 return sem_variable::equals (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)); 2089 case ERROR_MARK: 2090 return return_false_with_msg ("ERROR_MARK"); 2091 default: 2092 return return_false_with_msg ("Unknown TREE code reached"); 2093 } 2094 } 2095 2096 /* Parser function that visits a varpool NODE. */ 2097 2098 sem_variable * 2099 sem_variable::parse (varpool_node *node, bitmap_obstack *stack) 2100 { 2101 if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl) 2102 || node->alias) 2103 return NULL; 2104 2105 sem_variable *v = new sem_variable (node, stack); 2106 2107 v->init (); 2108 2109 return v; 2110 } 2111 2112 /* References independent hash function. */ 2113 2114 hashval_t 2115 sem_variable::get_hash (void) 2116 { 2117 if (m_hash_set) 2118 return m_hash; 2119 2120 /* All WPA streamed in symbols should have their hashes computed at compile 2121 time. At this point, the constructor may not be in memory at all. 2122 DECL_INITIAL (decl) would be error_mark_node in that case. */ 2123 gcc_assert (!node->lto_file_data); 2124 tree ctor = DECL_INITIAL (decl); 2125 inchash::hash hstate; 2126 2127 hstate.add_int (456346417); 2128 if (DECL_SIZE (decl) && tree_fits_shwi_p (DECL_SIZE (decl))) 2129 hstate.add_hwi (tree_to_shwi (DECL_SIZE (decl))); 2130 add_expr (ctor, hstate); 2131 set_hash (hstate.end ()); 2132 2133 return m_hash; 2134 } 2135 2136 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can 2137 be applied. */ 2138 2139 bool 2140 sem_variable::merge (sem_item *alias_item) 2141 { 2142 gcc_assert (alias_item->type == VAR); 2143 2144 if (!sem_item::target_supports_symbol_aliases_p ()) 2145 { 2146 if (dump_file) 2147 fprintf (dump_file, "Not unifying; " 2148 "Symbol aliases are not supported by target\n\n"); 2149 return false; 2150 } 2151 2152 if (DECL_EXTERNAL (alias_item->decl)) 2153 { 2154 if (dump_file) 2155 fprintf (dump_file, "Not unifying; alias is external.\n\n"); 2156 return false; 2157 } 2158 2159 sem_variable *alias_var = static_cast<sem_variable *> (alias_item); 2160 2161 varpool_node *original = get_node (); 2162 varpool_node *alias = alias_var->get_node (); 2163 bool original_discardable = false; 2164 2165 bool alias_address_matters = alias->address_matters_p (); 2166 2167 /* See if original is in a section that can be discarded if the main 2168 symbol is not used. 2169 Also consider case where we have resolution info and we know that 2170 original's definition is not going to be used. In this case we can not 2171 create alias to original. */ 2172 if (original->can_be_discarded_p () 2173 || (node->resolution != LDPR_UNKNOWN 2174 && !decl_binds_to_current_def_p (node->decl))) 2175 original_discardable = true; 2176 2177 gcc_assert (!TREE_ASM_WRITTEN (alias->decl)); 2178 2179 /* Constant pool machinery is not quite ready for aliases. 2180 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL. 2181 For LTO merging does not happen that is an important missing feature. 2182 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL 2183 flag is dropped and non-local symbol name is assigned. */ 2184 if (DECL_IN_CONSTANT_POOL (alias->decl) 2185 || DECL_IN_CONSTANT_POOL (original->decl)) 2186 { 2187 if (dump_file) 2188 fprintf (dump_file, 2189 "Not unifying; constant pool variables.\n\n"); 2190 return false; 2191 } 2192 2193 /* Do not attempt to mix functions from different user sections; 2194 we do not know what user intends with those. */ 2195 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section) 2196 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section)) 2197 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl)) 2198 { 2199 if (dump_file) 2200 fprintf (dump_file, 2201 "Not unifying; " 2202 "original and alias are in different sections.\n\n"); 2203 return false; 2204 } 2205 2206 /* We can not merge if address comparsion metters. */ 2207 if (alias_address_matters && flag_merge_constants < 2) 2208 { 2209 if (dump_file) 2210 fprintf (dump_file, 2211 "Not unifying; address of original may be compared.\n\n"); 2212 return false; 2213 } 2214 2215 if (DECL_ALIGN (original->decl) < DECL_ALIGN (alias->decl)) 2216 { 2217 if (dump_file) 2218 fprintf (dump_file, "Not unifying; " 2219 "original and alias have incompatible alignments\n\n"); 2220 2221 return false; 2222 } 2223 2224 if (DECL_COMDAT_GROUP (original->decl) != DECL_COMDAT_GROUP (alias->decl)) 2225 { 2226 if (dump_file) 2227 fprintf (dump_file, "Not unifying; alias cannot be created; " 2228 "across comdat group boundary\n\n"); 2229 2230 return false; 2231 } 2232 2233 if (original_discardable) 2234 { 2235 if (dump_file) 2236 fprintf (dump_file, "Not unifying; alias cannot be created; " 2237 "target is discardable\n\n"); 2238 2239 return false; 2240 } 2241 else 2242 { 2243 gcc_assert (!original->alias); 2244 gcc_assert (!alias->alias); 2245 2246 alias->analyzed = false; 2247 2248 DECL_INITIAL (alias->decl) = NULL; 2249 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl, 2250 NULL, true); 2251 alias->need_bounds_init = false; 2252 alias->remove_all_references (); 2253 if (TREE_ADDRESSABLE (alias->decl)) 2254 original->call_for_symbol_and_aliases (set_addressable, NULL, true); 2255 2256 varpool_node::create_alias (alias_var->decl, decl); 2257 alias->resolve_alias (original); 2258 2259 if (dump_file) 2260 fprintf (dump_file, "Unified; Variable alias has been created.\n"); 2261 2262 return true; 2263 } 2264 } 2265 2266 /* Dump symbol to FILE. */ 2267 2268 void 2269 sem_variable::dump_to_file (FILE *file) 2270 { 2271 gcc_assert (file); 2272 2273 print_node (file, "", decl, 0); 2274 fprintf (file, "\n\n"); 2275 } 2276 2277 unsigned int sem_item_optimizer::class_id = 0; 2278 2279 sem_item_optimizer::sem_item_optimizer () 2280 : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL), 2281 m_varpool_node_hooks (NULL), m_merged_variables () 2282 { 2283 m_items.create (0); 2284 bitmap_obstack_initialize (&m_bmstack); 2285 } 2286 2287 sem_item_optimizer::~sem_item_optimizer () 2288 { 2289 for (unsigned int i = 0; i < m_items.length (); i++) 2290 delete m_items[i]; 2291 2292 2293 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin (); 2294 it != m_classes.end (); ++it) 2295 { 2296 for (unsigned int i = 0; i < (*it)->classes.length (); i++) 2297 delete (*it)->classes[i]; 2298 2299 (*it)->classes.release (); 2300 free (*it); 2301 } 2302 2303 m_items.release (); 2304 2305 bitmap_obstack_release (&m_bmstack); 2306 m_merged_variables.release (); 2307 } 2308 2309 /* Write IPA ICF summary for symbols. */ 2310 2311 void 2312 sem_item_optimizer::write_summary (void) 2313 { 2314 unsigned int count = 0; 2315 2316 output_block *ob = create_output_block (LTO_section_ipa_icf); 2317 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder; 2318 ob->symbol = NULL; 2319 2320 /* Calculate number of symbols to be serialized. */ 2321 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder); 2322 !lsei_end_p (lsei); 2323 lsei_next_in_partition (&lsei)) 2324 { 2325 symtab_node *node = lsei_node (lsei); 2326 2327 if (m_symtab_node_map.get (node)) 2328 count++; 2329 } 2330 2331 streamer_write_uhwi (ob, count); 2332 2333 /* Process all of the symbols. */ 2334 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder); 2335 !lsei_end_p (lsei); 2336 lsei_next_in_partition (&lsei)) 2337 { 2338 symtab_node *node = lsei_node (lsei); 2339 2340 sem_item **item = m_symtab_node_map.get (node); 2341 2342 if (item && *item) 2343 { 2344 int node_ref = lto_symtab_encoder_encode (encoder, node); 2345 streamer_write_uhwi_stream (ob->main_stream, node_ref); 2346 2347 streamer_write_uhwi (ob, (*item)->get_hash ()); 2348 } 2349 } 2350 2351 streamer_write_char_stream (ob->main_stream, 0); 2352 produce_asm (ob, NULL); 2353 destroy_output_block (ob); 2354 } 2355 2356 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA 2357 contains LEN bytes. */ 2358 2359 void 2360 sem_item_optimizer::read_section (lto_file_decl_data *file_data, 2361 const char *data, size_t len) 2362 { 2363 const lto_function_header *header 2364 = (const lto_function_header *) data; 2365 const int cfg_offset = sizeof (lto_function_header); 2366 const int main_offset = cfg_offset + header->cfg_size; 2367 const int string_offset = main_offset + header->main_size; 2368 data_in *data_in; 2369 unsigned int i; 2370 unsigned int count; 2371 2372 lto_input_block ib_main ((const char *) data + main_offset, 0, 2373 header->main_size, file_data->mode_table); 2374 2375 data_in 2376 = lto_data_in_create (file_data, (const char *) data + string_offset, 2377 header->string_size, vNULL); 2378 2379 count = streamer_read_uhwi (&ib_main); 2380 2381 for (i = 0; i < count; i++) 2382 { 2383 unsigned int index; 2384 symtab_node *node; 2385 lto_symtab_encoder_t encoder; 2386 2387 index = streamer_read_uhwi (&ib_main); 2388 encoder = file_data->symtab_node_encoder; 2389 node = lto_symtab_encoder_deref (encoder, index); 2390 2391 hashval_t hash = streamer_read_uhwi (&ib_main); 2392 2393 gcc_assert (node->definition); 2394 2395 if (dump_file) 2396 fprintf (dump_file, "Symbol added: %s (tree: %p)\n", 2397 node->dump_asm_name (), (void *) node->decl); 2398 2399 if (is_a<cgraph_node *> (node)) 2400 { 2401 cgraph_node *cnode = dyn_cast <cgraph_node *> (node); 2402 2403 sem_function *fn = new sem_function (cnode, &m_bmstack); 2404 fn->set_hash (hash); 2405 m_items.safe_push (fn); 2406 } 2407 else 2408 { 2409 varpool_node *vnode = dyn_cast <varpool_node *> (node); 2410 2411 sem_variable *var = new sem_variable (vnode, &m_bmstack); 2412 var->set_hash (hash); 2413 m_items.safe_push (var); 2414 } 2415 } 2416 2417 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data, 2418 len); 2419 lto_data_in_delete (data_in); 2420 } 2421 2422 /* Read IPA ICF summary for symbols. */ 2423 2424 void 2425 sem_item_optimizer::read_summary (void) 2426 { 2427 lto_file_decl_data **file_data_vec = lto_get_file_decl_data (); 2428 lto_file_decl_data *file_data; 2429 unsigned int j = 0; 2430 2431 while ((file_data = file_data_vec[j++])) 2432 { 2433 size_t len; 2434 const char *data = lto_get_section_data (file_data, 2435 LTO_section_ipa_icf, NULL, &len); 2436 2437 if (data) 2438 read_section (file_data, data, len); 2439 } 2440 } 2441 2442 /* Register callgraph and varpool hooks. */ 2443 2444 void 2445 sem_item_optimizer::register_hooks (void) 2446 { 2447 if (!m_cgraph_node_hooks) 2448 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook 2449 (&sem_item_optimizer::cgraph_removal_hook, this); 2450 2451 if (!m_varpool_node_hooks) 2452 m_varpool_node_hooks = symtab->add_varpool_removal_hook 2453 (&sem_item_optimizer::varpool_removal_hook, this); 2454 } 2455 2456 /* Unregister callgraph and varpool hooks. */ 2457 2458 void 2459 sem_item_optimizer::unregister_hooks (void) 2460 { 2461 if (m_cgraph_node_hooks) 2462 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks); 2463 2464 if (m_varpool_node_hooks) 2465 symtab->remove_varpool_removal_hook (m_varpool_node_hooks); 2466 } 2467 2468 /* Adds a CLS to hashtable associated by hash value. */ 2469 2470 void 2471 sem_item_optimizer::add_class (congruence_class *cls) 2472 { 2473 gcc_assert (cls->members.length ()); 2474 2475 congruence_class_group *group 2476 = get_group_by_hash (cls->members[0]->get_hash (), 2477 cls->members[0]->type); 2478 group->classes.safe_push (cls); 2479 } 2480 2481 /* Gets a congruence class group based on given HASH value and TYPE. */ 2482 2483 congruence_class_group * 2484 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type) 2485 { 2486 congruence_class_group *item = XNEW (congruence_class_group); 2487 item->hash = hash; 2488 item->type = type; 2489 2490 congruence_class_group **slot = m_classes.find_slot (item, INSERT); 2491 2492 if (*slot) 2493 free (item); 2494 else 2495 { 2496 item->classes.create (1); 2497 *slot = item; 2498 } 2499 2500 return *slot; 2501 } 2502 2503 /* Callgraph removal hook called for a NODE with a custom DATA. */ 2504 2505 void 2506 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data) 2507 { 2508 sem_item_optimizer *optimizer = (sem_item_optimizer *) data; 2509 optimizer->remove_symtab_node (node); 2510 } 2511 2512 /* Varpool removal hook called for a NODE with a custom DATA. */ 2513 2514 void 2515 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data) 2516 { 2517 sem_item_optimizer *optimizer = (sem_item_optimizer *) data; 2518 optimizer->remove_symtab_node (node); 2519 } 2520 2521 /* Remove symtab NODE triggered by symtab removal hooks. */ 2522 2523 void 2524 sem_item_optimizer::remove_symtab_node (symtab_node *node) 2525 { 2526 gcc_assert (!m_classes.elements ()); 2527 2528 m_removed_items_set.add (node); 2529 } 2530 2531 void 2532 sem_item_optimizer::remove_item (sem_item *item) 2533 { 2534 if (m_symtab_node_map.get (item->node)) 2535 m_symtab_node_map.remove (item->node); 2536 delete item; 2537 } 2538 2539 /* Removes all callgraph and varpool nodes that are marked by symtab 2540 as deleted. */ 2541 2542 void 2543 sem_item_optimizer::filter_removed_items (void) 2544 { 2545 auto_vec <sem_item *> filtered; 2546 2547 for (unsigned int i = 0; i < m_items.length(); i++) 2548 { 2549 sem_item *item = m_items[i]; 2550 2551 if (m_removed_items_set.contains (item->node)) 2552 { 2553 remove_item (item); 2554 continue; 2555 } 2556 2557 if (item->type == FUNC) 2558 { 2559 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node (); 2560 2561 if (in_lto_p && (cnode->alias || cnode->body_removed)) 2562 remove_item (item); 2563 else 2564 filtered.safe_push (item); 2565 } 2566 else /* VAR. */ 2567 { 2568 if (!flag_ipa_icf_variables) 2569 remove_item (item); 2570 else 2571 { 2572 /* Filter out non-readonly variables. */ 2573 tree decl = item->decl; 2574 if (TREE_READONLY (decl)) 2575 filtered.safe_push (item); 2576 else 2577 remove_item (item); 2578 } 2579 } 2580 } 2581 2582 /* Clean-up of released semantic items. */ 2583 2584 m_items.release (); 2585 for (unsigned int i = 0; i < filtered.length(); i++) 2586 m_items.safe_push (filtered[i]); 2587 } 2588 2589 /* Optimizer entry point which returns true in case it processes 2590 a merge operation. True is returned if there's a merge operation 2591 processed. */ 2592 2593 bool 2594 sem_item_optimizer::execute (void) 2595 { 2596 filter_removed_items (); 2597 unregister_hooks (); 2598 2599 build_graph (); 2600 update_hash_by_addr_refs (); 2601 build_hash_based_classes (); 2602 2603 if (dump_file) 2604 fprintf (dump_file, "Dump after hash based groups\n"); 2605 dump_cong_classes (); 2606 2607 for (unsigned int i = 0; i < m_items.length(); i++) 2608 m_items[i]->init_wpa (); 2609 2610 subdivide_classes_by_equality (true); 2611 2612 if (dump_file) 2613 fprintf (dump_file, "Dump after WPA based types groups\n"); 2614 2615 dump_cong_classes (); 2616 2617 process_cong_reduction (); 2618 checking_verify_classes (); 2619 2620 if (dump_file) 2621 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n"); 2622 2623 dump_cong_classes (); 2624 2625 parse_nonsingleton_classes (); 2626 subdivide_classes_by_equality (); 2627 2628 if (dump_file) 2629 fprintf (dump_file, "Dump after full equality comparison of groups\n"); 2630 2631 dump_cong_classes (); 2632 2633 unsigned int prev_class_count = m_classes_count; 2634 2635 process_cong_reduction (); 2636 dump_cong_classes (); 2637 checking_verify_classes (); 2638 bool merged_p = merge_classes (prev_class_count); 2639 2640 if (dump_file && (dump_flags & TDF_DETAILS)) 2641 symtab->dump (dump_file); 2642 2643 return merged_p; 2644 } 2645 2646 /* Function responsible for visiting all potential functions and 2647 read-only variables that can be merged. */ 2648 2649 void 2650 sem_item_optimizer::parse_funcs_and_vars (void) 2651 { 2652 cgraph_node *cnode; 2653 2654 if (flag_ipa_icf_functions) 2655 FOR_EACH_DEFINED_FUNCTION (cnode) 2656 { 2657 sem_function *f = sem_function::parse (cnode, &m_bmstack); 2658 if (f) 2659 { 2660 m_items.safe_push (f); 2661 m_symtab_node_map.put (cnode, f); 2662 2663 if (dump_file) 2664 fprintf (dump_file, "Parsed function:%s\n", f->node->asm_name ()); 2665 2666 if (dump_file && (dump_flags & TDF_DETAILS)) 2667 f->dump_to_file (dump_file); 2668 } 2669 else if (dump_file) 2670 fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ()); 2671 } 2672 2673 varpool_node *vnode; 2674 2675 if (flag_ipa_icf_variables) 2676 FOR_EACH_DEFINED_VARIABLE (vnode) 2677 { 2678 sem_variable *v = sem_variable::parse (vnode, &m_bmstack); 2679 2680 if (v) 2681 { 2682 m_items.safe_push (v); 2683 m_symtab_node_map.put (vnode, v); 2684 } 2685 } 2686 } 2687 2688 /* Makes pairing between a congruence class CLS and semantic ITEM. */ 2689 2690 void 2691 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item) 2692 { 2693 item->index_in_class = cls->members.length (); 2694 cls->members.safe_push (item); 2695 item->cls = cls; 2696 } 2697 2698 /* For each semantic item, append hash values of references. */ 2699 2700 void 2701 sem_item_optimizer::update_hash_by_addr_refs () 2702 { 2703 /* First, append to hash sensitive references and class type if it need to 2704 be matched for ODR. */ 2705 for (unsigned i = 0; i < m_items.length (); i++) 2706 { 2707 m_items[i]->update_hash_by_addr_refs (m_symtab_node_map); 2708 if (m_items[i]->type == FUNC) 2709 { 2710 if (TREE_CODE (TREE_TYPE (m_items[i]->decl)) == METHOD_TYPE 2711 && contains_polymorphic_type_p 2712 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl))) 2713 && (DECL_CXX_CONSTRUCTOR_P (m_items[i]->decl) 2714 || (static_cast<sem_function *> (m_items[i])->param_used_p (0) 2715 && static_cast<sem_function *> (m_items[i]) 2716 ->compare_polymorphic_p ()))) 2717 { 2718 tree class_type 2719 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl)); 2720 inchash::hash hstate (m_items[i]->get_hash ()); 2721 2722 if (TYPE_NAME (class_type) 2723 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type))) 2724 hstate.add_hwi 2725 (IDENTIFIER_HASH_VALUE 2726 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type)))); 2727 2728 m_items[i]->set_hash (hstate.end ()); 2729 } 2730 } 2731 } 2732 2733 /* Once all symbols have enhanced hash value, we can append 2734 hash values of symbols that are seen by IPA ICF and are 2735 references by a semantic item. Newly computed values 2736 are saved to global_hash member variable. */ 2737 for (unsigned i = 0; i < m_items.length (); i++) 2738 m_items[i]->update_hash_by_local_refs (m_symtab_node_map); 2739 2740 /* Global hash value replace current hash values. */ 2741 for (unsigned i = 0; i < m_items.length (); i++) 2742 m_items[i]->set_hash (m_items[i]->global_hash); 2743 } 2744 2745 /* Congruence classes are built by hash value. */ 2746 2747 void 2748 sem_item_optimizer::build_hash_based_classes (void) 2749 { 2750 for (unsigned i = 0; i < m_items.length (); i++) 2751 { 2752 sem_item *item = m_items[i]; 2753 2754 congruence_class_group *group 2755 = get_group_by_hash (item->get_hash (), item->type); 2756 2757 if (!group->classes.length ()) 2758 { 2759 m_classes_count++; 2760 group->classes.safe_push (new congruence_class (class_id++)); 2761 } 2762 2763 add_item_to_class (group->classes[0], item); 2764 } 2765 } 2766 2767 /* Build references according to call graph. */ 2768 2769 void 2770 sem_item_optimizer::build_graph (void) 2771 { 2772 for (unsigned i = 0; i < m_items.length (); i++) 2773 { 2774 sem_item *item = m_items[i]; 2775 m_symtab_node_map.put (item->node, item); 2776 2777 /* Initialize hash values if we are not in LTO mode. */ 2778 if (!in_lto_p) 2779 item->get_hash (); 2780 } 2781 2782 for (unsigned i = 0; i < m_items.length (); i++) 2783 { 2784 sem_item *item = m_items[i]; 2785 2786 if (item->type == FUNC) 2787 { 2788 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node); 2789 2790 cgraph_edge *e = cnode->callees; 2791 while (e) 2792 { 2793 sem_item **slot = m_symtab_node_map.get 2794 (e->callee->ultimate_alias_target ()); 2795 if (slot) 2796 item->add_reference (*slot); 2797 2798 e = e->next_callee; 2799 } 2800 } 2801 2802 ipa_ref *ref = NULL; 2803 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++) 2804 { 2805 sem_item **slot = m_symtab_node_map.get 2806 (ref->referred->ultimate_alias_target ()); 2807 if (slot) 2808 item->add_reference (*slot); 2809 } 2810 } 2811 } 2812 2813 /* Semantic items in classes having more than one element and initialized. 2814 In case of WPA, we load function body. */ 2815 2816 void 2817 sem_item_optimizer::parse_nonsingleton_classes (void) 2818 { 2819 unsigned int init_called_count = 0; 2820 2821 for (unsigned i = 0; i < m_items.length (); i++) 2822 if (m_items[i]->cls->members.length () > 1) 2823 { 2824 m_items[i]->init (); 2825 init_called_count++; 2826 } 2827 2828 if (dump_file) 2829 fprintf (dump_file, "Init called for %u items (%.2f%%).\n", 2830 init_called_count, 2831 m_items.length () ? 100.0f * init_called_count / m_items.length () 2832 : 0.0f); 2833 } 2834 2835 /* Equality function for semantic items is used to subdivide existing 2836 classes. If IN_WPA, fast equality function is invoked. */ 2837 2838 void 2839 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa) 2840 { 2841 for (hash_table <congruence_class_hash>::iterator it = m_classes.begin (); 2842 it != m_classes.end (); ++it) 2843 { 2844 unsigned int class_count = (*it)->classes.length (); 2845 2846 for (unsigned i = 0; i < class_count; i++) 2847 { 2848 congruence_class *c = (*it)->classes[i]; 2849 2850 if (c->members.length() > 1) 2851 { 2852 auto_vec <sem_item *> new_vector; 2853 2854 sem_item *first = c->members[0]; 2855 new_vector.safe_push (first); 2856 2857 unsigned class_split_first = (*it)->classes.length (); 2858 2859 for (unsigned j = 1; j < c->members.length (); j++) 2860 { 2861 sem_item *item = c->members[j]; 2862 2863 bool equals 2864 = in_wpa ? first->equals_wpa (item, m_symtab_node_map) 2865 : first->equals (item, m_symtab_node_map); 2866 2867 if (equals) 2868 new_vector.safe_push (item); 2869 else 2870 { 2871 bool integrated = false; 2872 2873 for (unsigned k = class_split_first; 2874 k < (*it)->classes.length (); k++) 2875 { 2876 sem_item *x = (*it)->classes[k]->members[0]; 2877 bool equals 2878 = in_wpa ? x->equals_wpa (item, m_symtab_node_map) 2879 : x->equals (item, m_symtab_node_map); 2880 2881 if (equals) 2882 { 2883 integrated = true; 2884 add_item_to_class ((*it)->classes[k], item); 2885 2886 break; 2887 } 2888 } 2889 2890 if (!integrated) 2891 { 2892 congruence_class *c 2893 = new congruence_class (class_id++); 2894 m_classes_count++; 2895 add_item_to_class (c, item); 2896 2897 (*it)->classes.safe_push (c); 2898 } 2899 } 2900 } 2901 2902 // We replace newly created new_vector for the class we've just 2903 // splitted. 2904 c->members.release (); 2905 c->members.create (new_vector.length ()); 2906 2907 for (unsigned int j = 0; j < new_vector.length (); j++) 2908 add_item_to_class (c, new_vector[j]); 2909 } 2910 } 2911 } 2912 2913 checking_verify_classes (); 2914 } 2915 2916 /* Subdivide classes by address references that members of the class 2917 reference. Example can be a pair of functions that have an address 2918 taken from a function. If these addresses are different the class 2919 is split. */ 2920 2921 unsigned 2922 sem_item_optimizer::subdivide_classes_by_sensitive_refs () 2923 { 2924 typedef hash_map <symbol_compare_hash, vec <sem_item *> > subdivide_hash_map; 2925 2926 unsigned newly_created_classes = 0; 2927 2928 for (hash_table <congruence_class_hash>::iterator it = m_classes.begin (); 2929 it != m_classes.end (); ++it) 2930 { 2931 unsigned int class_count = (*it)->classes.length (); 2932 auto_vec<congruence_class *> new_classes; 2933 2934 for (unsigned i = 0; i < class_count; i++) 2935 { 2936 congruence_class *c = (*it)->classes[i]; 2937 2938 if (c->members.length() > 1) 2939 { 2940 subdivide_hash_map split_map; 2941 2942 for (unsigned j = 0; j < c->members.length (); j++) 2943 { 2944 sem_item *source_node = c->members[j]; 2945 2946 symbol_compare_collection *collection 2947 = new symbol_compare_collection (source_node->node); 2948 2949 bool existed; 2950 vec <sem_item *> *slot 2951 = &split_map.get_or_insert (collection, &existed); 2952 gcc_checking_assert (slot); 2953 2954 slot->safe_push (source_node); 2955 2956 if (existed) 2957 delete collection; 2958 } 2959 2960 /* If the map contains more than one key, we have to split 2961 the map appropriately. */ 2962 if (split_map.elements () != 1) 2963 { 2964 bool first_class = true; 2965 2966 for (subdivide_hash_map::iterator it2 = split_map.begin (); 2967 it2 != split_map.end (); ++it2) 2968 { 2969 congruence_class *new_cls; 2970 new_cls = new congruence_class (class_id++); 2971 2972 for (unsigned k = 0; k < (*it2).second.length (); k++) 2973 add_item_to_class (new_cls, (*it2).second[k]); 2974 2975 worklist_push (new_cls); 2976 newly_created_classes++; 2977 2978 if (first_class) 2979 { 2980 (*it)->classes[i] = new_cls; 2981 first_class = false; 2982 } 2983 else 2984 { 2985 new_classes.safe_push (new_cls); 2986 m_classes_count++; 2987 } 2988 } 2989 } 2990 2991 /* Release memory. */ 2992 for (subdivide_hash_map::iterator it2 = split_map.begin (); 2993 it2 != split_map.end (); ++it2) 2994 { 2995 delete (*it2).first; 2996 (*it2).second.release (); 2997 } 2998 } 2999 } 3000 3001 for (unsigned i = 0; i < new_classes.length (); i++) 3002 (*it)->classes.safe_push (new_classes[i]); 3003 } 3004 3005 return newly_created_classes; 3006 } 3007 3008 /* Verify congruence classes, if checking is enabled. */ 3009 3010 void 3011 sem_item_optimizer::checking_verify_classes (void) 3012 { 3013 if (flag_checking) 3014 verify_classes (); 3015 } 3016 3017 /* Verify congruence classes. */ 3018 3019 void 3020 sem_item_optimizer::verify_classes (void) 3021 { 3022 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin (); 3023 it != m_classes.end (); ++it) 3024 { 3025 for (unsigned int i = 0; i < (*it)->classes.length (); i++) 3026 { 3027 congruence_class *cls = (*it)->classes[i]; 3028 3029 gcc_assert (cls); 3030 gcc_assert (cls->members.length () > 0); 3031 3032 for (unsigned int j = 0; j < cls->members.length (); j++) 3033 { 3034 sem_item *item = cls->members[j]; 3035 3036 gcc_assert (item); 3037 gcc_assert (item->cls == cls); 3038 3039 for (unsigned k = 0; k < item->usages.length (); k++) 3040 { 3041 sem_usage_pair *usage = item->usages[k]; 3042 gcc_assert (usage->item->index_in_class 3043 < usage->item->cls->members.length ()); 3044 } 3045 } 3046 } 3047 } 3048 } 3049 3050 /* Disposes split map traverse function. CLS_PTR is pointer to congruence 3051 class, BSLOT is bitmap slot we want to release. DATA is mandatory, 3052 but unused argument. */ 3053 3054 bool 3055 sem_item_optimizer::release_split_map (congruence_class * const &, 3056 bitmap const &b, traverse_split_pair *) 3057 { 3058 bitmap bmp = b; 3059 3060 BITMAP_FREE (bmp); 3061 3062 return true; 3063 } 3064 3065 /* Process split operation for a class given as pointer CLS_PTR, 3066 where bitmap B splits congruence class members. DATA is used 3067 as argument of split pair. */ 3068 3069 bool 3070 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls, 3071 bitmap const &b, 3072 traverse_split_pair *pair) 3073 { 3074 sem_item_optimizer *optimizer = pair->optimizer; 3075 const congruence_class *splitter_cls = pair->cls; 3076 3077 /* If counted bits are greater than zero and less than the number of members 3078 a group will be splitted. */ 3079 unsigned popcount = bitmap_count_bits (b); 3080 3081 if (popcount > 0 && popcount < cls->members.length ()) 3082 { 3083 auto_vec <congruence_class *, 2> newclasses; 3084 newclasses.quick_push (new congruence_class (class_id++)); 3085 newclasses.quick_push (new congruence_class (class_id++)); 3086 3087 for (unsigned int i = 0; i < cls->members.length (); i++) 3088 { 3089 int target = bitmap_bit_p (b, i); 3090 congruence_class *tc = newclasses[target]; 3091 3092 add_item_to_class (tc, cls->members[i]); 3093 } 3094 3095 if (flag_checking) 3096 { 3097 for (unsigned int i = 0; i < 2; i++) 3098 gcc_assert (newclasses[i]->members.length ()); 3099 } 3100 3101 if (splitter_cls == cls) 3102 optimizer->splitter_class_removed = true; 3103 3104 /* Remove old class from worklist if presented. */ 3105 bool in_worklist = cls->in_worklist; 3106 3107 if (in_worklist) 3108 cls->in_worklist = false; 3109 3110 congruence_class_group g; 3111 g.hash = cls->members[0]->get_hash (); 3112 g.type = cls->members[0]->type; 3113 3114 congruence_class_group *slot = optimizer->m_classes.find (&g); 3115 3116 for (unsigned int i = 0; i < slot->classes.length (); i++) 3117 if (slot->classes[i] == cls) 3118 { 3119 slot->classes.ordered_remove (i); 3120 break; 3121 } 3122 3123 /* New class will be inserted and integrated to work list. */ 3124 for (unsigned int i = 0; i < 2; i++) 3125 optimizer->add_class (newclasses[i]); 3126 3127 /* Two classes replace one, so that increment just by one. */ 3128 optimizer->m_classes_count++; 3129 3130 /* If OLD class was presented in the worklist, we remove the class 3131 and replace it will both newly created classes. */ 3132 if (in_worklist) 3133 for (unsigned int i = 0; i < 2; i++) 3134 optimizer->worklist_push (newclasses[i]); 3135 else /* Just smaller class is inserted. */ 3136 { 3137 unsigned int smaller_index 3138 = (newclasses[0]->members.length () 3139 < newclasses[1]->members.length () 3140 ? 0 : 1); 3141 optimizer->worklist_push (newclasses[smaller_index]); 3142 } 3143 3144 if (dump_file && (dump_flags & TDF_DETAILS)) 3145 { 3146 fprintf (dump_file, " congruence class splitted:\n"); 3147 cls->dump (dump_file, 4); 3148 3149 fprintf (dump_file, " newly created groups:\n"); 3150 for (unsigned int i = 0; i < 2; i++) 3151 newclasses[i]->dump (dump_file, 4); 3152 } 3153 3154 /* Release class if not presented in work list. */ 3155 if (!in_worklist) 3156 delete cls; 3157 } 3158 3159 3160 return true; 3161 } 3162 3163 /* Compare function for sorting pairs in do_congruence_step_f. */ 3164 3165 int 3166 sem_item_optimizer::sort_congruence_split (const void *a_, const void *b_) 3167 { 3168 const std::pair<congruence_class *, bitmap> *a 3169 = (const std::pair<congruence_class *, bitmap> *)a_; 3170 const std::pair<congruence_class *, bitmap> *b 3171 = (const std::pair<congruence_class *, bitmap> *)b_; 3172 if (a->first->id < b->first->id) 3173 return -1; 3174 else if (a->first->id > b->first->id) 3175 return 1; 3176 return 0; 3177 } 3178 3179 /* Tests if a class CLS used as INDEXth splits any congruence classes. 3180 Bitmap stack BMSTACK is used for bitmap allocation. */ 3181 3182 void 3183 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls, 3184 unsigned int index) 3185 { 3186 hash_map <congruence_class *, bitmap> split_map; 3187 3188 for (unsigned int i = 0; i < cls->members.length (); i++) 3189 { 3190 sem_item *item = cls->members[i]; 3191 3192 /* Iterate all usages that have INDEX as usage of the item. */ 3193 for (unsigned int j = 0; j < item->usages.length (); j++) 3194 { 3195 sem_usage_pair *usage = item->usages[j]; 3196 3197 if (usage->index != index) 3198 continue; 3199 3200 bitmap *slot = split_map.get (usage->item->cls); 3201 bitmap b; 3202 3203 if(!slot) 3204 { 3205 b = BITMAP_ALLOC (&m_bmstack); 3206 split_map.put (usage->item->cls, b); 3207 } 3208 else 3209 b = *slot; 3210 3211 gcc_checking_assert (usage->item->cls); 3212 gcc_checking_assert (usage->item->index_in_class 3213 < usage->item->cls->members.length ()); 3214 3215 bitmap_set_bit (b, usage->item->index_in_class); 3216 } 3217 } 3218 3219 auto_vec<std::pair<congruence_class *, bitmap> > to_split; 3220 to_split.reserve_exact (split_map.elements ()); 3221 for (hash_map <congruence_class *, bitmap>::iterator i = split_map.begin (); 3222 i != split_map.end (); ++i) 3223 to_split.safe_push (*i); 3224 to_split.qsort (sort_congruence_split); 3225 3226 traverse_split_pair pair; 3227 pair.optimizer = this; 3228 pair.cls = cls; 3229 3230 splitter_class_removed = false; 3231 for (unsigned i = 0; i < to_split.length (); ++i) 3232 traverse_congruence_split (to_split[i].first, to_split[i].second, &pair); 3233 3234 /* Bitmap clean-up. */ 3235 split_map.traverse <traverse_split_pair *, 3236 sem_item_optimizer::release_split_map> (NULL); 3237 } 3238 3239 /* Every usage of a congruence class CLS is a candidate that can split the 3240 collection of classes. Bitmap stack BMSTACK is used for bitmap 3241 allocation. */ 3242 3243 void 3244 sem_item_optimizer::do_congruence_step (congruence_class *cls) 3245 { 3246 bitmap_iterator bi; 3247 unsigned int i; 3248 3249 bitmap usage = BITMAP_ALLOC (&m_bmstack); 3250 3251 for (unsigned int i = 0; i < cls->members.length (); i++) 3252 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap); 3253 3254 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi) 3255 { 3256 if (dump_file && (dump_flags & TDF_DETAILS)) 3257 fprintf (dump_file, " processing congruence step for class: %u, " 3258 "index: %u\n", cls->id, i); 3259 3260 do_congruence_step_for_index (cls, i); 3261 3262 if (splitter_class_removed) 3263 break; 3264 } 3265 3266 BITMAP_FREE (usage); 3267 } 3268 3269 /* Adds a newly created congruence class CLS to worklist. */ 3270 3271 void 3272 sem_item_optimizer::worklist_push (congruence_class *cls) 3273 { 3274 /* Return if the class CLS is already presented in work list. */ 3275 if (cls->in_worklist) 3276 return; 3277 3278 cls->in_worklist = true; 3279 worklist.push_back (cls); 3280 } 3281 3282 /* Pops a class from worklist. */ 3283 3284 congruence_class * 3285 sem_item_optimizer::worklist_pop (void) 3286 { 3287 congruence_class *cls; 3288 3289 while (!worklist.empty ()) 3290 { 3291 cls = worklist.front (); 3292 worklist.pop_front (); 3293 if (cls->in_worklist) 3294 { 3295 cls->in_worklist = false; 3296 3297 return cls; 3298 } 3299 else 3300 { 3301 /* Work list item was already intended to be removed. 3302 The only reason for doing it is to split a class. 3303 Thus, the class CLS is deleted. */ 3304 delete cls; 3305 } 3306 } 3307 3308 return NULL; 3309 } 3310 3311 /* Iterative congruence reduction function. */ 3312 3313 void 3314 sem_item_optimizer::process_cong_reduction (void) 3315 { 3316 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin (); 3317 it != m_classes.end (); ++it) 3318 for (unsigned i = 0; i < (*it)->classes.length (); i++) 3319 if ((*it)->classes[i]->is_class_used ()) 3320 worklist_push ((*it)->classes[i]); 3321 3322 if (dump_file) 3323 fprintf (dump_file, "Worklist has been filled with: %lu\n", 3324 (unsigned long) worklist.size ()); 3325 3326 if (dump_file && (dump_flags & TDF_DETAILS)) 3327 fprintf (dump_file, "Congruence class reduction\n"); 3328 3329 congruence_class *cls; 3330 3331 /* Process complete congruence reduction. */ 3332 while ((cls = worklist_pop ()) != NULL) 3333 do_congruence_step (cls); 3334 3335 /* Subdivide newly created classes according to references. */ 3336 unsigned new_classes = subdivide_classes_by_sensitive_refs (); 3337 3338 if (dump_file) 3339 fprintf (dump_file, "Address reference subdivision created: %u " 3340 "new classes.\n", new_classes); 3341 } 3342 3343 /* Debug function prints all informations about congruence classes. */ 3344 3345 void 3346 sem_item_optimizer::dump_cong_classes (void) 3347 { 3348 if (!dump_file) 3349 return; 3350 3351 fprintf (dump_file, 3352 "Congruence classes: %u (unique hash values: %lu), with total: " 3353 "%u items\n", m_classes_count, 3354 (unsigned long) m_classes.elements (), m_items.length ()); 3355 3356 /* Histogram calculation. */ 3357 unsigned int max_index = 0; 3358 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1); 3359 3360 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin (); 3361 it != m_classes.end (); ++it) 3362 for (unsigned i = 0; i < (*it)->classes.length (); i++) 3363 { 3364 unsigned int c = (*it)->classes[i]->members.length (); 3365 histogram[c]++; 3366 3367 if (c > max_index) 3368 max_index = c; 3369 } 3370 3371 fprintf (dump_file, 3372 "Class size histogram [num of members]: number of classe number " 3373 "of classess\n"); 3374 3375 for (unsigned int i = 0; i <= max_index; i++) 3376 if (histogram[i]) 3377 fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]); 3378 3379 fprintf (dump_file, "\n\n"); 3380 3381 if (dump_flags & TDF_DETAILS) 3382 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin (); 3383 it != m_classes.end (); ++it) 3384 { 3385 fprintf (dump_file, " group: with %u classes:\n", 3386 (*it)->classes.length ()); 3387 3388 for (unsigned i = 0; i < (*it)->classes.length (); i++) 3389 { 3390 (*it)->classes[i]->dump (dump_file, 4); 3391 3392 if (i < (*it)->classes.length () - 1) 3393 fprintf (dump_file, " "); 3394 } 3395 } 3396 3397 free (histogram); 3398 } 3399 3400 /* Sort pair of sem_items A and B by DECL_UID. */ 3401 3402 static int 3403 sort_sem_items_by_decl_uid (const void *a, const void *b) 3404 { 3405 const sem_item *i1 = *(const sem_item * const *)a; 3406 const sem_item *i2 = *(const sem_item * const *)b; 3407 3408 int uid1 = DECL_UID (i1->decl); 3409 int uid2 = DECL_UID (i2->decl); 3410 3411 if (uid1 < uid2) 3412 return -1; 3413 else if (uid1 > uid2) 3414 return 1; 3415 else 3416 return 0; 3417 } 3418 3419 /* Sort pair of congruence_classes A and B by DECL_UID of the first member. */ 3420 3421 static int 3422 sort_congruence_classes_by_decl_uid (const void *a, const void *b) 3423 { 3424 const congruence_class *c1 = *(const congruence_class * const *)a; 3425 const congruence_class *c2 = *(const congruence_class * const *)b; 3426 3427 int uid1 = DECL_UID (c1->members[0]->decl); 3428 int uid2 = DECL_UID (c2->members[0]->decl); 3429 3430 if (uid1 < uid2) 3431 return -1; 3432 else if (uid1 > uid2) 3433 return 1; 3434 else 3435 return 0; 3436 } 3437 3438 /* Sort pair of congruence_class_groups A and B by 3439 DECL_UID of the first member of a first group. */ 3440 3441 static int 3442 sort_congruence_class_groups_by_decl_uid (const void *a, const void *b) 3443 { 3444 const congruence_class_group *g1 3445 = *(const congruence_class_group * const *)a; 3446 const congruence_class_group *g2 3447 = *(const congruence_class_group * const *)b; 3448 3449 int uid1 = DECL_UID (g1->classes[0]->members[0]->decl); 3450 int uid2 = DECL_UID (g2->classes[0]->members[0]->decl); 3451 3452 if (uid1 < uid2) 3453 return -1; 3454 else if (uid1 > uid2) 3455 return 1; 3456 else 3457 return 0; 3458 } 3459 3460 /* After reduction is done, we can declare all items in a group 3461 to be equal. PREV_CLASS_COUNT is start number of classes 3462 before reduction. True is returned if there's a merge operation 3463 processed. */ 3464 3465 bool 3466 sem_item_optimizer::merge_classes (unsigned int prev_class_count) 3467 { 3468 unsigned int item_count = m_items.length (); 3469 unsigned int class_count = m_classes_count; 3470 unsigned int equal_items = item_count - class_count; 3471 3472 unsigned int non_singular_classes_count = 0; 3473 unsigned int non_singular_classes_sum = 0; 3474 3475 bool merged_p = false; 3476 3477 /* PR lto/78211 3478 Sort functions in congruence classes by DECL_UID and do the same 3479 for the classes to not to break -fcompare-debug. */ 3480 3481 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin (); 3482 it != m_classes.end (); ++it) 3483 { 3484 for (unsigned int i = 0; i < (*it)->classes.length (); i++) 3485 { 3486 congruence_class *c = (*it)->classes[i]; 3487 c->members.qsort (sort_sem_items_by_decl_uid); 3488 } 3489 3490 (*it)->classes.qsort (sort_congruence_classes_by_decl_uid); 3491 } 3492 3493 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin (); 3494 it != m_classes.end (); ++it) 3495 for (unsigned int i = 0; i < (*it)->classes.length (); i++) 3496 { 3497 congruence_class *c = (*it)->classes[i]; 3498 if (c->members.length () > 1) 3499 { 3500 non_singular_classes_count++; 3501 non_singular_classes_sum += c->members.length (); 3502 } 3503 } 3504 3505 auto_vec <congruence_class_group *> classes (m_classes.elements ()); 3506 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin (); 3507 it != m_classes.end (); ++it) 3508 classes.quick_push (*it); 3509 3510 classes.qsort (sort_congruence_class_groups_by_decl_uid); 3511 3512 if (dump_file) 3513 { 3514 fprintf (dump_file, "\nItem count: %u\n", item_count); 3515 fprintf (dump_file, "Congruent classes before: %u, after: %u\n", 3516 prev_class_count, class_count); 3517 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n", 3518 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f, 3519 class_count ? 1.0f * item_count / class_count : 0.0f); 3520 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n", 3521 non_singular_classes_count ? 1.0f * non_singular_classes_sum / 3522 non_singular_classes_count : 0.0f, 3523 non_singular_classes_count); 3524 fprintf (dump_file, "Equal symbols: %u\n", equal_items); 3525 fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n", 3526 item_count ? 100.0f * equal_items / item_count : 0.0f); 3527 } 3528 3529 unsigned int l; 3530 congruence_class_group *it; 3531 FOR_EACH_VEC_ELT (classes, l, it) 3532 for (unsigned int i = 0; i < it->classes.length (); i++) 3533 { 3534 congruence_class *c = it->classes[i]; 3535 3536 if (c->members.length () == 1) 3537 continue; 3538 3539 sem_item *source = c->members[0]; 3540 3541 if (DECL_NAME (source->decl) 3542 && MAIN_NAME_P (DECL_NAME (source->decl))) 3543 /* If merge via wrappers, picking main as the target can be 3544 problematic. */ 3545 source = c->members[1]; 3546 3547 for (unsigned int j = 0; j < c->members.length (); j++) 3548 { 3549 sem_item *alias = c->members[j]; 3550 3551 if (alias == source) 3552 continue; 3553 3554 if (dump_file) 3555 { 3556 fprintf (dump_file, "Semantic equality hit:%s->%s\n", 3557 xstrdup_for_dump (source->node->name ()), 3558 xstrdup_for_dump (alias->node->name ())); 3559 fprintf (dump_file, "Assembler symbol names:%s->%s\n", 3560 xstrdup_for_dump (source->node->asm_name ()), 3561 xstrdup_for_dump (alias->node->asm_name ())); 3562 } 3563 3564 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl))) 3565 { 3566 if (dump_file) 3567 fprintf (dump_file, 3568 "Merge operation is skipped due to no_icf " 3569 "attribute.\n\n"); 3570 3571 continue; 3572 } 3573 3574 if (dump_file && (dump_flags & TDF_DETAILS)) 3575 { 3576 source->dump_to_file (dump_file); 3577 alias->dump_to_file (dump_file); 3578 } 3579 3580 if (dbg_cnt (merged_ipa_icf)) 3581 { 3582 bool merged = source->merge (alias); 3583 merged_p |= merged; 3584 3585 if (merged && alias->type == VAR) 3586 { 3587 symtab_pair p = symtab_pair (source->node, alias->node); 3588 m_merged_variables.safe_push (p); 3589 } 3590 } 3591 } 3592 } 3593 3594 if (!m_merged_variables.is_empty ()) 3595 fixup_points_to_sets (); 3596 3597 return merged_p; 3598 } 3599 3600 /* Fixup points to set PT. */ 3601 3602 void 3603 sem_item_optimizer::fixup_pt_set (struct pt_solution *pt) 3604 { 3605 if (pt->vars == NULL) 3606 return; 3607 3608 unsigned i; 3609 symtab_pair *item; 3610 FOR_EACH_VEC_ELT (m_merged_variables, i, item) 3611 if (bitmap_bit_p (pt->vars, DECL_UID (item->second->decl))) 3612 bitmap_set_bit (pt->vars, DECL_UID (item->first->decl)); 3613 } 3614 3615 /* Set all points-to UIDs of aliases pointing to node N as UID. */ 3616 3617 static void 3618 set_alias_uids (symtab_node *n, int uid) 3619 { 3620 ipa_ref *ref; 3621 FOR_EACH_ALIAS (n, ref) 3622 { 3623 if (dump_file) 3624 fprintf (dump_file, " Setting points-to UID of [%s] as %d\n", 3625 xstrdup_for_dump (ref->referring->asm_name ()), uid); 3626 3627 SET_DECL_PT_UID (ref->referring->decl, uid); 3628 set_alias_uids (ref->referring, uid); 3629 } 3630 } 3631 3632 /* Fixup points to analysis info. */ 3633 3634 void 3635 sem_item_optimizer::fixup_points_to_sets (void) 3636 { 3637 /* TODO: remove in GCC 9 and trigger PTA re-creation after IPA passes. */ 3638 cgraph_node *cnode; 3639 3640 FOR_EACH_DEFINED_FUNCTION (cnode) 3641 { 3642 tree name; 3643 unsigned i; 3644 function *fn = DECL_STRUCT_FUNCTION (cnode->decl); 3645 if (!gimple_in_ssa_p (fn)) 3646 continue; 3647 3648 FOR_EACH_SSA_NAME (i, name, fn) 3649 if (POINTER_TYPE_P (TREE_TYPE (name)) 3650 && SSA_NAME_PTR_INFO (name)) 3651 fixup_pt_set (&SSA_NAME_PTR_INFO (name)->pt); 3652 fixup_pt_set (&fn->gimple_df->escaped); 3653 3654 /* The above get's us to 99% I guess, at least catching the 3655 address compares. Below also gets us aliasing correct 3656 but as said we're giving leeway to the situation with 3657 readonly vars anyway, so ... */ 3658 basic_block bb; 3659 FOR_EACH_BB_FN (bb, fn) 3660 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); 3661 gsi_next (&gsi)) 3662 { 3663 gcall *call = dyn_cast<gcall *> (gsi_stmt (gsi)); 3664 if (call) 3665 { 3666 fixup_pt_set (gimple_call_use_set (call)); 3667 fixup_pt_set (gimple_call_clobber_set (call)); 3668 } 3669 } 3670 } 3671 3672 unsigned i; 3673 symtab_pair *item; 3674 FOR_EACH_VEC_ELT (m_merged_variables, i, item) 3675 set_alias_uids (item->first, DECL_UID (item->first->decl)); 3676 } 3677 3678 /* Dump function prints all class members to a FILE with an INDENT. */ 3679 3680 void 3681 congruence_class::dump (FILE *file, unsigned int indent) const 3682 { 3683 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n", 3684 id, members[0]->get_hash (), members.length ()); 3685 3686 FPUTS_SPACES (file, indent + 2, ""); 3687 for (unsigned i = 0; i < members.length (); i++) 3688 fprintf (file, "%s ", members[i]->node->dump_asm_name ()); 3689 3690 fprintf (file, "\n"); 3691 } 3692 3693 /* Returns true if there's a member that is used from another group. */ 3694 3695 bool 3696 congruence_class::is_class_used (void) 3697 { 3698 for (unsigned int i = 0; i < members.length (); i++) 3699 if (members[i]->usages.length ()) 3700 return true; 3701 3702 return false; 3703 } 3704 3705 /* Generate pass summary for IPA ICF pass. */ 3706 3707 static void 3708 ipa_icf_generate_summary (void) 3709 { 3710 if (!optimizer) 3711 optimizer = new sem_item_optimizer (); 3712 3713 optimizer->register_hooks (); 3714 optimizer->parse_funcs_and_vars (); 3715 } 3716 3717 /* Write pass summary for IPA ICF pass. */ 3718 3719 static void 3720 ipa_icf_write_summary (void) 3721 { 3722 gcc_assert (optimizer); 3723 3724 optimizer->write_summary (); 3725 } 3726 3727 /* Read pass summary for IPA ICF pass. */ 3728 3729 static void 3730 ipa_icf_read_summary (void) 3731 { 3732 if (!optimizer) 3733 optimizer = new sem_item_optimizer (); 3734 3735 optimizer->read_summary (); 3736 optimizer->register_hooks (); 3737 } 3738 3739 /* Semantic equality exection function. */ 3740 3741 static unsigned int 3742 ipa_icf_driver (void) 3743 { 3744 gcc_assert (optimizer); 3745 3746 bool merged_p = optimizer->execute (); 3747 3748 delete optimizer; 3749 optimizer = NULL; 3750 3751 return merged_p ? TODO_remove_functions : 0; 3752 } 3753 3754 const pass_data pass_data_ipa_icf = 3755 { 3756 IPA_PASS, /* type */ 3757 "icf", /* name */ 3758 OPTGROUP_IPA, /* optinfo_flags */ 3759 TV_IPA_ICF, /* tv_id */ 3760 0, /* properties_required */ 3761 0, /* properties_provided */ 3762 0, /* properties_destroyed */ 3763 0, /* todo_flags_start */ 3764 0, /* todo_flags_finish */ 3765 }; 3766 3767 class pass_ipa_icf : public ipa_opt_pass_d 3768 { 3769 public: 3770 pass_ipa_icf (gcc::context *ctxt) 3771 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt, 3772 ipa_icf_generate_summary, /* generate_summary */ 3773 ipa_icf_write_summary, /* write_summary */ 3774 ipa_icf_read_summary, /* read_summary */ 3775 NULL, /* 3776 write_optimization_summary */ 3777 NULL, /* 3778 read_optimization_summary */ 3779 NULL, /* stmt_fixup */ 3780 0, /* function_transform_todo_flags_start */ 3781 NULL, /* function_transform */ 3782 NULL) /* variable_transform */ 3783 {} 3784 3785 /* opt_pass methods: */ 3786 virtual bool gate (function *) 3787 { 3788 return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions; 3789 } 3790 3791 virtual unsigned int execute (function *) 3792 { 3793 return ipa_icf_driver(); 3794 } 3795 }; // class pass_ipa_icf 3796 3797 } // ipa_icf namespace 3798 3799 ipa_opt_pass_d * 3800 make_pass_ipa_icf (gcc::context *ctxt) 3801 { 3802 return new ipa_icf::pass_ipa_icf (ctxt); 3803 } 3804