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 /* Checking types of arguments. */
410 for (unsigned i = 0; i < arg_types.length (); i++)
412 /* This guard is here for function pointer with attributes (pr59927.c). */
413 if (!arg_types[i] || !m_compared_func->arg_types[i])
414 return return_false_with_msg ("NULL argument type");
416 /* Polymorphic comparison is executed just for non-leaf functions. */
417 bool is_not_leaf = get_node ()->callees != NULL
418 || get_node ()->indirect_calls != NULL;
420 if (!func_checker::compatible_types_p (arg_types[i],
421 m_compared_func->arg_types[i],
422 is_not_leaf, i == 0))
423 return return_false_with_msg ("argument type is different");
424 if (POINTER_TYPE_P (arg_types[i])
425 && (TYPE_RESTRICT (arg_types[i])
426 != TYPE_RESTRICT (m_compared_func->arg_types[i])))
427 return return_false_with_msg ("argument restrict flag mismatch");
430 /* Result type checking. */
431 if (!func_checker::compatible_types_p (result_type,
432 m_compared_func->result_type))
433 return return_false_with_msg ("result types are different");
435 if (node->num_references () != item->node->num_references ())
436 return return_false_with_msg ("different number of references");
438 if (comp_type_attributes (TREE_TYPE (decl),
439 TREE_TYPE (item->decl)) != 1)
440 return return_false_with_msg ("different type attributes");
442 ipa_ref *ref = NULL, *ref2 = NULL;
443 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
445 item->node->iterate_reference (i, ref2);
447 if (!compare_cgraph_references (ignored_nodes, ref->referred,
449 ref->address_matters_p ()))
453 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
454 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
458 if (!compare_cgraph_references (ignored_nodes, e1->callee,
462 e1 = e1->next_callee;
463 e2 = e2->next_callee;
467 return return_false_with_msg ("different number of edges");
472 /* Returns true if the item equals to ITEM given as argument. */
475 sem_function::equals (sem_item *item,
476 hash_map <symtab_node *, sem_item *> &ignored_nodes)
478 gcc_assert (item->type == FUNC);
479 bool eq = equals_private (item, ignored_nodes);
481 if (m_checker != NULL)
487 if (dump_file && (dump_flags & TDF_DETAILS))
489 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
490 name(), item->name (), node->order, item->node->order, asm_name (),
491 item->asm_name (), eq ? "true" : "false");
496 /* Processes function equality comparison. */
499 sem_function::equals_private (sem_item *item,
500 hash_map <symtab_node *, sem_item *> &ignored_nodes)
502 if (item->type != FUNC)
505 basic_block bb1, bb2;
507 edge_iterator ei1, ei2;
511 m_compared_func = static_cast<sem_function *> (item);
513 gcc_assert (decl != item->decl);
515 if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
516 || edge_count != m_compared_func->edge_count
517 || cfg_checksum != m_compared_func->cfg_checksum)
518 return return_false ();
520 if (!equals_wpa (item, ignored_nodes))
523 /* Checking function TARGET and OPTIMIZATION flags. */
524 cl_target_option *tar1 = target_opts_for_fn (decl);
525 cl_target_option *tar2 = target_opts_for_fn (m_compared_func->decl);
527 if (tar1 != NULL && tar2 != NULL)
529 if (!cl_target_option_eq (tar1, tar2))
531 if (dump_file && (dump_flags & TDF_DETAILS))
533 fprintf (dump_file, "target flags difference");
534 cl_target_option_print_diff (dump_file, 2, tar1, tar2);
537 return return_false_with_msg ("Target flags are different");
540 else if (tar1 != NULL || tar2 != NULL)
541 return return_false_with_msg ("Target flags are different");
543 cl_optimization *opt1 = opts_for_fn (decl);
544 cl_optimization *opt2 = opts_for_fn (m_compared_func->decl);
546 if (opt1 != NULL && opt2 != NULL)
548 if (memcmp (opt1, opt2, sizeof(cl_optimization)))
550 if (dump_file && (dump_flags & TDF_DETAILS))
552 fprintf (dump_file, "optimization flags difference");
553 cl_optimization_print_diff (dump_file, 2, opt1, opt2);
556 return return_false_with_msg ("optimization flags are different");
559 else if (opt1 != NULL || opt2 != NULL)
560 return return_false_with_msg ("optimization flags are different");
562 /* Checking function arguments. */
563 tree decl1 = DECL_ATTRIBUTES (decl);
564 tree decl2 = DECL_ATTRIBUTES (m_compared_func->decl);
566 m_checker = new func_checker (decl, m_compared_func->decl,
567 compare_polymorphic_p (),
570 &m_compared_func->refs_set);
574 return return_false ();
576 if (get_attribute_name (decl1) != get_attribute_name (decl2))
577 return return_false ();
579 tree attr_value1 = TREE_VALUE (decl1);
580 tree attr_value2 = TREE_VALUE (decl2);
582 if (attr_value1 && attr_value2)
584 bool ret = m_checker->compare_operand (TREE_VALUE (attr_value1),
585 TREE_VALUE (attr_value2));
587 return return_false_with_msg ("attribute values are different");
589 else if (!attr_value1 && !attr_value2)
592 return return_false ();
594 decl1 = TREE_CHAIN (decl1);
595 decl2 = TREE_CHAIN (decl2);
599 return return_false();
602 for (arg1 = DECL_ARGUMENTS (decl),
603 arg2 = DECL_ARGUMENTS (m_compared_func->decl);
604 arg1; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2))
605 if (!m_checker->compare_decl (arg1, arg2))
606 return return_false ();
608 /* Fill-up label dictionary. */
609 for (unsigned i = 0; i < bb_sorted.length (); ++i)
611 m_checker->parse_labels (bb_sorted[i]);
612 m_checker->parse_labels (m_compared_func->bb_sorted[i]);
615 /* Checking all basic blocks. */
616 for (unsigned i = 0; i < bb_sorted.length (); ++i)
617 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
618 return return_false();
620 dump_message ("All BBs are equal\n");
622 auto_vec <int> bb_dict;
624 /* Basic block edges check. */
625 for (unsigned i = 0; i < bb_sorted.length (); ++i)
627 bb1 = bb_sorted[i]->bb;
628 bb2 = m_compared_func->bb_sorted[i]->bb;
630 ei2 = ei_start (bb2->preds);
632 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
636 if (e1->flags != e2->flags)
637 return return_false_with_msg ("flags comparison returns false");
639 if (!bb_dict_test (&bb_dict, e1->src->index, e2->src->index))
640 return return_false_with_msg ("edge comparison returns false");
642 if (!bb_dict_test (&bb_dict, e1->dest->index, e2->dest->index))
643 return return_false_with_msg ("BB comparison returns false");
645 if (!m_checker->compare_edge (e1, e2))
646 return return_false_with_msg ("edge comparison returns false");
652 /* Basic block PHI nodes comparison. */
653 for (unsigned i = 0; i < bb_sorted.length (); i++)
654 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
655 return return_false_with_msg ("PHI node comparison returns false");
657 /* Compare special function DECL attributes. */
658 if (DECL_FUNCTION_PERSONALITY (decl) != DECL_FUNCTION_PERSONALITY (item->decl))
659 return return_false_with_msg ("function personalities are different");
661 if (DECL_DISREGARD_INLINE_LIMITS (decl) != DECL_DISREGARD_INLINE_LIMITS (item->decl))
662 return return_false_with_msg ("DECL_DISREGARD_INLINE_LIMITS are different");
664 if (DECL_DECLARED_INLINE_P (decl) != DECL_DECLARED_INLINE_P (item->decl))
665 return return_false_with_msg ("inline attributes are different");
667 if (DECL_IS_OPERATOR_NEW (decl) != DECL_IS_OPERATOR_NEW (item->decl))
668 return return_false_with_msg ("operator new flags are different");
670 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
671 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item->decl))
672 return return_false_with_msg ("intrument function entry exit "
673 "attributes are different");
675 if (DECL_NO_LIMIT_STACK (decl) != DECL_NO_LIMIT_STACK (item->decl))
676 return return_false_with_msg ("no stack limit attributes are different");
678 if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
679 return return_false_with_msg ("decl_or_type flags are different");
684 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
685 Helper for call_for_symbol_thunks_and_aliases. */
688 set_local (cgraph_node *node, void *data)
690 node->local.local = data != NULL;
694 /* TREE_ADDRESSABLE of NODE to true.
695 Helper for call_for_symbol_thunks_and_aliases. */
698 set_addressable (varpool_node *node, void *)
700 TREE_ADDRESSABLE (node->decl) = 1;
704 /* Clear DECL_RTL of NODE.
705 Helper for call_for_symbol_thunks_and_aliases. */
708 clear_decl_rtl (symtab_node *node, void *)
710 SET_DECL_RTL (node->decl, NULL);
714 /* Redirect all callers of N and its aliases to TO. Remove aliases if
715 possible. Return number of redirections made. */
718 redirect_all_callers (cgraph_node *n, cgraph_node *to)
722 cgraph_edge *e = n->callers;
726 /* Redirecting thunks to interposable symbols or symbols in other sections
727 may not be supported by target output code. Play safe for now and
728 punt on redirection. */
729 if (!e->caller->thunk.thunk_p)
731 struct cgraph_edge *nexte = e->next_caller;
732 e->redirect_callee (to);
739 for (unsigned i = 0; n->iterate_direct_aliases (i, ref);)
741 bool removed = false;
742 cgraph_node *n_alias = dyn_cast <cgraph_node *> (ref->referring);
744 if ((DECL_COMDAT_GROUP (n->decl)
745 && (DECL_COMDAT_GROUP (n->decl)
746 == DECL_COMDAT_GROUP (n_alias->decl)))
747 || (n_alias->get_availability () > AVAIL_INTERPOSABLE
748 && n->get_availability () > AVAIL_INTERPOSABLE))
750 nredirected += redirect_all_callers (n_alias, to);
751 if (n_alias->can_remove_if_no_direct_calls_p ()
752 && !n_alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
754 && !n_alias->has_aliases_p ())
763 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
767 sem_function::merge (sem_item *alias_item)
769 gcc_assert (alias_item->type == FUNC);
771 sem_function *alias_func = static_cast<sem_function *> (alias_item);
773 cgraph_node *original = get_node ();
774 cgraph_node *local_original = NULL;
775 cgraph_node *alias = alias_func->get_node ();
777 bool create_wrapper = false;
778 bool create_alias = false;
779 bool redirect_callers = false;
782 bool original_discardable = false;
783 bool original_discarded = false;
785 bool original_address_matters = original->address_matters_p ();
786 bool alias_address_matters = alias->address_matters_p ();
788 if (DECL_NO_INLINE_WARNING_P (original->decl)
789 != DECL_NO_INLINE_WARNING_P (alias->decl))
794 "DECL_NO_INLINE_WARNING mismatch.\n\n");
798 /* Do not attempt to mix functions from different user sections;
799 we do not know what user intends with those. */
800 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
801 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
802 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
807 "original and alias are in different sections.\n\n");
811 /* See if original is in a section that can be discarded if the main
812 symbol is not used. */
814 if (original->can_be_discarded_p ())
815 original_discardable = true;
816 /* Also consider case where we have resolution info and we know that
817 original's definition is not going to be used. In this case we can not
818 create alias to original. */
819 if (node->resolution != LDPR_UNKNOWN
820 && !decl_binds_to_current_def_p (node->decl))
821 original_discardable = original_discarded = true;
823 /* Creating a symtab alias is the optimal way to merge.
824 It however can not be used in the following cases:
826 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
827 2) if ORIGINAL is in a section that may be discarded by linker or if
828 it is an external functions where we can not create an alias
829 (ORIGINAL_DISCARDABLE)
830 3) if target do not support symbol aliases.
831 4) original and alias lie in different comdat groups.
833 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
834 and/or redirect all callers from ALIAS to ORIGINAL. */
835 if ((original_address_matters && alias_address_matters)
836 || (original_discardable
837 && (!DECL_COMDAT_GROUP (alias->decl)
838 || (DECL_COMDAT_GROUP (alias->decl)
839 != DECL_COMDAT_GROUP (original->decl))))
840 || original_discarded
841 || !sem_item::target_supports_symbol_aliases_p ()
842 || DECL_COMDAT_GROUP (alias->decl) != DECL_COMDAT_GROUP (original->decl))
844 /* First see if we can produce wrapper. */
846 /* Do not turn function in one comdat group into wrapper to another
847 comdat group. Other compiler producing the body of the
848 another comdat group may make opossite decision and with unfortunate
849 linker choices this may close a loop. */
850 if (DECL_COMDAT_GROUP (original->decl) && DECL_COMDAT_GROUP (alias->decl)
851 && (DECL_COMDAT_GROUP (alias->decl)
852 != DECL_COMDAT_GROUP (original->decl)))
856 "Wrapper cannot be created because of COMDAT\n");
858 else if (DECL_STATIC_CHAIN (alias->decl))
862 "Can not create wrapper of nested functions.\n");
864 /* TODO: We can also deal with variadic functions never calling
866 else if (stdarg_p (TREE_TYPE (alias->decl)))
870 "can not create wrapper of stdarg function.\n");
872 else if (inline_summaries
873 && inline_summaries->get (alias)->self_size <= 2)
876 fprintf (dump_file, "Wrapper creation is not "
877 "profitable (function is too small).\n");
879 /* If user paid attention to mark function noinline, assume it is
880 somewhat special and do not try to turn it into a wrapper that can
881 not be undone by inliner. */
882 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
885 fprintf (dump_file, "Wrappers are not created for noinline.\n");
888 create_wrapper = true;
890 /* We can redirect local calls in the case both alias and orignal
891 are not interposable. */
893 = alias->get_availability () > AVAIL_INTERPOSABLE
894 && original->get_availability () > AVAIL_INTERPOSABLE
895 && !alias->instrumented_version;
897 if (!redirect_callers && !create_wrapper)
900 fprintf (dump_file, "Not unifying; can not redirect callers nor "
901 "produce wrapper\n\n");
905 /* Work out the symbol the wrapper should call.
906 If ORIGINAL is interposable, we need to call a local alias.
907 Also produce local alias (if possible) as an optimization.
909 Local aliases can not be created inside comdat groups because that
910 prevents inlining. */
911 if (!original_discardable && !original->get_comdat_group ())
914 = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
916 && original->get_availability () > AVAIL_INTERPOSABLE)
917 local_original = original;
919 /* If we can not use local alias, fallback to the original
921 else if (original->get_availability () > AVAIL_INTERPOSABLE)
922 local_original = original;
924 /* If original is COMDAT local, we can not really redirect calls outside
925 of its comdat group to it. */
926 if (original->comdat_local_p ())
927 redirect_callers = false;
931 fprintf (dump_file, "Not unifying; "
932 "can not produce local alias.\n\n");
936 if (!redirect_callers && !create_wrapper)
939 fprintf (dump_file, "Not unifying; "
940 "can not redirect callers nor produce a wrapper\n\n");
944 && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
946 && !alias->can_remove_if_no_direct_calls_p ())
949 fprintf (dump_file, "Not unifying; can not make wrapper and "
950 "function has other uses than direct calls\n\n");
957 if (redirect_callers)
959 int nredirected = redirect_all_callers (alias, local_original);
963 alias->icf_merged = true;
964 local_original->icf_merged = true;
966 if (dump_file && nredirected)
967 fprintf (dump_file, "%i local calls have been "
968 "redirected.\n", nredirected);
971 /* If all callers was redirected, do not produce wrapper. */
972 if (alias->can_remove_if_no_direct_calls_p ()
973 && !alias->has_aliases_p ())
975 create_wrapper = false;
978 gcc_assert (!create_alias);
980 else if (create_alias)
982 alias->icf_merged = true;
984 /* Remove the function's body. */
985 ipa_merge_profiles (original, alias);
986 alias->release_body (true);
988 /* Notice global symbol possibly produced RTL. */
989 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
992 /* Create the alias. */
993 cgraph_node::create_alias (alias_func->decl, decl);
994 alias->resolve_alias (original);
996 original->call_for_symbol_thunks_and_aliases
997 (set_local, (void *)(size_t) original->local_p (), true);
1000 fprintf (dump_file, "Unified; Function alias has been created.\n\n");
1004 gcc_assert (!create_alias);
1005 alias->icf_merged = true;
1006 local_original->icf_merged = true;
1008 ipa_merge_profiles (local_original, alias, true);
1009 alias->create_wrapper (local_original);
1012 fprintf (dump_file, "Unified; Wrapper has been created.\n\n");
1015 /* It's possible that redirection can hit thunks that block
1016 redirection opportunities. */
1017 gcc_assert (alias->icf_merged || remove || redirect_callers);
1018 original->icf_merged = true;
1020 /* Inform the inliner about cross-module merging. */
1021 if ((original->lto_file_data || alias->lto_file_data)
1022 && original->lto_file_data != alias->lto_file_data)
1023 local_original->merged = original->merged = true;
1027 ipa_merge_profiles (original, alias);
1028 alias->release_body ();
1030 alias->body_removed = true;
1031 alias->icf_merged = true;
1033 fprintf (dump_file, "Unified; Function body was removed.\n");
1039 /* Semantic item initialization function. */
1042 sem_function::init (void)
1045 get_node ()->get_untransformed_body ();
1047 tree fndecl = node->decl;
1048 function *func = DECL_STRUCT_FUNCTION (fndecl);
1051 gcc_assert (SSANAMES (func));
1053 ssa_names_size = SSANAMES (func)->length ();
1057 region_tree = func->eh->region_tree;
1059 /* iterating all function arguments. */
1060 arg_count = count_formal_params (fndecl);
1062 edge_count = n_edges_for_fn (func);
1063 cfg_checksum = coverage_compute_cfg_checksum (func);
1065 inchash::hash hstate;
1068 FOR_EACH_BB_FN (bb, func)
1070 unsigned nondbg_stmt_count = 0;
1073 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
1075 cfg_checksum = iterative_hash_host_wide_int (e->flags,
1078 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1081 gimple stmt = gsi_stmt (gsi);
1083 if (gimple_code (stmt) != GIMPLE_DEBUG
1084 && gimple_code (stmt) != GIMPLE_PREDICT)
1086 hash_stmt (stmt, hstate);
1087 nondbg_stmt_count++;
1091 gcode_hash = hstate.end ();
1092 bb_sizes.safe_push (nondbg_stmt_count);
1094 /* Inserting basic block to hash table. */
1095 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
1096 EDGE_COUNT (bb->preds)
1097 + EDGE_COUNT (bb->succs));
1099 bb_sorted.safe_push (semantic_bb);
1105 /* Accumulate to HSTATE a hash of expression EXP.
1106 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1107 and DECL equality classes. */
1110 sem_item::add_expr (const_tree exp, inchash::hash &hstate)
1112 if (exp == NULL_TREE)
1114 hstate.merge_hash (0);
1118 /* Handled component can be matched in a cureful way proving equivalence
1119 even if they syntactically differ. Just skip them. */
1121 while (handled_component_p (exp))
1122 exp = TREE_OPERAND (exp, 0);
1124 enum tree_code code = TREE_CODE (exp);
1125 hstate.add_int (code);
1129 /* Use inchash::add_expr for everything that is LTO stable. */
1137 inchash::add_expr (exp, hstate);
1141 unsigned HOST_WIDE_INT idx;
1144 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1146 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp), idx, value)
1148 add_expr (value, hstate);
1153 add_expr (get_base_address (TREE_OPERAND (exp, 0)), hstate);
1159 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1162 case POINTER_PLUS_EXPR:
1165 add_expr (TREE_OPERAND (exp, 0), hstate);
1166 add_expr (TREE_OPERAND (exp, 1), hstate);
1170 inchash::hash one, two;
1171 add_expr (TREE_OPERAND (exp, 0), one);
1172 add_expr (TREE_OPERAND (exp, 1), two);
1173 hstate.add_commutative (one, two);
1177 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1178 return add_expr (TREE_OPERAND (exp, 0), hstate);
1184 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1187 sem_function::hash_stmt (gimple stmt, inchash::hash &hstate)
1189 enum gimple_code code = gimple_code (stmt);
1191 hstate.add_int (code);
1196 if (commutative_tree_code (gimple_assign_rhs_code (stmt))
1197 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1199 inchash::hash one, two;
1201 add_expr (gimple_assign_rhs1 (stmt), one);
1202 add_expr (gimple_assign_rhs2 (stmt), two);
1203 hstate.add_commutative (one, two);
1204 add_expr (gimple_assign_lhs (stmt), hstate);
1207 /* ... fall through ... */
1213 /* All these statements are equivalent if their operands are. */
1214 for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1215 add_expr (gimple_op (stmt, i), hstate);
1222 /* Return true if polymorphic comparison must be processed. */
1225 sem_function::compare_polymorphic_p (void)
1227 return get_node ()->callees != NULL
1228 || get_node ()->indirect_calls != NULL
1229 || m_compared_func->get_node ()->callees != NULL
1230 || m_compared_func->get_node ()->indirect_calls != NULL;
1233 /* For a given call graph NODE, the function constructs new
1234 semantic function item. */
1237 sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
1239 tree fndecl = node->decl;
1240 function *func = DECL_STRUCT_FUNCTION (fndecl);
1242 /* TODO: add support for thunks. */
1244 if (!func || !node->has_gimple_body_p ())
1247 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
1250 sem_function *f = new sem_function (node, 0, stack);
1257 /* Parses function arguments and result type. */
1260 sem_function::parse_tree_args (void)
1264 if (arg_types.exists ())
1265 arg_types.release ();
1267 arg_types.create (4);
1268 tree fnargs = DECL_ARGUMENTS (decl);
1270 for (tree parm = fnargs; parm; parm = DECL_CHAIN (parm))
1271 arg_types.safe_push (DECL_ARG_TYPE (parm));
1273 /* Function result type. */
1274 result = DECL_RESULT (decl);
1275 result_type = result ? TREE_TYPE (result) : NULL;
1277 /* During WPA, we can get arguments by following method. */
1280 tree type = TYPE_ARG_TYPES (TREE_TYPE (decl));
1281 for (tree parm = type; parm; parm = TREE_CHAIN (parm))
1282 arg_types.safe_push (TYPE_CANONICAL (TREE_VALUE (parm)));
1284 result_type = TREE_TYPE (TREE_TYPE (decl));
1288 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1289 return true if phi nodes are semantically equivalent in these blocks . */
1292 sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
1294 gphi_iterator si1, si2;
1296 unsigned size1, size2, i;
1300 gcc_assert (bb1 != NULL);
1301 gcc_assert (bb2 != NULL);
1303 si2 = gsi_start_phis (bb2);
1304 for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
1307 gsi_next_nonvirtual_phi (&si1);
1308 gsi_next_nonvirtual_phi (&si2);
1310 if (gsi_end_p (si1) && gsi_end_p (si2))
1313 if (gsi_end_p (si1) || gsi_end_p (si2))
1314 return return_false();
1319 tree phi_result1 = gimple_phi_result (phi1);
1320 tree phi_result2 = gimple_phi_result (phi2);
1322 if (!m_checker->compare_operand (phi_result1, phi_result2))
1323 return return_false_with_msg ("PHI results are different");
1325 size1 = gimple_phi_num_args (phi1);
1326 size2 = gimple_phi_num_args (phi2);
1329 return return_false ();
1331 for (i = 0; i < size1; ++i)
1333 t1 = gimple_phi_arg (phi1, i)->def;
1334 t2 = gimple_phi_arg (phi2, i)->def;
1336 if (!m_checker->compare_operand (t1, t2))
1337 return return_false ();
1339 e1 = gimple_phi_arg_edge (phi1, i);
1340 e2 = gimple_phi_arg_edge (phi2, i);
1342 if (!m_checker->compare_edge (e1, e2))
1343 return return_false ();
1352 /* Returns true if tree T can be compared as a handled component. */
1355 sem_function::icf_handled_component_p (tree t)
1357 tree_code tc = TREE_CODE (t);
1359 return ((handled_component_p (t))
1360 || tc == ADDR_EXPR || tc == MEM_REF || tc == REALPART_EXPR
1361 || tc == IMAGPART_EXPR || tc == OBJ_TYPE_REF);
1364 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1365 corresponds to TARGET. */
1368 sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
1373 if (bb_dict->length () <= (unsigned)source)
1374 bb_dict->safe_grow_cleared (source + 1);
1376 if ((*bb_dict)[source] == 0)
1378 (*bb_dict)[source] = target;
1382 return (*bb_dict)[source] == target;
1385 /* Iterates all tree types in T1 and T2 and returns true if all types
1386 are compatible. If COMPARE_POLYMORPHIC is set to true,
1387 more strict comparison is executed. */
1390 sem_function::compare_type_list (tree t1, tree t2, bool compare_polymorphic)
1398 while (t1 != NULL && t2 != NULL)
1400 tv1 = TREE_VALUE (t1);
1401 tv2 = TREE_VALUE (t2);
1403 tc1 = TREE_CODE (tv1);
1404 tc2 = TREE_CODE (tv2);
1406 if (tc1 == NOP_EXPR && tc2 == NOP_EXPR)
1408 else if (tc1 == NOP_EXPR || tc2 == NOP_EXPR)
1410 else if (!func_checker::compatible_types_p (tv1, tv2, compare_polymorphic))
1413 t1 = TREE_CHAIN (t1);
1414 t2 = TREE_CHAIN (t2);
1421 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1423 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
1427 /* Constructor based on varpool node _NODE with computed hash _HASH.
1428 Bitmap STACK is used for memory allocation. */
1430 sem_variable::sem_variable (varpool_node *node, hashval_t _hash,
1431 bitmap_obstack *stack): sem_item(VAR,
1434 gcc_checking_assert (node);
1435 gcc_checking_assert (get_node ());
1438 /* Fast equality function based on knowledge known in WPA. */
1441 sem_variable::equals_wpa (sem_item *item,
1442 hash_map <symtab_node *, sem_item *> &ignored_nodes)
1444 gcc_assert (item->type == VAR);
1446 if (node->num_references () != item->node->num_references ())
1447 return return_false_with_msg ("different number of references");
1449 if (DECL_TLS_MODEL (decl) || DECL_TLS_MODEL (item->decl))
1450 return return_false_with_msg ("TLS model");
1452 if (DECL_ALIGN (decl) != DECL_ALIGN (item->decl))
1453 return return_false_with_msg ("alignment mismatch");
1455 if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
1456 return return_false_with_msg ("Virtual flag mismatch");
1458 if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
1459 && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
1460 || !operand_equal_p (DECL_SIZE (decl),
1461 DECL_SIZE (item->decl), OEP_ONLY_CONST)))
1462 return return_false_with_msg ("size mismatch");
1464 /* Do not attempt to mix data from different user sections;
1465 we do not know what user intends with those. */
1466 if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
1467 || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
1468 && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
1469 return return_false_with_msg ("user section mismatch");
1471 if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
1472 return return_false_with_msg ("text section");
1474 ipa_ref *ref = NULL, *ref2 = NULL;
1475 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
1477 item->node->iterate_reference (i, ref2);
1479 if (!compare_cgraph_references (ignored_nodes,
1480 ref->referred, ref2->referred,
1481 ref->address_matters_p ()))
1484 /* DECL_FINAL_P flag on methods referred by virtual tables is used
1485 to decide on completeness possible_polymorphic_call_targets lists
1486 and therefore it must match. */
1487 if ((DECL_VIRTUAL_P (decl) || DECL_VIRTUAL_P (item->decl))
1488 && (DECL_VIRTUAL_P (ref->referred->decl)
1489 || DECL_VIRTUAL_P (ref2->referred->decl))
1490 && ((DECL_VIRTUAL_P (ref->referred->decl)
1491 != DECL_VIRTUAL_P (ref2->referred->decl))
1492 || (DECL_FINAL_P (ref->referred->decl)
1493 != DECL_FINAL_P (ref2->referred->decl))))
1494 return return_false_with_msg ("virtual or final flag mismatch");
1500 /* Returns true if the item equals to ITEM given as argument. */
1502 /* Returns true if the item equals to ITEM given as argument. */
1505 sem_variable::equals (sem_item *item,
1506 hash_map <symtab_node *, sem_item *> &)
1508 gcc_assert (item->type == VAR);
1511 if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
1512 dyn_cast <varpool_node *>(node)->get_constructor ();
1513 if (DECL_INITIAL (item->decl) == error_mark_node && in_lto_p)
1514 dyn_cast <varpool_node *>(item->node)->get_constructor ();
1516 /* As seen in PR ipa/65303 we have to compare variables types. */
1517 if (!func_checker::compatible_types_p (TREE_TYPE (decl),
1518 TREE_TYPE (item->decl)))
1519 return return_false_with_msg ("variables types are different");
1521 ret = sem_variable::equals (DECL_INITIAL (decl),
1522 DECL_INITIAL (item->node->decl));
1523 if (dump_file && (dump_flags & TDF_DETAILS))
1525 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1526 name(), item->name (), node->order, item->node->order, asm_name (),
1527 item->asm_name (), ret ? "true" : "false");
1532 /* Compares trees T1 and T2 for semantic equality. */
1535 sem_variable::equals (tree t1, tree t2)
1538 return return_with_debug (t1 == t2);
1541 tree_code tc1 = TREE_CODE (t1);
1542 tree_code tc2 = TREE_CODE (t2);
1545 return return_false_with_msg ("TREE_CODE mismatch");
1551 vec<constructor_elt, va_gc> *v1, *v2;
1552 unsigned HOST_WIDE_INT idx;
1554 enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
1555 if (typecode != TREE_CODE (TREE_TYPE (t2)))
1556 return return_false_with_msg ("constructor type mismatch");
1558 if (typecode == ARRAY_TYPE)
1560 HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
1561 /* For arrays, check that the sizes all match. */
1562 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
1564 || size_1 != int_size_in_bytes (TREE_TYPE (t2)))
1565 return return_false_with_msg ("constructor array size mismatch");
1567 else if (!func_checker::compatible_types_p (TREE_TYPE (t1),
1569 return return_false_with_msg ("constructor type incompatible");
1571 v1 = CONSTRUCTOR_ELTS (t1);
1572 v2 = CONSTRUCTOR_ELTS (t2);
1573 if (vec_safe_length (v1) != vec_safe_length (v2))
1574 return return_false_with_msg ("constructor number of elts mismatch");
1576 for (idx = 0; idx < vec_safe_length (v1); ++idx)
1578 constructor_elt *c1 = &(*v1)[idx];
1579 constructor_elt *c2 = &(*v2)[idx];
1581 /* Check that each value is the same... */
1582 if (!sem_variable::equals (c1->value, c2->value))
1584 /* ... and that they apply to the same fields! */
1585 if (!sem_variable::equals (c1->index, c2->index))
1592 tree x1 = TREE_OPERAND (t1, 0);
1593 tree x2 = TREE_OPERAND (t2, 0);
1594 tree y1 = TREE_OPERAND (t1, 1);
1595 tree y2 = TREE_OPERAND (t2, 1);
1597 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2),
1599 return return_false ();
1601 /* Type of the offset on MEM_REF does not matter. */
1602 return return_with_debug (sem_variable::equals (x1, x2)
1603 && wi::to_offset (y1)
1604 == wi::to_offset (y2));
1609 tree op1 = TREE_OPERAND (t1, 0);
1610 tree op2 = TREE_OPERAND (t2, 0);
1611 return sem_variable::equals (op1, op2);
1613 /* References to other vars/decls are compared using ipa-ref. */
1616 if (decl_in_symtab_p (t1) && decl_in_symtab_p (t2))
1618 return return_false_with_msg ("Declaration mismatch");
1620 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1621 need to process its VAR/FUNCTION references without relying on ipa-ref
1625 return return_false_with_msg ("Declaration mismatch");
1627 /* Integer constants are the same only if the same width of type. */
1628 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1629 return return_false_with_msg ("INTEGER_CST precision mismatch");
1630 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1631 return return_false_with_msg ("INTEGER_CST mode mismatch");
1632 return return_with_debug (tree_int_cst_equal (t1, t2));
1634 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1635 return return_false_with_msg ("STRING_CST mode mismatch");
1636 if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
1637 return return_false_with_msg ("STRING_CST length mismatch");
1638 if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
1639 TREE_STRING_LENGTH (t1)))
1640 return return_false_with_msg ("STRING_CST mismatch");
1643 /* Fixed constants are the same only if the same width of type. */
1644 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1645 return return_false_with_msg ("FIXED_CST precision mismatch");
1647 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
1648 TREE_FIXED_CST (t2)));
1650 return (sem_variable::equals (TREE_REALPART (t1), TREE_REALPART (t2))
1651 && sem_variable::equals (TREE_IMAGPART (t1), TREE_IMAGPART (t2)));
1653 /* Real constants are the same only if the same width of type. */
1654 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1655 return return_false_with_msg ("REAL_CST precision mismatch");
1656 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1),
1657 TREE_REAL_CST (t2)));
1662 if (VECTOR_CST_NELTS (t1) != VECTOR_CST_NELTS (t2))
1663 return return_false_with_msg ("VECTOR_CST nelts mismatch");
1665 for (i = 0; i < VECTOR_CST_NELTS (t1); ++i)
1666 if (!sem_variable::equals (VECTOR_CST_ELT (t1, i),
1667 VECTOR_CST_ELT (t2, i)))
1673 case ARRAY_RANGE_REF:
1675 tree x1 = TREE_OPERAND (t1, 0);
1676 tree x2 = TREE_OPERAND (t2, 0);
1677 tree y1 = TREE_OPERAND (t1, 1);
1678 tree y2 = TREE_OPERAND (t2, 1);
1680 if (!sem_variable::equals (x1, x2) || !sem_variable::equals (y1, y2))
1682 if (!sem_variable::equals (array_ref_low_bound (t1),
1683 array_ref_low_bound (t2)))
1685 if (!sem_variable::equals (array_ref_element_size (t1),
1686 array_ref_element_size (t2)))
1692 case POINTER_PLUS_EXPR:
1697 tree x1 = TREE_OPERAND (t1, 0);
1698 tree x2 = TREE_OPERAND (t2, 0);
1699 tree y1 = TREE_OPERAND (t1, 1);
1700 tree y2 = TREE_OPERAND (t2, 1);
1702 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
1706 case VIEW_CONVERT_EXPR:
1707 if (!func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
1709 return return_false ();
1710 return sem_variable::equals (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1712 return return_false_with_msg ("ERROR_MARK");
1714 return return_false_with_msg ("Unknown TREE code reached");
1718 /* Parser function that visits a varpool NODE. */
1721 sem_variable::parse (varpool_node *node, bitmap_obstack *stack)
1723 if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl)
1727 sem_variable *v = new sem_variable (node, 0, stack);
1734 /* References independent hash function. */
1737 sem_variable::get_hash (void)
1742 /* All WPA streamed in symbols should have their hashes computed at compile
1743 time. At this point, the constructor may not be in memory at all.
1744 DECL_INITIAL (decl) would be error_mark_node in that case. */
1745 gcc_assert (!node->lto_file_data);
1746 tree ctor = DECL_INITIAL (decl);
1747 inchash::hash hstate;
1749 hstate.add_int (456346417);
1750 if (DECL_SIZE (decl) && tree_fits_shwi_p (DECL_SIZE (decl)))
1751 hstate.add_wide_int (tree_to_shwi (DECL_SIZE (decl)));
1752 add_expr (ctor, hstate);
1753 hash = hstate.end ();
1758 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1762 sem_variable::merge (sem_item *alias_item)
1764 gcc_assert (alias_item->type == VAR);
1766 if (!sem_item::target_supports_symbol_aliases_p ())
1769 fprintf (dump_file, "Not unifying; "
1770 "Symbol aliases are not supported by target\n\n");
1774 sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
1776 varpool_node *original = get_node ();
1777 varpool_node *alias = alias_var->get_node ();
1778 bool original_discardable = false;
1780 bool original_address_matters = original->address_matters_p ();
1781 bool alias_address_matters = alias->address_matters_p ();
1783 /* See if original is in a section that can be discarded if the main
1785 Also consider case where we have resolution info and we know that
1786 original's definition is not going to be used. In this case we can not
1787 create alias to original. */
1788 if (original->can_be_discarded_p ()
1789 || (node->resolution != LDPR_UNKNOWN
1790 && !decl_binds_to_current_def_p (node->decl)))
1791 original_discardable = true;
1793 gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
1795 /* Constant pool machinery is not quite ready for aliases.
1796 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
1797 For LTO merging does not happen that is an important missing feature.
1798 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
1799 flag is dropped and non-local symbol name is assigned. */
1800 if (DECL_IN_CONSTANT_POOL (alias->decl)
1801 || DECL_IN_CONSTANT_POOL (original->decl))
1805 "Not unifying; constant pool variables.\n\n");
1809 /* Do not attempt to mix functions from different user sections;
1810 we do not know what user intends with those. */
1811 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
1812 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
1813 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
1818 "original and alias are in different sections.\n\n");
1822 /* We can not merge if address comparsion metters. */
1823 if (original_address_matters && alias_address_matters
1824 && flag_merge_constants < 2)
1829 "adress of original and alias may be compared.\n\n");
1832 if (DECL_COMDAT_GROUP (original->decl) != DECL_COMDAT_GROUP (alias->decl))
1835 fprintf (dump_file, "Not unifying; alias cannot be created; "
1836 "across comdat group boundary\n\n");
1841 if (original_discardable)
1844 fprintf (dump_file, "Not unifying; alias cannot be created; "
1845 "target is discardable\n\n");
1851 gcc_assert (!original->alias);
1852 gcc_assert (!alias->alias);
1854 alias->analyzed = false;
1856 DECL_INITIAL (alias->decl) = NULL;
1857 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
1859 alias->need_bounds_init = false;
1860 alias->remove_all_references ();
1861 if (TREE_ADDRESSABLE (alias->decl))
1862 original->call_for_symbol_and_aliases (set_addressable, NULL, true);
1864 varpool_node::create_alias (alias_var->decl, decl);
1865 alias->resolve_alias (original);
1868 fprintf (dump_file, "Unified; Variable alias has been created.\n\n");
1874 /* Dump symbol to FILE. */
1877 sem_variable::dump_to_file (FILE *file)
1881 print_node (file, "", decl, 0);
1882 fprintf (file, "\n\n");
1885 /* Iterates though a constructor and identifies tree references
1886 we are interested in semantic function equality. */
1889 sem_variable::parse_tree_refs (tree t)
1891 switch (TREE_CODE (t))
1895 unsigned length = vec_safe_length (CONSTRUCTOR_ELTS (t));
1897 for (unsigned i = 0; i < length; i++)
1898 parse_tree_refs(CONSTRUCTOR_ELT (t, i)->value);
1905 tree op = TREE_OPERAND (t, 0);
1906 parse_tree_refs (op);
1911 tree_refs.safe_push (t);
1919 unsigned int sem_item_optimizer::class_id = 0;
1921 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1922 m_classes_count (0), m_cgraph_node_hooks (NULL), m_varpool_node_hooks (NULL)
1925 bitmap_obstack_initialize (&m_bmstack);
1928 sem_item_optimizer::~sem_item_optimizer ()
1930 for (unsigned int i = 0; i < m_items.length (); i++)
1933 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
1934 it != m_classes.end (); ++it)
1936 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
1937 delete (*it)->classes[i];
1939 (*it)->classes.release ();
1945 bitmap_obstack_release (&m_bmstack);
1948 /* Write IPA ICF summary for symbols. */
1951 sem_item_optimizer::write_summary (void)
1953 unsigned int count = 0;
1955 output_block *ob = create_output_block (LTO_section_ipa_icf);
1956 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
1959 /* Calculate number of symbols to be serialized. */
1960 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
1962 lsei_next_in_partition (&lsei))
1964 symtab_node *node = lsei_node (lsei);
1966 if (m_symtab_node_map.get (node))
1970 streamer_write_uhwi (ob, count);
1972 /* Process all of the symbols. */
1973 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
1975 lsei_next_in_partition (&lsei))
1977 symtab_node *node = lsei_node (lsei);
1979 sem_item **item = m_symtab_node_map.get (node);
1983 int node_ref = lto_symtab_encoder_encode (encoder, node);
1984 streamer_write_uhwi_stream (ob->main_stream, node_ref);
1986 streamer_write_uhwi (ob, (*item)->get_hash ());
1990 streamer_write_char_stream (ob->main_stream, 0);
1991 produce_asm (ob, NULL);
1992 destroy_output_block (ob);
1995 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1996 contains LEN bytes. */
1999 sem_item_optimizer::read_section (lto_file_decl_data *file_data,
2000 const char *data, size_t len)
2002 const lto_function_header *header =
2003 (const lto_function_header *) data;
2004 const int cfg_offset = sizeof (lto_function_header);
2005 const int main_offset = cfg_offset + header->cfg_size;
2006 const int string_offset = main_offset + header->main_size;
2011 lto_input_block ib_main ((const char *) data + main_offset, 0,
2012 header->main_size, file_data->mode_table);
2015 lto_data_in_create (file_data, (const char *) data + string_offset,
2016 header->string_size, vNULL);
2018 count = streamer_read_uhwi (&ib_main);
2020 for (i = 0; i < count; i++)
2024 lto_symtab_encoder_t encoder;
2026 index = streamer_read_uhwi (&ib_main);
2027 encoder = file_data->symtab_node_encoder;
2028 node = lto_symtab_encoder_deref (encoder, index);
2030 hashval_t hash = streamer_read_uhwi (&ib_main);
2032 gcc_assert (node->definition);
2035 fprintf (dump_file, "Symbol added:%s (tree: %p, uid:%u)\n", node->asm_name (),
2036 (void *) node->decl, node->order);
2038 if (is_a<cgraph_node *> (node))
2040 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
2042 m_items.safe_push (new sem_function (cnode, hash, &m_bmstack));
2046 varpool_node *vnode = dyn_cast <varpool_node *> (node);
2048 m_items.safe_push (new sem_variable (vnode, hash, &m_bmstack));
2052 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
2054 lto_data_in_delete (data_in);
2057 /* Read IPA IPA ICF summary for symbols. */
2060 sem_item_optimizer::read_summary (void)
2062 lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2063 lto_file_decl_data *file_data;
2066 while ((file_data = file_data_vec[j++]))
2069 const char *data = lto_get_section_data (file_data,
2070 LTO_section_ipa_icf, NULL, &len);
2073 read_section (file_data, data, len);
2077 /* Register callgraph and varpool hooks. */
2080 sem_item_optimizer::register_hooks (void)
2082 if (!m_cgraph_node_hooks)
2083 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
2084 (&sem_item_optimizer::cgraph_removal_hook, this);
2086 if (!m_varpool_node_hooks)
2087 m_varpool_node_hooks = symtab->add_varpool_removal_hook
2088 (&sem_item_optimizer::varpool_removal_hook, this);
2091 /* Unregister callgraph and varpool hooks. */
2094 sem_item_optimizer::unregister_hooks (void)
2096 if (m_cgraph_node_hooks)
2097 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
2099 if (m_varpool_node_hooks)
2100 symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
2103 /* Adds a CLS to hashtable associated by hash value. */
2106 sem_item_optimizer::add_class (congruence_class *cls)
2108 gcc_assert (cls->members.length ());
2110 congruence_class_group *group = get_group_by_hash (
2111 cls->members[0]->get_hash (),
2112 cls->members[0]->type);
2113 group->classes.safe_push (cls);
2116 /* Gets a congruence class group based on given HASH value and TYPE. */
2118 congruence_class_group *
2119 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
2121 congruence_class_group *item = XNEW (congruence_class_group);
2125 congruence_class_group **slot = m_classes.find_slot (item, INSERT);
2131 item->classes.create (1);
2138 /* Callgraph removal hook called for a NODE with a custom DATA. */
2141 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
2143 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2144 optimizer->remove_symtab_node (node);
2147 /* Varpool removal hook called for a NODE with a custom DATA. */
2150 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
2152 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2153 optimizer->remove_symtab_node (node);
2156 /* Remove symtab NODE triggered by symtab removal hooks. */
2159 sem_item_optimizer::remove_symtab_node (symtab_node *node)
2161 gcc_assert (!m_classes.elements());
2163 m_removed_items_set.add (node);
2167 sem_item_optimizer::remove_item (sem_item *item)
2169 if (m_symtab_node_map.get (item->node))
2170 m_symtab_node_map.remove (item->node);
2174 /* Removes all callgraph and varpool nodes that are marked by symtab
2178 sem_item_optimizer::filter_removed_items (void)
2180 auto_vec <sem_item *> filtered;
2182 for (unsigned int i = 0; i < m_items.length(); i++)
2184 sem_item *item = m_items[i];
2186 if (m_removed_items_set.contains (item->node))
2192 if (item->type == FUNC)
2194 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
2196 bool no_body_function = in_lto_p && (cnode->alias || cnode->body_removed);
2197 if (no_body_function || !opt_for_fn (item->decl, flag_ipa_icf_functions)
2198 || DECL_CXX_CONSTRUCTOR_P (item->decl)
2199 || DECL_CXX_DESTRUCTOR_P (item->decl))
2202 filtered.safe_push (item);
2206 if (!flag_ipa_icf_variables)
2210 /* Filter out non-readonly variables. */
2211 tree decl = item->decl;
2212 if (TREE_READONLY (decl))
2213 filtered.safe_push (item);
2220 /* Clean-up of released semantic items. */
2223 for (unsigned int i = 0; i < filtered.length(); i++)
2224 m_items.safe_push (filtered[i]);
2227 /* Optimizer entry point which returns true in case it processes
2228 a merge operation. True is returned if there's a merge operation
2232 sem_item_optimizer::execute (void)
2234 filter_removed_items ();
2235 unregister_hooks ();
2237 build_hash_based_classes ();
2240 fprintf (dump_file, "Dump after hash based groups\n");
2241 dump_cong_classes ();
2243 for (unsigned int i = 0; i < m_items.length(); i++)
2244 m_items[i]->init_wpa ();
2248 subdivide_classes_by_equality (true);
2251 fprintf (dump_file, "Dump after WPA based types groups\n");
2253 dump_cong_classes ();
2255 process_cong_reduction ();
2259 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
2261 dump_cong_classes ();
2263 parse_nonsingleton_classes ();
2264 subdivide_classes_by_equality ();
2267 fprintf (dump_file, "Dump after full equality comparison of groups\n");
2269 dump_cong_classes ();
2271 unsigned int prev_class_count = m_classes_count;
2273 process_cong_reduction ();
2274 dump_cong_classes ();
2276 bool merged_p = merge_classes (prev_class_count);
2278 if (dump_file && (dump_flags & TDF_DETAILS))
2279 symtab_node::dump_table (dump_file);
2284 /* Function responsible for visiting all potential functions and
2285 read-only variables that can be merged. */
2288 sem_item_optimizer::parse_funcs_and_vars (void)
2292 if (flag_ipa_icf_functions)
2293 FOR_EACH_DEFINED_FUNCTION (cnode)
2295 sem_function *f = sem_function::parse (cnode, &m_bmstack);
2298 m_items.safe_push (f);
2299 m_symtab_node_map.put (cnode, f);
2302 fprintf (dump_file, "Parsed function:%s\n", f->asm_name ());
2304 if (dump_file && (dump_flags & TDF_DETAILS))
2305 f->dump_to_file (dump_file);
2308 fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
2311 varpool_node *vnode;
2313 if (flag_ipa_icf_variables)
2314 FOR_EACH_DEFINED_VARIABLE (vnode)
2316 sem_variable *v = sem_variable::parse (vnode, &m_bmstack);
2320 m_items.safe_push (v);
2321 m_symtab_node_map.put (vnode, v);
2326 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2329 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
2331 item->index_in_class = cls->members.length ();
2332 cls->members.safe_push (item);
2336 /* Congruence classes are built by hash value. */
2339 sem_item_optimizer::build_hash_based_classes (void)
2341 for (unsigned i = 0; i < m_items.length (); i++)
2343 sem_item *item = m_items[i];
2345 congruence_class_group *group = get_group_by_hash (item->get_hash (),
2348 if (!group->classes.length ())
2351 group->classes.safe_push (new congruence_class (class_id++));
2354 add_item_to_class (group->classes[0], item);
2358 /* Build references according to call graph. */
2361 sem_item_optimizer::build_graph (void)
2363 for (unsigned i = 0; i < m_items.length (); i++)
2365 sem_item *item = m_items[i];
2366 m_symtab_node_map.put (item->node, item);
2369 for (unsigned i = 0; i < m_items.length (); i++)
2371 sem_item *item = m_items[i];
2373 if (item->type == FUNC)
2375 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
2377 cgraph_edge *e = cnode->callees;
2380 sem_item **slot = m_symtab_node_map.get
2381 (e->callee->ultimate_alias_target ());
2383 item->add_reference (*slot);
2389 ipa_ref *ref = NULL;
2390 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
2392 sem_item **slot = m_symtab_node_map.get
2393 (ref->referred->ultimate_alias_target ());
2395 item->add_reference (*slot);
2400 /* Semantic items in classes having more than one element and initialized.
2401 In case of WPA, we load function body. */
2404 sem_item_optimizer::parse_nonsingleton_classes (void)
2406 unsigned int init_called_count = 0;
2408 for (unsigned i = 0; i < m_items.length (); i++)
2409 if (m_items[i]->cls->members.length () > 1)
2411 m_items[i]->init ();
2412 init_called_count++;
2416 fprintf (dump_file, "Init called for %u items (%.2f%%).\n", init_called_count,
2417 m_items.length () ? 100.0f * init_called_count / m_items.length (): 0.0f);
2420 /* Equality function for semantic items is used to subdivide existing
2421 classes. If IN_WPA, fast equality function is invoked. */
2424 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
2426 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2427 it != m_classes.end (); ++it)
2429 unsigned int class_count = (*it)->classes.length ();
2431 for (unsigned i = 0; i < class_count; i++)
2433 congruence_class *c = (*it)->classes [i];
2435 if (c->members.length() > 1)
2437 auto_vec <sem_item *> new_vector;
2439 sem_item *first = c->members[0];
2440 new_vector.safe_push (first);
2442 unsigned class_split_first = (*it)->classes.length ();
2444 for (unsigned j = 1; j < c->members.length (); j++)
2446 sem_item *item = c->members[j];
2448 bool equals = in_wpa ? first->equals_wpa (item,
2449 m_symtab_node_map) : first->equals (item, m_symtab_node_map);
2452 new_vector.safe_push (item);
2455 bool integrated = false;
2457 for (unsigned k = class_split_first; k < (*it)->classes.length (); k++)
2459 sem_item *x = (*it)->classes[k]->members[0];
2460 bool equals = in_wpa ? x->equals_wpa (item,
2461 m_symtab_node_map) : x->equals (item, m_symtab_node_map);
2466 add_item_to_class ((*it)->classes[k], item);
2474 congruence_class *c = new congruence_class (class_id++);
2476 add_item_to_class (c, item);
2478 (*it)->classes.safe_push (c);
2483 // we replace newly created new_vector for the class we've just splitted
2484 c->members.release ();
2485 c->members.create (new_vector.length ());
2487 for (unsigned int j = 0; j < new_vector.length (); j++)
2488 add_item_to_class (c, new_vector[j]);
2496 /* Subdivide classes by address references that members of the class
2497 reference. Example can be a pair of functions that have an address
2498 taken from a function. If these addresses are different the class
2502 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2504 unsigned newly_created_classes = 0;
2506 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2507 it != m_classes.end (); ++it)
2509 unsigned int class_count = (*it)->classes.length ();
2510 auto_vec<congruence_class *> new_classes;
2512 for (unsigned i = 0; i < class_count; i++)
2514 congruence_class *c = (*it)->classes [i];
2516 if (c->members.length() > 1)
2518 hash_map <symbol_compare_collection *, vec <sem_item *>,
2519 symbol_compare_hashmap_traits> split_map;
2521 for (unsigned j = 0; j < c->members.length (); j++)
2523 sem_item *source_node = c->members[j];
2525 symbol_compare_collection *collection = new symbol_compare_collection (source_node->node);
2527 vec <sem_item *> *slot = &split_map.get_or_insert (collection);
2528 gcc_checking_assert (slot);
2530 slot->safe_push (source_node);
2533 /* If the map contains more than one key, we have to split the map
2535 if (split_map.elements () != 1)
2537 bool first_class = true;
2539 hash_map <symbol_compare_collection *, vec <sem_item *>,
2540 symbol_compare_hashmap_traits>::iterator it2 = split_map.begin ();
2541 for (; it2 != split_map.end (); ++it2)
2543 congruence_class *new_cls;
2544 new_cls = new congruence_class (class_id++);
2546 for (unsigned k = 0; k < (*it2).second.length (); k++)
2547 add_item_to_class (new_cls, (*it2).second[k]);
2549 worklist_push (new_cls);
2550 newly_created_classes++;
2554 (*it)->classes[i] = new_cls;
2555 first_class = false;
2559 new_classes.safe_push (new_cls);
2567 for (unsigned i = 0; i < new_classes.length (); i++)
2568 (*it)->classes.safe_push (new_classes[i]);
2571 return newly_created_classes;
2574 /* Verify congruence classes if checking is enabled. */
2577 sem_item_optimizer::verify_classes (void)
2580 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2581 it != m_classes.end (); ++it)
2583 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2585 congruence_class *cls = (*it)->classes[i];
2587 gcc_checking_assert (cls);
2588 gcc_checking_assert (cls->members.length () > 0);
2590 for (unsigned int j = 0; j < cls->members.length (); j++)
2592 sem_item *item = cls->members[j];
2594 gcc_checking_assert (item);
2595 gcc_checking_assert (item->cls == cls);
2597 for (unsigned k = 0; k < item->usages.length (); k++)
2599 sem_usage_pair *usage = item->usages[k];
2600 gcc_checking_assert (usage->item->index_in_class <
2601 usage->item->cls->members.length ());
2609 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2610 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2611 but unused argument. */
2614 sem_item_optimizer::release_split_map (congruence_class * const &,
2615 bitmap const &b, traverse_split_pair *)
2624 /* Process split operation for a class given as pointer CLS_PTR,
2625 where bitmap B splits congruence class members. DATA is used
2626 as argument of split pair. */
2629 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
2630 bitmap const &b, traverse_split_pair *pair)
2632 sem_item_optimizer *optimizer = pair->optimizer;
2633 const congruence_class *splitter_cls = pair->cls;
2635 /* If counted bits are greater than zero and less than the number of members
2636 a group will be splitted. */
2637 unsigned popcount = bitmap_count_bits (b);
2639 if (popcount > 0 && popcount < cls->members.length ())
2641 congruence_class* newclasses[2] = { new congruence_class (class_id++), new congruence_class (class_id++) };
2643 for (unsigned int i = 0; i < cls->members.length (); i++)
2645 int target = bitmap_bit_p (b, i);
2646 congruence_class *tc = newclasses[target];
2648 add_item_to_class (tc, cls->members[i]);
2651 #ifdef ENABLE_CHECKING
2652 for (unsigned int i = 0; i < 2; i++)
2653 gcc_checking_assert (newclasses[i]->members.length ());
2656 if (splitter_cls == cls)
2657 optimizer->splitter_class_removed = true;
2659 /* Remove old class from worklist if presented. */
2660 bool in_worklist = cls->in_worklist;
2663 cls->in_worklist = false;
2665 congruence_class_group g;
2666 g.hash = cls->members[0]->get_hash ();
2667 g.type = cls->members[0]->type;
2669 congruence_class_group *slot = optimizer->m_classes.find(&g);
2671 for (unsigned int i = 0; i < slot->classes.length (); i++)
2672 if (slot->classes[i] == cls)
2674 slot->classes.ordered_remove (i);
2678 /* New class will be inserted and integrated to work list. */
2679 for (unsigned int i = 0; i < 2; i++)
2680 optimizer->add_class (newclasses[i]);
2682 /* Two classes replace one, so that increment just by one. */
2683 optimizer->m_classes_count++;
2685 /* If OLD class was presented in the worklist, we remove the class
2686 and replace it will both newly created classes. */
2688 for (unsigned int i = 0; i < 2; i++)
2689 optimizer->worklist_push (newclasses[i]);
2690 else /* Just smaller class is inserted. */
2692 unsigned int smaller_index = newclasses[0]->members.length () <
2693 newclasses[1]->members.length () ?
2695 optimizer->worklist_push (newclasses[smaller_index]);
2698 if (dump_file && (dump_flags & TDF_DETAILS))
2700 fprintf (dump_file, " congruence class splitted:\n");
2701 cls->dump (dump_file, 4);
2703 fprintf (dump_file, " newly created groups:\n");
2704 for (unsigned int i = 0; i < 2; i++)
2705 newclasses[i]->dump (dump_file, 4);
2708 /* Release class if not presented in work list. */
2717 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2718 Bitmap stack BMSTACK is used for bitmap allocation. */
2721 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
2724 hash_map <congruence_class *, bitmap> split_map;
2726 for (unsigned int i = 0; i < cls->members.length (); i++)
2728 sem_item *item = cls->members[i];
2730 /* Iterate all usages that have INDEX as usage of the item. */
2731 for (unsigned int j = 0; j < item->usages.length (); j++)
2733 sem_usage_pair *usage = item->usages[j];
2735 if (usage->index != index)
2738 bitmap *slot = split_map.get (usage->item->cls);
2743 b = BITMAP_ALLOC (&m_bmstack);
2744 split_map.put (usage->item->cls, b);
2750 gcc_checking_assert (usage->item->cls);
2751 gcc_checking_assert (usage->item->index_in_class <
2752 usage->item->cls->members.length ());
2755 bitmap_set_bit (b, usage->item->index_in_class);
2759 traverse_split_pair pair;
2760 pair.optimizer = this;
2763 splitter_class_removed = false;
2765 <traverse_split_pair *, sem_item_optimizer::traverse_congruence_split> (&pair);
2767 /* Bitmap clean-up. */
2769 <traverse_split_pair *, sem_item_optimizer::release_split_map> (NULL);
2772 /* Every usage of a congruence class CLS is a candidate that can split the
2773 collection of classes. Bitmap stack BMSTACK is used for bitmap
2777 sem_item_optimizer::do_congruence_step (congruence_class *cls)
2782 bitmap usage = BITMAP_ALLOC (&m_bmstack);
2784 for (unsigned int i = 0; i < cls->members.length (); i++)
2785 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
2787 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
2789 if (dump_file && (dump_flags & TDF_DETAILS))
2790 fprintf (dump_file, " processing congruece step for class: %u, index: %u\n",
2793 do_congruence_step_for_index (cls, i);
2795 if (splitter_class_removed)
2799 BITMAP_FREE (usage);
2802 /* Adds a newly created congruence class CLS to worklist. */
2805 sem_item_optimizer::worklist_push (congruence_class *cls)
2807 /* Return if the class CLS is already presented in work list. */
2808 if (cls->in_worklist)
2811 cls->in_worklist = true;
2812 worklist.push_back (cls);
2815 /* Pops a class from worklist. */
2818 sem_item_optimizer::worklist_pop (void)
2820 congruence_class *cls;
2822 while (!worklist.empty ())
2824 cls = worklist.front ();
2825 worklist.pop_front ();
2826 if (cls->in_worklist)
2828 cls->in_worklist = false;
2834 /* Work list item was already intended to be removed.
2835 The only reason for doing it is to split a class.
2836 Thus, the class CLS is deleted. */
2844 /* Iterative congruence reduction function. */
2847 sem_item_optimizer::process_cong_reduction (void)
2849 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2850 it != m_classes.end (); ++it)
2851 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2852 if ((*it)->classes[i]->is_class_used ())
2853 worklist_push ((*it)->classes[i]);
2856 fprintf (dump_file, "Worklist has been filled with: %lu\n",
2857 (unsigned long) worklist.size ());
2859 if (dump_file && (dump_flags & TDF_DETAILS))
2860 fprintf (dump_file, "Congruence class reduction\n");
2862 congruence_class *cls;
2864 /* Process complete congruence reduction. */
2865 while ((cls = worklist_pop ()) != NULL)
2866 do_congruence_step (cls);
2868 /* Subdivide newly created classes according to references. */
2869 unsigned new_classes = subdivide_classes_by_sensitive_refs ();
2872 fprintf (dump_file, "Address reference subdivision created: %u "
2873 "new classes.\n", new_classes);
2876 /* Debug function prints all informations about congruence classes. */
2879 sem_item_optimizer::dump_cong_classes (void)
2885 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2886 m_classes_count, (unsigned long) m_classes.elements(), m_items.length ());
2888 /* Histogram calculation. */
2889 unsigned int max_index = 0;
2890 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
2892 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2893 it != m_classes.end (); ++it)
2895 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2897 unsigned int c = (*it)->classes[i]->members.length ();
2905 "Class size histogram [num of members]: number of classe number of classess\n");
2907 for (unsigned int i = 0; i <= max_index; i++)
2909 fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
2911 fprintf (dump_file, "\n\n");
2914 if (dump_flags & TDF_DETAILS)
2915 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2916 it != m_classes.end (); ++it)
2918 fprintf (dump_file, " group: with %u classes:\n", (*it)->classes.length ());
2920 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2922 (*it)->classes[i]->dump (dump_file, 4);
2924 if(i < (*it)->classes.length () - 1)
2925 fprintf (dump_file, " ");
2932 /* After reduction is done, we can declare all items in a group
2933 to be equal. PREV_CLASS_COUNT is start number of classes
2934 before reduction. True is returned if there's a merge operation
2938 sem_item_optimizer::merge_classes (unsigned int prev_class_count)
2940 unsigned int item_count = m_items.length ();
2941 unsigned int class_count = m_classes_count;
2942 unsigned int equal_items = item_count - class_count;
2944 unsigned int non_singular_classes_count = 0;
2945 unsigned int non_singular_classes_sum = 0;
2947 bool merged_p = false;
2949 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2950 it != m_classes.end (); ++it)
2951 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2953 congruence_class *c = (*it)->classes[i];
2954 if (c->members.length () > 1)
2956 non_singular_classes_count++;
2957 non_singular_classes_sum += c->members.length ();
2963 fprintf (dump_file, "\nItem count: %u\n", item_count);
2964 fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
2965 prev_class_count, class_count);
2966 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
2967 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
2968 class_count ? 1.0f * item_count / class_count : 0.0f);
2969 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
2970 non_singular_classes_count ? 1.0f * non_singular_classes_sum /
2971 non_singular_classes_count : 0.0f,
2972 non_singular_classes_count);
2973 fprintf (dump_file, "Equal symbols: %u\n", equal_items);
2974 fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
2975 item_count ? 100.0f * equal_items / item_count : 0.0f);
2978 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2979 it != m_classes.end (); ++it)
2980 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2982 congruence_class *c = (*it)->classes[i];
2984 if (c->members.length () == 1)
2987 gcc_assert (c->members.length ());
2989 sem_item *source = c->members[0];
2991 for (unsigned int j = 1; j < c->members.length (); j++)
2993 sem_item *alias = c->members[j];
2997 fprintf (dump_file, "Semantic equality hit:%s->%s\n",
2998 source->name (), alias->name ());
2999 fprintf (dump_file, "Assembler symbol names:%s->%s\n",
3000 source->asm_name (), alias->asm_name ());
3003 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl)))
3007 "Merge operation is skipped due to no_icf "
3013 if (dump_file && (dump_flags & TDF_DETAILS))
3015 source->dump_to_file (dump_file);
3016 alias->dump_to_file (dump_file);
3019 merged_p |= source->merge (alias);
3026 /* Dump function prints all class members to a FILE with an INDENT. */
3029 congruence_class::dump (FILE *file, unsigned int indent) const
3031 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
3032 id, members[0]->get_hash (), members.length ());
3034 FPUTS_SPACES (file, indent + 2, "");
3035 for (unsigned i = 0; i < members.length (); i++)
3036 fprintf (file, "%s(%p/%u) ", members[i]->asm_name (), (void *) members[i]->decl,
3037 members[i]->node->order);
3039 fprintf (file, "\n");
3042 /* Returns true if there's a member that is used from another group. */
3045 congruence_class::is_class_used (void)
3047 for (unsigned int i = 0; i < members.length (); i++)
3048 if (members[i]->usages.length ())
3054 /* Initialization and computation of symtab node hash, there data
3055 are propagated later on. */
3057 static sem_item_optimizer *optimizer = NULL;
3059 /* Generate pass summary for IPA ICF pass. */
3062 ipa_icf_generate_summary (void)
3065 optimizer = new sem_item_optimizer ();
3067 optimizer->register_hooks ();
3068 optimizer->parse_funcs_and_vars ();
3071 /* Write pass summary for IPA ICF pass. */
3074 ipa_icf_write_summary (void)
3076 gcc_assert (optimizer);
3078 optimizer->write_summary ();
3081 /* Read pass summary for IPA ICF pass. */
3084 ipa_icf_read_summary (void)
3087 optimizer = new sem_item_optimizer ();
3089 optimizer->read_summary ();
3090 optimizer->register_hooks ();
3093 /* Semantic equality exection function. */
3096 ipa_icf_driver (void)
3098 gcc_assert (optimizer);
3100 bool merged_p = optimizer->execute ();
3105 return merged_p ? TODO_remove_functions : 0;
3108 const pass_data pass_data_ipa_icf =
3110 IPA_PASS, /* type */
3112 OPTGROUP_IPA, /* optinfo_flags */
3113 TV_IPA_ICF, /* tv_id */
3114 0, /* properties_required */
3115 0, /* properties_provided */
3116 0, /* properties_destroyed */
3117 0, /* todo_flags_start */
3118 0, /* todo_flags_finish */
3121 class pass_ipa_icf : public ipa_opt_pass_d
3124 pass_ipa_icf (gcc::context *ctxt)
3125 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
3126 ipa_icf_generate_summary, /* generate_summary */
3127 ipa_icf_write_summary, /* write_summary */
3128 ipa_icf_read_summary, /* read_summary */
3130 write_optimization_summary */
3132 read_optimization_summary */
3133 NULL, /* stmt_fixup */
3134 0, /* function_transform_todo_flags_start */
3135 NULL, /* function_transform */
3136 NULL) /* variable_transform */
3139 /* opt_pass methods: */
3140 virtual bool gate (function *)
3142 return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
3145 virtual unsigned int execute (function *)
3147 return ipa_icf_driver();
3149 }; // class pass_ipa_icf
3151 } // ipa_icf namespace
3154 make_pass_ipa_icf (gcc::context *ctxt)
3156 return new ipa_icf::pass_ipa_icf (ctxt);