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;
133 symbol_compare_collection::symbol_compare_collection (symtab_node *node)
135 m_references.create (0);
136 m_interposables.create (0);
140 if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
143 for (unsigned i = 0; i < node->num_references (); i++)
145 ref = node->iterate_reference (i, ref);
146 if (ref->address_matters_p ())
147 m_references.safe_push (ref->referred);
149 if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE)
151 if (ref->address_matters_p ())
152 m_references.safe_push (ref->referred);
154 m_interposables.safe_push (ref->referred);
158 if (is_a <cgraph_node *> (node))
160 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
162 for (cgraph_edge *e = cnode->callees; e; e = e->next_callee)
163 if (e->callee->get_availability () <= AVAIL_INTERPOSABLE)
164 m_interposables.safe_push (e->callee);
168 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
170 sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index):
171 item (_item), index (_index)
175 /* Semantic item constructor for a node of _TYPE, where STACK is used
176 for bitmap memory allocation. */
178 sem_item::sem_item (sem_item_type _type,
179 bitmap_obstack *stack): type(_type), hash(0)
184 /* Semantic item constructor for a node of _TYPE, where STACK is used
185 for bitmap memory allocation. The item is based on symtab node _NODE
186 with computed _HASH. */
188 sem_item::sem_item (sem_item_type _type, symtab_node *_node,
189 hashval_t _hash, bitmap_obstack *stack): type(_type),
190 node (_node), hash (_hash)
196 /* Add reference to a semantic TARGET. */
199 sem_item::add_reference (sem_item *target)
201 refs.safe_push (target);
202 unsigned index = refs.length ();
203 target->usages.safe_push (new sem_usage_pair(this, index));
204 bitmap_set_bit (target->usage_index_bitmap, index);
205 refs_set.add (target->node);
208 /* Initialize internal data structures. Bitmap STACK is used for
209 bitmap memory allocation process. */
212 sem_item::setup (bitmap_obstack *stack)
214 gcc_checking_assert (node);
217 tree_refs.create (0);
219 usage_index_bitmap = BITMAP_ALLOC (stack);
222 sem_item::~sem_item ()
224 for (unsigned i = 0; i < usages.length (); i++)
228 tree_refs.release ();
231 BITMAP_FREE (usage_index_bitmap);
234 /* Dump function for debugging purpose. */
237 sem_item::dump (void)
241 fprintf (dump_file, "[%s] %s (%u) (tree:%p)\n", type == FUNC ? "func" : "var",
242 name(), node->order, (void *) node->decl);
243 fprintf (dump_file, " hash: %u\n", get_hash ());
244 fprintf (dump_file, " references: ");
246 for (unsigned i = 0; i < refs.length (); i++)
247 fprintf (dump_file, "%s%s ", refs[i]->name (),
248 i < refs.length() - 1 ? "," : "");
250 fprintf (dump_file, "\n");
254 /* Return true if target supports alias symbols. */
257 sem_item::target_supports_symbol_aliases_p (void)
259 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
266 /* Semantic function constructor that uses STACK as bitmap memory stack. */
268 sem_function::sem_function (bitmap_obstack *stack): sem_item (FUNC, stack),
269 m_checker (NULL), m_compared_func (NULL)
271 arg_types.create (0);
273 bb_sorted.create (0);
276 /* Constructor based on callgraph node _NODE with computed hash _HASH.
277 Bitmap STACK is used for memory allocation. */
278 sem_function::sem_function (cgraph_node *node, hashval_t hash,
279 bitmap_obstack *stack):
280 sem_item (FUNC, node, hash, stack),
281 m_checker (NULL), m_compared_func (NULL)
283 arg_types.create (0);
285 bb_sorted.create (0);
288 sem_function::~sem_function ()
290 for (unsigned i = 0; i < bb_sorted.length (); i++)
291 delete (bb_sorted[i]);
293 arg_types.release ();
295 bb_sorted.release ();
298 /* Calculates hash value based on a BASIC_BLOCK. */
301 sem_function::get_bb_hash (const sem_bb *basic_block)
303 inchash::hash hstate;
305 hstate.add_int (basic_block->nondbg_stmt_count);
306 hstate.add_int (basic_block->edge_count);
308 return hstate.end ();
311 /* References independent hash function. */
314 sem_function::get_hash (void)
318 inchash::hash hstate;
319 hstate.add_int (177454); /* Random number for function type. */
321 hstate.add_int (arg_count);
322 hstate.add_int (cfg_checksum);
323 hstate.add_int (gcode_hash);
325 for (unsigned i = 0; i < bb_sorted.length (); i++)
326 hstate.merge_hash (get_bb_hash (bb_sorted[i]));
328 for (unsigned i = 0; i < bb_sizes.length (); i++)
329 hstate.add_int (bb_sizes[i]);
331 hash = hstate.end ();
337 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
338 point to a same function. Comparison can be skipped if IGNORED_NODES
339 contains these nodes. ADDRESS indicate if address is taken. */
342 sem_item::compare_cgraph_references (
343 hash_map <symtab_node *, sem_item *> &ignored_nodes,
344 symtab_node *n1, symtab_node *n2, bool address)
346 enum availability avail1, avail2;
348 if (address && n1->equal_address_to (n2) == 1)
350 if (!address && n1->semantically_equivalent_p (n2))
353 n1 = n1->ultimate_alias_target (&avail1);
354 n2 = n2->ultimate_alias_target (&avail2);
356 if (avail1 >= AVAIL_INTERPOSABLE && ignored_nodes.get (n1)
357 && avail2 >= AVAIL_INTERPOSABLE && ignored_nodes.get (n2))
360 return return_false_with_msg ("different references");
363 /* If cgraph edges E1 and E2 are indirect calls, verify that
364 ECF flags are the same. */
366 bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
368 if (e1->indirect_info && e2->indirect_info)
370 int e1_flags = e1->indirect_info->ecf_flags;
371 int e2_flags = e2->indirect_info->ecf_flags;
373 if (e1_flags != e2_flags)
374 return return_false_with_msg ("ICF flags are different");
376 else if (e1->indirect_info || e2->indirect_info)
382 /* Fast equality function based on knowledge known in WPA. */
385 sem_function::equals_wpa (sem_item *item,
386 hash_map <symtab_node *, sem_item *> &ignored_nodes)
388 gcc_assert (item->type == FUNC);
390 m_compared_func = static_cast<sem_function *> (item);
392 if (arg_types.length () != m_compared_func->arg_types.length ())
393 return return_false_with_msg ("different number of arguments");
395 /* Checking types of arguments. */
396 for (unsigned i = 0; i < arg_types.length (); i++)
398 /* This guard is here for function pointer with attributes (pr59927.c). */
399 if (!arg_types[i] || !m_compared_func->arg_types[i])
400 return return_false_with_msg ("NULL argument type");
402 /* Polymorphic comparison is executed just for non-leaf functions. */
403 bool is_not_leaf = get_node ()->callees != NULL
404 || get_node ()->indirect_calls != NULL;
406 if (!func_checker::compatible_types_p (arg_types[i],
407 m_compared_func->arg_types[i],
408 is_not_leaf, i == 0))
409 return return_false_with_msg ("argument type is different");
412 /* Result type checking. */
413 if (!func_checker::compatible_types_p (result_type,
414 m_compared_func->result_type))
415 return return_false_with_msg ("result types are different");
417 if (node->num_references () != item->node->num_references ())
418 return return_false_with_msg ("different number of references");
420 ipa_ref *ref = NULL, *ref2 = NULL;
421 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
423 item->node->iterate_reference (i, ref2);
425 if (!compare_cgraph_references (ignored_nodes, ref->referred,
427 ref->address_matters_p ()))
431 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
432 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
436 if (!compare_cgraph_references (ignored_nodes, e1->callee,
440 e1 = e1->next_callee;
441 e2 = e2->next_callee;
445 return return_false_with_msg ("different number of edges");
450 /* Returns true if the item equals to ITEM given as argument. */
453 sem_function::equals (sem_item *item,
454 hash_map <symtab_node *, sem_item *> &ignored_nodes)
456 gcc_assert (item->type == FUNC);
457 bool eq = equals_private (item, ignored_nodes);
459 if (m_checker != NULL)
465 if (dump_file && (dump_flags & TDF_DETAILS))
467 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
468 name(), item->name (), node->order, item->node->order, asm_name (),
469 item->asm_name (), eq ? "true" : "false");
474 /* Processes function equality comparison. */
477 sem_function::equals_private (sem_item *item,
478 hash_map <symtab_node *, sem_item *> &ignored_nodes)
480 if (item->type != FUNC)
483 basic_block bb1, bb2;
485 edge_iterator ei1, ei2;
489 m_compared_func = static_cast<sem_function *> (item);
491 gcc_assert (decl != item->decl);
493 if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
494 || edge_count != m_compared_func->edge_count
495 || cfg_checksum != m_compared_func->cfg_checksum)
496 return return_false ();
498 if (!equals_wpa (item, ignored_nodes))
501 /* Checking function TARGET and OPTIMIZATION flags. */
502 cl_target_option *tar1 = target_opts_for_fn (decl);
503 cl_target_option *tar2 = target_opts_for_fn (m_compared_func->decl);
505 if (tar1 != NULL && tar2 != NULL)
507 if (!cl_target_option_eq (tar1, tar2))
509 if (dump_file && (dump_flags & TDF_DETAILS))
511 fprintf (dump_file, "target flags difference");
512 cl_target_option_print_diff (dump_file, 2, tar1, tar2);
515 return return_false_with_msg ("Target flags are different");
518 else if (tar1 != NULL || tar2 != NULL)
519 return return_false_with_msg ("Target flags are different");
521 cl_optimization *opt1 = opts_for_fn (decl);
522 cl_optimization *opt2 = opts_for_fn (m_compared_func->decl);
524 if (opt1 != NULL && opt2 != NULL)
526 if (memcmp (opt1, opt2, sizeof(cl_optimization)))
528 if (dump_file && (dump_flags & TDF_DETAILS))
530 fprintf (dump_file, "optimization flags difference");
531 cl_optimization_print_diff (dump_file, 2, opt1, opt2);
534 return return_false_with_msg ("optimization flags are different");
537 else if (opt1 != NULL || opt2 != NULL)
538 return return_false_with_msg ("optimization flags are different");
540 /* Checking function arguments. */
541 tree decl1 = DECL_ATTRIBUTES (decl);
542 tree decl2 = DECL_ATTRIBUTES (m_compared_func->decl);
544 m_checker = new func_checker (decl, m_compared_func->decl,
545 compare_polymorphic_p (),
548 &m_compared_func->refs_set);
552 return return_false ();
554 if (get_attribute_name (decl1) != get_attribute_name (decl2))
555 return return_false ();
557 tree attr_value1 = TREE_VALUE (decl1);
558 tree attr_value2 = TREE_VALUE (decl2);
560 if (attr_value1 && attr_value2)
562 bool ret = m_checker->compare_operand (TREE_VALUE (attr_value1),
563 TREE_VALUE (attr_value2));
565 return return_false_with_msg ("attribute values are different");
567 else if (!attr_value1 && !attr_value2)
570 return return_false ();
572 decl1 = TREE_CHAIN (decl1);
573 decl2 = TREE_CHAIN (decl2);
577 return return_false();
580 for (arg1 = DECL_ARGUMENTS (decl),
581 arg2 = DECL_ARGUMENTS (m_compared_func->decl);
582 arg1; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2))
583 if (!m_checker->compare_decl (arg1, arg2))
584 return return_false ();
586 /* Fill-up label dictionary. */
587 for (unsigned i = 0; i < bb_sorted.length (); ++i)
589 m_checker->parse_labels (bb_sorted[i]);
590 m_checker->parse_labels (m_compared_func->bb_sorted[i]);
593 /* Checking all basic blocks. */
594 for (unsigned i = 0; i < bb_sorted.length (); ++i)
595 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
596 return return_false();
598 dump_message ("All BBs are equal\n");
600 auto_vec <int> bb_dict;
602 /* Basic block edges check. */
603 for (unsigned i = 0; i < bb_sorted.length (); ++i)
605 bb1 = bb_sorted[i]->bb;
606 bb2 = m_compared_func->bb_sorted[i]->bb;
608 ei2 = ei_start (bb2->preds);
610 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
614 if (e1->flags != e2->flags)
615 return return_false_with_msg ("flags comparison returns false");
617 if (!bb_dict_test (&bb_dict, e1->src->index, e2->src->index))
618 return return_false_with_msg ("edge comparison returns false");
620 if (!bb_dict_test (&bb_dict, e1->dest->index, e2->dest->index))
621 return return_false_with_msg ("BB comparison returns false");
623 if (!m_checker->compare_edge (e1, e2))
624 return return_false_with_msg ("edge comparison returns false");
630 /* Basic block PHI nodes comparison. */
631 for (unsigned i = 0; i < bb_sorted.length (); i++)
632 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
633 return return_false_with_msg ("PHI node comparison returns false");
635 /* Compare special function DECL attributes. */
636 if (DECL_FUNCTION_PERSONALITY (decl) != DECL_FUNCTION_PERSONALITY (item->decl))
637 return return_false_with_msg ("function personalities are different");
639 if (DECL_DISREGARD_INLINE_LIMITS (decl) != DECL_DISREGARD_INLINE_LIMITS (item->decl))
640 return return_false_with_msg ("DECL_DISREGARD_INLINE_LIMITS are different");
642 if (DECL_DECLARED_INLINE_P (decl) != DECL_DECLARED_INLINE_P (item->decl))
643 return return_false_with_msg ("inline attributes are different");
645 if (DECL_IS_OPERATOR_NEW (decl) != DECL_IS_OPERATOR_NEW (item->decl))
646 return return_false_with_msg ("operator new flags are different");
648 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
649 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item->decl))
650 return return_false_with_msg ("intrument function entry exit "
651 "attributes are different");
653 if (DECL_NO_LIMIT_STACK (decl) != DECL_NO_LIMIT_STACK (item->decl))
654 return return_false_with_msg ("no stack limit attributes are different");
656 if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
657 return return_false_with_msg ("decl_or_type flags are different");
662 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
663 Helper for call_for_symbol_thunks_and_aliases. */
666 set_local (cgraph_node *node, void *data)
668 node->local.local = data != NULL;
672 /* TREE_ADDRESSABLE of NODE to true.
673 Helper for call_for_symbol_thunks_and_aliases. */
676 set_addressable (varpool_node *node, void *)
678 TREE_ADDRESSABLE (node->decl) = 1;
682 /* Clear DECL_RTL of NODE.
683 Helper for call_for_symbol_thunks_and_aliases. */
686 clear_decl_rtl (symtab_node *node, void *)
688 SET_DECL_RTL (node->decl, NULL);
692 /* Redirect all callers of N and its aliases to TO. Remove aliases if
693 possible. Return number of redirections made. */
696 redirect_all_callers (cgraph_node *n, cgraph_node *to)
700 cgraph_edge *e = n->callers;
704 /* Redirecting thunks to interposable symbols or symbols in other sections
705 may not be supported by target output code. Play safe for now and
706 punt on redirection. */
707 if (!e->caller->thunk.thunk_p)
709 struct cgraph_edge *nexte = e->next_caller;
710 e->redirect_callee (to);
717 for (unsigned i = 0; n->iterate_direct_aliases (i, ref);)
719 bool removed = false;
720 cgraph_node *n_alias = dyn_cast <cgraph_node *> (ref->referring);
722 if ((DECL_COMDAT_GROUP (n->decl)
723 && (DECL_COMDAT_GROUP (n->decl)
724 == DECL_COMDAT_GROUP (n_alias->decl)))
725 || (n_alias->get_availability () > AVAIL_INTERPOSABLE
726 && n->get_availability () > AVAIL_INTERPOSABLE))
728 nredirected += redirect_all_callers (n_alias, to);
729 if (n_alias->can_remove_if_no_direct_calls_p ()
730 && !n_alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
732 && !n_alias->has_aliases_p ())
741 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
745 sem_function::merge (sem_item *alias_item)
747 gcc_assert (alias_item->type == FUNC);
749 sem_function *alias_func = static_cast<sem_function *> (alias_item);
751 cgraph_node *original = get_node ();
752 cgraph_node *local_original = NULL;
753 cgraph_node *alias = alias_func->get_node ();
755 bool create_wrapper = false;
756 bool create_alias = false;
757 bool redirect_callers = false;
760 bool original_discardable = false;
761 bool original_discarded = false;
763 bool original_address_matters = original->address_matters_p ();
764 bool alias_address_matters = alias->address_matters_p ();
766 if (DECL_NO_INLINE_WARNING_P (original->decl)
767 != DECL_NO_INLINE_WARNING_P (alias->decl))
772 "DECL_NO_INLINE_WARNING mismatch.\n\n");
776 /* Do not attempt to mix functions from different user sections;
777 we do not know what user intends with those. */
778 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
779 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
780 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
785 "original and alias are in different sections.\n\n");
789 /* See if original is in a section that can be discarded if the main
790 symbol is not used. */
792 if (original->can_be_discarded_p ())
793 original_discardable = true;
794 /* Also consider case where we have resolution info and we know that
795 original's definition is not going to be used. In this case we can not
796 create alias to original. */
797 if (node->resolution != LDPR_UNKNOWN
798 && !decl_binds_to_current_def_p (node->decl))
799 original_discardable = original_discarded = true;
801 /* Creating a symtab alias is the optimal way to merge.
802 It however can not be used in the following cases:
804 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
805 2) if ORIGINAL is in a section that may be discarded by linker or if
806 it is an external functions where we can not create an alias
807 (ORIGINAL_DISCARDABLE)
808 3) if target do not support symbol aliases.
809 4) original and alias lie in different comdat groups.
811 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
812 and/or redirect all callers from ALIAS to ORIGINAL. */
813 if ((original_address_matters && alias_address_matters)
814 || (original_discardable
815 && (!DECL_COMDAT_GROUP (alias->decl)
816 || (DECL_COMDAT_GROUP (alias->decl)
817 != DECL_COMDAT_GROUP (original->decl))))
818 || original_discarded
819 || !sem_item::target_supports_symbol_aliases_p ()
820 || DECL_COMDAT_GROUP (alias->decl) != DECL_COMDAT_GROUP (original->decl))
822 /* First see if we can produce wrapper. */
824 /* Do not turn function in one comdat group into wrapper to another
825 comdat group. Other compiler producing the body of the
826 another comdat group may make opossite decision and with unfortunate
827 linker choices this may close a loop. */
828 if (DECL_COMDAT_GROUP (original->decl) && DECL_COMDAT_GROUP (alias->decl)
829 && (DECL_COMDAT_GROUP (alias->decl)
830 != DECL_COMDAT_GROUP (original->decl)))
834 "Wrapper cannot be created because of COMDAT\n");
836 else if (DECL_STATIC_CHAIN (alias->decl))
840 "Can not create wrapper of nested functions.\n");
842 /* TODO: We can also deal with variadic functions never calling
844 else if (stdarg_p (TREE_TYPE (alias->decl)))
848 "can not create wrapper of stdarg function.\n");
850 else if (inline_summaries
851 && inline_summaries->get (alias)->self_size <= 2)
854 fprintf (dump_file, "Wrapper creation is not "
855 "profitable (function is too small).\n");
857 /* If user paid attention to mark function noinline, assume it is
858 somewhat special and do not try to turn it into a wrapper that can
859 not be undone by inliner. */
860 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
863 fprintf (dump_file, "Wrappers are not created for noinline.\n");
866 create_wrapper = true;
868 /* We can redirect local calls in the case both alias and orignal
869 are not interposable. */
871 = alias->get_availability () > AVAIL_INTERPOSABLE
872 && original->get_availability () > AVAIL_INTERPOSABLE
873 && !alias->instrumented_version;
875 if (!redirect_callers && !create_wrapper)
878 fprintf (dump_file, "Not unifying; can not redirect callers nor "
879 "produce wrapper\n\n");
883 /* Work out the symbol the wrapper should call.
884 If ORIGINAL is interposable, we need to call a local alias.
885 Also produce local alias (if possible) as an optimization.
887 Local aliases can not be created inside comdat groups because that
888 prevents inlining. */
889 if (!original_discardable && !original->get_comdat_group ())
892 = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
894 && original->get_availability () > AVAIL_INTERPOSABLE)
895 local_original = original;
897 /* If we can not use local alias, fallback to the original
899 else if (original->get_availability () > AVAIL_INTERPOSABLE)
900 local_original = original;
902 /* If original is COMDAT local, we can not really redirect calls outside
903 of its comdat group to it. */
904 if (original->comdat_local_p ())
905 redirect_callers = false;
909 fprintf (dump_file, "Not unifying; "
910 "can not produce local alias.\n\n");
914 if (!redirect_callers && !create_wrapper)
917 fprintf (dump_file, "Not unifying; "
918 "can not redirect callers nor produce a wrapper\n\n");
922 && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
924 && !alias->can_remove_if_no_direct_calls_p ())
927 fprintf (dump_file, "Not unifying; can not make wrapper and "
928 "function has other uses than direct calls\n\n");
935 if (redirect_callers)
937 int nredirected = redirect_all_callers (alias, local_original);
941 alias->icf_merged = true;
942 local_original->icf_merged = true;
944 if (dump_file && nredirected)
945 fprintf (dump_file, "%i local calls have been "
946 "redirected.\n", nredirected);
949 /* If all callers was redirected, do not produce wrapper. */
950 if (alias->can_remove_if_no_direct_calls_p ()
951 && !alias->has_aliases_p ())
953 create_wrapper = false;
956 gcc_assert (!create_alias);
958 else if (create_alias)
960 alias->icf_merged = true;
962 /* Remove the function's body. */
963 ipa_merge_profiles (original, alias);
964 alias->release_body (true);
966 /* Notice global symbol possibly produced RTL. */
967 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
970 /* Create the alias. */
971 cgraph_node::create_alias (alias_func->decl, decl);
972 alias->resolve_alias (original);
974 original->call_for_symbol_thunks_and_aliases
975 (set_local, (void *)(size_t) original->local_p (), true);
978 fprintf (dump_file, "Unified; Function alias has been created.\n\n");
982 gcc_assert (!create_alias);
983 alias->icf_merged = true;
984 local_original->icf_merged = true;
986 ipa_merge_profiles (local_original, alias, true);
987 alias->create_wrapper (local_original);
990 fprintf (dump_file, "Unified; Wrapper has been created.\n\n");
993 /* It's possible that redirection can hit thunks that block
994 redirection opportunities. */
995 gcc_assert (alias->icf_merged || remove || redirect_callers);
996 original->icf_merged = true;
998 /* Inform the inliner about cross-module merging. */
999 if ((original->lto_file_data || alias->lto_file_data)
1000 && original->lto_file_data != alias->lto_file_data)
1001 local_original->merged = original->merged = true;
1005 ipa_merge_profiles (original, alias);
1006 alias->release_body ();
1008 alias->body_removed = true;
1009 alias->icf_merged = true;
1011 fprintf (dump_file, "Unified; Function body was removed.\n");
1017 /* Semantic item initialization function. */
1020 sem_function::init (void)
1023 get_node ()->get_untransformed_body ();
1025 tree fndecl = node->decl;
1026 function *func = DECL_STRUCT_FUNCTION (fndecl);
1029 gcc_assert (SSANAMES (func));
1031 ssa_names_size = SSANAMES (func)->length ();
1035 region_tree = func->eh->region_tree;
1037 /* iterating all function arguments. */
1038 arg_count = count_formal_params (fndecl);
1040 edge_count = n_edges_for_fn (func);
1041 cfg_checksum = coverage_compute_cfg_checksum (func);
1043 inchash::hash hstate;
1046 FOR_EACH_BB_FN (bb, func)
1048 unsigned nondbg_stmt_count = 0;
1051 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
1053 cfg_checksum = iterative_hash_host_wide_int (e->flags,
1056 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1059 gimple stmt = gsi_stmt (gsi);
1061 if (gimple_code (stmt) != GIMPLE_DEBUG
1062 && gimple_code (stmt) != GIMPLE_PREDICT)
1064 hash_stmt (stmt, hstate);
1065 nondbg_stmt_count++;
1069 gcode_hash = hstate.end ();
1070 bb_sizes.safe_push (nondbg_stmt_count);
1072 /* Inserting basic block to hash table. */
1073 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
1074 EDGE_COUNT (bb->preds)
1075 + EDGE_COUNT (bb->succs));
1077 bb_sorted.safe_push (semantic_bb);
1083 /* Accumulate to HSTATE a hash of expression EXP.
1084 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1085 and DECL equality classes. */
1088 sem_item::add_expr (const_tree exp, inchash::hash &hstate)
1090 if (exp == NULL_TREE)
1092 hstate.merge_hash (0);
1096 /* Handled component can be matched in a cureful way proving equivalence
1097 even if they syntactically differ. Just skip them. */
1099 while (handled_component_p (exp))
1100 exp = TREE_OPERAND (exp, 0);
1102 enum tree_code code = TREE_CODE (exp);
1103 hstate.add_int (code);
1107 /* Use inchash::add_expr for everything that is LTO stable. */
1115 inchash::add_expr (exp, hstate);
1119 unsigned HOST_WIDE_INT idx;
1122 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1124 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp), idx, value)
1126 add_expr (value, hstate);
1131 add_expr (get_base_address (TREE_OPERAND (exp, 0)), hstate);
1137 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1140 case POINTER_PLUS_EXPR:
1143 add_expr (TREE_OPERAND (exp, 0), hstate);
1144 add_expr (TREE_OPERAND (exp, 1), hstate);
1148 inchash::hash one, two;
1149 add_expr (TREE_OPERAND (exp, 0), one);
1150 add_expr (TREE_OPERAND (exp, 1), two);
1151 hstate.add_commutative (one, two);
1155 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1156 return add_expr (TREE_OPERAND (exp, 0), hstate);
1162 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1165 sem_function::hash_stmt (gimple stmt, inchash::hash &hstate)
1167 enum gimple_code code = gimple_code (stmt);
1169 hstate.add_int (code);
1174 if (commutative_tree_code (gimple_assign_rhs_code (stmt))
1175 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1177 inchash::hash one, two;
1179 add_expr (gimple_assign_rhs1 (stmt), one);
1180 add_expr (gimple_assign_rhs2 (stmt), two);
1181 hstate.add_commutative (one, two);
1182 add_expr (gimple_assign_lhs (stmt), hstate);
1185 /* ... fall through ... */
1191 /* All these statements are equivalent if their operands are. */
1192 for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1193 add_expr (gimple_op (stmt, i), hstate);
1200 /* Return true if polymorphic comparison must be processed. */
1203 sem_function::compare_polymorphic_p (void)
1205 return get_node ()->callees != NULL
1206 || get_node ()->indirect_calls != NULL
1207 || m_compared_func->get_node ()->callees != NULL
1208 || m_compared_func->get_node ()->indirect_calls != NULL;
1211 /* For a given call graph NODE, the function constructs new
1212 semantic function item. */
1215 sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
1217 tree fndecl = node->decl;
1218 function *func = DECL_STRUCT_FUNCTION (fndecl);
1220 /* TODO: add support for thunks. */
1222 if (!func || !node->has_gimple_body_p ())
1225 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
1228 sem_function *f = new sem_function (node, 0, stack);
1235 /* Parses function arguments and result type. */
1238 sem_function::parse_tree_args (void)
1242 if (arg_types.exists ())
1243 arg_types.release ();
1245 arg_types.create (4);
1246 tree fnargs = DECL_ARGUMENTS (decl);
1248 for (tree parm = fnargs; parm; parm = DECL_CHAIN (parm))
1249 arg_types.safe_push (DECL_ARG_TYPE (parm));
1251 /* Function result type. */
1252 result = DECL_RESULT (decl);
1253 result_type = result ? TREE_TYPE (result) : NULL;
1255 /* During WPA, we can get arguments by following method. */
1258 tree type = TYPE_ARG_TYPES (TREE_TYPE (decl));
1259 for (tree parm = type; parm; parm = TREE_CHAIN (parm))
1260 arg_types.safe_push (TYPE_CANONICAL (TREE_VALUE (parm)));
1262 result_type = TREE_TYPE (TREE_TYPE (decl));
1266 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1267 return true if phi nodes are semantically equivalent in these blocks . */
1270 sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
1272 gphi_iterator si1, si2;
1274 unsigned size1, size2, i;
1278 gcc_assert (bb1 != NULL);
1279 gcc_assert (bb2 != NULL);
1281 si2 = gsi_start_phis (bb2);
1282 for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
1285 gsi_next_nonvirtual_phi (&si1);
1286 gsi_next_nonvirtual_phi (&si2);
1288 if (gsi_end_p (si1) && gsi_end_p (si2))
1291 if (gsi_end_p (si1) || gsi_end_p (si2))
1292 return return_false();
1297 tree phi_result1 = gimple_phi_result (phi1);
1298 tree phi_result2 = gimple_phi_result (phi2);
1300 if (!m_checker->compare_operand (phi_result1, phi_result2))
1301 return return_false_with_msg ("PHI results are different");
1303 size1 = gimple_phi_num_args (phi1);
1304 size2 = gimple_phi_num_args (phi2);
1307 return return_false ();
1309 for (i = 0; i < size1; ++i)
1311 t1 = gimple_phi_arg (phi1, i)->def;
1312 t2 = gimple_phi_arg (phi2, i)->def;
1314 if (!m_checker->compare_operand (t1, t2))
1315 return return_false ();
1317 e1 = gimple_phi_arg_edge (phi1, i);
1318 e2 = gimple_phi_arg_edge (phi2, i);
1320 if (!m_checker->compare_edge (e1, e2))
1321 return return_false ();
1330 /* Returns true if tree T can be compared as a handled component. */
1333 sem_function::icf_handled_component_p (tree t)
1335 tree_code tc = TREE_CODE (t);
1337 return ((handled_component_p (t))
1338 || tc == ADDR_EXPR || tc == MEM_REF || tc == REALPART_EXPR
1339 || tc == IMAGPART_EXPR || tc == OBJ_TYPE_REF);
1342 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1343 corresponds to TARGET. */
1346 sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
1351 if (bb_dict->length () <= (unsigned)source)
1352 bb_dict->safe_grow_cleared (source + 1);
1354 if ((*bb_dict)[source] == 0)
1356 (*bb_dict)[source] = target;
1360 return (*bb_dict)[source] == target;
1363 /* Iterates all tree types in T1 and T2 and returns true if all types
1364 are compatible. If COMPARE_POLYMORPHIC is set to true,
1365 more strict comparison is executed. */
1368 sem_function::compare_type_list (tree t1, tree t2, bool compare_polymorphic)
1376 while (t1 != NULL && t2 != NULL)
1378 tv1 = TREE_VALUE (t1);
1379 tv2 = TREE_VALUE (t2);
1381 tc1 = TREE_CODE (tv1);
1382 tc2 = TREE_CODE (tv2);
1384 if (tc1 == NOP_EXPR && tc2 == NOP_EXPR)
1386 else if (tc1 == NOP_EXPR || tc2 == NOP_EXPR)
1388 else if (!func_checker::compatible_types_p (tv1, tv2, compare_polymorphic))
1391 t1 = TREE_CHAIN (t1);
1392 t2 = TREE_CHAIN (t2);
1399 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1401 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
1405 /* Constructor based on varpool node _NODE with computed hash _HASH.
1406 Bitmap STACK is used for memory allocation. */
1408 sem_variable::sem_variable (varpool_node *node, hashval_t _hash,
1409 bitmap_obstack *stack): sem_item(VAR,
1412 gcc_checking_assert (node);
1413 gcc_checking_assert (get_node ());
1416 /* Fast equality function based on knowledge known in WPA. */
1419 sem_variable::equals_wpa (sem_item *item,
1420 hash_map <symtab_node *, sem_item *> &ignored_nodes)
1422 gcc_assert (item->type == VAR);
1424 if (node->num_references () != item->node->num_references ())
1425 return return_false_with_msg ("different number of references");
1427 if (DECL_TLS_MODEL (decl) || DECL_TLS_MODEL (item->decl))
1428 return return_false_with_msg ("TLS model");
1430 if (DECL_ALIGN (decl) != DECL_ALIGN (item->decl))
1431 return return_false_with_msg ("alignment mismatch");
1433 if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
1434 return return_false_with_msg ("Virtual flag mismatch");
1436 if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
1437 && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
1438 || !operand_equal_p (DECL_SIZE (decl),
1439 DECL_SIZE (item->decl), OEP_ONLY_CONST)))
1440 return return_false_with_msg ("size mismatch");
1442 /* Do not attempt to mix data from different user sections;
1443 we do not know what user intends with those. */
1444 if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
1445 || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
1446 && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
1447 return return_false_with_msg ("user section mismatch");
1449 if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
1450 return return_false_with_msg ("text section");
1452 ipa_ref *ref = NULL, *ref2 = NULL;
1453 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
1455 item->node->iterate_reference (i, ref2);
1457 if (!compare_cgraph_references (ignored_nodes,
1458 ref->referred, ref2->referred,
1459 ref->address_matters_p ()))
1466 /* Returns true if the item equals to ITEM given as argument. */
1468 /* Returns true if the item equals to ITEM given as argument. */
1471 sem_variable::equals (sem_item *item,
1472 hash_map <symtab_node *, sem_item *> &)
1474 gcc_assert (item->type == VAR);
1477 if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
1478 dyn_cast <varpool_node *>(node)->get_constructor ();
1479 if (DECL_INITIAL (item->decl) == error_mark_node && in_lto_p)
1480 dyn_cast <varpool_node *>(item->node)->get_constructor ();
1482 ret = sem_variable::equals (DECL_INITIAL (decl),
1483 DECL_INITIAL (item->node->decl));
1484 if (dump_file && (dump_flags & TDF_DETAILS))
1486 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1487 name(), item->name (), node->order, item->node->order, asm_name (),
1488 item->asm_name (), ret ? "true" : "false");
1493 /* Compares trees T1 and T2 for semantic equality. */
1496 sem_variable::equals (tree t1, tree t2)
1499 return return_with_debug (t1 == t2);
1502 tree_code tc1 = TREE_CODE (t1);
1503 tree_code tc2 = TREE_CODE (t2);
1506 return return_false_with_msg ("TREE_CODE mismatch");
1512 vec<constructor_elt, va_gc> *v1, *v2;
1513 unsigned HOST_WIDE_INT idx;
1515 enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
1516 if (typecode != TREE_CODE (TREE_TYPE (t2)))
1517 return return_false_with_msg ("constructor type mismatch");
1519 if (typecode == ARRAY_TYPE)
1521 HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
1522 /* For arrays, check that the sizes all match. */
1523 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
1525 || size_1 != int_size_in_bytes (TREE_TYPE (t2)))
1526 return return_false_with_msg ("constructor array size mismatch");
1528 else if (!func_checker::compatible_types_p (TREE_TYPE (t1),
1530 return return_false_with_msg ("constructor type incompatible");
1532 v1 = CONSTRUCTOR_ELTS (t1);
1533 v2 = CONSTRUCTOR_ELTS (t2);
1534 if (vec_safe_length (v1) != vec_safe_length (v2))
1535 return return_false_with_msg ("constructor number of elts mismatch");
1537 for (idx = 0; idx < vec_safe_length (v1); ++idx)
1539 constructor_elt *c1 = &(*v1)[idx];
1540 constructor_elt *c2 = &(*v2)[idx];
1542 /* Check that each value is the same... */
1543 if (!sem_variable::equals (c1->value, c2->value))
1545 /* ... and that they apply to the same fields! */
1546 if (!sem_variable::equals (c1->index, c2->index))
1553 tree x1 = TREE_OPERAND (t1, 0);
1554 tree x2 = TREE_OPERAND (t2, 0);
1555 tree y1 = TREE_OPERAND (t1, 1);
1556 tree y2 = TREE_OPERAND (t2, 1);
1558 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2),
1560 return return_false ();
1562 /* Type of the offset on MEM_REF does not matter. */
1563 return return_with_debug (sem_variable::equals (x1, x2)
1564 && wi::to_offset (y1)
1565 == wi::to_offset (y2));
1570 tree op1 = TREE_OPERAND (t1, 0);
1571 tree op2 = TREE_OPERAND (t2, 0);
1572 return sem_variable::equals (op1, op2);
1574 /* References to other vars/decls are compared using ipa-ref. */
1577 if (decl_in_symtab_p (t1) && decl_in_symtab_p (t2))
1579 return return_false_with_msg ("Declaration mismatch");
1581 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1582 need to process its VAR/FUNCTION references without relying on ipa-ref
1586 return return_false_with_msg ("Declaration mismatch");
1588 /* Integer constants are the same only if the same width of type. */
1589 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1590 return return_false_with_msg ("INTEGER_CST precision mismatch");
1591 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1592 return return_false_with_msg ("INTEGER_CST mode mismatch");
1593 return return_with_debug (tree_int_cst_equal (t1, t2));
1595 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1596 return return_false_with_msg ("STRING_CST mode mismatch");
1597 if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
1598 return return_false_with_msg ("STRING_CST length mismatch");
1599 if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
1600 TREE_STRING_LENGTH (t1)))
1601 return return_false_with_msg ("STRING_CST mismatch");
1604 /* Fixed constants are the same only if the same width of type. */
1605 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1606 return return_false_with_msg ("FIXED_CST precision mismatch");
1608 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
1609 TREE_FIXED_CST (t2)));
1611 return (sem_variable::equals (TREE_REALPART (t1), TREE_REALPART (t2))
1612 && sem_variable::equals (TREE_IMAGPART (t1), TREE_IMAGPART (t2)));
1614 /* Real constants are the same only if the same width of type. */
1615 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1616 return return_false_with_msg ("REAL_CST precision mismatch");
1617 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1),
1618 TREE_REAL_CST (t2)));
1623 if (VECTOR_CST_NELTS (t1) != VECTOR_CST_NELTS (t2))
1624 return return_false_with_msg ("VECTOR_CST nelts mismatch");
1626 for (i = 0; i < VECTOR_CST_NELTS (t1); ++i)
1627 if (!sem_variable::equals (VECTOR_CST_ELT (t1, i),
1628 VECTOR_CST_ELT (t2, i)))
1634 case ARRAY_RANGE_REF:
1636 tree x1 = TREE_OPERAND (t1, 0);
1637 tree x2 = TREE_OPERAND (t2, 0);
1638 tree y1 = TREE_OPERAND (t1, 1);
1639 tree y2 = TREE_OPERAND (t2, 1);
1641 if (!sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2))
1643 if (!sem_variable::equals (array_ref_low_bound (t1),
1644 array_ref_low_bound (t2)))
1646 if (!sem_variable::equals (array_ref_element_size (t1),
1647 array_ref_element_size (t2)))
1653 case POINTER_PLUS_EXPR:
1658 tree x1 = TREE_OPERAND (t1, 0);
1659 tree x2 = TREE_OPERAND (t2, 0);
1660 tree y1 = TREE_OPERAND (t1, 1);
1661 tree y2 = TREE_OPERAND (t2, 1);
1663 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
1667 case VIEW_CONVERT_EXPR:
1668 if (!func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
1670 return return_false ();
1671 return sem_variable::equals (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1673 return return_false_with_msg ("ERROR_MARK");
1675 return return_false_with_msg ("Unknown TREE code reached");
1679 /* Parser function that visits a varpool NODE. */
1682 sem_variable::parse (varpool_node *node, bitmap_obstack *stack)
1684 if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl))
1687 sem_variable *v = new sem_variable (node, 0, stack);
1694 /* References independent hash function. */
1697 sem_variable::get_hash (void)
1702 /* All WPA streamed in symbols should have their hashes computed at compile
1703 time. At this point, the constructor may not be in memory at all.
1704 DECL_INITIAL (decl) would be error_mark_node in that case. */
1705 gcc_assert (!node->lto_file_data);
1706 tree ctor = DECL_INITIAL (decl);
1707 inchash::hash hstate;
1709 hstate.add_int (456346417);
1710 if (DECL_SIZE (decl) && tree_fits_shwi_p (DECL_SIZE (decl)))
1711 hstate.add_wide_int (tree_to_shwi (DECL_SIZE (decl)));
1712 add_expr (ctor, hstate);
1713 hash = hstate.end ();
1718 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1722 sem_variable::merge (sem_item *alias_item)
1724 gcc_assert (alias_item->type == VAR);
1726 if (!sem_item::target_supports_symbol_aliases_p ())
1729 fprintf (dump_file, "Not unifying; "
1730 "Symbol aliases are not supported by target\n\n");
1734 sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
1736 varpool_node *original = get_node ();
1737 varpool_node *alias = alias_var->get_node ();
1738 bool original_discardable = false;
1740 bool original_address_matters = original->address_matters_p ();
1741 bool alias_address_matters = alias->address_matters_p ();
1743 /* See if original is in a section that can be discarded if the main
1745 Also consider case where we have resolution info and we know that
1746 original's definition is not going to be used. In this case we can not
1747 create alias to original. */
1748 if (original->can_be_discarded_p ()
1749 || (node->resolution != LDPR_UNKNOWN
1750 && !decl_binds_to_current_def_p (node->decl)))
1751 original_discardable = true;
1753 gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
1755 /* Constant pool machinery is not quite ready for aliases.
1756 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
1757 For LTO merging does not happen that is an important missing feature.
1758 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
1759 flag is dropped and non-local symbol name is assigned. */
1760 if (DECL_IN_CONSTANT_POOL (alias->decl)
1761 || DECL_IN_CONSTANT_POOL (original->decl))
1765 "Not unifying; constant pool variables.\n\n");
1769 /* Do not attempt to mix functions from different user sections;
1770 we do not know what user intends with those. */
1771 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
1772 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
1773 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
1778 "original and alias are in different sections.\n\n");
1782 /* We can not merge if address comparsion metters. */
1783 if (original_address_matters && alias_address_matters
1784 && flag_merge_constants < 2)
1789 "adress of original and alias may be compared.\n\n");
1792 if (DECL_COMDAT_GROUP (original->decl) != DECL_COMDAT_GROUP (alias->decl))
1795 fprintf (dump_file, "Not unifying; alias cannot be created; "
1796 "across comdat group boundary\n\n");
1801 if (original_discardable)
1804 fprintf (dump_file, "Not unifying; alias cannot be created; "
1805 "target is discardable\n\n");
1811 gcc_assert (!original->alias);
1812 gcc_assert (!alias->alias);
1814 alias->analyzed = false;
1816 DECL_INITIAL (alias->decl) = NULL;
1817 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
1819 alias->need_bounds_init = false;
1820 alias->remove_all_references ();
1821 if (TREE_ADDRESSABLE (alias->decl))
1822 original->call_for_symbol_and_aliases (set_addressable, NULL, true);
1824 varpool_node::create_alias (alias_var->decl, decl);
1825 alias->resolve_alias (original);
1828 fprintf (dump_file, "Unified; Variable alias has been created.\n\n");
1834 /* Dump symbol to FILE. */
1837 sem_variable::dump_to_file (FILE *file)
1841 print_node (file, "", decl, 0);
1842 fprintf (file, "\n\n");
1845 /* Iterates though a constructor and identifies tree references
1846 we are interested in semantic function equality. */
1849 sem_variable::parse_tree_refs (tree t)
1851 switch (TREE_CODE (t))
1855 unsigned length = vec_safe_length (CONSTRUCTOR_ELTS (t));
1857 for (unsigned i = 0; i < length; i++)
1858 parse_tree_refs(CONSTRUCTOR_ELT (t, i)->value);
1865 tree op = TREE_OPERAND (t, 0);
1866 parse_tree_refs (op);
1871 tree_refs.safe_push (t);
1879 unsigned int sem_item_optimizer::class_id = 0;
1881 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1882 m_classes_count (0), m_cgraph_node_hooks (NULL), m_varpool_node_hooks (NULL)
1885 bitmap_obstack_initialize (&m_bmstack);
1888 sem_item_optimizer::~sem_item_optimizer ()
1890 for (unsigned int i = 0; i < m_items.length (); i++)
1893 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
1894 it != m_classes.end (); ++it)
1896 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
1897 delete (*it)->classes[i];
1899 (*it)->classes.release ();
1905 bitmap_obstack_release (&m_bmstack);
1908 /* Write IPA ICF summary for symbols. */
1911 sem_item_optimizer::write_summary (void)
1913 unsigned int count = 0;
1915 output_block *ob = create_output_block (LTO_section_ipa_icf);
1916 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
1919 /* Calculate number of symbols to be serialized. */
1920 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
1922 lsei_next_in_partition (&lsei))
1924 symtab_node *node = lsei_node (lsei);
1926 if (m_symtab_node_map.get (node))
1930 streamer_write_uhwi (ob, count);
1932 /* Process all of the symbols. */
1933 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
1935 lsei_next_in_partition (&lsei))
1937 symtab_node *node = lsei_node (lsei);
1939 sem_item **item = m_symtab_node_map.get (node);
1943 int node_ref = lto_symtab_encoder_encode (encoder, node);
1944 streamer_write_uhwi_stream (ob->main_stream, node_ref);
1946 streamer_write_uhwi (ob, (*item)->get_hash ());
1950 streamer_write_char_stream (ob->main_stream, 0);
1951 produce_asm (ob, NULL);
1952 destroy_output_block (ob);
1955 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1956 contains LEN bytes. */
1959 sem_item_optimizer::read_section (lto_file_decl_data *file_data,
1960 const char *data, size_t len)
1962 const lto_function_header *header =
1963 (const lto_function_header *) data;
1964 const int cfg_offset = sizeof (lto_function_header);
1965 const int main_offset = cfg_offset + header->cfg_size;
1966 const int string_offset = main_offset + header->main_size;
1971 lto_input_block ib_main ((const char *) data + main_offset, 0,
1972 header->main_size, file_data->mode_table);
1975 lto_data_in_create (file_data, (const char *) data + string_offset,
1976 header->string_size, vNULL);
1978 count = streamer_read_uhwi (&ib_main);
1980 for (i = 0; i < count; i++)
1984 lto_symtab_encoder_t encoder;
1986 index = streamer_read_uhwi (&ib_main);
1987 encoder = file_data->symtab_node_encoder;
1988 node = lto_symtab_encoder_deref (encoder, index);
1990 hashval_t hash = streamer_read_uhwi (&ib_main);
1992 gcc_assert (node->definition);
1995 fprintf (dump_file, "Symbol added:%s (tree: %p, uid:%u)\n", node->asm_name (),
1996 (void *) node->decl, node->order);
1998 if (is_a<cgraph_node *> (node))
2000 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
2002 m_items.safe_push (new sem_function (cnode, hash, &m_bmstack));
2006 varpool_node *vnode = dyn_cast <varpool_node *> (node);
2008 m_items.safe_push (new sem_variable (vnode, hash, &m_bmstack));
2012 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
2014 lto_data_in_delete (data_in);
2017 /* Read IPA IPA ICF summary for symbols. */
2020 sem_item_optimizer::read_summary (void)
2022 lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2023 lto_file_decl_data *file_data;
2026 while ((file_data = file_data_vec[j++]))
2029 const char *data = lto_get_section_data (file_data,
2030 LTO_section_ipa_icf, NULL, &len);
2033 read_section (file_data, data, len);
2037 /* Register callgraph and varpool hooks. */
2040 sem_item_optimizer::register_hooks (void)
2042 if (!m_cgraph_node_hooks)
2043 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
2044 (&sem_item_optimizer::cgraph_removal_hook, this);
2046 if (!m_varpool_node_hooks)
2047 m_varpool_node_hooks = symtab->add_varpool_removal_hook
2048 (&sem_item_optimizer::varpool_removal_hook, this);
2051 /* Unregister callgraph and varpool hooks. */
2054 sem_item_optimizer::unregister_hooks (void)
2056 if (m_cgraph_node_hooks)
2057 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
2059 if (m_varpool_node_hooks)
2060 symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
2063 /* Adds a CLS to hashtable associated by hash value. */
2066 sem_item_optimizer::add_class (congruence_class *cls)
2068 gcc_assert (cls->members.length ());
2070 congruence_class_group *group = get_group_by_hash (
2071 cls->members[0]->get_hash (),
2072 cls->members[0]->type);
2073 group->classes.safe_push (cls);
2076 /* Gets a congruence class group based on given HASH value and TYPE. */
2078 congruence_class_group *
2079 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
2081 congruence_class_group *item = XNEW (congruence_class_group);
2085 congruence_class_group **slot = m_classes.find_slot (item, INSERT);
2091 item->classes.create (1);
2098 /* Callgraph removal hook called for a NODE with a custom DATA. */
2101 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
2103 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2104 optimizer->remove_symtab_node (node);
2107 /* Varpool removal hook called for a NODE with a custom DATA. */
2110 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
2112 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2113 optimizer->remove_symtab_node (node);
2116 /* Remove symtab NODE triggered by symtab removal hooks. */
2119 sem_item_optimizer::remove_symtab_node (symtab_node *node)
2121 gcc_assert (!m_classes.elements());
2123 m_removed_items_set.add (node);
2127 sem_item_optimizer::remove_item (sem_item *item)
2129 if (m_symtab_node_map.get (item->node))
2130 m_symtab_node_map.remove (item->node);
2134 /* Removes all callgraph and varpool nodes that are marked by symtab
2138 sem_item_optimizer::filter_removed_items (void)
2140 auto_vec <sem_item *> filtered;
2142 for (unsigned int i = 0; i < m_items.length(); i++)
2144 sem_item *item = m_items[i];
2146 if (m_removed_items_set.contains (item->node))
2152 if (item->type == FUNC)
2154 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
2156 bool no_body_function = in_lto_p && (cnode->alias || cnode->body_removed);
2157 if (no_body_function || !opt_for_fn (item->decl, flag_ipa_icf_functions)
2158 || DECL_CXX_CONSTRUCTOR_P (item->decl)
2159 || DECL_CXX_DESTRUCTOR_P (item->decl))
2162 filtered.safe_push (item);
2166 if (!flag_ipa_icf_variables)
2170 /* Filter out non-readonly variables. */
2171 tree decl = item->decl;
2172 if (TREE_READONLY (decl))
2173 filtered.safe_push (item);
2180 /* Clean-up of released semantic items. */
2183 for (unsigned int i = 0; i < filtered.length(); i++)
2184 m_items.safe_push (filtered[i]);
2187 /* Optimizer entry point which returns true in case it processes
2188 a merge operation. True is returned if there's a merge operation
2192 sem_item_optimizer::execute (void)
2194 filter_removed_items ();
2195 unregister_hooks ();
2197 build_hash_based_classes ();
2200 fprintf (dump_file, "Dump after hash based groups\n");
2201 dump_cong_classes ();
2203 for (unsigned int i = 0; i < m_items.length(); i++)
2204 m_items[i]->init_wpa ();
2208 subdivide_classes_by_equality (true);
2211 fprintf (dump_file, "Dump after WPA based types groups\n");
2213 dump_cong_classes ();
2215 process_cong_reduction ();
2219 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
2221 dump_cong_classes ();
2223 parse_nonsingleton_classes ();
2224 subdivide_classes_by_equality ();
2227 fprintf (dump_file, "Dump after full equality comparison of groups\n");
2229 dump_cong_classes ();
2231 unsigned int prev_class_count = m_classes_count;
2233 process_cong_reduction ();
2234 dump_cong_classes ();
2236 bool merged_p = merge_classes (prev_class_count);
2238 if (dump_file && (dump_flags & TDF_DETAILS))
2239 symtab_node::dump_table (dump_file);
2244 /* Function responsible for visiting all potential functions and
2245 read-only variables that can be merged. */
2248 sem_item_optimizer::parse_funcs_and_vars (void)
2252 if (flag_ipa_icf_functions)
2253 FOR_EACH_DEFINED_FUNCTION (cnode)
2255 sem_function *f = sem_function::parse (cnode, &m_bmstack);
2258 m_items.safe_push (f);
2259 m_symtab_node_map.put (cnode, f);
2262 fprintf (dump_file, "Parsed function:%s\n", f->asm_name ());
2264 if (dump_file && (dump_flags & TDF_DETAILS))
2265 f->dump_to_file (dump_file);
2268 fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
2271 varpool_node *vnode;
2273 if (flag_ipa_icf_variables)
2274 FOR_EACH_DEFINED_VARIABLE (vnode)
2276 sem_variable *v = sem_variable::parse (vnode, &m_bmstack);
2280 m_items.safe_push (v);
2281 m_symtab_node_map.put (vnode, v);
2286 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2289 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
2291 item->index_in_class = cls->members.length ();
2292 cls->members.safe_push (item);
2296 /* Congruence classes are built by hash value. */
2299 sem_item_optimizer::build_hash_based_classes (void)
2301 for (unsigned i = 0; i < m_items.length (); i++)
2303 sem_item *item = m_items[i];
2305 congruence_class_group *group = get_group_by_hash (item->get_hash (),
2308 if (!group->classes.length ())
2311 group->classes.safe_push (new congruence_class (class_id++));
2314 add_item_to_class (group->classes[0], item);
2318 /* Build references according to call graph. */
2321 sem_item_optimizer::build_graph (void)
2323 for (unsigned i = 0; i < m_items.length (); i++)
2325 sem_item *item = m_items[i];
2326 m_symtab_node_map.put (item->node, item);
2329 for (unsigned i = 0; i < m_items.length (); i++)
2331 sem_item *item = m_items[i];
2333 if (item->type == FUNC)
2335 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
2337 cgraph_edge *e = cnode->callees;
2340 sem_item **slot = m_symtab_node_map.get
2341 (e->callee->ultimate_alias_target ());
2343 item->add_reference (*slot);
2349 ipa_ref *ref = NULL;
2350 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
2352 sem_item **slot = m_symtab_node_map.get
2353 (ref->referred->ultimate_alias_target ());
2355 item->add_reference (*slot);
2360 /* Semantic items in classes having more than one element and initialized.
2361 In case of WPA, we load function body. */
2364 sem_item_optimizer::parse_nonsingleton_classes (void)
2366 unsigned int init_called_count = 0;
2368 for (unsigned i = 0; i < m_items.length (); i++)
2369 if (m_items[i]->cls->members.length () > 1)
2371 m_items[i]->init ();
2372 init_called_count++;
2376 fprintf (dump_file, "Init called for %u items (%.2f%%).\n", init_called_count,
2377 m_items.length () ? 100.0f * init_called_count / m_items.length (): 0.0f);
2380 /* Equality function for semantic items is used to subdivide existing
2381 classes. If IN_WPA, fast equality function is invoked. */
2384 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
2386 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2387 it != m_classes.end (); ++it)
2389 unsigned int class_count = (*it)->classes.length ();
2391 for (unsigned i = 0; i < class_count; i++)
2393 congruence_class *c = (*it)->classes [i];
2395 if (c->members.length() > 1)
2397 auto_vec <sem_item *> new_vector;
2399 sem_item *first = c->members[0];
2400 new_vector.safe_push (first);
2402 unsigned class_split_first = (*it)->classes.length ();
2404 for (unsigned j = 1; j < c->members.length (); j++)
2406 sem_item *item = c->members[j];
2408 bool equals = in_wpa ? first->equals_wpa (item,
2409 m_symtab_node_map) : first->equals (item, m_symtab_node_map);
2412 new_vector.safe_push (item);
2415 bool integrated = false;
2417 for (unsigned k = class_split_first; k < (*it)->classes.length (); k++)
2419 sem_item *x = (*it)->classes[k]->members[0];
2420 bool equals = in_wpa ? x->equals_wpa (item,
2421 m_symtab_node_map) : x->equals (item, m_symtab_node_map);
2426 add_item_to_class ((*it)->classes[k], item);
2434 congruence_class *c = new congruence_class (class_id++);
2436 add_item_to_class (c, item);
2438 (*it)->classes.safe_push (c);
2443 // we replace newly created new_vector for the class we've just splitted
2444 c->members.release ();
2445 c->members.create (new_vector.length ());
2447 for (unsigned int j = 0; j < new_vector.length (); j++)
2448 add_item_to_class (c, new_vector[j]);
2456 /* Subdivide classes by address references that members of the class
2457 reference. Example can be a pair of functions that have an address
2458 taken from a function. If these addresses are different the class
2462 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2464 unsigned newly_created_classes = 0;
2466 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2467 it != m_classes.end (); ++it)
2469 unsigned int class_count = (*it)->classes.length ();
2470 auto_vec<congruence_class *> new_classes;
2472 for (unsigned i = 0; i < class_count; i++)
2474 congruence_class *c = (*it)->classes [i];
2476 if (c->members.length() > 1)
2478 hash_map <symbol_compare_collection *, vec <sem_item *>,
2479 symbol_compare_hashmap_traits> split_map;
2481 for (unsigned j = 0; j < c->members.length (); j++)
2483 sem_item *source_node = c->members[j];
2485 symbol_compare_collection *collection = new symbol_compare_collection (source_node->node);
2487 vec <sem_item *> *slot = &split_map.get_or_insert (collection);
2488 gcc_checking_assert (slot);
2490 slot->safe_push (source_node);
2493 /* If the map contains more than one key, we have to split the map
2495 if (split_map.elements () != 1)
2497 bool first_class = true;
2499 hash_map <symbol_compare_collection *, vec <sem_item *>,
2500 symbol_compare_hashmap_traits>::iterator it2 = split_map.begin ();
2501 for (; it2 != split_map.end (); ++it2)
2503 congruence_class *new_cls;
2504 new_cls = new congruence_class (class_id++);
2506 for (unsigned k = 0; k < (*it2).second.length (); k++)
2507 add_item_to_class (new_cls, (*it2).second[k]);
2509 worklist_push (new_cls);
2510 newly_created_classes++;
2514 (*it)->classes[i] = new_cls;
2515 first_class = false;
2519 new_classes.safe_push (new_cls);
2527 for (unsigned i = 0; i < new_classes.length (); i++)
2528 (*it)->classes.safe_push (new_classes[i]);
2531 return newly_created_classes;
2534 /* Verify congruence classes if checking is enabled. */
2537 sem_item_optimizer::verify_classes (void)
2540 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2541 it != m_classes.end (); ++it)
2543 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2545 congruence_class *cls = (*it)->classes[i];
2547 gcc_checking_assert (cls);
2548 gcc_checking_assert (cls->members.length () > 0);
2550 for (unsigned int j = 0; j < cls->members.length (); j++)
2552 sem_item *item = cls->members[j];
2554 gcc_checking_assert (item);
2555 gcc_checking_assert (item->cls == cls);
2557 for (unsigned k = 0; k < item->usages.length (); k++)
2559 sem_usage_pair *usage = item->usages[k];
2560 gcc_checking_assert (usage->item->index_in_class <
2561 usage->item->cls->members.length ());
2569 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2570 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2571 but unused argument. */
2574 sem_item_optimizer::release_split_map (congruence_class * const &,
2575 bitmap const &b, traverse_split_pair *)
2584 /* Process split operation for a class given as pointer CLS_PTR,
2585 where bitmap B splits congruence class members. DATA is used
2586 as argument of split pair. */
2589 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
2590 bitmap const &b, traverse_split_pair *pair)
2592 sem_item_optimizer *optimizer = pair->optimizer;
2593 const congruence_class *splitter_cls = pair->cls;
2595 /* If counted bits are greater than zero and less than the number of members
2596 a group will be splitted. */
2597 unsigned popcount = bitmap_count_bits (b);
2599 if (popcount > 0 && popcount < cls->members.length ())
2601 congruence_class* newclasses[2] = { new congruence_class (class_id++), new congruence_class (class_id++) };
2603 for (unsigned int i = 0; i < cls->members.length (); i++)
2605 int target = bitmap_bit_p (b, i);
2606 congruence_class *tc = newclasses[target];
2608 add_item_to_class (tc, cls->members[i]);
2611 #ifdef ENABLE_CHECKING
2612 for (unsigned int i = 0; i < 2; i++)
2613 gcc_checking_assert (newclasses[i]->members.length ());
2616 if (splitter_cls == cls)
2617 optimizer->splitter_class_removed = true;
2619 /* Remove old class from worklist if presented. */
2620 bool in_worklist = cls->in_worklist;
2623 cls->in_worklist = false;
2625 congruence_class_group g;
2626 g.hash = cls->members[0]->get_hash ();
2627 g.type = cls->members[0]->type;
2629 congruence_class_group *slot = optimizer->m_classes.find(&g);
2631 for (unsigned int i = 0; i < slot->classes.length (); i++)
2632 if (slot->classes[i] == cls)
2634 slot->classes.ordered_remove (i);
2638 /* New class will be inserted and integrated to work list. */
2639 for (unsigned int i = 0; i < 2; i++)
2640 optimizer->add_class (newclasses[i]);
2642 /* Two classes replace one, so that increment just by one. */
2643 optimizer->m_classes_count++;
2645 /* If OLD class was presented in the worklist, we remove the class
2646 and replace it will both newly created classes. */
2648 for (unsigned int i = 0; i < 2; i++)
2649 optimizer->worklist_push (newclasses[i]);
2650 else /* Just smaller class is inserted. */
2652 unsigned int smaller_index = newclasses[0]->members.length () <
2653 newclasses[1]->members.length () ?
2655 optimizer->worklist_push (newclasses[smaller_index]);
2658 if (dump_file && (dump_flags & TDF_DETAILS))
2660 fprintf (dump_file, " congruence class splitted:\n");
2661 cls->dump (dump_file, 4);
2663 fprintf (dump_file, " newly created groups:\n");
2664 for (unsigned int i = 0; i < 2; i++)
2665 newclasses[i]->dump (dump_file, 4);
2668 /* Release class if not presented in work list. */
2677 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2678 Bitmap stack BMSTACK is used for bitmap allocation. */
2681 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
2684 hash_map <congruence_class *, bitmap> split_map;
2686 for (unsigned int i = 0; i < cls->members.length (); i++)
2688 sem_item *item = cls->members[i];
2690 /* Iterate all usages that have INDEX as usage of the item. */
2691 for (unsigned int j = 0; j < item->usages.length (); j++)
2693 sem_usage_pair *usage = item->usages[j];
2695 if (usage->index != index)
2698 bitmap *slot = split_map.get (usage->item->cls);
2703 b = BITMAP_ALLOC (&m_bmstack);
2704 split_map.put (usage->item->cls, b);
2710 gcc_checking_assert (usage->item->cls);
2711 gcc_checking_assert (usage->item->index_in_class <
2712 usage->item->cls->members.length ());
2715 bitmap_set_bit (b, usage->item->index_in_class);
2719 traverse_split_pair pair;
2720 pair.optimizer = this;
2723 splitter_class_removed = false;
2725 <traverse_split_pair *, sem_item_optimizer::traverse_congruence_split> (&pair);
2727 /* Bitmap clean-up. */
2729 <traverse_split_pair *, sem_item_optimizer::release_split_map> (NULL);
2732 /* Every usage of a congruence class CLS is a candidate that can split the
2733 collection of classes. Bitmap stack BMSTACK is used for bitmap
2737 sem_item_optimizer::do_congruence_step (congruence_class *cls)
2742 bitmap usage = BITMAP_ALLOC (&m_bmstack);
2744 for (unsigned int i = 0; i < cls->members.length (); i++)
2745 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
2747 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
2749 if (dump_file && (dump_flags & TDF_DETAILS))
2750 fprintf (dump_file, " processing congruece step for class: %u, index: %u\n",
2753 do_congruence_step_for_index (cls, i);
2755 if (splitter_class_removed)
2759 BITMAP_FREE (usage);
2762 /* Adds a newly created congruence class CLS to worklist. */
2765 sem_item_optimizer::worklist_push (congruence_class *cls)
2767 /* Return if the class CLS is already presented in work list. */
2768 if (cls->in_worklist)
2771 cls->in_worklist = true;
2772 worklist.push_back (cls);
2775 /* Pops a class from worklist. */
2778 sem_item_optimizer::worklist_pop (void)
2780 congruence_class *cls;
2782 while (!worklist.empty ())
2784 cls = worklist.front ();
2785 worklist.pop_front ();
2786 if (cls->in_worklist)
2788 cls->in_worklist = false;
2794 /* Work list item was already intended to be removed.
2795 The only reason for doing it is to split a class.
2796 Thus, the class CLS is deleted. */
2804 /* Iterative congruence reduction function. */
2807 sem_item_optimizer::process_cong_reduction (void)
2809 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2810 it != m_classes.end (); ++it)
2811 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2812 if ((*it)->classes[i]->is_class_used ())
2813 worklist_push ((*it)->classes[i]);
2816 fprintf (dump_file, "Worklist has been filled with: %lu\n",
2817 (unsigned long) worklist.size ());
2819 if (dump_file && (dump_flags & TDF_DETAILS))
2820 fprintf (dump_file, "Congruence class reduction\n");
2822 congruence_class *cls;
2824 /* Process complete congruence reduction. */
2825 while ((cls = worklist_pop ()) != NULL)
2826 do_congruence_step (cls);
2828 /* Subdivide newly created classes according to references. */
2829 unsigned new_classes = subdivide_classes_by_sensitive_refs ();
2832 fprintf (dump_file, "Address reference subdivision created: %u "
2833 "new classes.\n", new_classes);
2836 /* Debug function prints all informations about congruence classes. */
2839 sem_item_optimizer::dump_cong_classes (void)
2845 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2846 m_classes_count, (unsigned long) m_classes.elements(), m_items.length ());
2848 /* Histogram calculation. */
2849 unsigned int max_index = 0;
2850 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
2852 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2853 it != m_classes.end (); ++it)
2855 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2857 unsigned int c = (*it)->classes[i]->members.length ();
2865 "Class size histogram [num of members]: number of classe number of classess\n");
2867 for (unsigned int i = 0; i <= max_index; i++)
2869 fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
2871 fprintf (dump_file, "\n\n");
2874 if (dump_flags & TDF_DETAILS)
2875 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2876 it != m_classes.end (); ++it)
2878 fprintf (dump_file, " group: with %u classes:\n", (*it)->classes.length ());
2880 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2882 (*it)->classes[i]->dump (dump_file, 4);
2884 if(i < (*it)->classes.length () - 1)
2885 fprintf (dump_file, " ");
2892 /* After reduction is done, we can declare all items in a group
2893 to be equal. PREV_CLASS_COUNT is start number of classes
2894 before reduction. True is returned if there's a merge operation
2898 sem_item_optimizer::merge_classes (unsigned int prev_class_count)
2900 unsigned int item_count = m_items.length ();
2901 unsigned int class_count = m_classes_count;
2902 unsigned int equal_items = item_count - class_count;
2904 unsigned int non_singular_classes_count = 0;
2905 unsigned int non_singular_classes_sum = 0;
2907 bool merged_p = false;
2909 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2910 it != m_classes.end (); ++it)
2911 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2913 congruence_class *c = (*it)->classes[i];
2914 if (c->members.length () > 1)
2916 non_singular_classes_count++;
2917 non_singular_classes_sum += c->members.length ();
2923 fprintf (dump_file, "\nItem count: %u\n", item_count);
2924 fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
2925 prev_class_count, class_count);
2926 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
2927 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
2928 class_count ? 1.0f * item_count / class_count : 0.0f);
2929 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
2930 non_singular_classes_count ? 1.0f * non_singular_classes_sum /
2931 non_singular_classes_count : 0.0f,
2932 non_singular_classes_count);
2933 fprintf (dump_file, "Equal symbols: %u\n", equal_items);
2934 fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
2935 item_count ? 100.0f * equal_items / item_count : 0.0f);
2938 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2939 it != m_classes.end (); ++it)
2940 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2942 congruence_class *c = (*it)->classes[i];
2944 if (c->members.length () == 1)
2947 gcc_assert (c->members.length ());
2949 sem_item *source = c->members[0];
2951 for (unsigned int j = 1; j < c->members.length (); j++)
2953 sem_item *alias = c->members[j];
2957 fprintf (dump_file, "Semantic equality hit:%s->%s\n",
2958 source->name (), alias->name ());
2959 fprintf (dump_file, "Assembler symbol names:%s->%s\n",
2960 source->asm_name (), alias->asm_name ());
2963 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl)))
2967 "Merge operation is skipped due to no_icf "
2973 if (dump_file && (dump_flags & TDF_DETAILS))
2975 source->dump_to_file (dump_file);
2976 alias->dump_to_file (dump_file);
2979 if (source->merge (alias))
2987 /* Dump function prints all class members to a FILE with an INDENT. */
2990 congruence_class::dump (FILE *file, unsigned int indent) const
2992 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
2993 id, members[0]->get_hash (), members.length ());
2995 FPUTS_SPACES (file, indent + 2, "");
2996 for (unsigned i = 0; i < members.length (); i++)
2997 fprintf (file, "%s(%p/%u) ", members[i]->asm_name (), (void *) members[i]->decl,
2998 members[i]->node->order);
3000 fprintf (file, "\n");
3003 /* Returns true if there's a member that is used from another group. */
3006 congruence_class::is_class_used (void)
3008 for (unsigned int i = 0; i < members.length (); i++)
3009 if (members[i]->usages.length ())
3015 /* Initialization and computation of symtab node hash, there data
3016 are propagated later on. */
3018 static sem_item_optimizer *optimizer = NULL;
3020 /* Generate pass summary for IPA ICF pass. */
3023 ipa_icf_generate_summary (void)
3026 optimizer = new sem_item_optimizer ();
3028 optimizer->register_hooks ();
3029 optimizer->parse_funcs_and_vars ();
3032 /* Write pass summary for IPA ICF pass. */
3035 ipa_icf_write_summary (void)
3037 gcc_assert (optimizer);
3039 optimizer->write_summary ();
3042 /* Read pass summary for IPA ICF pass. */
3045 ipa_icf_read_summary (void)
3048 optimizer = new sem_item_optimizer ();
3050 optimizer->read_summary ();
3051 optimizer->register_hooks ();
3054 /* Semantic equality exection function. */
3057 ipa_icf_driver (void)
3059 gcc_assert (optimizer);
3061 bool merged_p = optimizer->execute ();
3066 return merged_p ? TODO_remove_functions : 0;
3069 const pass_data pass_data_ipa_icf =
3071 IPA_PASS, /* type */
3073 OPTGROUP_IPA, /* optinfo_flags */
3074 TV_IPA_ICF, /* tv_id */
3075 0, /* properties_required */
3076 0, /* properties_provided */
3077 0, /* properties_destroyed */
3078 0, /* todo_flags_start */
3079 0, /* todo_flags_finish */
3082 class pass_ipa_icf : public ipa_opt_pass_d
3085 pass_ipa_icf (gcc::context *ctxt)
3086 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
3087 ipa_icf_generate_summary, /* generate_summary */
3088 ipa_icf_write_summary, /* write_summary */
3089 ipa_icf_read_summary, /* read_summary */
3091 write_optimization_summary */
3093 read_optimization_summary */
3094 NULL, /* stmt_fixup */
3095 0, /* function_transform_todo_flags_start */
3096 NULL, /* function_transform */
3097 NULL) /* variable_transform */
3100 /* opt_pass methods: */
3101 virtual bool gate (function *)
3103 return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
3106 virtual unsigned int execute (function *)
3108 return ipa_icf_driver();
3110 }; // class pass_ipa_icf
3112 } // ipa_icf namespace
3115 make_pass_ipa_icf (gcc::context *ctxt)
3117 return new ipa_icf::pass_ipa_icf (ctxt);