1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2015 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
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
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
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/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
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
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
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.
56 #include "coretypes.h"
62 #include "alloc-pool.h"
63 #include "tree-pass.h"
67 #include "gimple-pretty-print.h"
68 #include "data-streamer.h"
70 #include "fold-const.h"
73 #include "gimple-iterator.h"
75 #include "symbol-summary.h"
77 #include "ipa-inline.h"
80 #include "print-tree.h"
81 #include "ipa-utils.h"
82 #include "ipa-icf-gimple.h"
84 #include "stor-layout.h"
87 using namespace ipa_icf_gimple;
91 /* Initialization and computation of symtab node hash, there data
92 are propagated later on. */
94 static sem_item_optimizer *optimizer = NULL;
98 symbol_compare_collection::symbol_compare_collection (symtab_node *node)
100 m_references.create (0);
101 m_interposables.create (0);
105 if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
108 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
110 if (ref->address_matters_p ())
111 m_references.safe_push (ref->referred);
113 if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE)
115 if (ref->address_matters_p ())
116 m_references.safe_push (ref->referred);
118 m_interposables.safe_push (ref->referred);
122 if (is_a <cgraph_node *> (node))
124 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
126 for (cgraph_edge *e = cnode->callees; e; e = e->next_callee)
127 if (e->callee->get_availability () <= AVAIL_INTERPOSABLE)
128 m_interposables.safe_push (e->callee);
132 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
134 sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index):
135 item (_item), index (_index)
139 /* Semantic item constructor for a node of _TYPE, where STACK is used
140 for bitmap memory allocation. */
142 sem_item::sem_item (sem_item_type _type,
143 bitmap_obstack *stack): type (_type), m_hash (0)
148 /* Semantic item constructor for a node of _TYPE, where STACK is used
149 for bitmap memory allocation. The item is based on symtab node _NODE
150 with computed _HASH. */
152 sem_item::sem_item (sem_item_type _type, symtab_node *_node,
153 hashval_t _hash, bitmap_obstack *stack): type(_type),
154 node (_node), m_hash (_hash)
160 /* Add reference to a semantic TARGET. */
163 sem_item::add_reference (sem_item *target)
165 refs.safe_push (target);
166 unsigned index = refs.length ();
167 target->usages.safe_push (new sem_usage_pair(this, index));
168 bitmap_set_bit (target->usage_index_bitmap, index);
169 refs_set.add (target->node);
172 /* Initialize internal data structures. Bitmap STACK is used for
173 bitmap memory allocation process. */
176 sem_item::setup (bitmap_obstack *stack)
178 gcc_checking_assert (node);
181 tree_refs.create (0);
183 usage_index_bitmap = BITMAP_ALLOC (stack);
186 sem_item::~sem_item ()
188 for (unsigned i = 0; i < usages.length (); i++)
192 tree_refs.release ();
195 BITMAP_FREE (usage_index_bitmap);
198 /* Dump function for debugging purpose. */
201 sem_item::dump (void)
205 fprintf (dump_file, "[%s] %s (%u) (tree:%p)\n", type == FUNC ? "func" : "var",
206 node->name(), node->order, (void *) node->decl);
207 fprintf (dump_file, " hash: %u\n", get_hash ());
208 fprintf (dump_file, " references: ");
210 for (unsigned i = 0; i < refs.length (); i++)
211 fprintf (dump_file, "%s%s ", refs[i]->node->name (),
212 i < refs.length() - 1 ? "," : "");
214 fprintf (dump_file, "\n");
218 /* Return true if target supports alias symbols. */
221 sem_item::target_supports_symbol_aliases_p (void)
223 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
230 void sem_item::set_hash (hashval_t hash)
235 /* Semantic function constructor that uses STACK as bitmap memory stack. */
237 sem_function::sem_function (bitmap_obstack *stack): sem_item (FUNC, stack),
238 m_checker (NULL), m_compared_func (NULL)
241 bb_sorted.create (0);
244 /* Constructor based on callgraph node _NODE with computed hash _HASH.
245 Bitmap STACK is used for memory allocation. */
246 sem_function::sem_function (cgraph_node *node, hashval_t hash,
247 bitmap_obstack *stack):
248 sem_item (FUNC, node, hash, stack),
249 m_checker (NULL), m_compared_func (NULL)
252 bb_sorted.create (0);
255 sem_function::~sem_function ()
257 for (unsigned i = 0; i < bb_sorted.length (); i++)
258 delete (bb_sorted[i]);
261 bb_sorted.release ();
264 /* Calculates hash value based on a BASIC_BLOCK. */
267 sem_function::get_bb_hash (const sem_bb *basic_block)
269 inchash::hash hstate;
271 hstate.add_int (basic_block->nondbg_stmt_count);
272 hstate.add_int (basic_block->edge_count);
274 return hstate.end ();
277 /* References independent hash function. */
280 sem_function::get_hash (void)
284 inchash::hash hstate;
285 hstate.add_int (177454); /* Random number for function type. */
287 hstate.add_int (arg_count);
288 hstate.add_int (cfg_checksum);
289 hstate.add_int (gcode_hash);
291 for (unsigned i = 0; i < bb_sorted.length (); i++)
292 hstate.merge_hash (get_bb_hash (bb_sorted[i]));
294 for (unsigned i = 0; i < bb_sizes.length (); i++)
295 hstate.add_int (bb_sizes[i]);
297 /* Add common features of declaration itself. */
298 if (DECL_FUNCTION_SPECIFIC_TARGET (decl))
300 (cl_target_option_hash
301 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl))));
302 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))
303 (cl_optimization_hash
304 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))));
305 hstate.add_flag (DECL_CXX_CONSTRUCTOR_P (decl));
306 hstate.add_flag (DECL_CXX_DESTRUCTOR_P (decl));
308 set_hash (hstate.end ());
314 /* Return ture if A1 and A2 represent equivalent function attribute lists.
315 Based on comp_type_attributes. */
318 sem_item::compare_attributes (const_tree a1, const_tree a2)
323 for (a = a1; a != NULL_TREE; a = TREE_CHAIN (a))
325 const struct attribute_spec *as;
328 as = lookup_attribute_spec (get_attribute_name (a));
329 /* TODO: We can introduce as->affects_decl_identity
330 and as->affects_decl_reference_identity if attribute mismatch
331 gets a common reason to give up on merging. It may not be worth
333 For example returns_nonnull affects only references, while
334 optimize attribute can be ignored because it is already lowered
335 into flags representation and compared separately. */
339 attr = lookup_attribute (as->name, CONST_CAST_TREE (a2));
340 if (!attr || !attribute_value_equal (a, attr))
345 for (a = a2; a != NULL_TREE; a = TREE_CHAIN (a))
347 const struct attribute_spec *as;
349 as = lookup_attribute_spec (get_attribute_name (a));
353 if (!lookup_attribute (as->name, CONST_CAST_TREE (a1)))
355 /* We don't need to compare trees again, as we did this
356 already in first loop. */
361 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
365 /* Compare properties of symbols N1 and N2 that does not affect semantics of
366 symbol itself but affects semantics of its references from USED_BY (which
367 may be NULL if it is unknown). If comparsion is false, symbols
368 can still be merged but any symbols referring them can't.
370 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
372 TODO: We can also split attributes to those that determine codegen of
373 a function body/variable constructor itself and those that are used when
377 sem_item::compare_referenced_symbol_properties (symtab_node *used_by,
382 if (is_a <cgraph_node *> (n1))
384 /* Inline properties matters: we do now want to merge uses of inline
385 function to uses of normal function because inline hint would be lost.
386 We however can merge inline function to noinline because the alias
387 will keep its DECL_DECLARED_INLINE flag.
389 Also ignore inline flag when optimizing for size or when function
390 is known to not be inlinable.
392 TODO: the optimize_size checks can also be assumed to be true if
393 unit has no !optimize_size functions. */
395 if ((!used_by || address || !is_a <cgraph_node *> (used_by)
396 || !opt_for_fn (used_by->decl, optimize_size))
397 && !opt_for_fn (n1->decl, optimize_size)
398 && n1->get_availability () > AVAIL_INTERPOSABLE
399 && (!DECL_UNINLINABLE (n1->decl) || !DECL_UNINLINABLE (n2->decl)))
401 if (DECL_DISREGARD_INLINE_LIMITS (n1->decl)
402 != DECL_DISREGARD_INLINE_LIMITS (n2->decl))
403 return return_false_with_msg
404 ("DECL_DISREGARD_INLINE_LIMITS are different");
406 if (DECL_DECLARED_INLINE_P (n1->decl)
407 != DECL_DECLARED_INLINE_P (n2->decl))
408 return return_false_with_msg ("inline attributes are different");
411 if (DECL_IS_OPERATOR_NEW (n1->decl)
412 != DECL_IS_OPERATOR_NEW (n2->decl))
413 return return_false_with_msg ("operator new flags are different");
416 /* Merging two definitions with a reference to equivalent vtables, but
417 belonging to a different type may result in ipa-polymorphic-call analysis
418 giving a wrong answer about the dynamic type of instance. */
419 if (is_a <varpool_node *> (n1))
421 if ((DECL_VIRTUAL_P (n1->decl) || DECL_VIRTUAL_P (n2->decl))
422 && (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl)
423 || !types_must_be_same_for_odr (DECL_CONTEXT (n1->decl),
424 DECL_CONTEXT (n2->decl)))
425 && (!used_by || !is_a <cgraph_node *> (used_by) || address
426 || opt_for_fn (used_by->decl, flag_devirtualize)))
427 return return_false_with_msg
428 ("references to virtual tables can not be merged");
430 if (address && DECL_ALIGN (n1->decl) != DECL_ALIGN (n2->decl))
431 return return_false_with_msg ("alignment mismatch");
433 /* For functions we compare attributes in equals_wpa, because we do
434 not know what attributes may cause codegen differences, but for
435 variables just compare attributes for references - the codegen
436 for constructors is affected only by those attributes that we lower
437 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
438 if (!compare_attributes (DECL_ATTRIBUTES (n1->decl),
439 DECL_ATTRIBUTES (n2->decl)))
440 return return_false_with_msg ("different var decl attributes");
441 if (comp_type_attributes (TREE_TYPE (n1->decl),
442 TREE_TYPE (n2->decl)) != 1)
443 return return_false_with_msg ("different var type attributes");
446 /* When matching virtual tables, be sure to also match information
447 relevant for polymorphic call analysis. */
448 if (used_by && is_a <varpool_node *> (used_by)
449 && DECL_VIRTUAL_P (used_by->decl))
451 if (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl))
452 return return_false_with_msg ("virtual flag mismatch");
453 if (DECL_VIRTUAL_P (n1->decl) && is_a <cgraph_node *> (n1)
454 && (DECL_FINAL_P (n1->decl) != DECL_FINAL_P (n2->decl)))
455 return return_false_with_msg ("final flag mismatch");
460 /* Hash properties that are compared by compare_referenced_symbol_properties. */
463 sem_item::hash_referenced_symbol_properties (symtab_node *ref,
464 inchash::hash &hstate,
467 if (is_a <cgraph_node *> (ref))
469 if ((type != FUNC || address || !opt_for_fn (decl, optimize_size))
470 && !opt_for_fn (ref->decl, optimize_size)
471 && !DECL_UNINLINABLE (ref->decl))
473 hstate.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref->decl));
474 hstate.add_flag (DECL_DECLARED_INLINE_P (ref->decl));
476 hstate.add_flag (DECL_IS_OPERATOR_NEW (ref->decl));
478 else if (is_a <varpool_node *> (ref))
480 hstate.add_flag (DECL_VIRTUAL_P (ref->decl));
482 hstate.add_int (DECL_ALIGN (ref->decl));
487 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
488 point to a same function. Comparison can be skipped if IGNORED_NODES
489 contains these nodes. ADDRESS indicate if address is taken. */
492 sem_item::compare_symbol_references (
493 hash_map <symtab_node *, sem_item *> &ignored_nodes,
494 symtab_node *n1, symtab_node *n2, bool address)
496 enum availability avail1, avail2;
501 /* Never match variable and function. */
502 if (is_a <varpool_node *> (n1) != is_a <varpool_node *> (n2))
505 if (!compare_referenced_symbol_properties (node, n1, n2, address))
507 if (address && n1->equal_address_to (n2) == 1)
509 if (!address && n1->semantically_equivalent_p (n2))
512 n1 = n1->ultimate_alias_target (&avail1);
513 n2 = n2->ultimate_alias_target (&avail2);
515 if (avail1 > AVAIL_INTERPOSABLE && ignored_nodes.get (n1)
516 && avail2 > AVAIL_INTERPOSABLE && ignored_nodes.get (n2))
519 return return_false_with_msg ("different references");
522 /* If cgraph edges E1 and E2 are indirect calls, verify that
523 ECF flags are the same. */
525 bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
527 if (e1->indirect_info && e2->indirect_info)
529 int e1_flags = e1->indirect_info->ecf_flags;
530 int e2_flags = e2->indirect_info->ecf_flags;
532 if (e1_flags != e2_flags)
533 return return_false_with_msg ("ICF flags are different");
535 else if (e1->indirect_info || e2->indirect_info)
541 /* Return true if parameter I may be used. */
544 sem_function::param_used_p (unsigned int i)
546 if (ipa_node_params_sum == NULL)
549 struct ipa_node_params *parms_info = IPA_NODE_REF (get_node ());
551 if (parms_info->descriptors.is_empty ()
552 || parms_info->descriptors.length () <= i)
555 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i);
558 /* Perform additional check needed to match types function parameters that are
559 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
560 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
563 sem_function::compatible_parm_types_p (tree parm1, tree parm2)
565 /* Be sure that parameters are TBAA compatible. */
566 if (!func_checker::compatible_types_p (parm1, parm2))
567 return return_false_with_msg ("parameter type is not compatible");
569 if (POINTER_TYPE_P (parm1)
570 && (TYPE_RESTRICT (parm1) != TYPE_RESTRICT (parm2)))
571 return return_false_with_msg ("argument restrict flag mismatch");
573 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
574 if (POINTER_TYPE_P (parm1)
575 && TREE_CODE (parm1) != TREE_CODE (parm2)
576 && opt_for_fn (decl, flag_delete_null_pointer_checks))
577 return return_false_with_msg ("pointer wrt reference mismatch");
582 /* Fast equality function based on knowledge known in WPA. */
585 sem_function::equals_wpa (sem_item *item,
586 hash_map <symtab_node *, sem_item *> &ignored_nodes)
588 gcc_assert (item->type == FUNC);
589 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
590 cgraph_node *cnode2 = dyn_cast <cgraph_node *> (item->node);
592 m_compared_func = static_cast<sem_function *> (item);
594 if (cnode->thunk.thunk_p != cnode2->thunk.thunk_p)
595 return return_false_with_msg ("thunk_p mismatch");
597 if (cnode->thunk.thunk_p)
599 if (cnode->thunk.fixed_offset != cnode2->thunk.fixed_offset)
600 return return_false_with_msg ("thunk fixed_offset mismatch");
601 if (cnode->thunk.virtual_value != cnode2->thunk.virtual_value)
602 return return_false_with_msg ("thunk virtual_value mismatch");
603 if (cnode->thunk.this_adjusting != cnode2->thunk.this_adjusting)
604 return return_false_with_msg ("thunk this_adjusting mismatch");
605 if (cnode->thunk.virtual_offset_p != cnode2->thunk.virtual_offset_p)
606 return return_false_with_msg ("thunk virtual_offset_p mismatch");
607 if (cnode->thunk.add_pointer_bounds_args
608 != cnode2->thunk.add_pointer_bounds_args)
609 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
612 /* Compare special function DECL attributes. */
613 if (DECL_FUNCTION_PERSONALITY (decl)
614 != DECL_FUNCTION_PERSONALITY (item->decl))
615 return return_false_with_msg ("function personalities are different");
617 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
618 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item->decl))
619 return return_false_with_msg ("intrument function entry exit "
620 "attributes are different");
622 if (DECL_NO_LIMIT_STACK (decl) != DECL_NO_LIMIT_STACK (item->decl))
623 return return_false_with_msg ("no stack limit attributes are different");
625 if (DECL_CXX_CONSTRUCTOR_P (decl) != DECL_CXX_CONSTRUCTOR_P (item->decl))
626 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
628 if (DECL_CXX_DESTRUCTOR_P (decl) != DECL_CXX_DESTRUCTOR_P (item->decl))
629 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
631 /* TODO: pure/const flags mostly matters only for references, except for
632 the fact that codegen takes LOOPING flag as a hint that loops are
633 finite. We may arrange the code to always pick leader that has least
634 specified flags and then this can go into comparing symbol properties. */
635 if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
636 return return_false_with_msg ("decl_or_type flags are different");
638 /* Do not match polymorphic constructors of different types. They calls
639 type memory location for ipa-polymorphic-call and we do not want
640 it to get confused by wrong type. */
641 if (DECL_CXX_CONSTRUCTOR_P (decl)
642 && TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE)
644 if (TREE_CODE (TREE_TYPE (item->decl)) != METHOD_TYPE)
645 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
646 else if (!func_checker::compatible_polymorphic_types_p
647 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
648 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
649 return return_false_with_msg ("ctor polymorphic type mismatch");
652 /* Checking function TARGET and OPTIMIZATION flags. */
653 cl_target_option *tar1 = target_opts_for_fn (decl);
654 cl_target_option *tar2 = target_opts_for_fn (item->decl);
656 if (tar1 != tar2 && !cl_target_option_eq (tar1, tar2))
658 if (dump_file && (dump_flags & TDF_DETAILS))
660 fprintf (dump_file, "target flags difference");
661 cl_target_option_print_diff (dump_file, 2, tar1, tar2);
664 return return_false_with_msg ("Target flags are different");
667 cl_optimization *opt1 = opts_for_fn (decl);
668 cl_optimization *opt2 = opts_for_fn (item->decl);
670 if (opt1 != opt2 && memcmp (opt1, opt2, sizeof(cl_optimization)))
672 if (dump_file && (dump_flags & TDF_DETAILS))
674 fprintf (dump_file, "optimization flags difference");
675 cl_optimization_print_diff (dump_file, 2, opt1, opt2);
678 return return_false_with_msg ("optimization flags are different");
681 /* Result type checking. */
682 if (!func_checker::compatible_types_p
683 (TREE_TYPE (TREE_TYPE (decl)),
684 TREE_TYPE (TREE_TYPE (m_compared_func->decl))))
685 return return_false_with_msg ("result types are different");
687 /* Checking types of arguments. */
688 tree list1 = TYPE_ARG_TYPES (TREE_TYPE (decl)),
689 list2 = TYPE_ARG_TYPES (TREE_TYPE (m_compared_func->decl));
690 for (unsigned i = 0; list1 && list2;
691 list1 = TREE_CHAIN (list1), list2 = TREE_CHAIN (list2), i++)
693 tree parm1 = TREE_VALUE (list1);
694 tree parm2 = TREE_VALUE (list2);
696 /* This guard is here for function pointer with attributes (pr59927.c). */
697 if (!parm1 || !parm2)
698 return return_false_with_msg ("NULL argument type");
700 /* Verify that types are compatible to ensure that both functions
701 have same calling conventions. */
702 if (!types_compatible_p (parm1, parm2))
703 return return_false_with_msg ("parameter types are not compatible");
705 if (!param_used_p (i))
708 /* Perform additional checks for used parameters. */
709 if (!compatible_parm_types_p (parm1, parm2))
714 return return_false_with_msg ("Mismatched number of parameters");
716 if (node->num_references () != item->node->num_references ())
717 return return_false_with_msg ("different number of references");
719 /* Checking function attributes.
720 This is quadratic in number of attributes */
721 if (comp_type_attributes (TREE_TYPE (decl),
722 TREE_TYPE (item->decl)) != 1)
723 return return_false_with_msg ("different type attributes");
724 if (!compare_attributes (DECL_ATTRIBUTES (decl),
725 DECL_ATTRIBUTES (item->decl)))
726 return return_false_with_msg ("different decl attributes");
728 /* The type of THIS pointer type memory location for
729 ipa-polymorphic-call-analysis. */
730 if (opt_for_fn (decl, flag_devirtualize)
731 && (TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE
732 || TREE_CODE (TREE_TYPE (item->decl)) == METHOD_TYPE)
734 && compare_polymorphic_p ())
736 if (TREE_CODE (TREE_TYPE (decl)) != TREE_CODE (TREE_TYPE (item->decl)))
737 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
738 if (!func_checker::compatible_polymorphic_types_p
739 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
740 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
741 return return_false_with_msg ("THIS pointer ODR type mismatch");
744 ipa_ref *ref = NULL, *ref2 = NULL;
745 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
747 item->node->iterate_reference (i, ref2);
749 if (ref->use != ref2->use)
750 return return_false_with_msg ("reference use mismatch");
752 if (!compare_symbol_references (ignored_nodes, ref->referred,
754 ref->address_matters_p ()))
758 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
759 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
763 if (!compare_symbol_references (ignored_nodes, e1->callee,
766 if (!compare_edge_flags (e1, e2))
769 e1 = e1->next_callee;
770 e2 = e2->next_callee;
774 return return_false_with_msg ("different number of calls");
776 e1 = dyn_cast <cgraph_node *> (node)->indirect_calls;
777 e2 = dyn_cast <cgraph_node *> (item->node)->indirect_calls;
781 if (!compare_edge_flags (e1, e2))
784 e1 = e1->next_callee;
785 e2 = e2->next_callee;
789 return return_false_with_msg ("different number of indirect calls");
794 /* Update hash by address sensitive references. We iterate over all
795 sensitive references (address_matters_p) and we hash ultime alias
796 target of these nodes, which can improve a semantic item hash.
798 Also hash in referenced symbols properties. This can be done at any time
799 (as the properties should not change), but it is convenient to do it here
800 while we walk the references anyway. */
803 sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
804 sem_item *> &m_symtab_node_map)
807 inchash::hash hstate (get_hash ());
809 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
811 hstate.add_int (ref->use);
812 hash_referenced_symbol_properties (ref->referred, hstate,
813 ref->use == IPA_REF_ADDR);
814 if (ref->address_matters_p () || !m_symtab_node_map.get (ref->referred))
815 hstate.add_int (ref->referred->ultimate_alias_target ()->order);
818 if (is_a <cgraph_node *> (node))
820 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
823 sem_item **result = m_symtab_node_map.get (e->callee);
824 hash_referenced_symbol_properties (e->callee, hstate, false);
826 hstate.add_int (e->callee->ultimate_alias_target ()->order);
830 set_hash (hstate.end ());
833 /* Update hash by computed local hash values taken from different
835 TODO: stronger SCC based hashing would be desirable here. */
838 sem_item::update_hash_by_local_refs (hash_map <symtab_node *,
839 sem_item *> &m_symtab_node_map)
842 inchash::hash state (get_hash ());
844 for (unsigned j = 0; node->iterate_reference (j, ref); j++)
846 sem_item **result = m_symtab_node_map.get (ref->referring);
848 state.merge_hash ((*result)->get_hash ());
853 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e;
856 sem_item **result = m_symtab_node_map.get (e->caller);
858 state.merge_hash ((*result)->get_hash ());
862 global_hash = state.end ();
865 /* Returns true if the item equals to ITEM given as argument. */
868 sem_function::equals (sem_item *item,
869 hash_map <symtab_node *, sem_item *> &)
871 gcc_assert (item->type == FUNC);
872 bool eq = equals_private (item);
874 if (m_checker != NULL)
880 if (dump_file && (dump_flags & TDF_DETAILS))
882 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
883 xstrdup_for_dump (node->name()),
884 xstrdup_for_dump (item->node->name ()),
887 xstrdup_for_dump (node->asm_name ()),
888 xstrdup_for_dump (item->node->asm_name ()),
889 eq ? "true" : "false");
894 /* Processes function equality comparison. */
897 sem_function::equals_private (sem_item *item)
899 if (item->type != FUNC)
902 basic_block bb1, bb2;
904 edge_iterator ei1, ei2;
908 m_compared_func = static_cast<sem_function *> (item);
910 gcc_assert (decl != item->decl);
912 if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
913 || edge_count != m_compared_func->edge_count
914 || cfg_checksum != m_compared_func->cfg_checksum)
915 return return_false ();
917 m_checker = new func_checker (decl, m_compared_func->decl,
918 compare_polymorphic_p (),
921 &m_compared_func->refs_set);
922 arg1 = DECL_ARGUMENTS (decl);
923 arg2 = DECL_ARGUMENTS (m_compared_func->decl);
925 arg1 && arg2; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2), i++)
927 if (!types_compatible_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
928 return return_false_with_msg ("argument types are not compatible");
929 if (!param_used_p (i))
931 /* Perform additional checks for used parameters. */
932 if (!compatible_parm_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
934 if (!m_checker->compare_decl (arg1, arg2))
935 return return_false ();
938 return return_false_with_msg ("Mismatched number of arguments");
940 if (!dyn_cast <cgraph_node *> (node)->has_gimple_body_p ())
943 /* Fill-up label dictionary. */
944 for (unsigned i = 0; i < bb_sorted.length (); ++i)
946 m_checker->parse_labels (bb_sorted[i]);
947 m_checker->parse_labels (m_compared_func->bb_sorted[i]);
950 /* Checking all basic blocks. */
951 for (unsigned i = 0; i < bb_sorted.length (); ++i)
952 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
953 return return_false();
955 dump_message ("All BBs are equal\n");
957 auto_vec <int> bb_dict;
959 /* Basic block edges check. */
960 for (unsigned i = 0; i < bb_sorted.length (); ++i)
962 bb1 = bb_sorted[i]->bb;
963 bb2 = m_compared_func->bb_sorted[i]->bb;
965 ei2 = ei_start (bb2->preds);
967 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
971 if (e1->flags != e2->flags)
972 return return_false_with_msg ("flags comparison returns false");
974 if (!bb_dict_test (&bb_dict, e1->src->index, e2->src->index))
975 return return_false_with_msg ("edge comparison returns false");
977 if (!bb_dict_test (&bb_dict, e1->dest->index, e2->dest->index))
978 return return_false_with_msg ("BB comparison returns false");
980 if (!m_checker->compare_edge (e1, e2))
981 return return_false_with_msg ("edge comparison returns false");
987 /* Basic block PHI nodes comparison. */
988 for (unsigned i = 0; i < bb_sorted.length (); i++)
989 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
990 return return_false_with_msg ("PHI node comparison returns false");
995 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
996 Helper for call_for_symbol_thunks_and_aliases. */
999 set_local (cgraph_node *node, void *data)
1001 node->local.local = data != NULL;
1005 /* TREE_ADDRESSABLE of NODE to true.
1006 Helper for call_for_symbol_thunks_and_aliases. */
1009 set_addressable (varpool_node *node, void *)
1011 TREE_ADDRESSABLE (node->decl) = 1;
1015 /* Clear DECL_RTL of NODE.
1016 Helper for call_for_symbol_thunks_and_aliases. */
1019 clear_decl_rtl (symtab_node *node, void *)
1021 SET_DECL_RTL (node->decl, NULL);
1025 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1026 possible. Return number of redirections made. */
1029 redirect_all_callers (cgraph_node *n, cgraph_node *to)
1031 int nredirected = 0;
1033 cgraph_edge *e = n->callers;
1037 /* Redirecting thunks to interposable symbols or symbols in other sections
1038 may not be supported by target output code. Play safe for now and
1039 punt on redirection. */
1040 if (!e->caller->thunk.thunk_p)
1042 struct cgraph_edge *nexte = e->next_caller;
1043 e->redirect_callee (to);
1050 for (unsigned i = 0; n->iterate_direct_aliases (i, ref);)
1052 bool removed = false;
1053 cgraph_node *n_alias = dyn_cast <cgraph_node *> (ref->referring);
1055 if ((DECL_COMDAT_GROUP (n->decl)
1056 && (DECL_COMDAT_GROUP (n->decl)
1057 == DECL_COMDAT_GROUP (n_alias->decl)))
1058 || (n_alias->get_availability () > AVAIL_INTERPOSABLE
1059 && n->get_availability () > AVAIL_INTERPOSABLE))
1061 nredirected += redirect_all_callers (n_alias, to);
1062 if (n_alias->can_remove_if_no_direct_calls_p ()
1063 && !n_alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1065 && !n_alias->has_aliases_p ())
1074 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1078 sem_function::merge (sem_item *alias_item)
1080 gcc_assert (alias_item->type == FUNC);
1082 sem_function *alias_func = static_cast<sem_function *> (alias_item);
1084 cgraph_node *original = get_node ();
1085 cgraph_node *local_original = NULL;
1086 cgraph_node *alias = alias_func->get_node ();
1088 bool create_wrapper = false;
1089 bool create_alias = false;
1090 bool redirect_callers = false;
1091 bool remove = false;
1093 bool original_discardable = false;
1094 bool original_discarded = false;
1096 bool original_address_matters = original->address_matters_p ();
1097 bool alias_address_matters = alias->address_matters_p ();
1099 if (DECL_EXTERNAL (alias->decl))
1102 fprintf (dump_file, "Not unifying; alias is external.\n\n");
1106 if (DECL_NO_INLINE_WARNING_P (original->decl)
1107 != DECL_NO_INLINE_WARNING_P (alias->decl))
1112 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1116 /* Do not attempt to mix functions from different user sections;
1117 we do not know what user intends with those. */
1118 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
1119 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
1120 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
1125 "original and alias are in different sections.\n\n");
1129 /* See if original is in a section that can be discarded if the main
1130 symbol is not used. */
1132 if (original->can_be_discarded_p ())
1133 original_discardable = true;
1134 /* Also consider case where we have resolution info and we know that
1135 original's definition is not going to be used. In this case we can not
1136 create alias to original. */
1137 if (node->resolution != LDPR_UNKNOWN
1138 && !decl_binds_to_current_def_p (node->decl))
1139 original_discardable = original_discarded = true;
1141 /* Creating a symtab alias is the optimal way to merge.
1142 It however can not be used in the following cases:
1144 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1145 2) if ORIGINAL is in a section that may be discarded by linker or if
1146 it is an external functions where we can not create an alias
1147 (ORIGINAL_DISCARDABLE)
1148 3) if target do not support symbol aliases.
1149 4) original and alias lie in different comdat groups.
1151 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1152 and/or redirect all callers from ALIAS to ORIGINAL. */
1153 if ((original_address_matters && alias_address_matters)
1154 || (original_discardable
1155 && (!DECL_COMDAT_GROUP (alias->decl)
1156 || (DECL_COMDAT_GROUP (alias->decl)
1157 != DECL_COMDAT_GROUP (original->decl))))
1158 || original_discarded
1159 || !sem_item::target_supports_symbol_aliases_p ()
1160 || DECL_COMDAT_GROUP (alias->decl) != DECL_COMDAT_GROUP (original->decl))
1162 /* First see if we can produce wrapper. */
1164 /* Symbol properties that matter for references must be preserved.
1165 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1166 with proper properties. */
1167 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1168 alias->address_taken))
1172 "Wrapper cannot be created because referenced symbol "
1173 "properties mismatch\n");
1175 /* Do not turn function in one comdat group into wrapper to another
1176 comdat group. Other compiler producing the body of the
1177 another comdat group may make opossite decision and with unfortunate
1178 linker choices this may close a loop. */
1179 else if (DECL_COMDAT_GROUP (original->decl)
1180 && DECL_COMDAT_GROUP (alias->decl)
1181 && (DECL_COMDAT_GROUP (alias->decl)
1182 != DECL_COMDAT_GROUP (original->decl)))
1186 "Wrapper cannot be created because of COMDAT\n");
1188 else if (DECL_STATIC_CHAIN (alias->decl))
1192 "Can not create wrapper of nested functions.\n");
1194 /* TODO: We can also deal with variadic functions never calling
1196 else if (stdarg_p (TREE_TYPE (alias->decl)))
1200 "can not create wrapper of stdarg function.\n");
1202 else if (inline_summaries
1203 && inline_summaries->get (alias)->self_size <= 2)
1206 fprintf (dump_file, "Wrapper creation is not "
1207 "profitable (function is too small).\n");
1209 /* If user paid attention to mark function noinline, assume it is
1210 somewhat special and do not try to turn it into a wrapper that can
1211 not be undone by inliner. */
1212 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
1215 fprintf (dump_file, "Wrappers are not created for noinline.\n");
1218 create_wrapper = true;
1220 /* We can redirect local calls in the case both alias and orignal
1221 are not interposable. */
1223 = alias->get_availability () > AVAIL_INTERPOSABLE
1224 && original->get_availability () > AVAIL_INTERPOSABLE
1225 && !alias->instrumented_version;
1226 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1227 with proper properties. */
1228 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1229 alias->address_taken))
1230 redirect_callers = false;
1232 if (!redirect_callers && !create_wrapper)
1235 fprintf (dump_file, "Not unifying; can not redirect callers nor "
1236 "produce wrapper\n\n");
1240 /* Work out the symbol the wrapper should call.
1241 If ORIGINAL is interposable, we need to call a local alias.
1242 Also produce local alias (if possible) as an optimization.
1244 Local aliases can not be created inside comdat groups because that
1245 prevents inlining. */
1246 if (!original_discardable && !original->get_comdat_group ())
1249 = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
1251 && original->get_availability () > AVAIL_INTERPOSABLE)
1252 local_original = original;
1254 /* If we can not use local alias, fallback to the original
1256 else if (original->get_availability () > AVAIL_INTERPOSABLE)
1257 local_original = original;
1259 /* If original is COMDAT local, we can not really redirect calls outside
1260 of its comdat group to it. */
1261 if (original->comdat_local_p ())
1262 redirect_callers = false;
1263 if (!local_original)
1266 fprintf (dump_file, "Not unifying; "
1267 "can not produce local alias.\n\n");
1271 if (!redirect_callers && !create_wrapper)
1274 fprintf (dump_file, "Not unifying; "
1275 "can not redirect callers nor produce a wrapper\n\n");
1279 && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1281 && !alias->can_remove_if_no_direct_calls_p ())
1284 fprintf (dump_file, "Not unifying; can not make wrapper and "
1285 "function has other uses than direct calls\n\n");
1290 create_alias = true;
1292 if (redirect_callers)
1294 int nredirected = redirect_all_callers (alias, local_original);
1298 alias->icf_merged = true;
1299 local_original->icf_merged = true;
1301 if (dump_file && nredirected)
1302 fprintf (dump_file, "%i local calls have been "
1303 "redirected.\n", nredirected);
1306 /* If all callers was redirected, do not produce wrapper. */
1307 if (alias->can_remove_if_no_direct_calls_p ()
1308 && !alias->has_aliases_p ())
1310 create_wrapper = false;
1313 gcc_assert (!create_alias);
1315 else if (create_alias)
1317 alias->icf_merged = true;
1319 /* Remove the function's body. */
1320 ipa_merge_profiles (original, alias);
1321 alias->release_body (true);
1323 /* Notice global symbol possibly produced RTL. */
1324 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
1327 /* Create the alias. */
1328 cgraph_node::create_alias (alias_func->decl, decl);
1329 alias->resolve_alias (original);
1331 original->call_for_symbol_thunks_and_aliases
1332 (set_local, (void *)(size_t) original->local_p (), true);
1335 fprintf (dump_file, "Unified; Function alias has been created.\n\n");
1339 gcc_assert (!create_alias);
1340 alias->icf_merged = true;
1341 local_original->icf_merged = true;
1343 ipa_merge_profiles (local_original, alias, true);
1344 alias->create_wrapper (local_original);
1347 fprintf (dump_file, "Unified; Wrapper has been created.\n\n");
1350 /* It's possible that redirection can hit thunks that block
1351 redirection opportunities. */
1352 gcc_assert (alias->icf_merged || remove || redirect_callers);
1353 original->icf_merged = true;
1355 /* Inform the inliner about cross-module merging. */
1356 if ((original->lto_file_data || alias->lto_file_data)
1357 && original->lto_file_data != alias->lto_file_data)
1358 local_original->merged = original->merged = true;
1362 ipa_merge_profiles (original, alias);
1363 alias->release_body ();
1365 alias->body_removed = true;
1366 alias->icf_merged = true;
1368 fprintf (dump_file, "Unified; Function body was removed.\n");
1374 /* Semantic item initialization function. */
1377 sem_function::init (void)
1380 get_node ()->get_untransformed_body ();
1382 tree fndecl = node->decl;
1383 function *func = DECL_STRUCT_FUNCTION (fndecl);
1386 gcc_assert (SSANAMES (func));
1388 ssa_names_size = SSANAMES (func)->length ();
1392 region_tree = func->eh->region_tree;
1394 /* iterating all function arguments. */
1395 arg_count = count_formal_params (fndecl);
1397 edge_count = n_edges_for_fn (func);
1398 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1399 if (!cnode->thunk.thunk_p)
1401 cfg_checksum = coverage_compute_cfg_checksum (func);
1403 inchash::hash hstate;
1406 FOR_EACH_BB_FN (bb, func)
1408 unsigned nondbg_stmt_count = 0;
1411 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
1413 cfg_checksum = iterative_hash_host_wide_int (e->flags,
1416 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1419 gimple *stmt = gsi_stmt (gsi);
1421 if (gimple_code (stmt) != GIMPLE_DEBUG
1422 && gimple_code (stmt) != GIMPLE_PREDICT)
1424 hash_stmt (stmt, hstate);
1425 nondbg_stmt_count++;
1429 gcode_hash = hstate.end ();
1430 bb_sizes.safe_push (nondbg_stmt_count);
1432 /* Inserting basic block to hash table. */
1433 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
1434 EDGE_COUNT (bb->preds)
1435 + EDGE_COUNT (bb->succs));
1437 bb_sorted.safe_push (semantic_bb);
1443 inchash::hash hstate;
1444 hstate.add_wide_int (cnode->thunk.fixed_offset);
1445 hstate.add_wide_int (cnode->thunk.virtual_value);
1446 hstate.add_flag (cnode->thunk.this_adjusting);
1447 hstate.add_flag (cnode->thunk.virtual_offset_p);
1448 hstate.add_flag (cnode->thunk.add_pointer_bounds_args);
1449 gcode_hash = hstate.end ();
1453 /* Accumulate to HSTATE a hash of expression EXP.
1454 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1455 and DECL equality classes. */
1458 sem_item::add_expr (const_tree exp, inchash::hash &hstate)
1460 if (exp == NULL_TREE)
1462 hstate.merge_hash (0);
1466 /* Handled component can be matched in a cureful way proving equivalence
1467 even if they syntactically differ. Just skip them. */
1469 while (handled_component_p (exp))
1470 exp = TREE_OPERAND (exp, 0);
1472 enum tree_code code = TREE_CODE (exp);
1473 hstate.add_int (code);
1477 /* Use inchash::add_expr for everything that is LTO stable. */
1485 inchash::add_expr (exp, hstate);
1489 unsigned HOST_WIDE_INT idx;
1492 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1494 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp), idx, value)
1496 add_expr (value, hstate);
1501 add_expr (get_base_address (TREE_OPERAND (exp, 0)), hstate);
1507 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1510 case POINTER_PLUS_EXPR:
1513 add_expr (TREE_OPERAND (exp, 0), hstate);
1514 add_expr (TREE_OPERAND (exp, 1), hstate);
1518 inchash::hash one, two;
1519 add_expr (TREE_OPERAND (exp, 0), one);
1520 add_expr (TREE_OPERAND (exp, 1), two);
1521 hstate.add_commutative (one, two);
1525 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1526 return add_expr (TREE_OPERAND (exp, 0), hstate);
1532 /* Accumulate to HSTATE a hash of type t.
1533 TYpes that may end up being compatible after LTO type merging needs to have
1537 sem_item::add_type (const_tree type, inchash::hash &hstate)
1539 if (type == NULL_TREE)
1541 hstate.merge_hash (0);
1545 type = TYPE_MAIN_VARIANT (type);
1546 if (TYPE_CANONICAL (type))
1547 type = TYPE_CANONICAL (type);
1549 if (!AGGREGATE_TYPE_P (type))
1550 hstate.add_int (TYPE_MODE (type));
1552 if (TREE_CODE (type) == COMPLEX_TYPE)
1554 hstate.add_int (COMPLEX_TYPE);
1555 sem_item::add_type (TREE_TYPE (type), hstate);
1557 else if (INTEGRAL_TYPE_P (type))
1559 hstate.add_int (INTEGER_TYPE);
1560 hstate.add_flag (TYPE_UNSIGNED (type));
1561 hstate.add_int (TYPE_PRECISION (type));
1563 else if (VECTOR_TYPE_P (type))
1565 hstate.add_int (VECTOR_TYPE);
1566 hstate.add_int (TYPE_PRECISION (type));
1567 sem_item::add_type (TREE_TYPE (type), hstate);
1569 else if (TREE_CODE (type) == ARRAY_TYPE)
1571 hstate.add_int (ARRAY_TYPE);
1572 /* Do not hash size, so complete and incomplete types can match. */
1573 sem_item::add_type (TREE_TYPE (type), hstate);
1575 else if (RECORD_OR_UNION_TYPE_P (type))
1577 hashval_t *val = optimizer->m_type_hash_cache.get (type);
1581 inchash::hash hstate2;
1586 hstate2.add_int (RECORD_TYPE);
1587 gcc_assert (COMPLETE_TYPE_P (type));
1589 for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
1590 if (TREE_CODE (f) == FIELD_DECL)
1592 add_type (TREE_TYPE (f), hstate2);
1596 hstate2.add_int (nf);
1597 hash = hstate2.end ();
1598 hstate.add_wide_int (hash);
1599 optimizer->m_type_hash_cache.put (type, hash);
1602 hstate.add_wide_int (*val);
1606 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1609 sem_function::hash_stmt (gimple *stmt, inchash::hash &hstate)
1611 enum gimple_code code = gimple_code (stmt);
1613 hstate.add_int (code);
1618 add_expr (gimple_switch_index (as_a <gswitch *> (stmt)), hstate);
1621 hstate.add_int (gimple_assign_rhs_code (stmt));
1622 if (commutative_tree_code (gimple_assign_rhs_code (stmt))
1623 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1625 inchash::hash one, two;
1627 add_expr (gimple_assign_rhs1 (stmt), one);
1628 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt)), one);
1629 add_expr (gimple_assign_rhs2 (stmt), two);
1630 hstate.add_commutative (one, two);
1631 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1633 add_expr (gimple_assign_rhs3 (stmt), hstate);
1634 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt)), hstate);
1636 add_expr (gimple_assign_lhs (stmt), hstate);
1637 add_type (TREE_TYPE (gimple_assign_lhs (stmt)), two);
1640 /* ... fall through ... */
1646 /* All these statements are equivalent if their operands are. */
1647 for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1649 add_expr (gimple_op (stmt, i), hstate);
1650 if (gimple_op (stmt, i))
1651 add_type (TREE_TYPE (gimple_op (stmt, i)), hstate);
1659 /* Return true if polymorphic comparison must be processed. */
1662 sem_function::compare_polymorphic_p (void)
1664 struct cgraph_edge *e;
1666 if (!opt_for_fn (get_node ()->decl, flag_devirtualize))
1668 if (get_node ()->indirect_calls != NULL)
1670 /* TODO: We can do simple propagation determining what calls may lead to
1671 a polymorphic call. */
1672 for (e = get_node ()->callees; e; e = e->next_callee)
1673 if (e->callee->definition
1674 && opt_for_fn (e->callee->decl, flag_devirtualize))
1679 /* For a given call graph NODE, the function constructs new
1680 semantic function item. */
1683 sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
1685 tree fndecl = node->decl;
1686 function *func = DECL_STRUCT_FUNCTION (fndecl);
1688 if (!func || (!node->has_gimple_body_p () && !node->thunk.thunk_p))
1691 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
1694 sem_function *f = new sem_function (node, 0, stack);
1701 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1702 return true if phi nodes are semantically equivalent in these blocks . */
1705 sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
1707 gphi_iterator si1, si2;
1709 unsigned size1, size2, i;
1713 gcc_assert (bb1 != NULL);
1714 gcc_assert (bb2 != NULL);
1716 si2 = gsi_start_phis (bb2);
1717 for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
1720 gsi_next_nonvirtual_phi (&si1);
1721 gsi_next_nonvirtual_phi (&si2);
1723 if (gsi_end_p (si1) && gsi_end_p (si2))
1726 if (gsi_end_p (si1) || gsi_end_p (si2))
1727 return return_false();
1732 tree phi_result1 = gimple_phi_result (phi1);
1733 tree phi_result2 = gimple_phi_result (phi2);
1735 if (!m_checker->compare_operand (phi_result1, phi_result2))
1736 return return_false_with_msg ("PHI results are different");
1738 size1 = gimple_phi_num_args (phi1);
1739 size2 = gimple_phi_num_args (phi2);
1742 return return_false ();
1744 for (i = 0; i < size1; ++i)
1746 t1 = gimple_phi_arg (phi1, i)->def;
1747 t2 = gimple_phi_arg (phi2, i)->def;
1749 if (!m_checker->compare_operand (t1, t2))
1750 return return_false ();
1752 e1 = gimple_phi_arg_edge (phi1, i);
1753 e2 = gimple_phi_arg_edge (phi2, i);
1755 if (!m_checker->compare_edge (e1, e2))
1756 return return_false ();
1765 /* Returns true if tree T can be compared as a handled component. */
1768 sem_function::icf_handled_component_p (tree t)
1770 tree_code tc = TREE_CODE (t);
1772 return (handled_component_p (t)
1773 || tc == ADDR_EXPR || tc == MEM_REF || tc == OBJ_TYPE_REF);
1776 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1777 corresponds to TARGET. */
1780 sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
1785 if (bb_dict->length () <= (unsigned)source)
1786 bb_dict->safe_grow_cleared (source + 1);
1788 if ((*bb_dict)[source] == 0)
1790 (*bb_dict)[source] = target;
1794 return (*bb_dict)[source] == target;
1798 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1800 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
1804 /* Constructor based on varpool node _NODE with computed hash _HASH.
1805 Bitmap STACK is used for memory allocation. */
1807 sem_variable::sem_variable (varpool_node *node, hashval_t _hash,
1808 bitmap_obstack *stack): sem_item(VAR,
1811 gcc_checking_assert (node);
1812 gcc_checking_assert (get_node ());
1815 /* Fast equality function based on knowledge known in WPA. */
1818 sem_variable::equals_wpa (sem_item *item,
1819 hash_map <symtab_node *, sem_item *> &ignored_nodes)
1821 gcc_assert (item->type == VAR);
1823 if (node->num_references () != item->node->num_references ())
1824 return return_false_with_msg ("different number of references");
1826 if (DECL_TLS_MODEL (decl) || DECL_TLS_MODEL (item->decl))
1827 return return_false_with_msg ("TLS model");
1829 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1830 alignment out of all aliases. */
1832 if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
1833 return return_false_with_msg ("Virtual flag mismatch");
1835 if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
1836 && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
1837 || !operand_equal_p (DECL_SIZE (decl),
1838 DECL_SIZE (item->decl), OEP_ONLY_CONST)))
1839 return return_false_with_msg ("size mismatch");
1841 /* Do not attempt to mix data from different user sections;
1842 we do not know what user intends with those. */
1843 if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
1844 || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
1845 && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
1846 return return_false_with_msg ("user section mismatch");
1848 if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
1849 return return_false_with_msg ("text section");
1851 ipa_ref *ref = NULL, *ref2 = NULL;
1852 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
1854 item->node->iterate_reference (i, ref2);
1856 if (ref->use != ref2->use)
1857 return return_false_with_msg ("reference use mismatch");
1859 if (!compare_symbol_references (ignored_nodes,
1860 ref->referred, ref2->referred,
1861 ref->address_matters_p ()))
1868 /* Returns true if the item equals to ITEM given as argument. */
1871 sem_variable::equals (sem_item *item,
1872 hash_map <symtab_node *, sem_item *> &)
1874 gcc_assert (item->type == VAR);
1877 if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
1878 dyn_cast <varpool_node *>(node)->get_constructor ();
1879 if (DECL_INITIAL (item->decl) == error_mark_node && in_lto_p)
1880 dyn_cast <varpool_node *>(item->node)->get_constructor ();
1882 /* As seen in PR ipa/65303 we have to compare variables types. */
1883 if (!func_checker::compatible_types_p (TREE_TYPE (decl),
1884 TREE_TYPE (item->decl)))
1885 return return_false_with_msg ("variables types are different");
1887 ret = sem_variable::equals (DECL_INITIAL (decl),
1888 DECL_INITIAL (item->node->decl));
1889 if (dump_file && (dump_flags & TDF_DETAILS))
1891 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1892 xstrdup_for_dump (node->name()),
1893 xstrdup_for_dump (item->node->name ()),
1894 node->order, item->node->order,
1895 xstrdup_for_dump (node->asm_name ()),
1896 xstrdup_for_dump (item->node->asm_name ()), ret ? "true" : "false");
1901 /* Compares trees T1 and T2 for semantic equality. */
1904 sem_variable::equals (tree t1, tree t2)
1907 return return_with_debug (t1 == t2);
1910 tree_code tc1 = TREE_CODE (t1);
1911 tree_code tc2 = TREE_CODE (t2);
1914 return return_false_with_msg ("TREE_CODE mismatch");
1920 vec<constructor_elt, va_gc> *v1, *v2;
1921 unsigned HOST_WIDE_INT idx;
1923 enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
1924 if (typecode != TREE_CODE (TREE_TYPE (t2)))
1925 return return_false_with_msg ("constructor type mismatch");
1927 if (typecode == ARRAY_TYPE)
1929 HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
1930 /* For arrays, check that the sizes all match. */
1931 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
1933 || size_1 != int_size_in_bytes (TREE_TYPE (t2)))
1934 return return_false_with_msg ("constructor array size mismatch");
1936 else if (!func_checker::compatible_types_p (TREE_TYPE (t1),
1938 return return_false_with_msg ("constructor type incompatible");
1940 v1 = CONSTRUCTOR_ELTS (t1);
1941 v2 = CONSTRUCTOR_ELTS (t2);
1942 if (vec_safe_length (v1) != vec_safe_length (v2))
1943 return return_false_with_msg ("constructor number of elts mismatch");
1945 for (idx = 0; idx < vec_safe_length (v1); ++idx)
1947 constructor_elt *c1 = &(*v1)[idx];
1948 constructor_elt *c2 = &(*v2)[idx];
1950 /* Check that each value is the same... */
1951 if (!sem_variable::equals (c1->value, c2->value))
1953 /* ... and that they apply to the same fields! */
1954 if (!sem_variable::equals (c1->index, c2->index))
1961 tree x1 = TREE_OPERAND (t1, 0);
1962 tree x2 = TREE_OPERAND (t2, 0);
1963 tree y1 = TREE_OPERAND (t1, 1);
1964 tree y2 = TREE_OPERAND (t2, 1);
1966 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
1967 return return_false ();
1969 /* Type of the offset on MEM_REF does not matter. */
1970 return return_with_debug (sem_variable::equals (x1, x2)
1971 && wi::to_offset (y1)
1972 == wi::to_offset (y2));
1977 tree op1 = TREE_OPERAND (t1, 0);
1978 tree op2 = TREE_OPERAND (t2, 0);
1979 return sem_variable::equals (op1, op2);
1981 /* References to other vars/decls are compared using ipa-ref. */
1984 if (decl_in_symtab_p (t1) && decl_in_symtab_p (t2))
1986 return return_false_with_msg ("Declaration mismatch");
1988 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1989 need to process its VAR/FUNCTION references without relying on ipa-ref
1993 return return_false_with_msg ("Declaration mismatch");
1995 /* Integer constants are the same only if the same width of type. */
1996 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1997 return return_false_with_msg ("INTEGER_CST precision mismatch");
1998 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1999 return return_false_with_msg ("INTEGER_CST mode mismatch");
2000 return return_with_debug (tree_int_cst_equal (t1, t2));
2002 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
2003 return return_false_with_msg ("STRING_CST mode mismatch");
2004 if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
2005 return return_false_with_msg ("STRING_CST length mismatch");
2006 if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
2007 TREE_STRING_LENGTH (t1)))
2008 return return_false_with_msg ("STRING_CST mismatch");
2011 /* Fixed constants are the same only if the same width of type. */
2012 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2013 return return_false_with_msg ("FIXED_CST precision mismatch");
2015 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
2016 TREE_FIXED_CST (t2)));
2018 return (sem_variable::equals (TREE_REALPART (t1), TREE_REALPART (t2))
2019 && sem_variable::equals (TREE_IMAGPART (t1), TREE_IMAGPART (t2)));
2021 /* Real constants are the same only if the same width of type. */
2022 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2023 return return_false_with_msg ("REAL_CST precision mismatch");
2024 return return_with_debug (real_identical (&TREE_REAL_CST (t1),
2025 &TREE_REAL_CST (t2)));
2030 if (VECTOR_CST_NELTS (t1) != VECTOR_CST_NELTS (t2))
2031 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2033 for (i = 0; i < VECTOR_CST_NELTS (t1); ++i)
2034 if (!sem_variable::equals (VECTOR_CST_ELT (t1, i),
2035 VECTOR_CST_ELT (t2, i)))
2041 case ARRAY_RANGE_REF:
2043 tree x1 = TREE_OPERAND (t1, 0);
2044 tree x2 = TREE_OPERAND (t2, 0);
2045 tree y1 = TREE_OPERAND (t1, 1);
2046 tree y2 = TREE_OPERAND (t2, 1);
2048 if (!sem_variable::equals (x1, x2) || !sem_variable::equals (y1, y2))
2050 if (!sem_variable::equals (array_ref_low_bound (t1),
2051 array_ref_low_bound (t2)))
2053 if (!sem_variable::equals (array_ref_element_size (t1),
2054 array_ref_element_size (t2)))
2060 case POINTER_PLUS_EXPR:
2065 tree x1 = TREE_OPERAND (t1, 0);
2066 tree x2 = TREE_OPERAND (t2, 0);
2067 tree y1 = TREE_OPERAND (t1, 1);
2068 tree y2 = TREE_OPERAND (t2, 1);
2070 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
2074 case VIEW_CONVERT_EXPR:
2075 if (!func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
2076 return return_false ();
2077 return sem_variable::equals (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
2079 return return_false_with_msg ("ERROR_MARK");
2081 return return_false_with_msg ("Unknown TREE code reached");
2085 /* Parser function that visits a varpool NODE. */
2088 sem_variable::parse (varpool_node *node, bitmap_obstack *stack)
2090 if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl)
2094 sem_variable *v = new sem_variable (node, 0, stack);
2101 /* References independent hash function. */
2104 sem_variable::get_hash (void)
2109 /* All WPA streamed in symbols should have their hashes computed at compile
2110 time. At this point, the constructor may not be in memory at all.
2111 DECL_INITIAL (decl) would be error_mark_node in that case. */
2112 gcc_assert (!node->lto_file_data);
2113 tree ctor = DECL_INITIAL (decl);
2114 inchash::hash hstate;
2116 hstate.add_int (456346417);
2117 if (DECL_SIZE (decl) && tree_fits_shwi_p (DECL_SIZE (decl)))
2118 hstate.add_wide_int (tree_to_shwi (DECL_SIZE (decl)));
2119 add_expr (ctor, hstate);
2120 set_hash (hstate.end ());
2125 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2129 sem_variable::merge (sem_item *alias_item)
2131 gcc_assert (alias_item->type == VAR);
2133 if (!sem_item::target_supports_symbol_aliases_p ())
2136 fprintf (dump_file, "Not unifying; "
2137 "Symbol aliases are not supported by target\n\n");
2141 if (DECL_EXTERNAL (alias_item->decl))
2144 fprintf (dump_file, "Not unifying; alias is external.\n\n");
2148 sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
2150 varpool_node *original = get_node ();
2151 varpool_node *alias = alias_var->get_node ();
2152 bool original_discardable = false;
2154 bool original_address_matters = original->address_matters_p ();
2155 bool alias_address_matters = alias->address_matters_p ();
2157 /* See if original is in a section that can be discarded if the main
2159 Also consider case where we have resolution info and we know that
2160 original's definition is not going to be used. In this case we can not
2161 create alias to original. */
2162 if (original->can_be_discarded_p ()
2163 || (node->resolution != LDPR_UNKNOWN
2164 && !decl_binds_to_current_def_p (node->decl)))
2165 original_discardable = true;
2167 gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
2169 /* Constant pool machinery is not quite ready for aliases.
2170 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2171 For LTO merging does not happen that is an important missing feature.
2172 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2173 flag is dropped and non-local symbol name is assigned. */
2174 if (DECL_IN_CONSTANT_POOL (alias->decl)
2175 || DECL_IN_CONSTANT_POOL (original->decl))
2179 "Not unifying; constant pool variables.\n\n");
2183 /* Do not attempt to mix functions from different user sections;
2184 we do not know what user intends with those. */
2185 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
2186 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
2187 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
2192 "original and alias are in different sections.\n\n");
2196 /* We can not merge if address comparsion metters. */
2197 if (original_address_matters && alias_address_matters
2198 && flag_merge_constants < 2)
2203 "adress of original and alias may be compared.\n\n");
2206 if (DECL_COMDAT_GROUP (original->decl) != DECL_COMDAT_GROUP (alias->decl))
2209 fprintf (dump_file, "Not unifying; alias cannot be created; "
2210 "across comdat group boundary\n\n");
2215 if (original_discardable)
2218 fprintf (dump_file, "Not unifying; alias cannot be created; "
2219 "target is discardable\n\n");
2225 gcc_assert (!original->alias);
2226 gcc_assert (!alias->alias);
2228 alias->analyzed = false;
2230 DECL_INITIAL (alias->decl) = NULL;
2231 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
2233 alias->need_bounds_init = false;
2234 alias->remove_all_references ();
2235 if (TREE_ADDRESSABLE (alias->decl))
2236 original->call_for_symbol_and_aliases (set_addressable, NULL, true);
2238 varpool_node::create_alias (alias_var->decl, decl);
2239 alias->resolve_alias (original);
2242 fprintf (dump_file, "Unified; Variable alias has been created.\n\n");
2248 /* Dump symbol to FILE. */
2251 sem_variable::dump_to_file (FILE *file)
2255 print_node (file, "", decl, 0);
2256 fprintf (file, "\n\n");
2259 unsigned int sem_item_optimizer::class_id = 0;
2261 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2262 m_classes_count (0), m_cgraph_node_hooks (NULL), m_varpool_node_hooks (NULL)
2265 bitmap_obstack_initialize (&m_bmstack);
2268 sem_item_optimizer::~sem_item_optimizer ()
2270 for (unsigned int i = 0; i < m_items.length (); i++)
2273 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2274 it != m_classes.end (); ++it)
2276 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2277 delete (*it)->classes[i];
2279 (*it)->classes.release ();
2285 bitmap_obstack_release (&m_bmstack);
2288 /* Write IPA ICF summary for symbols. */
2291 sem_item_optimizer::write_summary (void)
2293 unsigned int count = 0;
2295 output_block *ob = create_output_block (LTO_section_ipa_icf);
2296 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
2299 /* Calculate number of symbols to be serialized. */
2300 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2302 lsei_next_in_partition (&lsei))
2304 symtab_node *node = lsei_node (lsei);
2306 if (m_symtab_node_map.get (node))
2310 streamer_write_uhwi (ob, count);
2312 /* Process all of the symbols. */
2313 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2315 lsei_next_in_partition (&lsei))
2317 symtab_node *node = lsei_node (lsei);
2319 sem_item **item = m_symtab_node_map.get (node);
2323 int node_ref = lto_symtab_encoder_encode (encoder, node);
2324 streamer_write_uhwi_stream (ob->main_stream, node_ref);
2326 streamer_write_uhwi (ob, (*item)->get_hash ());
2330 streamer_write_char_stream (ob->main_stream, 0);
2331 produce_asm (ob, NULL);
2332 destroy_output_block (ob);
2335 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2336 contains LEN bytes. */
2339 sem_item_optimizer::read_section (lto_file_decl_data *file_data,
2340 const char *data, size_t len)
2342 const lto_function_header *header =
2343 (const lto_function_header *) data;
2344 const int cfg_offset = sizeof (lto_function_header);
2345 const int main_offset = cfg_offset + header->cfg_size;
2346 const int string_offset = main_offset + header->main_size;
2351 lto_input_block ib_main ((const char *) data + main_offset, 0,
2352 header->main_size, file_data->mode_table);
2355 lto_data_in_create (file_data, (const char *) data + string_offset,
2356 header->string_size, vNULL);
2358 count = streamer_read_uhwi (&ib_main);
2360 for (i = 0; i < count; i++)
2364 lto_symtab_encoder_t encoder;
2366 index = streamer_read_uhwi (&ib_main);
2367 encoder = file_data->symtab_node_encoder;
2368 node = lto_symtab_encoder_deref (encoder, index);
2370 hashval_t hash = streamer_read_uhwi (&ib_main);
2372 gcc_assert (node->definition);
2375 fprintf (dump_file, "Symbol added:%s (tree: %p, uid:%u)\n",
2376 node->asm_name (), (void *) node->decl, node->order);
2378 if (is_a<cgraph_node *> (node))
2380 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
2382 m_items.safe_push (new sem_function (cnode, hash, &m_bmstack));
2386 varpool_node *vnode = dyn_cast <varpool_node *> (node);
2388 m_items.safe_push (new sem_variable (vnode, hash, &m_bmstack));
2392 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
2394 lto_data_in_delete (data_in);
2397 /* Read IPA ICF summary for symbols. */
2400 sem_item_optimizer::read_summary (void)
2402 lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2403 lto_file_decl_data *file_data;
2406 while ((file_data = file_data_vec[j++]))
2409 const char *data = lto_get_section_data (file_data,
2410 LTO_section_ipa_icf, NULL, &len);
2413 read_section (file_data, data, len);
2417 /* Register callgraph and varpool hooks. */
2420 sem_item_optimizer::register_hooks (void)
2422 if (!m_cgraph_node_hooks)
2423 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
2424 (&sem_item_optimizer::cgraph_removal_hook, this);
2426 if (!m_varpool_node_hooks)
2427 m_varpool_node_hooks = symtab->add_varpool_removal_hook
2428 (&sem_item_optimizer::varpool_removal_hook, this);
2431 /* Unregister callgraph and varpool hooks. */
2434 sem_item_optimizer::unregister_hooks (void)
2436 if (m_cgraph_node_hooks)
2437 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
2439 if (m_varpool_node_hooks)
2440 symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
2443 /* Adds a CLS to hashtable associated by hash value. */
2446 sem_item_optimizer::add_class (congruence_class *cls)
2448 gcc_assert (cls->members.length ());
2450 congruence_class_group *group = get_group_by_hash (
2451 cls->members[0]->get_hash (),
2452 cls->members[0]->type);
2453 group->classes.safe_push (cls);
2456 /* Gets a congruence class group based on given HASH value and TYPE. */
2458 congruence_class_group *
2459 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
2461 congruence_class_group *item = XNEW (congruence_class_group);
2465 congruence_class_group **slot = m_classes.find_slot (item, INSERT);
2471 item->classes.create (1);
2478 /* Callgraph removal hook called for a NODE with a custom DATA. */
2481 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
2483 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2484 optimizer->remove_symtab_node (node);
2487 /* Varpool removal hook called for a NODE with a custom DATA. */
2490 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
2492 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2493 optimizer->remove_symtab_node (node);
2496 /* Remove symtab NODE triggered by symtab removal hooks. */
2499 sem_item_optimizer::remove_symtab_node (symtab_node *node)
2501 gcc_assert (!m_classes.elements());
2503 m_removed_items_set.add (node);
2507 sem_item_optimizer::remove_item (sem_item *item)
2509 if (m_symtab_node_map.get (item->node))
2510 m_symtab_node_map.remove (item->node);
2514 /* Removes all callgraph and varpool nodes that are marked by symtab
2518 sem_item_optimizer::filter_removed_items (void)
2520 auto_vec <sem_item *> filtered;
2522 for (unsigned int i = 0; i < m_items.length(); i++)
2524 sem_item *item = m_items[i];
2526 if (m_removed_items_set.contains (item->node))
2532 if (item->type == FUNC)
2534 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
2536 if (in_lto_p && (cnode->alias || cnode->body_removed))
2539 filtered.safe_push (item);
2543 if (!flag_ipa_icf_variables)
2547 /* Filter out non-readonly variables. */
2548 tree decl = item->decl;
2549 if (TREE_READONLY (decl))
2550 filtered.safe_push (item);
2557 /* Clean-up of released semantic items. */
2560 for (unsigned int i = 0; i < filtered.length(); i++)
2561 m_items.safe_push (filtered[i]);
2564 /* Optimizer entry point which returns true in case it processes
2565 a merge operation. True is returned if there's a merge operation
2569 sem_item_optimizer::execute (void)
2571 filter_removed_items ();
2572 unregister_hooks ();
2575 update_hash_by_addr_refs ();
2576 build_hash_based_classes ();
2579 fprintf (dump_file, "Dump after hash based groups\n");
2580 dump_cong_classes ();
2582 for (unsigned int i = 0; i < m_items.length(); i++)
2583 m_items[i]->init_wpa ();
2585 subdivide_classes_by_equality (true);
2588 fprintf (dump_file, "Dump after WPA based types groups\n");
2590 dump_cong_classes ();
2592 process_cong_reduction ();
2593 checking_verify_classes ();
2596 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
2598 dump_cong_classes ();
2600 parse_nonsingleton_classes ();
2601 subdivide_classes_by_equality ();
2604 fprintf (dump_file, "Dump after full equality comparison of groups\n");
2606 dump_cong_classes ();
2608 unsigned int prev_class_count = m_classes_count;
2610 process_cong_reduction ();
2611 dump_cong_classes ();
2612 checking_verify_classes ();
2613 bool merged_p = merge_classes (prev_class_count);
2615 if (dump_file && (dump_flags & TDF_DETAILS))
2616 symtab_node::dump_table (dump_file);
2621 /* Function responsible for visiting all potential functions and
2622 read-only variables that can be merged. */
2625 sem_item_optimizer::parse_funcs_and_vars (void)
2629 if (flag_ipa_icf_functions)
2630 FOR_EACH_DEFINED_FUNCTION (cnode)
2632 sem_function *f = sem_function::parse (cnode, &m_bmstack);
2635 m_items.safe_push (f);
2636 m_symtab_node_map.put (cnode, f);
2639 fprintf (dump_file, "Parsed function:%s\n", f->node->asm_name ());
2641 if (dump_file && (dump_flags & TDF_DETAILS))
2642 f->dump_to_file (dump_file);
2645 fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
2648 varpool_node *vnode;
2650 if (flag_ipa_icf_variables)
2651 FOR_EACH_DEFINED_VARIABLE (vnode)
2653 sem_variable *v = sem_variable::parse (vnode, &m_bmstack);
2657 m_items.safe_push (v);
2658 m_symtab_node_map.put (vnode, v);
2663 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2666 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
2668 item->index_in_class = cls->members.length ();
2669 cls->members.safe_push (item);
2673 /* For each semantic item, append hash values of references. */
2676 sem_item_optimizer::update_hash_by_addr_refs ()
2678 /* First, append to hash sensitive references and class type if it need to
2679 be matched for ODR. */
2680 for (unsigned i = 0; i < m_items.length (); i++)
2682 m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
2683 if (m_items[i]->type == FUNC)
2685 if (TREE_CODE (TREE_TYPE (m_items[i]->decl)) == METHOD_TYPE
2686 && contains_polymorphic_type_p
2687 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl)))
2688 && (DECL_CXX_CONSTRUCTOR_P (m_items[i]->decl)
2689 || (static_cast<sem_function *> (m_items[i])->param_used_p (0)
2690 && static_cast<sem_function *> (m_items[i])
2691 ->compare_polymorphic_p ())))
2694 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl));
2695 inchash::hash hstate (m_items[i]->get_hash ());
2697 if (TYPE_NAME (class_type)
2698 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type)))
2700 (IDENTIFIER_HASH_VALUE
2701 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type))));
2703 m_items[i]->set_hash (hstate.end ());
2708 /* Once all symbols have enhanced hash value, we can append
2709 hash values of symbols that are seen by IPA ICF and are
2710 references by a semantic item. Newly computed values
2711 are saved to global_hash member variable. */
2712 for (unsigned i = 0; i < m_items.length (); i++)
2713 m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
2715 /* Global hash value replace current hash values. */
2716 for (unsigned i = 0; i < m_items.length (); i++)
2717 m_items[i]->set_hash (m_items[i]->global_hash);
2720 /* Congruence classes are built by hash value. */
2723 sem_item_optimizer::build_hash_based_classes (void)
2725 for (unsigned i = 0; i < m_items.length (); i++)
2727 sem_item *item = m_items[i];
2729 congruence_class_group *group = get_group_by_hash (item->get_hash (),
2732 if (!group->classes.length ())
2735 group->classes.safe_push (new congruence_class (class_id++));
2738 add_item_to_class (group->classes[0], item);
2742 /* Build references according to call graph. */
2745 sem_item_optimizer::build_graph (void)
2747 for (unsigned i = 0; i < m_items.length (); i++)
2749 sem_item *item = m_items[i];
2750 m_symtab_node_map.put (item->node, item);
2752 /* Initialize hash values if we are not in LTO mode. */
2757 for (unsigned i = 0; i < m_items.length (); i++)
2759 sem_item *item = m_items[i];
2761 if (item->type == FUNC)
2763 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
2765 cgraph_edge *e = cnode->callees;
2768 sem_item **slot = m_symtab_node_map.get
2769 (e->callee->ultimate_alias_target ());
2771 item->add_reference (*slot);
2777 ipa_ref *ref = NULL;
2778 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
2780 sem_item **slot = m_symtab_node_map.get
2781 (ref->referred->ultimate_alias_target ());
2783 item->add_reference (*slot);
2788 /* Semantic items in classes having more than one element and initialized.
2789 In case of WPA, we load function body. */
2792 sem_item_optimizer::parse_nonsingleton_classes (void)
2794 unsigned int init_called_count = 0;
2796 for (unsigned i = 0; i < m_items.length (); i++)
2797 if (m_items[i]->cls->members.length () > 1)
2799 m_items[i]->init ();
2800 init_called_count++;
2804 fprintf (dump_file, "Init called for %u items (%.2f%%).\n", init_called_count,
2805 m_items.length () ? 100.0f * init_called_count / m_items.length (): 0.0f);
2808 /* Equality function for semantic items is used to subdivide existing
2809 classes. If IN_WPA, fast equality function is invoked. */
2812 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
2814 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2815 it != m_classes.end (); ++it)
2817 unsigned int class_count = (*it)->classes.length ();
2819 for (unsigned i = 0; i < class_count; i++)
2821 congruence_class *c = (*it)->classes [i];
2823 if (c->members.length() > 1)
2825 auto_vec <sem_item *> new_vector;
2827 sem_item *first = c->members[0];
2828 new_vector.safe_push (first);
2830 unsigned class_split_first = (*it)->classes.length ();
2832 for (unsigned j = 1; j < c->members.length (); j++)
2834 sem_item *item = c->members[j];
2836 bool equals = in_wpa ? first->equals_wpa (item,
2837 m_symtab_node_map) : first->equals (item, m_symtab_node_map);
2840 new_vector.safe_push (item);
2843 bool integrated = false;
2845 for (unsigned k = class_split_first; k < (*it)->classes.length (); k++)
2847 sem_item *x = (*it)->classes[k]->members[0];
2848 bool equals = in_wpa ? x->equals_wpa (item,
2849 m_symtab_node_map) : x->equals (item, m_symtab_node_map);
2854 add_item_to_class ((*it)->classes[k], item);
2862 congruence_class *c = new congruence_class (class_id++);
2864 add_item_to_class (c, item);
2866 (*it)->classes.safe_push (c);
2871 // we replace newly created new_vector for the class we've just splitted
2872 c->members.release ();
2873 c->members.create (new_vector.length ());
2875 for (unsigned int j = 0; j < new_vector.length (); j++)
2876 add_item_to_class (c, new_vector[j]);
2881 checking_verify_classes ();
2884 /* Subdivide classes by address references that members of the class
2885 reference. Example can be a pair of functions that have an address
2886 taken from a function. If these addresses are different the class
2890 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2892 typedef hash_map <symbol_compare_hash, vec <sem_item *> > subdivide_hash_map;
2894 unsigned newly_created_classes = 0;
2896 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2897 it != m_classes.end (); ++it)
2899 unsigned int class_count = (*it)->classes.length ();
2900 auto_vec<congruence_class *> new_classes;
2902 for (unsigned i = 0; i < class_count; i++)
2904 congruence_class *c = (*it)->classes [i];
2906 if (c->members.length() > 1)
2908 subdivide_hash_map split_map;
2910 for (unsigned j = 0; j < c->members.length (); j++)
2912 sem_item *source_node = c->members[j];
2914 symbol_compare_collection *collection = new symbol_compare_collection (source_node->node);
2917 vec <sem_item *> *slot = &split_map.get_or_insert (collection,
2919 gcc_checking_assert (slot);
2921 slot->safe_push (source_node);
2927 /* If the map contains more than one key, we have to split the map
2929 if (split_map.elements () != 1)
2931 bool first_class = true;
2933 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2934 it2 != split_map.end (); ++it2)
2936 congruence_class *new_cls;
2937 new_cls = new congruence_class (class_id++);
2939 for (unsigned k = 0; k < (*it2).second.length (); k++)
2940 add_item_to_class (new_cls, (*it2).second[k]);
2942 worklist_push (new_cls);
2943 newly_created_classes++;
2947 (*it)->classes[i] = new_cls;
2948 first_class = false;
2952 new_classes.safe_push (new_cls);
2958 /* Release memory. */
2959 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2960 it2 != split_map.end (); ++it2)
2962 delete (*it2).first;
2963 (*it2).second.release ();
2968 for (unsigned i = 0; i < new_classes.length (); i++)
2969 (*it)->classes.safe_push (new_classes[i]);
2972 return newly_created_classes;
2975 /* Verify congruence classes, if checking is enabled. */
2978 sem_item_optimizer::checking_verify_classes (void)
2984 /* Verify congruence classes. */
2987 sem_item_optimizer::verify_classes (void)
2989 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2990 it != m_classes.end (); ++it)
2992 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2994 congruence_class *cls = (*it)->classes[i];
2997 gcc_assert (cls->members.length () > 0);
2999 for (unsigned int j = 0; j < cls->members.length (); j++)
3001 sem_item *item = cls->members[j];
3004 gcc_assert (item->cls == cls);
3006 for (unsigned k = 0; k < item->usages.length (); k++)
3008 sem_usage_pair *usage = item->usages[k];
3009 gcc_assert (usage->item->index_in_class <
3010 usage->item->cls->members.length ());
3017 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3018 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3019 but unused argument. */
3022 sem_item_optimizer::release_split_map (congruence_class * const &,
3023 bitmap const &b, traverse_split_pair *)
3032 /* Process split operation for a class given as pointer CLS_PTR,
3033 where bitmap B splits congruence class members. DATA is used
3034 as argument of split pair. */
3037 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
3038 bitmap const &b, traverse_split_pair *pair)
3040 sem_item_optimizer *optimizer = pair->optimizer;
3041 const congruence_class *splitter_cls = pair->cls;
3043 /* If counted bits are greater than zero and less than the number of members
3044 a group will be splitted. */
3045 unsigned popcount = bitmap_count_bits (b);
3047 if (popcount > 0 && popcount < cls->members.length ())
3049 auto_vec <congruence_class *, 2> newclasses;
3050 newclasses.quick_push (new congruence_class (class_id++));
3051 newclasses.quick_push (new congruence_class (class_id++));
3053 for (unsigned int i = 0; i < cls->members.length (); i++)
3055 int target = bitmap_bit_p (b, i);
3056 congruence_class *tc = newclasses[target];
3058 add_item_to_class (tc, cls->members[i]);
3063 for (unsigned int i = 0; i < 2; i++)
3064 gcc_assert (newclasses[i]->members.length ());
3067 if (splitter_cls == cls)
3068 optimizer->splitter_class_removed = true;
3070 /* Remove old class from worklist if presented. */
3071 bool in_worklist = cls->in_worklist;
3074 cls->in_worklist = false;
3076 congruence_class_group g;
3077 g.hash = cls->members[0]->get_hash ();
3078 g.type = cls->members[0]->type;
3080 congruence_class_group *slot = optimizer->m_classes.find(&g);
3082 for (unsigned int i = 0; i < slot->classes.length (); i++)
3083 if (slot->classes[i] == cls)
3085 slot->classes.ordered_remove (i);
3089 /* New class will be inserted and integrated to work list. */
3090 for (unsigned int i = 0; i < 2; i++)
3091 optimizer->add_class (newclasses[i]);
3093 /* Two classes replace one, so that increment just by one. */
3094 optimizer->m_classes_count++;
3096 /* If OLD class was presented in the worklist, we remove the class
3097 and replace it will both newly created classes. */
3099 for (unsigned int i = 0; i < 2; i++)
3100 optimizer->worklist_push (newclasses[i]);
3101 else /* Just smaller class is inserted. */
3103 unsigned int smaller_index = newclasses[0]->members.length () <
3104 newclasses[1]->members.length () ?
3106 optimizer->worklist_push (newclasses[smaller_index]);
3109 if (dump_file && (dump_flags & TDF_DETAILS))
3111 fprintf (dump_file, " congruence class splitted:\n");
3112 cls->dump (dump_file, 4);
3114 fprintf (dump_file, " newly created groups:\n");
3115 for (unsigned int i = 0; i < 2; i++)
3116 newclasses[i]->dump (dump_file, 4);
3119 /* Release class if not presented in work list. */
3128 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3129 Bitmap stack BMSTACK is used for bitmap allocation. */
3132 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
3135 hash_map <congruence_class *, bitmap> split_map;
3137 for (unsigned int i = 0; i < cls->members.length (); i++)
3139 sem_item *item = cls->members[i];
3141 /* Iterate all usages that have INDEX as usage of the item. */
3142 for (unsigned int j = 0; j < item->usages.length (); j++)
3144 sem_usage_pair *usage = item->usages[j];
3146 if (usage->index != index)
3149 bitmap *slot = split_map.get (usage->item->cls);
3154 b = BITMAP_ALLOC (&m_bmstack);
3155 split_map.put (usage->item->cls, b);
3160 gcc_checking_assert (usage->item->cls);
3161 gcc_checking_assert (usage->item->index_in_class <
3162 usage->item->cls->members.length ());
3164 bitmap_set_bit (b, usage->item->index_in_class);
3168 traverse_split_pair pair;
3169 pair.optimizer = this;
3172 splitter_class_removed = false;
3174 <traverse_split_pair *, sem_item_optimizer::traverse_congruence_split> (&pair);
3176 /* Bitmap clean-up. */
3178 <traverse_split_pair *, sem_item_optimizer::release_split_map> (NULL);
3181 /* Every usage of a congruence class CLS is a candidate that can split the
3182 collection of classes. Bitmap stack BMSTACK is used for bitmap
3186 sem_item_optimizer::do_congruence_step (congruence_class *cls)
3191 bitmap usage = BITMAP_ALLOC (&m_bmstack);
3193 for (unsigned int i = 0; i < cls->members.length (); i++)
3194 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
3196 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
3198 if (dump_file && (dump_flags & TDF_DETAILS))
3199 fprintf (dump_file, " processing congruence step for class: %u, index: %u\n",
3202 do_congruence_step_for_index (cls, i);
3204 if (splitter_class_removed)
3208 BITMAP_FREE (usage);
3211 /* Adds a newly created congruence class CLS to worklist. */
3214 sem_item_optimizer::worklist_push (congruence_class *cls)
3216 /* Return if the class CLS is already presented in work list. */
3217 if (cls->in_worklist)
3220 cls->in_worklist = true;
3221 worklist.push_back (cls);
3224 /* Pops a class from worklist. */
3227 sem_item_optimizer::worklist_pop (void)
3229 congruence_class *cls;
3231 while (!worklist.empty ())
3233 cls = worklist.front ();
3234 worklist.pop_front ();
3235 if (cls->in_worklist)
3237 cls->in_worklist = false;
3243 /* Work list item was already intended to be removed.
3244 The only reason for doing it is to split a class.
3245 Thus, the class CLS is deleted. */
3253 /* Iterative congruence reduction function. */
3256 sem_item_optimizer::process_cong_reduction (void)
3258 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3259 it != m_classes.end (); ++it)
3260 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3261 if ((*it)->classes[i]->is_class_used ())
3262 worklist_push ((*it)->classes[i]);
3265 fprintf (dump_file, "Worklist has been filled with: %lu\n",
3266 (unsigned long) worklist.size ());
3268 if (dump_file && (dump_flags & TDF_DETAILS))
3269 fprintf (dump_file, "Congruence class reduction\n");
3271 congruence_class *cls;
3273 /* Process complete congruence reduction. */
3274 while ((cls = worklist_pop ()) != NULL)
3275 do_congruence_step (cls);
3277 /* Subdivide newly created classes according to references. */
3278 unsigned new_classes = subdivide_classes_by_sensitive_refs ();
3281 fprintf (dump_file, "Address reference subdivision created: %u "
3282 "new classes.\n", new_classes);
3285 /* Debug function prints all informations about congruence classes. */
3288 sem_item_optimizer::dump_cong_classes (void)
3294 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3295 m_classes_count, (unsigned long) m_classes.elements(), m_items.length ());
3297 /* Histogram calculation. */
3298 unsigned int max_index = 0;
3299 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
3301 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3302 it != m_classes.end (); ++it)
3304 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3306 unsigned int c = (*it)->classes[i]->members.length ();
3314 "Class size histogram [num of members]: number of classe number of classess\n");
3316 for (unsigned int i = 0; i <= max_index; i++)
3318 fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
3320 fprintf (dump_file, "\n\n");
3323 if (dump_flags & TDF_DETAILS)
3324 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3325 it != m_classes.end (); ++it)
3327 fprintf (dump_file, " group: with %u classes:\n", (*it)->classes.length ());
3329 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3331 (*it)->classes[i]->dump (dump_file, 4);
3333 if(i < (*it)->classes.length () - 1)
3334 fprintf (dump_file, " ");
3341 /* After reduction is done, we can declare all items in a group
3342 to be equal. PREV_CLASS_COUNT is start number of classes
3343 before reduction. True is returned if there's a merge operation
3347 sem_item_optimizer::merge_classes (unsigned int prev_class_count)
3349 unsigned int item_count = m_items.length ();
3350 unsigned int class_count = m_classes_count;
3351 unsigned int equal_items = item_count - class_count;
3353 unsigned int non_singular_classes_count = 0;
3354 unsigned int non_singular_classes_sum = 0;
3356 bool merged_p = false;
3358 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3359 it != m_classes.end (); ++it)
3360 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3362 congruence_class *c = (*it)->classes[i];
3363 if (c->members.length () > 1)
3365 non_singular_classes_count++;
3366 non_singular_classes_sum += c->members.length ();
3372 fprintf (dump_file, "\nItem count: %u\n", item_count);
3373 fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
3374 prev_class_count, class_count);
3375 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
3376 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
3377 class_count ? 1.0f * item_count / class_count : 0.0f);
3378 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
3379 non_singular_classes_count ? 1.0f * non_singular_classes_sum /
3380 non_singular_classes_count : 0.0f,
3381 non_singular_classes_count);
3382 fprintf (dump_file, "Equal symbols: %u\n", equal_items);
3383 fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
3384 item_count ? 100.0f * equal_items / item_count : 0.0f);
3387 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3388 it != m_classes.end (); ++it)
3389 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3391 congruence_class *c = (*it)->classes[i];
3393 if (c->members.length () == 1)
3396 gcc_assert (c->members.length ());
3398 sem_item *source = c->members[0];
3400 for (unsigned int j = 1; j < c->members.length (); j++)
3402 sem_item *alias = c->members[j];
3406 fprintf (dump_file, "Semantic equality hit:%s->%s\n",
3407 xstrdup_for_dump (source->node->name ()),
3408 xstrdup_for_dump (alias->node->name ()));
3409 fprintf (dump_file, "Assembler symbol names:%s->%s\n",
3410 xstrdup_for_dump (source->node->asm_name ()),
3411 xstrdup_for_dump (alias->node->asm_name ()));
3414 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl)))
3418 "Merge operation is skipped due to no_icf "
3424 if (dump_file && (dump_flags & TDF_DETAILS))
3426 source->dump_to_file (dump_file);
3427 alias->dump_to_file (dump_file);
3430 if (dbg_cnt (merged_ipa_icf))
3431 merged_p |= source->merge (alias);
3438 /* Dump function prints all class members to a FILE with an INDENT. */
3441 congruence_class::dump (FILE *file, unsigned int indent) const
3443 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
3444 id, members[0]->get_hash (), members.length ());
3446 FPUTS_SPACES (file, indent + 2, "");
3447 for (unsigned i = 0; i < members.length (); i++)
3448 fprintf (file, "%s(%p/%u) ", members[i]->node->asm_name (),
3449 (void *) members[i]->decl,
3450 members[i]->node->order);
3452 fprintf (file, "\n");
3455 /* Returns true if there's a member that is used from another group. */
3458 congruence_class::is_class_used (void)
3460 for (unsigned int i = 0; i < members.length (); i++)
3461 if (members[i]->usages.length ())
3467 /* Generate pass summary for IPA ICF pass. */
3470 ipa_icf_generate_summary (void)
3473 optimizer = new sem_item_optimizer ();
3475 optimizer->register_hooks ();
3476 optimizer->parse_funcs_and_vars ();
3479 /* Write pass summary for IPA ICF pass. */
3482 ipa_icf_write_summary (void)
3484 gcc_assert (optimizer);
3486 optimizer->write_summary ();
3489 /* Read pass summary for IPA ICF pass. */
3492 ipa_icf_read_summary (void)
3495 optimizer = new sem_item_optimizer ();
3497 optimizer->read_summary ();
3498 optimizer->register_hooks ();
3501 /* Semantic equality exection function. */
3504 ipa_icf_driver (void)
3506 gcc_assert (optimizer);
3508 bool merged_p = optimizer->execute ();
3513 return merged_p ? TODO_remove_functions : 0;
3516 const pass_data pass_data_ipa_icf =
3518 IPA_PASS, /* type */
3520 OPTGROUP_IPA, /* optinfo_flags */
3521 TV_IPA_ICF, /* tv_id */
3522 0, /* properties_required */
3523 0, /* properties_provided */
3524 0, /* properties_destroyed */
3525 0, /* todo_flags_start */
3526 0, /* todo_flags_finish */
3529 class pass_ipa_icf : public ipa_opt_pass_d
3532 pass_ipa_icf (gcc::context *ctxt)
3533 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
3534 ipa_icf_generate_summary, /* generate_summary */
3535 ipa_icf_write_summary, /* write_summary */
3536 ipa_icf_read_summary, /* read_summary */
3538 write_optimization_summary */
3540 read_optimization_summary */
3541 NULL, /* stmt_fixup */
3542 0, /* function_transform_todo_flags_start */
3543 NULL, /* function_transform */
3544 NULL) /* variable_transform */
3547 /* opt_pass methods: */
3548 virtual bool gate (function *)
3550 return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
3553 virtual unsigned int execute (function *)
3555 return ipa_icf_driver();
3557 }; // class pass_ipa_icf
3559 } // ipa_icf namespace
3562 make_pass_ipa_icf (gcc::context *ctxt)
3564 return new ipa_icf::pass_ipa_icf (ctxt);