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;
351 /* Merging two definitions with a reference to equivalent vtables, but
352 belonging to a different type may result in ipa-polymorphic-call analysis
353 giving a wrong answer about the dynamic type of instance. */
354 if (is_a <varpool_node *> (n1)
355 && (DECL_VIRTUAL_P (n1->decl) || DECL_VIRTUAL_P (n2->decl))
356 && (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl)
357 || !types_must_be_same_for_odr (DECL_CONTEXT (n1->decl),
358 DECL_CONTEXT (n2->decl))))
359 return return_false_with_msg
360 ("references to virtual tables can not be merged");
362 if (address && n1->equal_address_to (n2) == 1)
364 if (!address && n1->semantically_equivalent_p (n2))
367 n1 = n1->ultimate_alias_target (&avail1);
368 n2 = n2->ultimate_alias_target (&avail2);
370 if (avail1 >= AVAIL_INTERPOSABLE && ignored_nodes.get (n1)
371 && avail2 >= AVAIL_INTERPOSABLE && ignored_nodes.get (n2))
374 return return_false_with_msg ("different references");
377 /* If cgraph edges E1 and E2 are indirect calls, verify that
378 ECF flags are the same. */
380 bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
382 if (e1->indirect_info && e2->indirect_info)
384 int e1_flags = e1->indirect_info->ecf_flags;
385 int e2_flags = e2->indirect_info->ecf_flags;
387 if (e1_flags != e2_flags)
388 return return_false_with_msg ("ICF flags are different");
390 else if (e1->indirect_info || e2->indirect_info)
396 /* Fast equality function based on knowledge known in WPA. */
399 sem_function::equals_wpa (sem_item *item,
400 hash_map <symtab_node *, sem_item *> &ignored_nodes)
402 gcc_assert (item->type == FUNC);
404 m_compared_func = static_cast<sem_function *> (item);
406 if (arg_types.length () != m_compared_func->arg_types.length ())
407 return return_false_with_msg ("different number of arguments");
409 /* Compare special function DECL attributes. */
410 if (DECL_FUNCTION_PERSONALITY (decl)
411 != DECL_FUNCTION_PERSONALITY (item->decl))
412 return return_false_with_msg ("function personalities are different");
414 if (DECL_DISREGARD_INLINE_LIMITS (decl)
415 != DECL_DISREGARD_INLINE_LIMITS (item->decl))
416 return return_false_with_msg ("DECL_DISREGARD_INLINE_LIMITS are different");
418 if (DECL_DECLARED_INLINE_P (decl) != DECL_DECLARED_INLINE_P (item->decl))
419 return return_false_with_msg ("inline attributes are different");
421 if (DECL_IS_OPERATOR_NEW (decl) != DECL_IS_OPERATOR_NEW (item->decl))
422 return return_false_with_msg ("operator new flags are different");
424 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
425 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item->decl))
426 return return_false_with_msg ("intrument function entry exit "
427 "attributes are different");
429 if (DECL_NO_LIMIT_STACK (decl) != DECL_NO_LIMIT_STACK (item->decl))
430 return return_false_with_msg ("no stack limit attributes are different");
432 if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
433 return return_false_with_msg ("decl_or_type flags are different");
435 /* Checking function TARGET and OPTIMIZATION flags. */
436 cl_target_option *tar1 = target_opts_for_fn (decl);
437 cl_target_option *tar2 = target_opts_for_fn (item->decl);
439 if (tar1 != tar2 && !cl_target_option_eq (tar1, tar2))
441 if (dump_file && (dump_flags & TDF_DETAILS))
443 fprintf (dump_file, "target flags difference");
444 cl_target_option_print_diff (dump_file, 2, tar1, tar2);
447 return return_false_with_msg ("Target flags are different");
450 cl_optimization *opt1 = opts_for_fn (decl);
451 cl_optimization *opt2 = opts_for_fn (item->decl);
453 if (opt1 != opt2 && memcmp (opt1, opt2, sizeof(cl_optimization)))
455 if (dump_file && (dump_flags & TDF_DETAILS))
457 fprintf (dump_file, "optimization flags difference");
458 cl_optimization_print_diff (dump_file, 2, opt1, opt2);
461 return return_false_with_msg ("optimization flags are different");
464 /* Result type checking. */
465 if (!func_checker::compatible_types_p (result_type,
466 m_compared_func->result_type))
467 return return_false_with_msg ("result types are different");
469 /* Checking types of arguments. */
470 for (unsigned i = 0; i < arg_types.length (); i++)
472 /* This guard is here for function pointer with attributes (pr59927.c). */
473 if (!arg_types[i] || !m_compared_func->arg_types[i])
474 return return_false_with_msg ("NULL argument type");
476 /* Polymorphic comparison is executed just for non-leaf functions. */
477 bool is_not_leaf = get_node ()->callees != NULL
478 || get_node ()->indirect_calls != NULL;
480 if (!func_checker::compatible_types_p (arg_types[i],
481 m_compared_func->arg_types[i],
482 is_not_leaf, i == 0))
483 return return_false_with_msg ("argument type is different");
484 if (POINTER_TYPE_P (arg_types[i])
485 && (TYPE_RESTRICT (arg_types[i])
486 != TYPE_RESTRICT (m_compared_func->arg_types[i])))
487 return return_false_with_msg ("argument restrict flag mismatch");
490 if (node->num_references () != item->node->num_references ())
491 return return_false_with_msg ("different number of references");
493 if (comp_type_attributes (TREE_TYPE (decl),
494 TREE_TYPE (item->decl)) != 1)
495 return return_false_with_msg ("different type attributes");
497 ipa_ref *ref = NULL, *ref2 = NULL;
498 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
500 item->node->iterate_reference (i, ref2);
502 if (!compare_cgraph_references (ignored_nodes, ref->referred,
504 ref->address_matters_p ()))
508 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
509 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
513 if (!compare_cgraph_references (ignored_nodes, e1->callee,
517 e1 = e1->next_callee;
518 e2 = e2->next_callee;
522 return return_false_with_msg ("different number of edges");
527 /* Returns true if the item equals to ITEM given as argument. */
530 sem_function::equals (sem_item *item,
531 hash_map <symtab_node *, sem_item *> &ignored_nodes)
533 gcc_assert (item->type == FUNC);
534 bool eq = equals_private (item, ignored_nodes);
536 if (m_checker != NULL)
542 if (dump_file && (dump_flags & TDF_DETAILS))
544 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
545 name(), item->name (), node->order, item->node->order, asm_name (),
546 item->asm_name (), eq ? "true" : "false");
551 /* Processes function equality comparison. */
554 sem_function::equals_private (sem_item *item,
555 hash_map <symtab_node *, sem_item *> &ignored_nodes)
557 if (item->type != FUNC)
560 basic_block bb1, bb2;
562 edge_iterator ei1, ei2;
566 m_compared_func = static_cast<sem_function *> (item);
568 gcc_assert (decl != item->decl);
570 if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
571 || edge_count != m_compared_func->edge_count
572 || cfg_checksum != m_compared_func->cfg_checksum)
573 return return_false ();
575 if (!equals_wpa (item, ignored_nodes))
578 /* Checking function arguments. */
579 tree decl1 = DECL_ATTRIBUTES (decl);
580 tree decl2 = DECL_ATTRIBUTES (m_compared_func->decl);
582 m_checker = new func_checker (decl, m_compared_func->decl,
583 compare_polymorphic_p (),
586 &m_compared_func->refs_set);
590 return return_false ();
592 if (get_attribute_name (decl1) != get_attribute_name (decl2))
593 return return_false ();
595 tree attr_value1 = TREE_VALUE (decl1);
596 tree attr_value2 = TREE_VALUE (decl2);
598 if (attr_value1 && attr_value2)
600 bool ret = m_checker->compare_operand (TREE_VALUE (attr_value1),
601 TREE_VALUE (attr_value2));
603 return return_false_with_msg ("attribute values are different");
605 else if (!attr_value1 && !attr_value2)
608 return return_false ();
610 decl1 = TREE_CHAIN (decl1);
611 decl2 = TREE_CHAIN (decl2);
615 return return_false();
618 for (arg1 = DECL_ARGUMENTS (decl),
619 arg2 = DECL_ARGUMENTS (m_compared_func->decl);
620 arg1; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2))
621 if (!m_checker->compare_decl (arg1, arg2))
622 return return_false ();
624 /* Fill-up label dictionary. */
625 for (unsigned i = 0; i < bb_sorted.length (); ++i)
627 m_checker->parse_labels (bb_sorted[i]);
628 m_checker->parse_labels (m_compared_func->bb_sorted[i]);
631 /* Checking all basic blocks. */
632 for (unsigned i = 0; i < bb_sorted.length (); ++i)
633 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
634 return return_false();
636 dump_message ("All BBs are equal\n");
638 auto_vec <int> bb_dict;
640 /* Basic block edges check. */
641 for (unsigned i = 0; i < bb_sorted.length (); ++i)
643 bb1 = bb_sorted[i]->bb;
644 bb2 = m_compared_func->bb_sorted[i]->bb;
646 ei2 = ei_start (bb2->preds);
648 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
652 if (e1->flags != e2->flags)
653 return return_false_with_msg ("flags comparison returns false");
655 if (!bb_dict_test (&bb_dict, e1->src->index, e2->src->index))
656 return return_false_with_msg ("edge comparison returns false");
658 if (!bb_dict_test (&bb_dict, e1->dest->index, e2->dest->index))
659 return return_false_with_msg ("BB comparison returns false");
661 if (!m_checker->compare_edge (e1, e2))
662 return return_false_with_msg ("edge comparison returns false");
668 /* Basic block PHI nodes comparison. */
669 for (unsigned i = 0; i < bb_sorted.length (); i++)
670 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
671 return return_false_with_msg ("PHI node comparison returns false");
676 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
677 Helper for call_for_symbol_thunks_and_aliases. */
680 set_local (cgraph_node *node, void *data)
682 node->local.local = data != NULL;
686 /* TREE_ADDRESSABLE of NODE to true.
687 Helper for call_for_symbol_thunks_and_aliases. */
690 set_addressable (varpool_node *node, void *)
692 TREE_ADDRESSABLE (node->decl) = 1;
696 /* Clear DECL_RTL of NODE.
697 Helper for call_for_symbol_thunks_and_aliases. */
700 clear_decl_rtl (symtab_node *node, void *)
702 SET_DECL_RTL (node->decl, NULL);
706 /* Redirect all callers of N and its aliases to TO. Remove aliases if
707 possible. Return number of redirections made. */
710 redirect_all_callers (cgraph_node *n, cgraph_node *to)
714 cgraph_edge *e = n->callers;
718 /* Redirecting thunks to interposable symbols or symbols in other sections
719 may not be supported by target output code. Play safe for now and
720 punt on redirection. */
721 if (!e->caller->thunk.thunk_p)
723 struct cgraph_edge *nexte = e->next_caller;
724 e->redirect_callee (to);
731 for (unsigned i = 0; n->iterate_direct_aliases (i, ref);)
733 bool removed = false;
734 cgraph_node *n_alias = dyn_cast <cgraph_node *> (ref->referring);
736 if ((DECL_COMDAT_GROUP (n->decl)
737 && (DECL_COMDAT_GROUP (n->decl)
738 == DECL_COMDAT_GROUP (n_alias->decl)))
739 || (n_alias->get_availability () > AVAIL_INTERPOSABLE
740 && n->get_availability () > AVAIL_INTERPOSABLE))
742 nredirected += redirect_all_callers (n_alias, to);
743 if (n_alias->can_remove_if_no_direct_calls_p ()
744 && !n_alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
746 && !n_alias->has_aliases_p ())
755 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
759 sem_function::merge (sem_item *alias_item)
761 gcc_assert (alias_item->type == FUNC);
763 sem_function *alias_func = static_cast<sem_function *> (alias_item);
765 cgraph_node *original = get_node ();
766 cgraph_node *local_original = NULL;
767 cgraph_node *alias = alias_func->get_node ();
769 bool create_wrapper = false;
770 bool create_alias = false;
771 bool redirect_callers = false;
774 bool original_discardable = false;
775 bool original_discarded = false;
777 bool original_address_matters = original->address_matters_p ();
778 bool alias_address_matters = alias->address_matters_p ();
780 if (DECL_NO_INLINE_WARNING_P (original->decl)
781 != DECL_NO_INLINE_WARNING_P (alias->decl))
786 "DECL_NO_INLINE_WARNING mismatch.\n\n");
790 /* Do not attempt to mix functions from different user sections;
791 we do not know what user intends with those. */
792 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
793 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
794 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
799 "original and alias are in different sections.\n\n");
803 /* See if original is in a section that can be discarded if the main
804 symbol is not used. */
806 if (original->can_be_discarded_p ())
807 original_discardable = true;
808 /* Also consider case where we have resolution info and we know that
809 original's definition is not going to be used. In this case we can not
810 create alias to original. */
811 if (node->resolution != LDPR_UNKNOWN
812 && !decl_binds_to_current_def_p (node->decl))
813 original_discardable = original_discarded = true;
815 /* Creating a symtab alias is the optimal way to merge.
816 It however can not be used in the following cases:
818 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
819 2) if ORIGINAL is in a section that may be discarded by linker or if
820 it is an external functions where we can not create an alias
821 (ORIGINAL_DISCARDABLE)
822 3) if target do not support symbol aliases.
823 4) original and alias lie in different comdat groups.
825 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
826 and/or redirect all callers from ALIAS to ORIGINAL. */
827 if ((original_address_matters && alias_address_matters)
828 || (original_discardable
829 && (!DECL_COMDAT_GROUP (alias->decl)
830 || (DECL_COMDAT_GROUP (alias->decl)
831 != DECL_COMDAT_GROUP (original->decl))))
832 || original_discarded
833 || !sem_item::target_supports_symbol_aliases_p ()
834 || DECL_COMDAT_GROUP (alias->decl) != DECL_COMDAT_GROUP (original->decl))
836 /* First see if we can produce wrapper. */
838 /* Do not turn function in one comdat group into wrapper to another
839 comdat group. Other compiler producing the body of the
840 another comdat group may make opossite decision and with unfortunate
841 linker choices this may close a loop. */
842 if (DECL_COMDAT_GROUP (original->decl) && DECL_COMDAT_GROUP (alias->decl)
843 && (DECL_COMDAT_GROUP (alias->decl)
844 != DECL_COMDAT_GROUP (original->decl)))
848 "Wrapper cannot be created because of COMDAT\n");
850 else if (DECL_STATIC_CHAIN (alias->decl))
854 "Can not create wrapper of nested functions.\n");
856 /* TODO: We can also deal with variadic functions never calling
858 else if (stdarg_p (TREE_TYPE (alias->decl)))
862 "can not create wrapper of stdarg function.\n");
864 else if (inline_summaries
865 && inline_summaries->get (alias)->self_size <= 2)
868 fprintf (dump_file, "Wrapper creation is not "
869 "profitable (function is too small).\n");
871 /* If user paid attention to mark function noinline, assume it is
872 somewhat special and do not try to turn it into a wrapper that can
873 not be undone by inliner. */
874 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
877 fprintf (dump_file, "Wrappers are not created for noinline.\n");
880 create_wrapper = true;
882 /* We can redirect local calls in the case both alias and orignal
883 are not interposable. */
885 = alias->get_availability () > AVAIL_INTERPOSABLE
886 && original->get_availability () > AVAIL_INTERPOSABLE
887 && !alias->instrumented_version;
889 if (!redirect_callers && !create_wrapper)
892 fprintf (dump_file, "Not unifying; can not redirect callers nor "
893 "produce wrapper\n\n");
897 /* Work out the symbol the wrapper should call.
898 If ORIGINAL is interposable, we need to call a local alias.
899 Also produce local alias (if possible) as an optimization.
901 Local aliases can not be created inside comdat groups because that
902 prevents inlining. */
903 if (!original_discardable && !original->get_comdat_group ())
906 = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
908 && original->get_availability () > AVAIL_INTERPOSABLE)
909 local_original = original;
911 /* If we can not use local alias, fallback to the original
913 else if (original->get_availability () > AVAIL_INTERPOSABLE)
914 local_original = original;
916 /* If original is COMDAT local, we can not really redirect calls outside
917 of its comdat group to it. */
918 if (original->comdat_local_p ())
919 redirect_callers = false;
923 fprintf (dump_file, "Not unifying; "
924 "can not produce local alias.\n\n");
928 if (!redirect_callers && !create_wrapper)
931 fprintf (dump_file, "Not unifying; "
932 "can not redirect callers nor produce a wrapper\n\n");
936 && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
938 && !alias->can_remove_if_no_direct_calls_p ())
941 fprintf (dump_file, "Not unifying; can not make wrapper and "
942 "function has other uses than direct calls\n\n");
949 if (redirect_callers)
951 int nredirected = redirect_all_callers (alias, local_original);
955 alias->icf_merged = true;
956 local_original->icf_merged = true;
958 if (dump_file && nredirected)
959 fprintf (dump_file, "%i local calls have been "
960 "redirected.\n", nredirected);
963 /* If all callers was redirected, do not produce wrapper. */
964 if (alias->can_remove_if_no_direct_calls_p ()
965 && !alias->has_aliases_p ())
967 create_wrapper = false;
970 gcc_assert (!create_alias);
972 else if (create_alias)
974 alias->icf_merged = true;
976 /* Remove the function's body. */
977 ipa_merge_profiles (original, alias);
978 alias->release_body (true);
980 /* Notice global symbol possibly produced RTL. */
981 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
984 /* Create the alias. */
985 cgraph_node::create_alias (alias_func->decl, decl);
986 alias->resolve_alias (original);
988 original->call_for_symbol_thunks_and_aliases
989 (set_local, (void *)(size_t) original->local_p (), true);
992 fprintf (dump_file, "Unified; Function alias has been created.\n\n");
996 gcc_assert (!create_alias);
997 alias->icf_merged = true;
998 local_original->icf_merged = true;
1000 ipa_merge_profiles (local_original, alias, true);
1001 alias->create_wrapper (local_original);
1004 fprintf (dump_file, "Unified; Wrapper has been created.\n\n");
1007 /* It's possible that redirection can hit thunks that block
1008 redirection opportunities. */
1009 gcc_assert (alias->icf_merged || remove || redirect_callers);
1010 original->icf_merged = true;
1012 /* Inform the inliner about cross-module merging. */
1013 if ((original->lto_file_data || alias->lto_file_data)
1014 && original->lto_file_data != alias->lto_file_data)
1015 local_original->merged = original->merged = true;
1019 ipa_merge_profiles (original, alias);
1020 alias->release_body ();
1022 alias->body_removed = true;
1023 alias->icf_merged = true;
1025 fprintf (dump_file, "Unified; Function body was removed.\n");
1031 /* Semantic item initialization function. */
1034 sem_function::init (void)
1037 get_node ()->get_untransformed_body ();
1039 tree fndecl = node->decl;
1040 function *func = DECL_STRUCT_FUNCTION (fndecl);
1043 gcc_assert (SSANAMES (func));
1045 ssa_names_size = SSANAMES (func)->length ();
1049 region_tree = func->eh->region_tree;
1051 /* iterating all function arguments. */
1052 arg_count = count_formal_params (fndecl);
1054 edge_count = n_edges_for_fn (func);
1055 cfg_checksum = coverage_compute_cfg_checksum (func);
1057 inchash::hash hstate;
1060 FOR_EACH_BB_FN (bb, func)
1062 unsigned nondbg_stmt_count = 0;
1065 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
1067 cfg_checksum = iterative_hash_host_wide_int (e->flags,
1070 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1073 gimple stmt = gsi_stmt (gsi);
1075 if (gimple_code (stmt) != GIMPLE_DEBUG
1076 && gimple_code (stmt) != GIMPLE_PREDICT)
1078 hash_stmt (stmt, hstate);
1079 nondbg_stmt_count++;
1083 gcode_hash = hstate.end ();
1084 bb_sizes.safe_push (nondbg_stmt_count);
1086 /* Inserting basic block to hash table. */
1087 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
1088 EDGE_COUNT (bb->preds)
1089 + EDGE_COUNT (bb->succs));
1091 bb_sorted.safe_push (semantic_bb);
1097 /* Accumulate to HSTATE a hash of expression EXP.
1098 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1099 and DECL equality classes. */
1102 sem_item::add_expr (const_tree exp, inchash::hash &hstate)
1104 if (exp == NULL_TREE)
1106 hstate.merge_hash (0);
1110 /* Handled component can be matched in a cureful way proving equivalence
1111 even if they syntactically differ. Just skip them. */
1113 while (handled_component_p (exp))
1114 exp = TREE_OPERAND (exp, 0);
1116 enum tree_code code = TREE_CODE (exp);
1117 hstate.add_int (code);
1121 /* Use inchash::add_expr for everything that is LTO stable. */
1129 inchash::add_expr (exp, hstate);
1133 unsigned HOST_WIDE_INT idx;
1136 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1138 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp), idx, value)
1140 add_expr (value, hstate);
1145 add_expr (get_base_address (TREE_OPERAND (exp, 0)), hstate);
1151 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1154 case POINTER_PLUS_EXPR:
1157 add_expr (TREE_OPERAND (exp, 0), hstate);
1158 add_expr (TREE_OPERAND (exp, 1), hstate);
1162 inchash::hash one, two;
1163 add_expr (TREE_OPERAND (exp, 0), one);
1164 add_expr (TREE_OPERAND (exp, 1), two);
1165 hstate.add_commutative (one, two);
1169 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1170 return add_expr (TREE_OPERAND (exp, 0), hstate);
1176 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1179 sem_function::hash_stmt (gimple stmt, inchash::hash &hstate)
1181 enum gimple_code code = gimple_code (stmt);
1183 hstate.add_int (code);
1188 if (commutative_tree_code (gimple_assign_rhs_code (stmt))
1189 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1191 inchash::hash one, two;
1193 add_expr (gimple_assign_rhs1 (stmt), one);
1194 add_expr (gimple_assign_rhs2 (stmt), two);
1195 hstate.add_commutative (one, two);
1196 add_expr (gimple_assign_lhs (stmt), hstate);
1199 /* ... fall through ... */
1205 /* All these statements are equivalent if their operands are. */
1206 for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1207 add_expr (gimple_op (stmt, i), hstate);
1214 /* Return true if polymorphic comparison must be processed. */
1217 sem_function::compare_polymorphic_p (void)
1219 return get_node ()->callees != NULL
1220 || get_node ()->indirect_calls != NULL
1221 || m_compared_func->get_node ()->callees != NULL
1222 || m_compared_func->get_node ()->indirect_calls != NULL;
1225 /* For a given call graph NODE, the function constructs new
1226 semantic function item. */
1229 sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
1231 tree fndecl = node->decl;
1232 function *func = DECL_STRUCT_FUNCTION (fndecl);
1234 /* TODO: add support for thunks. */
1236 if (!func || !node->has_gimple_body_p ())
1239 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
1242 sem_function *f = new sem_function (node, 0, stack);
1249 /* Parses function arguments and result type. */
1252 sem_function::parse_tree_args (void)
1256 if (arg_types.exists ())
1257 arg_types.release ();
1259 arg_types.create (4);
1260 tree fnargs = DECL_ARGUMENTS (decl);
1262 for (tree parm = fnargs; parm; parm = DECL_CHAIN (parm))
1263 arg_types.safe_push (DECL_ARG_TYPE (parm));
1265 /* Function result type. */
1266 result = DECL_RESULT (decl);
1267 result_type = result ? TREE_TYPE (result) : NULL;
1269 /* During WPA, we can get arguments by following method. */
1272 tree type = TYPE_ARG_TYPES (TREE_TYPE (decl));
1273 for (tree parm = type; parm; parm = TREE_CHAIN (parm))
1274 arg_types.safe_push (TYPE_CANONICAL (TREE_VALUE (parm)));
1276 result_type = TREE_TYPE (TREE_TYPE (decl));
1280 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1281 return true if phi nodes are semantically equivalent in these blocks . */
1284 sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
1286 gphi_iterator si1, si2;
1288 unsigned size1, size2, i;
1292 gcc_assert (bb1 != NULL);
1293 gcc_assert (bb2 != NULL);
1295 si2 = gsi_start_phis (bb2);
1296 for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
1299 gsi_next_nonvirtual_phi (&si1);
1300 gsi_next_nonvirtual_phi (&si2);
1302 if (gsi_end_p (si1) && gsi_end_p (si2))
1305 if (gsi_end_p (si1) || gsi_end_p (si2))
1306 return return_false();
1311 tree phi_result1 = gimple_phi_result (phi1);
1312 tree phi_result2 = gimple_phi_result (phi2);
1314 if (!m_checker->compare_operand (phi_result1, phi_result2))
1315 return return_false_with_msg ("PHI results are different");
1317 size1 = gimple_phi_num_args (phi1);
1318 size2 = gimple_phi_num_args (phi2);
1321 return return_false ();
1323 for (i = 0; i < size1; ++i)
1325 t1 = gimple_phi_arg (phi1, i)->def;
1326 t2 = gimple_phi_arg (phi2, i)->def;
1328 if (!m_checker->compare_operand (t1, t2))
1329 return return_false ();
1331 e1 = gimple_phi_arg_edge (phi1, i);
1332 e2 = gimple_phi_arg_edge (phi2, i);
1334 if (!m_checker->compare_edge (e1, e2))
1335 return return_false ();
1344 /* Returns true if tree T can be compared as a handled component. */
1347 sem_function::icf_handled_component_p (tree t)
1349 tree_code tc = TREE_CODE (t);
1351 return ((handled_component_p (t))
1352 || tc == ADDR_EXPR || tc == MEM_REF || tc == REALPART_EXPR
1353 || tc == IMAGPART_EXPR || tc == OBJ_TYPE_REF);
1356 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1357 corresponds to TARGET. */
1360 sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
1365 if (bb_dict->length () <= (unsigned)source)
1366 bb_dict->safe_grow_cleared (source + 1);
1368 if ((*bb_dict)[source] == 0)
1370 (*bb_dict)[source] = target;
1374 return (*bb_dict)[source] == target;
1377 /* Iterates all tree types in T1 and T2 and returns true if all types
1378 are compatible. If COMPARE_POLYMORPHIC is set to true,
1379 more strict comparison is executed. */
1382 sem_function::compare_type_list (tree t1, tree t2, bool compare_polymorphic)
1390 while (t1 != NULL && t2 != NULL)
1392 tv1 = TREE_VALUE (t1);
1393 tv2 = TREE_VALUE (t2);
1395 tc1 = TREE_CODE (tv1);
1396 tc2 = TREE_CODE (tv2);
1398 if (tc1 == NOP_EXPR && tc2 == NOP_EXPR)
1400 else if (tc1 == NOP_EXPR || tc2 == NOP_EXPR)
1402 else if (!func_checker::compatible_types_p (tv1, tv2, compare_polymorphic))
1405 t1 = TREE_CHAIN (t1);
1406 t2 = TREE_CHAIN (t2);
1413 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1415 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
1419 /* Constructor based on varpool node _NODE with computed hash _HASH.
1420 Bitmap STACK is used for memory allocation. */
1422 sem_variable::sem_variable (varpool_node *node, hashval_t _hash,
1423 bitmap_obstack *stack): sem_item(VAR,
1426 gcc_checking_assert (node);
1427 gcc_checking_assert (get_node ());
1430 /* Fast equality function based on knowledge known in WPA. */
1433 sem_variable::equals_wpa (sem_item *item,
1434 hash_map <symtab_node *, sem_item *> &ignored_nodes)
1436 gcc_assert (item->type == VAR);
1438 if (node->num_references () != item->node->num_references ())
1439 return return_false_with_msg ("different number of references");
1441 if (DECL_TLS_MODEL (decl) || DECL_TLS_MODEL (item->decl))
1442 return return_false_with_msg ("TLS model");
1444 if (DECL_ALIGN (decl) != DECL_ALIGN (item->decl))
1445 return return_false_with_msg ("alignment mismatch");
1447 if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
1448 return return_false_with_msg ("Virtual flag mismatch");
1450 if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
1451 && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
1452 || !operand_equal_p (DECL_SIZE (decl),
1453 DECL_SIZE (item->decl), OEP_ONLY_CONST)))
1454 return return_false_with_msg ("size mismatch");
1456 /* Do not attempt to mix data from different user sections;
1457 we do not know what user intends with those. */
1458 if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
1459 || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
1460 && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
1461 return return_false_with_msg ("user section mismatch");
1463 if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
1464 return return_false_with_msg ("text section");
1466 ipa_ref *ref = NULL, *ref2 = NULL;
1467 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
1469 item->node->iterate_reference (i, ref2);
1471 if (!compare_cgraph_references (ignored_nodes,
1472 ref->referred, ref2->referred,
1473 ref->address_matters_p ()))
1476 /* DECL_FINAL_P flag on methods referred by virtual tables is used
1477 to decide on completeness possible_polymorphic_call_targets lists
1478 and therefore it must match. */
1479 if ((DECL_VIRTUAL_P (decl) || DECL_VIRTUAL_P (item->decl))
1480 && (DECL_VIRTUAL_P (ref->referred->decl)
1481 || DECL_VIRTUAL_P (ref2->referred->decl))
1482 && ((DECL_VIRTUAL_P (ref->referred->decl)
1483 != DECL_VIRTUAL_P (ref2->referred->decl))
1484 || (DECL_FINAL_P (ref->referred->decl)
1485 != DECL_FINAL_P (ref2->referred->decl))))
1486 return return_false_with_msg ("virtual or final flag mismatch");
1492 /* Returns true if the item equals to ITEM given as argument. */
1494 /* Returns true if the item equals to ITEM given as argument. */
1497 sem_variable::equals (sem_item *item,
1498 hash_map <symtab_node *, sem_item *> &)
1500 gcc_assert (item->type == VAR);
1503 if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
1504 dyn_cast <varpool_node *>(node)->get_constructor ();
1505 if (DECL_INITIAL (item->decl) == error_mark_node && in_lto_p)
1506 dyn_cast <varpool_node *>(item->node)->get_constructor ();
1508 /* As seen in PR ipa/65303 we have to compare variables types. */
1509 if (!func_checker::compatible_types_p (TREE_TYPE (decl),
1510 TREE_TYPE (item->decl)))
1511 return return_false_with_msg ("variables types are different");
1513 ret = sem_variable::equals (DECL_INITIAL (decl),
1514 DECL_INITIAL (item->node->decl));
1515 if (dump_file && (dump_flags & TDF_DETAILS))
1517 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1518 name(), item->name (), node->order, item->node->order, asm_name (),
1519 item->asm_name (), ret ? "true" : "false");
1524 /* Compares trees T1 and T2 for semantic equality. */
1527 sem_variable::equals (tree t1, tree t2)
1530 return return_with_debug (t1 == t2);
1533 tree_code tc1 = TREE_CODE (t1);
1534 tree_code tc2 = TREE_CODE (t2);
1537 return return_false_with_msg ("TREE_CODE mismatch");
1543 vec<constructor_elt, va_gc> *v1, *v2;
1544 unsigned HOST_WIDE_INT idx;
1546 enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
1547 if (typecode != TREE_CODE (TREE_TYPE (t2)))
1548 return return_false_with_msg ("constructor type mismatch");
1550 if (typecode == ARRAY_TYPE)
1552 HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
1553 /* For arrays, check that the sizes all match. */
1554 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
1556 || size_1 != int_size_in_bytes (TREE_TYPE (t2)))
1557 return return_false_with_msg ("constructor array size mismatch");
1559 else if (!func_checker::compatible_types_p (TREE_TYPE (t1),
1561 return return_false_with_msg ("constructor type incompatible");
1563 v1 = CONSTRUCTOR_ELTS (t1);
1564 v2 = CONSTRUCTOR_ELTS (t2);
1565 if (vec_safe_length (v1) != vec_safe_length (v2))
1566 return return_false_with_msg ("constructor number of elts mismatch");
1568 for (idx = 0; idx < vec_safe_length (v1); ++idx)
1570 constructor_elt *c1 = &(*v1)[idx];
1571 constructor_elt *c2 = &(*v2)[idx];
1573 /* Check that each value is the same... */
1574 if (!sem_variable::equals (c1->value, c2->value))
1576 /* ... and that they apply to the same fields! */
1577 if (!sem_variable::equals (c1->index, c2->index))
1584 tree x1 = TREE_OPERAND (t1, 0);
1585 tree x2 = TREE_OPERAND (t2, 0);
1586 tree y1 = TREE_OPERAND (t1, 1);
1587 tree y2 = TREE_OPERAND (t2, 1);
1589 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2),
1591 return return_false ();
1593 /* Type of the offset on MEM_REF does not matter. */
1594 return return_with_debug (sem_variable::equals (x1, x2)
1595 && wi::to_offset (y1)
1596 == wi::to_offset (y2));
1601 tree op1 = TREE_OPERAND (t1, 0);
1602 tree op2 = TREE_OPERAND (t2, 0);
1603 return sem_variable::equals (op1, op2);
1605 /* References to other vars/decls are compared using ipa-ref. */
1608 if (decl_in_symtab_p (t1) && decl_in_symtab_p (t2))
1610 return return_false_with_msg ("Declaration mismatch");
1612 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1613 need to process its VAR/FUNCTION references without relying on ipa-ref
1617 return return_false_with_msg ("Declaration mismatch");
1619 /* Integer constants are the same only if the same width of type. */
1620 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1621 return return_false_with_msg ("INTEGER_CST precision mismatch");
1622 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1623 return return_false_with_msg ("INTEGER_CST mode mismatch");
1624 return return_with_debug (tree_int_cst_equal (t1, t2));
1626 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1627 return return_false_with_msg ("STRING_CST mode mismatch");
1628 if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
1629 return return_false_with_msg ("STRING_CST length mismatch");
1630 if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
1631 TREE_STRING_LENGTH (t1)))
1632 return return_false_with_msg ("STRING_CST mismatch");
1635 /* Fixed constants are the same only if the same width of type. */
1636 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1637 return return_false_with_msg ("FIXED_CST precision mismatch");
1639 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
1640 TREE_FIXED_CST (t2)));
1642 return (sem_variable::equals (TREE_REALPART (t1), TREE_REALPART (t2))
1643 && sem_variable::equals (TREE_IMAGPART (t1), TREE_IMAGPART (t2)));
1645 /* Real constants are the same only if the same width of type. */
1646 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1647 return return_false_with_msg ("REAL_CST precision mismatch");
1648 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1),
1649 TREE_REAL_CST (t2)));
1654 if (VECTOR_CST_NELTS (t1) != VECTOR_CST_NELTS (t2))
1655 return return_false_with_msg ("VECTOR_CST nelts mismatch");
1657 for (i = 0; i < VECTOR_CST_NELTS (t1); ++i)
1658 if (!sem_variable::equals (VECTOR_CST_ELT (t1, i),
1659 VECTOR_CST_ELT (t2, i)))
1665 case ARRAY_RANGE_REF:
1667 tree x1 = TREE_OPERAND (t1, 0);
1668 tree x2 = TREE_OPERAND (t2, 0);
1669 tree y1 = TREE_OPERAND (t1, 1);
1670 tree y2 = TREE_OPERAND (t2, 1);
1672 if (!sem_variable::equals (x1, x2) || !sem_variable::equals (y1, y2))
1674 if (!sem_variable::equals (array_ref_low_bound (t1),
1675 array_ref_low_bound (t2)))
1677 if (!sem_variable::equals (array_ref_element_size (t1),
1678 array_ref_element_size (t2)))
1684 case POINTER_PLUS_EXPR:
1689 tree x1 = TREE_OPERAND (t1, 0);
1690 tree x2 = TREE_OPERAND (t2, 0);
1691 tree y1 = TREE_OPERAND (t1, 1);
1692 tree y2 = TREE_OPERAND (t2, 1);
1694 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
1698 case VIEW_CONVERT_EXPR:
1699 if (!func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
1701 return return_false ();
1702 return sem_variable::equals (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1704 return return_false_with_msg ("ERROR_MARK");
1706 return return_false_with_msg ("Unknown TREE code reached");
1710 /* Parser function that visits a varpool NODE. */
1713 sem_variable::parse (varpool_node *node, bitmap_obstack *stack)
1715 if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl)
1719 sem_variable *v = new sem_variable (node, 0, stack);
1726 /* References independent hash function. */
1729 sem_variable::get_hash (void)
1734 /* All WPA streamed in symbols should have their hashes computed at compile
1735 time. At this point, the constructor may not be in memory at all.
1736 DECL_INITIAL (decl) would be error_mark_node in that case. */
1737 gcc_assert (!node->lto_file_data);
1738 tree ctor = DECL_INITIAL (decl);
1739 inchash::hash hstate;
1741 hstate.add_int (456346417);
1742 if (DECL_SIZE (decl) && tree_fits_shwi_p (DECL_SIZE (decl)))
1743 hstate.add_wide_int (tree_to_shwi (DECL_SIZE (decl)));
1744 add_expr (ctor, hstate);
1745 hash = hstate.end ();
1750 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1754 sem_variable::merge (sem_item *alias_item)
1756 gcc_assert (alias_item->type == VAR);
1758 if (!sem_item::target_supports_symbol_aliases_p ())
1761 fprintf (dump_file, "Not unifying; "
1762 "Symbol aliases are not supported by target\n\n");
1766 sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
1768 varpool_node *original = get_node ();
1769 varpool_node *alias = alias_var->get_node ();
1770 bool original_discardable = false;
1772 bool original_address_matters = original->address_matters_p ();
1773 bool alias_address_matters = alias->address_matters_p ();
1775 /* See if original is in a section that can be discarded if the main
1777 Also consider case where we have resolution info and we know that
1778 original's definition is not going to be used. In this case we can not
1779 create alias to original. */
1780 if (original->can_be_discarded_p ()
1781 || (node->resolution != LDPR_UNKNOWN
1782 && !decl_binds_to_current_def_p (node->decl)))
1783 original_discardable = true;
1785 gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
1787 /* Constant pool machinery is not quite ready for aliases.
1788 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
1789 For LTO merging does not happen that is an important missing feature.
1790 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
1791 flag is dropped and non-local symbol name is assigned. */
1792 if (DECL_IN_CONSTANT_POOL (alias->decl)
1793 || DECL_IN_CONSTANT_POOL (original->decl))
1797 "Not unifying; constant pool variables.\n\n");
1801 /* Do not attempt to mix functions from different user sections;
1802 we do not know what user intends with those. */
1803 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
1804 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
1805 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
1810 "original and alias are in different sections.\n\n");
1814 /* We can not merge if address comparsion metters. */
1815 if (original_address_matters && alias_address_matters
1816 && flag_merge_constants < 2)
1821 "adress of original and alias may be compared.\n\n");
1824 if (DECL_COMDAT_GROUP (original->decl) != DECL_COMDAT_GROUP (alias->decl))
1827 fprintf (dump_file, "Not unifying; alias cannot be created; "
1828 "across comdat group boundary\n\n");
1833 if (original_discardable)
1836 fprintf (dump_file, "Not unifying; alias cannot be created; "
1837 "target is discardable\n\n");
1843 gcc_assert (!original->alias);
1844 gcc_assert (!alias->alias);
1846 alias->analyzed = false;
1848 DECL_INITIAL (alias->decl) = NULL;
1849 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
1851 alias->need_bounds_init = false;
1852 alias->remove_all_references ();
1853 if (TREE_ADDRESSABLE (alias->decl))
1854 original->call_for_symbol_and_aliases (set_addressable, NULL, true);
1856 varpool_node::create_alias (alias_var->decl, decl);
1857 alias->resolve_alias (original);
1860 fprintf (dump_file, "Unified; Variable alias has been created.\n\n");
1866 /* Dump symbol to FILE. */
1869 sem_variable::dump_to_file (FILE *file)
1873 print_node (file, "", decl, 0);
1874 fprintf (file, "\n\n");
1877 /* Iterates though a constructor and identifies tree references
1878 we are interested in semantic function equality. */
1881 sem_variable::parse_tree_refs (tree t)
1883 switch (TREE_CODE (t))
1887 unsigned length = vec_safe_length (CONSTRUCTOR_ELTS (t));
1889 for (unsigned i = 0; i < length; i++)
1890 parse_tree_refs(CONSTRUCTOR_ELT (t, i)->value);
1897 tree op = TREE_OPERAND (t, 0);
1898 parse_tree_refs (op);
1903 tree_refs.safe_push (t);
1911 unsigned int sem_item_optimizer::class_id = 0;
1913 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1914 m_classes_count (0), m_cgraph_node_hooks (NULL), m_varpool_node_hooks (NULL)
1917 bitmap_obstack_initialize (&m_bmstack);
1920 sem_item_optimizer::~sem_item_optimizer ()
1922 for (unsigned int i = 0; i < m_items.length (); i++)
1925 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
1926 it != m_classes.end (); ++it)
1928 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
1929 delete (*it)->classes[i];
1931 (*it)->classes.release ();
1937 bitmap_obstack_release (&m_bmstack);
1940 /* Write IPA ICF summary for symbols. */
1943 sem_item_optimizer::write_summary (void)
1945 unsigned int count = 0;
1947 output_block *ob = create_output_block (LTO_section_ipa_icf);
1948 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
1951 /* Calculate number of symbols to be serialized. */
1952 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
1954 lsei_next_in_partition (&lsei))
1956 symtab_node *node = lsei_node (lsei);
1958 if (m_symtab_node_map.get (node))
1962 streamer_write_uhwi (ob, count);
1964 /* Process all of the symbols. */
1965 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
1967 lsei_next_in_partition (&lsei))
1969 symtab_node *node = lsei_node (lsei);
1971 sem_item **item = m_symtab_node_map.get (node);
1975 int node_ref = lto_symtab_encoder_encode (encoder, node);
1976 streamer_write_uhwi_stream (ob->main_stream, node_ref);
1978 streamer_write_uhwi (ob, (*item)->get_hash ());
1982 streamer_write_char_stream (ob->main_stream, 0);
1983 produce_asm (ob, NULL);
1984 destroy_output_block (ob);
1987 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1988 contains LEN bytes. */
1991 sem_item_optimizer::read_section (lto_file_decl_data *file_data,
1992 const char *data, size_t len)
1994 const lto_function_header *header =
1995 (const lto_function_header *) data;
1996 const int cfg_offset = sizeof (lto_function_header);
1997 const int main_offset = cfg_offset + header->cfg_size;
1998 const int string_offset = main_offset + header->main_size;
2003 lto_input_block ib_main ((const char *) data + main_offset, 0,
2004 header->main_size, file_data->mode_table);
2007 lto_data_in_create (file_data, (const char *) data + string_offset,
2008 header->string_size, vNULL);
2010 count = streamer_read_uhwi (&ib_main);
2012 for (i = 0; i < count; i++)
2016 lto_symtab_encoder_t encoder;
2018 index = streamer_read_uhwi (&ib_main);
2019 encoder = file_data->symtab_node_encoder;
2020 node = lto_symtab_encoder_deref (encoder, index);
2022 hashval_t hash = streamer_read_uhwi (&ib_main);
2024 gcc_assert (node->definition);
2027 fprintf (dump_file, "Symbol added:%s (tree: %p, uid:%u)\n", node->asm_name (),
2028 (void *) node->decl, node->order);
2030 if (is_a<cgraph_node *> (node))
2032 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
2034 m_items.safe_push (new sem_function (cnode, hash, &m_bmstack));
2038 varpool_node *vnode = dyn_cast <varpool_node *> (node);
2040 m_items.safe_push (new sem_variable (vnode, hash, &m_bmstack));
2044 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
2046 lto_data_in_delete (data_in);
2049 /* Read IPA IPA ICF summary for symbols. */
2052 sem_item_optimizer::read_summary (void)
2054 lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2055 lto_file_decl_data *file_data;
2058 while ((file_data = file_data_vec[j++]))
2061 const char *data = lto_get_section_data (file_data,
2062 LTO_section_ipa_icf, NULL, &len);
2065 read_section (file_data, data, len);
2069 /* Register callgraph and varpool hooks. */
2072 sem_item_optimizer::register_hooks (void)
2074 if (!m_cgraph_node_hooks)
2075 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
2076 (&sem_item_optimizer::cgraph_removal_hook, this);
2078 if (!m_varpool_node_hooks)
2079 m_varpool_node_hooks = symtab->add_varpool_removal_hook
2080 (&sem_item_optimizer::varpool_removal_hook, this);
2083 /* Unregister callgraph and varpool hooks. */
2086 sem_item_optimizer::unregister_hooks (void)
2088 if (m_cgraph_node_hooks)
2089 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
2091 if (m_varpool_node_hooks)
2092 symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
2095 /* Adds a CLS to hashtable associated by hash value. */
2098 sem_item_optimizer::add_class (congruence_class *cls)
2100 gcc_assert (cls->members.length ());
2102 congruence_class_group *group = get_group_by_hash (
2103 cls->members[0]->get_hash (),
2104 cls->members[0]->type);
2105 group->classes.safe_push (cls);
2108 /* Gets a congruence class group based on given HASH value and TYPE. */
2110 congruence_class_group *
2111 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
2113 congruence_class_group *item = XNEW (congruence_class_group);
2117 congruence_class_group **slot = m_classes.find_slot (item, INSERT);
2123 item->classes.create (1);
2130 /* Callgraph removal hook called for a NODE with a custom DATA. */
2133 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
2135 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2136 optimizer->remove_symtab_node (node);
2139 /* Varpool removal hook called for a NODE with a custom DATA. */
2142 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
2144 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2145 optimizer->remove_symtab_node (node);
2148 /* Remove symtab NODE triggered by symtab removal hooks. */
2151 sem_item_optimizer::remove_symtab_node (symtab_node *node)
2153 gcc_assert (!m_classes.elements());
2155 m_removed_items_set.add (node);
2159 sem_item_optimizer::remove_item (sem_item *item)
2161 if (m_symtab_node_map.get (item->node))
2162 m_symtab_node_map.remove (item->node);
2166 /* Removes all callgraph and varpool nodes that are marked by symtab
2170 sem_item_optimizer::filter_removed_items (void)
2172 auto_vec <sem_item *> filtered;
2174 for (unsigned int i = 0; i < m_items.length(); i++)
2176 sem_item *item = m_items[i];
2178 if (m_removed_items_set.contains (item->node))
2184 if (item->type == FUNC)
2186 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
2188 bool no_body_function = in_lto_p && (cnode->alias || cnode->body_removed);
2189 if (no_body_function || !opt_for_fn (item->decl, flag_ipa_icf_functions)
2190 || DECL_CXX_CONSTRUCTOR_P (item->decl)
2191 || DECL_CXX_DESTRUCTOR_P (item->decl))
2194 filtered.safe_push (item);
2198 if (!flag_ipa_icf_variables)
2202 /* Filter out non-readonly variables. */
2203 tree decl = item->decl;
2204 if (TREE_READONLY (decl))
2205 filtered.safe_push (item);
2212 /* Clean-up of released semantic items. */
2215 for (unsigned int i = 0; i < filtered.length(); i++)
2216 m_items.safe_push (filtered[i]);
2219 /* Optimizer entry point which returns true in case it processes
2220 a merge operation. True is returned if there's a merge operation
2224 sem_item_optimizer::execute (void)
2226 filter_removed_items ();
2227 unregister_hooks ();
2229 build_hash_based_classes ();
2232 fprintf (dump_file, "Dump after hash based groups\n");
2233 dump_cong_classes ();
2235 for (unsigned int i = 0; i < m_items.length(); i++)
2236 m_items[i]->init_wpa ();
2240 subdivide_classes_by_equality (true);
2243 fprintf (dump_file, "Dump after WPA based types groups\n");
2245 dump_cong_classes ();
2247 process_cong_reduction ();
2251 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
2253 dump_cong_classes ();
2255 parse_nonsingleton_classes ();
2256 subdivide_classes_by_equality ();
2259 fprintf (dump_file, "Dump after full equality comparison of groups\n");
2261 dump_cong_classes ();
2263 unsigned int prev_class_count = m_classes_count;
2265 process_cong_reduction ();
2266 dump_cong_classes ();
2268 bool merged_p = merge_classes (prev_class_count);
2270 if (dump_file && (dump_flags & TDF_DETAILS))
2271 symtab_node::dump_table (dump_file);
2276 /* Function responsible for visiting all potential functions and
2277 read-only variables that can be merged. */
2280 sem_item_optimizer::parse_funcs_and_vars (void)
2284 if (flag_ipa_icf_functions)
2285 FOR_EACH_DEFINED_FUNCTION (cnode)
2287 sem_function *f = sem_function::parse (cnode, &m_bmstack);
2290 m_items.safe_push (f);
2291 m_symtab_node_map.put (cnode, f);
2294 fprintf (dump_file, "Parsed function:%s\n", f->asm_name ());
2296 if (dump_file && (dump_flags & TDF_DETAILS))
2297 f->dump_to_file (dump_file);
2300 fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
2303 varpool_node *vnode;
2305 if (flag_ipa_icf_variables)
2306 FOR_EACH_DEFINED_VARIABLE (vnode)
2308 sem_variable *v = sem_variable::parse (vnode, &m_bmstack);
2312 m_items.safe_push (v);
2313 m_symtab_node_map.put (vnode, v);
2318 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2321 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
2323 item->index_in_class = cls->members.length ();
2324 cls->members.safe_push (item);
2328 /* Congruence classes are built by hash value. */
2331 sem_item_optimizer::build_hash_based_classes (void)
2333 for (unsigned i = 0; i < m_items.length (); i++)
2335 sem_item *item = m_items[i];
2337 congruence_class_group *group = get_group_by_hash (item->get_hash (),
2340 if (!group->classes.length ())
2343 group->classes.safe_push (new congruence_class (class_id++));
2346 add_item_to_class (group->classes[0], item);
2350 /* Build references according to call graph. */
2353 sem_item_optimizer::build_graph (void)
2355 for (unsigned i = 0; i < m_items.length (); i++)
2357 sem_item *item = m_items[i];
2358 m_symtab_node_map.put (item->node, item);
2361 for (unsigned i = 0; i < m_items.length (); i++)
2363 sem_item *item = m_items[i];
2365 if (item->type == FUNC)
2367 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
2369 cgraph_edge *e = cnode->callees;
2372 sem_item **slot = m_symtab_node_map.get
2373 (e->callee->ultimate_alias_target ());
2375 item->add_reference (*slot);
2381 ipa_ref *ref = NULL;
2382 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
2384 sem_item **slot = m_symtab_node_map.get
2385 (ref->referred->ultimate_alias_target ());
2387 item->add_reference (*slot);
2392 /* Semantic items in classes having more than one element and initialized.
2393 In case of WPA, we load function body. */
2396 sem_item_optimizer::parse_nonsingleton_classes (void)
2398 unsigned int init_called_count = 0;
2400 for (unsigned i = 0; i < m_items.length (); i++)
2401 if (m_items[i]->cls->members.length () > 1)
2403 m_items[i]->init ();
2404 init_called_count++;
2408 fprintf (dump_file, "Init called for %u items (%.2f%%).\n", init_called_count,
2409 m_items.length () ? 100.0f * init_called_count / m_items.length (): 0.0f);
2412 /* Equality function for semantic items is used to subdivide existing
2413 classes. If IN_WPA, fast equality function is invoked. */
2416 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
2418 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2419 it != m_classes.end (); ++it)
2421 unsigned int class_count = (*it)->classes.length ();
2423 for (unsigned i = 0; i < class_count; i++)
2425 congruence_class *c = (*it)->classes [i];
2427 if (c->members.length() > 1)
2429 auto_vec <sem_item *> new_vector;
2431 sem_item *first = c->members[0];
2432 new_vector.safe_push (first);
2434 unsigned class_split_first = (*it)->classes.length ();
2436 for (unsigned j = 1; j < c->members.length (); j++)
2438 sem_item *item = c->members[j];
2440 bool equals = in_wpa ? first->equals_wpa (item,
2441 m_symtab_node_map) : first->equals (item, m_symtab_node_map);
2444 new_vector.safe_push (item);
2447 bool integrated = false;
2449 for (unsigned k = class_split_first; k < (*it)->classes.length (); k++)
2451 sem_item *x = (*it)->classes[k]->members[0];
2452 bool equals = in_wpa ? x->equals_wpa (item,
2453 m_symtab_node_map) : x->equals (item, m_symtab_node_map);
2458 add_item_to_class ((*it)->classes[k], item);
2466 congruence_class *c = new congruence_class (class_id++);
2468 add_item_to_class (c, item);
2470 (*it)->classes.safe_push (c);
2475 // we replace newly created new_vector for the class we've just splitted
2476 c->members.release ();
2477 c->members.create (new_vector.length ());
2479 for (unsigned int j = 0; j < new_vector.length (); j++)
2480 add_item_to_class (c, new_vector[j]);
2488 /* Subdivide classes by address references that members of the class
2489 reference. Example can be a pair of functions that have an address
2490 taken from a function. If these addresses are different the class
2494 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2496 unsigned newly_created_classes = 0;
2498 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2499 it != m_classes.end (); ++it)
2501 unsigned int class_count = (*it)->classes.length ();
2502 auto_vec<congruence_class *> new_classes;
2504 for (unsigned i = 0; i < class_count; i++)
2506 congruence_class *c = (*it)->classes [i];
2508 if (c->members.length() > 1)
2510 hash_map <symbol_compare_collection *, vec <sem_item *>,
2511 symbol_compare_hashmap_traits> split_map;
2513 for (unsigned j = 0; j < c->members.length (); j++)
2515 sem_item *source_node = c->members[j];
2517 symbol_compare_collection *collection = new symbol_compare_collection (source_node->node);
2519 vec <sem_item *> *slot = &split_map.get_or_insert (collection);
2520 gcc_checking_assert (slot);
2522 slot->safe_push (source_node);
2525 /* If the map contains more than one key, we have to split the map
2527 if (split_map.elements () != 1)
2529 bool first_class = true;
2531 hash_map <symbol_compare_collection *, vec <sem_item *>,
2532 symbol_compare_hashmap_traits>::iterator it2 = split_map.begin ();
2533 for (; it2 != split_map.end (); ++it2)
2535 congruence_class *new_cls;
2536 new_cls = new congruence_class (class_id++);
2538 for (unsigned k = 0; k < (*it2).second.length (); k++)
2539 add_item_to_class (new_cls, (*it2).second[k]);
2541 worklist_push (new_cls);
2542 newly_created_classes++;
2546 (*it)->classes[i] = new_cls;
2547 first_class = false;
2551 new_classes.safe_push (new_cls);
2559 for (unsigned i = 0; i < new_classes.length (); i++)
2560 (*it)->classes.safe_push (new_classes[i]);
2563 return newly_created_classes;
2566 /* Verify congruence classes if checking is enabled. */
2569 sem_item_optimizer::verify_classes (void)
2572 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2573 it != m_classes.end (); ++it)
2575 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2577 congruence_class *cls = (*it)->classes[i];
2579 gcc_checking_assert (cls);
2580 gcc_checking_assert (cls->members.length () > 0);
2582 for (unsigned int j = 0; j < cls->members.length (); j++)
2584 sem_item *item = cls->members[j];
2586 gcc_checking_assert (item);
2587 gcc_checking_assert (item->cls == cls);
2589 for (unsigned k = 0; k < item->usages.length (); k++)
2591 sem_usage_pair *usage = item->usages[k];
2592 gcc_checking_assert (usage->item->index_in_class <
2593 usage->item->cls->members.length ());
2601 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2602 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2603 but unused argument. */
2606 sem_item_optimizer::release_split_map (congruence_class * const &,
2607 bitmap const &b, traverse_split_pair *)
2616 /* Process split operation for a class given as pointer CLS_PTR,
2617 where bitmap B splits congruence class members. DATA is used
2618 as argument of split pair. */
2621 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
2622 bitmap const &b, traverse_split_pair *pair)
2624 sem_item_optimizer *optimizer = pair->optimizer;
2625 const congruence_class *splitter_cls = pair->cls;
2627 /* If counted bits are greater than zero and less than the number of members
2628 a group will be splitted. */
2629 unsigned popcount = bitmap_count_bits (b);
2631 if (popcount > 0 && popcount < cls->members.length ())
2633 congruence_class* newclasses[2] = { new congruence_class (class_id++), new congruence_class (class_id++) };
2635 for (unsigned int i = 0; i < cls->members.length (); i++)
2637 int target = bitmap_bit_p (b, i);
2638 congruence_class *tc = newclasses[target];
2640 add_item_to_class (tc, cls->members[i]);
2643 #ifdef ENABLE_CHECKING
2644 for (unsigned int i = 0; i < 2; i++)
2645 gcc_checking_assert (newclasses[i]->members.length ());
2648 if (splitter_cls == cls)
2649 optimizer->splitter_class_removed = true;
2651 /* Remove old class from worklist if presented. */
2652 bool in_worklist = cls->in_worklist;
2655 cls->in_worklist = false;
2657 congruence_class_group g;
2658 g.hash = cls->members[0]->get_hash ();
2659 g.type = cls->members[0]->type;
2661 congruence_class_group *slot = optimizer->m_classes.find(&g);
2663 for (unsigned int i = 0; i < slot->classes.length (); i++)
2664 if (slot->classes[i] == cls)
2666 slot->classes.ordered_remove (i);
2670 /* New class will be inserted and integrated to work list. */
2671 for (unsigned int i = 0; i < 2; i++)
2672 optimizer->add_class (newclasses[i]);
2674 /* Two classes replace one, so that increment just by one. */
2675 optimizer->m_classes_count++;
2677 /* If OLD class was presented in the worklist, we remove the class
2678 and replace it will both newly created classes. */
2680 for (unsigned int i = 0; i < 2; i++)
2681 optimizer->worklist_push (newclasses[i]);
2682 else /* Just smaller class is inserted. */
2684 unsigned int smaller_index = newclasses[0]->members.length () <
2685 newclasses[1]->members.length () ?
2687 optimizer->worklist_push (newclasses[smaller_index]);
2690 if (dump_file && (dump_flags & TDF_DETAILS))
2692 fprintf (dump_file, " congruence class splitted:\n");
2693 cls->dump (dump_file, 4);
2695 fprintf (dump_file, " newly created groups:\n");
2696 for (unsigned int i = 0; i < 2; i++)
2697 newclasses[i]->dump (dump_file, 4);
2700 /* Release class if not presented in work list. */
2709 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2710 Bitmap stack BMSTACK is used for bitmap allocation. */
2713 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
2716 hash_map <congruence_class *, bitmap> split_map;
2718 for (unsigned int i = 0; i < cls->members.length (); i++)
2720 sem_item *item = cls->members[i];
2722 /* Iterate all usages that have INDEX as usage of the item. */
2723 for (unsigned int j = 0; j < item->usages.length (); j++)
2725 sem_usage_pair *usage = item->usages[j];
2727 if (usage->index != index)
2730 bitmap *slot = split_map.get (usage->item->cls);
2735 b = BITMAP_ALLOC (&m_bmstack);
2736 split_map.put (usage->item->cls, b);
2742 gcc_checking_assert (usage->item->cls);
2743 gcc_checking_assert (usage->item->index_in_class <
2744 usage->item->cls->members.length ());
2747 bitmap_set_bit (b, usage->item->index_in_class);
2751 traverse_split_pair pair;
2752 pair.optimizer = this;
2755 splitter_class_removed = false;
2757 <traverse_split_pair *, sem_item_optimizer::traverse_congruence_split> (&pair);
2759 /* Bitmap clean-up. */
2761 <traverse_split_pair *, sem_item_optimizer::release_split_map> (NULL);
2764 /* Every usage of a congruence class CLS is a candidate that can split the
2765 collection of classes. Bitmap stack BMSTACK is used for bitmap
2769 sem_item_optimizer::do_congruence_step (congruence_class *cls)
2774 bitmap usage = BITMAP_ALLOC (&m_bmstack);
2776 for (unsigned int i = 0; i < cls->members.length (); i++)
2777 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
2779 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
2781 if (dump_file && (dump_flags & TDF_DETAILS))
2782 fprintf (dump_file, " processing congruece step for class: %u, index: %u\n",
2785 do_congruence_step_for_index (cls, i);
2787 if (splitter_class_removed)
2791 BITMAP_FREE (usage);
2794 /* Adds a newly created congruence class CLS to worklist. */
2797 sem_item_optimizer::worklist_push (congruence_class *cls)
2799 /* Return if the class CLS is already presented in work list. */
2800 if (cls->in_worklist)
2803 cls->in_worklist = true;
2804 worklist.push_back (cls);
2807 /* Pops a class from worklist. */
2810 sem_item_optimizer::worklist_pop (void)
2812 congruence_class *cls;
2814 while (!worklist.empty ())
2816 cls = worklist.front ();
2817 worklist.pop_front ();
2818 if (cls->in_worklist)
2820 cls->in_worklist = false;
2826 /* Work list item was already intended to be removed.
2827 The only reason for doing it is to split a class.
2828 Thus, the class CLS is deleted. */
2836 /* Iterative congruence reduction function. */
2839 sem_item_optimizer::process_cong_reduction (void)
2841 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2842 it != m_classes.end (); ++it)
2843 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2844 if ((*it)->classes[i]->is_class_used ())
2845 worklist_push ((*it)->classes[i]);
2848 fprintf (dump_file, "Worklist has been filled with: %lu\n",
2849 (unsigned long) worklist.size ());
2851 if (dump_file && (dump_flags & TDF_DETAILS))
2852 fprintf (dump_file, "Congruence class reduction\n");
2854 congruence_class *cls;
2856 /* Process complete congruence reduction. */
2857 while ((cls = worklist_pop ()) != NULL)
2858 do_congruence_step (cls);
2860 /* Subdivide newly created classes according to references. */
2861 unsigned new_classes = subdivide_classes_by_sensitive_refs ();
2864 fprintf (dump_file, "Address reference subdivision created: %u "
2865 "new classes.\n", new_classes);
2868 /* Debug function prints all informations about congruence classes. */
2871 sem_item_optimizer::dump_cong_classes (void)
2877 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2878 m_classes_count, (unsigned long) m_classes.elements(), m_items.length ());
2880 /* Histogram calculation. */
2881 unsigned int max_index = 0;
2882 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
2884 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2885 it != m_classes.end (); ++it)
2887 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2889 unsigned int c = (*it)->classes[i]->members.length ();
2897 "Class size histogram [num of members]: number of classe number of classess\n");
2899 for (unsigned int i = 0; i <= max_index; i++)
2901 fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
2903 fprintf (dump_file, "\n\n");
2906 if (dump_flags & TDF_DETAILS)
2907 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2908 it != m_classes.end (); ++it)
2910 fprintf (dump_file, " group: with %u classes:\n", (*it)->classes.length ());
2912 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2914 (*it)->classes[i]->dump (dump_file, 4);
2916 if(i < (*it)->classes.length () - 1)
2917 fprintf (dump_file, " ");
2924 /* After reduction is done, we can declare all items in a group
2925 to be equal. PREV_CLASS_COUNT is start number of classes
2926 before reduction. True is returned if there's a merge operation
2930 sem_item_optimizer::merge_classes (unsigned int prev_class_count)
2932 unsigned int item_count = m_items.length ();
2933 unsigned int class_count = m_classes_count;
2934 unsigned int equal_items = item_count - class_count;
2936 unsigned int non_singular_classes_count = 0;
2937 unsigned int non_singular_classes_sum = 0;
2939 bool merged_p = false;
2941 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2942 it != m_classes.end (); ++it)
2943 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2945 congruence_class *c = (*it)->classes[i];
2946 if (c->members.length () > 1)
2948 non_singular_classes_count++;
2949 non_singular_classes_sum += c->members.length ();
2955 fprintf (dump_file, "\nItem count: %u\n", item_count);
2956 fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
2957 prev_class_count, class_count);
2958 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
2959 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
2960 class_count ? 1.0f * item_count / class_count : 0.0f);
2961 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
2962 non_singular_classes_count ? 1.0f * non_singular_classes_sum /
2963 non_singular_classes_count : 0.0f,
2964 non_singular_classes_count);
2965 fprintf (dump_file, "Equal symbols: %u\n", equal_items);
2966 fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
2967 item_count ? 100.0f * equal_items / item_count : 0.0f);
2970 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2971 it != m_classes.end (); ++it)
2972 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2974 congruence_class *c = (*it)->classes[i];
2976 if (c->members.length () == 1)
2979 gcc_assert (c->members.length ());
2981 sem_item *source = c->members[0];
2983 for (unsigned int j = 1; j < c->members.length (); j++)
2985 sem_item *alias = c->members[j];
2989 fprintf (dump_file, "Semantic equality hit:%s->%s\n",
2990 source->name (), alias->name ());
2991 fprintf (dump_file, "Assembler symbol names:%s->%s\n",
2992 source->asm_name (), alias->asm_name ());
2995 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl)))
2999 "Merge operation is skipped due to no_icf "
3005 if (dump_file && (dump_flags & TDF_DETAILS))
3007 source->dump_to_file (dump_file);
3008 alias->dump_to_file (dump_file);
3011 merged_p |= source->merge (alias);
3018 /* Dump function prints all class members to a FILE with an INDENT. */
3021 congruence_class::dump (FILE *file, unsigned int indent) const
3023 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
3024 id, members[0]->get_hash (), members.length ());
3026 FPUTS_SPACES (file, indent + 2, "");
3027 for (unsigned i = 0; i < members.length (); i++)
3028 fprintf (file, "%s(%p/%u) ", members[i]->asm_name (), (void *) members[i]->decl,
3029 members[i]->node->order);
3031 fprintf (file, "\n");
3034 /* Returns true if there's a member that is used from another group. */
3037 congruence_class::is_class_used (void)
3039 for (unsigned int i = 0; i < members.length (); i++)
3040 if (members[i]->usages.length ())
3046 /* Initialization and computation of symtab node hash, there data
3047 are propagated later on. */
3049 static sem_item_optimizer *optimizer = NULL;
3051 /* Generate pass summary for IPA ICF pass. */
3054 ipa_icf_generate_summary (void)
3057 optimizer = new sem_item_optimizer ();
3059 optimizer->register_hooks ();
3060 optimizer->parse_funcs_and_vars ();
3063 /* Write pass summary for IPA ICF pass. */
3066 ipa_icf_write_summary (void)
3068 gcc_assert (optimizer);
3070 optimizer->write_summary ();
3073 /* Read pass summary for IPA ICF pass. */
3076 ipa_icf_read_summary (void)
3079 optimizer = new sem_item_optimizer ();
3081 optimizer->read_summary ();
3082 optimizer->register_hooks ();
3085 /* Semantic equality exection function. */
3088 ipa_icf_driver (void)
3090 gcc_assert (optimizer);
3092 bool merged_p = optimizer->execute ();
3097 return merged_p ? TODO_remove_functions : 0;
3100 const pass_data pass_data_ipa_icf =
3102 IPA_PASS, /* type */
3104 OPTGROUP_IPA, /* optinfo_flags */
3105 TV_IPA_ICF, /* tv_id */
3106 0, /* properties_required */
3107 0, /* properties_provided */
3108 0, /* properties_destroyed */
3109 0, /* todo_flags_start */
3110 0, /* todo_flags_finish */
3113 class pass_ipa_icf : public ipa_opt_pass_d
3116 pass_ipa_icf (gcc::context *ctxt)
3117 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
3118 ipa_icf_generate_summary, /* generate_summary */
3119 ipa_icf_write_summary, /* write_summary */
3120 ipa_icf_read_summary, /* read_summary */
3122 write_optimization_summary */
3124 read_optimization_summary */
3125 NULL, /* stmt_fixup */
3126 0, /* function_transform_todo_flags_start */
3127 NULL, /* function_transform */
3128 NULL) /* variable_transform */
3131 /* opt_pass methods: */
3132 virtual bool gate (function *)
3134 return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
3137 virtual unsigned int execute (function *)
3139 return ipa_icf_driver();
3141 }; // class pass_ipa_icf
3143 } // ipa_icf namespace
3146 make_pass_ipa_icf (gcc::context *ctxt)
3148 return new ipa_icf::pass_ipa_icf (ctxt);