gcc/ipa-icf.c

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