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);
604 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
605 cgraph_node *cnode2 = dyn_cast <cgraph_node *> (item->node);
607 m_compared_func = static_cast<sem_function *> (item);
609 if (arg_types.length () != m_compared_func->arg_types.length ())
610 return return_false_with_msg ("different number of arguments");
612 if (cnode->thunk.thunk_p != cnode2->thunk.thunk_p)
613 return return_false_with_msg ("thunk_p mismatch");
615 if (cnode->thunk.thunk_p)
617 if (cnode->thunk.fixed_offset != cnode2->thunk.fixed_offset)
618 return return_false_with_msg ("thunk fixed_offset mismatch");
619 if (cnode->thunk.virtual_value != cnode2->thunk.virtual_value)
620 return return_false_with_msg ("thunk virtual_value mismatch");
621 if (cnode->thunk.this_adjusting != cnode2->thunk.this_adjusting)
622 return return_false_with_msg ("thunk this_adjusting mismatch");
623 if (cnode->thunk.virtual_offset_p != cnode2->thunk.virtual_offset_p)
624 return return_false_with_msg ("thunk virtual_offset_p mismatch");
625 if (cnode->thunk.add_pointer_bounds_args
626 != cnode2->thunk.add_pointer_bounds_args)
627 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
630 /* Compare special function DECL attributes. */
631 if (DECL_FUNCTION_PERSONALITY (decl)
632 != DECL_FUNCTION_PERSONALITY (item->decl))
633 return return_false_with_msg ("function personalities are different");
635 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
636 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item->decl))
637 return return_false_with_msg ("intrument function entry exit "
638 "attributes are different");
640 if (DECL_NO_LIMIT_STACK (decl) != DECL_NO_LIMIT_STACK (item->decl))
641 return return_false_with_msg ("no stack limit attributes are different");
643 if (DECL_CXX_CONSTRUCTOR_P (decl) != DECL_CXX_CONSTRUCTOR_P (item->decl))
644 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
646 if (DECL_CXX_DESTRUCTOR_P (decl) != DECL_CXX_DESTRUCTOR_P (item->decl))
647 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
649 /* TODO: pure/const flags mostly matters only for references, except for
650 the fact that codegen takes LOOPING flag as a hint that loops are
651 finite. We may arrange the code to always pick leader that has least
652 specified flags and then this can go into comparing symbol properties. */
653 if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
654 return return_false_with_msg ("decl_or_type flags are different");
656 /* Do not match polymorphic constructors of different types. They calls
657 type memory location for ipa-polymorphic-call and we do not want
658 it to get confused by wrong type. */
659 if (DECL_CXX_CONSTRUCTOR_P (decl)
660 && TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE)
662 if (TREE_CODE (TREE_TYPE (item->decl)) != METHOD_TYPE)
663 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
664 else if (!func_checker::compatible_polymorphic_types_p
665 (method_class_type (TREE_TYPE (decl)),
666 method_class_type (TREE_TYPE (item->decl)), false))
667 return return_false_with_msg ("ctor polymorphic type mismatch");
670 /* Checking function TARGET and OPTIMIZATION flags. */
671 cl_target_option *tar1 = target_opts_for_fn (decl);
672 cl_target_option *tar2 = target_opts_for_fn (item->decl);
674 if (tar1 != tar2 && !cl_target_option_eq (tar1, tar2))
676 if (dump_file && (dump_flags & TDF_DETAILS))
678 fprintf (dump_file, "target flags difference");
679 cl_target_option_print_diff (dump_file, 2, tar1, tar2);
682 return return_false_with_msg ("Target flags are different");
685 cl_optimization *opt1 = opts_for_fn (decl);
686 cl_optimization *opt2 = opts_for_fn (item->decl);
688 if (opt1 != opt2 && memcmp (opt1, opt2, sizeof(cl_optimization)))
690 if (dump_file && (dump_flags & TDF_DETAILS))
692 fprintf (dump_file, "optimization flags difference");
693 cl_optimization_print_diff (dump_file, 2, opt1, opt2);
696 return return_false_with_msg ("optimization flags are different");
699 /* Result type checking. */
700 if (!func_checker::compatible_types_p (result_type,
701 m_compared_func->result_type))
702 return return_false_with_msg ("result types are different");
704 /* Checking types of arguments. */
705 for (unsigned i = 0; i < arg_types.length (); i++)
707 /* This guard is here for function pointer with attributes (pr59927.c). */
708 if (!arg_types[i] || !m_compared_func->arg_types[i])
709 return return_false_with_msg ("NULL argument type");
711 /* We always need to match types so we are sure the callin conventions
713 if (!func_checker::compatible_types_p (arg_types[i],
714 m_compared_func->arg_types[i]))
715 return return_false_with_msg ("argument type is different");
717 /* On used arguments we need to do a bit more of work. */
718 if (!param_used_p (i))
720 if (POINTER_TYPE_P (arg_types[i])
721 && (TYPE_RESTRICT (arg_types[i])
722 != TYPE_RESTRICT (m_compared_func->arg_types[i])))
723 return return_false_with_msg ("argument restrict flag mismatch");
724 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
725 if (POINTER_TYPE_P (arg_types[i])
726 && TREE_CODE (arg_types[i])
727 != TREE_CODE (m_compared_func->arg_types[i])
728 && opt_for_fn (decl, flag_delete_null_pointer_checks))
729 return return_false_with_msg ("pointer wrt reference mismatch");
732 if (node->num_references () != item->node->num_references ())
733 return return_false_with_msg ("different number of references");
735 /* Checking function attributes.
736 This is quadratic in number of attributes */
737 if (comp_type_attributes (TREE_TYPE (decl),
738 TREE_TYPE (item->decl)) != 1)
739 return return_false_with_msg ("different type attributes");
740 if (!compare_attributes (DECL_ATTRIBUTES (decl),
741 DECL_ATTRIBUTES (item->decl)))
742 return return_false_with_msg ("different decl attributes");
744 /* The type of THIS pointer type memory location for
745 ipa-polymorphic-call-analysis. */
746 if (opt_for_fn (decl, flag_devirtualize)
747 && (TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE
748 || TREE_CODE (TREE_TYPE (item->decl)) == METHOD_TYPE)
750 && compare_polymorphic_p ())
752 if (TREE_CODE (TREE_TYPE (decl)) != TREE_CODE (TREE_TYPE (item->decl)))
753 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
754 if (!func_checker::compatible_polymorphic_types_p
755 (method_class_type (TREE_TYPE (decl)),
756 method_class_type (TREE_TYPE (item->decl)), false))
757 return return_false_with_msg ("THIS pointer ODR type mismatch");
760 ipa_ref *ref = NULL, *ref2 = NULL;
761 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
763 item->node->iterate_reference (i, ref2);
765 if (ref->use != ref2->use)
766 return return_false_with_msg ("reference use mismatch");
768 if (!compare_symbol_references (ignored_nodes, ref->referred,
770 ref->address_matters_p ()))
774 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
775 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
779 if (!compare_symbol_references (ignored_nodes, e1->callee,
782 if (!compare_edge_flags (e1, e2))
785 e1 = e1->next_callee;
786 e2 = e2->next_callee;
790 return return_false_with_msg ("different number of calls");
792 e1 = dyn_cast <cgraph_node *> (node)->indirect_calls;
793 e2 = dyn_cast <cgraph_node *> (item->node)->indirect_calls;
797 if (!compare_edge_flags (e1, e2))
800 e1 = e1->next_callee;
801 e2 = e2->next_callee;
805 return return_false_with_msg ("different number of indirect calls");
810 /* Update hash by address sensitive references. We iterate over all
811 sensitive references (address_matters_p) and we hash ultime alias
812 target of these nodes, which can improve a semantic item hash.
814 Also hash in referenced symbols properties. This can be done at any time
815 (as the properties should not change), but it is convenient to do it here
816 while we walk the references anyway. */
819 sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
820 sem_item *> &m_symtab_node_map)
823 inchash::hash hstate (hash);
825 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
827 hstate.add_int (ref->use);
828 hash_referenced_symbol_properties (ref->referred, hstate,
829 ref->use == IPA_REF_ADDR);
830 if (ref->address_matters_p () || !m_symtab_node_map.get (ref->referred))
831 hstate.add_int (ref->referred->ultimate_alias_target ()->order);
834 if (is_a <cgraph_node *> (node))
836 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
839 sem_item **result = m_symtab_node_map.get (e->callee);
840 hash_referenced_symbol_properties (e->callee, hstate, false);
842 hstate.add_int (e->callee->ultimate_alias_target ()->order);
846 hash = hstate.end ();
849 /* Update hash by computed local hash values taken from different
851 TODO: stronger SCC based hashing would be desirable here. */
854 sem_item::update_hash_by_local_refs (hash_map <symtab_node *,
855 sem_item *> &m_symtab_node_map)
858 inchash::hash state (hash);
860 for (unsigned j = 0; node->iterate_reference (j, ref); j++)
862 sem_item **result = m_symtab_node_map.get (ref->referring);
864 state.merge_hash ((*result)->hash);
869 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e;
872 sem_item **result = m_symtab_node_map.get (e->caller);
874 state.merge_hash ((*result)->hash);
878 global_hash = state.end ();
881 /* Returns true if the item equals to ITEM given as argument. */
884 sem_function::equals (sem_item *item,
885 hash_map <symtab_node *, sem_item *> &)
887 gcc_assert (item->type == FUNC);
888 bool eq = equals_private (item);
890 if (m_checker != NULL)
896 if (dump_file && (dump_flags & TDF_DETAILS))
898 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
899 xstrdup_for_dump (node->name()),
900 xstrdup_for_dump (item->node->name ()),
903 xstrdup_for_dump (node->asm_name ()),
904 xstrdup_for_dump (item->node->asm_name ()),
905 eq ? "true" : "false");
910 /* Processes function equality comparison. */
913 sem_function::equals_private (sem_item *item)
915 if (item->type != FUNC)
918 basic_block bb1, bb2;
920 edge_iterator ei1, ei2;
924 m_compared_func = static_cast<sem_function *> (item);
926 gcc_assert (decl != item->decl);
928 if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
929 || edge_count != m_compared_func->edge_count
930 || cfg_checksum != m_compared_func->cfg_checksum)
931 return return_false ();
933 m_checker = new func_checker (decl, m_compared_func->decl,
934 compare_polymorphic_p (),
937 &m_compared_func->refs_set);
938 for (arg1 = DECL_ARGUMENTS (decl),
939 arg2 = DECL_ARGUMENTS (m_compared_func->decl);
940 arg1; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2))
941 if (!m_checker->compare_decl (arg1, arg2))
942 return return_false ();
944 if (!dyn_cast <cgraph_node *> (node)->has_gimple_body_p ())
947 /* Fill-up label dictionary. */
948 for (unsigned i = 0; i < bb_sorted.length (); ++i)
950 m_checker->parse_labels (bb_sorted[i]);
951 m_checker->parse_labels (m_compared_func->bb_sorted[i]);
954 /* Checking all basic blocks. */
955 for (unsigned i = 0; i < bb_sorted.length (); ++i)
956 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
957 return return_false();
959 dump_message ("All BBs are equal\n");
961 auto_vec <int> bb_dict;
963 /* Basic block edges check. */
964 for (unsigned i = 0; i < bb_sorted.length (); ++i)
966 bb1 = bb_sorted[i]->bb;
967 bb2 = m_compared_func->bb_sorted[i]->bb;
969 ei2 = ei_start (bb2->preds);
971 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
975 if (e1->flags != e2->flags)
976 return return_false_with_msg ("flags comparison returns false");
978 if (!bb_dict_test (&bb_dict, e1->src->index, e2->src->index))
979 return return_false_with_msg ("edge comparison returns false");
981 if (!bb_dict_test (&bb_dict, e1->dest->index, e2->dest->index))
982 return return_false_with_msg ("BB comparison returns false");
984 if (!m_checker->compare_edge (e1, e2))
985 return return_false_with_msg ("edge comparison returns false");
991 /* Basic block PHI nodes comparison. */
992 for (unsigned i = 0; i < bb_sorted.length (); i++)
993 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
994 return return_false_with_msg ("PHI node comparison returns false");
999 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
1000 Helper for call_for_symbol_thunks_and_aliases. */
1003 set_local (cgraph_node *node, void *data)
1005 node->local.local = data != NULL;
1009 /* TREE_ADDRESSABLE of NODE to true.
1010 Helper for call_for_symbol_thunks_and_aliases. */
1013 set_addressable (varpool_node *node, void *)
1015 TREE_ADDRESSABLE (node->decl) = 1;
1019 /* Clear DECL_RTL of NODE.
1020 Helper for call_for_symbol_thunks_and_aliases. */
1023 clear_decl_rtl (symtab_node *node, void *)
1025 SET_DECL_RTL (node->decl, NULL);
1029 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1030 possible. Return number of redirections made. */
1033 redirect_all_callers (cgraph_node *n, cgraph_node *to)
1035 int nredirected = 0;
1037 cgraph_edge *e = n->callers;
1041 /* Redirecting thunks to interposable symbols or symbols in other sections
1042 may not be supported by target output code. Play safe for now and
1043 punt on redirection. */
1044 if (!e->caller->thunk.thunk_p)
1046 struct cgraph_edge *nexte = e->next_caller;
1047 e->redirect_callee (to);
1054 for (unsigned i = 0; n->iterate_direct_aliases (i, ref);)
1056 bool removed = false;
1057 cgraph_node *n_alias = dyn_cast <cgraph_node *> (ref->referring);
1059 if ((DECL_COMDAT_GROUP (n->decl)
1060 && (DECL_COMDAT_GROUP (n->decl)
1061 == DECL_COMDAT_GROUP (n_alias->decl)))
1062 || (n_alias->get_availability () > AVAIL_INTERPOSABLE
1063 && n->get_availability () > AVAIL_INTERPOSABLE))
1065 nredirected += redirect_all_callers (n_alias, to);
1066 if (n_alias->can_remove_if_no_direct_calls_p ()
1067 && !n_alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1069 && !n_alias->has_aliases_p ())
1078 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1082 sem_function::merge (sem_item *alias_item)
1084 gcc_assert (alias_item->type == FUNC);
1086 sem_function *alias_func = static_cast<sem_function *> (alias_item);
1088 cgraph_node *original = get_node ();
1089 cgraph_node *local_original = NULL;
1090 cgraph_node *alias = alias_func->get_node ();
1092 bool create_wrapper = false;
1093 bool create_alias = false;
1094 bool redirect_callers = false;
1095 bool remove = false;
1097 bool original_discardable = false;
1098 bool original_discarded = false;
1100 bool original_address_matters = original->address_matters_p ();
1101 bool alias_address_matters = alias->address_matters_p ();
1103 if (DECL_EXTERNAL (alias->decl))
1106 fprintf (dump_file, "Not unifying; alias is external.\n\n");
1110 if (DECL_NO_INLINE_WARNING_P (original->decl)
1111 != DECL_NO_INLINE_WARNING_P (alias->decl))
1116 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1120 /* Do not attempt to mix functions from different user sections;
1121 we do not know what user intends with those. */
1122 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
1123 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
1124 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
1129 "original and alias are in different sections.\n\n");
1133 /* See if original is in a section that can be discarded if the main
1134 symbol is not used. */
1136 if (original->can_be_discarded_p ())
1137 original_discardable = true;
1138 /* Also consider case where we have resolution info and we know that
1139 original's definition is not going to be used. In this case we can not
1140 create alias to original. */
1141 if (node->resolution != LDPR_UNKNOWN
1142 && !decl_binds_to_current_def_p (node->decl))
1143 original_discardable = original_discarded = true;
1145 /* Creating a symtab alias is the optimal way to merge.
1146 It however can not be used in the following cases:
1148 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1149 2) if ORIGINAL is in a section that may be discarded by linker or if
1150 it is an external functions where we can not create an alias
1151 (ORIGINAL_DISCARDABLE)
1152 3) if target do not support symbol aliases.
1153 4) original and alias lie in different comdat groups.
1155 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1156 and/or redirect all callers from ALIAS to ORIGINAL. */
1157 if ((original_address_matters && alias_address_matters)
1158 || (original_discardable
1159 && (!DECL_COMDAT_GROUP (alias->decl)
1160 || (DECL_COMDAT_GROUP (alias->decl)
1161 != DECL_COMDAT_GROUP (original->decl))))
1162 || original_discarded
1163 || !sem_item::target_supports_symbol_aliases_p ()
1164 || DECL_COMDAT_GROUP (alias->decl) != DECL_COMDAT_GROUP (original->decl))
1166 /* First see if we can produce wrapper. */
1168 /* Symbol properties that matter for references must be preserved.
1169 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1170 with proper properties. */
1171 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1172 alias->address_taken))
1176 "Wrapper cannot be created because referenced symbol "
1177 "properties mismatch\n");
1179 /* Do not turn function in one comdat group into wrapper to another
1180 comdat group. Other compiler producing the body of the
1181 another comdat group may make opossite decision and with unfortunate
1182 linker choices this may close a loop. */
1183 else if (DECL_COMDAT_GROUP (original->decl)
1184 && DECL_COMDAT_GROUP (alias->decl)
1185 && (DECL_COMDAT_GROUP (alias->decl)
1186 != DECL_COMDAT_GROUP (original->decl)))
1190 "Wrapper cannot be created because of COMDAT\n");
1192 else if (DECL_STATIC_CHAIN (alias->decl))
1196 "Can not create wrapper of nested functions.\n");
1198 /* TODO: We can also deal with variadic functions never calling
1200 else if (stdarg_p (TREE_TYPE (alias->decl)))
1204 "can not create wrapper of stdarg function.\n");
1206 else if (inline_summaries
1207 && inline_summaries->get (alias)->self_size <= 2)
1210 fprintf (dump_file, "Wrapper creation is not "
1211 "profitable (function is too small).\n");
1213 /* If user paid attention to mark function noinline, assume it is
1214 somewhat special and do not try to turn it into a wrapper that can
1215 not be undone by inliner. */
1216 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
1219 fprintf (dump_file, "Wrappers are not created for noinline.\n");
1222 create_wrapper = true;
1224 /* We can redirect local calls in the case both alias and orignal
1225 are not interposable. */
1227 = alias->get_availability () > AVAIL_INTERPOSABLE
1228 && original->get_availability () > AVAIL_INTERPOSABLE
1229 && !alias->instrumented_version;
1230 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1231 with proper properties. */
1232 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1233 alias->address_taken))
1234 redirect_callers = false;
1236 if (!redirect_callers && !create_wrapper)
1239 fprintf (dump_file, "Not unifying; can not redirect callers nor "
1240 "produce wrapper\n\n");
1244 /* Work out the symbol the wrapper should call.
1245 If ORIGINAL is interposable, we need to call a local alias.
1246 Also produce local alias (if possible) as an optimization.
1248 Local aliases can not be created inside comdat groups because that
1249 prevents inlining. */
1250 if (!original_discardable && !original->get_comdat_group ())
1253 = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
1255 && original->get_availability () > AVAIL_INTERPOSABLE)
1256 local_original = original;
1258 /* If we can not use local alias, fallback to the original
1260 else if (original->get_availability () > AVAIL_INTERPOSABLE)
1261 local_original = original;
1263 /* If original is COMDAT local, we can not really redirect calls outside
1264 of its comdat group to it. */
1265 if (original->comdat_local_p ())
1266 redirect_callers = false;
1267 if (!local_original)
1270 fprintf (dump_file, "Not unifying; "
1271 "can not produce local alias.\n\n");
1275 if (!redirect_callers && !create_wrapper)
1278 fprintf (dump_file, "Not unifying; "
1279 "can not redirect callers nor produce a wrapper\n\n");
1283 && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1285 && !alias->can_remove_if_no_direct_calls_p ())
1288 fprintf (dump_file, "Not unifying; can not make wrapper and "
1289 "function has other uses than direct calls\n\n");
1294 create_alias = true;
1296 if (redirect_callers)
1298 int nredirected = redirect_all_callers (alias, local_original);
1302 alias->icf_merged = true;
1303 local_original->icf_merged = true;
1305 if (dump_file && nredirected)
1306 fprintf (dump_file, "%i local calls have been "
1307 "redirected.\n", nredirected);
1310 /* If all callers was redirected, do not produce wrapper. */
1311 if (alias->can_remove_if_no_direct_calls_p ()
1312 && !alias->has_aliases_p ())
1314 create_wrapper = false;
1317 gcc_assert (!create_alias);
1319 else if (create_alias)
1321 alias->icf_merged = true;
1323 /* Remove the function's body. */
1324 ipa_merge_profiles (original, alias);
1325 alias->release_body (true);
1327 /* Notice global symbol possibly produced RTL. */
1328 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
1331 /* Create the alias. */
1332 cgraph_node::create_alias (alias_func->decl, decl);
1333 alias->resolve_alias (original);
1335 original->call_for_symbol_thunks_and_aliases
1336 (set_local, (void *)(size_t) original->local_p (), true);
1339 fprintf (dump_file, "Unified; Function alias has been created.\n\n");
1343 gcc_assert (!create_alias);
1344 alias->icf_merged = true;
1345 local_original->icf_merged = true;
1347 ipa_merge_profiles (local_original, alias, true);
1348 alias->create_wrapper (local_original);
1351 fprintf (dump_file, "Unified; Wrapper has been created.\n\n");
1354 /* It's possible that redirection can hit thunks that block
1355 redirection opportunities. */
1356 gcc_assert (alias->icf_merged || remove || redirect_callers);
1357 original->icf_merged = true;
1359 /* Inform the inliner about cross-module merging. */
1360 if ((original->lto_file_data || alias->lto_file_data)
1361 && original->lto_file_data != alias->lto_file_data)
1362 local_original->merged = original->merged = true;
1366 ipa_merge_profiles (original, alias);
1367 alias->release_body ();
1369 alias->body_removed = true;
1370 alias->icf_merged = true;
1372 fprintf (dump_file, "Unified; Function body was removed.\n");
1378 /* Semantic item initialization function. */
1381 sem_function::init (void)
1384 get_node ()->get_untransformed_body ();
1386 tree fndecl = node->decl;
1387 function *func = DECL_STRUCT_FUNCTION (fndecl);
1390 gcc_assert (SSANAMES (func));
1392 ssa_names_size = SSANAMES (func)->length ();
1396 region_tree = func->eh->region_tree;
1398 /* iterating all function arguments. */
1399 arg_count = count_formal_params (fndecl);
1401 edge_count = n_edges_for_fn (func);
1402 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1403 if (!cnode->thunk.thunk_p)
1405 cfg_checksum = coverage_compute_cfg_checksum (func);
1407 inchash::hash hstate;
1410 FOR_EACH_BB_FN (bb, func)
1412 unsigned nondbg_stmt_count = 0;
1415 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
1417 cfg_checksum = iterative_hash_host_wide_int (e->flags,
1420 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1423 gimple stmt = gsi_stmt (gsi);
1425 if (gimple_code (stmt) != GIMPLE_DEBUG
1426 && gimple_code (stmt) != GIMPLE_PREDICT)
1428 hash_stmt (stmt, hstate);
1429 nondbg_stmt_count++;
1433 gcode_hash = hstate.end ();
1434 bb_sizes.safe_push (nondbg_stmt_count);
1436 /* Inserting basic block to hash table. */
1437 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
1438 EDGE_COUNT (bb->preds)
1439 + EDGE_COUNT (bb->succs));
1441 bb_sorted.safe_push (semantic_bb);
1447 inchash::hash hstate;
1448 hstate.add_wide_int (cnode->thunk.fixed_offset);
1449 hstate.add_wide_int (cnode->thunk.virtual_value);
1450 hstate.add_flag (cnode->thunk.this_adjusting);
1451 hstate.add_flag (cnode->thunk.virtual_offset_p);
1452 hstate.add_flag (cnode->thunk.add_pointer_bounds_args);
1453 gcode_hash = hstate.end ();
1459 /* Accumulate to HSTATE a hash of expression EXP.
1460 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1461 and DECL equality classes. */
1464 sem_item::add_expr (const_tree exp, inchash::hash &hstate)
1466 if (exp == NULL_TREE)
1468 hstate.merge_hash (0);
1472 /* Handled component can be matched in a cureful way proving equivalence
1473 even if they syntactically differ. Just skip them. */
1475 while (handled_component_p (exp))
1476 exp = TREE_OPERAND (exp, 0);
1478 enum tree_code code = TREE_CODE (exp);
1479 hstate.add_int (code);
1483 /* Use inchash::add_expr for everything that is LTO stable. */
1491 inchash::add_expr (exp, hstate);
1495 unsigned HOST_WIDE_INT idx;
1498 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1500 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp), idx, value)
1502 add_expr (value, hstate);
1507 add_expr (get_base_address (TREE_OPERAND (exp, 0)), hstate);
1513 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1516 case POINTER_PLUS_EXPR:
1519 add_expr (TREE_OPERAND (exp, 0), hstate);
1520 add_expr (TREE_OPERAND (exp, 1), hstate);
1524 inchash::hash one, two;
1525 add_expr (TREE_OPERAND (exp, 0), one);
1526 add_expr (TREE_OPERAND (exp, 1), two);
1527 hstate.add_commutative (one, two);
1531 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1532 return add_expr (TREE_OPERAND (exp, 0), hstate);
1538 /* Accumulate to HSTATE a hash of type t.
1539 TYpes that may end up being compatible after LTO type merging needs to have
1543 sem_item::add_type (const_tree type, inchash::hash &hstate)
1545 if (type == NULL_TREE)
1547 hstate.merge_hash (0);
1551 type = TYPE_MAIN_VARIANT (type);
1552 if (TYPE_CANONICAL (type))
1553 type = TYPE_CANONICAL (type);
1555 if (!AGGREGATE_TYPE_P (type))
1556 hstate.add_int (TYPE_MODE (type));
1558 if (TREE_CODE (type) == COMPLEX_TYPE)
1560 hstate.add_int (COMPLEX_TYPE);
1561 sem_item::add_type (TREE_TYPE (type), hstate);
1563 else if (INTEGRAL_TYPE_P (type))
1565 hstate.add_int (INTEGER_TYPE);
1566 hstate.add_flag (TYPE_UNSIGNED (type));
1567 hstate.add_int (TYPE_PRECISION (type));
1569 else if (VECTOR_TYPE_P (type))
1571 hstate.add_int (VECTOR_TYPE);
1572 hstate.add_int (TYPE_PRECISION (type));
1573 sem_item::add_type (TREE_TYPE (type), hstate);
1575 else if (TREE_CODE (type) == ARRAY_TYPE)
1577 hstate.add_int (ARRAY_TYPE);
1578 /* Do not hash size, so complete and incomplete types can match. */
1579 sem_item::add_type (TREE_TYPE (type), hstate);
1581 else if (RECORD_OR_UNION_TYPE_P (type))
1583 hashval_t *val = optimizer->m_type_hash_cache.get (type);
1587 inchash::hash hstate2;
1592 hstate2.add_int (RECORD_TYPE);
1593 gcc_assert (COMPLETE_TYPE_P (type));
1595 for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
1596 if (TREE_CODE (f) == FIELD_DECL)
1598 add_type (TREE_TYPE (f), hstate2);
1602 hstate2.add_int (nf);
1603 hash = hstate2.end ();
1604 hstate.add_wide_int (hash);
1605 optimizer->m_type_hash_cache.put (type, hash);
1608 hstate.add_wide_int (*val);
1612 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1615 sem_function::hash_stmt (gimple stmt, inchash::hash &hstate)
1617 enum gimple_code code = gimple_code (stmt);
1619 hstate.add_int (code);
1624 add_expr (gimple_switch_index (as_a <gswitch *> (stmt)), hstate);
1627 hstate.add_int (gimple_assign_rhs_code (stmt));
1628 if (commutative_tree_code (gimple_assign_rhs_code (stmt))
1629 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1631 inchash::hash one, two;
1633 add_expr (gimple_assign_rhs1 (stmt), one);
1634 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt)), one);
1635 add_expr (gimple_assign_rhs2 (stmt), two);
1636 hstate.add_commutative (one, two);
1637 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1639 add_expr (gimple_assign_rhs3 (stmt), hstate);
1640 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt)), hstate);
1642 add_expr (gimple_assign_lhs (stmt), hstate);
1643 add_type (TREE_TYPE (gimple_assign_lhs (stmt)), two);
1646 /* ... fall through ... */
1652 /* All these statements are equivalent if their operands are. */
1653 for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1655 add_expr (gimple_op (stmt, i), hstate);
1656 if (gimple_op (stmt, i))
1657 add_type (TREE_TYPE (gimple_op (stmt, i)), hstate);
1665 /* Return true if polymorphic comparison must be processed. */
1668 sem_function::compare_polymorphic_p (void)
1670 struct cgraph_edge *e;
1672 if (!opt_for_fn (get_node ()->decl, flag_devirtualize))
1674 if (get_node ()->indirect_calls != NULL)
1676 /* TODO: We can do simple propagation determining what calls may lead to
1677 a polymorphic call. */
1678 for (e = get_node ()->callees; e; e = e->next_callee)
1679 if (e->callee->definition
1680 && opt_for_fn (e->callee->decl, flag_devirtualize))
1685 /* For a given call graph NODE, the function constructs new
1686 semantic function item. */
1689 sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
1691 tree fndecl = node->decl;
1692 function *func = DECL_STRUCT_FUNCTION (fndecl);
1694 if (!func || (!node->has_gimple_body_p () && !node->thunk.thunk_p))
1697 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
1700 sem_function *f = new sem_function (node, 0, stack);
1707 /* Parses function arguments and result type. */
1710 sem_function::parse_tree_args (void)
1714 if (arg_types.exists ())
1715 arg_types.release ();
1717 arg_types.create (4);
1718 tree fnargs = DECL_ARGUMENTS (decl);
1720 for (tree parm = fnargs; parm; parm = DECL_CHAIN (parm))
1721 arg_types.safe_push (DECL_ARG_TYPE (parm));
1723 /* Function result type. */
1724 result = DECL_RESULT (decl);
1725 result_type = result ? TREE_TYPE (result) : NULL;
1727 /* During WPA, we can get arguments by following method. */
1730 tree type = TYPE_ARG_TYPES (TREE_TYPE (decl));
1731 for (tree parm = type; parm; parm = TREE_CHAIN (parm))
1732 arg_types.safe_push (TYPE_CANONICAL (TREE_VALUE (parm)));
1734 result_type = TREE_TYPE (TREE_TYPE (decl));
1738 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1739 return true if phi nodes are semantically equivalent in these blocks . */
1742 sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
1744 gphi_iterator si1, si2;
1746 unsigned size1, size2, i;
1750 gcc_assert (bb1 != NULL);
1751 gcc_assert (bb2 != NULL);
1753 si2 = gsi_start_phis (bb2);
1754 for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
1757 gsi_next_nonvirtual_phi (&si1);
1758 gsi_next_nonvirtual_phi (&si2);
1760 if (gsi_end_p (si1) && gsi_end_p (si2))
1763 if (gsi_end_p (si1) || gsi_end_p (si2))
1764 return return_false();
1769 tree phi_result1 = gimple_phi_result (phi1);
1770 tree phi_result2 = gimple_phi_result (phi2);
1772 if (!m_checker->compare_operand (phi_result1, phi_result2))
1773 return return_false_with_msg ("PHI results are different");
1775 size1 = gimple_phi_num_args (phi1);
1776 size2 = gimple_phi_num_args (phi2);
1779 return return_false ();
1781 for (i = 0; i < size1; ++i)
1783 t1 = gimple_phi_arg (phi1, i)->def;
1784 t2 = gimple_phi_arg (phi2, i)->def;
1786 if (!m_checker->compare_operand (t1, t2))
1787 return return_false ();
1789 e1 = gimple_phi_arg_edge (phi1, i);
1790 e2 = gimple_phi_arg_edge (phi2, i);
1792 if (!m_checker->compare_edge (e1, e2))
1793 return return_false ();
1802 /* Returns true if tree T can be compared as a handled component. */
1805 sem_function::icf_handled_component_p (tree t)
1807 tree_code tc = TREE_CODE (t);
1809 return ((handled_component_p (t))
1810 || tc == ADDR_EXPR || tc == MEM_REF || tc == REALPART_EXPR
1811 || tc == IMAGPART_EXPR || tc == OBJ_TYPE_REF);
1814 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1815 corresponds to TARGET. */
1818 sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
1823 if (bb_dict->length () <= (unsigned)source)
1824 bb_dict->safe_grow_cleared (source + 1);
1826 if ((*bb_dict)[source] == 0)
1828 (*bb_dict)[source] = target;
1832 return (*bb_dict)[source] == target;
1836 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1838 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
1842 /* Constructor based on varpool node _NODE with computed hash _HASH.
1843 Bitmap STACK is used for memory allocation. */
1845 sem_variable::sem_variable (varpool_node *node, hashval_t _hash,
1846 bitmap_obstack *stack): sem_item(VAR,
1849 gcc_checking_assert (node);
1850 gcc_checking_assert (get_node ());
1853 /* Fast equality function based on knowledge known in WPA. */
1856 sem_variable::equals_wpa (sem_item *item,
1857 hash_map <symtab_node *, sem_item *> &ignored_nodes)
1859 gcc_assert (item->type == VAR);
1861 if (node->num_references () != item->node->num_references ())
1862 return return_false_with_msg ("different number of references");
1864 if (DECL_TLS_MODEL (decl) || DECL_TLS_MODEL (item->decl))
1865 return return_false_with_msg ("TLS model");
1867 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1868 alignment out of all aliases. */
1870 if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
1871 return return_false_with_msg ("Virtual flag mismatch");
1873 if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
1874 && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
1875 || !operand_equal_p (DECL_SIZE (decl),
1876 DECL_SIZE (item->decl), OEP_ONLY_CONST)))
1877 return return_false_with_msg ("size mismatch");
1879 /* Do not attempt to mix data from different user sections;
1880 we do not know what user intends with those. */
1881 if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
1882 || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
1883 && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
1884 return return_false_with_msg ("user section mismatch");
1886 if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
1887 return return_false_with_msg ("text section");
1889 ipa_ref *ref = NULL, *ref2 = NULL;
1890 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
1892 item->node->iterate_reference (i, ref2);
1894 if (ref->use != ref2->use)
1895 return return_false_with_msg ("reference use mismatch");
1897 if (!compare_symbol_references (ignored_nodes,
1898 ref->referred, ref2->referred,
1899 ref->address_matters_p ()))
1906 /* Returns true if the item equals to ITEM given as argument. */
1909 sem_variable::equals (sem_item *item,
1910 hash_map <symtab_node *, sem_item *> &)
1912 gcc_assert (item->type == VAR);
1915 if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
1916 dyn_cast <varpool_node *>(node)->get_constructor ();
1917 if (DECL_INITIAL (item->decl) == error_mark_node && in_lto_p)
1918 dyn_cast <varpool_node *>(item->node)->get_constructor ();
1920 /* As seen in PR ipa/65303 we have to compare variables types. */
1921 if (!func_checker::compatible_types_p (TREE_TYPE (decl),
1922 TREE_TYPE (item->decl)))
1923 return return_false_with_msg ("variables types are different");
1925 ret = sem_variable::equals (DECL_INITIAL (decl),
1926 DECL_INITIAL (item->node->decl));
1927 if (dump_file && (dump_flags & TDF_DETAILS))
1929 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1930 xstrdup_for_dump (node->name()),
1931 xstrdup_for_dump (item->node->name ()),
1932 node->order, item->node->order,
1933 xstrdup_for_dump (node->asm_name ()),
1934 xstrdup_for_dump (item->node->asm_name ()), ret ? "true" : "false");
1939 /* Compares trees T1 and T2 for semantic equality. */
1942 sem_variable::equals (tree t1, tree t2)
1945 return return_with_debug (t1 == t2);
1948 tree_code tc1 = TREE_CODE (t1);
1949 tree_code tc2 = TREE_CODE (t2);
1952 return return_false_with_msg ("TREE_CODE mismatch");
1958 vec<constructor_elt, va_gc> *v1, *v2;
1959 unsigned HOST_WIDE_INT idx;
1961 enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
1962 if (typecode != TREE_CODE (TREE_TYPE (t2)))
1963 return return_false_with_msg ("constructor type mismatch");
1965 if (typecode == ARRAY_TYPE)
1967 HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
1968 /* For arrays, check that the sizes all match. */
1969 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
1971 || size_1 != int_size_in_bytes (TREE_TYPE (t2)))
1972 return return_false_with_msg ("constructor array size mismatch");
1974 else if (!func_checker::compatible_types_p (TREE_TYPE (t1),
1976 return return_false_with_msg ("constructor type incompatible");
1978 v1 = CONSTRUCTOR_ELTS (t1);
1979 v2 = CONSTRUCTOR_ELTS (t2);
1980 if (vec_safe_length (v1) != vec_safe_length (v2))
1981 return return_false_with_msg ("constructor number of elts mismatch");
1983 for (idx = 0; idx < vec_safe_length (v1); ++idx)
1985 constructor_elt *c1 = &(*v1)[idx];
1986 constructor_elt *c2 = &(*v2)[idx];
1988 /* Check that each value is the same... */
1989 if (!sem_variable::equals (c1->value, c2->value))
1991 /* ... and that they apply to the same fields! */
1992 if (!sem_variable::equals (c1->index, c2->index))
1999 tree x1 = TREE_OPERAND (t1, 0);
2000 tree x2 = TREE_OPERAND (t2, 0);
2001 tree y1 = TREE_OPERAND (t1, 1);
2002 tree y2 = TREE_OPERAND (t2, 1);
2004 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
2005 return return_false ();
2007 /* Type of the offset on MEM_REF does not matter. */
2008 return return_with_debug (sem_variable::equals (x1, x2)
2009 && wi::to_offset (y1)
2010 == wi::to_offset (y2));
2015 tree op1 = TREE_OPERAND (t1, 0);
2016 tree op2 = TREE_OPERAND (t2, 0);
2017 return sem_variable::equals (op1, op2);
2019 /* References to other vars/decls are compared using ipa-ref. */
2022 if (decl_in_symtab_p (t1) && decl_in_symtab_p (t2))
2024 return return_false_with_msg ("Declaration mismatch");
2026 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
2027 need to process its VAR/FUNCTION references without relying on ipa-ref
2031 return return_false_with_msg ("Declaration mismatch");
2033 /* Integer constants are the same only if the same width of type. */
2034 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2035 return return_false_with_msg ("INTEGER_CST precision mismatch");
2036 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
2037 return return_false_with_msg ("INTEGER_CST mode mismatch");
2038 return return_with_debug (tree_int_cst_equal (t1, t2));
2040 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
2041 return return_false_with_msg ("STRING_CST mode mismatch");
2042 if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
2043 return return_false_with_msg ("STRING_CST length mismatch");
2044 if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
2045 TREE_STRING_LENGTH (t1)))
2046 return return_false_with_msg ("STRING_CST mismatch");
2049 /* Fixed constants are the same only if the same width of type. */
2050 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2051 return return_false_with_msg ("FIXED_CST precision mismatch");
2053 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
2054 TREE_FIXED_CST (t2)));
2056 return (sem_variable::equals (TREE_REALPART (t1), TREE_REALPART (t2))
2057 && sem_variable::equals (TREE_IMAGPART (t1), TREE_IMAGPART (t2)));
2059 /* Real constants are the same only if the same width of type. */
2060 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2061 return return_false_with_msg ("REAL_CST precision mismatch");
2062 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1),
2063 TREE_REAL_CST (t2)));
2068 if (VECTOR_CST_NELTS (t1) != VECTOR_CST_NELTS (t2))
2069 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2071 for (i = 0; i < VECTOR_CST_NELTS (t1); ++i)
2072 if (!sem_variable::equals (VECTOR_CST_ELT (t1, i),
2073 VECTOR_CST_ELT (t2, i)))
2079 case ARRAY_RANGE_REF:
2081 tree x1 = TREE_OPERAND (t1, 0);
2082 tree x2 = TREE_OPERAND (t2, 0);
2083 tree y1 = TREE_OPERAND (t1, 1);
2084 tree y2 = TREE_OPERAND (t2, 1);
2086 if (!sem_variable::equals (x1, x2) || !sem_variable::equals (y1, y2))
2088 if (!sem_variable::equals (array_ref_low_bound (t1),
2089 array_ref_low_bound (t2)))
2091 if (!sem_variable::equals (array_ref_element_size (t1),
2092 array_ref_element_size (t2)))
2098 case POINTER_PLUS_EXPR:
2103 tree x1 = TREE_OPERAND (t1, 0);
2104 tree x2 = TREE_OPERAND (t2, 0);
2105 tree y1 = TREE_OPERAND (t1, 1);
2106 tree y2 = TREE_OPERAND (t2, 1);
2108 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
2112 case VIEW_CONVERT_EXPR:
2113 if (!func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
2114 return return_false ();
2115 return sem_variable::equals (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
2117 return return_false_with_msg ("ERROR_MARK");
2119 return return_false_with_msg ("Unknown TREE code reached");
2123 /* Parser function that visits a varpool NODE. */
2126 sem_variable::parse (varpool_node *node, bitmap_obstack *stack)
2128 if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl)
2132 sem_variable *v = new sem_variable (node, 0, stack);
2139 /* References independent hash function. */
2142 sem_variable::get_hash (void)
2147 /* All WPA streamed in symbols should have their hashes computed at compile
2148 time. At this point, the constructor may not be in memory at all.
2149 DECL_INITIAL (decl) would be error_mark_node in that case. */
2150 gcc_assert (!node->lto_file_data);
2151 tree ctor = DECL_INITIAL (decl);
2152 inchash::hash hstate;
2154 hstate.add_int (456346417);
2155 if (DECL_SIZE (decl) && tree_fits_shwi_p (DECL_SIZE (decl)))
2156 hstate.add_wide_int (tree_to_shwi (DECL_SIZE (decl)));
2157 add_expr (ctor, hstate);
2158 hash = hstate.end ();
2163 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2167 sem_variable::merge (sem_item *alias_item)
2169 gcc_assert (alias_item->type == VAR);
2171 if (!sem_item::target_supports_symbol_aliases_p ())
2174 fprintf (dump_file, "Not unifying; "
2175 "Symbol aliases are not supported by target\n\n");
2179 if (DECL_EXTERNAL (alias_item->decl))
2182 fprintf (dump_file, "Not unifying; alias is external.\n\n");
2186 sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
2188 varpool_node *original = get_node ();
2189 varpool_node *alias = alias_var->get_node ();
2190 bool original_discardable = false;
2192 bool original_address_matters = original->address_matters_p ();
2193 bool alias_address_matters = alias->address_matters_p ();
2195 /* See if original is in a section that can be discarded if the main
2197 Also consider case where we have resolution info and we know that
2198 original's definition is not going to be used. In this case we can not
2199 create alias to original. */
2200 if (original->can_be_discarded_p ()
2201 || (node->resolution != LDPR_UNKNOWN
2202 && !decl_binds_to_current_def_p (node->decl)))
2203 original_discardable = true;
2205 gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
2207 /* Constant pool machinery is not quite ready for aliases.
2208 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2209 For LTO merging does not happen that is an important missing feature.
2210 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2211 flag is dropped and non-local symbol name is assigned. */
2212 if (DECL_IN_CONSTANT_POOL (alias->decl)
2213 || DECL_IN_CONSTANT_POOL (original->decl))
2217 "Not unifying; constant pool variables.\n\n");
2221 /* Do not attempt to mix functions from different user sections;
2222 we do not know what user intends with those. */
2223 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
2224 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
2225 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
2230 "original and alias are in different sections.\n\n");
2234 /* We can not merge if address comparsion metters. */
2235 if (original_address_matters && alias_address_matters
2236 && flag_merge_constants < 2)
2241 "adress of original and alias may be compared.\n\n");
2244 if (DECL_COMDAT_GROUP (original->decl) != DECL_COMDAT_GROUP (alias->decl))
2247 fprintf (dump_file, "Not unifying; alias cannot be created; "
2248 "across comdat group boundary\n\n");
2253 if (original_discardable)
2256 fprintf (dump_file, "Not unifying; alias cannot be created; "
2257 "target is discardable\n\n");
2263 gcc_assert (!original->alias);
2264 gcc_assert (!alias->alias);
2266 alias->analyzed = false;
2268 DECL_INITIAL (alias->decl) = NULL;
2269 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
2271 alias->need_bounds_init = false;
2272 alias->remove_all_references ();
2273 if (TREE_ADDRESSABLE (alias->decl))
2274 original->call_for_symbol_and_aliases (set_addressable, NULL, true);
2276 varpool_node::create_alias (alias_var->decl, decl);
2277 alias->resolve_alias (original);
2280 fprintf (dump_file, "Unified; Variable alias has been created.\n\n");
2286 /* Dump symbol to FILE. */
2289 sem_variable::dump_to_file (FILE *file)
2293 print_node (file, "", decl, 0);
2294 fprintf (file, "\n\n");
2297 unsigned int sem_item_optimizer::class_id = 0;
2299 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2300 m_classes_count (0), m_cgraph_node_hooks (NULL), m_varpool_node_hooks (NULL)
2303 bitmap_obstack_initialize (&m_bmstack);
2306 sem_item_optimizer::~sem_item_optimizer ()
2308 for (unsigned int i = 0; i < m_items.length (); i++)
2311 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2312 it != m_classes.end (); ++it)
2314 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2315 delete (*it)->classes[i];
2317 (*it)->classes.release ();
2323 bitmap_obstack_release (&m_bmstack);
2326 /* Write IPA ICF summary for symbols. */
2329 sem_item_optimizer::write_summary (void)
2331 unsigned int count = 0;
2333 output_block *ob = create_output_block (LTO_section_ipa_icf);
2334 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
2337 /* Calculate number of symbols to be serialized. */
2338 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2340 lsei_next_in_partition (&lsei))
2342 symtab_node *node = lsei_node (lsei);
2344 if (m_symtab_node_map.get (node))
2348 streamer_write_uhwi (ob, count);
2350 /* Process all of the symbols. */
2351 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2353 lsei_next_in_partition (&lsei))
2355 symtab_node *node = lsei_node (lsei);
2357 sem_item **item = m_symtab_node_map.get (node);
2361 int node_ref = lto_symtab_encoder_encode (encoder, node);
2362 streamer_write_uhwi_stream (ob->main_stream, node_ref);
2364 streamer_write_uhwi (ob, (*item)->get_hash ());
2368 streamer_write_char_stream (ob->main_stream, 0);
2369 produce_asm (ob, NULL);
2370 destroy_output_block (ob);
2373 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2374 contains LEN bytes. */
2377 sem_item_optimizer::read_section (lto_file_decl_data *file_data,
2378 const char *data, size_t len)
2380 const lto_function_header *header =
2381 (const lto_function_header *) data;
2382 const int cfg_offset = sizeof (lto_function_header);
2383 const int main_offset = cfg_offset + header->cfg_size;
2384 const int string_offset = main_offset + header->main_size;
2389 lto_input_block ib_main ((const char *) data + main_offset, 0,
2390 header->main_size, file_data->mode_table);
2393 lto_data_in_create (file_data, (const char *) data + string_offset,
2394 header->string_size, vNULL);
2396 count = streamer_read_uhwi (&ib_main);
2398 for (i = 0; i < count; i++)
2402 lto_symtab_encoder_t encoder;
2404 index = streamer_read_uhwi (&ib_main);
2405 encoder = file_data->symtab_node_encoder;
2406 node = lto_symtab_encoder_deref (encoder, index);
2408 hashval_t hash = streamer_read_uhwi (&ib_main);
2410 gcc_assert (node->definition);
2413 fprintf (dump_file, "Symbol added:%s (tree: %p, uid:%u)\n",
2414 node->asm_name (), (void *) node->decl, node->order);
2416 if (is_a<cgraph_node *> (node))
2418 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
2420 m_items.safe_push (new sem_function (cnode, hash, &m_bmstack));
2424 varpool_node *vnode = dyn_cast <varpool_node *> (node);
2426 m_items.safe_push (new sem_variable (vnode, hash, &m_bmstack));
2430 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
2432 lto_data_in_delete (data_in);
2435 /* Read IPA IPA ICF summary for symbols. */
2438 sem_item_optimizer::read_summary (void)
2440 lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2441 lto_file_decl_data *file_data;
2444 while ((file_data = file_data_vec[j++]))
2447 const char *data = lto_get_section_data (file_data,
2448 LTO_section_ipa_icf, NULL, &len);
2451 read_section (file_data, data, len);
2455 /* Register callgraph and varpool hooks. */
2458 sem_item_optimizer::register_hooks (void)
2460 if (!m_cgraph_node_hooks)
2461 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
2462 (&sem_item_optimizer::cgraph_removal_hook, this);
2464 if (!m_varpool_node_hooks)
2465 m_varpool_node_hooks = symtab->add_varpool_removal_hook
2466 (&sem_item_optimizer::varpool_removal_hook, this);
2469 /* Unregister callgraph and varpool hooks. */
2472 sem_item_optimizer::unregister_hooks (void)
2474 if (m_cgraph_node_hooks)
2475 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
2477 if (m_varpool_node_hooks)
2478 symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
2481 /* Adds a CLS to hashtable associated by hash value. */
2484 sem_item_optimizer::add_class (congruence_class *cls)
2486 gcc_assert (cls->members.length ());
2488 congruence_class_group *group = get_group_by_hash (
2489 cls->members[0]->get_hash (),
2490 cls->members[0]->type);
2491 group->classes.safe_push (cls);
2494 /* Gets a congruence class group based on given HASH value and TYPE. */
2496 congruence_class_group *
2497 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
2499 congruence_class_group *item = XNEW (congruence_class_group);
2503 congruence_class_group **slot = m_classes.find_slot (item, INSERT);
2509 item->classes.create (1);
2516 /* Callgraph removal hook called for a NODE with a custom DATA. */
2519 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
2521 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2522 optimizer->remove_symtab_node (node);
2525 /* Varpool removal hook called for a NODE with a custom DATA. */
2528 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
2530 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2531 optimizer->remove_symtab_node (node);
2534 /* Remove symtab NODE triggered by symtab removal hooks. */
2537 sem_item_optimizer::remove_symtab_node (symtab_node *node)
2539 gcc_assert (!m_classes.elements());
2541 m_removed_items_set.add (node);
2545 sem_item_optimizer::remove_item (sem_item *item)
2547 if (m_symtab_node_map.get (item->node))
2548 m_symtab_node_map.remove (item->node);
2552 /* Removes all callgraph and varpool nodes that are marked by symtab
2556 sem_item_optimizer::filter_removed_items (void)
2558 auto_vec <sem_item *> filtered;
2560 for (unsigned int i = 0; i < m_items.length(); i++)
2562 sem_item *item = m_items[i];
2564 if (m_removed_items_set.contains (item->node))
2570 if (item->type == FUNC)
2572 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
2574 if (in_lto_p && (cnode->alias || cnode->body_removed))
2577 filtered.safe_push (item);
2581 if (!flag_ipa_icf_variables)
2585 /* Filter out non-readonly variables. */
2586 tree decl = item->decl;
2587 if (TREE_READONLY (decl))
2588 filtered.safe_push (item);
2595 /* Clean-up of released semantic items. */
2598 for (unsigned int i = 0; i < filtered.length(); i++)
2599 m_items.safe_push (filtered[i]);
2602 /* Optimizer entry point which returns true in case it processes
2603 a merge operation. True is returned if there's a merge operation
2607 sem_item_optimizer::execute (void)
2609 filter_removed_items ();
2610 unregister_hooks ();
2613 update_hash_by_addr_refs ();
2614 build_hash_based_classes ();
2617 fprintf (dump_file, "Dump after hash based groups\n");
2618 dump_cong_classes ();
2620 for (unsigned int i = 0; i < m_items.length(); i++)
2621 m_items[i]->init_wpa ();
2623 subdivide_classes_by_equality (true);
2626 fprintf (dump_file, "Dump after WPA based types groups\n");
2628 dump_cong_classes ();
2630 process_cong_reduction ();
2634 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
2636 dump_cong_classes ();
2638 parse_nonsingleton_classes ();
2639 subdivide_classes_by_equality ();
2642 fprintf (dump_file, "Dump after full equality comparison of groups\n");
2644 dump_cong_classes ();
2646 unsigned int prev_class_count = m_classes_count;
2648 process_cong_reduction ();
2649 dump_cong_classes ();
2651 bool merged_p = merge_classes (prev_class_count);
2653 if (dump_file && (dump_flags & TDF_DETAILS))
2654 symtab_node::dump_table (dump_file);
2659 /* Function responsible for visiting all potential functions and
2660 read-only variables that can be merged. */
2663 sem_item_optimizer::parse_funcs_and_vars (void)
2667 if (flag_ipa_icf_functions)
2668 FOR_EACH_DEFINED_FUNCTION (cnode)
2670 sem_function *f = sem_function::parse (cnode, &m_bmstack);
2673 m_items.safe_push (f);
2674 m_symtab_node_map.put (cnode, f);
2677 fprintf (dump_file, "Parsed function:%s\n", f->node->asm_name ());
2679 if (dump_file && (dump_flags & TDF_DETAILS))
2680 f->dump_to_file (dump_file);
2683 fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
2686 varpool_node *vnode;
2688 if (flag_ipa_icf_variables)
2689 FOR_EACH_DEFINED_VARIABLE (vnode)
2691 sem_variable *v = sem_variable::parse (vnode, &m_bmstack);
2695 m_items.safe_push (v);
2696 m_symtab_node_map.put (vnode, v);
2701 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2704 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
2706 item->index_in_class = cls->members.length ();
2707 cls->members.safe_push (item);
2711 /* For each semantic item, append hash values of references. */
2714 sem_item_optimizer::update_hash_by_addr_refs ()
2716 /* First, append to hash sensitive references and class type if it need to
2717 be matched for ODR. */
2718 for (unsigned i = 0; i < m_items.length (); i++)
2720 m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
2721 if (m_items[i]->type == FUNC)
2723 if (TREE_CODE (TREE_TYPE (m_items[i]->decl)) == METHOD_TYPE
2724 && contains_polymorphic_type_p
2725 (method_class_type (TREE_TYPE (m_items[i]->decl)))
2726 && (DECL_CXX_CONSTRUCTOR_P (m_items[i]->decl)
2727 || (static_cast<sem_function *> (m_items[i])->param_used_p (0)
2728 && static_cast<sem_function *> (m_items[i])
2729 ->compare_polymorphic_p ())))
2732 = method_class_type (TREE_TYPE (m_items[i]->decl));
2733 inchash::hash hstate (m_items[i]->hash);
2735 if (TYPE_NAME (class_type)
2736 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type)))
2738 (IDENTIFIER_HASH_VALUE
2739 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type))));
2741 m_items[i]->hash = hstate.end ();
2746 /* Once all symbols have enhanced hash value, we can append
2747 hash values of symbols that are seen by IPA ICF and are
2748 references by a semantic item. Newly computed values
2749 are saved to global_hash member variable. */
2750 for (unsigned i = 0; i < m_items.length (); i++)
2751 m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
2753 /* Global hash value replace current hash values. */
2754 for (unsigned i = 0; i < m_items.length (); i++)
2755 m_items[i]->hash = m_items[i]->global_hash;
2758 /* Congruence classes are built by hash value. */
2761 sem_item_optimizer::build_hash_based_classes (void)
2763 for (unsigned i = 0; i < m_items.length (); i++)
2765 sem_item *item = m_items[i];
2767 congruence_class_group *group = get_group_by_hash (item->hash,
2770 if (!group->classes.length ())
2773 group->classes.safe_push (new congruence_class (class_id++));
2776 add_item_to_class (group->classes[0], item);
2780 /* Build references according to call graph. */
2783 sem_item_optimizer::build_graph (void)
2785 for (unsigned i = 0; i < m_items.length (); i++)
2787 sem_item *item = m_items[i];
2788 m_symtab_node_map.put (item->node, item);
2791 for (unsigned i = 0; i < m_items.length (); i++)
2793 sem_item *item = m_items[i];
2795 if (item->type == FUNC)
2797 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
2799 cgraph_edge *e = cnode->callees;
2802 sem_item **slot = m_symtab_node_map.get
2803 (e->callee->ultimate_alias_target ());
2805 item->add_reference (*slot);
2811 ipa_ref *ref = NULL;
2812 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
2814 sem_item **slot = m_symtab_node_map.get
2815 (ref->referred->ultimate_alias_target ());
2817 item->add_reference (*slot);
2822 /* Semantic items in classes having more than one element and initialized.
2823 In case of WPA, we load function body. */
2826 sem_item_optimizer::parse_nonsingleton_classes (void)
2828 unsigned int init_called_count = 0;
2830 for (unsigned i = 0; i < m_items.length (); i++)
2831 if (m_items[i]->cls->members.length () > 1)
2833 m_items[i]->init ();
2834 init_called_count++;
2838 fprintf (dump_file, "Init called for %u items (%.2f%%).\n", init_called_count,
2839 m_items.length () ? 100.0f * init_called_count / m_items.length (): 0.0f);
2842 /* Equality function for semantic items is used to subdivide existing
2843 classes. If IN_WPA, fast equality function is invoked. */
2846 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
2848 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2849 it != m_classes.end (); ++it)
2851 unsigned int class_count = (*it)->classes.length ();
2853 for (unsigned i = 0; i < class_count; i++)
2855 congruence_class *c = (*it)->classes [i];
2857 if (c->members.length() > 1)
2859 auto_vec <sem_item *> new_vector;
2861 sem_item *first = c->members[0];
2862 new_vector.safe_push (first);
2864 unsigned class_split_first = (*it)->classes.length ();
2866 for (unsigned j = 1; j < c->members.length (); j++)
2868 sem_item *item = c->members[j];
2870 bool equals = in_wpa ? first->equals_wpa (item,
2871 m_symtab_node_map) : first->equals (item, m_symtab_node_map);
2874 new_vector.safe_push (item);
2877 bool integrated = false;
2879 for (unsigned k = class_split_first; k < (*it)->classes.length (); k++)
2881 sem_item *x = (*it)->classes[k]->members[0];
2882 bool equals = in_wpa ? x->equals_wpa (item,
2883 m_symtab_node_map) : x->equals (item, m_symtab_node_map);
2888 add_item_to_class ((*it)->classes[k], item);
2896 congruence_class *c = new congruence_class (class_id++);
2898 add_item_to_class (c, item);
2900 (*it)->classes.safe_push (c);
2905 // we replace newly created new_vector for the class we've just splitted
2906 c->members.release ();
2907 c->members.create (new_vector.length ());
2909 for (unsigned int j = 0; j < new_vector.length (); j++)
2910 add_item_to_class (c, new_vector[j]);
2918 /* Subdivide classes by address references that members of the class
2919 reference. Example can be a pair of functions that have an address
2920 taken from a function. If these addresses are different the class
2924 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2926 typedef hash_map <symbol_compare_collection *, vec <sem_item *>,
2927 symbol_compare_hashmap_traits> subdivide_hash_map;
2929 unsigned newly_created_classes = 0;
2931 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2932 it != m_classes.end (); ++it)
2934 unsigned int class_count = (*it)->classes.length ();
2935 auto_vec<congruence_class *> new_classes;
2937 for (unsigned i = 0; i < class_count; i++)
2939 congruence_class *c = (*it)->classes [i];
2941 if (c->members.length() > 1)
2943 subdivide_hash_map split_map;
2945 for (unsigned j = 0; j < c->members.length (); j++)
2947 sem_item *source_node = c->members[j];
2949 symbol_compare_collection *collection = new symbol_compare_collection (source_node->node);
2952 vec <sem_item *> *slot = &split_map.get_or_insert (collection,
2954 gcc_checking_assert (slot);
2956 slot->safe_push (source_node);
2962 /* If the map contains more than one key, we have to split the map
2964 if (split_map.elements () != 1)
2966 bool first_class = true;
2968 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2969 it2 != split_map.end (); ++it2)
2971 congruence_class *new_cls;
2972 new_cls = new congruence_class (class_id++);
2974 for (unsigned k = 0; k < (*it2).second.length (); k++)
2975 add_item_to_class (new_cls, (*it2).second[k]);
2977 worklist_push (new_cls);
2978 newly_created_classes++;
2982 (*it)->classes[i] = new_cls;
2983 first_class = false;
2987 new_classes.safe_push (new_cls);
2993 /* Release memory. */
2994 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2995 it2 != split_map.end (); ++it2)
2997 delete (*it2).first;
2998 (*it2).second.release ();
3003 for (unsigned i = 0; i < new_classes.length (); i++)
3004 (*it)->classes.safe_push (new_classes[i]);
3007 return newly_created_classes;
3010 /* Verify congruence classes if checking is enabled. */
3013 sem_item_optimizer::verify_classes (void)
3016 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
3017 it != m_classes.end (); ++it)
3019 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3021 congruence_class *cls = (*it)->classes[i];
3023 gcc_checking_assert (cls);
3024 gcc_checking_assert (cls->members.length () > 0);
3026 for (unsigned int j = 0; j < cls->members.length (); j++)
3028 sem_item *item = cls->members[j];
3030 gcc_checking_assert (item);
3031 gcc_checking_assert (item->cls == cls);
3033 for (unsigned k = 0; k < item->usages.length (); k++)
3035 sem_usage_pair *usage = item->usages[k];
3036 gcc_checking_assert (usage->item->index_in_class <
3037 usage->item->cls->members.length ());
3045 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3046 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3047 but unused argument. */
3050 sem_item_optimizer::release_split_map (congruence_class * const &,
3051 bitmap const &b, traverse_split_pair *)
3060 /* Process split operation for a class given as pointer CLS_PTR,
3061 where bitmap B splits congruence class members. DATA is used
3062 as argument of split pair. */
3065 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
3066 bitmap const &b, traverse_split_pair *pair)
3068 sem_item_optimizer *optimizer = pair->optimizer;
3069 const congruence_class *splitter_cls = pair->cls;
3071 /* If counted bits are greater than zero and less than the number of members
3072 a group will be splitted. */
3073 unsigned popcount = bitmap_count_bits (b);
3075 if (popcount > 0 && popcount < cls->members.length ())
3077 congruence_class* newclasses[2] = { new congruence_class (class_id++), new congruence_class (class_id++) };
3079 for (unsigned int i = 0; i < cls->members.length (); i++)
3081 int target = bitmap_bit_p (b, i);
3082 congruence_class *tc = newclasses[target];
3084 add_item_to_class (tc, cls->members[i]);
3087 #ifdef ENABLE_CHECKING
3088 for (unsigned int i = 0; i < 2; i++)
3089 gcc_checking_assert (newclasses[i]->members.length ());
3092 if (splitter_cls == cls)
3093 optimizer->splitter_class_removed = true;
3095 /* Remove old class from worklist if presented. */
3096 bool in_worklist = cls->in_worklist;
3099 cls->in_worklist = false;
3101 congruence_class_group g;
3102 g.hash = cls->members[0]->get_hash ();
3103 g.type = cls->members[0]->type;
3105 congruence_class_group *slot = optimizer->m_classes.find(&g);
3107 for (unsigned int i = 0; i < slot->classes.length (); i++)
3108 if (slot->classes[i] == cls)
3110 slot->classes.ordered_remove (i);
3114 /* New class will be inserted and integrated to work list. */
3115 for (unsigned int i = 0; i < 2; i++)
3116 optimizer->add_class (newclasses[i]);
3118 /* Two classes replace one, so that increment just by one. */
3119 optimizer->m_classes_count++;
3121 /* If OLD class was presented in the worklist, we remove the class
3122 and replace it will both newly created classes. */
3124 for (unsigned int i = 0; i < 2; i++)
3125 optimizer->worklist_push (newclasses[i]);
3126 else /* Just smaller class is inserted. */
3128 unsigned int smaller_index = newclasses[0]->members.length () <
3129 newclasses[1]->members.length () ?
3131 optimizer->worklist_push (newclasses[smaller_index]);
3134 if (dump_file && (dump_flags & TDF_DETAILS))
3136 fprintf (dump_file, " congruence class splitted:\n");
3137 cls->dump (dump_file, 4);
3139 fprintf (dump_file, " newly created groups:\n");
3140 for (unsigned int i = 0; i < 2; i++)
3141 newclasses[i]->dump (dump_file, 4);
3144 /* Release class if not presented in work list. */
3153 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3154 Bitmap stack BMSTACK is used for bitmap allocation. */
3157 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
3160 hash_map <congruence_class *, bitmap> split_map;
3162 for (unsigned int i = 0; i < cls->members.length (); i++)
3164 sem_item *item = cls->members[i];
3166 /* Iterate all usages that have INDEX as usage of the item. */
3167 for (unsigned int j = 0; j < item->usages.length (); j++)
3169 sem_usage_pair *usage = item->usages[j];
3171 if (usage->index != index)
3174 bitmap *slot = split_map.get (usage->item->cls);
3179 b = BITMAP_ALLOC (&m_bmstack);
3180 split_map.put (usage->item->cls, b);
3186 gcc_checking_assert (usage->item->cls);
3187 gcc_checking_assert (usage->item->index_in_class <
3188 usage->item->cls->members.length ());
3191 bitmap_set_bit (b, usage->item->index_in_class);
3195 traverse_split_pair pair;
3196 pair.optimizer = this;
3199 splitter_class_removed = false;
3201 <traverse_split_pair *, sem_item_optimizer::traverse_congruence_split> (&pair);
3203 /* Bitmap clean-up. */
3205 <traverse_split_pair *, sem_item_optimizer::release_split_map> (NULL);
3208 /* Every usage of a congruence class CLS is a candidate that can split the
3209 collection of classes. Bitmap stack BMSTACK is used for bitmap
3213 sem_item_optimizer::do_congruence_step (congruence_class *cls)
3218 bitmap usage = BITMAP_ALLOC (&m_bmstack);
3220 for (unsigned int i = 0; i < cls->members.length (); i++)
3221 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
3223 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
3225 if (dump_file && (dump_flags & TDF_DETAILS))
3226 fprintf (dump_file, " processing congruece step for class: %u, index: %u\n",
3229 do_congruence_step_for_index (cls, i);
3231 if (splitter_class_removed)
3235 BITMAP_FREE (usage);
3238 /* Adds a newly created congruence class CLS to worklist. */
3241 sem_item_optimizer::worklist_push (congruence_class *cls)
3243 /* Return if the class CLS is already presented in work list. */
3244 if (cls->in_worklist)
3247 cls->in_worklist = true;
3248 worklist.push_back (cls);
3251 /* Pops a class from worklist. */
3254 sem_item_optimizer::worklist_pop (void)
3256 congruence_class *cls;
3258 while (!worklist.empty ())
3260 cls = worklist.front ();
3261 worklist.pop_front ();
3262 if (cls->in_worklist)
3264 cls->in_worklist = false;
3270 /* Work list item was already intended to be removed.
3271 The only reason for doing it is to split a class.
3272 Thus, the class CLS is deleted. */
3280 /* Iterative congruence reduction function. */
3283 sem_item_optimizer::process_cong_reduction (void)
3285 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3286 it != m_classes.end (); ++it)
3287 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3288 if ((*it)->classes[i]->is_class_used ())
3289 worklist_push ((*it)->classes[i]);
3292 fprintf (dump_file, "Worklist has been filled with: %lu\n",
3293 (unsigned long) worklist.size ());
3295 if (dump_file && (dump_flags & TDF_DETAILS))
3296 fprintf (dump_file, "Congruence class reduction\n");
3298 congruence_class *cls;
3300 /* Process complete congruence reduction. */
3301 while ((cls = worklist_pop ()) != NULL)
3302 do_congruence_step (cls);
3304 /* Subdivide newly created classes according to references. */
3305 unsigned new_classes = subdivide_classes_by_sensitive_refs ();
3308 fprintf (dump_file, "Address reference subdivision created: %u "
3309 "new classes.\n", new_classes);
3312 /* Debug function prints all informations about congruence classes. */
3315 sem_item_optimizer::dump_cong_classes (void)
3321 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3322 m_classes_count, (unsigned long) m_classes.elements(), m_items.length ());
3324 /* Histogram calculation. */
3325 unsigned int max_index = 0;
3326 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
3328 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3329 it != m_classes.end (); ++it)
3331 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3333 unsigned int c = (*it)->classes[i]->members.length ();
3341 "Class size histogram [num of members]: number of classe number of classess\n");
3343 for (unsigned int i = 0; i <= max_index; i++)
3345 fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
3347 fprintf (dump_file, "\n\n");
3350 if (dump_flags & TDF_DETAILS)
3351 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3352 it != m_classes.end (); ++it)
3354 fprintf (dump_file, " group: with %u classes:\n", (*it)->classes.length ());
3356 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3358 (*it)->classes[i]->dump (dump_file, 4);
3360 if(i < (*it)->classes.length () - 1)
3361 fprintf (dump_file, " ");
3368 /* After reduction is done, we can declare all items in a group
3369 to be equal. PREV_CLASS_COUNT is start number of classes
3370 before reduction. True is returned if there's a merge operation
3374 sem_item_optimizer::merge_classes (unsigned int prev_class_count)
3376 unsigned int item_count = m_items.length ();
3377 unsigned int class_count = m_classes_count;
3378 unsigned int equal_items = item_count - class_count;
3380 unsigned int non_singular_classes_count = 0;
3381 unsigned int non_singular_classes_sum = 0;
3383 bool merged_p = false;
3385 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3386 it != m_classes.end (); ++it)
3387 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3389 congruence_class *c = (*it)->classes[i];
3390 if (c->members.length () > 1)
3392 non_singular_classes_count++;
3393 non_singular_classes_sum += c->members.length ();
3399 fprintf (dump_file, "\nItem count: %u\n", item_count);
3400 fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
3401 prev_class_count, class_count);
3402 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
3403 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
3404 class_count ? 1.0f * item_count / class_count : 0.0f);
3405 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
3406 non_singular_classes_count ? 1.0f * non_singular_classes_sum /
3407 non_singular_classes_count : 0.0f,
3408 non_singular_classes_count);
3409 fprintf (dump_file, "Equal symbols: %u\n", equal_items);
3410 fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
3411 item_count ? 100.0f * equal_items / item_count : 0.0f);
3414 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3415 it != m_classes.end (); ++it)
3416 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3418 congruence_class *c = (*it)->classes[i];
3420 if (c->members.length () == 1)
3423 gcc_assert (c->members.length ());
3425 sem_item *source = c->members[0];
3427 for (unsigned int j = 1; j < c->members.length (); j++)
3429 sem_item *alias = c->members[j];
3433 fprintf (dump_file, "Semantic equality hit:%s->%s\n",
3434 xstrdup_for_dump (source->node->name ()),
3435 xstrdup_for_dump (alias->node->name ()));
3436 fprintf (dump_file, "Assembler symbol names:%s->%s\n",
3437 xstrdup_for_dump (source->node->asm_name ()),
3438 xstrdup_for_dump (alias->node->asm_name ()));
3441 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl)))
3445 "Merge operation is skipped due to no_icf "
3451 if (dump_file && (dump_flags & TDF_DETAILS))
3453 source->dump_to_file (dump_file);
3454 alias->dump_to_file (dump_file);
3457 merged_p |= source->merge (alias);
3464 /* Dump function prints all class members to a FILE with an INDENT. */
3467 congruence_class::dump (FILE *file, unsigned int indent) const
3469 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
3470 id, members[0]->get_hash (), members.length ());
3472 FPUTS_SPACES (file, indent + 2, "");
3473 for (unsigned i = 0; i < members.length (); i++)
3474 fprintf (file, "%s(%p/%u) ", members[i]->node->asm_name (),
3475 (void *) members[i]->decl,
3476 members[i]->node->order);
3478 fprintf (file, "\n");
3481 /* Returns true if there's a member that is used from another group. */
3484 congruence_class::is_class_used (void)
3486 for (unsigned int i = 0; i < members.length (); i++)
3487 if (members[i]->usages.length ())
3493 /* Generate pass summary for IPA ICF pass. */
3496 ipa_icf_generate_summary (void)
3499 optimizer = new sem_item_optimizer ();
3501 optimizer->register_hooks ();
3502 optimizer->parse_funcs_and_vars ();
3505 /* Write pass summary for IPA ICF pass. */
3508 ipa_icf_write_summary (void)
3510 gcc_assert (optimizer);
3512 optimizer->write_summary ();
3515 /* Read pass summary for IPA ICF pass. */
3518 ipa_icf_read_summary (void)
3521 optimizer = new sem_item_optimizer ();
3523 optimizer->read_summary ();
3524 optimizer->register_hooks ();
3527 /* Semantic equality exection function. */
3530 ipa_icf_driver (void)
3532 gcc_assert (optimizer);
3534 bool merged_p = optimizer->execute ();
3539 return merged_p ? TODO_remove_functions : 0;
3542 const pass_data pass_data_ipa_icf =
3544 IPA_PASS, /* type */
3546 OPTGROUP_IPA, /* optinfo_flags */
3547 TV_IPA_ICF, /* tv_id */
3548 0, /* properties_required */
3549 0, /* properties_provided */
3550 0, /* properties_destroyed */
3551 0, /* todo_flags_start */
3552 0, /* todo_flags_finish */
3555 class pass_ipa_icf : public ipa_opt_pass_d
3558 pass_ipa_icf (gcc::context *ctxt)
3559 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
3560 ipa_icf_generate_summary, /* generate_summary */
3561 ipa_icf_write_summary, /* write_summary */
3562 ipa_icf_read_summary, /* read_summary */
3564 write_optimization_summary */
3566 read_optimization_summary */
3567 NULL, /* stmt_fixup */
3568 0, /* function_transform_todo_flags_start */
3569 NULL, /* function_transform */
3570 NULL) /* variable_transform */
3573 /* opt_pass methods: */
3574 virtual bool gate (function *)
3576 return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
3579 virtual unsigned int execute (function *)
3581 return ipa_icf_driver();
3583 }; // class pass_ipa_icf
3585 } // ipa_icf namespace
3588 make_pass_ipa_icf (gcc::context *ctxt)
3590 return new ipa_icf::pass_ipa_icf (ctxt);