Fix the build after the merge from trunk
[official-gcc.git] / gcc / ipa-icf.c
blob33c888946db379a07b492f41b78c7c40919afc2f
1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014 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
11 version.
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
16 for more details.
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
23 read-only variables.
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
28 In case of functions,
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
32 aliases if possible.
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
45 correspond.
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.
54 #include "config.h"
55 #include "system.h"
56 #include "coretypes.h"
57 #include "tree.h"
58 #include "predict.h"
59 #include "vec.h"
60 #include "hashtab.h"
61 #include "hash-set.h"
62 #include "machmode.h"
63 #include "tm.h"
64 #include "hard-reg-set.h"
65 #include "input.h"
66 #include "function.h"
67 #include "dominance.h"
68 #include "cfg.h"
69 #include "basic-block.h"
70 #include "tree-ssa-alias.h"
71 #include "internal-fn.h"
72 #include "gimple-expr.h"
73 #include "is-a.h"
74 #include "gimple.h"
75 #include "expr.h"
76 #include "gimple-iterator.h"
77 #include "gimple-ssa.h"
78 #include "tree-cfg.h"
79 #include "tree-phinodes.h"
80 #include "stringpool.h"
81 #include "tree-ssanames.h"
82 #include "tree-dfa.h"
83 #include "tree-pass.h"
84 #include "gimple-pretty-print.h"
85 #include "ipa-inline.h"
86 #include "cfgloop.h"
87 #include "except.h"
88 #include "hash-table.h"
89 #include "coverage.h"
90 #include "attribs.h"
91 #include "print-tree.h"
92 #include "lto-streamer.h"
93 #include "data-streamer.h"
94 #include "ipa-utils.h"
95 #include <list>
96 #include "ipa-icf-gimple.h"
97 #include "ipa-icf.h"
99 using namespace ipa_icf_gimple;
101 namespace ipa_icf {
102 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
104 sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index):
105 item (_item), index (_index)
109 /* Semantic item constructor for a node of _TYPE, where STACK is used
110 for bitmap memory allocation. */
112 sem_item::sem_item (sem_item_type _type,
113 bitmap_obstack *stack): type(_type), hash(0)
115 setup (stack);
118 /* Semantic item constructor for a node of _TYPE, where STACK is used
119 for bitmap memory allocation. The item is based on symtab node _NODE
120 with computed _HASH. */
122 sem_item::sem_item (sem_item_type _type, symtab_node *_node,
123 hashval_t _hash, bitmap_obstack *stack): type(_type),
124 node (_node), hash (_hash)
126 decl = node->decl;
127 setup (stack);
130 /* Add reference to a semantic TARGET. */
132 void
133 sem_item::add_reference (sem_item *target)
135 refs.safe_push (target);
136 unsigned index = refs.length ();
137 target->usages.safe_push (new sem_usage_pair(this, index));
138 bitmap_set_bit (target->usage_index_bitmap, index);
139 refs_set.add (target->node);
142 /* Initialize internal data structures. Bitmap STACK is used for
143 bitmap memory allocation process. */
145 void
146 sem_item::setup (bitmap_obstack *stack)
148 gcc_checking_assert (node);
150 refs.create (0);
151 tree_refs.create (0);
152 usages.create (0);
153 usage_index_bitmap = BITMAP_ALLOC (stack);
156 sem_item::~sem_item ()
158 for (unsigned i = 0; i < usages.length (); i++)
159 delete usages[i];
161 refs.release ();
162 tree_refs.release ();
163 usages.release ();
165 BITMAP_FREE (usage_index_bitmap);
168 /* Dump function for debugging purpose. */
170 DEBUG_FUNCTION void
171 sem_item::dump (void)
173 if (dump_file)
175 fprintf (dump_file, "[%s] %s (%u) (tree:%p)\n", type == FUNC ? "func" : "var",
176 name(), node->order, (void *) node->decl);
177 fprintf (dump_file, " hash: %u\n", get_hash ());
178 fprintf (dump_file, " references: ");
180 for (unsigned i = 0; i < refs.length (); i++)
181 fprintf (dump_file, "%s%s ", refs[i]->name (),
182 i < refs.length() - 1 ? "," : "");
184 fprintf (dump_file, "\n");
188 /* Semantic function constructor that uses STACK as bitmap memory stack. */
190 sem_function::sem_function (bitmap_obstack *stack): sem_item (FUNC, stack),
191 m_checker (NULL), m_compared_func (NULL)
193 arg_types.create (0);
194 bb_sizes.create (0);
195 bb_sorted.create (0);
198 /* Constructor based on callgraph node _NODE with computed hash _HASH.
199 Bitmap STACK is used for memory allocation. */
200 sem_function::sem_function (cgraph_node *node, hashval_t hash,
201 bitmap_obstack *stack):
202 sem_item (FUNC, node, hash, stack),
203 m_checker (NULL), m_compared_func (NULL)
205 arg_types.create (0);
206 bb_sizes.create (0);
207 bb_sorted.create (0);
210 sem_function::~sem_function ()
212 for (unsigned i = 0; i < bb_sorted.length (); i++)
213 free (bb_sorted[i]);
215 arg_types.release ();
216 bb_sizes.release ();
217 bb_sorted.release ();
220 /* Calculates hash value based on a BASIC_BLOCK. */
222 hashval_t
223 sem_function::get_bb_hash (const sem_bb *basic_block)
225 inchash::hash hstate;
227 hstate.add_int (basic_block->nondbg_stmt_count);
228 hstate.add_int (basic_block->edge_count);
230 return hstate.end ();
233 /* References independent hash function. */
235 hashval_t
236 sem_function::get_hash (void)
238 if(!hash)
240 inchash::hash hstate;
241 hstate.add_int (177454); /* Random number for function type. */
243 hstate.add_int (arg_count);
244 hstate.add_int (cfg_checksum);
245 hstate.add_int (gcode_hash);
247 for (unsigned i = 0; i < bb_sorted.length (); i++)
248 hstate.merge_hash (get_bb_hash (bb_sorted[i]));
250 for (unsigned i = 0; i < bb_sizes.length (); i++)
251 hstate.add_int (bb_sizes[i]);
253 hash = hstate.end ();
256 return hash;
259 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
260 point to a same function. Comparison can be skipped if IGNORED_NODES
261 contains these nodes. */
263 bool
264 sem_function::compare_cgraph_references (hash_map <symtab_node *, sem_item *>
265 &ignored_nodes,
266 symtab_node *n1, symtab_node *n2)
268 if (n1 == n2 || (ignored_nodes.get (n1) && ignored_nodes.get (n2)))
269 return true;
271 /* TODO: add more precise comparison for weakrefs, etc. */
273 return return_false_with_msg ("different references");
276 /* If cgraph edges E1 and E2 are indirect calls, verify that
277 ECF flags are the same. */
279 bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
281 if (e1->indirect_info && e2->indirect_info)
283 int e1_flags = e1->indirect_info->ecf_flags;
284 int e2_flags = e2->indirect_info->ecf_flags;
286 if (e1_flags != e2_flags)
287 return return_false_with_msg ("ICF flags are different");
289 else if (e1->indirect_info || e2->indirect_info)
290 return false;
292 return true;
295 /* Fast equality function based on knowledge known in WPA. */
297 bool
298 sem_function::equals_wpa (sem_item *item,
299 hash_map <symtab_node *, sem_item *> &ignored_nodes)
301 gcc_assert (item->type == FUNC);
303 m_compared_func = static_cast<sem_function *> (item);
305 if (arg_types.length () != m_compared_func->arg_types.length ())
306 return return_false_with_msg ("different number of arguments");
308 /* Checking types of arguments. */
309 for (unsigned i = 0; i < arg_types.length (); i++)
311 /* This guard is here for function pointer with attributes (pr59927.c). */
312 if (!arg_types[i] || !m_compared_func->arg_types[i])
313 return return_false_with_msg ("NULL argument type");
315 /* Polymorphic comparison is executed just for non-leaf functions. */
316 bool is_not_leaf = get_node ()->callees != NULL;
318 if (!func_checker::compatible_types_p (arg_types[i],
319 m_compared_func->arg_types[i],
320 is_not_leaf, i == 0))
321 return return_false_with_msg ("argument type is different");
324 /* Result type checking. */
325 if (!func_checker::compatible_types_p (result_type,
326 m_compared_func->result_type))
327 return return_false_with_msg ("result types are different");
329 if (node->num_references () != item->node->num_references ())
330 return return_false_with_msg ("different number of references");
332 ipa_ref *ref = NULL, *ref2 = NULL;
333 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
335 item->node->iterate_reference (i, ref2);
337 if (!compare_cgraph_references (ignored_nodes, ref->referred, ref2->referred))
338 return false;
341 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
342 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
344 while (e1 && e2)
346 if (!compare_cgraph_references (ignored_nodes, e1->callee, e2->callee))
347 return false;
349 e1 = e1->next_callee;
350 e2 = e2->next_callee;
353 if (e1 || e2)
354 return return_false_with_msg ("different number of edges");
356 return true;
359 /* Returns true if the item equals to ITEM given as argument. */
361 bool
362 sem_function::equals (sem_item *item,
363 hash_map <symtab_node *, sem_item *> &ignored_nodes)
365 gcc_assert (item->type == FUNC);
366 bool eq = equals_private (item, ignored_nodes);
368 if (m_checker != NULL)
370 delete m_checker;
371 m_checker = NULL;
374 if (dump_file && (dump_flags & TDF_DETAILS))
375 fprintf (dump_file,
376 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
377 name(), item->name (), node->order, item->node->order, asm_name (),
378 item->asm_name (), eq ? "true" : "false");
380 return eq;
383 /* Processes function equality comparison. */
385 bool
386 sem_function::equals_private (sem_item *item,
387 hash_map <symtab_node *, sem_item *> &ignored_nodes)
389 if (item->type != FUNC)
390 return false;
392 basic_block bb1, bb2;
393 edge e1, e2;
394 edge_iterator ei1, ei2;
395 int *bb_dict = NULL;
396 bool result = true;
397 tree arg1, arg2;
399 m_compared_func = static_cast<sem_function *> (item);
401 gcc_assert (decl != item->decl);
403 if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
404 || edge_count != m_compared_func->edge_count
405 || cfg_checksum != m_compared_func->cfg_checksum)
406 return return_false ();
408 if (!equals_wpa (item, ignored_nodes))
409 return false;
411 /* Checking function arguments. */
412 tree decl1 = DECL_ATTRIBUTES (decl);
413 tree decl2 = DECL_ATTRIBUTES (m_compared_func->decl);
415 m_checker = new func_checker (decl, m_compared_func->decl,
416 compare_polymorphic_p (),
417 false,
418 &refs_set,
419 &m_compared_func->refs_set);
420 while (decl1)
422 if (decl2 == NULL)
423 return return_false ();
425 if (get_attribute_name (decl1) != get_attribute_name (decl2))
426 return return_false ();
428 tree attr_value1 = TREE_VALUE (decl1);
429 tree attr_value2 = TREE_VALUE (decl2);
431 if (attr_value1 && attr_value2)
433 bool ret = m_checker->compare_operand (TREE_VALUE (attr_value1),
434 TREE_VALUE (attr_value2));
435 if (!ret)
436 return return_false_with_msg ("attribute values are different");
438 else if (!attr_value1 && !attr_value2)
440 else
441 return return_false ();
443 decl1 = TREE_CHAIN (decl1);
444 decl2 = TREE_CHAIN (decl2);
447 if (decl1 != decl2)
448 return return_false();
451 for (arg1 = DECL_ARGUMENTS (decl),
452 arg2 = DECL_ARGUMENTS (m_compared_func->decl);
453 arg1; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2))
454 if (!m_checker->compare_decl (arg1, arg2))
455 return return_false ();
457 /* Fill-up label dictionary. */
458 for (unsigned i = 0; i < bb_sorted.length (); ++i)
460 m_checker->parse_labels (bb_sorted[i]);
461 m_checker->parse_labels (m_compared_func->bb_sorted[i]);
464 /* Checking all basic blocks. */
465 for (unsigned i = 0; i < bb_sorted.length (); ++i)
466 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
467 return return_false();
469 dump_message ("All BBs are equal\n");
471 /* Basic block edges check. */
472 for (unsigned i = 0; i < bb_sorted.length (); ++i)
474 bb_dict = XNEWVEC (int, bb_sorted.length () + 2);
475 memset (bb_dict, -1, (bb_sorted.length () + 2) * sizeof (int));
477 bb1 = bb_sorted[i]->bb;
478 bb2 = m_compared_func->bb_sorted[i]->bb;
480 ei2 = ei_start (bb2->preds);
482 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
484 ei_cond (ei2, &e2);
486 if (e1->flags != e2->flags)
487 return return_false_with_msg ("flags comparison returns false");
489 if (!bb_dict_test (bb_dict, e1->src->index, e2->src->index))
490 return return_false_with_msg ("edge comparison returns false");
492 if (!bb_dict_test (bb_dict, e1->dest->index, e2->dest->index))
493 return return_false_with_msg ("BB comparison returns false");
495 if (!m_checker->compare_edge (e1, e2))
496 return return_false_with_msg ("edge comparison returns false");
498 ei_next (&ei2);
502 /* Basic block PHI nodes comparison. */
503 for (unsigned i = 0; i < bb_sorted.length (); i++)
504 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
505 return return_false_with_msg ("PHI node comparison returns false");
507 return result;
510 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
511 be applied. */
512 bool
513 sem_function::merge (sem_item *alias_item)
515 gcc_assert (alias_item->type == FUNC);
517 sem_function *alias_func = static_cast<sem_function *> (alias_item);
519 cgraph_node *original = get_node ();
520 cgraph_node *local_original = original;
521 cgraph_node *alias = alias_func->get_node ();
522 bool original_address_matters;
523 bool alias_address_matters;
525 bool create_thunk = false;
526 bool create_alias = false;
527 bool redirect_callers = false;
528 bool original_discardable = false;
530 /* Do not attempt to mix functions from different user sections;
531 we do not know what user intends with those. */
532 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
533 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
534 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
536 if (dump_file)
537 fprintf (dump_file,
538 "Not unifying; original and alias are in different sections.\n\n");
539 return false;
542 /* See if original is in a section that can be discarded if the main
543 symbol is not used. */
544 if (DECL_EXTERNAL (original->decl))
545 original_discardable = true;
546 if (original->resolution == LDPR_PREEMPTED_REG
547 || original->resolution == LDPR_PREEMPTED_IR)
548 original_discardable = true;
549 if (original->can_be_discarded_p ())
550 original_discardable = true;
552 /* See if original and/or alias address can be compared for equality. */
553 original_address_matters
554 = (!DECL_VIRTUAL_P (original->decl)
555 && (original->externally_visible
556 || original->address_taken_from_non_vtable_p ()));
557 alias_address_matters
558 = (!DECL_VIRTUAL_P (alias->decl)
559 && (alias->externally_visible
560 || alias->address_taken_from_non_vtable_p ()));
562 /* If alias and original can be compared for address equality, we need
563 to create a thunk. Also we can not create extra aliases into discardable
564 section (or we risk link failures when section is discarded). */
565 if ((original_address_matters
566 && alias_address_matters)
567 || original_discardable)
569 create_thunk = !stdarg_p (TREE_TYPE (alias->decl));
570 create_alias = false;
571 /* When both alias and original are not overwritable, we can save
572 the extra thunk wrapper for direct calls. */
573 redirect_callers
574 = (!original_discardable
575 && alias->get_availability () > AVAIL_INTERPOSABLE
576 && original->get_availability () > AVAIL_INTERPOSABLE);
578 else
580 create_alias = true;
581 create_thunk = false;
582 redirect_callers = false;
585 if (create_alias && DECL_COMDAT_GROUP (alias->decl))
587 create_alias = false;
588 create_thunk = true;
591 /* We want thunk to always jump to the local function body
592 unless the body is comdat and may be optimized out. */
593 if ((create_thunk || redirect_callers)
594 && (!original_discardable
595 || (DECL_COMDAT_GROUP (original->decl)
596 && (DECL_COMDAT_GROUP (original->decl)
597 == DECL_COMDAT_GROUP (alias->decl)))))
598 local_original
599 = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
601 if (redirect_callers)
603 /* If alias is non-overwritable then
604 all direct calls are safe to be redirected to the original. */
605 bool redirected = false;
606 while (alias->callers)
608 cgraph_edge *e = alias->callers;
609 e->redirect_callee (local_original);
610 push_cfun (DECL_STRUCT_FUNCTION (e->caller->decl));
612 if (e->call_stmt)
613 e->redirect_call_stmt_to_callee ();
615 pop_cfun ();
616 redirected = true;
619 alias->icf_merged = true;
621 /* The alias function is removed if symbol address
622 does not matter. */
623 if (!alias_address_matters)
624 alias->remove ();
626 if (dump_file && redirected)
627 fprintf (dump_file, "Callgraph local calls have been redirected.\n\n");
629 /* If the condtion above is not met, we are lucky and can turn the
630 function into real alias. */
631 else if (create_alias)
633 alias->icf_merged = true;
635 /* Remove the function's body. */
636 ipa_merge_profiles (original, alias);
637 alias->release_body (true);
638 alias->reset ();
640 /* Create the alias. */
641 cgraph_node::create_alias (alias_func->decl, decl);
642 alias->resolve_alias (original);
644 /* Workaround for PR63566 that forces equal calling convention
645 to be used. */
646 alias->local.local = false;
647 original->local.local = false;
649 if (dump_file)
650 fprintf (dump_file, "Callgraph alias has been created.\n\n");
652 else if (create_thunk)
654 if (DECL_COMDAT_GROUP (alias->decl))
656 if (dump_file)
657 fprintf (dump_file, "Callgraph thunk cannot be created because of COMDAT\n");
659 return 0;
662 alias->icf_merged = true;
663 ipa_merge_profiles (local_original, alias);
664 alias->create_wrapper (local_original);
666 if (dump_file)
667 fprintf (dump_file, "Callgraph thunk has been created.\n\n");
669 else if (dump_file)
670 fprintf (dump_file, "Callgraph merge operation cannot be performed.\n\n");
672 return true;
675 /* Semantic item initialization function. */
677 void
678 sem_function::init (void)
680 if (in_lto_p)
681 get_node ()->get_body ();
683 tree fndecl = node->decl;
684 function *func = DECL_STRUCT_FUNCTION (fndecl);
686 gcc_assert (func);
687 gcc_assert (SSANAMES (func));
689 ssa_names_size = SSANAMES (func)->length ();
690 node = node;
692 decl = fndecl;
693 region_tree = func->eh->region_tree;
695 /* iterating all function arguments. */
696 arg_count = count_formal_params (fndecl);
698 edge_count = n_edges_for_fn (func);
699 cfg_checksum = coverage_compute_cfg_checksum (func);
701 inchash::hash hstate;
703 basic_block bb;
704 FOR_EACH_BB_FN (bb, func)
706 unsigned nondbg_stmt_count = 0;
708 edge e;
709 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e); ei_next (&ei))
710 cfg_checksum = iterative_hash_host_wide_int (e->flags,
711 cfg_checksum);
713 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
714 gsi_next (&gsi))
716 gimple stmt = gsi_stmt (gsi);
718 if (gimple_code (stmt) != GIMPLE_DEBUG)
720 hash_stmt (&hstate, stmt);
721 nondbg_stmt_count++;
725 gcode_hash = hstate.end ();
726 bb_sizes.safe_push (nondbg_stmt_count);
728 /* Inserting basic block to hash table. */
729 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
730 EDGE_COUNT (bb->preds) + EDGE_COUNT (bb->succs));
732 bb_sorted.safe_push (semantic_bb);
735 parse_tree_args ();
738 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
740 void
741 sem_function::hash_stmt (inchash::hash *hstate, gimple stmt)
743 enum gimple_code code = gimple_code (stmt);
745 hstate->add_int (code);
747 if (code == GIMPLE_CALL)
749 /* Checking of argument. */
750 for (unsigned i = 0; i < gimple_call_num_args (stmt); ++i)
752 tree argument = gimple_call_arg (stmt, i);
754 switch (TREE_CODE (argument))
756 case INTEGER_CST:
757 if (tree_fits_shwi_p (argument))
758 hstate->add_wide_int (tree_to_shwi (argument));
759 else if (tree_fits_uhwi_p (argument))
760 hstate->add_wide_int (tree_to_uhwi (argument));
761 break;
762 case REAL_CST:
763 REAL_VALUE_TYPE c;
764 HOST_WIDE_INT n;
766 c = TREE_REAL_CST (argument);
767 n = real_to_integer (&c);
769 hstate->add_wide_int (n);
770 break;
771 case ADDR_EXPR:
773 tree addr_operand = TREE_OPERAND (argument, 0);
775 if (TREE_CODE (addr_operand) == STRING_CST)
776 hstate->add (TREE_STRING_POINTER (addr_operand),
777 TREE_STRING_LENGTH (addr_operand));
778 break;
780 default:
781 break;
788 /* Return true if polymorphic comparison must be processed. */
790 bool
791 sem_function::compare_polymorphic_p (void)
793 return get_node ()->callees != NULL
794 || m_compared_func->get_node ()->callees != NULL;
797 /* For a given call graph NODE, the function constructs new
798 semantic function item. */
800 sem_function *
801 sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
803 tree fndecl = node->decl;
804 function *func = DECL_STRUCT_FUNCTION (fndecl);
806 /* TODO: add support for thunks and aliases. */
808 if (!func || !node->has_gimple_body_p ())
809 return NULL;
811 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
812 return NULL;
814 sem_function *f = new sem_function (node, 0, stack);
816 f->init ();
818 return f;
821 /* Parses function arguments and result type. */
823 void
824 sem_function::parse_tree_args (void)
826 tree result;
828 if (arg_types.exists ())
829 arg_types.release ();
831 arg_types.create (4);
832 tree fnargs = DECL_ARGUMENTS (decl);
834 for (tree parm = fnargs; parm; parm = DECL_CHAIN (parm))
835 arg_types.safe_push (DECL_ARG_TYPE (parm));
837 /* Function result type. */
838 result = DECL_RESULT (decl);
839 result_type = result ? TREE_TYPE (result) : NULL;
841 /* During WPA, we can get arguments by following method. */
842 if (!fnargs)
844 tree type = TYPE_ARG_TYPES (TREE_TYPE (decl));
845 for (tree parm = type; parm; parm = TREE_CHAIN (parm))
846 arg_types.safe_push (TYPE_CANONICAL (TREE_VALUE (parm)));
848 result_type = TREE_TYPE (TREE_TYPE (decl));
852 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
853 return true if phi nodes are semantically equivalent in these blocks . */
855 bool
856 sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
858 gphi_iterator si1, si2;
859 gphi *phi1, *phi2;
860 unsigned size1, size2, i;
861 tree t1, t2;
862 edge e1, e2;
864 gcc_assert (bb1 != NULL);
865 gcc_assert (bb2 != NULL);
867 si2 = gsi_start_phis (bb2);
868 for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
869 gsi_next (&si1))
871 gsi_next_nonvirtual_phi (&si1);
872 gsi_next_nonvirtual_phi (&si2);
874 if (gsi_end_p (si1) && gsi_end_p (si2))
875 break;
877 if (gsi_end_p (si1) || gsi_end_p (si2))
878 return return_false();
880 phi1 = si1.phi ();
881 phi2 = si2.phi ();
883 tree phi_result1 = gimple_phi_result (phi1);
884 tree phi_result2 = gimple_phi_result (phi2);
886 if (!m_checker->compare_operand (phi_result1, phi_result2))
887 return return_false_with_msg ("PHI results are different");
889 size1 = gimple_phi_num_args (phi1);
890 size2 = gimple_phi_num_args (phi2);
892 if (size1 != size2)
893 return return_false ();
895 for (i = 0; i < size1; ++i)
897 t1 = gimple_phi_arg (phi1, i)->def;
898 t2 = gimple_phi_arg (phi2, i)->def;
900 if (!m_checker->compare_operand (t1, t2))
901 return return_false ();
903 e1 = gimple_phi_arg_edge (phi1, i);
904 e2 = gimple_phi_arg_edge (phi2, i);
906 if (!m_checker->compare_edge (e1, e2))
907 return return_false ();
910 gsi_next (&si2);
913 return true;
916 /* Returns true if tree T can be compared as a handled component. */
918 bool
919 sem_function::icf_handled_component_p (tree t)
921 tree_code tc = TREE_CODE (t);
923 return ((handled_component_p (t))
924 || tc == ADDR_EXPR || tc == MEM_REF || tc == REALPART_EXPR
925 || tc == IMAGPART_EXPR || tc == OBJ_TYPE_REF);
928 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
929 corresponds to TARGET. */
931 bool
932 sem_function::bb_dict_test (int* bb_dict, int source, int target)
934 if (bb_dict[source] == -1)
936 bb_dict[source] = target;
937 return true;
939 else
940 return bb_dict[source] == target;
943 /* Iterates all tree types in T1 and T2 and returns true if all types
944 are compatible. If COMPARE_POLYMORPHIC is set to true,
945 more strict comparison is executed. */
947 bool
948 sem_function::compare_type_list (tree t1, tree t2, bool compare_polymorphic)
950 tree tv1, tv2;
951 tree_code tc1, tc2;
953 if (!t1 && !t2)
954 return true;
956 while (t1 != NULL && t2 != NULL)
958 tv1 = TREE_VALUE (t1);
959 tv2 = TREE_VALUE (t2);
961 tc1 = TREE_CODE (tv1);
962 tc2 = TREE_CODE (tv2);
964 if (tc1 == NOP_EXPR && tc2 == NOP_EXPR)
966 else if (tc1 == NOP_EXPR || tc2 == NOP_EXPR)
967 return false;
968 else if (!func_checker::compatible_types_p (tv1, tv2, compare_polymorphic))
969 return false;
971 t1 = TREE_CHAIN (t1);
972 t2 = TREE_CHAIN (t2);
975 return !(t1 || t2);
979 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
981 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
985 /* Constructor based on varpool node _NODE with computed hash _HASH.
986 Bitmap STACK is used for memory allocation. */
988 sem_variable::sem_variable (varpool_node *node, hashval_t _hash,
989 bitmap_obstack *stack): sem_item(VAR,
990 node, _hash, stack)
992 gcc_checking_assert (node);
993 gcc_checking_assert (get_node ());
996 /* Returns true if the item equals to ITEM given as argument. */
998 bool
999 sem_variable::equals (sem_item *item,
1000 hash_map <symtab_node *, sem_item *> & ARG_UNUSED (ignored_nodes))
1002 gcc_assert (item->type == VAR);
1004 sem_variable *v = static_cast<sem_variable *>(item);
1006 if (!ctor || !v->ctor)
1007 return return_false_with_msg ("ctor is missing for semantic variable");
1009 return sem_variable::equals (ctor, v->ctor);
1012 /* Compares trees T1 and T2 for semantic equality. */
1014 bool
1015 sem_variable::equals (tree t1, tree t2)
1017 tree_code tc1 = TREE_CODE (t1);
1018 tree_code tc2 = TREE_CODE (t2);
1020 if (tc1 != tc2)
1021 return false;
1023 switch (tc1)
1025 case CONSTRUCTOR:
1027 unsigned len1 = vec_safe_length (CONSTRUCTOR_ELTS (t1));
1028 unsigned len2 = vec_safe_length (CONSTRUCTOR_ELTS (t2));
1030 if (len1 != len2)
1031 return false;
1033 for (unsigned i = 0; i < len1; i++)
1034 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1, i)->value,
1035 CONSTRUCTOR_ELT (t2, i)->value)
1036 || CONSTRUCTOR_ELT (t1, i)->index != CONSTRUCTOR_ELT (t2, i)->index)
1037 return false;
1039 return true;
1041 case MEM_REF:
1043 tree x1 = TREE_OPERAND (t1, 0);
1044 tree x2 = TREE_OPERAND (t2, 0);
1045 tree y1 = TREE_OPERAND (t1, 1);
1046 tree y2 = TREE_OPERAND (t2, 1);
1048 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2),
1049 true))
1050 return return_false ();
1052 /* Type of the offset on MEM_REF does not matter. */
1053 return sem_variable::equals (x1, x2)
1054 && wi::to_offset (y1) == wi::to_offset (y2);
1056 case NOP_EXPR:
1057 case ADDR_EXPR:
1059 tree op1 = TREE_OPERAND (t1, 0);
1060 tree op2 = TREE_OPERAND (t2, 0);
1061 return sem_variable::equals (op1, op2);
1063 case FUNCTION_DECL:
1064 case VAR_DECL:
1065 case FIELD_DECL:
1066 case LABEL_DECL:
1067 return t1 == t2;
1068 case INTEGER_CST:
1069 return func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
1070 true)
1071 && wi::to_offset (t1) == wi::to_offset (t2);
1072 case STRING_CST:
1073 case REAL_CST:
1074 case COMPLEX_CST:
1075 return operand_equal_p (t1, t2, OEP_ONLY_CONST);
1076 case COMPONENT_REF:
1077 case ARRAY_REF:
1078 case POINTER_PLUS_EXPR:
1080 tree x1 = TREE_OPERAND (t1, 0);
1081 tree x2 = TREE_OPERAND (t2, 0);
1082 tree y1 = TREE_OPERAND (t1, 1);
1083 tree y2 = TREE_OPERAND (t2, 1);
1085 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
1087 case ERROR_MARK:
1088 return return_false_with_msg ("ERROR_MARK");
1089 default:
1090 return return_false_with_msg ("Unknown TREE code reached");
1094 /* Parser function that visits a varpool NODE. */
1096 sem_variable *
1097 sem_variable::parse (varpool_node *node, bitmap_obstack *stack)
1099 tree decl = node->decl;
1101 bool readonly = TYPE_P (decl) ? TYPE_READONLY (decl) : TREE_READONLY (decl);
1102 bool can_handle = readonly && (DECL_VIRTUAL_P (decl)
1103 || !TREE_ADDRESSABLE (decl));
1105 if (!can_handle)
1106 return NULL;
1108 tree ctor = ctor_for_folding (decl);
1109 if (!ctor)
1110 return NULL;
1112 sem_variable *v = new sem_variable (node, 0, stack);
1114 v->init ();
1116 return v;
1119 /* References independent hash function. */
1121 hashval_t
1122 sem_variable::get_hash (void)
1124 if (hash)
1125 return hash;
1127 inchash::hash hstate;
1129 hstate.add_int (456346417);
1130 hstate.add_int (TREE_CODE (ctor));
1132 if (TREE_CODE (ctor) == CONSTRUCTOR)
1134 unsigned length = vec_safe_length (CONSTRUCTOR_ELTS (ctor));
1135 hstate.add_int (length);
1138 hash = hstate.end ();
1140 return hash;
1143 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1144 be applied. */
1146 bool
1147 sem_variable::merge (sem_item *alias_item)
1149 gcc_assert (alias_item->type == VAR);
1151 sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
1153 varpool_node *original = get_node ();
1154 varpool_node *alias = alias_var->get_node ();
1155 bool original_discardable = false;
1157 /* See if original is in a section that can be discarded if the main
1158 symbol is not used. */
1159 if (DECL_EXTERNAL (original->decl))
1160 original_discardable = true;
1161 if (original->resolution == LDPR_PREEMPTED_REG
1162 || original->resolution == LDPR_PREEMPTED_IR)
1163 original_discardable = true;
1164 if (original->can_be_discarded_p ())
1165 original_discardable = true;
1167 gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
1169 if (original_discardable || DECL_EXTERNAL (alias_var->decl) ||
1170 !compare_sections (alias_var))
1172 if (dump_file)
1173 fprintf (dump_file, "Varpool alias cannot be created\n\n");
1175 return false;
1177 else
1179 // alias cycle creation check
1180 varpool_node *n = original;
1182 while (n->alias)
1184 n = n->get_alias_target ();
1185 if (n == alias)
1187 if (dump_file)
1188 fprintf (dump_file, "Varpool alias cannot be created (alias cycle).\n\n");
1190 return false;
1194 alias->analyzed = false;
1196 DECL_INITIAL (alias->decl) = NULL;
1197 alias->remove_all_references ();
1199 varpool_node::create_alias (alias_var->decl, decl);
1200 alias->resolve_alias (original);
1202 if (dump_file)
1203 fprintf (dump_file, "Varpool alias has been created.\n\n");
1205 return true;
1209 bool
1210 sem_variable::compare_sections (sem_variable *alias)
1212 const char *source = node->get_section ();
1213 const char *target = alias->node->get_section();
1215 if (source == NULL && target == NULL)
1216 return true;
1217 else if(!source || !target)
1218 return false;
1219 else
1220 return strcmp (source, target) == 0;
1223 /* Dump symbol to FILE. */
1225 void
1226 sem_variable::dump_to_file (FILE *file)
1228 gcc_assert (file);
1230 print_node (file, "", decl, 0);
1231 fprintf (file, "\n\n");
1234 /* Iterates though a constructor and identifies tree references
1235 we are interested in semantic function equality. */
1237 void
1238 sem_variable::parse_tree_refs (tree t)
1240 switch (TREE_CODE (t))
1242 case CONSTRUCTOR:
1244 unsigned length = vec_safe_length (CONSTRUCTOR_ELTS (t));
1246 for (unsigned i = 0; i < length; i++)
1247 parse_tree_refs(CONSTRUCTOR_ELT (t, i)->value);
1249 break;
1251 case NOP_EXPR:
1252 case ADDR_EXPR:
1254 tree op = TREE_OPERAND (t, 0);
1255 parse_tree_refs (op);
1256 break;
1258 case FUNCTION_DECL:
1260 tree_refs.safe_push (t);
1261 break;
1263 default:
1264 break;
1268 unsigned int sem_item_optimizer::class_id = 0;
1270 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1271 m_classes_count (0), m_cgraph_node_hooks (NULL), m_varpool_node_hooks (NULL)
1273 m_items.create (0);
1274 bitmap_obstack_initialize (&m_bmstack);
1277 sem_item_optimizer::~sem_item_optimizer ()
1279 for (unsigned int i = 0; i < m_items.length (); i++)
1280 delete m_items[i];
1282 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
1283 it != m_classes.end (); ++it)
1285 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
1286 delete (*it)->classes[i];
1288 (*it)->classes.release ();
1291 m_items.release ();
1293 bitmap_obstack_release (&m_bmstack);
1296 /* Write IPA ICF summary for symbols. */
1298 void
1299 sem_item_optimizer::write_summary (void)
1301 unsigned int count = 0;
1303 output_block *ob = create_output_block (LTO_section_ipa_icf);
1304 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
1305 ob->symbol = NULL;
1307 /* Calculate number of symbols to be serialized. */
1308 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
1309 !lsei_end_p (lsei);
1310 lsei_next_in_partition (&lsei))
1312 symtab_node *node = lsei_node (lsei);
1314 if (m_symtab_node_map.get (node))
1315 count++;
1318 streamer_write_uhwi (ob, count);
1320 /* Process all of the symbols. */
1321 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
1322 !lsei_end_p (lsei);
1323 lsei_next_in_partition (&lsei))
1325 symtab_node *node = lsei_node (lsei);
1327 sem_item **item = m_symtab_node_map.get (node);
1329 if (item && *item)
1331 int node_ref = lto_symtab_encoder_encode (encoder, node);
1332 streamer_write_uhwi_stream (ob->main_stream, node_ref);
1334 streamer_write_uhwi (ob, (*item)->get_hash ());
1338 streamer_write_char_stream (ob->main_stream, 0);
1339 produce_asm (ob, NULL);
1340 destroy_output_block (ob);
1343 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1344 contains LEN bytes. */
1346 void
1347 sem_item_optimizer::read_section (lto_file_decl_data *file_data,
1348 const char *data, size_t len)
1350 const lto_function_header *header =
1351 (const lto_function_header *) data;
1352 const int cfg_offset = sizeof (lto_function_header);
1353 const int main_offset = cfg_offset + header->cfg_size;
1354 const int string_offset = main_offset + header->main_size;
1355 data_in *data_in;
1356 unsigned int i;
1357 unsigned int count;
1359 lto_input_block ib_main ((const char *) data + main_offset, 0,
1360 header->main_size);
1362 data_in =
1363 lto_data_in_create (file_data, (const char *) data + string_offset,
1364 header->string_size, vNULL);
1366 count = streamer_read_uhwi (&ib_main);
1368 for (i = 0; i < count; i++)
1370 unsigned int index;
1371 symtab_node *node;
1372 lto_symtab_encoder_t encoder;
1374 index = streamer_read_uhwi (&ib_main);
1375 encoder = file_data->symtab_node_encoder;
1376 node = lto_symtab_encoder_deref (encoder, index);
1378 hashval_t hash = streamer_read_uhwi (&ib_main);
1380 gcc_assert (node->definition);
1382 if (dump_file)
1383 fprintf (dump_file, "Symbol added:%s (tree: %p, uid:%u)\n", node->asm_name (),
1384 (void *) node->decl, node->order);
1386 if (is_a<cgraph_node *> (node))
1388 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1390 m_items.safe_push (new sem_function (cnode, hash, &m_bmstack));
1392 else
1394 varpool_node *vnode = dyn_cast <varpool_node *> (node);
1396 m_items.safe_push (new sem_variable (vnode, hash, &m_bmstack));
1400 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
1401 len);
1402 lto_data_in_delete (data_in);
1405 /* Read IPA IPA ICF summary for symbols. */
1407 void
1408 sem_item_optimizer::read_summary (void)
1410 lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
1411 lto_file_decl_data *file_data;
1412 unsigned int j = 0;
1414 while ((file_data = file_data_vec[j++]))
1416 size_t len;
1417 const char *data = lto_get_section_data (file_data,
1418 LTO_section_ipa_icf, NULL, &len);
1420 if (data)
1421 read_section (file_data, data, len);
1425 /* Register callgraph and varpool hooks. */
1427 void
1428 sem_item_optimizer::register_hooks (void)
1430 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
1431 (&sem_item_optimizer::cgraph_removal_hook, this);
1433 m_varpool_node_hooks = symtab->add_varpool_removal_hook
1434 (&sem_item_optimizer::varpool_removal_hook, this);
1437 /* Unregister callgraph and varpool hooks. */
1439 void
1440 sem_item_optimizer::unregister_hooks (void)
1442 if (m_cgraph_node_hooks)
1443 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
1445 if (m_varpool_node_hooks)
1446 symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
1449 /* Adds a CLS to hashtable associated by hash value. */
1451 void
1452 sem_item_optimizer::add_class (congruence_class *cls)
1454 gcc_assert (cls->members.length ());
1456 congruence_class_group *group = get_group_by_hash (
1457 cls->members[0]->get_hash (),
1458 cls->members[0]->type);
1459 group->classes.safe_push (cls);
1462 /* Gets a congruence class group based on given HASH value and TYPE. */
1464 congruence_class_group *
1465 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
1467 congruence_class_group *item = XNEW (congruence_class_group);
1468 item->hash = hash;
1469 item->type = type;
1471 congruence_class_group **slot = m_classes.find_slot (item, INSERT);
1473 if (*slot)
1474 free (item);
1475 else
1477 item->classes.create (1);
1478 *slot = item;
1481 return *slot;
1484 /* Callgraph removal hook called for a NODE with a custom DATA. */
1486 void
1487 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
1489 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
1490 optimizer->remove_symtab_node (node);
1493 /* Varpool removal hook called for a NODE with a custom DATA. */
1495 void
1496 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
1498 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
1499 optimizer->remove_symtab_node (node);
1502 /* Remove symtab NODE triggered by symtab removal hooks. */
1504 void
1505 sem_item_optimizer::remove_symtab_node (symtab_node *node)
1507 gcc_assert (!m_classes.elements());
1509 m_removed_items_set.add (node);
1512 void
1513 sem_item_optimizer::remove_item (sem_item *item)
1515 if (m_symtab_node_map.get (item->node))
1516 m_symtab_node_map.remove (item->node);
1517 delete item;
1520 /* Removes all callgraph and varpool nodes that are marked by symtab
1521 as deleted. */
1523 void
1524 sem_item_optimizer::filter_removed_items (void)
1526 auto_vec <sem_item *> filtered;
1528 for (unsigned int i = 0; i < m_items.length(); i++)
1530 sem_item *item = m_items[i];
1532 if (!flag_ipa_icf_functions && item->type == FUNC)
1534 remove_item (item);
1535 continue;
1538 if (!flag_ipa_icf_variables && item->type == VAR)
1540 remove_item (item);
1541 continue;
1544 bool no_body_function = false;
1546 if (item->type == FUNC)
1548 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
1550 no_body_function = in_lto_p && (cnode->alias || cnode->body_removed);
1553 if(!m_removed_items_set.contains (m_items[i]->node)
1554 && !no_body_function)
1556 if (item->type == VAR || (!DECL_CXX_CONSTRUCTOR_P (item->decl)
1557 && !DECL_CXX_DESTRUCTOR_P (item->decl)))
1559 filtered.safe_push (m_items[i]);
1560 continue;
1564 remove_item (item);
1567 /* Clean-up of released semantic items. */
1569 m_items.release ();
1570 for (unsigned int i = 0; i < filtered.length(); i++)
1571 m_items.safe_push (filtered[i]);
1574 /* Optimizer entry point. */
1576 void
1577 sem_item_optimizer::execute (void)
1579 filter_removed_items ();
1580 build_hash_based_classes ();
1582 if (dump_file)
1583 fprintf (dump_file, "Dump after hash based groups\n");
1584 dump_cong_classes ();
1586 for (unsigned int i = 0; i < m_items.length(); i++)
1587 m_items[i]->init_wpa ();
1589 build_graph ();
1591 subdivide_classes_by_equality (true);
1593 if (dump_file)
1594 fprintf (dump_file, "Dump after WPA based types groups\n");
1596 dump_cong_classes ();
1598 process_cong_reduction ();
1599 verify_classes ();
1601 if (dump_file)
1602 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
1604 dump_cong_classes ();
1606 parse_nonsingleton_classes ();
1607 subdivide_classes_by_equality ();
1609 if (dump_file)
1610 fprintf (dump_file, "Dump after full equality comparison of groups\n");
1612 dump_cong_classes ();
1614 unsigned int prev_class_count = m_classes_count;
1616 process_cong_reduction ();
1617 dump_cong_classes ();
1618 verify_classes ();
1619 merge_classes (prev_class_count);
1621 if (dump_file && (dump_flags & TDF_DETAILS))
1622 symtab_node::dump_table (dump_file);
1625 /* Function responsible for visiting all potential functions and
1626 read-only variables that can be merged. */
1628 void
1629 sem_item_optimizer::parse_funcs_and_vars (void)
1631 cgraph_node *cnode;
1633 if (flag_ipa_icf_functions)
1634 FOR_EACH_DEFINED_FUNCTION (cnode)
1636 sem_function *f = sem_function::parse (cnode, &m_bmstack);
1637 if (f)
1639 m_items.safe_push (f);
1640 m_symtab_node_map.put (cnode, f);
1642 if (dump_file)
1643 fprintf (dump_file, "Parsed function:%s\n", f->asm_name ());
1645 if (dump_file && (dump_flags & TDF_DETAILS))
1646 f->dump_to_file (dump_file);
1648 else if (dump_file)
1649 fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
1652 varpool_node *vnode;
1654 if (flag_ipa_icf_variables)
1655 FOR_EACH_DEFINED_VARIABLE (vnode)
1657 sem_variable *v = sem_variable::parse (vnode, &m_bmstack);
1659 if (v)
1661 m_items.safe_push (v);
1662 m_symtab_node_map.put (vnode, v);
1667 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1669 void
1670 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
1672 item->index_in_class = cls->members.length ();
1673 cls->members.safe_push (item);
1674 item->cls = cls;
1677 /* Congruence classes are built by hash value. */
1679 void
1680 sem_item_optimizer::build_hash_based_classes (void)
1682 for (unsigned i = 0; i < m_items.length (); i++)
1684 sem_item *item = m_items[i];
1686 congruence_class_group *group = get_group_by_hash (item->get_hash (),
1687 item->type);
1689 if (!group->classes.length ())
1691 m_classes_count++;
1692 group->classes.safe_push (new congruence_class (class_id++));
1695 add_item_to_class (group->classes[0], item);
1699 /* Build references according to call graph. */
1701 void
1702 sem_item_optimizer::build_graph (void)
1704 for (unsigned i = 0; i < m_items.length (); i++)
1706 sem_item *item = m_items[i];
1707 m_symtab_node_map.put (item->node, item);
1710 for (unsigned i = 0; i < m_items.length (); i++)
1712 sem_item *item = m_items[i];
1714 if (item->type == FUNC)
1716 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
1718 cgraph_edge *e = cnode->callees;
1719 while (e)
1721 sem_item **slot = m_symtab_node_map.get (e->callee);
1722 if (slot)
1723 item->add_reference (*slot);
1725 e = e->next_callee;
1729 ipa_ref *ref = NULL;
1730 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
1732 sem_item **slot = m_symtab_node_map.get (ref->referred);
1733 if (slot)
1734 item->add_reference (*slot);
1739 /* Semantic items in classes having more than one element and initialized.
1740 In case of WPA, we load function body. */
1742 void
1743 sem_item_optimizer::parse_nonsingleton_classes (void)
1745 unsigned int init_called_count = 0;
1747 for (unsigned i = 0; i < m_items.length (); i++)
1748 if (m_items[i]->cls->members.length () > 1)
1750 m_items[i]->init ();
1751 init_called_count++;
1754 if (dump_file)
1755 fprintf (dump_file, "Init called for %u items (%.2f%%).\n", init_called_count,
1756 m_items.length () ? 100.0f * init_called_count / m_items.length (): 0.0f);
1759 /* Equality function for semantic items is used to subdivide existing
1760 classes. If IN_WPA, fast equality function is invoked. */
1762 void
1763 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
1765 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
1766 it != m_classes.end (); ++it)
1768 unsigned int class_count = (*it)->classes.length ();
1770 for (unsigned i = 0; i < class_count; i++)
1772 congruence_class *c = (*it)->classes [i];
1774 if (c->members.length() > 1)
1776 auto_vec <sem_item *> new_vector;
1778 sem_item *first = c->members[0];
1779 new_vector.safe_push (first);
1781 unsigned class_split_first = (*it)->classes.length ();
1783 for (unsigned j = 1; j < c->members.length (); j++)
1785 sem_item *item = c->members[j];
1787 bool equals = in_wpa ? first->equals_wpa (item,
1788 m_symtab_node_map) : first->equals (item, m_symtab_node_map);
1790 if (equals)
1791 new_vector.safe_push (item);
1792 else
1794 bool integrated = false;
1796 for (unsigned k = class_split_first; k < (*it)->classes.length (); k++)
1798 sem_item *x = (*it)->classes[k]->members[0];
1799 bool equals = in_wpa ? x->equals_wpa (item,
1800 m_symtab_node_map) : x->equals (item, m_symtab_node_map);
1802 if (equals)
1804 integrated = true;
1805 add_item_to_class ((*it)->classes[k], item);
1807 break;
1811 if (!integrated)
1813 congruence_class *c = new congruence_class (class_id++);
1814 m_classes_count++;
1815 add_item_to_class (c, item);
1817 (*it)->classes.safe_push (c);
1822 // we replace newly created new_vector for the class we've just splitted
1823 c->members.release ();
1824 c->members.create (new_vector.length ());
1826 for (unsigned int j = 0; j < new_vector.length (); j++)
1827 add_item_to_class (c, new_vector[j]);
1832 verify_classes ();
1835 /* Verify congruence classes if checking is enabled. */
1837 void
1838 sem_item_optimizer::verify_classes (void)
1840 #if ENABLE_CHECKING
1841 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
1842 it != m_classes.end (); ++it)
1844 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
1846 congruence_class *cls = (*it)->classes[i];
1848 gcc_checking_assert (cls);
1849 gcc_checking_assert (cls->members.length () > 0);
1851 for (unsigned int j = 0; j < cls->members.length (); j++)
1853 sem_item *item = cls->members[j];
1855 gcc_checking_assert (item);
1856 gcc_checking_assert (item->cls == cls);
1858 for (unsigned k = 0; k < item->usages.length (); k++)
1860 sem_usage_pair *usage = item->usages[k];
1861 gcc_checking_assert (usage->item->index_in_class <
1862 usage->item->cls->members.length ());
1867 #endif
1870 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
1871 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
1872 but unused argument. */
1874 bool
1875 sem_item_optimizer::release_split_map (congruence_class * const &,
1876 bitmap const &b, traverse_split_pair *)
1878 bitmap bmp = b;
1880 BITMAP_FREE (bmp);
1882 return true;
1885 /* Process split operation for a class given as pointer CLS_PTR,
1886 where bitmap B splits congruence class members. DATA is used
1887 as argument of split pair. */
1889 bool
1890 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
1891 bitmap const &b, traverse_split_pair *pair)
1893 sem_item_optimizer *optimizer = pair->optimizer;
1894 const congruence_class *splitter_cls = pair->cls;
1896 /* If counted bits are greater than zero and less than the number of members
1897 a group will be splitted. */
1898 unsigned popcount = bitmap_count_bits (b);
1900 if (popcount > 0 && popcount < cls->members.length ())
1902 congruence_class* newclasses[2] = { new congruence_class (class_id++), new congruence_class (class_id++) };
1904 for (unsigned int i = 0; i < cls->members.length (); i++)
1906 int target = bitmap_bit_p (b, i);
1907 congruence_class *tc = newclasses[target];
1909 add_item_to_class (tc, cls->members[i]);
1912 #ifdef ENABLE_CHECKING
1913 for (unsigned int i = 0; i < 2; i++)
1914 gcc_checking_assert (newclasses[i]->members.length ());
1915 #endif
1917 if (splitter_cls == cls)
1918 optimizer->splitter_class_removed = true;
1920 /* Remove old class from worklist if presented. */
1921 bool in_worklist = cls->in_worklist;
1923 if (in_worklist)
1924 cls->in_worklist = false;
1926 congruence_class_group g;
1927 g.hash = cls->members[0]->get_hash ();
1928 g.type = cls->members[0]->type;
1930 congruence_class_group *slot = optimizer->m_classes.find(&g);
1932 for (unsigned int i = 0; i < slot->classes.length (); i++)
1933 if (slot->classes[i] == cls)
1935 slot->classes.ordered_remove (i);
1936 break;
1939 /* New class will be inserted and integrated to work list. */
1940 for (unsigned int i = 0; i < 2; i++)
1941 optimizer->add_class (newclasses[i]);
1943 /* Two classes replace one, so that increment just by one. */
1944 optimizer->m_classes_count++;
1946 /* If OLD class was presented in the worklist, we remove the class
1947 and replace it will both newly created classes. */
1948 if (in_worklist)
1949 for (unsigned int i = 0; i < 2; i++)
1950 optimizer->worklist_push (newclasses[i]);
1951 else /* Just smaller class is inserted. */
1953 unsigned int smaller_index = newclasses[0]->members.length () <
1954 newclasses[1]->members.length () ?
1955 0 : 1;
1956 optimizer->worklist_push (newclasses[smaller_index]);
1959 if (dump_file && (dump_flags & TDF_DETAILS))
1961 fprintf (dump_file, " congruence class splitted:\n");
1962 cls->dump (dump_file, 4);
1964 fprintf (dump_file, " newly created groups:\n");
1965 for (unsigned int i = 0; i < 2; i++)
1966 newclasses[i]->dump (dump_file, 4);
1969 /* Release class if not presented in work list. */
1970 if (!in_worklist)
1971 delete cls;
1975 return true;
1978 /* Tests if a class CLS used as INDEXth splits any congruence classes.
1979 Bitmap stack BMSTACK is used for bitmap allocation. */
1981 void
1982 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
1983 unsigned int index)
1985 hash_map <congruence_class *, bitmap> split_map;
1987 for (unsigned int i = 0; i < cls->members.length (); i++)
1989 sem_item *item = cls->members[i];
1991 /* Iterate all usages that have INDEX as usage of the item. */
1992 for (unsigned int j = 0; j < item->usages.length (); j++)
1994 sem_usage_pair *usage = item->usages[j];
1996 if (usage->index != index)
1997 continue;
1999 bitmap *slot = split_map.get (usage->item->cls);
2000 bitmap b;
2002 if(!slot)
2004 b = BITMAP_ALLOC (&m_bmstack);
2005 split_map.put (usage->item->cls, b);
2007 else
2008 b = *slot;
2010 #if ENABLE_CHECKING
2011 gcc_checking_assert (usage->item->cls);
2012 gcc_checking_assert (usage->item->index_in_class <
2013 usage->item->cls->members.length ());
2014 #endif
2016 bitmap_set_bit (b, usage->item->index_in_class);
2020 traverse_split_pair pair;
2021 pair.optimizer = this;
2022 pair.cls = cls;
2024 splitter_class_removed = false;
2025 split_map.traverse
2026 <traverse_split_pair *, sem_item_optimizer::traverse_congruence_split> (&pair);
2028 /* Bitmap clean-up. */
2029 split_map.traverse
2030 <traverse_split_pair *, sem_item_optimizer::release_split_map> (NULL);
2033 /* Every usage of a congruence class CLS is a candidate that can split the
2034 collection of classes. Bitmap stack BMSTACK is used for bitmap
2035 allocation. */
2037 void
2038 sem_item_optimizer::do_congruence_step (congruence_class *cls)
2040 bitmap_iterator bi;
2041 unsigned int i;
2043 bitmap usage = BITMAP_ALLOC (&m_bmstack);
2045 for (unsigned int i = 0; i < cls->members.length (); i++)
2046 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
2048 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
2050 if (dump_file && (dump_flags & TDF_DETAILS))
2051 fprintf (dump_file, " processing congruece step for class: %u, index: %u\n",
2052 cls->id, i);
2054 do_congruence_step_for_index (cls, i);
2056 if (splitter_class_removed)
2057 break;
2060 BITMAP_FREE (usage);
2063 /* Adds a newly created congruence class CLS to worklist. */
2065 void
2066 sem_item_optimizer::worklist_push (congruence_class *cls)
2068 /* Return if the class CLS is already presented in work list. */
2069 if (cls->in_worklist)
2070 return;
2072 cls->in_worklist = true;
2073 worklist.push_back (cls);
2076 /* Pops a class from worklist. */
2078 congruence_class *
2079 sem_item_optimizer::worklist_pop (void)
2081 congruence_class *cls;
2083 while (!worklist.empty ())
2085 cls = worklist.front ();
2086 worklist.pop_front ();
2087 if (cls->in_worklist)
2089 cls->in_worklist = false;
2091 return cls;
2093 else
2095 /* Work list item was already intended to be removed.
2096 The only reason for doing it is to split a class.
2097 Thus, the class CLS is deleted. */
2098 delete cls;
2102 return NULL;
2105 /* Iterative congruence reduction function. */
2107 void
2108 sem_item_optimizer::process_cong_reduction (void)
2110 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2111 it != m_classes.end (); ++it)
2112 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2113 if ((*it)->classes[i]->is_class_used ())
2114 worklist_push ((*it)->classes[i]);
2116 if (dump_file)
2117 fprintf (dump_file, "Worklist has been filled with: %lu\n",
2118 (unsigned long) worklist.size ());
2120 if (dump_file && (dump_flags & TDF_DETAILS))
2121 fprintf (dump_file, "Congruence class reduction\n");
2123 congruence_class *cls;
2124 while ((cls = worklist_pop ()) != NULL)
2125 do_congruence_step (cls);
2128 /* Debug function prints all informations about congruence classes. */
2130 void
2131 sem_item_optimizer::dump_cong_classes (void)
2133 if (!dump_file)
2134 return;
2136 fprintf (dump_file,
2137 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2138 m_classes_count, (unsigned long) m_classes.elements(), m_items.length ());
2140 /* Histogram calculation. */
2141 unsigned int max_index = 0;
2142 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
2144 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2145 it != m_classes.end (); ++it)
2147 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2149 unsigned int c = (*it)->classes[i]->members.length ();
2150 histogram[c]++;
2152 if (c > max_index)
2153 max_index = c;
2156 fprintf (dump_file,
2157 "Class size histogram [num of members]: number of classe number of classess\n");
2159 for (unsigned int i = 0; i <= max_index; i++)
2160 if (histogram[i])
2161 fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
2163 fprintf (dump_file, "\n\n");
2166 if (dump_flags & TDF_DETAILS)
2167 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2168 it != m_classes.end (); ++it)
2170 fprintf (dump_file, " group: with %u classes:\n", (*it)->classes.length ());
2172 for (unsigned i = 0; i < (*it)->classes.length (); i++)
2174 (*it)->classes[i]->dump (dump_file, 4);
2176 if(i < (*it)->classes.length () - 1)
2177 fprintf (dump_file, " ");
2181 free (histogram);
2184 /* After reduction is done, we can declare all items in a group
2185 to be equal. PREV_CLASS_COUNT is start number of classes
2186 before reduction. */
2188 void
2189 sem_item_optimizer::merge_classes (unsigned int prev_class_count)
2191 unsigned int item_count = m_items.length ();
2192 unsigned int class_count = m_classes_count;
2193 unsigned int equal_items = item_count - class_count;
2195 unsigned int non_singular_classes_count = 0;
2196 unsigned int non_singular_classes_sum = 0;
2198 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2199 it != m_classes.end (); ++it)
2200 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2202 congruence_class *c = (*it)->classes[i];
2203 if (c->members.length () > 1)
2205 non_singular_classes_count++;
2206 non_singular_classes_sum += c->members.length ();
2210 if (dump_file)
2212 fprintf (dump_file, "\nItem count: %u\n", item_count);
2213 fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
2214 prev_class_count, class_count);
2215 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
2216 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
2217 class_count ? 1.0f * item_count / class_count : 0.0f);
2218 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
2219 non_singular_classes_count ? 1.0f * non_singular_classes_sum /
2220 non_singular_classes_count : 0.0f,
2221 non_singular_classes_count);
2222 fprintf (dump_file, "Equal symbols: %u\n", equal_items);
2223 fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
2224 item_count ? 100.0f * equal_items / item_count : 0.0f);
2227 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2228 it != m_classes.end (); ++it)
2229 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2231 congruence_class *c = (*it)->classes[i];
2233 if (c->members.length () == 1)
2234 continue;
2236 gcc_assert (c->members.length ());
2238 sem_item *source = c->members[0];
2240 for (unsigned int j = 1; j < c->members.length (); j++)
2242 sem_item *alias = c->members[j];
2243 source->equals (alias, m_symtab_node_map);
2245 if (dump_file)
2247 fprintf (dump_file, "Semantic equality hit:%s->%s\n",
2248 source->name (), alias->name ());
2249 fprintf (dump_file, "Assembler symbol names:%s->%s\n",
2250 source->asm_name (), alias->asm_name ());
2253 if (dump_file && (dump_flags & TDF_DETAILS))
2255 source->dump_to_file (dump_file);
2256 alias->dump_to_file (dump_file);
2259 source->merge (alias);
2264 /* Dump function prints all class members to a FILE with an INDENT. */
2266 void
2267 congruence_class::dump (FILE *file, unsigned int indent) const
2269 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
2270 id, members[0]->get_hash (), members.length ());
2272 FPUTS_SPACES (file, indent + 2, "");
2273 for (unsigned i = 0; i < members.length (); i++)
2274 fprintf (file, "%s(%p/%u) ", members[i]->asm_name (), (void *) members[i]->decl,
2275 members[i]->node->order);
2277 fprintf (file, "\n");
2280 /* Returns true if there's a member that is used from another group. */
2282 bool
2283 congruence_class::is_class_used (void)
2285 for (unsigned int i = 0; i < members.length (); i++)
2286 if (members[i]->usages.length ())
2287 return true;
2289 return false;
2292 /* Initialization and computation of symtab node hash, there data
2293 are propagated later on. */
2295 static sem_item_optimizer *optimizer = NULL;
2297 /* Generate pass summary for IPA ICF pass. */
2299 static void
2300 ipa_icf_generate_summary (void)
2302 if (!optimizer)
2303 optimizer = new sem_item_optimizer ();
2305 optimizer->parse_funcs_and_vars ();
2308 /* Write pass summary for IPA ICF pass. */
2310 static void
2311 ipa_icf_write_summary (void)
2313 gcc_assert (optimizer);
2315 optimizer->write_summary ();
2318 /* Read pass summary for IPA ICF pass. */
2320 static void
2321 ipa_icf_read_summary (void)
2323 if (!optimizer)
2324 optimizer = new sem_item_optimizer ();
2326 optimizer->read_summary ();
2327 optimizer->register_hooks ();
2330 /* Semantic equality exection function. */
2332 static unsigned int
2333 ipa_icf_driver (void)
2335 gcc_assert (optimizer);
2337 optimizer->execute ();
2338 optimizer->unregister_hooks ();
2340 delete optimizer;
2341 optimizer = NULL;
2343 return 0;
2346 const pass_data pass_data_ipa_icf =
2348 IPA_PASS, /* type */
2349 "icf", /* name */
2350 OPTGROUP_IPA, /* optinfo_flags */
2351 TV_IPA_ICF, /* tv_id */
2352 0, /* properties_required */
2353 0, /* properties_provided */
2354 0, /* properties_destroyed */
2355 0, /* todo_flags_start */
2356 0, /* todo_flags_finish */
2359 class pass_ipa_icf : public ipa_opt_pass_d
2361 public:
2362 pass_ipa_icf (gcc::context *ctxt)
2363 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
2364 ipa_icf_generate_summary, /* generate_summary */
2365 ipa_icf_write_summary, /* write_summary */
2366 ipa_icf_read_summary, /* read_summary */
2367 NULL, /*
2368 write_optimization_summary */
2369 NULL, /*
2370 read_optimization_summary */
2371 NULL, /* stmt_fixup */
2372 0, /* function_transform_todo_flags_start */
2373 NULL, /* function_transform */
2374 NULL) /* variable_transform */
2377 /* opt_pass methods: */
2378 virtual bool gate (function *)
2380 return flag_ipa_icf_variables || flag_ipa_icf_functions;
2383 virtual unsigned int execute (function *)
2385 return ipa_icf_driver();
2387 }; // class pass_ipa_icf
2389 } // ipa_icf namespace
2391 ipa_opt_pass_d *
2392 make_pass_ipa_icf (gcc::context *ctxt)
2394 return new ipa_icf::pass_ipa_icf (ctxt);