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