Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / 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 "coretypes.h"
57 #include "hash-set.h"
58 #include "machmode.h"
59 #include "vec.h"
60 #include "double-int.h"
61 #include "input.h"
62 #include "alias.h"
63 #include "symtab.h"
64 #include "options.h"
65 #include "wide-int.h"
66 #include "inchash.h"
67 #include "tree.h"
68 #include "fold-const.h"
69 #include "predict.h"
70 #include "tm.h"
71 #include "hard-reg-set.h"
72 #include "function.h"
73 #include "dominance.h"
74 #include "cfg.h"
75 #include "basic-block.h"
76 #include "tree-ssa-alias.h"
77 #include "internal-fn.h"
78 #include "gimple-expr.h"
79 #include "is-a.h"
80 #include "gimple.h"
81 #include "hashtab.h"
82 #include "rtl.h"
83 #include "flags.h"
84 #include "statistics.h"
85 #include "real.h"
86 #include "fixed-value.h"
87 #include "insn-config.h"
88 #include "expmed.h"
89 #include "dojump.h"
90 #include "explow.h"
91 #include "calls.h"
92 #include "emit-rtl.h"
93 #include "varasm.h"
94 #include "stmt.h"
95 #include "expr.h"
96 #include "gimple-iterator.h"
97 #include "gimple-ssa.h"
98 #include "tree-cfg.h"
99 #include "tree-phinodes.h"
100 #include "stringpool.h"
101 #include "tree-ssanames.h"
102 #include "tree-dfa.h"
103 #include "tree-pass.h"
104 #include "gimple-pretty-print.h"
105 #include "hash-map.h"
106 #include "plugin-api.h"
107 #include "ipa-ref.h"
108 #include "cgraph.h"
109 #include "alloc-pool.h"
110 #include "symbol-summary.h"
111 #include "ipa-prop.h"
112 #include "ipa-inline.h"
113 #include "cfgloop.h"
114 #include "except.h"
115 #include "hash-table.h"
116 #include "coverage.h"
117 #include "attribs.h"
118 #include "print-tree.h"
119 #include "lto-streamer.h"
120 #include "data-streamer.h"
121 #include "ipa-utils.h"
122 #include <list>
123 #include "ipa-icf-gimple.h"
124 #include "ipa-icf.h"
125
126 using namespace ipa_icf_gimple;
127
128 namespace ipa_icf {
129 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target.  */
130
131 sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index):
132   item (_item), index (_index)
133 {
134 }
135
136 /* Semantic item constructor for a node of _TYPE, where STACK is used
137    for bitmap memory allocation.  */
138
139 sem_item::sem_item (sem_item_type _type,
140                     bitmap_obstack *stack): type(_type), hash(0)
141 {
142   setup (stack);
143 }
144
145 /* Semantic item constructor for a node of _TYPE, where STACK is used
146    for bitmap memory allocation. The item is based on symtab node _NODE
147    with computed _HASH.  */
148
149 sem_item::sem_item (sem_item_type _type, symtab_node *_node,
150                     hashval_t _hash, bitmap_obstack *stack): type(_type),
151   node (_node), hash (_hash)
152 {
153   decl = node->decl;
154   setup (stack);
155 }
156
157 /* Add reference to a semantic TARGET.  */
158
159 void
160 sem_item::add_reference (sem_item *target)
161 {
162   refs.safe_push (target);
163   unsigned index = refs.length ();
164   target->usages.safe_push (new sem_usage_pair(this, index));
165   bitmap_set_bit (target->usage_index_bitmap, index);
166   refs_set.add (target->node);
167 }
168
169 /* Initialize internal data structures. Bitmap STACK is used for
170    bitmap memory allocation process.  */
171
172 void
173 sem_item::setup (bitmap_obstack *stack)
174 {
175   gcc_checking_assert (node);
176
177   refs.create (0);
178   tree_refs.create (0);
179   usages.create (0);
180   usage_index_bitmap = BITMAP_ALLOC (stack);
181 }
182
183 sem_item::~sem_item ()
184 {
185   for (unsigned i = 0; i < usages.length (); i++)
186     delete usages[i];
187
188   refs.release ();
189   tree_refs.release ();
190   usages.release ();
191
192   BITMAP_FREE (usage_index_bitmap);
193 }
194
195 /* Dump function for debugging purpose.  */
196
197 DEBUG_FUNCTION void
198 sem_item::dump (void)
199 {
200   if (dump_file)
201     {
202       fprintf (dump_file, "[%s] %s (%u) (tree:%p)\n", type == FUNC ? "func" : "var",
203                name(), node->order, (void *) node->decl);
204       fprintf (dump_file, "  hash: %u\n", get_hash ());
205       fprintf (dump_file, "  references: ");
206
207       for (unsigned i = 0; i < refs.length (); i++)
208         fprintf (dump_file, "%s%s ", refs[i]->name (),
209                  i < refs.length() - 1 ? "," : "");
210
211       fprintf (dump_file, "\n");
212     }
213 }
214
215 /* Return true if target supports alias symbols.  */
216
217 bool
218 sem_item::target_supports_symbol_aliases_p (void)
219 {
220 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
221   return false;
222 #else
223   return true;
224 #endif
225 }
226
227 /* Semantic function constructor that uses STACK as bitmap memory stack.  */
228
229 sem_function::sem_function (bitmap_obstack *stack): sem_item (FUNC, stack),
230   m_checker (NULL), m_compared_func (NULL)
231 {
232   arg_types.create (0);
233   bb_sizes.create (0);
234   bb_sorted.create (0);
235 }
236
237 /*  Constructor based on callgraph node _NODE with computed hash _HASH.
238     Bitmap STACK is used for memory allocation.  */
239 sem_function::sem_function (cgraph_node *node, hashval_t hash,
240                             bitmap_obstack *stack):
241   sem_item (FUNC, node, hash, stack),
242   m_checker (NULL), m_compared_func (NULL)
243 {
244   arg_types.create (0);
245   bb_sizes.create (0);
246   bb_sorted.create (0);
247 }
248
249 sem_function::~sem_function ()
250 {
251   for (unsigned i = 0; i < bb_sorted.length (); i++)
252     delete (bb_sorted[i]);
253
254   arg_types.release ();
255   bb_sizes.release ();
256   bb_sorted.release ();
257 }
258
259 /* Calculates hash value based on a BASIC_BLOCK.  */
260
261 hashval_t
262 sem_function::get_bb_hash (const sem_bb *basic_block)
263 {
264   inchash::hash hstate;
265
266   hstate.add_int (basic_block->nondbg_stmt_count);
267   hstate.add_int (basic_block->edge_count);
268
269   return hstate.end ();
270 }
271
272 /* References independent hash function.  */
273
274 hashval_t
275 sem_function::get_hash (void)
276 {
277   if(!hash)
278     {
279       inchash::hash hstate;
280       hstate.add_int (177454); /* Random number for function type.  */
281
282       hstate.add_int (arg_count);
283       hstate.add_int (cfg_checksum);
284       hstate.add_int (gcode_hash);
285
286       for (unsigned i = 0; i < bb_sorted.length (); i++)
287         hstate.merge_hash (get_bb_hash (bb_sorted[i]));
288
289       for (unsigned i = 0; i < bb_sizes.length (); i++)
290         hstate.add_int (bb_sizes[i]);
291
292       hash = hstate.end ();
293     }
294
295   return hash;
296 }
297
298 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
299    point to a same function. Comparison can be skipped if IGNORED_NODES
300    contains these nodes.  */
301
302 bool
303 sem_function::compare_cgraph_references (hash_map <symtab_node *, sem_item *>
304     &ignored_nodes,
305     symtab_node *n1, symtab_node *n2)
306 {
307   if (n1 == n2 || (ignored_nodes.get (n1) && ignored_nodes.get (n2)))
308     return true;
309
310   /* TODO: add more precise comparison for weakrefs, etc.  */
311
312   return return_false_with_msg ("different references");
313 }
314
315 /* If cgraph edges E1 and E2 are indirect calls, verify that
316    ECF flags are the same.  */
317
318 bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
319 {
320   if (e1->indirect_info && e2->indirect_info)
321     {
322       int e1_flags = e1->indirect_info->ecf_flags;
323       int e2_flags = e2->indirect_info->ecf_flags;
324
325       if (e1_flags != e2_flags)
326         return return_false_with_msg ("ICF flags are different");
327     }
328   else if (e1->indirect_info || e2->indirect_info)
329     return false;
330
331   return true;
332 }
333
334 /* Fast equality function based on knowledge known in WPA.  */
335
336 bool
337 sem_function::equals_wpa (sem_item *item,
338                           hash_map <symtab_node *, sem_item *> &ignored_nodes)
339 {
340   gcc_assert (item->type == FUNC);
341
342   m_compared_func = static_cast<sem_function *> (item);
343
344   if (arg_types.length () != m_compared_func->arg_types.length ())
345     return return_false_with_msg ("different number of arguments");
346
347   /* Checking types of arguments.  */
348   for (unsigned i = 0; i < arg_types.length (); i++)
349     {
350       /* This guard is here for function pointer with attributes (pr59927.c).  */
351       if (!arg_types[i] || !m_compared_func->arg_types[i])
352         return return_false_with_msg ("NULL argument type");
353
354       /* Polymorphic comparison is executed just for non-leaf functions.  */
355       bool is_not_leaf = get_node ()->callees != NULL
356                          || get_node ()->indirect_calls != NULL;
357
358       if (!func_checker::compatible_types_p (arg_types[i],
359                                              m_compared_func->arg_types[i],
360                                              is_not_leaf, i == 0))
361         return return_false_with_msg ("argument type is different");
362     }
363
364   /* Result type checking.  */
365   if (!func_checker::compatible_types_p (result_type,
366                                          m_compared_func->result_type))
367     return return_false_with_msg ("result types are different");
368
369   if (node->num_references () != item->node->num_references ())
370     return return_false_with_msg ("different number of references");
371
372   ipa_ref *ref = NULL, *ref2 = NULL;
373   for (unsigned i = 0; node->iterate_reference (i, ref); i++)
374     {
375       item->node->iterate_reference (i, ref2);
376
377       if (!compare_cgraph_references (ignored_nodes, ref->referred, ref2->referred))
378         return false;
379     }
380
381   cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
382   cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
383
384   while (e1 && e2)
385     {
386       if (!compare_cgraph_references (ignored_nodes, e1->callee, e2->callee))
387         return false;
388
389       e1 = e1->next_callee;
390       e2 = e2->next_callee;
391     }
392
393   if (e1 || e2)
394     return return_false_with_msg ("different number of edges");
395
396   return true;
397 }
398
399 /* Returns true if the item equals to ITEM given as argument.  */
400
401 bool
402 sem_function::equals (sem_item *item,
403                       hash_map <symtab_node *, sem_item *> &ignored_nodes)
404 {
405   gcc_assert (item->type == FUNC);
406   bool eq = equals_private (item, ignored_nodes);
407
408   if (m_checker != NULL)
409     {
410       delete m_checker;
411       m_checker = NULL;
412     }
413
414   if (dump_file && (dump_flags & TDF_DETAILS))
415     fprintf (dump_file,
416              "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
417              name(), item->name (), node->order, item->node->order, asm_name (),
418              item->asm_name (), eq ? "true" : "false");
419
420   return eq;
421 }
422
423 /* Processes function equality comparison.  */
424
425 bool
426 sem_function::equals_private (sem_item *item,
427                               hash_map <symtab_node *, sem_item *> &ignored_nodes)
428 {
429   if (item->type != FUNC)
430     return false;
431
432   basic_block bb1, bb2;
433   edge e1, e2;
434   edge_iterator ei1, ei2;
435   bool result = true;
436   tree arg1, arg2;
437
438   m_compared_func = static_cast<sem_function *> (item);
439
440   gcc_assert (decl != item->decl);
441
442   if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
443       || edge_count != m_compared_func->edge_count
444       || cfg_checksum != m_compared_func->cfg_checksum)
445     return return_false ();
446
447   if (!equals_wpa (item, ignored_nodes))
448     return false;
449
450   /* Checking function TARGET and OPTIMIZATION flags.  */
451   cl_target_option *tar1 = target_opts_for_fn (decl);
452   cl_target_option *tar2 = target_opts_for_fn (m_compared_func->decl);
453
454   if (tar1 != NULL && tar2 != NULL)
455     {
456       if (!cl_target_option_eq (tar1, tar2))
457         {
458           if (dump_file && (dump_flags & TDF_DETAILS))
459             {
460               fprintf (dump_file, "target flags difference");
461               cl_target_option_print_diff (dump_file, 2, tar1, tar2);
462             }
463
464           return return_false_with_msg ("Target flags are different");
465         }
466     }
467   else if (tar1 != NULL || tar2 != NULL)
468     return return_false_with_msg ("Target flags are different");
469
470   cl_optimization *opt1 = opts_for_fn (decl);
471   cl_optimization *opt2 = opts_for_fn (m_compared_func->decl);
472
473   if (opt1 != NULL && opt2 != NULL)
474     {
475       if (memcmp (opt1, opt2, sizeof(cl_optimization)))
476         {
477           if (dump_file && (dump_flags & TDF_DETAILS))
478             {
479               fprintf (dump_file, "optimization flags difference");
480               cl_optimization_print_diff (dump_file, 2, opt1, opt2);
481             }
482
483           return return_false_with_msg ("optimization flags are different");
484         }
485     }
486   else if (opt1 != NULL || opt2 != NULL)
487     return return_false_with_msg ("optimization flags are different");
488
489   /* Checking function arguments.  */
490   tree decl1 = DECL_ATTRIBUTES (decl);
491   tree decl2 = DECL_ATTRIBUTES (m_compared_func->decl);
492
493   m_checker = new func_checker (decl, m_compared_func->decl,
494                                 compare_polymorphic_p (),
495                                 false,
496                                 &refs_set,
497                                 &m_compared_func->refs_set);
498   while (decl1)
499     {
500       if (decl2 == NULL)
501         return return_false ();
502
503       if (get_attribute_name (decl1) != get_attribute_name (decl2))
504         return return_false ();
505
506       tree attr_value1 = TREE_VALUE (decl1);
507       tree attr_value2 = TREE_VALUE (decl2);
508
509       if (attr_value1 && attr_value2)
510         {
511           bool ret = m_checker->compare_operand (TREE_VALUE (attr_value1),
512                                                  TREE_VALUE (attr_value2));
513           if (!ret)
514             return return_false_with_msg ("attribute values are different");
515         }
516       else if (!attr_value1 && !attr_value2)
517         {}
518       else
519         return return_false ();
520
521       decl1 = TREE_CHAIN (decl1);
522       decl2 = TREE_CHAIN (decl2);
523     }
524
525   if (decl1 != decl2)
526     return return_false();
527
528
529   for (arg1 = DECL_ARGUMENTS (decl),
530        arg2 = DECL_ARGUMENTS (m_compared_func->decl);
531        arg1; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2))
532     if (!m_checker->compare_decl (arg1, arg2))
533       return return_false ();
534
535   /* Fill-up label dictionary.  */
536   for (unsigned i = 0; i < bb_sorted.length (); ++i)
537     {
538       m_checker->parse_labels (bb_sorted[i]);
539       m_checker->parse_labels (m_compared_func->bb_sorted[i]);
540     }
541
542   /* Checking all basic blocks.  */
543   for (unsigned i = 0; i < bb_sorted.length (); ++i)
544     if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
545       return return_false();
546
547   dump_message ("All BBs are equal\n");
548
549   auto_vec <int> bb_dict;
550
551   /* Basic block edges check.  */
552   for (unsigned i = 0; i < bb_sorted.length (); ++i)
553     {
554       bb1 = bb_sorted[i]->bb;
555       bb2 = m_compared_func->bb_sorted[i]->bb;
556
557       ei2 = ei_start (bb2->preds);
558
559       for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
560         {
561           ei_cond (ei2, &e2);
562
563           if (e1->flags != e2->flags)
564             return return_false_with_msg ("flags comparison returns false");
565
566           if (!bb_dict_test (bb_dict, e1->src->index, e2->src->index))
567             return return_false_with_msg ("edge comparison returns false");
568
569           if (!bb_dict_test (bb_dict, e1->dest->index, e2->dest->index))
570             return return_false_with_msg ("BB comparison returns false");
571
572           if (!m_checker->compare_edge (e1, e2))
573             return return_false_with_msg ("edge comparison returns false");
574
575           ei_next (&ei2);
576         }
577     }
578
579   /* Basic block PHI nodes comparison.  */
580   for (unsigned i = 0; i < bb_sorted.length (); i++)
581     if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
582       return return_false_with_msg ("PHI node comparison returns false");
583
584   return result;
585 }
586
587 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
588    be applied.  */
589 bool
590 sem_function::merge (sem_item *alias_item)
591 {
592   gcc_assert (alias_item->type == FUNC);
593
594   sem_function *alias_func = static_cast<sem_function *> (alias_item);
595
596   cgraph_node *original = get_node ();
597   cgraph_node *local_original = original;
598   cgraph_node *alias = alias_func->get_node ();
599   bool original_address_matters;
600   bool alias_address_matters;
601
602   bool create_thunk = false;
603   bool create_alias = false;
604   bool redirect_callers = false;
605   bool original_discardable = false;
606
607   /* Do not attempt to mix functions from different user sections;
608      we do not know what user intends with those.  */
609   if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
610        || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
611       && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
612     {
613       if (dump_file)
614         fprintf (dump_file,
615                  "Not unifying; original and alias are in different sections.\n\n");
616       return false;
617     }
618
619   /* See if original is in a section that can be discarded if the main
620      symbol is not used.  */
621   if (DECL_EXTERNAL (original->decl))
622     original_discardable = true;
623   if (original->resolution == LDPR_PREEMPTED_REG
624       || original->resolution == LDPR_PREEMPTED_IR)
625     original_discardable = true;
626   if (original->can_be_discarded_p ())
627     original_discardable = true;
628
629   /* See if original and/or alias address can be compared for equality.  */
630   original_address_matters
631     = (!DECL_VIRTUAL_P (original->decl)
632        && (original->externally_visible
633            || original->address_taken_from_non_vtable_p ()));
634   alias_address_matters
635     = (!DECL_VIRTUAL_P (alias->decl)
636        && (alias->externally_visible
637            || alias->address_taken_from_non_vtable_p ()));
638
639   /* If alias and original can be compared for address equality, we need
640      to create a thunk.  Also we can not create extra aliases into discardable
641      section (or we risk link failures when section is discarded).  */
642   if ((original_address_matters
643        && alias_address_matters)
644       || original_discardable)
645     {
646       create_thunk = !stdarg_p (TREE_TYPE (alias->decl));
647       create_alias = false;
648       /* When both alias and original are not overwritable, we can save
649          the extra thunk wrapper for direct calls.  */
650       redirect_callers
651         = (!original_discardable
652            && alias->get_availability () > AVAIL_INTERPOSABLE
653            && original->get_availability () > AVAIL_INTERPOSABLE
654            && !alias->instrumented_version);
655     }
656   else
657     {
658       create_alias = true;
659       create_thunk = false;
660       redirect_callers = false;
661     }
662
663   if (create_alias && (DECL_COMDAT_GROUP (alias->decl)
664                        || !sem_item::target_supports_symbol_aliases_p ()))
665     {
666       create_alias = false;
667       create_thunk = true;
668     }
669
670   /* We want thunk to always jump to the local function body
671      unless the body is comdat and may be optimized out.  */
672   if ((create_thunk || redirect_callers)
673       && (!original_discardable
674           || (DECL_COMDAT_GROUP (original->decl)
675               && (DECL_COMDAT_GROUP (original->decl)
676                   == DECL_COMDAT_GROUP (alias->decl)))))
677     local_original
678       = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
679
680     if (!local_original)
681       {
682         if (dump_file)
683           fprintf (dump_file, "Noninterposable alias cannot be created.\n\n");
684
685         return false;
686       }
687
688   if (!decl_binds_to_current_def_p (alias->decl))
689     {
690       if (dump_file)
691         fprintf (dump_file, "Declaration does not bind to currect definition.\n\n");
692       return false;
693     }
694
695   if (redirect_callers)
696     {
697       /* If alias is non-overwritable then
698          all direct calls are safe to be redirected to the original.  */
699       bool redirected = false;
700       while (alias->callers)
701         {
702           cgraph_edge *e = alias->callers;
703           e->redirect_callee (local_original);
704           push_cfun (DECL_STRUCT_FUNCTION (e->caller->decl));
705
706           if (e->call_stmt)
707             e->redirect_call_stmt_to_callee ();
708
709           pop_cfun ();
710           redirected = true;
711         }
712
713       alias->icf_merged = true;
714
715       /* The alias function is removed if symbol address
716          does not matter.  */
717       if (!alias_address_matters)
718         alias->remove ();
719
720       if (dump_file && redirected)
721         fprintf (dump_file, "Callgraph local calls have been redirected.\n\n");
722     }
723   /* If the condtion above is not met, we are lucky and can turn the
724      function into real alias.  */
725   else if (create_alias)
726     {
727       alias->icf_merged = true;
728
729       /* Remove the function's body.  */
730       ipa_merge_profiles (original, alias);
731       alias->release_body (true);
732       alias->reset ();
733
734       /* Create the alias.  */
735       cgraph_node::create_alias (alias_func->decl, decl);
736       alias->resolve_alias (original);
737
738       /* Workaround for PR63566 that forces equal calling convention
739        to be used.  */
740       alias->local.local = false;
741       original->local.local = false;
742
743       if (dump_file)
744         fprintf (dump_file, "Callgraph alias has been created.\n\n");
745     }
746   else if (create_thunk)
747     {
748       if (DECL_COMDAT_GROUP (alias->decl))
749         {
750           if (dump_file)
751             fprintf (dump_file, "Callgraph thunk cannot be created because of COMDAT\n");
752
753           return 0;
754         }
755
756       if (DECL_STATIC_CHAIN (alias->decl))
757         {
758          if (dump_file)
759            fprintf (dump_file, "Thunk creation is risky for static-chain functions.\n\n");
760
761          return 0;
762         }
763
764       alias->icf_merged = true;
765       ipa_merge_profiles (local_original, alias, true);
766       alias->create_wrapper (local_original);
767
768       if (dump_file)
769         fprintf (dump_file, "Callgraph thunk has been created.\n\n");
770     }
771   else if (dump_file)
772     fprintf (dump_file, "Callgraph merge operation cannot be performed.\n\n");
773
774   return true;
775 }
776
777 /* Semantic item initialization function.  */
778
779 void
780 sem_function::init (void)
781 {
782   if (in_lto_p)
783     get_node ()->get_untransformed_body ();
784
785   tree fndecl = node->decl;
786   function *func = DECL_STRUCT_FUNCTION (fndecl);
787
788   gcc_assert (func);
789   gcc_assert (SSANAMES (func));
790
791   ssa_names_size = SSANAMES (func)->length ();
792   node = node;
793
794   decl = fndecl;
795   region_tree = func->eh->region_tree;
796
797   /* iterating all function arguments.  */
798   arg_count = count_formal_params (fndecl);
799
800   edge_count = n_edges_for_fn (func);
801   cfg_checksum = coverage_compute_cfg_checksum (func);
802
803   inchash::hash hstate;
804
805   basic_block bb;
806   FOR_EACH_BB_FN (bb, func)
807   {
808     unsigned nondbg_stmt_count = 0;
809
810     edge e;
811     for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e); ei_next (&ei))
812       cfg_checksum = iterative_hash_host_wide_int (e->flags,
813                      cfg_checksum);
814
815     for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
816          gsi_next (&gsi))
817       {
818         gimple stmt = gsi_stmt (gsi);
819
820         if (gimple_code (stmt) != GIMPLE_DEBUG)
821           {
822             hash_stmt (&hstate, stmt);
823             nondbg_stmt_count++;
824           }
825       }
826
827     gcode_hash = hstate.end ();
828     bb_sizes.safe_push (nondbg_stmt_count);
829
830     /* Inserting basic block to hash table.  */
831     sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
832                                       EDGE_COUNT (bb->preds) + EDGE_COUNT (bb->succs));
833
834     bb_sorted.safe_push (semantic_bb);
835   }
836
837   parse_tree_args ();
838 }
839
840 /* Improve accumulated hash for HSTATE based on a gimple statement STMT.  */
841
842 void
843 sem_function::hash_stmt (inchash::hash *hstate, gimple stmt)
844 {
845   enum gimple_code code = gimple_code (stmt);
846
847   hstate->add_int (code);
848
849   if (code == GIMPLE_CALL)
850     {
851       /* Checking of argument.  */
852       for (unsigned i = 0; i < gimple_call_num_args (stmt); ++i)
853         {
854           tree argument = gimple_call_arg (stmt, i);
855
856           switch (TREE_CODE (argument))
857             {
858             case INTEGER_CST:
859               if (tree_fits_shwi_p (argument))
860                 hstate->add_wide_int (tree_to_shwi (argument));
861               else if (tree_fits_uhwi_p (argument))
862                 hstate->add_wide_int (tree_to_uhwi (argument));
863               break;
864             case REAL_CST:
865               REAL_VALUE_TYPE c;
866               HOST_WIDE_INT n;
867
868               c = TREE_REAL_CST (argument);
869               n = real_to_integer (&c);
870
871               hstate->add_wide_int (n);
872               break;
873             case ADDR_EXPR:
874               {
875                 tree addr_operand = TREE_OPERAND (argument, 0);
876
877                 if (TREE_CODE (addr_operand) == STRING_CST)
878                   hstate->add (TREE_STRING_POINTER (addr_operand),
879                                TREE_STRING_LENGTH (addr_operand));
880                 break;
881               }
882             default:
883               break;
884             }
885         }
886     }
887 }
888
889
890 /* Return true if polymorphic comparison must be processed.  */
891
892 bool
893 sem_function::compare_polymorphic_p (void)
894 {
895   return get_node ()->callees != NULL
896          || get_node ()->indirect_calls != NULL
897          || m_compared_func->get_node ()->callees != NULL
898          || m_compared_func->get_node ()->indirect_calls != NULL;
899 }
900
901 /* For a given call graph NODE, the function constructs new
902    semantic function item.  */
903
904 sem_function *
905 sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
906 {
907   tree fndecl = node->decl;
908   function *func = DECL_STRUCT_FUNCTION (fndecl);
909
910   /* TODO: add support for thunks and aliases.  */
911
912   if (!func || !node->has_gimple_body_p ())
913     return NULL;
914
915   if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
916     return NULL;
917
918   sem_function *f = new sem_function (node, 0, stack);
919
920   f->init ();
921
922   return f;
923 }
924
925 /* Parses function arguments and result type.  */
926
927 void
928 sem_function::parse_tree_args (void)
929 {
930   tree result;
931
932   if (arg_types.exists ())
933     arg_types.release ();
934
935   arg_types.create (4);
936   tree fnargs = DECL_ARGUMENTS (decl);
937
938   for (tree parm = fnargs; parm; parm = DECL_CHAIN (parm))
939     arg_types.safe_push (DECL_ARG_TYPE (parm));
940
941   /* Function result type.  */
942   result = DECL_RESULT (decl);
943   result_type = result ? TREE_TYPE (result) : NULL;
944
945   /* During WPA, we can get arguments by following method.  */
946   if (!fnargs)
947     {
948       tree type = TYPE_ARG_TYPES (TREE_TYPE (decl));
949       for (tree parm = type; parm; parm = TREE_CHAIN (parm))
950         arg_types.safe_push (TYPE_CANONICAL (TREE_VALUE (parm)));
951
952       result_type = TREE_TYPE (TREE_TYPE (decl));
953     }
954 }
955
956 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
957    return true if phi nodes are semantically equivalent in these blocks .  */
958
959 bool
960 sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
961 {
962   gphi_iterator si1, si2;
963   gphi *phi1, *phi2;
964   unsigned size1, size2, i;
965   tree t1, t2;
966   edge e1, e2;
967
968   gcc_assert (bb1 != NULL);
969   gcc_assert (bb2 != NULL);
970
971   si2 = gsi_start_phis (bb2);
972   for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
973        gsi_next (&si1))
974     {
975       gsi_next_nonvirtual_phi (&si1);
976       gsi_next_nonvirtual_phi (&si2);
977
978       if (gsi_end_p (si1) && gsi_end_p (si2))
979         break;
980
981       if (gsi_end_p (si1) || gsi_end_p (si2))
982         return return_false();
983
984       phi1 = si1.phi ();
985       phi2 = si2.phi ();
986
987       tree phi_result1 = gimple_phi_result (phi1);
988       tree phi_result2 = gimple_phi_result (phi2);
989
990       if (!m_checker->compare_operand (phi_result1, phi_result2))
991         return return_false_with_msg ("PHI results are different");
992
993       size1 = gimple_phi_num_args (phi1);
994       size2 = gimple_phi_num_args (phi2);
995
996       if (size1 != size2)
997         return return_false ();
998
999       for (i = 0; i < size1; ++i)
1000         {
1001           t1 = gimple_phi_arg (phi1, i)->def;
1002           t2 = gimple_phi_arg (phi2, i)->def;
1003
1004           if (!m_checker->compare_operand (t1, t2))
1005             return return_false ();
1006
1007           e1 = gimple_phi_arg_edge (phi1, i);
1008           e2 = gimple_phi_arg_edge (phi2, i);
1009
1010           if (!m_checker->compare_edge (e1, e2))
1011             return return_false ();
1012         }
1013
1014       gsi_next (&si2);
1015     }
1016
1017   return true;
1018 }
1019
1020 /* Returns true if tree T can be compared as a handled component.  */
1021
1022 bool
1023 sem_function::icf_handled_component_p (tree t)
1024 {
1025   tree_code tc = TREE_CODE (t);
1026
1027   return ((handled_component_p (t))
1028           || tc == ADDR_EXPR || tc == MEM_REF || tc == REALPART_EXPR
1029           || tc == IMAGPART_EXPR || tc == OBJ_TYPE_REF);
1030 }
1031
1032 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1033    corresponds to TARGET.  */
1034
1035 bool
1036 sem_function::bb_dict_test (auto_vec<int> bb_dict, int source, int target)
1037 {
1038   source++;
1039   target++;
1040
1041   if (bb_dict.length () <= (unsigned)source)
1042     bb_dict.safe_grow_cleared (source + 1);
1043
1044   if (bb_dict[source] == 0)
1045     {
1046       bb_dict[source] = target;
1047       return true;
1048     }
1049   else
1050     return bb_dict[source] == target;
1051 }
1052
1053 /* Iterates all tree types in T1 and T2 and returns true if all types
1054    are compatible. If COMPARE_POLYMORPHIC is set to true,
1055    more strict comparison is executed.  */
1056
1057 bool
1058 sem_function::compare_type_list (tree t1, tree t2, bool compare_polymorphic)
1059 {
1060   tree tv1, tv2;
1061   tree_code tc1, tc2;
1062
1063   if (!t1 && !t2)
1064     return true;
1065
1066   while (t1 != NULL && t2 != NULL)
1067     {
1068       tv1 = TREE_VALUE (t1);
1069       tv2 = TREE_VALUE (t2);
1070
1071       tc1 = TREE_CODE (tv1);
1072       tc2 = TREE_CODE (tv2);
1073
1074       if (tc1 == NOP_EXPR && tc2 == NOP_EXPR)
1075         {}
1076       else if (tc1 == NOP_EXPR || tc2 == NOP_EXPR)
1077         return false;
1078       else if (!func_checker::compatible_types_p (tv1, tv2, compare_polymorphic))
1079         return false;
1080
1081       t1 = TREE_CHAIN (t1);
1082       t2 = TREE_CHAIN (t2);
1083     }
1084
1085   return !(t1 || t2);
1086 }
1087
1088
1089 /* Semantic variable constructor that uses STACK as bitmap memory stack.  */
1090
1091 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
1092 {
1093 }
1094
1095 /*  Constructor based on varpool node _NODE with computed hash _HASH.
1096     Bitmap STACK is used for memory allocation.  */
1097
1098 sem_variable::sem_variable (varpool_node *node, hashval_t _hash,
1099                             bitmap_obstack *stack): sem_item(VAR,
1100                                   node, _hash, stack)
1101 {
1102   gcc_checking_assert (node);
1103   gcc_checking_assert (get_node ());
1104 }
1105
1106 /* Returns true if the item equals to ITEM given as argument.  */
1107
1108 bool
1109 sem_variable::equals (sem_item *item,
1110                       hash_map <symtab_node *, sem_item *> & ARG_UNUSED (ignored_nodes))
1111 {
1112   gcc_assert (item->type == VAR);
1113
1114   sem_variable *v = static_cast<sem_variable *>(item);
1115
1116   if (!ctor || !v->ctor)
1117     return return_false_with_msg ("ctor is missing for semantic variable");
1118
1119   return sem_variable::equals (ctor, v->ctor);
1120 }
1121
1122 /* Compares trees T1 and T2 for semantic equality.  */
1123
1124 bool
1125 sem_variable::equals (tree t1, tree t2)
1126 {
1127   tree_code tc1 = TREE_CODE (t1);
1128   tree_code tc2 = TREE_CODE (t2);
1129
1130   if (tc1 != tc2)
1131     return false;
1132
1133   switch (tc1)
1134     {
1135     case CONSTRUCTOR:
1136       {
1137         unsigned len1 = vec_safe_length (CONSTRUCTOR_ELTS (t1));
1138         unsigned len2 = vec_safe_length (CONSTRUCTOR_ELTS (t2));
1139
1140         if (len1 != len2)
1141           return false;
1142
1143         for (unsigned i = 0; i < len1; i++)
1144           if (!sem_variable::equals (CONSTRUCTOR_ELT (t1, i)->value,
1145                                      CONSTRUCTOR_ELT (t2, i)->value)
1146               || CONSTRUCTOR_ELT (t1, i)->index != CONSTRUCTOR_ELT (t2, i)->index)
1147             return false;
1148
1149         return true;
1150       }
1151     case MEM_REF:
1152       {
1153         tree x1 = TREE_OPERAND (t1, 0);
1154         tree x2 = TREE_OPERAND (t2, 0);
1155         tree y1 = TREE_OPERAND (t1, 1);
1156         tree y2 = TREE_OPERAND (t2, 1);
1157
1158         if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2),
1159                                                true))
1160           return return_false ();
1161
1162         /* Type of the offset on MEM_REF does not matter.  */
1163         return sem_variable::equals (x1, x2)
1164                && wi::to_offset  (y1) == wi::to_offset  (y2);
1165       }
1166     case NOP_EXPR:
1167     case ADDR_EXPR:
1168       {
1169         tree op1 = TREE_OPERAND (t1, 0);
1170         tree op2 = TREE_OPERAND (t2, 0);
1171         return sem_variable::equals (op1, op2);
1172       }
1173     case FUNCTION_DECL:
1174     case VAR_DECL:
1175     case FIELD_DECL:
1176     case LABEL_DECL:
1177       return t1 == t2;
1178     case INTEGER_CST:
1179       return func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
1180              true)
1181              && wi::to_offset (t1) == wi::to_offset (t2);
1182     case STRING_CST:
1183     case REAL_CST:
1184     case COMPLEX_CST:
1185       return operand_equal_p (t1, t2, OEP_ONLY_CONST);
1186     case COMPONENT_REF:
1187     case ARRAY_REF:
1188     case POINTER_PLUS_EXPR:
1189       {
1190         tree x1 = TREE_OPERAND (t1, 0);
1191         tree x2 = TREE_OPERAND (t2, 0);
1192         tree y1 = TREE_OPERAND (t1, 1);
1193         tree y2 = TREE_OPERAND (t2, 1);
1194
1195         return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
1196       }
1197     case ERROR_MARK:
1198       return return_false_with_msg ("ERROR_MARK");
1199     default:
1200       return return_false_with_msg ("Unknown TREE code reached");
1201     }
1202 }
1203
1204 /* Parser function that visits a varpool NODE.  */
1205
1206 sem_variable *
1207 sem_variable::parse (varpool_node *node, bitmap_obstack *stack)
1208 {
1209   tree decl = node->decl;
1210
1211   bool readonly = TYPE_P (decl) ? TYPE_READONLY (decl) : TREE_READONLY (decl);
1212   if (!readonly)
1213     return NULL;
1214
1215   bool can_handle = DECL_VIRTUAL_P (decl)
1216                     || flag_merge_constants >= 2
1217                     || (!TREE_ADDRESSABLE (decl) && !node->externally_visible);
1218
1219   if (!can_handle || DECL_EXTERNAL (decl))
1220     return NULL;
1221
1222   tree ctor = ctor_for_folding (decl);
1223   if (!ctor)
1224     return NULL;
1225
1226   sem_variable *v = new sem_variable (node, 0, stack);
1227
1228   v->init ();
1229
1230   return v;
1231 }
1232
1233 /* References independent hash function.  */
1234
1235 hashval_t
1236 sem_variable::get_hash (void)
1237 {
1238   if (hash)
1239     return hash;
1240
1241   inchash::hash hstate;
1242
1243   hstate.add_int (456346417);
1244   hstate.add_int (TREE_CODE (ctor));
1245
1246   if (TREE_CODE (ctor) == CONSTRUCTOR)
1247     {
1248       unsigned length = vec_safe_length (CONSTRUCTOR_ELTS (ctor));
1249       hstate.add_int (length);
1250     }
1251
1252   hash = hstate.end ();
1253
1254   return hash;
1255 }
1256
1257 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1258    be applied.  */
1259
1260 bool
1261 sem_variable::merge (sem_item *alias_item)
1262 {
1263   gcc_assert (alias_item->type == VAR);
1264
1265   if (!sem_item::target_supports_symbol_aliases_p ())
1266     {
1267       if (dump_file)
1268         fprintf (dump_file, "Symbol aliases are not supported by target\n\n");
1269       return false;
1270     }
1271
1272   sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
1273
1274   varpool_node *original = get_node ();
1275   varpool_node *alias = alias_var->get_node ();
1276   bool original_discardable = false;
1277
1278   /* See if original is in a section that can be discarded if the main
1279      symbol is not used.  */
1280   if (DECL_EXTERNAL (original->decl))
1281     original_discardable = true;
1282   if (original->resolution == LDPR_PREEMPTED_REG
1283       || original->resolution == LDPR_PREEMPTED_IR)
1284     original_discardable = true;
1285   if (original->can_be_discarded_p ())
1286     original_discardable = true;
1287
1288   gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
1289
1290   if (original_discardable || DECL_EXTERNAL (alias_var->decl) ||
1291       !compare_sections (alias_var))
1292     {
1293       if (dump_file)
1294         fprintf (dump_file, "Varpool alias cannot be created\n\n");
1295
1296       return false;
1297     }
1298   else
1299     {
1300       // alias cycle creation check
1301       varpool_node *n = original;
1302
1303       while (n->alias)
1304         {
1305           n = n->get_alias_target ();
1306           if (n == alias)
1307             {
1308               if (dump_file)
1309                 fprintf (dump_file, "Varpool alias cannot be created (alias cycle).\n\n");
1310
1311               return false;
1312             }
1313         }
1314
1315       alias->analyzed = false;
1316
1317       DECL_INITIAL (alias->decl) = NULL;
1318       alias->need_bounds_init = false;
1319       alias->remove_all_references ();
1320
1321       varpool_node::create_alias (alias_var->decl, decl);
1322       alias->resolve_alias (original);
1323
1324       if (dump_file)
1325         fprintf (dump_file, "Varpool alias has been created.\n\n");
1326
1327       return true;
1328     }
1329 }
1330
1331 bool
1332 sem_variable::compare_sections (sem_variable *alias)
1333 {
1334   const char *source = node->get_section ();
1335   const char *target = alias->node->get_section();
1336
1337   if (source == NULL && target == NULL)
1338     return true;
1339   else if(!source || !target)
1340     return false;
1341   else
1342     return strcmp (source, target) == 0;
1343 }
1344
1345 /* Dump symbol to FILE.  */
1346
1347 void
1348 sem_variable::dump_to_file (FILE *file)
1349 {
1350   gcc_assert (file);
1351
1352   print_node (file, "", decl, 0);
1353   fprintf (file, "\n\n");
1354 }
1355
1356 /* Iterates though a constructor and identifies tree references
1357    we are interested in semantic function equality.  */
1358
1359 void
1360 sem_variable::parse_tree_refs (tree t)
1361 {
1362   switch (TREE_CODE (t))
1363     {
1364     case CONSTRUCTOR:
1365       {
1366         unsigned length = vec_safe_length (CONSTRUCTOR_ELTS (t));
1367
1368         for (unsigned i = 0; i < length; i++)
1369           parse_tree_refs(CONSTRUCTOR_ELT (t, i)->value);
1370
1371         break;
1372       }
1373     case NOP_EXPR:
1374     case ADDR_EXPR:
1375       {
1376         tree op = TREE_OPERAND (t, 0);
1377         parse_tree_refs (op);
1378         break;
1379       }
1380     case FUNCTION_DECL:
1381       {
1382         tree_refs.safe_push (t);
1383         break;
1384       }
1385     default:
1386       break;
1387     }
1388 }
1389
1390 unsigned int sem_item_optimizer::class_id = 0;
1391
1392 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1393   m_classes_count (0), m_cgraph_node_hooks (NULL), m_varpool_node_hooks (NULL)
1394 {
1395   m_items.create (0);
1396   bitmap_obstack_initialize (&m_bmstack);
1397 }
1398
1399 sem_item_optimizer::~sem_item_optimizer ()
1400 {
1401   for (unsigned int i = 0; i < m_items.length (); i++)
1402     delete m_items[i];
1403
1404   for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
1405        it != m_classes.end (); ++it)
1406     {
1407       for (unsigned int i = 0; i < (*it)->classes.length (); i++)
1408         delete (*it)->classes[i];
1409
1410       (*it)->classes.release ();
1411       free (*it);
1412     }
1413
1414   m_items.release ();
1415
1416   bitmap_obstack_release (&m_bmstack);
1417 }
1418
1419 /* Write IPA ICF summary for symbols.  */
1420
1421 void
1422 sem_item_optimizer::write_summary (void)
1423 {
1424   unsigned int count = 0;
1425
1426   output_block *ob = create_output_block (LTO_section_ipa_icf);
1427   lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
1428   ob->symbol = NULL;
1429
1430   /* Calculate number of symbols to be serialized.  */
1431   for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
1432        !lsei_end_p (lsei);
1433        lsei_next_in_partition (&lsei))
1434     {
1435       symtab_node *node = lsei_node (lsei);
1436
1437       if (m_symtab_node_map.get (node))
1438         count++;
1439     }
1440
1441   streamer_write_uhwi (ob, count);
1442
1443   /* Process all of the symbols.  */
1444   for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
1445        !lsei_end_p (lsei);
1446        lsei_next_in_partition (&lsei))
1447     {
1448       symtab_node *node = lsei_node (lsei);
1449
1450       sem_item **item = m_symtab_node_map.get (node);
1451
1452       if (item && *item)
1453         {
1454           int node_ref = lto_symtab_encoder_encode (encoder, node);
1455           streamer_write_uhwi_stream (ob->main_stream, node_ref);
1456
1457           streamer_write_uhwi (ob, (*item)->get_hash ());
1458         }
1459     }
1460
1461   streamer_write_char_stream (ob->main_stream, 0);
1462   produce_asm (ob, NULL);
1463   destroy_output_block (ob);
1464 }
1465
1466 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1467    contains LEN bytes.  */
1468
1469 void
1470 sem_item_optimizer::read_section (lto_file_decl_data *file_data,
1471                                   const char *data, size_t len)
1472 {
1473   const lto_function_header *header =
1474     (const lto_function_header *) data;
1475   const int cfg_offset = sizeof (lto_function_header);
1476   const int main_offset = cfg_offset + header->cfg_size;
1477   const int string_offset = main_offset + header->main_size;
1478   data_in *data_in;
1479   unsigned int i;
1480   unsigned int count;
1481
1482   lto_input_block ib_main ((const char *) data + main_offset, 0,
1483                            header->main_size);
1484
1485   data_in =
1486     lto_data_in_create (file_data, (const char *) data + string_offset,
1487                         header->string_size, vNULL);
1488
1489   count = streamer_read_uhwi (&ib_main);
1490
1491   for (i = 0; i < count; i++)
1492     {
1493       unsigned int index;
1494       symtab_node *node;
1495       lto_symtab_encoder_t encoder;
1496
1497       index = streamer_read_uhwi (&ib_main);
1498       encoder = file_data->symtab_node_encoder;
1499       node = lto_symtab_encoder_deref (encoder, index);
1500
1501       hashval_t hash = streamer_read_uhwi (&ib_main);
1502
1503       gcc_assert (node->definition);
1504
1505       if (dump_file)
1506         fprintf (dump_file, "Symbol added:%s (tree: %p, uid:%u)\n", node->asm_name (),
1507                  (void *) node->decl, node->order);
1508
1509       if (is_a<cgraph_node *> (node))
1510         {
1511           cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1512
1513           m_items.safe_push (new sem_function (cnode, hash, &m_bmstack));
1514         }
1515       else
1516         {
1517           varpool_node *vnode = dyn_cast <varpool_node *> (node);
1518
1519           m_items.safe_push (new sem_variable (vnode, hash, &m_bmstack));
1520         }
1521     }
1522
1523   lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
1524                          len);
1525   lto_data_in_delete (data_in);
1526 }
1527
1528 /* Read IPA IPA ICF summary for symbols.  */
1529
1530 void
1531 sem_item_optimizer::read_summary (void)
1532 {
1533   lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
1534   lto_file_decl_data *file_data;
1535   unsigned int j = 0;
1536
1537   while ((file_data = file_data_vec[j++]))
1538     {
1539       size_t len;
1540       const char *data = lto_get_section_data (file_data,
1541                          LTO_section_ipa_icf, NULL, &len);
1542
1543       if (data)
1544         read_section (file_data, data, len);
1545     }
1546 }
1547
1548 /* Register callgraph and varpool hooks.  */
1549
1550 void
1551 sem_item_optimizer::register_hooks (void)
1552 {
1553   m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
1554                         (&sem_item_optimizer::cgraph_removal_hook, this);
1555
1556   m_varpool_node_hooks = symtab->add_varpool_removal_hook
1557                          (&sem_item_optimizer::varpool_removal_hook, this);
1558 }
1559
1560 /* Unregister callgraph and varpool hooks.  */
1561
1562 void
1563 sem_item_optimizer::unregister_hooks (void)
1564 {
1565   if (m_cgraph_node_hooks)
1566     symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
1567
1568   if (m_varpool_node_hooks)
1569     symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
1570 }
1571
1572 /* Adds a CLS to hashtable associated by hash value.  */
1573
1574 void
1575 sem_item_optimizer::add_class (congruence_class *cls)
1576 {
1577   gcc_assert (cls->members.length ());
1578
1579   congruence_class_group *group = get_group_by_hash (
1580                                     cls->members[0]->get_hash (),
1581                                     cls->members[0]->type);
1582   group->classes.safe_push (cls);
1583 }
1584
1585 /* Gets a congruence class group based on given HASH value and TYPE.  */
1586
1587 congruence_class_group *
1588 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
1589 {
1590   congruence_class_group *item = XNEW (congruence_class_group);
1591   item->hash = hash;
1592   item->type = type;
1593
1594   congruence_class_group **slot = m_classes.find_slot (item, INSERT);
1595
1596   if (*slot)
1597     free (item);
1598   else
1599     {
1600       item->classes.create (1);
1601       *slot = item;
1602     }
1603
1604   return *slot;
1605 }
1606
1607 /* Callgraph removal hook called for a NODE with a custom DATA.  */
1608
1609 void
1610 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
1611 {
1612   sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
1613   optimizer->remove_symtab_node (node);
1614 }
1615
1616 /* Varpool removal hook called for a NODE with a custom DATA.  */
1617
1618 void
1619 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
1620 {
1621   sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
1622   optimizer->remove_symtab_node (node);
1623 }
1624
1625 /* Remove symtab NODE triggered by symtab removal hooks.  */
1626
1627 void
1628 sem_item_optimizer::remove_symtab_node (symtab_node *node)
1629 {
1630   gcc_assert (!m_classes.elements());
1631
1632   m_removed_items_set.add (node);
1633 }
1634
1635 void
1636 sem_item_optimizer::remove_item (sem_item *item)
1637 {
1638   if (m_symtab_node_map.get (item->node))
1639     m_symtab_node_map.remove (item->node);
1640   delete item;
1641 }
1642
1643 /* Removes all callgraph and varpool nodes that are marked by symtab
1644    as deleted.  */
1645
1646 void
1647 sem_item_optimizer::filter_removed_items (void)
1648 {
1649   auto_vec <sem_item *> filtered;
1650
1651   for (unsigned int i = 0; i < m_items.length(); i++)
1652     {
1653       sem_item *item = m_items[i];
1654
1655       if (m_removed_items_set.contains (item->node))
1656         {
1657           remove_item (item);
1658           continue;
1659         }
1660
1661       if (item->type == FUNC)
1662         {
1663           cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
1664
1665           bool no_body_function = in_lto_p && (cnode->alias || cnode->body_removed);
1666           if (no_body_function || !opt_for_fn (item->decl, flag_ipa_icf_functions)
1667               || DECL_CXX_CONSTRUCTOR_P (item->decl)
1668               || DECL_CXX_DESTRUCTOR_P (item->decl))
1669             remove_item (item);
1670           else
1671             filtered.safe_push (item);
1672         }
1673       else /* VAR.  */
1674         {
1675           if (!flag_ipa_icf_variables)
1676             remove_item (item);
1677           else
1678             filtered.safe_push (item);
1679         }
1680     }
1681
1682   /* Clean-up of released semantic items.  */
1683
1684   m_items.release ();
1685   for (unsigned int i = 0; i < filtered.length(); i++)
1686     m_items.safe_push (filtered[i]);
1687 }
1688
1689 /* Optimizer entry point.  */
1690
1691 void
1692 sem_item_optimizer::execute (void)
1693 {
1694   filter_removed_items ();
1695   build_hash_based_classes ();
1696
1697   if (dump_file)
1698     fprintf (dump_file, "Dump after hash based groups\n");
1699   dump_cong_classes ();
1700
1701   for (unsigned int i = 0; i < m_items.length(); i++)
1702     m_items[i]->init_wpa ();
1703
1704   build_graph ();
1705
1706   subdivide_classes_by_equality (true);
1707
1708   if (dump_file)
1709     fprintf (dump_file, "Dump after WPA based types groups\n");
1710
1711   dump_cong_classes ();
1712
1713   process_cong_reduction ();
1714   verify_classes ();
1715
1716   if (dump_file)
1717     fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
1718
1719   dump_cong_classes ();
1720
1721   parse_nonsingleton_classes ();
1722   subdivide_classes_by_equality ();
1723
1724   if (dump_file)
1725     fprintf (dump_file, "Dump after full equality comparison of groups\n");
1726
1727   dump_cong_classes ();
1728
1729   unsigned int prev_class_count = m_classes_count;
1730
1731   process_cong_reduction ();
1732   dump_cong_classes ();
1733   verify_classes ();
1734   merge_classes (prev_class_count);
1735
1736   if (dump_file && (dump_flags & TDF_DETAILS))
1737     symtab_node::dump_table (dump_file);
1738 }
1739
1740 /* Function responsible for visiting all potential functions and
1741    read-only variables that can be merged.  */
1742
1743 void
1744 sem_item_optimizer::parse_funcs_and_vars (void)
1745 {
1746   cgraph_node *cnode;
1747
1748   if (flag_ipa_icf_functions)
1749     FOR_EACH_DEFINED_FUNCTION (cnode)
1750     {
1751       sem_function *f = sem_function::parse (cnode, &m_bmstack);
1752       if (f)
1753         {
1754           m_items.safe_push (f);
1755           m_symtab_node_map.put (cnode, f);
1756
1757           if (dump_file)
1758             fprintf (dump_file, "Parsed function:%s\n", f->asm_name ());
1759
1760           if (dump_file && (dump_flags & TDF_DETAILS))
1761             f->dump_to_file (dump_file);
1762         }
1763       else if (dump_file)
1764         fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
1765     }
1766
1767   varpool_node *vnode;
1768
1769   if (flag_ipa_icf_variables)
1770     FOR_EACH_DEFINED_VARIABLE (vnode)
1771     {
1772       sem_variable *v = sem_variable::parse (vnode, &m_bmstack);
1773
1774       if (v)
1775         {
1776           m_items.safe_push (v);
1777           m_symtab_node_map.put (vnode, v);
1778         }
1779     }
1780 }
1781
1782 /* Makes pairing between a congruence class CLS and semantic ITEM.  */
1783
1784 void
1785 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
1786 {
1787   item->index_in_class = cls->members.length ();
1788   cls->members.safe_push (item);
1789   item->cls = cls;
1790 }
1791
1792 /* Congruence classes are built by hash value.  */
1793
1794 void
1795 sem_item_optimizer::build_hash_based_classes (void)
1796 {
1797   for (unsigned i = 0; i < m_items.length (); i++)
1798     {
1799       sem_item *item = m_items[i];
1800
1801       congruence_class_group *group = get_group_by_hash (item->get_hash (),
1802                                       item->type);
1803
1804       if (!group->classes.length ())
1805         {
1806           m_classes_count++;
1807           group->classes.safe_push (new congruence_class (class_id++));
1808         }
1809
1810       add_item_to_class (group->classes[0], item);
1811     }
1812 }
1813
1814 /* Build references according to call graph.  */
1815
1816 void
1817 sem_item_optimizer::build_graph (void)
1818 {
1819   for (unsigned i = 0; i < m_items.length (); i++)
1820     {
1821       sem_item *item = m_items[i];
1822       m_symtab_node_map.put (item->node, item);
1823     }
1824
1825   for (unsigned i = 0; i < m_items.length (); i++)
1826     {
1827       sem_item *item = m_items[i];
1828
1829       if (item->type == FUNC)
1830         {
1831           cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
1832
1833           cgraph_edge *e = cnode->callees;
1834           while (e)
1835             {
1836               sem_item **slot = m_symtab_node_map.get (e->callee);
1837               if (slot)
1838                 item->add_reference (*slot);
1839
1840               e = e->next_callee;
1841             }
1842         }
1843
1844       ipa_ref *ref = NULL;
1845       for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
1846         {
1847           sem_item **slot = m_symtab_node_map.get (ref->referred);
1848           if (slot)
1849             item->add_reference (*slot);
1850         }
1851     }
1852 }
1853
1854 /* Semantic items in classes having more than one element and initialized.
1855    In case of WPA, we load function body.  */
1856
1857 void
1858 sem_item_optimizer::parse_nonsingleton_classes (void)
1859 {
1860   unsigned int init_called_count = 0;
1861
1862   for (unsigned i = 0; i < m_items.length (); i++)
1863     if (m_items[i]->cls->members.length () > 1)
1864       {
1865         m_items[i]->init ();
1866         init_called_count++;
1867       }
1868
1869   if (dump_file)
1870     fprintf (dump_file, "Init called for %u items (%.2f%%).\n", init_called_count,
1871              m_items.length () ? 100.0f * init_called_count / m_items.length (): 0.0f);
1872 }
1873
1874 /* Equality function for semantic items is used to subdivide existing
1875    classes. If IN_WPA, fast equality function is invoked.  */
1876
1877 void
1878 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
1879 {
1880   for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
1881        it != m_classes.end (); ++it)
1882     {
1883       unsigned int class_count = (*it)->classes.length ();
1884
1885       for (unsigned i = 0; i < class_count; i++)
1886         {
1887           congruence_class *c = (*it)->classes [i];
1888
1889           if (c->members.length() > 1)
1890             {
1891               auto_vec <sem_item *> new_vector;
1892
1893               sem_item *first = c->members[0];
1894               new_vector.safe_push (first);
1895
1896               unsigned class_split_first = (*it)->classes.length ();
1897
1898               for (unsigned j = 1; j < c->members.length (); j++)
1899                 {
1900                   sem_item *item = c->members[j];
1901
1902                   bool equals = in_wpa ? first->equals_wpa (item,
1903                                 m_symtab_node_map) : first->equals (item, m_symtab_node_map);
1904
1905                   if (equals)
1906                     new_vector.safe_push (item);
1907                   else
1908                     {
1909                       bool integrated = false;
1910
1911                       for (unsigned k = class_split_first; k < (*it)->classes.length (); k++)
1912                         {
1913                           sem_item *x = (*it)->classes[k]->members[0];
1914                           bool equals = in_wpa ? x->equals_wpa (item,
1915                                                                 m_symtab_node_map) : x->equals (item, m_symtab_node_map);
1916
1917                           if (equals)
1918                             {
1919                               integrated = true;
1920                               add_item_to_class ((*it)->classes[k], item);
1921
1922                               break;
1923                             }
1924                         }
1925
1926                       if (!integrated)
1927                         {
1928                           congruence_class *c = new congruence_class (class_id++);
1929                           m_classes_count++;
1930                           add_item_to_class (c, item);
1931
1932                           (*it)->classes.safe_push (c);
1933                         }
1934                     }
1935                 }
1936
1937               // we replace newly created new_vector for the class we've just splitted
1938               c->members.release ();
1939               c->members.create (new_vector.length ());
1940
1941               for (unsigned int j = 0; j < new_vector.length (); j++)
1942                 add_item_to_class (c, new_vector[j]);
1943             }
1944         }
1945     }
1946
1947   verify_classes ();
1948 }
1949
1950 /* Verify congruence classes if checking is enabled.  */
1951
1952 void
1953 sem_item_optimizer::verify_classes (void)
1954 {
1955 #if ENABLE_CHECKING
1956   for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
1957        it != m_classes.end (); ++it)
1958     {
1959       for (unsigned int i = 0; i < (*it)->classes.length (); i++)
1960         {
1961           congruence_class *cls = (*it)->classes[i];
1962
1963           gcc_checking_assert (cls);
1964           gcc_checking_assert (cls->members.length () > 0);
1965
1966           for (unsigned int j = 0; j < cls->members.length (); j++)
1967             {
1968               sem_item *item = cls->members[j];
1969
1970               gcc_checking_assert (item);
1971               gcc_checking_assert (item->cls == cls);
1972
1973               for (unsigned k = 0; k < item->usages.length (); k++)
1974                 {
1975                   sem_usage_pair *usage = item->usages[k];
1976                   gcc_checking_assert (usage->item->index_in_class <
1977                                        usage->item->cls->members.length ());
1978                 }
1979             }
1980         }
1981     }
1982 #endif
1983 }
1984
1985 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
1986    class, BSLOT is bitmap slot we want to release. DATA is mandatory,
1987    but unused argument.  */
1988
1989 bool
1990 sem_item_optimizer::release_split_map (congruence_class * const &,
1991                                        bitmap const &b, traverse_split_pair *)
1992 {
1993   bitmap bmp = b;
1994
1995   BITMAP_FREE (bmp);
1996
1997   return true;
1998 }
1999
2000 /* Process split operation for a class given as pointer CLS_PTR,
2001    where bitmap B splits congruence class members. DATA is used
2002    as argument of split pair.  */
2003
2004 bool
2005 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
2006     bitmap const &b, traverse_split_pair *pair)
2007 {
2008   sem_item_optimizer *optimizer = pair->optimizer;
2009   const congruence_class *splitter_cls = pair->cls;
2010
2011   /* If counted bits are greater than zero and less than the number of members
2012      a group will be splitted.  */
2013   unsigned popcount = bitmap_count_bits (b);
2014
2015   if (popcount > 0 && popcount < cls->members.length ())
2016     {
2017       congruence_class* newclasses[2] = { new congruence_class (class_id++), new congruence_class (class_id++) };
2018
2019       for (unsigned int i = 0; i < cls->members.length (); i++)
2020         {
2021           int target = bitmap_bit_p (b, i);
2022           congruence_class *tc = newclasses[target];
2023
2024           add_item_to_class (tc, cls->members[i]);
2025         }
2026
2027 #ifdef ENABLE_CHECKING
2028       for (unsigned int i = 0; i < 2; i++)
2029         gcc_checking_assert (newclasses[i]->members.length ());
2030 #endif
2031
2032       if (splitter_cls == cls)
2033         optimizer->splitter_class_removed = true;
2034
2035       /* Remove old class from worklist if presented.  */
2036       bool in_worklist = cls->in_worklist;
2037
2038       if (in_worklist)
2039         cls->in_worklist = false;
2040
2041       congruence_class_group g;
2042       g.hash = cls->members[0]->get_hash ();
2043       g.type = cls->members[0]->type;
2044
2045       congruence_class_group *slot = optimizer->m_classes.find(&g);
2046
2047       for (unsigned int i = 0; i < slot->classes.length (); i++)
2048         if (slot->classes[i] == cls)
2049           {
2050             slot->classes.ordered_remove (i);
2051             break;
2052           }
2053
2054       /* New class will be inserted and integrated to work list.  */
2055       for (unsigned int i = 0; i < 2; i++)
2056         optimizer->add_class (newclasses[i]);
2057
2058       /* Two classes replace one, so that increment just by one.  */
2059       optimizer->m_classes_count++;
2060
2061       /* If OLD class was presented in the worklist, we remove the class
2062          and replace it will both newly created classes.  */
2063       if (in_worklist)
2064         for (unsigned int i = 0; i < 2; i++)
2065           optimizer->worklist_push (newclasses[i]);
2066       else /* Just smaller class is inserted.  */
2067         {
2068           unsigned int smaller_index = newclasses[0]->members.length () <
2069                                        newclasses[1]->members.length () ?
2070                                        0 : 1;
2071           optimizer->worklist_push (newclasses[smaller_index]);
2072         }
2073
2074       if (dump_file && (dump_flags & TDF_DETAILS))
2075         {
2076           fprintf (dump_file, "  congruence class splitted:\n");
2077           cls->dump (dump_file, 4);
2078
2079           fprintf (dump_file, "  newly created groups:\n");
2080           for (unsigned int i = 0; i < 2; i++)
2081             newclasses[i]->dump (dump_file, 4);
2082         }
2083
2084       /* Release class if not presented in work list.  */
2085       if (!in_worklist)
2086         delete cls;
2087     }
2088
2089
2090   return true;
2091 }
2092
2093 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2094    Bitmap stack BMSTACK is used for bitmap allocation.  */
2095
2096 void
2097 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
2098     unsigned int index)
2099 {
2100   hash_map <congruence_class *, bitmap> split_map;
2101
2102   for (unsigned int i = 0; i < cls->members.length (); i++)
2103     {
2104       sem_item *item = cls->members[i];
2105
2106       /* Iterate all usages that have INDEX as usage of the item.  */
2107       for (unsigned int j = 0; j < item->usages.length (); j++)
2108         {
2109           sem_usage_pair *usage = item->usages[j];
2110
2111           if (usage->index != index)
2112             continue;
2113
2114           bitmap *slot = split_map.get (usage->item->cls);
2115           bitmap b;
2116
2117           if(!slot)
2118             {
2119               b = BITMAP_ALLOC (&m_bmstack);
2120               split_map.put (usage->item->cls, b);
2121             }
2122           else
2123             b = *slot;
2124
2125 #if ENABLE_CHECKING
2126           gcc_checking_assert (usage->item->cls);
2127           gcc_checking_assert (usage->item->index_in_class <
2128                                usage->item->cls->members.length ());
2129 #endif
2130
2131           bitmap_set_bit (b, usage->item->index_in_class);
2132         }
2133     }
2134
2135   traverse_split_pair pair;
2136   pair.optimizer = this;
2137   pair.cls = cls;
2138
2139   splitter_class_removed = false;
2140   split_map.traverse
2141   <traverse_split_pair *, sem_item_optimizer::traverse_congruence_split> (&pair);
2142
2143   /* Bitmap clean-up.  */
2144   split_map.traverse
2145   <traverse_split_pair *, sem_item_optimizer::release_split_map> (NULL);
2146 }
2147
2148 /* Every usage of a congruence class CLS is a candidate that can split the
2149    collection of classes. Bitmap stack BMSTACK is used for bitmap
2150    allocation.  */
2151
2152 void
2153 sem_item_optimizer::do_congruence_step (congruence_class *cls)
2154 {
2155   bitmap_iterator bi;
2156   unsigned int i;
2157
2158   bitmap usage = BITMAP_ALLOC (&m_bmstack);
2159
2160   for (unsigned int i = 0; i < cls->members.length (); i++)
2161     bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
2162
2163   EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
2164   {
2165     if (dump_file && (dump_flags & TDF_DETAILS))
2166       fprintf (dump_file, "  processing congruece step for class: %u, index: %u\n",
2167                cls->id, i);
2168
2169     do_congruence_step_for_index (cls, i);
2170
2171     if (splitter_class_removed)
2172       break;
2173   }
2174
2175   BITMAP_FREE (usage);
2176 }
2177
2178 /* Adds a newly created congruence class CLS to worklist.  */
2179
2180 void
2181 sem_item_optimizer::worklist_push (congruence_class *cls)
2182 {
2183   /* Return if the class CLS is already presented in work list.  */
2184   if (cls->in_worklist)
2185     return;
2186
2187   cls->in_worklist = true;
2188   worklist.push_back (cls);
2189 }
2190
2191 /* Pops a class from worklist. */
2192
2193 congruence_class *
2194 sem_item_optimizer::worklist_pop (void)
2195 {
2196   congruence_class *cls;
2197
2198   while (!worklist.empty ())
2199     {
2200       cls = worklist.front ();
2201       worklist.pop_front ();
2202       if (cls->in_worklist)
2203         {
2204           cls->in_worklist = false;
2205
2206           return cls;
2207         }
2208       else
2209         {
2210           /* Work list item was already intended to be removed.
2211              The only reason for doing it is to split a class.
2212              Thus, the class CLS is deleted.  */
2213           delete cls;
2214         }
2215     }
2216
2217   return NULL;
2218 }
2219
2220 /* Iterative congruence reduction function.  */
2221
2222 void
2223 sem_item_optimizer::process_cong_reduction (void)
2224 {
2225   for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2226        it != m_classes.end (); ++it)
2227     for (unsigned i = 0; i < (*it)->classes.length (); i++)
2228       if ((*it)->classes[i]->is_class_used ())
2229         worklist_push ((*it)->classes[i]);
2230
2231   if (dump_file)
2232     fprintf (dump_file, "Worklist has been filled with: %lu\n",
2233              (unsigned long) worklist.size ());
2234
2235   if (dump_file && (dump_flags & TDF_DETAILS))
2236     fprintf (dump_file, "Congruence class reduction\n");
2237
2238   congruence_class *cls;
2239   while ((cls = worklist_pop ()) != NULL)
2240     do_congruence_step (cls);
2241 }
2242
2243 /* Debug function prints all informations about congruence classes.  */
2244
2245 void
2246 sem_item_optimizer::dump_cong_classes (void)
2247 {
2248   if (!dump_file)
2249     return;
2250
2251   fprintf (dump_file,
2252            "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2253            m_classes_count, (unsigned long) m_classes.elements(), m_items.length ());
2254
2255   /* Histogram calculation.  */
2256   unsigned int max_index = 0;
2257   unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
2258
2259   for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2260        it != m_classes.end (); ++it)
2261
2262     for (unsigned i = 0; i < (*it)->classes.length (); i++)
2263       {
2264         unsigned int c = (*it)->classes[i]->members.length ();
2265         histogram[c]++;
2266
2267         if (c > max_index)
2268           max_index = c;
2269       }
2270
2271   fprintf (dump_file,
2272            "Class size histogram [num of members]: number of classe number of classess\n");
2273
2274   for (unsigned int i = 0; i <= max_index; i++)
2275     if (histogram[i])
2276       fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
2277
2278   fprintf (dump_file, "\n\n");
2279
2280
2281   if (dump_flags & TDF_DETAILS)
2282     for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2283          it != m_classes.end (); ++it)
2284       {
2285         fprintf (dump_file, "  group: with %u classes:\n", (*it)->classes.length ());
2286
2287         for (unsigned i = 0; i < (*it)->classes.length (); i++)
2288           {
2289             (*it)->classes[i]->dump (dump_file, 4);
2290
2291             if(i < (*it)->classes.length () - 1)
2292               fprintf (dump_file, " ");
2293           }
2294       }
2295
2296   free (histogram);
2297 }
2298
2299 /* After reduction is done, we can declare all items in a group
2300    to be equal. PREV_CLASS_COUNT is start number of classes
2301    before reduction.  */
2302
2303 void
2304 sem_item_optimizer::merge_classes (unsigned int prev_class_count)
2305 {
2306   unsigned int item_count = m_items.length ();
2307   unsigned int class_count = m_classes_count;
2308   unsigned int equal_items = item_count - class_count;
2309
2310   unsigned int non_singular_classes_count = 0;
2311   unsigned int non_singular_classes_sum = 0;
2312
2313   for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2314        it != m_classes.end (); ++it)
2315     for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2316       {
2317         congruence_class *c = (*it)->classes[i];
2318         if (c->members.length () > 1)
2319           {
2320             non_singular_classes_count++;
2321             non_singular_classes_sum += c->members.length ();
2322           }
2323       }
2324
2325   if (dump_file)
2326     {
2327       fprintf (dump_file, "\nItem count: %u\n", item_count);
2328       fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
2329                prev_class_count, class_count);
2330       fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
2331                prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
2332                class_count ? 1.0f * item_count / class_count : 0.0f);
2333       fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
2334                non_singular_classes_count ? 1.0f * non_singular_classes_sum /
2335                non_singular_classes_count : 0.0f,
2336                non_singular_classes_count);
2337       fprintf (dump_file, "Equal symbols: %u\n", equal_items);
2338       fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
2339                item_count ? 100.0f * equal_items / item_count : 0.0f);
2340     }
2341
2342   for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2343        it != m_classes.end (); ++it)
2344     for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2345       {
2346         congruence_class *c = (*it)->classes[i];
2347
2348         if (c->members.length () == 1)
2349           continue;
2350
2351         gcc_assert (c->members.length ());
2352
2353         sem_item *source = c->members[0];
2354
2355         for (unsigned int j = 1; j < c->members.length (); j++)
2356           {
2357             sem_item *alias = c->members[j];
2358
2359             if (dump_file)
2360               {
2361                 fprintf (dump_file, "Semantic equality hit:%s->%s\n",
2362                          source->name (), alias->name ());
2363                 fprintf (dump_file, "Assembler symbol names:%s->%s\n",
2364                          source->asm_name (), alias->asm_name ());
2365               }
2366
2367             if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl)))
2368               {
2369                 if (dump_file)
2370                   fprintf (dump_file,
2371                            "Merge operation is skipped due to no_icf "
2372                            "attribute.\n\n");
2373
2374                 continue;
2375               }
2376
2377             if (dump_file && (dump_flags & TDF_DETAILS))
2378               {
2379                 source->dump_to_file (dump_file);
2380                 alias->dump_to_file (dump_file);
2381               }
2382
2383             source->merge (alias);
2384           }
2385       }
2386 }
2387
2388 /* Dump function prints all class members to a FILE with an INDENT.  */
2389
2390 void
2391 congruence_class::dump (FILE *file, unsigned int indent) const
2392 {
2393   FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
2394                   id, members[0]->get_hash (), members.length ());
2395
2396   FPUTS_SPACES (file, indent + 2, "");
2397   for (unsigned i = 0; i < members.length (); i++)
2398     fprintf (file, "%s(%p/%u) ", members[i]->asm_name (), (void *) members[i]->decl,
2399              members[i]->node->order);
2400
2401   fprintf (file, "\n");
2402 }
2403
2404 /* Returns true if there's a member that is used from another group.  */
2405
2406 bool
2407 congruence_class::is_class_used (void)
2408 {
2409   for (unsigned int i = 0; i < members.length (); i++)
2410     if (members[i]->usages.length ())
2411       return true;
2412
2413   return false;
2414 }
2415
2416 /* Initialization and computation of symtab node hash, there data
2417    are propagated later on.  */
2418
2419 static sem_item_optimizer *optimizer = NULL;
2420
2421 /* Generate pass summary for IPA ICF pass.  */
2422
2423 static void
2424 ipa_icf_generate_summary (void)
2425 {
2426   if (!optimizer)
2427     optimizer = new sem_item_optimizer ();
2428
2429   optimizer->parse_funcs_and_vars ();
2430 }
2431
2432 /* Write pass summary for IPA ICF pass.  */
2433
2434 static void
2435 ipa_icf_write_summary (void)
2436 {
2437   gcc_assert (optimizer);
2438
2439   optimizer->write_summary ();
2440 }
2441
2442 /* Read pass summary for IPA ICF pass.  */
2443
2444 static void
2445 ipa_icf_read_summary (void)
2446 {
2447   if (!optimizer)
2448     optimizer = new sem_item_optimizer ();
2449
2450   optimizer->read_summary ();
2451   optimizer->register_hooks ();
2452 }
2453
2454 /* Semantic equality exection function.  */
2455
2456 static unsigned int
2457 ipa_icf_driver (void)
2458 {
2459   gcc_assert (optimizer);
2460
2461   optimizer->execute ();
2462   optimizer->unregister_hooks ();
2463
2464   delete optimizer;
2465   optimizer = NULL;
2466
2467   return 0;
2468 }
2469
2470 const pass_data pass_data_ipa_icf =
2471 {
2472   IPA_PASS,                 /* type */
2473   "icf",                    /* name */
2474   OPTGROUP_IPA,             /* optinfo_flags */
2475   TV_IPA_ICF,               /* tv_id */
2476   0,                        /* properties_required */
2477   0,                        /* properties_provided */
2478   0,                        /* properties_destroyed */
2479   0,                        /* todo_flags_start */
2480   0,                        /* todo_flags_finish */
2481 };
2482
2483 class pass_ipa_icf : public ipa_opt_pass_d
2484 {
2485 public:
2486   pass_ipa_icf (gcc::context *ctxt)
2487     : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
2488                       ipa_icf_generate_summary, /* generate_summary */
2489                       ipa_icf_write_summary, /* write_summary */
2490                       ipa_icf_read_summary, /* read_summary */
2491                       NULL, /*
2492                       write_optimization_summary */
2493                       NULL, /*
2494                       read_optimization_summary */
2495                       NULL, /* stmt_fixup */
2496                       0, /* function_transform_todo_flags_start */
2497                       NULL, /* function_transform */
2498                       NULL) /* variable_transform */
2499   {}
2500
2501   /* opt_pass methods: */
2502   virtual bool gate (function *)
2503   {
2504     return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
2505   }
2506
2507   virtual unsigned int execute (function *)
2508   {
2509     return ipa_icf_driver();
2510   }
2511 }; // class pass_ipa_icf
2512
2513 } // ipa_icf namespace
2514
2515 ipa_opt_pass_d *
2516 make_pass_ipa_icf (gcc::context *ctxt)
2517 {
2518   return new ipa_icf::pass_ipa_icf (ctxt);
2519 }