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.
56 #include "coretypes.h"
60 #include "double-int.h"
68 #include "fold-const.h"
71 #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"
83 #include "gimple-iterator.h"
84 #include "gimple-ssa.h"
86 #include "tree-phinodes.h"
87 #include "stringpool.h"
88 #include "tree-ssanames.h"
90 #include "tree-pass.h"
91 #include "gimple-pretty-print.h"
93 #include "plugin-api.h"
96 #include "alloc-pool.h"
97 #include "symbol-summary.h"
99 #include "ipa-inline.h"
102 #include "hash-table.h"
103 #include "coverage.h"
105 #include "print-tree.h"
106 #include "lto-streamer.h"
107 #include "data-streamer.h"
108 #include "ipa-utils.h"
110 #include "ipa-icf-gimple.h"
114 using namespace ipa_icf_gimple;
117 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
119 sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index):
120 item (_item), index (_index)
124 /* Semantic item constructor for a node of _TYPE, where STACK is used
125 for bitmap memory allocation. */
127 sem_item::sem_item (sem_item_type _type,
128 bitmap_obstack *stack): type(_type), hash(0)
133 /* Semantic item constructor for a node of _TYPE, where STACK is used
134 for bitmap memory allocation. The item is based on symtab node _NODE
135 with computed _HASH. */
137 sem_item::sem_item (sem_item_type _type, symtab_node *_node,
138 hashval_t _hash, bitmap_obstack *stack): type(_type),
139 node (_node), hash (_hash)
145 /* Add reference to a semantic TARGET. */
148 sem_item::add_reference (sem_item *target)
150 refs.safe_push (target);
151 unsigned index = refs.length ();
152 target->usages.safe_push (new sem_usage_pair(this, index));
153 bitmap_set_bit (target->usage_index_bitmap, index);
154 refs_set.add (target->node);
157 /* Initialize internal data structures. Bitmap STACK is used for
158 bitmap memory allocation process. */
161 sem_item::setup (bitmap_obstack *stack)
163 gcc_checking_assert (node);
166 tree_refs.create (0);
168 usage_index_bitmap = BITMAP_ALLOC (stack);
171 sem_item::~sem_item ()
173 for (unsigned i = 0; i < usages.length (); i++)
177 tree_refs.release ();
180 BITMAP_FREE (usage_index_bitmap);
183 /* Dump function for debugging purpose. */
186 sem_item::dump (void)
190 fprintf (dump_file, "[%s] %s (%u) (tree:%p)\n", type == FUNC ? "func" : "var",
191 name(), node->order, (void *) node->decl);
192 fprintf (dump_file, " hash: %u\n", get_hash ());
193 fprintf (dump_file, " references: ");
195 for (unsigned i = 0; i < refs.length (); i++)
196 fprintf (dump_file, "%s%s ", refs[i]->name (),
197 i < refs.length() - 1 ? "," : "");
199 fprintf (dump_file, "\n");
203 /* Return true if target supports alias symbols. */
206 sem_item::target_supports_symbol_aliases_p (void)
208 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
215 /* Semantic function constructor that uses STACK as bitmap memory stack. */
217 sem_function::sem_function (bitmap_obstack *stack): sem_item (FUNC, stack),
218 m_checker (NULL), m_compared_func (NULL)
220 arg_types.create (0);
222 bb_sorted.create (0);
225 /* Constructor based on callgraph node _NODE with computed hash _HASH.
226 Bitmap STACK is used for memory allocation. */
227 sem_function::sem_function (cgraph_node *node, hashval_t hash,
228 bitmap_obstack *stack):
229 sem_item (FUNC, node, hash, stack),
230 m_checker (NULL), m_compared_func (NULL)
232 arg_types.create (0);
234 bb_sorted.create (0);
237 sem_function::~sem_function ()
239 for (unsigned i = 0; i < bb_sorted.length (); i++)
240 delete (bb_sorted[i]);
242 arg_types.release ();
244 bb_sorted.release ();
247 /* Calculates hash value based on a BASIC_BLOCK. */
250 sem_function::get_bb_hash (const sem_bb *basic_block)
252 inchash::hash hstate;
254 hstate.add_int (basic_block->nondbg_stmt_count);
255 hstate.add_int (basic_block->edge_count);
257 return hstate.end ();
260 /* References independent hash function. */
263 sem_function::get_hash (void)
267 inchash::hash hstate;
268 hstate.add_int (177454); /* Random number for function type. */
270 hstate.add_int (arg_count);
271 hstate.add_int (cfg_checksum);
272 hstate.add_int (gcode_hash);
274 for (unsigned i = 0; i < bb_sorted.length (); i++)
275 hstate.merge_hash (get_bb_hash (bb_sorted[i]));
277 for (unsigned i = 0; i < bb_sizes.length (); i++)
278 hstate.add_int (bb_sizes[i]);
280 hash = hstate.end ();
286 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
287 point to a same function. Comparison can be skipped if IGNORED_NODES
288 contains these nodes. */
291 sem_function::compare_cgraph_references (hash_map <symtab_node *, sem_item *>
293 symtab_node *n1, symtab_node *n2)
295 if (n1 == n2 || (ignored_nodes.get (n1) && ignored_nodes.get (n2)))
298 /* TODO: add more precise comparison for weakrefs, etc. */
300 return return_false_with_msg ("different references");
303 /* If cgraph edges E1 and E2 are indirect calls, verify that
304 ECF flags are the same. */
306 bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
308 if (e1->indirect_info && e2->indirect_info)
310 int e1_flags = e1->indirect_info->ecf_flags;
311 int e2_flags = e2->indirect_info->ecf_flags;
313 if (e1_flags != e2_flags)
314 return return_false_with_msg ("ICF flags are different");
316 else if (e1->indirect_info || e2->indirect_info)
322 /* Fast equality function based on knowledge known in WPA. */
325 sem_function::equals_wpa (sem_item *item,
326 hash_map <symtab_node *, sem_item *> &ignored_nodes)
328 gcc_assert (item->type == FUNC);
330 m_compared_func = static_cast<sem_function *> (item);
332 if (arg_types.length () != m_compared_func->arg_types.length ())
333 return return_false_with_msg ("different number of arguments");
335 /* Checking types of arguments. */
336 for (unsigned i = 0; i < arg_types.length (); i++)
338 /* This guard is here for function pointer with attributes (pr59927.c). */
339 if (!arg_types[i] || !m_compared_func->arg_types[i])
340 return return_false_with_msg ("NULL argument type");
342 /* Polymorphic comparison is executed just for non-leaf functions. */
343 bool is_not_leaf = get_node ()->callees != NULL;
345 if (!func_checker::compatible_types_p (arg_types[i],
346 m_compared_func->arg_types[i],
347 is_not_leaf, i == 0))
348 return return_false_with_msg ("argument type is different");
351 /* Result type checking. */
352 if (!func_checker::compatible_types_p (result_type,
353 m_compared_func->result_type))
354 return return_false_with_msg ("result types are different");
356 if (node->num_references () != item->node->num_references ())
357 return return_false_with_msg ("different number of references");
359 ipa_ref *ref = NULL, *ref2 = NULL;
360 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
362 item->node->iterate_reference (i, ref2);
364 if (!compare_cgraph_references (ignored_nodes, ref->referred, ref2->referred))
368 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
369 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
373 if (!compare_cgraph_references (ignored_nodes, e1->callee, e2->callee))
376 e1 = e1->next_callee;
377 e2 = e2->next_callee;
381 return return_false_with_msg ("different number of edges");
386 /* Returns true if the item equals to ITEM given as argument. */
389 sem_function::equals (sem_item *item,
390 hash_map <symtab_node *, sem_item *> &ignored_nodes)
392 gcc_assert (item->type == FUNC);
393 bool eq = equals_private (item, ignored_nodes);
395 if (m_checker != NULL)
401 if (dump_file && (dump_flags & TDF_DETAILS))
403 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
404 name(), item->name (), node->order, item->node->order, asm_name (),
405 item->asm_name (), eq ? "true" : "false");
410 /* Processes function equality comparison. */
413 sem_function::equals_private (sem_item *item,
414 hash_map <symtab_node *, sem_item *> &ignored_nodes)
416 if (item->type != FUNC)
419 basic_block bb1, bb2;
421 edge_iterator ei1, ei2;
425 m_compared_func = static_cast<sem_function *> (item);
427 gcc_assert (decl != item->decl);
429 if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
430 || edge_count != m_compared_func->edge_count
431 || cfg_checksum != m_compared_func->cfg_checksum)
432 return return_false ();
434 if (!equals_wpa (item, ignored_nodes))
437 /* Checking function TARGET and OPTIMIZATION flags. */
438 cl_target_option *tar1 = target_opts_for_fn (decl);
439 cl_target_option *tar2 = target_opts_for_fn (m_compared_func->decl);
441 if (tar1 != NULL || tar2 != NULL)
443 if (!cl_target_option_eq (tar1, tar2))
445 if (dump_file && (dump_flags & TDF_DETAILS))
447 fprintf (dump_file, "Source target flags\n");
448 cl_target_option_print (dump_file, 2, tar1);
449 fprintf (dump_file, "Target target flags\n");
450 cl_target_option_print (dump_file, 2, tar2);
453 return return_false_with_msg ("Target flags are different");
456 else if (tar1 != NULL || tar2 != NULL)
457 return return_false_with_msg ("Target flags are different");
459 cl_optimization *opt1 = opts_for_fn (decl);
460 cl_optimization *opt2 = opts_for_fn (m_compared_func->decl);
462 if (opt1 != NULL && opt2 != NULL)
464 if (memcmp (opt1, opt2, sizeof(cl_optimization)))
466 if (dump_file && (dump_flags & TDF_DETAILS))
468 fprintf (dump_file, "Source optimization flags\n");
469 cl_optimization_print (dump_file, 2, opt1);
470 fprintf (dump_file, "Target optimization flags\n");
471 cl_optimization_print (dump_file, 2, opt2);
474 return return_false_with_msg ("optimization flags are different");
477 else if (opt1 != NULL || opt2 != NULL)
478 return return_false_with_msg ("optimization flags are different");
480 /* Checking function arguments. */
481 tree decl1 = DECL_ATTRIBUTES (decl);
482 tree decl2 = DECL_ATTRIBUTES (m_compared_func->decl);
484 m_checker = new func_checker (decl, m_compared_func->decl,
485 compare_polymorphic_p (),
488 &m_compared_func->refs_set);
492 return return_false ();
494 if (get_attribute_name (decl1) != get_attribute_name (decl2))
495 return return_false ();
497 tree attr_value1 = TREE_VALUE (decl1);
498 tree attr_value2 = TREE_VALUE (decl2);
500 if (attr_value1 && attr_value2)
502 bool ret = m_checker->compare_operand (TREE_VALUE (attr_value1),
503 TREE_VALUE (attr_value2));
505 return return_false_with_msg ("attribute values are different");
507 else if (!attr_value1 && !attr_value2)
510 return return_false ();
512 decl1 = TREE_CHAIN (decl1);
513 decl2 = TREE_CHAIN (decl2);
517 return return_false();
520 for (arg1 = DECL_ARGUMENTS (decl),
521 arg2 = DECL_ARGUMENTS (m_compared_func->decl);
522 arg1; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2))
523 if (!m_checker->compare_decl (arg1, arg2))
524 return return_false ();
526 /* Fill-up label dictionary. */
527 for (unsigned i = 0; i < bb_sorted.length (); ++i)
529 m_checker->parse_labels (bb_sorted[i]);
530 m_checker->parse_labels (m_compared_func->bb_sorted[i]);
533 /* Checking all basic blocks. */
534 for (unsigned i = 0; i < bb_sorted.length (); ++i)
535 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
536 return return_false();
538 dump_message ("All BBs are equal\n");
540 auto_vec <int> bb_dict;
542 /* Basic block edges check. */
543 for (unsigned i = 0; i < bb_sorted.length (); ++i)
545 bb1 = bb_sorted[i]->bb;
546 bb2 = m_compared_func->bb_sorted[i]->bb;
548 ei2 = ei_start (bb2->preds);
550 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
554 if (e1->flags != e2->flags)
555 return return_false_with_msg ("flags comparison returns false");
557 if (!bb_dict_test (bb_dict, e1->src->index, e2->src->index))
558 return return_false_with_msg ("edge comparison returns false");
560 if (!bb_dict_test (bb_dict, e1->dest->index, e2->dest->index))
561 return return_false_with_msg ("BB comparison returns false");
563 if (!m_checker->compare_edge (e1, e2))
564 return return_false_with_msg ("edge comparison returns false");
570 /* Basic block PHI nodes comparison. */
571 for (unsigned i = 0; i < bb_sorted.length (); i++)
572 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
573 return return_false_with_msg ("PHI node comparison returns false");
578 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
581 sem_function::merge (sem_item *alias_item)
583 gcc_assert (alias_item->type == FUNC);
585 sem_function *alias_func = static_cast<sem_function *> (alias_item);
587 cgraph_node *original = get_node ();
588 cgraph_node *local_original = original;
589 cgraph_node *alias = alias_func->get_node ();
590 bool original_address_matters;
591 bool alias_address_matters;
593 bool create_thunk = false;
594 bool create_alias = false;
595 bool redirect_callers = false;
596 bool original_discardable = false;
598 /* Do not attempt to mix functions from different user sections;
599 we do not know what user intends with those. */
600 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
601 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
602 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
606 "Not unifying; original and alias are in different sections.\n\n");
610 /* See if original is in a section that can be discarded if the main
611 symbol is not used. */
612 if (DECL_EXTERNAL (original->decl))
613 original_discardable = true;
614 if (original->resolution == LDPR_PREEMPTED_REG
615 || original->resolution == LDPR_PREEMPTED_IR)
616 original_discardable = true;
617 if (original->can_be_discarded_p ())
618 original_discardable = true;
620 /* See if original and/or alias address can be compared for equality. */
621 original_address_matters
622 = (!DECL_VIRTUAL_P (original->decl)
623 && (original->externally_visible
624 || original->address_taken_from_non_vtable_p ()));
625 alias_address_matters
626 = (!DECL_VIRTUAL_P (alias->decl)
627 && (alias->externally_visible
628 || alias->address_taken_from_non_vtable_p ()));
630 /* If alias and original can be compared for address equality, we need
631 to create a thunk. Also we can not create extra aliases into discardable
632 section (or we risk link failures when section is discarded). */
633 if ((original_address_matters
634 && alias_address_matters)
635 || original_discardable)
637 create_thunk = !stdarg_p (TREE_TYPE (alias->decl));
638 create_alias = false;
639 /* When both alias and original are not overwritable, we can save
640 the extra thunk wrapper for direct calls. */
642 = (!original_discardable
643 && alias->get_availability () > AVAIL_INTERPOSABLE
644 && original->get_availability () > AVAIL_INTERPOSABLE
645 && !alias->instrumented_version);
650 create_thunk = false;
651 redirect_callers = false;
654 if (create_alias && (DECL_COMDAT_GROUP (alias->decl)
655 || !sem_item::target_supports_symbol_aliases_p ()))
657 create_alias = false;
661 /* We want thunk to always jump to the local function body
662 unless the body is comdat and may be optimized out. */
663 if ((create_thunk || redirect_callers)
664 && (!original_discardable
665 || (DECL_COMDAT_GROUP (original->decl)
666 && (DECL_COMDAT_GROUP (original->decl)
667 == DECL_COMDAT_GROUP (alias->decl)))))
669 = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
674 fprintf (dump_file, "Noninterposable alias cannot be created.\n\n");
679 if (!decl_binds_to_current_def_p (alias->decl))
682 fprintf (dump_file, "Declaration does not bind to currect definition.\n\n");
686 if (redirect_callers)
688 /* If alias is non-overwritable then
689 all direct calls are safe to be redirected to the original. */
690 bool redirected = false;
691 while (alias->callers)
693 cgraph_edge *e = alias->callers;
694 e->redirect_callee (local_original);
695 push_cfun (DECL_STRUCT_FUNCTION (e->caller->decl));
698 e->redirect_call_stmt_to_callee ();
704 alias->icf_merged = true;
706 /* The alias function is removed if symbol address
708 if (!alias_address_matters)
711 if (dump_file && redirected)
712 fprintf (dump_file, "Callgraph local calls have been redirected.\n\n");
714 /* If the condtion above is not met, we are lucky and can turn the
715 function into real alias. */
716 else if (create_alias)
718 alias->icf_merged = true;
720 /* Remove the function's body. */
721 ipa_merge_profiles (original, alias);
722 alias->release_body (true);
725 /* Create the alias. */
726 cgraph_node::create_alias (alias_func->decl, decl);
727 alias->resolve_alias (original);
729 /* Workaround for PR63566 that forces equal calling convention
731 alias->local.local = false;
732 original->local.local = false;
735 fprintf (dump_file, "Callgraph alias has been created.\n\n");
737 else if (create_thunk)
739 if (DECL_COMDAT_GROUP (alias->decl))
742 fprintf (dump_file, "Callgraph thunk cannot be created because of COMDAT\n");
747 if (DECL_STATIC_CHAIN (alias->decl))
750 fprintf (dump_file, "Thunk creation is risky for static-chain functions.\n\n");
755 alias->icf_merged = true;
756 ipa_merge_profiles (local_original, alias);
757 alias->create_wrapper (local_original);
760 fprintf (dump_file, "Callgraph thunk has been created.\n\n");
763 fprintf (dump_file, "Callgraph merge operation cannot be performed.\n\n");
768 /* Semantic item initialization function. */
771 sem_function::init (void)
774 get_node ()->get_untransformed_body ();
776 tree fndecl = node->decl;
777 function *func = DECL_STRUCT_FUNCTION (fndecl);
780 gcc_assert (SSANAMES (func));
782 ssa_names_size = SSANAMES (func)->length ();
786 region_tree = func->eh->region_tree;
788 /* iterating all function arguments. */
789 arg_count = count_formal_params (fndecl);
791 edge_count = n_edges_for_fn (func);
792 cfg_checksum = coverage_compute_cfg_checksum (func);
794 inchash::hash hstate;
797 FOR_EACH_BB_FN (bb, func)
799 unsigned nondbg_stmt_count = 0;
802 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e); ei_next (&ei))
803 cfg_checksum = iterative_hash_host_wide_int (e->flags,
806 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
809 gimple stmt = gsi_stmt (gsi);
811 if (gimple_code (stmt) != GIMPLE_DEBUG)
813 hash_stmt (&hstate, stmt);
818 gcode_hash = hstate.end ();
819 bb_sizes.safe_push (nondbg_stmt_count);
821 /* Inserting basic block to hash table. */
822 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
823 EDGE_COUNT (bb->preds) + EDGE_COUNT (bb->succs));
825 bb_sorted.safe_push (semantic_bb);
831 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
834 sem_function::hash_stmt (inchash::hash *hstate, gimple stmt)
836 enum gimple_code code = gimple_code (stmt);
838 hstate->add_int (code);
840 if (code == GIMPLE_CALL)
842 /* Checking of argument. */
843 for (unsigned i = 0; i < gimple_call_num_args (stmt); ++i)
845 tree argument = gimple_call_arg (stmt, i);
847 switch (TREE_CODE (argument))
850 if (tree_fits_shwi_p (argument))
851 hstate->add_wide_int (tree_to_shwi (argument));
852 else if (tree_fits_uhwi_p (argument))
853 hstate->add_wide_int (tree_to_uhwi (argument));
859 c = TREE_REAL_CST (argument);
860 n = real_to_integer (&c);
862 hstate->add_wide_int (n);
866 tree addr_operand = TREE_OPERAND (argument, 0);
868 if (TREE_CODE (addr_operand) == STRING_CST)
869 hstate->add (TREE_STRING_POINTER (addr_operand),
870 TREE_STRING_LENGTH (addr_operand));
881 /* Return true if polymorphic comparison must be processed. */
884 sem_function::compare_polymorphic_p (void)
886 return get_node ()->callees != NULL
887 || m_compared_func->get_node ()->callees != NULL;
890 /* For a given call graph NODE, the function constructs new
891 semantic function item. */
894 sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
896 tree fndecl = node->decl;
897 function *func = DECL_STRUCT_FUNCTION (fndecl);
899 /* TODO: add support for thunks and aliases. */
901 if (!func || !node->has_gimple_body_p ())
904 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
907 sem_function *f = new sem_function (node, 0, stack);
914 /* Parses function arguments and result type. */
917 sem_function::parse_tree_args (void)
921 if (arg_types.exists ())
922 arg_types.release ();
924 arg_types.create (4);
925 tree fnargs = DECL_ARGUMENTS (decl);
927 for (tree parm = fnargs; parm; parm = DECL_CHAIN (parm))
928 arg_types.safe_push (DECL_ARG_TYPE (parm));
930 /* Function result type. */
931 result = DECL_RESULT (decl);
932 result_type = result ? TREE_TYPE (result) : NULL;
934 /* During WPA, we can get arguments by following method. */
937 tree type = TYPE_ARG_TYPES (TREE_TYPE (decl));
938 for (tree parm = type; parm; parm = TREE_CHAIN (parm))
939 arg_types.safe_push (TYPE_CANONICAL (TREE_VALUE (parm)));
941 result_type = TREE_TYPE (TREE_TYPE (decl));
945 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
946 return true if phi nodes are semantically equivalent in these blocks . */
949 sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
951 gphi_iterator si1, si2;
953 unsigned size1, size2, i;
957 gcc_assert (bb1 != NULL);
958 gcc_assert (bb2 != NULL);
960 si2 = gsi_start_phis (bb2);
961 for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
964 gsi_next_nonvirtual_phi (&si1);
965 gsi_next_nonvirtual_phi (&si2);
967 if (gsi_end_p (si1) && gsi_end_p (si2))
970 if (gsi_end_p (si1) || gsi_end_p (si2))
971 return return_false();
976 tree phi_result1 = gimple_phi_result (phi1);
977 tree phi_result2 = gimple_phi_result (phi2);
979 if (!m_checker->compare_operand (phi_result1, phi_result2))
980 return return_false_with_msg ("PHI results are different");
982 size1 = gimple_phi_num_args (phi1);
983 size2 = gimple_phi_num_args (phi2);
986 return return_false ();
988 for (i = 0; i < size1; ++i)
990 t1 = gimple_phi_arg (phi1, i)->def;
991 t2 = gimple_phi_arg (phi2, i)->def;
993 if (!m_checker->compare_operand (t1, t2))
994 return return_false ();
996 e1 = gimple_phi_arg_edge (phi1, i);
997 e2 = gimple_phi_arg_edge (phi2, i);
999 if (!m_checker->compare_edge (e1, e2))
1000 return return_false ();
1009 /* Returns true if tree T can be compared as a handled component. */
1012 sem_function::icf_handled_component_p (tree t)
1014 tree_code tc = TREE_CODE (t);
1016 return ((handled_component_p (t))
1017 || tc == ADDR_EXPR || tc == MEM_REF || tc == REALPART_EXPR
1018 || tc == IMAGPART_EXPR || tc == OBJ_TYPE_REF);
1021 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1022 corresponds to TARGET. */
1025 sem_function::bb_dict_test (auto_vec<int> bb_dict, int source, int target)
1030 if (bb_dict.length () <= (unsigned)source)
1031 bb_dict.safe_grow_cleared (source + 1);
1033 if (bb_dict[source] == 0)
1035 bb_dict[source] = target;
1039 return bb_dict[source] == target;
1042 /* Iterates all tree types in T1 and T2 and returns true if all types
1043 are compatible. If COMPARE_POLYMORPHIC is set to true,
1044 more strict comparison is executed. */
1047 sem_function::compare_type_list (tree t1, tree t2, bool compare_polymorphic)
1055 while (t1 != NULL && t2 != NULL)
1057 tv1 = TREE_VALUE (t1);
1058 tv2 = TREE_VALUE (t2);
1060 tc1 = TREE_CODE (tv1);
1061 tc2 = TREE_CODE (tv2);
1063 if (tc1 == NOP_EXPR && tc2 == NOP_EXPR)
1065 else if (tc1 == NOP_EXPR || tc2 == NOP_EXPR)
1067 else if (!func_checker::compatible_types_p (tv1, tv2, compare_polymorphic))
1070 t1 = TREE_CHAIN (t1);
1071 t2 = TREE_CHAIN (t2);
1078 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1080 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
1084 /* Constructor based on varpool node _NODE with computed hash _HASH.
1085 Bitmap STACK is used for memory allocation. */
1087 sem_variable::sem_variable (varpool_node *node, hashval_t _hash,
1088 bitmap_obstack *stack): sem_item(VAR,
1091 gcc_checking_assert (node);
1092 gcc_checking_assert (get_node ());
1095 /* Returns true if the item equals to ITEM given as argument. */
1098 sem_variable::equals (sem_item *item,
1099 hash_map <symtab_node *, sem_item *> & ARG_UNUSED (ignored_nodes))
1101 gcc_assert (item->type == VAR);
1103 sem_variable *v = static_cast<sem_variable *>(item);
1105 if (!ctor || !v->ctor)
1106 return return_false_with_msg ("ctor is missing for semantic variable");
1108 return sem_variable::equals (ctor, v->ctor);
1111 /* Compares trees T1 and T2 for semantic equality. */
1114 sem_variable::equals (tree t1, tree t2)
1116 tree_code tc1 = TREE_CODE (t1);
1117 tree_code tc2 = TREE_CODE (t2);
1126 unsigned len1 = vec_safe_length (CONSTRUCTOR_ELTS (t1));
1127 unsigned len2 = vec_safe_length (CONSTRUCTOR_ELTS (t2));
1132 for (unsigned i = 0; i < len1; i++)
1133 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1, i)->value,
1134 CONSTRUCTOR_ELT (t2, i)->value)
1135 || CONSTRUCTOR_ELT (t1, i)->index != CONSTRUCTOR_ELT (t2, i)->index)
1142 tree x1 = TREE_OPERAND (t1, 0);
1143 tree x2 = TREE_OPERAND (t2, 0);
1144 tree y1 = TREE_OPERAND (t1, 1);
1145 tree y2 = TREE_OPERAND (t2, 1);
1147 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2),
1149 return return_false ();
1151 /* Type of the offset on MEM_REF does not matter. */
1152 return sem_variable::equals (x1, x2)
1153 && wi::to_offset (y1) == wi::to_offset (y2);
1158 tree op1 = TREE_OPERAND (t1, 0);
1159 tree op2 = TREE_OPERAND (t2, 0);
1160 return sem_variable::equals (op1, op2);
1168 return func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
1170 && wi::to_offset (t1) == wi::to_offset (t2);
1174 return operand_equal_p (t1, t2, OEP_ONLY_CONST);
1177 case POINTER_PLUS_EXPR:
1179 tree x1 = TREE_OPERAND (t1, 0);
1180 tree x2 = TREE_OPERAND (t2, 0);
1181 tree y1 = TREE_OPERAND (t1, 1);
1182 tree y2 = TREE_OPERAND (t2, 1);
1184 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
1187 return return_false_with_msg ("ERROR_MARK");
1189 return return_false_with_msg ("Unknown TREE code reached");
1193 /* Parser function that visits a varpool NODE. */
1196 sem_variable::parse (varpool_node *node, bitmap_obstack *stack)
1198 tree decl = node->decl;
1200 bool readonly = TYPE_P (decl) ? TYPE_READONLY (decl) : TREE_READONLY (decl);
1204 bool can_handle = DECL_VIRTUAL_P (decl)
1205 || flag_merge_constants >= 2
1206 || (!TREE_ADDRESSABLE (decl) && !node->externally_visible);
1208 if (!can_handle || DECL_EXTERNAL (decl))
1211 tree ctor = ctor_for_folding (decl);
1215 sem_variable *v = new sem_variable (node, 0, stack);
1222 /* References independent hash function. */
1225 sem_variable::get_hash (void)
1230 inchash::hash hstate;
1232 hstate.add_int (456346417);
1233 hstate.add_int (TREE_CODE (ctor));
1235 if (TREE_CODE (ctor) == CONSTRUCTOR)
1237 unsigned length = vec_safe_length (CONSTRUCTOR_ELTS (ctor));
1238 hstate.add_int (length);
1241 hash = hstate.end ();
1246 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1250 sem_variable::merge (sem_item *alias_item)
1252 gcc_assert (alias_item->type == VAR);
1254 if (!sem_item::target_supports_symbol_aliases_p ())
1257 fprintf (dump_file, "Symbol aliases are not supported by target\n\n");
1261 sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
1263 varpool_node *original = get_node ();
1264 varpool_node *alias = alias_var->get_node ();
1265 bool original_discardable = false;
1267 /* See if original is in a section that can be discarded if the main
1268 symbol is not used. */
1269 if (DECL_EXTERNAL (original->decl))
1270 original_discardable = true;
1271 if (original->resolution == LDPR_PREEMPTED_REG
1272 || original->resolution == LDPR_PREEMPTED_IR)
1273 original_discardable = true;
1274 if (original->can_be_discarded_p ())
1275 original_discardable = true;
1277 gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
1279 if (original_discardable || DECL_EXTERNAL (alias_var->decl) ||
1280 !compare_sections (alias_var))
1283 fprintf (dump_file, "Varpool alias cannot be created\n\n");
1289 // alias cycle creation check
1290 varpool_node *n = original;
1294 n = n->get_alias_target ();
1298 fprintf (dump_file, "Varpool alias cannot be created (alias cycle).\n\n");
1304 alias->analyzed = false;
1306 DECL_INITIAL (alias->decl) = NULL;
1307 alias->need_bounds_init = false;
1308 alias->remove_all_references ();
1310 varpool_node::create_alias (alias_var->decl, decl);
1311 alias->resolve_alias (original);
1314 fprintf (dump_file, "Varpool alias has been created.\n\n");
1321 sem_variable::compare_sections (sem_variable *alias)
1323 const char *source = node->get_section ();
1324 const char *target = alias->node->get_section();
1326 if (source == NULL && target == NULL)
1328 else if(!source || !target)
1331 return strcmp (source, target) == 0;
1334 /* Dump symbol to FILE. */
1337 sem_variable::dump_to_file (FILE *file)
1341 print_node (file, "", decl, 0);
1342 fprintf (file, "\n\n");
1345 /* Iterates though a constructor and identifies tree references
1346 we are interested in semantic function equality. */
1349 sem_variable::parse_tree_refs (tree t)
1351 switch (TREE_CODE (t))
1355 unsigned length = vec_safe_length (CONSTRUCTOR_ELTS (t));
1357 for (unsigned i = 0; i < length; i++)
1358 parse_tree_refs(CONSTRUCTOR_ELT (t, i)->value);
1365 tree op = TREE_OPERAND (t, 0);
1366 parse_tree_refs (op);
1371 tree_refs.safe_push (t);
1379 unsigned int sem_item_optimizer::class_id = 0;
1381 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1382 m_classes_count (0), m_cgraph_node_hooks (NULL), m_varpool_node_hooks (NULL)
1385 bitmap_obstack_initialize (&m_bmstack);
1388 sem_item_optimizer::~sem_item_optimizer ()
1390 for (unsigned int i = 0; i < m_items.length (); i++)
1393 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
1394 it != m_classes.end (); ++it)
1396 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
1397 delete (*it)->classes[i];
1399 (*it)->classes.release ();
1405 bitmap_obstack_release (&m_bmstack);
1408 /* Write IPA ICF summary for symbols. */
1411 sem_item_optimizer::write_summary (void)
1413 unsigned int count = 0;
1415 output_block *ob = create_output_block (LTO_section_ipa_icf);
1416 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
1419 /* Calculate number of symbols to be serialized. */
1420 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
1422 lsei_next_in_partition (&lsei))
1424 symtab_node *node = lsei_node (lsei);
1426 if (m_symtab_node_map.get (node))
1430 streamer_write_uhwi (ob, count);
1432 /* Process all of the symbols. */
1433 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
1435 lsei_next_in_partition (&lsei))
1437 symtab_node *node = lsei_node (lsei);
1439 sem_item **item = m_symtab_node_map.get (node);
1443 int node_ref = lto_symtab_encoder_encode (encoder, node);
1444 streamer_write_uhwi_stream (ob->main_stream, node_ref);
1446 streamer_write_uhwi (ob, (*item)->get_hash ());
1450 streamer_write_char_stream (ob->main_stream, 0);
1451 produce_asm (ob, NULL);
1452 destroy_output_block (ob);
1455 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1456 contains LEN bytes. */
1459 sem_item_optimizer::read_section (lto_file_decl_data *file_data,
1460 const char *data, size_t len)
1462 const lto_function_header *header =
1463 (const lto_function_header *) data;
1464 const int cfg_offset = sizeof (lto_function_header);
1465 const int main_offset = cfg_offset + header->cfg_size;
1466 const int string_offset = main_offset + header->main_size;
1471 lto_input_block ib_main ((const char *) data + main_offset, 0,
1475 lto_data_in_create (file_data, (const char *) data + string_offset,
1476 header->string_size, vNULL);
1478 count = streamer_read_uhwi (&ib_main);
1480 for (i = 0; i < count; i++)
1484 lto_symtab_encoder_t encoder;
1486 index = streamer_read_uhwi (&ib_main);
1487 encoder = file_data->symtab_node_encoder;
1488 node = lto_symtab_encoder_deref (encoder, index);
1490 hashval_t hash = streamer_read_uhwi (&ib_main);
1492 gcc_assert (node->definition);
1495 fprintf (dump_file, "Symbol added:%s (tree: %p, uid:%u)\n", node->asm_name (),
1496 (void *) node->decl, node->order);
1498 if (is_a<cgraph_node *> (node))
1500 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1502 m_items.safe_push (new sem_function (cnode, hash, &m_bmstack));
1506 varpool_node *vnode = dyn_cast <varpool_node *> (node);
1508 m_items.safe_push (new sem_variable (vnode, hash, &m_bmstack));
1512 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
1514 lto_data_in_delete (data_in);
1517 /* Read IPA IPA ICF summary for symbols. */
1520 sem_item_optimizer::read_summary (void)
1522 lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
1523 lto_file_decl_data *file_data;
1526 while ((file_data = file_data_vec[j++]))
1529 const char *data = lto_get_section_data (file_data,
1530 LTO_section_ipa_icf, NULL, &len);
1533 read_section (file_data, data, len);
1537 /* Register callgraph and varpool hooks. */
1540 sem_item_optimizer::register_hooks (void)
1542 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
1543 (&sem_item_optimizer::cgraph_removal_hook, this);
1545 m_varpool_node_hooks = symtab->add_varpool_removal_hook
1546 (&sem_item_optimizer::varpool_removal_hook, this);
1549 /* Unregister callgraph and varpool hooks. */
1552 sem_item_optimizer::unregister_hooks (void)
1554 if (m_cgraph_node_hooks)
1555 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
1557 if (m_varpool_node_hooks)
1558 symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
1561 /* Adds a CLS to hashtable associated by hash value. */
1564 sem_item_optimizer::add_class (congruence_class *cls)
1566 gcc_assert (cls->members.length ());
1568 congruence_class_group *group = get_group_by_hash (
1569 cls->members[0]->get_hash (),
1570 cls->members[0]->type);
1571 group->classes.safe_push (cls);
1574 /* Gets a congruence class group based on given HASH value and TYPE. */
1576 congruence_class_group *
1577 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
1579 congruence_class_group *item = XNEW (congruence_class_group);
1583 congruence_class_group **slot = m_classes.find_slot (item, INSERT);
1589 item->classes.create (1);
1596 /* Callgraph removal hook called for a NODE with a custom DATA. */
1599 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
1601 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
1602 optimizer->remove_symtab_node (node);
1605 /* Varpool removal hook called for a NODE with a custom DATA. */
1608 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
1610 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
1611 optimizer->remove_symtab_node (node);
1614 /* Remove symtab NODE triggered by symtab removal hooks. */
1617 sem_item_optimizer::remove_symtab_node (symtab_node *node)
1619 gcc_assert (!m_classes.elements());
1621 m_removed_items_set.add (node);
1625 sem_item_optimizer::remove_item (sem_item *item)
1627 if (m_symtab_node_map.get (item->node))
1628 m_symtab_node_map.remove (item->node);
1632 /* Removes all callgraph and varpool nodes that are marked by symtab
1636 sem_item_optimizer::filter_removed_items (void)
1638 auto_vec <sem_item *> filtered;
1640 for (unsigned int i = 0; i < m_items.length(); i++)
1642 sem_item *item = m_items[i];
1644 if (!flag_ipa_icf_functions && item->type == FUNC)
1650 if (!flag_ipa_icf_variables && item->type == VAR)
1656 bool no_body_function = false;
1658 if (item->type == FUNC)
1660 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
1662 no_body_function = in_lto_p && (cnode->alias || cnode->body_removed);
1665 if(!m_removed_items_set.contains (m_items[i]->node)
1666 && !no_body_function)
1668 if (item->type == VAR || (!DECL_CXX_CONSTRUCTOR_P (item->decl)
1669 && !DECL_CXX_DESTRUCTOR_P (item->decl)))
1671 filtered.safe_push (m_items[i]);
1679 /* Clean-up of released semantic items. */
1682 for (unsigned int i = 0; i < filtered.length(); i++)
1683 m_items.safe_push (filtered[i]);
1686 /* Optimizer entry point. */
1689 sem_item_optimizer::execute (void)
1691 filter_removed_items ();
1692 build_hash_based_classes ();
1695 fprintf (dump_file, "Dump after hash based groups\n");
1696 dump_cong_classes ();
1698 for (unsigned int i = 0; i < m_items.length(); i++)
1699 m_items[i]->init_wpa ();
1703 subdivide_classes_by_equality (true);
1706 fprintf (dump_file, "Dump after WPA based types groups\n");
1708 dump_cong_classes ();
1710 process_cong_reduction ();
1714 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
1716 dump_cong_classes ();
1718 parse_nonsingleton_classes ();
1719 subdivide_classes_by_equality ();
1722 fprintf (dump_file, "Dump after full equality comparison of groups\n");
1724 dump_cong_classes ();
1726 unsigned int prev_class_count = m_classes_count;
1728 process_cong_reduction ();
1729 dump_cong_classes ();
1731 merge_classes (prev_class_count);
1733 if (dump_file && (dump_flags & TDF_DETAILS))
1734 symtab_node::dump_table (dump_file);
1737 /* Function responsible for visiting all potential functions and
1738 read-only variables that can be merged. */
1741 sem_item_optimizer::parse_funcs_and_vars (void)
1745 if (flag_ipa_icf_functions)
1746 FOR_EACH_DEFINED_FUNCTION (cnode)
1748 sem_function *f = sem_function::parse (cnode, &m_bmstack);
1751 m_items.safe_push (f);
1752 m_symtab_node_map.put (cnode, f);
1755 fprintf (dump_file, "Parsed function:%s\n", f->asm_name ());
1757 if (dump_file && (dump_flags & TDF_DETAILS))
1758 f->dump_to_file (dump_file);
1761 fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
1764 varpool_node *vnode;
1766 if (flag_ipa_icf_variables)
1767 FOR_EACH_DEFINED_VARIABLE (vnode)
1769 sem_variable *v = sem_variable::parse (vnode, &m_bmstack);
1773 m_items.safe_push (v);
1774 m_symtab_node_map.put (vnode, v);
1779 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1782 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
1784 item->index_in_class = cls->members.length ();
1785 cls->members.safe_push (item);
1789 /* Congruence classes are built by hash value. */
1792 sem_item_optimizer::build_hash_based_classes (void)
1794 for (unsigned i = 0; i < m_items.length (); i++)
1796 sem_item *item = m_items[i];
1798 congruence_class_group *group = get_group_by_hash (item->get_hash (),
1801 if (!group->classes.length ())
1804 group->classes.safe_push (new congruence_class (class_id++));
1807 add_item_to_class (group->classes[0], item);
1811 /* Build references according to call graph. */
1814 sem_item_optimizer::build_graph (void)
1816 for (unsigned i = 0; i < m_items.length (); i++)
1818 sem_item *item = m_items[i];
1819 m_symtab_node_map.put (item->node, item);
1822 for (unsigned i = 0; i < m_items.length (); i++)
1824 sem_item *item = m_items[i];
1826 if (item->type == FUNC)
1828 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
1830 cgraph_edge *e = cnode->callees;
1833 sem_item **slot = m_symtab_node_map.get (e->callee);
1835 item->add_reference (*slot);
1841 ipa_ref *ref = NULL;
1842 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
1844 sem_item **slot = m_symtab_node_map.get (ref->referred);
1846 item->add_reference (*slot);
1851 /* Semantic items in classes having more than one element and initialized.
1852 In case of WPA, we load function body. */
1855 sem_item_optimizer::parse_nonsingleton_classes (void)
1857 unsigned int init_called_count = 0;
1859 for (unsigned i = 0; i < m_items.length (); i++)
1860 if (m_items[i]->cls->members.length () > 1)
1862 m_items[i]->init ();
1863 init_called_count++;
1867 fprintf (dump_file, "Init called for %u items (%.2f%%).\n", init_called_count,
1868 m_items.length () ? 100.0f * init_called_count / m_items.length (): 0.0f);
1871 /* Equality function for semantic items is used to subdivide existing
1872 classes. If IN_WPA, fast equality function is invoked. */
1875 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
1877 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
1878 it != m_classes.end (); ++it)
1880 unsigned int class_count = (*it)->classes.length ();
1882 for (unsigned i = 0; i < class_count; i++)
1884 congruence_class *c = (*it)->classes [i];
1886 if (c->members.length() > 1)
1888 auto_vec <sem_item *> new_vector;
1890 sem_item *first = c->members[0];
1891 new_vector.safe_push (first);
1893 unsigned class_split_first = (*it)->classes.length ();
1895 for (unsigned j = 1; j < c->members.length (); j++)
1897 sem_item *item = c->members[j];
1899 bool equals = in_wpa ? first->equals_wpa (item,
1900 m_symtab_node_map) : first->equals (item, m_symtab_node_map);
1903 new_vector.safe_push (item);
1906 bool integrated = false;
1908 for (unsigned k = class_split_first; k < (*it)->classes.length (); k++)
1910 sem_item *x = (*it)->classes[k]->members[0];
1911 bool equals = in_wpa ? x->equals_wpa (item,
1912 m_symtab_node_map) : x->equals (item, m_symtab_node_map);
1917 add_item_to_class ((*it)->classes[k], item);
1925 congruence_class *c = new congruence_class (class_id++);
1927 add_item_to_class (c, item);
1929 (*it)->classes.safe_push (c);
1934 // we replace newly created new_vector for the class we've just splitted
1935 c->members.release ();
1936 c->members.create (new_vector.length ());
1938 for (unsigned int j = 0; j < new_vector.length (); j++)
1939 add_item_to_class (c, new_vector[j]);
1947 /* Verify congruence classes if checking is enabled. */
1950 sem_item_optimizer::verify_classes (void)
1953 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
1954 it != m_classes.end (); ++it)
1956 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
1958 congruence_class *cls = (*it)->classes[i];
1960 gcc_checking_assert (cls);
1961 gcc_checking_assert (cls->members.length () > 0);
1963 for (unsigned int j = 0; j < cls->members.length (); j++)
1965 sem_item *item = cls->members[j];
1967 gcc_checking_assert (item);
1968 gcc_checking_assert (item->cls == cls);
1970 for (unsigned k = 0; k < item->usages.length (); k++)
1972 sem_usage_pair *usage = item->usages[k];
1973 gcc_checking_assert (usage->item->index_in_class <
1974 usage->item->cls->members.length ());
1982 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
1983 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
1984 but unused argument. */
1987 sem_item_optimizer::release_split_map (congruence_class * const &,
1988 bitmap const &b, traverse_split_pair *)
1997 /* Process split operation for a class given as pointer CLS_PTR,
1998 where bitmap B splits congruence class members. DATA is used
1999 as argument of split pair. */
2002 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
2003 bitmap const &b, traverse_split_pair *pair)
2005 sem_item_optimizer *optimizer = pair->optimizer;
2006 const congruence_class *splitter_cls = pair->cls;
2008 /* If counted bits are greater than zero and less than the number of members
2009 a group will be splitted. */
2010 unsigned popcount = bitmap_count_bits (b);
2012 if (popcount > 0 && popcount < cls->members.length ())
2014 congruence_class* newclasses[2] = { new congruence_class (class_id++), new congruence_class (class_id++) };
2016 for (unsigned int i = 0; i < cls->members.length (); i++)
2018 int target = bitmap_bit_p (b, i);
2019 congruence_class *tc = newclasses[target];
2021 add_item_to_class (tc, cls->members[i]);
2024 #ifdef ENABLE_CHECKING
2025 for (unsigned int i = 0; i < 2; i++)
2026 gcc_checking_assert (newclasses[i]->members.length ());
2029 if (splitter_cls == cls)
2030 optimizer->splitter_class_removed = true;
2032 /* Remove old class from worklist if presented. */
2033 bool in_worklist = cls->in_worklist;
2036 cls->in_worklist = false;
2038 congruence_class_group g;
2039 g.hash = cls->members[0]->get_hash ();
2040 g.type = cls->members[0]->type;
2042 congruence_class_group *slot = optimizer->m_classes.find(&g);
2044 for (unsigned int i = 0; i < slot->classes.length (); i++)
2045 if (slot->classes[i] == cls)
2047 slot->classes.ordered_remove (i);
2051 /* New class will be inserted and integrated to work list. */
2052 for (unsigned int i = 0; i < 2; i++)
2053 optimizer->add_class (newclasses[i]);
2055 /* Two classes replace one, so that increment just by one. */
2056 optimizer->m_classes_count++;
2058 /* If OLD class was presented in the worklist, we remove the class
2059 and replace it will both newly created classes. */
2061 for (unsigned int i = 0; i < 2; i++)
2062 optimizer->worklist_push (newclasses[i]);
2063 else /* Just smaller class is inserted. */
2065 unsigned int smaller_index = newclasses[0]->members.length () <
2066 newclasses[1]->members.length () ?
2068 optimizer->worklist_push (newclasses[smaller_index]);
2071 if (dump_file && (dump_flags & TDF_DETAILS))
2073 fprintf (dump_file, " congruence class splitted:\n");
2074 cls->dump (dump_file, 4);
2076 fprintf (dump_file, " newly created groups:\n");
2077 for (unsigned int i = 0; i < 2; i++)
2078 newclasses[i]->dump (dump_file, 4);
2081 /* Release class if not presented in work list. */
2090 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2091 Bitmap stack BMSTACK is used for bitmap allocation. */
2094 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
2097 hash_map <congruence_class *, bitmap> split_map;
2099 for (unsigned int i = 0; i < cls->members.length (); i++)
2101 sem_item *item = cls->members[i];
2103 /* Iterate all usages that have INDEX as usage of the item. */
2104 for (unsigned int j = 0; j < item->usages.length (); j++)
2106 sem_usage_pair *usage = item->usages[j];
2108 if (usage->index != index)
2111 bitmap *slot = split_map.get (usage->item->cls);
2116 b = BITMAP_ALLOC (&m_bmstack);
2117 split_map.put (usage->item->cls, b);
2123 gcc_checking_assert (usage->item->cls);
2124 gcc_checking_assert (usage->item->index_in_class <
2125 usage->item->cls->members.length ());
2128 bitmap_set_bit (b, usage->item->index_in_class);
2132 traverse_split_pair pair;
2133 pair.optimizer = this;
2136 splitter_class_removed = false;
2138 <traverse_split_pair *, sem_item_optimizer::traverse_congruence_split> (&pair);
2140 /* Bitmap clean-up. */
2142 <traverse_split_pair *, sem_item_optimizer::release_split_map> (NULL);
2145 /* Every usage of a congruence class CLS is a candidate that can split the
2146 collection of classes. Bitmap stack BMSTACK is used for bitmap
2150 sem_item_optimizer::do_congruence_step (congruence_class *cls)
2155 bitmap usage = BITMAP_ALLOC (&m_bmstack);
2157 for (unsigned int i = 0; i < cls->members.length (); i++)
2158 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
2160 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
2162 if (dump_file && (dump_flags & TDF_DETAILS))
2163 fprintf (dump_file, " processing congruece step for class: %u, index: %u\n",
2166 do_congruence_step_for_index (cls, i);
2168 if (splitter_class_removed)
2172 BITMAP_FREE (usage);
2175 /* Adds a newly created congruence class CLS to worklist. */
2178 sem_item_optimizer::worklist_push (congruence_class *cls)
2180 /* Return if the class CLS is already presented in work list. */
2181 if (cls->in_worklist)
2184 cls->in_worklist = true;
2185 worklist.push_back (cls);
2188 /* Pops a class from worklist. */
2191 sem_item_optimizer::worklist_pop (void)
2193 congruence_class *cls;
2195 while (!worklist.empty ())
2197 cls = worklist.front ();
2198 worklist.pop_front ();
2199 if (cls->in_worklist)
2201 cls->in_worklist = false;
2207 /* Work list item was already intended to be removed.
2208 The only reason for doing it is to split a class.
2209 Thus, the class CLS is deleted. */
2217 /* Iterative congruence reduction function. */
2220 sem_item_optimizer::process_cong_reduction (void)
2222 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2223 it != m_classes.end (); ++it)
2224 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2225 if ((*it)->classes[i]->is_class_used ())
2226 worklist_push ((*it)->classes[i]);
2229 fprintf (dump_file, "Worklist has been filled with: %lu\n",
2230 (unsigned long) worklist.size ());
2232 if (dump_file && (dump_flags & TDF_DETAILS))
2233 fprintf (dump_file, "Congruence class reduction\n");
2235 congruence_class *cls;
2236 while ((cls = worklist_pop ()) != NULL)
2237 do_congruence_step (cls);
2240 /* Debug function prints all informations about congruence classes. */
2243 sem_item_optimizer::dump_cong_classes (void)
2249 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2250 m_classes_count, (unsigned long) m_classes.elements(), m_items.length ());
2252 /* Histogram calculation. */
2253 unsigned int max_index = 0;
2254 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
2256 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2257 it != m_classes.end (); ++it)
2259 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2261 unsigned int c = (*it)->classes[i]->members.length ();
2269 "Class size histogram [num of members]: number of classe number of classess\n");
2271 for (unsigned int i = 0; i <= max_index; i++)
2273 fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
2275 fprintf (dump_file, "\n\n");
2278 if (dump_flags & TDF_DETAILS)
2279 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2280 it != m_classes.end (); ++it)
2282 fprintf (dump_file, " group: with %u classes:\n", (*it)->classes.length ());
2284 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2286 (*it)->classes[i]->dump (dump_file, 4);
2288 if(i < (*it)->classes.length () - 1)
2289 fprintf (dump_file, " ");
2296 /* After reduction is done, we can declare all items in a group
2297 to be equal. PREV_CLASS_COUNT is start number of classes
2298 before reduction. */
2301 sem_item_optimizer::merge_classes (unsigned int prev_class_count)
2303 unsigned int item_count = m_items.length ();
2304 unsigned int class_count = m_classes_count;
2305 unsigned int equal_items = item_count - class_count;
2307 unsigned int non_singular_classes_count = 0;
2308 unsigned int non_singular_classes_sum = 0;
2310 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2311 it != m_classes.end (); ++it)
2312 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2314 congruence_class *c = (*it)->classes[i];
2315 if (c->members.length () > 1)
2317 non_singular_classes_count++;
2318 non_singular_classes_sum += c->members.length ();
2324 fprintf (dump_file, "\nItem count: %u\n", item_count);
2325 fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
2326 prev_class_count, class_count);
2327 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
2328 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
2329 class_count ? 1.0f * item_count / class_count : 0.0f);
2330 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
2331 non_singular_classes_count ? 1.0f * non_singular_classes_sum /
2332 non_singular_classes_count : 0.0f,
2333 non_singular_classes_count);
2334 fprintf (dump_file, "Equal symbols: %u\n", equal_items);
2335 fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
2336 item_count ? 100.0f * equal_items / item_count : 0.0f);
2339 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2340 it != m_classes.end (); ++it)
2341 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2343 congruence_class *c = (*it)->classes[i];
2345 if (c->members.length () == 1)
2348 gcc_assert (c->members.length ());
2350 sem_item *source = c->members[0];
2352 for (unsigned int j = 1; j < c->members.length (); j++)
2354 sem_item *alias = c->members[j];
2358 fprintf (dump_file, "Semantic equality hit:%s->%s\n",
2359 source->name (), alias->name ());
2360 fprintf (dump_file, "Assembler symbol names:%s->%s\n",
2361 source->asm_name (), alias->asm_name ());
2364 if (dump_file && (dump_flags & TDF_DETAILS))
2366 source->dump_to_file (dump_file);
2367 alias->dump_to_file (dump_file);
2370 source->merge (alias);
2375 /* Dump function prints all class members to a FILE with an INDENT. */
2378 congruence_class::dump (FILE *file, unsigned int indent) const
2380 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
2381 id, members[0]->get_hash (), members.length ());
2383 FPUTS_SPACES (file, indent + 2, "");
2384 for (unsigned i = 0; i < members.length (); i++)
2385 fprintf (file, "%s(%p/%u) ", members[i]->asm_name (), (void *) members[i]->decl,
2386 members[i]->node->order);
2388 fprintf (file, "\n");
2391 /* Returns true if there's a member that is used from another group. */
2394 congruence_class::is_class_used (void)
2396 for (unsigned int i = 0; i < members.length (); i++)
2397 if (members[i]->usages.length ())
2403 /* Initialization and computation of symtab node hash, there data
2404 are propagated later on. */
2406 static sem_item_optimizer *optimizer = NULL;
2408 /* Generate pass summary for IPA ICF pass. */
2411 ipa_icf_generate_summary (void)
2414 optimizer = new sem_item_optimizer ();
2416 optimizer->parse_funcs_and_vars ();
2419 /* Write pass summary for IPA ICF pass. */
2422 ipa_icf_write_summary (void)
2424 gcc_assert (optimizer);
2426 optimizer->write_summary ();
2429 /* Read pass summary for IPA ICF pass. */
2432 ipa_icf_read_summary (void)
2435 optimizer = new sem_item_optimizer ();
2437 optimizer->read_summary ();
2438 optimizer->register_hooks ();
2441 /* Semantic equality exection function. */
2444 ipa_icf_driver (void)
2446 gcc_assert (optimizer);
2448 optimizer->execute ();
2449 optimizer->unregister_hooks ();
2457 const pass_data pass_data_ipa_icf =
2459 IPA_PASS, /* type */
2461 OPTGROUP_IPA, /* optinfo_flags */
2462 TV_IPA_ICF, /* tv_id */
2463 0, /* properties_required */
2464 0, /* properties_provided */
2465 0, /* properties_destroyed */
2466 0, /* todo_flags_start */
2467 0, /* todo_flags_finish */
2470 class pass_ipa_icf : public ipa_opt_pass_d
2473 pass_ipa_icf (gcc::context *ctxt)
2474 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
2475 ipa_icf_generate_summary, /* generate_summary */
2476 ipa_icf_write_summary, /* write_summary */
2477 ipa_icf_read_summary, /* read_summary */
2479 write_optimization_summary */
2481 read_optimization_summary */
2482 NULL, /* stmt_fixup */
2483 0, /* function_transform_todo_flags_start */
2484 NULL, /* function_transform */
2485 NULL) /* variable_transform */
2488 /* opt_pass methods: */
2489 virtual bool gate (function *)
2491 return flag_ipa_icf_variables || flag_ipa_icf_functions;
2494 virtual unsigned int execute (function *)
2496 return ipa_icf_driver();
2498 }; // class pass_ipa_icf
2500 } // ipa_icf namespace
2503 make_pass_ipa_icf (gcc::context *ctxt)
2505 return new ipa_icf::pass_ipa_icf (ctxt);