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