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.
57 #include "coretypes.h"
61 #include "double-int.h"
69 #include "fold-const.h"
72 #include "hard-reg-set.h"
74 #include "dominance.h"
76 #include "basic-block.h"
77 #include "tree-ssa-alias.h"
78 #include "internal-fn.h"
79 #include "gimple-expr.h"
85 #include "statistics.h"
87 #include "fixed-value.h"
88 #include "insn-config.h"
97 #include "gimple-iterator.h"
98 #include "gimple-ssa.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"
110 #include "alloc-pool.h"
111 #include "symbol-summary.h"
112 #include "ipa-prop.h"
113 #include "ipa-inline.h"
116 #include "hash-table.h"
117 #include "coverage.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"
125 #include "stor-layout.h"
127 using namespace ipa_icf_gimple;
131 /* Initialization and computation of symtab node hash, there data
132 are propagated later on. */
134 static sem_item_optimizer *optimizer = NULL;
138 symbol_compare_collection::symbol_compare_collection (symtab_node *node)
140 m_references.create (0);
141 m_interposables.create (0);
145 if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
148 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
150 if (ref->address_matters_p ())
151 m_references.safe_push (ref->referred);
153 if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE)
155 if (ref->address_matters_p ())
156 m_references.safe_push (ref->referred);
158 m_interposables.safe_push (ref->referred);
162 if (is_a <cgraph_node *> (node))
164 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
166 for (cgraph_edge *e = cnode->callees; e; e = e->next_callee)
167 if (e->callee->get_availability () <= AVAIL_INTERPOSABLE)
168 m_interposables.safe_push (e->callee);
172 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
174 sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index):
175 item (_item), index (_index)
179 /* Semantic item constructor for a node of _TYPE, where STACK is used
180 for bitmap memory allocation. */
182 sem_item::sem_item (sem_item_type _type,
183 bitmap_obstack *stack): type(_type), hash(0)
188 /* Semantic item constructor for a node of _TYPE, where STACK is used
189 for bitmap memory allocation. The item is based on symtab node _NODE
190 with computed _HASH. */
192 sem_item::sem_item (sem_item_type _type, symtab_node *_node,
193 hashval_t _hash, bitmap_obstack *stack): type(_type),
194 node (_node), hash (_hash)
200 /* Add reference to a semantic TARGET. */
203 sem_item::add_reference (sem_item *target)
205 refs.safe_push (target);
206 unsigned index = refs.length ();
207 target->usages.safe_push (new sem_usage_pair(this, index));
208 bitmap_set_bit (target->usage_index_bitmap, index);
209 refs_set.add (target->node);
212 /* Initialize internal data structures. Bitmap STACK is used for
213 bitmap memory allocation process. */
216 sem_item::setup (bitmap_obstack *stack)
218 gcc_checking_assert (node);
221 tree_refs.create (0);
223 usage_index_bitmap = BITMAP_ALLOC (stack);
226 sem_item::~sem_item ()
228 for (unsigned i = 0; i < usages.length (); i++)
232 tree_refs.release ();
235 BITMAP_FREE (usage_index_bitmap);
238 /* Dump function for debugging purpose. */
241 sem_item::dump (void)
245 fprintf (dump_file, "[%s] %s (%u) (tree:%p)\n", type == FUNC ? "func" : "var",
246 node->name(), node->order, (void *) node->decl);
247 fprintf (dump_file, " hash: %u\n", get_hash ());
248 fprintf (dump_file, " references: ");
250 for (unsigned i = 0; i < refs.length (); i++)
251 fprintf (dump_file, "%s%s ", refs[i]->node->name (),
252 i < refs.length() - 1 ? "," : "");
254 fprintf (dump_file, "\n");
258 /* Return true if target supports alias symbols. */
261 sem_item::target_supports_symbol_aliases_p (void)
263 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
270 /* Semantic function constructor that uses STACK as bitmap memory stack. */
272 sem_function::sem_function (bitmap_obstack *stack): sem_item (FUNC, stack),
273 m_checker (NULL), m_compared_func (NULL)
275 arg_types.create (0);
277 bb_sorted.create (0);
280 /* Constructor based on callgraph node _NODE with computed hash _HASH.
281 Bitmap STACK is used for memory allocation. */
282 sem_function::sem_function (cgraph_node *node, hashval_t hash,
283 bitmap_obstack *stack):
284 sem_item (FUNC, node, hash, stack),
285 m_checker (NULL), m_compared_func (NULL)
287 arg_types.create (0);
289 bb_sorted.create (0);
292 sem_function::~sem_function ()
294 for (unsigned i = 0; i < bb_sorted.length (); i++)
295 delete (bb_sorted[i]);
297 arg_types.release ();
299 bb_sorted.release ();
302 /* Calculates hash value based on a BASIC_BLOCK. */
305 sem_function::get_bb_hash (const sem_bb *basic_block)
307 inchash::hash hstate;
309 hstate.add_int (basic_block->nondbg_stmt_count);
310 hstate.add_int (basic_block->edge_count);
312 return hstate.end ();
315 /* References independent hash function. */
318 sem_function::get_hash (void)
322 inchash::hash hstate;
323 hstate.add_int (177454); /* Random number for function type. */
325 hstate.add_int (arg_count);
326 hstate.add_int (cfg_checksum);
327 hstate.add_int (gcode_hash);
329 for (unsigned i = 0; i < bb_sorted.length (); i++)
330 hstate.merge_hash (get_bb_hash (bb_sorted[i]));
332 for (unsigned i = 0; i < bb_sizes.length (); i++)
333 hstate.add_int (bb_sizes[i]);
336 /* Add common features of declaration itself. */
337 if (DECL_FUNCTION_SPECIFIC_TARGET (decl))
339 (cl_target_option_hash
340 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl))));
341 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))
342 (cl_optimization_hash
343 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))));
344 hstate.add_flag (DECL_CXX_CONSTRUCTOR_P (decl));
345 hstate.add_flag (DECL_CXX_DESTRUCTOR_P (decl));
347 hash = hstate.end ();
353 /* Return ture if A1 and A2 represent equivalent function attribute lists.
354 Based on comp_type_attributes. */
357 sem_item::compare_attributes (const_tree a1, const_tree a2)
362 for (a = a1; a != NULL_TREE; a = TREE_CHAIN (a))
364 const struct attribute_spec *as;
367 as = lookup_attribute_spec (get_attribute_name (a));
368 /* TODO: We can introduce as->affects_decl_identity
369 and as->affects_decl_reference_identity if attribute mismatch
370 gets a common reason to give up on merging. It may not be worth
372 For example returns_nonnull affects only references, while
373 optimize attribute can be ignored because it is already lowered
374 into flags representation and compared separately. */
378 attr = lookup_attribute (as->name, CONST_CAST_TREE (a2));
379 if (!attr || !attribute_value_equal (a, attr))
384 for (a = a2; a != NULL_TREE; a = TREE_CHAIN (a))
386 const struct attribute_spec *as;
388 as = lookup_attribute_spec (get_attribute_name (a));
392 if (!lookup_attribute (as->name, CONST_CAST_TREE (a1)))
394 /* We don't need to compare trees again, as we did this
395 already in first loop. */
400 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
404 /* Compare properties of symbols N1 and N2 that does not affect semantics of
405 symbol itself but affects semantics of its references from USED_BY (which
406 may be NULL if it is unknown). If comparsion is false, symbols
407 can still be merged but any symbols referring them can't.
409 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
411 TODO: We can also split attributes to those that determine codegen of
412 a function body/variable constructor itself and those that are used when
416 sem_item::compare_referenced_symbol_properties (symtab_node *used_by,
421 if (is_a <cgraph_node *> (n1))
423 /* Inline properties matters: we do now want to merge uses of inline
424 function to uses of normal function because inline hint would be lost.
425 We however can merge inline function to noinline because the alias
426 will keep its DECL_DECLARED_INLINE flag.
428 Also ignore inline flag when optimizing for size or when function
429 is known to not be inlinable.
431 TODO: the optimize_size checks can also be assumed to be true if
432 unit has no !optimize_size functions. */
434 if ((!used_by || address || !is_a <cgraph_node *> (used_by)
435 || !opt_for_fn (used_by->decl, optimize_size))
436 && !opt_for_fn (n1->decl, optimize_size)
437 && n1->get_availability () > AVAIL_INTERPOSABLE
438 && (!DECL_UNINLINABLE (n1->decl) || !DECL_UNINLINABLE (n2->decl)))
440 if (DECL_DISREGARD_INLINE_LIMITS (n1->decl)
441 != DECL_DISREGARD_INLINE_LIMITS (n2->decl))
442 return return_false_with_msg
443 ("DECL_DISREGARD_INLINE_LIMITS are different");
445 if (DECL_DECLARED_INLINE_P (n1->decl)
446 != DECL_DECLARED_INLINE_P (n2->decl))
447 return return_false_with_msg ("inline attributes are different");
450 if (DECL_IS_OPERATOR_NEW (n1->decl)
451 != DECL_IS_OPERATOR_NEW (n2->decl))
452 return return_false_with_msg ("operator new flags are different");
455 /* Merging two definitions with a reference to equivalent vtables, but
456 belonging to a different type may result in ipa-polymorphic-call analysis
457 giving a wrong answer about the dynamic type of instance. */
458 if (is_a <varpool_node *> (n1))
460 if ((DECL_VIRTUAL_P (n1->decl) || DECL_VIRTUAL_P (n2->decl))
461 && (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl)
462 || !types_must_be_same_for_odr (DECL_CONTEXT (n1->decl),
463 DECL_CONTEXT (n2->decl)))
464 && (!used_by || !is_a <cgraph_node *> (used_by) || address
465 || opt_for_fn (used_by->decl, flag_devirtualize)))
466 return return_false_with_msg
467 ("references to virtual tables can not be merged");
469 if (address && DECL_ALIGN (n1->decl) != DECL_ALIGN (n2->decl))
470 return return_false_with_msg ("alignment mismatch");
472 /* For functions we compare attributes in equals_wpa, because we do
473 not know what attributes may cause codegen differences, but for
474 variables just compare attributes for references - the codegen
475 for constructors is affected only by those attributes that we lower
476 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
477 if (!compare_attributes (DECL_ATTRIBUTES (n1->decl),
478 DECL_ATTRIBUTES (n2->decl)))
479 return return_false_with_msg ("different var decl attributes");
480 if (comp_type_attributes (TREE_TYPE (n1->decl),
481 TREE_TYPE (n2->decl)) != 1)
482 return return_false_with_msg ("different var type attributes");
485 /* When matching virtual tables, be sure to also match information
486 relevant for polymorphic call analysis. */
487 if (used_by && is_a <varpool_node *> (used_by)
488 && DECL_VIRTUAL_P (used_by->decl))
490 if (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl))
491 return return_false_with_msg ("virtual flag mismatch");
492 if (DECL_VIRTUAL_P (n1->decl) && is_a <cgraph_node *> (n1)
493 && (DECL_FINAL_P (n1->decl) != DECL_FINAL_P (n2->decl)))
494 return return_false_with_msg ("final flag mismatch");
499 /* Hash properties that are compared by compare_referenced_symbol_properties. */
502 sem_item::hash_referenced_symbol_properties (symtab_node *ref,
503 inchash::hash &hstate,
506 if (is_a <cgraph_node *> (ref))
508 if ((!type == FUNC || address || !opt_for_fn (decl, optimize_size))
509 && !opt_for_fn (ref->decl, optimize_size)
510 && !DECL_UNINLINABLE (ref->decl))
512 hstate.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref->decl));
513 hstate.add_flag (DECL_DECLARED_INLINE_P (ref->decl));
515 hstate.add_flag (DECL_IS_OPERATOR_NEW (ref->decl));
517 else if (is_a <varpool_node *> (ref))
519 hstate.add_flag (DECL_VIRTUAL_P (ref->decl));
521 hstate.add_int (DECL_ALIGN (ref->decl));
526 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
527 point to a same function. Comparison can be skipped if IGNORED_NODES
528 contains these nodes. ADDRESS indicate if address is taken. */
531 sem_item::compare_symbol_references (
532 hash_map <symtab_node *, sem_item *> &ignored_nodes,
533 symtab_node *n1, symtab_node *n2, bool address)
535 enum availability avail1, avail2;
540 /* Never match variable and function. */
541 if (is_a <varpool_node *> (n1) != is_a <varpool_node *> (n2))
544 if (!compare_referenced_symbol_properties (node, n1, n2, address))
546 if (address && n1->equal_address_to (n2) == 1)
548 if (!address && n1->semantically_equivalent_p (n2))
551 n1 = n1->ultimate_alias_target (&avail1);
552 n2 = n2->ultimate_alias_target (&avail2);
554 if (avail1 >= AVAIL_INTERPOSABLE && ignored_nodes.get (n1)
555 && avail2 >= AVAIL_INTERPOSABLE && ignored_nodes.get (n2))
558 return return_false_with_msg ("different references");
561 /* If cgraph edges E1 and E2 are indirect calls, verify that
562 ECF flags are the same. */
564 bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
566 if (e1->indirect_info && e2->indirect_info)
568 int e1_flags = e1->indirect_info->ecf_flags;
569 int e2_flags = e2->indirect_info->ecf_flags;
571 if (e1_flags != e2_flags)
572 return return_false_with_msg ("ICF flags are different");
574 else if (e1->indirect_info || e2->indirect_info)
580 /* Return true if parameter I may be used. */
583 sem_function::param_used_p (unsigned int i)
585 if (ipa_node_params_sum == NULL)
588 struct ipa_node_params *parms_info = IPA_NODE_REF (get_node ());
590 if (parms_info->descriptors.is_empty ()
591 || parms_info->descriptors.length () <= i)
594 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i);
597 /* Fast equality function based on knowledge known in WPA. */
600 sem_function::equals_wpa (sem_item *item,
601 hash_map <symtab_node *, sem_item *> &ignored_nodes)
603 gcc_assert (item->type == FUNC);
605 m_compared_func = static_cast<sem_function *> (item);
607 if (arg_types.length () != m_compared_func->arg_types.length ())
608 return return_false_with_msg ("different number of arguments");
610 /* Compare special function DECL attributes. */
611 if (DECL_FUNCTION_PERSONALITY (decl)
612 != DECL_FUNCTION_PERSONALITY (item->decl))
613 return return_false_with_msg ("function personalities are different");
615 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
616 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item->decl))
617 return return_false_with_msg ("intrument function entry exit "
618 "attributes are different");
620 if (DECL_NO_LIMIT_STACK (decl) != DECL_NO_LIMIT_STACK (item->decl))
621 return return_false_with_msg ("no stack limit attributes are different");
623 if (DECL_CXX_CONSTRUCTOR_P (decl) != DECL_CXX_CONSTRUCTOR_P (item->decl))
624 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
626 if (DECL_CXX_DESTRUCTOR_P (decl) != DECL_CXX_DESTRUCTOR_P (item->decl))
627 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
629 /* TODO: pure/const flags mostly matters only for references, except for
630 the fact that codegen takes LOOPING flag as a hint that loops are
631 finite. We may arrange the code to always pick leader that has least
632 specified flags and then this can go into comparing symbol properties. */
633 if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
634 return return_false_with_msg ("decl_or_type flags are different");
636 /* Do not match polymorphic constructors of different types. They calls
637 type memory location for ipa-polymorphic-call and we do not want
638 it to get confused by wrong type. */
639 if (DECL_CXX_CONSTRUCTOR_P (decl)
640 && TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE)
642 if (TREE_CODE (TREE_TYPE (item->decl)) != METHOD_TYPE)
643 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
644 else if (!func_checker::compatible_polymorphic_types_p
645 (method_class_type (TREE_TYPE (decl)),
646 method_class_type (TREE_TYPE (item->decl)), false))
647 return return_false_with_msg ("ctor polymorphic type mismatch");
650 /* Checking function TARGET and OPTIMIZATION flags. */
651 cl_target_option *tar1 = target_opts_for_fn (decl);
652 cl_target_option *tar2 = target_opts_for_fn (item->decl);
654 if (tar1 != tar2 && !cl_target_option_eq (tar1, tar2))
656 if (dump_file && (dump_flags & TDF_DETAILS))
658 fprintf (dump_file, "target flags difference");
659 cl_target_option_print_diff (dump_file, 2, tar1, tar2);
662 return return_false_with_msg ("Target flags are different");
665 cl_optimization *opt1 = opts_for_fn (decl);
666 cl_optimization *opt2 = opts_for_fn (item->decl);
668 if (opt1 != opt2 && memcmp (opt1, opt2, sizeof(cl_optimization)))
670 if (dump_file && (dump_flags & TDF_DETAILS))
672 fprintf (dump_file, "optimization flags difference");
673 cl_optimization_print_diff (dump_file, 2, opt1, opt2);
676 return return_false_with_msg ("optimization flags are different");
679 /* Result type checking. */
680 if (!func_checker::compatible_types_p (result_type,
681 m_compared_func->result_type))
682 return return_false_with_msg ("result types are different");
684 /* Checking types of arguments. */
685 for (unsigned i = 0; i < arg_types.length (); i++)
687 /* This guard is here for function pointer with attributes (pr59927.c). */
688 if (!arg_types[i] || !m_compared_func->arg_types[i])
689 return return_false_with_msg ("NULL argument type");
691 /* We always need to match types so we are sure the callin conventions
693 if (!func_checker::compatible_types_p (arg_types[i],
694 m_compared_func->arg_types[i]))
695 return return_false_with_msg ("argument type is different");
697 /* On used arguments we need to do a bit more of work. */
698 if (!param_used_p (i))
700 if (POINTER_TYPE_P (arg_types[i])
701 && (TYPE_RESTRICT (arg_types[i])
702 != TYPE_RESTRICT (m_compared_func->arg_types[i])))
703 return return_false_with_msg ("argument restrict flag mismatch");
704 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
705 if (POINTER_TYPE_P (arg_types[i])
706 && TREE_CODE (arg_types[i])
707 != TREE_CODE (m_compared_func->arg_types[i])
708 && opt_for_fn (decl, flag_delete_null_pointer_checks))
709 return return_false_with_msg ("pointer wrt reference mismatch");
712 if (node->num_references () != item->node->num_references ())
713 return return_false_with_msg ("different number of references");
715 /* Checking function attributes.
716 This is quadratic in number of attributes */
717 if (comp_type_attributes (TREE_TYPE (decl),
718 TREE_TYPE (item->decl)) != 1)
719 return return_false_with_msg ("different type attributes");
720 if (!compare_attributes (DECL_ATTRIBUTES (decl),
721 DECL_ATTRIBUTES (item->decl)))
722 return return_false_with_msg ("different decl attributes");
724 /* The type of THIS pointer type memory location for
725 ipa-polymorphic-call-analysis. */
726 if (opt_for_fn (decl, flag_devirtualize)
727 && (TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE
728 || TREE_CODE (TREE_TYPE (item->decl)) == METHOD_TYPE)
730 && compare_polymorphic_p ())
732 if (TREE_CODE (TREE_TYPE (decl)) != TREE_CODE (TREE_TYPE (item->decl)))
733 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
734 if (!func_checker::compatible_polymorphic_types_p
735 (method_class_type (TREE_TYPE (decl)),
736 method_class_type (TREE_TYPE (item->decl)), false))
737 return return_false_with_msg ("THIS pointer ODR type mismatch");
740 ipa_ref *ref = NULL, *ref2 = NULL;
741 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
743 item->node->iterate_reference (i, ref2);
745 if (ref->use != ref2->use)
746 return return_false_with_msg ("reference use mismatch");
748 if (!compare_symbol_references (ignored_nodes, ref->referred,
750 ref->address_matters_p ()))
754 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
755 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
759 if (!compare_symbol_references (ignored_nodes, e1->callee,
762 if (!compare_edge_flags (e1, e2))
765 e1 = e1->next_callee;
766 e2 = e2->next_callee;
770 return return_false_with_msg ("different number of calls");
772 e1 = dyn_cast <cgraph_node *> (node)->indirect_calls;
773 e2 = dyn_cast <cgraph_node *> (item->node)->indirect_calls;
777 if (!compare_edge_flags (e1, e2))
780 e1 = e1->next_callee;
781 e2 = e2->next_callee;
785 return return_false_with_msg ("different number of indirect calls");
790 /* Update hash by address sensitive references. We iterate over all
791 sensitive references (address_matters_p) and we hash ultime alias
792 target of these nodes, which can improve a semantic item hash.
794 Also hash in referenced symbols properties. This can be done at any time
795 (as the properties should not change), but it is convenient to do it here
796 while we walk the references anyway. */
799 sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
800 sem_item *> &m_symtab_node_map)
803 inchash::hash hstate (hash);
805 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
807 hstate.add_int (ref->use);
808 hash_referenced_symbol_properties (ref->referred, hstate,
809 ref->use == IPA_REF_ADDR);
810 if (ref->address_matters_p () || !m_symtab_node_map.get (ref->referred))
811 hstate.add_int (ref->referred->ultimate_alias_target ()->order);
814 if (is_a <cgraph_node *> (node))
816 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
819 sem_item **result = m_symtab_node_map.get (e->callee);
820 hash_referenced_symbol_properties (e->callee, hstate, false);
822 hstate.add_int (e->callee->ultimate_alias_target ()->order);
826 hash = hstate.end ();
829 /* Update hash by computed local hash values taken from different
831 TODO: stronger SCC based hashing would be desirable here. */
834 sem_item::update_hash_by_local_refs (hash_map <symtab_node *,
835 sem_item *> &m_symtab_node_map)
838 inchash::hash state (hash);
840 for (unsigned j = 0; node->iterate_reference (j, ref); j++)
842 sem_item **result = m_symtab_node_map.get (ref->referring);
844 state.merge_hash ((*result)->hash);
849 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e;
852 sem_item **result = m_symtab_node_map.get (e->caller);
854 state.merge_hash ((*result)->hash);
858 global_hash = state.end ();
861 /* Returns true if the item equals to ITEM given as argument. */
864 sem_function::equals (sem_item *item,
865 hash_map <symtab_node *, sem_item *> &ignored_nodes)
867 gcc_assert (item->type == FUNC);
868 bool eq = equals_private (item, ignored_nodes);
870 if (m_checker != NULL)
876 if (dump_file && (dump_flags & TDF_DETAILS))
878 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
879 xstrdup_for_dump (node->name()),
880 xstrdup_for_dump (item->node->name ()),
883 xstrdup_for_dump (node->asm_name ()),
884 xstrdup_for_dump (item->node->asm_name ()),
885 eq ? "true" : "false");
890 /* Processes function equality comparison. */
893 sem_function::equals_private (sem_item *item,
894 hash_map <symtab_node *, sem_item *> &ignored_nodes)
896 if (item->type != FUNC)
899 basic_block bb1, bb2;
901 edge_iterator ei1, ei2;
905 m_compared_func = static_cast<sem_function *> (item);
907 gcc_assert (decl != item->decl);
909 if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
910 || edge_count != m_compared_func->edge_count
911 || cfg_checksum != m_compared_func->cfg_checksum)
912 return return_false ();
914 if (!equals_wpa (item, ignored_nodes))
917 m_checker = new func_checker (decl, m_compared_func->decl,
918 compare_polymorphic_p (),
921 &m_compared_func->refs_set);
922 for (arg1 = DECL_ARGUMENTS (decl),
923 arg2 = DECL_ARGUMENTS (m_compared_func->decl);
924 arg1; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2))
925 if (!m_checker->compare_decl (arg1, arg2))
926 return return_false ();
928 /* Fill-up label dictionary. */
929 for (unsigned i = 0; i < bb_sorted.length (); ++i)
931 m_checker->parse_labels (bb_sorted[i]);
932 m_checker->parse_labels (m_compared_func->bb_sorted[i]);
935 /* Checking all basic blocks. */
936 for (unsigned i = 0; i < bb_sorted.length (); ++i)
937 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
938 return return_false();
940 dump_message ("All BBs are equal\n");
942 auto_vec <int> bb_dict;
944 /* Basic block edges check. */
945 for (unsigned i = 0; i < bb_sorted.length (); ++i)
947 bb1 = bb_sorted[i]->bb;
948 bb2 = m_compared_func->bb_sorted[i]->bb;
950 ei2 = ei_start (bb2->preds);
952 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
956 if (e1->flags != e2->flags)
957 return return_false_with_msg ("flags comparison returns false");
959 if (!bb_dict_test (&bb_dict, e1->src->index, e2->src->index))
960 return return_false_with_msg ("edge comparison returns false");
962 if (!bb_dict_test (&bb_dict, e1->dest->index, e2->dest->index))
963 return return_false_with_msg ("BB comparison returns false");
965 if (!m_checker->compare_edge (e1, e2))
966 return return_false_with_msg ("edge comparison returns false");
972 /* Basic block PHI nodes comparison. */
973 for (unsigned i = 0; i < bb_sorted.length (); i++)
974 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
975 return return_false_with_msg ("PHI node comparison returns false");
980 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
981 Helper for call_for_symbol_thunks_and_aliases. */
984 set_local (cgraph_node *node, void *data)
986 node->local.local = data != NULL;
990 /* TREE_ADDRESSABLE of NODE to true.
991 Helper for call_for_symbol_thunks_and_aliases. */
994 set_addressable (varpool_node *node, void *)
996 TREE_ADDRESSABLE (node->decl) = 1;
1000 /* Clear DECL_RTL of NODE.
1001 Helper for call_for_symbol_thunks_and_aliases. */
1004 clear_decl_rtl (symtab_node *node, void *)
1006 SET_DECL_RTL (node->decl, NULL);
1010 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1011 possible. Return number of redirections made. */
1014 redirect_all_callers (cgraph_node *n, cgraph_node *to)
1016 int nredirected = 0;
1018 cgraph_edge *e = n->callers;
1022 /* Redirecting thunks to interposable symbols or symbols in other sections
1023 may not be supported by target output code. Play safe for now and
1024 punt on redirection. */
1025 if (!e->caller->thunk.thunk_p)
1027 struct cgraph_edge *nexte = e->next_caller;
1028 e->redirect_callee (to);
1035 for (unsigned i = 0; n->iterate_direct_aliases (i, ref);)
1037 bool removed = false;
1038 cgraph_node *n_alias = dyn_cast <cgraph_node *> (ref->referring);
1040 if ((DECL_COMDAT_GROUP (n->decl)
1041 && (DECL_COMDAT_GROUP (n->decl)
1042 == DECL_COMDAT_GROUP (n_alias->decl)))
1043 || (n_alias->get_availability () > AVAIL_INTERPOSABLE
1044 && n->get_availability () > AVAIL_INTERPOSABLE))
1046 nredirected += redirect_all_callers (n_alias, to);
1047 if (n_alias->can_remove_if_no_direct_calls_p ()
1048 && !n_alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1050 && !n_alias->has_aliases_p ())
1059 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1063 sem_function::merge (sem_item *alias_item)
1065 gcc_assert (alias_item->type == FUNC);
1067 sem_function *alias_func = static_cast<sem_function *> (alias_item);
1069 cgraph_node *original = get_node ();
1070 cgraph_node *local_original = NULL;
1071 cgraph_node *alias = alias_func->get_node ();
1073 bool create_wrapper = false;
1074 bool create_alias = false;
1075 bool redirect_callers = false;
1076 bool remove = false;
1078 bool original_discardable = false;
1079 bool original_discarded = false;
1081 bool original_address_matters = original->address_matters_p ();
1082 bool alias_address_matters = alias->address_matters_p ();
1084 if (DECL_EXTERNAL (alias->decl))
1087 fprintf (dump_file, "Not unifying; alias is external.\n\n");
1091 if (DECL_NO_INLINE_WARNING_P (original->decl)
1092 != DECL_NO_INLINE_WARNING_P (alias->decl))
1097 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1101 /* Do not attempt to mix functions from different user sections;
1102 we do not know what user intends with those. */
1103 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
1104 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
1105 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
1110 "original and alias are in different sections.\n\n");
1114 /* See if original is in a section that can be discarded if the main
1115 symbol is not used. */
1117 if (original->can_be_discarded_p ())
1118 original_discardable = true;
1119 /* Also consider case where we have resolution info and we know that
1120 original's definition is not going to be used. In this case we can not
1121 create alias to original. */
1122 if (node->resolution != LDPR_UNKNOWN
1123 && !decl_binds_to_current_def_p (node->decl))
1124 original_discardable = original_discarded = true;
1126 /* Creating a symtab alias is the optimal way to merge.
1127 It however can not be used in the following cases:
1129 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1130 2) if ORIGINAL is in a section that may be discarded by linker or if
1131 it is an external functions where we can not create an alias
1132 (ORIGINAL_DISCARDABLE)
1133 3) if target do not support symbol aliases.
1134 4) original and alias lie in different comdat groups.
1136 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1137 and/or redirect all callers from ALIAS to ORIGINAL. */
1138 if ((original_address_matters && alias_address_matters)
1139 || (original_discardable
1140 && (!DECL_COMDAT_GROUP (alias->decl)
1141 || (DECL_COMDAT_GROUP (alias->decl)
1142 != DECL_COMDAT_GROUP (original->decl))))
1143 || original_discarded
1144 || !sem_item::target_supports_symbol_aliases_p ()
1145 || DECL_COMDAT_GROUP (alias->decl) != DECL_COMDAT_GROUP (original->decl))
1147 /* First see if we can produce wrapper. */
1149 /* Symbol properties that matter for references must be preserved.
1150 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1151 with proper properties. */
1152 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1153 alias->address_taken))
1157 "Wrapper cannot be created because referenced symbol "
1158 "properties mismatch\n");
1160 /* Do not turn function in one comdat group into wrapper to another
1161 comdat group. Other compiler producing the body of the
1162 another comdat group may make opossite decision and with unfortunate
1163 linker choices this may close a loop. */
1164 else if (DECL_COMDAT_GROUP (original->decl)
1165 && DECL_COMDAT_GROUP (alias->decl)
1166 && (DECL_COMDAT_GROUP (alias->decl)
1167 != DECL_COMDAT_GROUP (original->decl)))
1171 "Wrapper cannot be created because of COMDAT\n");
1173 else if (DECL_STATIC_CHAIN (alias->decl))
1177 "Can not create wrapper of nested functions.\n");
1179 /* TODO: We can also deal with variadic functions never calling
1181 else if (stdarg_p (TREE_TYPE (alias->decl)))
1185 "can not create wrapper of stdarg function.\n");
1187 else if (inline_summaries
1188 && inline_summaries->get (alias)->self_size <= 2)
1191 fprintf (dump_file, "Wrapper creation is not "
1192 "profitable (function is too small).\n");
1194 /* If user paid attention to mark function noinline, assume it is
1195 somewhat special and do not try to turn it into a wrapper that can
1196 not be undone by inliner. */
1197 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
1200 fprintf (dump_file, "Wrappers are not created for noinline.\n");
1203 create_wrapper = true;
1205 /* We can redirect local calls in the case both alias and orignal
1206 are not interposable. */
1208 = alias->get_availability () > AVAIL_INTERPOSABLE
1209 && original->get_availability () > AVAIL_INTERPOSABLE
1210 && !alias->instrumented_version;
1211 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1212 with proper properties. */
1213 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1214 alias->address_taken))
1215 redirect_callers = false;
1217 if (!redirect_callers && !create_wrapper)
1220 fprintf (dump_file, "Not unifying; can not redirect callers nor "
1221 "produce wrapper\n\n");
1225 /* Work out the symbol the wrapper should call.
1226 If ORIGINAL is interposable, we need to call a local alias.
1227 Also produce local alias (if possible) as an optimization.
1229 Local aliases can not be created inside comdat groups because that
1230 prevents inlining. */
1231 if (!original_discardable && !original->get_comdat_group ())
1234 = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
1236 && original->get_availability () > AVAIL_INTERPOSABLE)
1237 local_original = original;
1239 /* If we can not use local alias, fallback to the original
1241 else if (original->get_availability () > AVAIL_INTERPOSABLE)
1242 local_original = original;
1244 /* If original is COMDAT local, we can not really redirect calls outside
1245 of its comdat group to it. */
1246 if (original->comdat_local_p ())
1247 redirect_callers = false;
1248 if (!local_original)
1251 fprintf (dump_file, "Not unifying; "
1252 "can not produce local alias.\n\n");
1256 if (!redirect_callers && !create_wrapper)
1259 fprintf (dump_file, "Not unifying; "
1260 "can not redirect callers nor produce a wrapper\n\n");
1264 && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1266 && !alias->can_remove_if_no_direct_calls_p ())
1269 fprintf (dump_file, "Not unifying; can not make wrapper and "
1270 "function has other uses than direct calls\n\n");
1275 create_alias = true;
1277 if (redirect_callers)
1279 int nredirected = redirect_all_callers (alias, local_original);
1283 alias->icf_merged = true;
1284 local_original->icf_merged = true;
1286 if (dump_file && nredirected)
1287 fprintf (dump_file, "%i local calls have been "
1288 "redirected.\n", nredirected);
1291 /* If all callers was redirected, do not produce wrapper. */
1292 if (alias->can_remove_if_no_direct_calls_p ()
1293 && !alias->has_aliases_p ())
1295 create_wrapper = false;
1298 gcc_assert (!create_alias);
1300 else if (create_alias)
1302 alias->icf_merged = true;
1304 /* Remove the function's body. */
1305 ipa_merge_profiles (original, alias);
1306 alias->release_body (true);
1308 /* Notice global symbol possibly produced RTL. */
1309 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
1312 /* Create the alias. */
1313 cgraph_node::create_alias (alias_func->decl, decl);
1314 alias->resolve_alias (original);
1316 original->call_for_symbol_thunks_and_aliases
1317 (set_local, (void *)(size_t) original->local_p (), true);
1320 fprintf (dump_file, "Unified; Function alias has been created.\n\n");
1324 gcc_assert (!create_alias);
1325 alias->icf_merged = true;
1326 local_original->icf_merged = true;
1328 ipa_merge_profiles (local_original, alias, true);
1329 alias->create_wrapper (local_original);
1332 fprintf (dump_file, "Unified; Wrapper has been created.\n\n");
1335 /* It's possible that redirection can hit thunks that block
1336 redirection opportunities. */
1337 gcc_assert (alias->icf_merged || remove || redirect_callers);
1338 original->icf_merged = true;
1340 /* Inform the inliner about cross-module merging. */
1341 if ((original->lto_file_data || alias->lto_file_data)
1342 && original->lto_file_data != alias->lto_file_data)
1343 local_original->merged = original->merged = true;
1347 ipa_merge_profiles (original, alias);
1348 alias->release_body ();
1350 alias->body_removed = true;
1351 alias->icf_merged = true;
1353 fprintf (dump_file, "Unified; Function body was removed.\n");
1359 /* Semantic item initialization function. */
1362 sem_function::init (void)
1365 get_node ()->get_untransformed_body ();
1367 tree fndecl = node->decl;
1368 function *func = DECL_STRUCT_FUNCTION (fndecl);
1371 gcc_assert (SSANAMES (func));
1373 ssa_names_size = SSANAMES (func)->length ();
1377 region_tree = func->eh->region_tree;
1379 /* iterating all function arguments. */
1380 arg_count = count_formal_params (fndecl);
1382 edge_count = n_edges_for_fn (func);
1383 cfg_checksum = coverage_compute_cfg_checksum (func);
1385 inchash::hash hstate;
1388 FOR_EACH_BB_FN (bb, func)
1390 unsigned nondbg_stmt_count = 0;
1393 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
1395 cfg_checksum = iterative_hash_host_wide_int (e->flags,
1398 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1401 gimple stmt = gsi_stmt (gsi);
1403 if (gimple_code (stmt) != GIMPLE_DEBUG
1404 && gimple_code (stmt) != GIMPLE_PREDICT)
1406 hash_stmt (stmt, hstate);
1407 nondbg_stmt_count++;
1411 gcode_hash = hstate.end ();
1412 bb_sizes.safe_push (nondbg_stmt_count);
1414 /* Inserting basic block to hash table. */
1415 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
1416 EDGE_COUNT (bb->preds)
1417 + EDGE_COUNT (bb->succs));
1419 bb_sorted.safe_push (semantic_bb);
1425 /* Accumulate to HSTATE a hash of expression EXP.
1426 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1427 and DECL equality classes. */
1430 sem_item::add_expr (const_tree exp, inchash::hash &hstate)
1432 if (exp == NULL_TREE)
1434 hstate.merge_hash (0);
1438 /* Handled component can be matched in a cureful way proving equivalence
1439 even if they syntactically differ. Just skip them. */
1441 while (handled_component_p (exp))
1442 exp = TREE_OPERAND (exp, 0);
1444 enum tree_code code = TREE_CODE (exp);
1445 hstate.add_int (code);
1449 /* Use inchash::add_expr for everything that is LTO stable. */
1457 inchash::add_expr (exp, hstate);
1461 unsigned HOST_WIDE_INT idx;
1464 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1466 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp), idx, value)
1468 add_expr (value, hstate);
1473 add_expr (get_base_address (TREE_OPERAND (exp, 0)), hstate);
1479 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1482 case POINTER_PLUS_EXPR:
1485 add_expr (TREE_OPERAND (exp, 0), hstate);
1486 add_expr (TREE_OPERAND (exp, 1), hstate);
1490 inchash::hash one, two;
1491 add_expr (TREE_OPERAND (exp, 0), one);
1492 add_expr (TREE_OPERAND (exp, 1), two);
1493 hstate.add_commutative (one, two);
1497 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1498 return add_expr (TREE_OPERAND (exp, 0), hstate);
1504 /* Accumulate to HSTATE a hash of type t.
1505 TYpes that may end up being compatible after LTO type merging needs to have
1509 sem_item::add_type (const_tree type, inchash::hash &hstate)
1511 if (type == NULL_TREE)
1513 hstate.merge_hash (0);
1517 type = TYPE_MAIN_VARIANT (type);
1518 if (TYPE_CANONICAL (type))
1519 type = TYPE_CANONICAL (type);
1521 if (!AGGREGATE_TYPE_P (type))
1522 hstate.add_int (TYPE_MODE (type));
1524 if (TREE_CODE (type) == COMPLEX_TYPE)
1526 hstate.add_int (COMPLEX_TYPE);
1527 sem_item::add_type (TREE_TYPE (type), hstate);
1529 else if (INTEGRAL_TYPE_P (type))
1531 hstate.add_int (INTEGER_TYPE);
1532 hstate.add_flag (TYPE_UNSIGNED (type));
1533 hstate.add_int (TYPE_PRECISION (type));
1535 else if (VECTOR_TYPE_P (type))
1537 hstate.add_int (VECTOR_TYPE);
1538 hstate.add_int (TYPE_PRECISION (type));
1539 sem_item::add_type (TREE_TYPE (type), hstate);
1541 else if (TREE_CODE (type) == ARRAY_TYPE)
1543 hstate.add_int (ARRAY_TYPE);
1544 /* Do not hash size, so complete and incomplete types can match. */
1545 sem_item::add_type (TREE_TYPE (type), hstate);
1547 else if (RECORD_OR_UNION_TYPE_P (type))
1549 hashval_t *val = optimizer->m_type_hash_cache.get (type);
1553 inchash::hash hstate2;
1558 hstate2.add_int (RECORD_TYPE);
1559 gcc_assert (COMPLETE_TYPE_P (type));
1561 for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
1562 if (TREE_CODE (f) == FIELD_DECL)
1564 add_type (TREE_TYPE (f), hstate2);
1568 hstate2.add_int (nf);
1569 hash = hstate2.end ();
1570 hstate.add_wide_int (hash);
1571 optimizer->m_type_hash_cache.put (type, hash);
1574 hstate.add_wide_int (*val);
1578 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1581 sem_function::hash_stmt (gimple stmt, inchash::hash &hstate)
1583 enum gimple_code code = gimple_code (stmt);
1585 hstate.add_int (code);
1590 add_expr (gimple_switch_index (as_a <gswitch *> (stmt)), hstate);
1593 hstate.add_int (gimple_assign_rhs_code (stmt));
1594 if (commutative_tree_code (gimple_assign_rhs_code (stmt))
1595 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1597 inchash::hash one, two;
1599 add_expr (gimple_assign_rhs1 (stmt), one);
1600 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt)), one);
1601 add_expr (gimple_assign_rhs2 (stmt), two);
1602 hstate.add_commutative (one, two);
1603 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1605 add_expr (gimple_assign_rhs3 (stmt), hstate);
1606 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt)), hstate);
1608 add_expr (gimple_assign_lhs (stmt), hstate);
1609 add_type (TREE_TYPE (gimple_assign_lhs (stmt)), two);
1612 /* ... fall through ... */
1618 /* All these statements are equivalent if their operands are. */
1619 for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1621 add_expr (gimple_op (stmt, i), hstate);
1622 if (gimple_op (stmt, i))
1623 add_type (TREE_TYPE (gimple_op (stmt, i)), hstate);
1631 /* Return true if polymorphic comparison must be processed. */
1634 sem_function::compare_polymorphic_p (void)
1636 struct cgraph_edge *e;
1638 if (!opt_for_fn (get_node ()->decl, flag_devirtualize))
1640 if (get_node ()->indirect_calls != NULL)
1642 /* TODO: We can do simple propagation determining what calls may lead to
1643 a polymorphic call. */
1644 for (e = get_node ()->callees; e; e = e->next_callee)
1645 if (e->callee->definition
1646 && opt_for_fn (e->callee->decl, flag_devirtualize))
1651 /* For a given call graph NODE, the function constructs new
1652 semantic function item. */
1655 sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
1657 tree fndecl = node->decl;
1658 function *func = DECL_STRUCT_FUNCTION (fndecl);
1660 /* TODO: add support for thunks. */
1662 if (!func || !node->has_gimple_body_p ())
1665 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
1668 sem_function *f = new sem_function (node, 0, stack);
1675 /* Parses function arguments and result type. */
1678 sem_function::parse_tree_args (void)
1682 if (arg_types.exists ())
1683 arg_types.release ();
1685 arg_types.create (4);
1686 tree fnargs = DECL_ARGUMENTS (decl);
1688 for (tree parm = fnargs; parm; parm = DECL_CHAIN (parm))
1689 arg_types.safe_push (DECL_ARG_TYPE (parm));
1691 /* Function result type. */
1692 result = DECL_RESULT (decl);
1693 result_type = result ? TREE_TYPE (result) : NULL;
1695 /* During WPA, we can get arguments by following method. */
1698 tree type = TYPE_ARG_TYPES (TREE_TYPE (decl));
1699 for (tree parm = type; parm; parm = TREE_CHAIN (parm))
1700 arg_types.safe_push (TYPE_CANONICAL (TREE_VALUE (parm)));
1702 result_type = TREE_TYPE (TREE_TYPE (decl));
1706 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1707 return true if phi nodes are semantically equivalent in these blocks . */
1710 sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
1712 gphi_iterator si1, si2;
1714 unsigned size1, size2, i;
1718 gcc_assert (bb1 != NULL);
1719 gcc_assert (bb2 != NULL);
1721 si2 = gsi_start_phis (bb2);
1722 for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
1725 gsi_next_nonvirtual_phi (&si1);
1726 gsi_next_nonvirtual_phi (&si2);
1728 if (gsi_end_p (si1) && gsi_end_p (si2))
1731 if (gsi_end_p (si1) || gsi_end_p (si2))
1732 return return_false();
1737 tree phi_result1 = gimple_phi_result (phi1);
1738 tree phi_result2 = gimple_phi_result (phi2);
1740 if (!m_checker->compare_operand (phi_result1, phi_result2))
1741 return return_false_with_msg ("PHI results are different");
1743 size1 = gimple_phi_num_args (phi1);
1744 size2 = gimple_phi_num_args (phi2);
1747 return return_false ();
1749 for (i = 0; i < size1; ++i)
1751 t1 = gimple_phi_arg (phi1, i)->def;
1752 t2 = gimple_phi_arg (phi2, i)->def;
1754 if (!m_checker->compare_operand (t1, t2))
1755 return return_false ();
1757 e1 = gimple_phi_arg_edge (phi1, i);
1758 e2 = gimple_phi_arg_edge (phi2, i);
1760 if (!m_checker->compare_edge (e1, e2))
1761 return return_false ();
1770 /* Returns true if tree T can be compared as a handled component. */
1773 sem_function::icf_handled_component_p (tree t)
1775 tree_code tc = TREE_CODE (t);
1777 return ((handled_component_p (t))
1778 || tc == ADDR_EXPR || tc == MEM_REF || tc == REALPART_EXPR
1779 || tc == IMAGPART_EXPR || tc == OBJ_TYPE_REF);
1782 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1783 corresponds to TARGET. */
1786 sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
1791 if (bb_dict->length () <= (unsigned)source)
1792 bb_dict->safe_grow_cleared (source + 1);
1794 if ((*bb_dict)[source] == 0)
1796 (*bb_dict)[source] = target;
1800 return (*bb_dict)[source] == target;
1804 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1806 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
1810 /* Constructor based on varpool node _NODE with computed hash _HASH.
1811 Bitmap STACK is used for memory allocation. */
1813 sem_variable::sem_variable (varpool_node *node, hashval_t _hash,
1814 bitmap_obstack *stack): sem_item(VAR,
1817 gcc_checking_assert (node);
1818 gcc_checking_assert (get_node ());
1821 /* Fast equality function based on knowledge known in WPA. */
1824 sem_variable::equals_wpa (sem_item *item,
1825 hash_map <symtab_node *, sem_item *> &ignored_nodes)
1827 gcc_assert (item->type == VAR);
1829 if (node->num_references () != item->node->num_references ())
1830 return return_false_with_msg ("different number of references");
1832 if (DECL_TLS_MODEL (decl) || DECL_TLS_MODEL (item->decl))
1833 return return_false_with_msg ("TLS model");
1835 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1836 alignment out of all aliases. */
1838 if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
1839 return return_false_with_msg ("Virtual flag mismatch");
1841 if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
1842 && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
1843 || !operand_equal_p (DECL_SIZE (decl),
1844 DECL_SIZE (item->decl), OEP_ONLY_CONST)))
1845 return return_false_with_msg ("size mismatch");
1847 /* Do not attempt to mix data from different user sections;
1848 we do not know what user intends with those. */
1849 if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
1850 || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
1851 && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
1852 return return_false_with_msg ("user section mismatch");
1854 if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
1855 return return_false_with_msg ("text section");
1857 ipa_ref *ref = NULL, *ref2 = NULL;
1858 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
1860 item->node->iterate_reference (i, ref2);
1862 if (ref->use != ref2->use)
1863 return return_false_with_msg ("reference use mismatch");
1865 if (!compare_symbol_references (ignored_nodes,
1866 ref->referred, ref2->referred,
1867 ref->address_matters_p ()))
1874 /* Returns true if the item equals to ITEM given as argument. */
1877 sem_variable::equals (sem_item *item,
1878 hash_map <symtab_node *, sem_item *> &)
1880 gcc_assert (item->type == VAR);
1883 if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
1884 dyn_cast <varpool_node *>(node)->get_constructor ();
1885 if (DECL_INITIAL (item->decl) == error_mark_node && in_lto_p)
1886 dyn_cast <varpool_node *>(item->node)->get_constructor ();
1888 /* As seen in PR ipa/65303 we have to compare variables types. */
1889 if (!func_checker::compatible_types_p (TREE_TYPE (decl),
1890 TREE_TYPE (item->decl)))
1891 return return_false_with_msg ("variables types are different");
1893 ret = sem_variable::equals (DECL_INITIAL (decl),
1894 DECL_INITIAL (item->node->decl));
1895 if (dump_file && (dump_flags & TDF_DETAILS))
1897 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1898 xstrdup_for_dump (node->name()),
1899 xstrdup_for_dump (item->node->name ()),
1900 node->order, item->node->order,
1901 xstrdup_for_dump (node->asm_name ()),
1902 xstrdup_for_dump (item->node->asm_name ()), ret ? "true" : "false");
1907 /* Compares trees T1 and T2 for semantic equality. */
1910 sem_variable::equals (tree t1, tree t2)
1913 return return_with_debug (t1 == t2);
1916 tree_code tc1 = TREE_CODE (t1);
1917 tree_code tc2 = TREE_CODE (t2);
1920 return return_false_with_msg ("TREE_CODE mismatch");
1926 vec<constructor_elt, va_gc> *v1, *v2;
1927 unsigned HOST_WIDE_INT idx;
1929 enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
1930 if (typecode != TREE_CODE (TREE_TYPE (t2)))
1931 return return_false_with_msg ("constructor type mismatch");
1933 if (typecode == ARRAY_TYPE)
1935 HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
1936 /* For arrays, check that the sizes all match. */
1937 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
1939 || size_1 != int_size_in_bytes (TREE_TYPE (t2)))
1940 return return_false_with_msg ("constructor array size mismatch");
1942 else if (!func_checker::compatible_types_p (TREE_TYPE (t1),
1944 return return_false_with_msg ("constructor type incompatible");
1946 v1 = CONSTRUCTOR_ELTS (t1);
1947 v2 = CONSTRUCTOR_ELTS (t2);
1948 if (vec_safe_length (v1) != vec_safe_length (v2))
1949 return return_false_with_msg ("constructor number of elts mismatch");
1951 for (idx = 0; idx < vec_safe_length (v1); ++idx)
1953 constructor_elt *c1 = &(*v1)[idx];
1954 constructor_elt *c2 = &(*v2)[idx];
1956 /* Check that each value is the same... */
1957 if (!sem_variable::equals (c1->value, c2->value))
1959 /* ... and that they apply to the same fields! */
1960 if (!sem_variable::equals (c1->index, c2->index))
1967 tree x1 = TREE_OPERAND (t1, 0);
1968 tree x2 = TREE_OPERAND (t2, 0);
1969 tree y1 = TREE_OPERAND (t1, 1);
1970 tree y2 = TREE_OPERAND (t2, 1);
1972 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
1973 return return_false ();
1975 /* Type of the offset on MEM_REF does not matter. */
1976 return return_with_debug (sem_variable::equals (x1, x2)
1977 && wi::to_offset (y1)
1978 == wi::to_offset (y2));
1983 tree op1 = TREE_OPERAND (t1, 0);
1984 tree op2 = TREE_OPERAND (t2, 0);
1985 return sem_variable::equals (op1, op2);
1987 /* References to other vars/decls are compared using ipa-ref. */
1990 if (decl_in_symtab_p (t1) && decl_in_symtab_p (t2))
1992 return return_false_with_msg ("Declaration mismatch");
1994 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1995 need to process its VAR/FUNCTION references without relying on ipa-ref
1999 return return_false_with_msg ("Declaration mismatch");
2001 /* Integer constants are the same only if the same width of type. */
2002 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2003 return return_false_with_msg ("INTEGER_CST precision mismatch");
2004 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
2005 return return_false_with_msg ("INTEGER_CST mode mismatch");
2006 return return_with_debug (tree_int_cst_equal (t1, t2));
2008 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
2009 return return_false_with_msg ("STRING_CST mode mismatch");
2010 if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
2011 return return_false_with_msg ("STRING_CST length mismatch");
2012 if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
2013 TREE_STRING_LENGTH (t1)))
2014 return return_false_with_msg ("STRING_CST mismatch");
2017 /* Fixed constants are the same only if the same width of type. */
2018 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2019 return return_false_with_msg ("FIXED_CST precision mismatch");
2021 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
2022 TREE_FIXED_CST (t2)));
2024 return (sem_variable::equals (TREE_REALPART (t1), TREE_REALPART (t2))
2025 && sem_variable::equals (TREE_IMAGPART (t1), TREE_IMAGPART (t2)));
2027 /* Real constants are the same only if the same width of type. */
2028 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2029 return return_false_with_msg ("REAL_CST precision mismatch");
2030 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1),
2031 TREE_REAL_CST (t2)));
2036 if (VECTOR_CST_NELTS (t1) != VECTOR_CST_NELTS (t2))
2037 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2039 for (i = 0; i < VECTOR_CST_NELTS (t1); ++i)
2040 if (!sem_variable::equals (VECTOR_CST_ELT (t1, i),
2041 VECTOR_CST_ELT (t2, i)))
2047 case ARRAY_RANGE_REF:
2049 tree x1 = TREE_OPERAND (t1, 0);
2050 tree x2 = TREE_OPERAND (t2, 0);
2051 tree y1 = TREE_OPERAND (t1, 1);
2052 tree y2 = TREE_OPERAND (t2, 1);
2054 if (!sem_variable::equals (x1, x2) || !sem_variable::equals (y1, y2))
2056 if (!sem_variable::equals (array_ref_low_bound (t1),
2057 array_ref_low_bound (t2)))
2059 if (!sem_variable::equals (array_ref_element_size (t1),
2060 array_ref_element_size (t2)))
2066 case POINTER_PLUS_EXPR:
2071 tree x1 = TREE_OPERAND (t1, 0);
2072 tree x2 = TREE_OPERAND (t2, 0);
2073 tree y1 = TREE_OPERAND (t1, 1);
2074 tree y2 = TREE_OPERAND (t2, 1);
2076 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
2080 case VIEW_CONVERT_EXPR:
2081 if (!func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
2082 return return_false ();
2083 return sem_variable::equals (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
2085 return return_false_with_msg ("ERROR_MARK");
2087 return return_false_with_msg ("Unknown TREE code reached");
2091 /* Parser function that visits a varpool NODE. */
2094 sem_variable::parse (varpool_node *node, bitmap_obstack *stack)
2096 if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl)
2100 sem_variable *v = new sem_variable (node, 0, stack);
2107 /* References independent hash function. */
2110 sem_variable::get_hash (void)
2115 /* All WPA streamed in symbols should have their hashes computed at compile
2116 time. At this point, the constructor may not be in memory at all.
2117 DECL_INITIAL (decl) would be error_mark_node in that case. */
2118 gcc_assert (!node->lto_file_data);
2119 tree ctor = DECL_INITIAL (decl);
2120 inchash::hash hstate;
2122 hstate.add_int (456346417);
2123 if (DECL_SIZE (decl) && tree_fits_shwi_p (DECL_SIZE (decl)))
2124 hstate.add_wide_int (tree_to_shwi (DECL_SIZE (decl)));
2125 add_expr (ctor, hstate);
2126 hash = hstate.end ();
2131 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2135 sem_variable::merge (sem_item *alias_item)
2137 gcc_assert (alias_item->type == VAR);
2139 if (!sem_item::target_supports_symbol_aliases_p ())
2142 fprintf (dump_file, "Not unifying; "
2143 "Symbol aliases are not supported by target\n\n");
2147 if (DECL_EXTERNAL (alias_item->decl))
2150 fprintf (dump_file, "Not unifying; alias is external.\n\n");
2154 sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
2156 varpool_node *original = get_node ();
2157 varpool_node *alias = alias_var->get_node ();
2158 bool original_discardable = false;
2160 bool original_address_matters = original->address_matters_p ();
2161 bool alias_address_matters = alias->address_matters_p ();
2163 /* See if original is in a section that can be discarded if the main
2165 Also consider case where we have resolution info and we know that
2166 original's definition is not going to be used. In this case we can not
2167 create alias to original. */
2168 if (original->can_be_discarded_p ()
2169 || (node->resolution != LDPR_UNKNOWN
2170 && !decl_binds_to_current_def_p (node->decl)))
2171 original_discardable = true;
2173 gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
2175 /* Constant pool machinery is not quite ready for aliases.
2176 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2177 For LTO merging does not happen that is an important missing feature.
2178 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2179 flag is dropped and non-local symbol name is assigned. */
2180 if (DECL_IN_CONSTANT_POOL (alias->decl)
2181 || DECL_IN_CONSTANT_POOL (original->decl))
2185 "Not unifying; constant pool variables.\n\n");
2189 /* Do not attempt to mix functions from different user sections;
2190 we do not know what user intends with those. */
2191 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
2192 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
2193 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
2198 "original and alias are in different sections.\n\n");
2202 /* We can not merge if address comparsion metters. */
2203 if (original_address_matters && alias_address_matters
2204 && flag_merge_constants < 2)
2209 "adress of original and alias may be compared.\n\n");
2212 if (DECL_COMDAT_GROUP (original->decl) != DECL_COMDAT_GROUP (alias->decl))
2215 fprintf (dump_file, "Not unifying; alias cannot be created; "
2216 "across comdat group boundary\n\n");
2221 if (original_discardable)
2224 fprintf (dump_file, "Not unifying; alias cannot be created; "
2225 "target is discardable\n\n");
2231 gcc_assert (!original->alias);
2232 gcc_assert (!alias->alias);
2234 alias->analyzed = false;
2236 DECL_INITIAL (alias->decl) = NULL;
2237 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
2239 alias->need_bounds_init = false;
2240 alias->remove_all_references ();
2241 if (TREE_ADDRESSABLE (alias->decl))
2242 original->call_for_symbol_and_aliases (set_addressable, NULL, true);
2244 varpool_node::create_alias (alias_var->decl, decl);
2245 alias->resolve_alias (original);
2248 fprintf (dump_file, "Unified; Variable alias has been created.\n\n");
2254 /* Dump symbol to FILE. */
2257 sem_variable::dump_to_file (FILE *file)
2261 print_node (file, "", decl, 0);
2262 fprintf (file, "\n\n");
2265 unsigned int sem_item_optimizer::class_id = 0;
2267 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2268 m_classes_count (0), m_cgraph_node_hooks (NULL), m_varpool_node_hooks (NULL)
2271 bitmap_obstack_initialize (&m_bmstack);
2274 sem_item_optimizer::~sem_item_optimizer ()
2276 for (unsigned int i = 0; i < m_items.length (); i++)
2279 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2280 it != m_classes.end (); ++it)
2282 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2283 delete (*it)->classes[i];
2285 (*it)->classes.release ();
2291 bitmap_obstack_release (&m_bmstack);
2294 /* Write IPA ICF summary for symbols. */
2297 sem_item_optimizer::write_summary (void)
2299 unsigned int count = 0;
2301 output_block *ob = create_output_block (LTO_section_ipa_icf);
2302 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
2305 /* Calculate number of symbols to be serialized. */
2306 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2308 lsei_next_in_partition (&lsei))
2310 symtab_node *node = lsei_node (lsei);
2312 if (m_symtab_node_map.get (node))
2316 streamer_write_uhwi (ob, count);
2318 /* Process all of the symbols. */
2319 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2321 lsei_next_in_partition (&lsei))
2323 symtab_node *node = lsei_node (lsei);
2325 sem_item **item = m_symtab_node_map.get (node);
2329 int node_ref = lto_symtab_encoder_encode (encoder, node);
2330 streamer_write_uhwi_stream (ob->main_stream, node_ref);
2332 streamer_write_uhwi (ob, (*item)->get_hash ());
2336 streamer_write_char_stream (ob->main_stream, 0);
2337 produce_asm (ob, NULL);
2338 destroy_output_block (ob);
2341 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2342 contains LEN bytes. */
2345 sem_item_optimizer::read_section (lto_file_decl_data *file_data,
2346 const char *data, size_t len)
2348 const lto_function_header *header =
2349 (const lto_function_header *) data;
2350 const int cfg_offset = sizeof (lto_function_header);
2351 const int main_offset = cfg_offset + header->cfg_size;
2352 const int string_offset = main_offset + header->main_size;
2357 lto_input_block ib_main ((const char *) data + main_offset, 0,
2358 header->main_size, file_data->mode_table);
2361 lto_data_in_create (file_data, (const char *) data + string_offset,
2362 header->string_size, vNULL);
2364 count = streamer_read_uhwi (&ib_main);
2366 for (i = 0; i < count; i++)
2370 lto_symtab_encoder_t encoder;
2372 index = streamer_read_uhwi (&ib_main);
2373 encoder = file_data->symtab_node_encoder;
2374 node = lto_symtab_encoder_deref (encoder, index);
2376 hashval_t hash = streamer_read_uhwi (&ib_main);
2378 gcc_assert (node->definition);
2381 fprintf (dump_file, "Symbol added:%s (tree: %p, uid:%u)\n",
2382 node->asm_name (), (void *) node->decl, node->order);
2384 if (is_a<cgraph_node *> (node))
2386 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
2388 m_items.safe_push (new sem_function (cnode, hash, &m_bmstack));
2392 varpool_node *vnode = dyn_cast <varpool_node *> (node);
2394 m_items.safe_push (new sem_variable (vnode, hash, &m_bmstack));
2398 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
2400 lto_data_in_delete (data_in);
2403 /* Read IPA IPA ICF summary for symbols. */
2406 sem_item_optimizer::read_summary (void)
2408 lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2409 lto_file_decl_data *file_data;
2412 while ((file_data = file_data_vec[j++]))
2415 const char *data = lto_get_section_data (file_data,
2416 LTO_section_ipa_icf, NULL, &len);
2419 read_section (file_data, data, len);
2423 /* Register callgraph and varpool hooks. */
2426 sem_item_optimizer::register_hooks (void)
2428 if (!m_cgraph_node_hooks)
2429 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
2430 (&sem_item_optimizer::cgraph_removal_hook, this);
2432 if (!m_varpool_node_hooks)
2433 m_varpool_node_hooks = symtab->add_varpool_removal_hook
2434 (&sem_item_optimizer::varpool_removal_hook, this);
2437 /* Unregister callgraph and varpool hooks. */
2440 sem_item_optimizer::unregister_hooks (void)
2442 if (m_cgraph_node_hooks)
2443 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
2445 if (m_varpool_node_hooks)
2446 symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
2449 /* Adds a CLS to hashtable associated by hash value. */
2452 sem_item_optimizer::add_class (congruence_class *cls)
2454 gcc_assert (cls->members.length ());
2456 congruence_class_group *group = get_group_by_hash (
2457 cls->members[0]->get_hash (),
2458 cls->members[0]->type);
2459 group->classes.safe_push (cls);
2462 /* Gets a congruence class group based on given HASH value and TYPE. */
2464 congruence_class_group *
2465 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
2467 congruence_class_group *item = XNEW (congruence_class_group);
2471 congruence_class_group **slot = m_classes.find_slot (item, INSERT);
2477 item->classes.create (1);
2484 /* Callgraph removal hook called for a NODE with a custom DATA. */
2487 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
2489 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2490 optimizer->remove_symtab_node (node);
2493 /* Varpool removal hook called for a NODE with a custom DATA. */
2496 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
2498 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2499 optimizer->remove_symtab_node (node);
2502 /* Remove symtab NODE triggered by symtab removal hooks. */
2505 sem_item_optimizer::remove_symtab_node (symtab_node *node)
2507 gcc_assert (!m_classes.elements());
2509 m_removed_items_set.add (node);
2513 sem_item_optimizer::remove_item (sem_item *item)
2515 if (m_symtab_node_map.get (item->node))
2516 m_symtab_node_map.remove (item->node);
2520 /* Removes all callgraph and varpool nodes that are marked by symtab
2524 sem_item_optimizer::filter_removed_items (void)
2526 auto_vec <sem_item *> filtered;
2528 for (unsigned int i = 0; i < m_items.length(); i++)
2530 sem_item *item = m_items[i];
2532 if (m_removed_items_set.contains (item->node))
2538 if (item->type == FUNC)
2540 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
2542 if (in_lto_p && (cnode->alias || cnode->body_removed))
2545 filtered.safe_push (item);
2549 if (!flag_ipa_icf_variables)
2553 /* Filter out non-readonly variables. */
2554 tree decl = item->decl;
2555 if (TREE_READONLY (decl))
2556 filtered.safe_push (item);
2563 /* Clean-up of released semantic items. */
2566 for (unsigned int i = 0; i < filtered.length(); i++)
2567 m_items.safe_push (filtered[i]);
2570 /* Optimizer entry point which returns true in case it processes
2571 a merge operation. True is returned if there's a merge operation
2575 sem_item_optimizer::execute (void)
2577 filter_removed_items ();
2578 unregister_hooks ();
2581 update_hash_by_addr_refs ();
2582 build_hash_based_classes ();
2585 fprintf (dump_file, "Dump after hash based groups\n");
2586 dump_cong_classes ();
2588 for (unsigned int i = 0; i < m_items.length(); i++)
2589 m_items[i]->init_wpa ();
2591 subdivide_classes_by_equality (true);
2594 fprintf (dump_file, "Dump after WPA based types groups\n");
2596 dump_cong_classes ();
2598 process_cong_reduction ();
2602 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
2604 dump_cong_classes ();
2606 parse_nonsingleton_classes ();
2607 subdivide_classes_by_equality ();
2610 fprintf (dump_file, "Dump after full equality comparison of groups\n");
2612 dump_cong_classes ();
2614 unsigned int prev_class_count = m_classes_count;
2616 process_cong_reduction ();
2617 dump_cong_classes ();
2619 bool merged_p = merge_classes (prev_class_count);
2621 if (dump_file && (dump_flags & TDF_DETAILS))
2622 symtab_node::dump_table (dump_file);
2627 /* Function responsible for visiting all potential functions and
2628 read-only variables that can be merged. */
2631 sem_item_optimizer::parse_funcs_and_vars (void)
2635 if (flag_ipa_icf_functions)
2636 FOR_EACH_DEFINED_FUNCTION (cnode)
2638 sem_function *f = sem_function::parse (cnode, &m_bmstack);
2641 m_items.safe_push (f);
2642 m_symtab_node_map.put (cnode, f);
2645 fprintf (dump_file, "Parsed function:%s\n", f->node->asm_name ());
2647 if (dump_file && (dump_flags & TDF_DETAILS))
2648 f->dump_to_file (dump_file);
2651 fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
2654 varpool_node *vnode;
2656 if (flag_ipa_icf_variables)
2657 FOR_EACH_DEFINED_VARIABLE (vnode)
2659 sem_variable *v = sem_variable::parse (vnode, &m_bmstack);
2663 m_items.safe_push (v);
2664 m_symtab_node_map.put (vnode, v);
2669 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2672 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
2674 item->index_in_class = cls->members.length ();
2675 cls->members.safe_push (item);
2679 /* For each semantic item, append hash values of references. */
2682 sem_item_optimizer::update_hash_by_addr_refs ()
2684 /* First, append to hash sensitive references and class type if it need to
2685 be matched for ODR. */
2686 for (unsigned i = 0; i < m_items.length (); i++)
2688 m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
2689 if (m_items[i]->type == FUNC)
2691 if (TREE_CODE (TREE_TYPE (m_items[i]->decl)) == METHOD_TYPE
2692 && contains_polymorphic_type_p
2693 (method_class_type (TREE_TYPE (m_items[i]->decl)))
2694 && (DECL_CXX_CONSTRUCTOR_P (m_items[i]->decl)
2695 || (static_cast<sem_function *> (m_items[i])->param_used_p (0)
2696 && static_cast<sem_function *> (m_items[i])
2697 ->compare_polymorphic_p ())))
2700 = method_class_type (TREE_TYPE (m_items[i]->decl));
2701 inchash::hash hstate (m_items[i]->hash);
2703 if (TYPE_NAME (class_type)
2704 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type)))
2706 (IDENTIFIER_HASH_VALUE
2707 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type))));
2709 m_items[i]->hash = hstate.end ();
2714 /* Once all symbols have enhanced hash value, we can append
2715 hash values of symbols that are seen by IPA ICF and are
2716 references by a semantic item. Newly computed values
2717 are saved to global_hash member variable. */
2718 for (unsigned i = 0; i < m_items.length (); i++)
2719 m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
2721 /* Global hash value replace current hash values. */
2722 for (unsigned i = 0; i < m_items.length (); i++)
2723 m_items[i]->hash = m_items[i]->global_hash;
2726 /* Congruence classes are built by hash value. */
2729 sem_item_optimizer::build_hash_based_classes (void)
2731 for (unsigned i = 0; i < m_items.length (); i++)
2733 sem_item *item = m_items[i];
2735 congruence_class_group *group = get_group_by_hash (item->hash,
2738 if (!group->classes.length ())
2741 group->classes.safe_push (new congruence_class (class_id++));
2744 add_item_to_class (group->classes[0], item);
2748 /* Build references according to call graph. */
2751 sem_item_optimizer::build_graph (void)
2753 for (unsigned i = 0; i < m_items.length (); i++)
2755 sem_item *item = m_items[i];
2756 m_symtab_node_map.put (item->node, item);
2759 for (unsigned i = 0; i < m_items.length (); i++)
2761 sem_item *item = m_items[i];
2763 if (item->type == FUNC)
2765 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
2767 cgraph_edge *e = cnode->callees;
2770 sem_item **slot = m_symtab_node_map.get
2771 (e->callee->ultimate_alias_target ());
2773 item->add_reference (*slot);
2779 ipa_ref *ref = NULL;
2780 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
2782 sem_item **slot = m_symtab_node_map.get
2783 (ref->referred->ultimate_alias_target ());
2785 item->add_reference (*slot);
2790 /* Semantic items in classes having more than one element and initialized.
2791 In case of WPA, we load function body. */
2794 sem_item_optimizer::parse_nonsingleton_classes (void)
2796 unsigned int init_called_count = 0;
2798 for (unsigned i = 0; i < m_items.length (); i++)
2799 if (m_items[i]->cls->members.length () > 1)
2801 m_items[i]->init ();
2802 init_called_count++;
2806 fprintf (dump_file, "Init called for %u items (%.2f%%).\n", init_called_count,
2807 m_items.length () ? 100.0f * init_called_count / m_items.length (): 0.0f);
2810 /* Equality function for semantic items is used to subdivide existing
2811 classes. If IN_WPA, fast equality function is invoked. */
2814 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
2816 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2817 it != m_classes.end (); ++it)
2819 unsigned int class_count = (*it)->classes.length ();
2821 for (unsigned i = 0; i < class_count; i++)
2823 congruence_class *c = (*it)->classes [i];
2825 if (c->members.length() > 1)
2827 auto_vec <sem_item *> new_vector;
2829 sem_item *first = c->members[0];
2830 new_vector.safe_push (first);
2832 unsigned class_split_first = (*it)->classes.length ();
2834 for (unsigned j = 1; j < c->members.length (); j++)
2836 sem_item *item = c->members[j];
2838 bool equals = in_wpa ? first->equals_wpa (item,
2839 m_symtab_node_map) : first->equals (item, m_symtab_node_map);
2842 new_vector.safe_push (item);
2845 bool integrated = false;
2847 for (unsigned k = class_split_first; k < (*it)->classes.length (); k++)
2849 sem_item *x = (*it)->classes[k]->members[0];
2850 bool equals = in_wpa ? x->equals_wpa (item,
2851 m_symtab_node_map) : x->equals (item, m_symtab_node_map);
2856 add_item_to_class ((*it)->classes[k], item);
2864 congruence_class *c = new congruence_class (class_id++);
2866 add_item_to_class (c, item);
2868 (*it)->classes.safe_push (c);
2873 // we replace newly created new_vector for the class we've just splitted
2874 c->members.release ();
2875 c->members.create (new_vector.length ());
2877 for (unsigned int j = 0; j < new_vector.length (); j++)
2878 add_item_to_class (c, new_vector[j]);
2886 /* Subdivide classes by address references that members of the class
2887 reference. Example can be a pair of functions that have an address
2888 taken from a function. If these addresses are different the class
2892 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2894 typedef hash_map <symbol_compare_collection *, vec <sem_item *>,
2895 symbol_compare_hashmap_traits> subdivide_hash_map;
2897 unsigned newly_created_classes = 0;
2899 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2900 it != m_classes.end (); ++it)
2902 unsigned int class_count = (*it)->classes.length ();
2903 auto_vec<congruence_class *> new_classes;
2905 for (unsigned i = 0; i < class_count; i++)
2907 congruence_class *c = (*it)->classes [i];
2909 if (c->members.length() > 1)
2911 subdivide_hash_map split_map;
2913 for (unsigned j = 0; j < c->members.length (); j++)
2915 sem_item *source_node = c->members[j];
2917 symbol_compare_collection *collection = new symbol_compare_collection (source_node->node);
2920 vec <sem_item *> *slot = &split_map.get_or_insert (collection,
2922 gcc_checking_assert (slot);
2924 slot->safe_push (source_node);
2930 /* If the map contains more than one key, we have to split the map
2932 if (split_map.elements () != 1)
2934 bool first_class = true;
2936 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2937 it2 != split_map.end (); ++it2)
2939 congruence_class *new_cls;
2940 new_cls = new congruence_class (class_id++);
2942 for (unsigned k = 0; k < (*it2).second.length (); k++)
2943 add_item_to_class (new_cls, (*it2).second[k]);
2945 worklist_push (new_cls);
2946 newly_created_classes++;
2950 (*it)->classes[i] = new_cls;
2951 first_class = false;
2955 new_classes.safe_push (new_cls);
2961 /* Release memory. */
2962 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2963 it2 != split_map.end (); ++it2)
2965 delete (*it2).first;
2966 (*it2).second.release ();
2971 for (unsigned i = 0; i < new_classes.length (); i++)
2972 (*it)->classes.safe_push (new_classes[i]);
2975 return newly_created_classes;
2978 /* Verify congruence classes if checking is enabled. */
2981 sem_item_optimizer::verify_classes (void)
2984 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2985 it != m_classes.end (); ++it)
2987 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2989 congruence_class *cls = (*it)->classes[i];
2991 gcc_checking_assert (cls);
2992 gcc_checking_assert (cls->members.length () > 0);
2994 for (unsigned int j = 0; j < cls->members.length (); j++)
2996 sem_item *item = cls->members[j];
2998 gcc_checking_assert (item);
2999 gcc_checking_assert (item->cls == cls);
3001 for (unsigned k = 0; k < item->usages.length (); k++)
3003 sem_usage_pair *usage = item->usages[k];
3004 gcc_checking_assert (usage->item->index_in_class <
3005 usage->item->cls->members.length ());
3013 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3014 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3015 but unused argument. */
3018 sem_item_optimizer::release_split_map (congruence_class * const &,
3019 bitmap const &b, traverse_split_pair *)
3028 /* Process split operation for a class given as pointer CLS_PTR,
3029 where bitmap B splits congruence class members. DATA is used
3030 as argument of split pair. */
3033 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
3034 bitmap const &b, traverse_split_pair *pair)
3036 sem_item_optimizer *optimizer = pair->optimizer;
3037 const congruence_class *splitter_cls = pair->cls;
3039 /* If counted bits are greater than zero and less than the number of members
3040 a group will be splitted. */
3041 unsigned popcount = bitmap_count_bits (b);
3043 if (popcount > 0 && popcount < cls->members.length ())
3045 congruence_class* newclasses[2] = { new congruence_class (class_id++), new congruence_class (class_id++) };
3047 for (unsigned int i = 0; i < cls->members.length (); i++)
3049 int target = bitmap_bit_p (b, i);
3050 congruence_class *tc = newclasses[target];
3052 add_item_to_class (tc, cls->members[i]);
3055 #ifdef ENABLE_CHECKING
3056 for (unsigned int i = 0; i < 2; i++)
3057 gcc_checking_assert (newclasses[i]->members.length ());
3060 if (splitter_cls == cls)
3061 optimizer->splitter_class_removed = true;
3063 /* Remove old class from worklist if presented. */
3064 bool in_worklist = cls->in_worklist;
3067 cls->in_worklist = false;
3069 congruence_class_group g;
3070 g.hash = cls->members[0]->get_hash ();
3071 g.type = cls->members[0]->type;
3073 congruence_class_group *slot = optimizer->m_classes.find(&g);
3075 for (unsigned int i = 0; i < slot->classes.length (); i++)
3076 if (slot->classes[i] == cls)
3078 slot->classes.ordered_remove (i);
3082 /* New class will be inserted and integrated to work list. */
3083 for (unsigned int i = 0; i < 2; i++)
3084 optimizer->add_class (newclasses[i]);
3086 /* Two classes replace one, so that increment just by one. */
3087 optimizer->m_classes_count++;
3089 /* If OLD class was presented in the worklist, we remove the class
3090 and replace it will both newly created classes. */
3092 for (unsigned int i = 0; i < 2; i++)
3093 optimizer->worklist_push (newclasses[i]);
3094 else /* Just smaller class is inserted. */
3096 unsigned int smaller_index = newclasses[0]->members.length () <
3097 newclasses[1]->members.length () ?
3099 optimizer->worklist_push (newclasses[smaller_index]);
3102 if (dump_file && (dump_flags & TDF_DETAILS))
3104 fprintf (dump_file, " congruence class splitted:\n");
3105 cls->dump (dump_file, 4);
3107 fprintf (dump_file, " newly created groups:\n");
3108 for (unsigned int i = 0; i < 2; i++)
3109 newclasses[i]->dump (dump_file, 4);
3112 /* Release class if not presented in work list. */
3121 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3122 Bitmap stack BMSTACK is used for bitmap allocation. */
3125 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
3128 hash_map <congruence_class *, bitmap> split_map;
3130 for (unsigned int i = 0; i < cls->members.length (); i++)
3132 sem_item *item = cls->members[i];
3134 /* Iterate all usages that have INDEX as usage of the item. */
3135 for (unsigned int j = 0; j < item->usages.length (); j++)
3137 sem_usage_pair *usage = item->usages[j];
3139 if (usage->index != index)
3142 bitmap *slot = split_map.get (usage->item->cls);
3147 b = BITMAP_ALLOC (&m_bmstack);
3148 split_map.put (usage->item->cls, b);
3154 gcc_checking_assert (usage->item->cls);
3155 gcc_checking_assert (usage->item->index_in_class <
3156 usage->item->cls->members.length ());
3159 bitmap_set_bit (b, usage->item->index_in_class);
3163 traverse_split_pair pair;
3164 pair.optimizer = this;
3167 splitter_class_removed = false;
3169 <traverse_split_pair *, sem_item_optimizer::traverse_congruence_split> (&pair);
3171 /* Bitmap clean-up. */
3173 <traverse_split_pair *, sem_item_optimizer::release_split_map> (NULL);
3176 /* Every usage of a congruence class CLS is a candidate that can split the
3177 collection of classes. Bitmap stack BMSTACK is used for bitmap
3181 sem_item_optimizer::do_congruence_step (congruence_class *cls)
3186 bitmap usage = BITMAP_ALLOC (&m_bmstack);
3188 for (unsigned int i = 0; i < cls->members.length (); i++)
3189 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
3191 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
3193 if (dump_file && (dump_flags & TDF_DETAILS))
3194 fprintf (dump_file, " processing congruece step for class: %u, index: %u\n",
3197 do_congruence_step_for_index (cls, i);
3199 if (splitter_class_removed)
3203 BITMAP_FREE (usage);
3206 /* Adds a newly created congruence class CLS to worklist. */
3209 sem_item_optimizer::worklist_push (congruence_class *cls)
3211 /* Return if the class CLS is already presented in work list. */
3212 if (cls->in_worklist)
3215 cls->in_worklist = true;
3216 worklist.push_back (cls);
3219 /* Pops a class from worklist. */
3222 sem_item_optimizer::worklist_pop (void)
3224 congruence_class *cls;
3226 while (!worklist.empty ())
3228 cls = worklist.front ();
3229 worklist.pop_front ();
3230 if (cls->in_worklist)
3232 cls->in_worklist = false;
3238 /* Work list item was already intended to be removed.
3239 The only reason for doing it is to split a class.
3240 Thus, the class CLS is deleted. */
3248 /* Iterative congruence reduction function. */
3251 sem_item_optimizer::process_cong_reduction (void)
3253 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3254 it != m_classes.end (); ++it)
3255 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3256 if ((*it)->classes[i]->is_class_used ())
3257 worklist_push ((*it)->classes[i]);
3260 fprintf (dump_file, "Worklist has been filled with: %lu\n",
3261 (unsigned long) worklist.size ());
3263 if (dump_file && (dump_flags & TDF_DETAILS))
3264 fprintf (dump_file, "Congruence class reduction\n");
3266 congruence_class *cls;
3268 /* Process complete congruence reduction. */
3269 while ((cls = worklist_pop ()) != NULL)
3270 do_congruence_step (cls);
3272 /* Subdivide newly created classes according to references. */
3273 unsigned new_classes = subdivide_classes_by_sensitive_refs ();
3276 fprintf (dump_file, "Address reference subdivision created: %u "
3277 "new classes.\n", new_classes);
3280 /* Debug function prints all informations about congruence classes. */
3283 sem_item_optimizer::dump_cong_classes (void)
3289 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3290 m_classes_count, (unsigned long) m_classes.elements(), m_items.length ());
3292 /* Histogram calculation. */
3293 unsigned int max_index = 0;
3294 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
3296 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3297 it != m_classes.end (); ++it)
3299 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3301 unsigned int c = (*it)->classes[i]->members.length ();
3309 "Class size histogram [num of members]: number of classe number of classess\n");
3311 for (unsigned int i = 0; i <= max_index; i++)
3313 fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
3315 fprintf (dump_file, "\n\n");
3318 if (dump_flags & TDF_DETAILS)
3319 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3320 it != m_classes.end (); ++it)
3322 fprintf (dump_file, " group: with %u classes:\n", (*it)->classes.length ());
3324 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3326 (*it)->classes[i]->dump (dump_file, 4);
3328 if(i < (*it)->classes.length () - 1)
3329 fprintf (dump_file, " ");
3336 /* After reduction is done, we can declare all items in a group
3337 to be equal. PREV_CLASS_COUNT is start number of classes
3338 before reduction. True is returned if there's a merge operation
3342 sem_item_optimizer::merge_classes (unsigned int prev_class_count)
3344 unsigned int item_count = m_items.length ();
3345 unsigned int class_count = m_classes_count;
3346 unsigned int equal_items = item_count - class_count;
3348 unsigned int non_singular_classes_count = 0;
3349 unsigned int non_singular_classes_sum = 0;
3351 bool merged_p = false;
3353 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3354 it != m_classes.end (); ++it)
3355 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3357 congruence_class *c = (*it)->classes[i];
3358 if (c->members.length () > 1)
3360 non_singular_classes_count++;
3361 non_singular_classes_sum += c->members.length ();
3367 fprintf (dump_file, "\nItem count: %u\n", item_count);
3368 fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
3369 prev_class_count, class_count);
3370 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
3371 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
3372 class_count ? 1.0f * item_count / class_count : 0.0f);
3373 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
3374 non_singular_classes_count ? 1.0f * non_singular_classes_sum /
3375 non_singular_classes_count : 0.0f,
3376 non_singular_classes_count);
3377 fprintf (dump_file, "Equal symbols: %u\n", equal_items);
3378 fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
3379 item_count ? 100.0f * equal_items / item_count : 0.0f);
3382 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3383 it != m_classes.end (); ++it)
3384 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3386 congruence_class *c = (*it)->classes[i];
3388 if (c->members.length () == 1)
3391 gcc_assert (c->members.length ());
3393 sem_item *source = c->members[0];
3395 for (unsigned int j = 1; j < c->members.length (); j++)
3397 sem_item *alias = c->members[j];
3401 fprintf (dump_file, "Semantic equality hit:%s->%s\n",
3402 xstrdup_for_dump (source->node->name ()),
3403 xstrdup_for_dump (alias->node->name ()));
3404 fprintf (dump_file, "Assembler symbol names:%s->%s\n",
3405 xstrdup_for_dump (source->node->asm_name ()),
3406 xstrdup_for_dump (alias->node->asm_name ()));
3409 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl)))
3413 "Merge operation is skipped due to no_icf "
3419 if (dump_file && (dump_flags & TDF_DETAILS))
3421 source->dump_to_file (dump_file);
3422 alias->dump_to_file (dump_file);
3425 merged_p |= source->merge (alias);
3432 /* Dump function prints all class members to a FILE with an INDENT. */
3435 congruence_class::dump (FILE *file, unsigned int indent) const
3437 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
3438 id, members[0]->get_hash (), members.length ());
3440 FPUTS_SPACES (file, indent + 2, "");
3441 for (unsigned i = 0; i < members.length (); i++)
3442 fprintf (file, "%s(%p/%u) ", members[i]->node->asm_name (),
3443 (void *) members[i]->decl,
3444 members[i]->node->order);
3446 fprintf (file, "\n");
3449 /* Returns true if there's a member that is used from another group. */
3452 congruence_class::is_class_used (void)
3454 for (unsigned int i = 0; i < members.length (); i++)
3455 if (members[i]->usages.length ())
3461 /* Generate pass summary for IPA ICF pass. */
3464 ipa_icf_generate_summary (void)
3467 optimizer = new sem_item_optimizer ();
3469 optimizer->register_hooks ();
3470 optimizer->parse_funcs_and_vars ();
3473 /* Write pass summary for IPA ICF pass. */
3476 ipa_icf_write_summary (void)
3478 gcc_assert (optimizer);
3480 optimizer->write_summary ();
3483 /* Read pass summary for IPA ICF pass. */
3486 ipa_icf_read_summary (void)
3489 optimizer = new sem_item_optimizer ();
3491 optimizer->read_summary ();
3492 optimizer->register_hooks ();
3495 /* Semantic equality exection function. */
3498 ipa_icf_driver (void)
3500 gcc_assert (optimizer);
3502 bool merged_p = optimizer->execute ();
3507 return merged_p ? TODO_remove_functions : 0;
3510 const pass_data pass_data_ipa_icf =
3512 IPA_PASS, /* type */
3514 OPTGROUP_IPA, /* optinfo_flags */
3515 TV_IPA_ICF, /* tv_id */
3516 0, /* properties_required */
3517 0, /* properties_provided */
3518 0, /* properties_destroyed */
3519 0, /* todo_flags_start */
3520 0, /* todo_flags_finish */
3523 class pass_ipa_icf : public ipa_opt_pass_d
3526 pass_ipa_icf (gcc::context *ctxt)
3527 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
3528 ipa_icf_generate_summary, /* generate_summary */
3529 ipa_icf_write_summary, /* write_summary */
3530 ipa_icf_read_summary, /* read_summary */
3532 write_optimization_summary */
3534 read_optimization_summary */
3535 NULL, /* stmt_fixup */
3536 0, /* function_transform_todo_flags_start */
3537 NULL, /* function_transform */
3538 NULL) /* variable_transform */
3541 /* opt_pass methods: */
3542 virtual bool gate (function *)
3544 return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
3547 virtual unsigned int execute (function *)
3549 return ipa_icf_driver();
3551 }; // class pass_ipa_icf
3553 } // ipa_icf namespace
3556 make_pass_ipa_icf (gcc::context *ctxt)
3558 return new ipa_icf::pass_ipa_icf (ctxt);