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