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"
73 #include "dominance.h"
75 #include "basic-block.h"
76 #include "tree-ssa-alias.h"
77 #include "internal-fn.h"
78 #include "gimple-expr.h"
84 #include "statistics.h"
86 #include "fixed-value.h"
87 #include "insn-config.h"
96 #include "gimple-iterator.h"
97 #include "gimple-ssa.h"
99 #include "tree-phinodes.h"
100 #include "stringpool.h"
101 #include "tree-ssanames.h"
102 #include "tree-dfa.h"
103 #include "tree-pass.h"
104 #include "gimple-pretty-print.h"
105 #include "hash-map.h"
106 #include "plugin-api.h"
109 #include "alloc-pool.h"
110 #include "symbol-summary.h"
111 #include "ipa-prop.h"
112 #include "ipa-inline.h"
115 #include "hash-table.h"
116 #include "coverage.h"
118 #include "print-tree.h"
119 #include "lto-streamer.h"
120 #include "data-streamer.h"
121 #include "ipa-utils.h"
123 #include "ipa-icf-gimple.h"
126 using namespace ipa_icf_gimple
;
132 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
134 m_references
.create (0);
135 m_interposables
.create (0);
139 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
142 for (unsigned i
= 0; i
< node
->num_references (); i
++)
144 ref
= node
->iterate_reference (i
, ref
);
145 if (ref
->address_matters_p ())
146 m_references
.safe_push (ref
->referred
);
148 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
150 if (ref
->address_matters_p ())
151 m_references
.safe_push (ref
->referred
);
153 m_interposables
.safe_push (ref
->referred
);
157 if (is_a
<cgraph_node
*> (node
))
159 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
161 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
162 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
163 m_interposables
.safe_push (e
->callee
);
167 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
169 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
170 item (_item
), index (_index
)
174 /* Semantic item constructor for a node of _TYPE, where STACK is used
175 for bitmap memory allocation. */
177 sem_item::sem_item (sem_item_type _type
,
178 bitmap_obstack
*stack
): type(_type
), hash(0)
183 /* Semantic item constructor for a node of _TYPE, where STACK is used
184 for bitmap memory allocation. The item is based on symtab node _NODE
185 with computed _HASH. */
187 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
188 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
189 node (_node
), hash (_hash
)
195 /* Add reference to a semantic TARGET. */
198 sem_item::add_reference (sem_item
*target
)
200 refs
.safe_push (target
);
201 unsigned index
= refs
.length ();
202 target
->usages
.safe_push (new sem_usage_pair(this, index
));
203 bitmap_set_bit (target
->usage_index_bitmap
, index
);
204 refs_set
.add (target
->node
);
207 /* Initialize internal data structures. Bitmap STACK is used for
208 bitmap memory allocation process. */
211 sem_item::setup (bitmap_obstack
*stack
)
213 gcc_checking_assert (node
);
216 tree_refs
.create (0);
218 usage_index_bitmap
= BITMAP_ALLOC (stack
);
221 sem_item::~sem_item ()
223 for (unsigned i
= 0; i
< usages
.length (); i
++)
227 tree_refs
.release ();
230 BITMAP_FREE (usage_index_bitmap
);
233 /* Dump function for debugging purpose. */
236 sem_item::dump (void)
240 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
241 name(), node
->order
, (void *) node
->decl
);
242 fprintf (dump_file
, " hash: %u\n", get_hash ());
243 fprintf (dump_file
, " references: ");
245 for (unsigned i
= 0; i
< refs
.length (); i
++)
246 fprintf (dump_file
, "%s%s ", refs
[i
]->name (),
247 i
< refs
.length() - 1 ? "," : "");
249 fprintf (dump_file
, "\n");
253 /* Return true if target supports alias symbols. */
256 sem_item::target_supports_symbol_aliases_p (void)
258 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
265 /* Semantic function constructor that uses STACK as bitmap memory stack. */
267 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
268 m_checker (NULL
), m_compared_func (NULL
)
270 arg_types
.create (0);
272 bb_sorted
.create (0);
275 /* Constructor based on callgraph node _NODE with computed hash _HASH.
276 Bitmap STACK is used for memory allocation. */
277 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
278 bitmap_obstack
*stack
):
279 sem_item (FUNC
, node
, hash
, stack
),
280 m_checker (NULL
), m_compared_func (NULL
)
282 arg_types
.create (0);
284 bb_sorted
.create (0);
287 sem_function::~sem_function ()
289 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
290 delete (bb_sorted
[i
]);
292 arg_types
.release ();
294 bb_sorted
.release ();
297 /* Calculates hash value based on a BASIC_BLOCK. */
300 sem_function::get_bb_hash (const sem_bb
*basic_block
)
302 inchash::hash hstate
;
304 hstate
.add_int (basic_block
->nondbg_stmt_count
);
305 hstate
.add_int (basic_block
->edge_count
);
307 return hstate
.end ();
310 /* References independent hash function. */
313 sem_function::get_hash (void)
317 inchash::hash hstate
;
318 hstate
.add_int (177454); /* Random number for function type. */
320 hstate
.add_int (arg_count
);
321 hstate
.add_int (cfg_checksum
);
322 hstate
.add_int (gcode_hash
);
324 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
325 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
327 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
328 hstate
.add_int (bb_sizes
[i
]);
330 hash
= hstate
.end ();
336 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
337 point to a same function. Comparison can be skipped if IGNORED_NODES
338 contains these nodes. */
341 sem_function::compare_cgraph_references (hash_map
<symtab_node
*, sem_item
*>
343 symtab_node
*n1
, symtab_node
*n2
)
345 if (n1
== n2
|| (ignored_nodes
.get (n1
) && ignored_nodes
.get (n2
)))
348 /* TODO: add more precise comparison for weakrefs, etc. */
350 return return_false_with_msg ("different references");
353 /* If cgraph edges E1 and E2 are indirect calls, verify that
354 ECF flags are the same. */
356 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
358 if (e1
->indirect_info
&& e2
->indirect_info
)
360 int e1_flags
= e1
->indirect_info
->ecf_flags
;
361 int e2_flags
= e2
->indirect_info
->ecf_flags
;
363 if (e1_flags
!= e2_flags
)
364 return return_false_with_msg ("ICF flags are different");
366 else if (e1
->indirect_info
|| e2
->indirect_info
)
372 /* Fast equality function based on knowledge known in WPA. */
375 sem_function::equals_wpa (sem_item
*item
,
376 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
378 gcc_assert (item
->type
== FUNC
);
380 m_compared_func
= static_cast<sem_function
*> (item
);
382 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
383 return return_false_with_msg ("different number of arguments");
385 /* Checking types of arguments. */
386 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
388 /* This guard is here for function pointer with attributes (pr59927.c). */
389 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
390 return return_false_with_msg ("NULL argument type");
392 /* Polymorphic comparison is executed just for non-leaf functions. */
393 bool is_not_leaf
= get_node ()->callees
!= NULL
394 || get_node ()->indirect_calls
!= NULL
;
396 if (!func_checker::compatible_types_p (arg_types
[i
],
397 m_compared_func
->arg_types
[i
],
398 is_not_leaf
, i
== 0))
399 return return_false_with_msg ("argument type is different");
402 /* Result type checking. */
403 if (!func_checker::compatible_types_p (result_type
,
404 m_compared_func
->result_type
))
405 return return_false_with_msg ("result types are different");
407 if (node
->num_references () != item
->node
->num_references ())
408 return return_false_with_msg ("different number of references");
410 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
411 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
413 item
->node
->iterate_reference (i
, ref2
);
415 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
, ref2
->referred
))
419 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
420 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
424 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
, e2
->callee
))
427 e1
= e1
->next_callee
;
428 e2
= e2
->next_callee
;
432 return return_false_with_msg ("different number of edges");
437 /* Returns true if the item equals to ITEM given as argument. */
440 sem_function::equals (sem_item
*item
,
441 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
443 gcc_assert (item
->type
== FUNC
);
444 bool eq
= equals_private (item
, ignored_nodes
);
446 if (m_checker
!= NULL
)
452 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
454 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
455 name(), item
->name (), node
->order
, item
->node
->order
, asm_name (),
456 item
->asm_name (), eq
? "true" : "false");
461 /* Processes function equality comparison. */
464 sem_function::equals_private (sem_item
*item
,
465 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
467 if (item
->type
!= FUNC
)
470 basic_block bb1
, bb2
;
472 edge_iterator ei1
, ei2
;
476 m_compared_func
= static_cast<sem_function
*> (item
);
478 gcc_assert (decl
!= item
->decl
);
480 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
481 || edge_count
!= m_compared_func
->edge_count
482 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
483 return return_false ();
485 if (!equals_wpa (item
, ignored_nodes
))
488 /* Checking function TARGET and OPTIMIZATION flags. */
489 cl_target_option
*tar1
= target_opts_for_fn (decl
);
490 cl_target_option
*tar2
= target_opts_for_fn (m_compared_func
->decl
);
492 if (tar1
!= NULL
&& tar2
!= NULL
)
494 if (!cl_target_option_eq (tar1
, tar2
))
496 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
498 fprintf (dump_file
, "target flags difference");
499 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
502 return return_false_with_msg ("Target flags are different");
505 else if (tar1
!= NULL
|| tar2
!= NULL
)
506 return return_false_with_msg ("Target flags are different");
508 cl_optimization
*opt1
= opts_for_fn (decl
);
509 cl_optimization
*opt2
= opts_for_fn (m_compared_func
->decl
);
511 if (opt1
!= NULL
&& opt2
!= NULL
)
513 if (memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
515 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
517 fprintf (dump_file
, "optimization flags difference");
518 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
521 return return_false_with_msg ("optimization flags are different");
524 else if (opt1
!= NULL
|| opt2
!= NULL
)
525 return return_false_with_msg ("optimization flags are different");
527 /* Checking function arguments. */
528 tree decl1
= DECL_ATTRIBUTES (decl
);
529 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
531 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
532 compare_polymorphic_p (),
535 &m_compared_func
->refs_set
);
539 return return_false ();
541 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
542 return return_false ();
544 tree attr_value1
= TREE_VALUE (decl1
);
545 tree attr_value2
= TREE_VALUE (decl2
);
547 if (attr_value1
&& attr_value2
)
549 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
550 TREE_VALUE (attr_value2
));
552 return return_false_with_msg ("attribute values are different");
554 else if (!attr_value1
&& !attr_value2
)
557 return return_false ();
559 decl1
= TREE_CHAIN (decl1
);
560 decl2
= TREE_CHAIN (decl2
);
564 return return_false();
567 for (arg1
= DECL_ARGUMENTS (decl
),
568 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
569 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
570 if (!m_checker
->compare_decl (arg1
, arg2
))
571 return return_false ();
573 /* Fill-up label dictionary. */
574 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
576 m_checker
->parse_labels (bb_sorted
[i
]);
577 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
580 /* Checking all basic blocks. */
581 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
582 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
583 return return_false();
585 dump_message ("All BBs are equal\n");
587 auto_vec
<int> bb_dict
;
589 /* Basic block edges check. */
590 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
592 bb1
= bb_sorted
[i
]->bb
;
593 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
595 ei2
= ei_start (bb2
->preds
);
597 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
601 if (e1
->flags
!= e2
->flags
)
602 return return_false_with_msg ("flags comparison returns false");
604 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
605 return return_false_with_msg ("edge comparison returns false");
607 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
608 return return_false_with_msg ("BB comparison returns false");
610 if (!m_checker
->compare_edge (e1
, e2
))
611 return return_false_with_msg ("edge comparison returns false");
617 /* Basic block PHI nodes comparison. */
618 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
619 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
620 return return_false_with_msg ("PHI node comparison returns false");
625 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
626 Helper for call_for_symbol_thunks_and_aliases. */
629 set_local (cgraph_node
*node
, void *data
)
631 node
->local
.local
= data
!= NULL
;
635 /* TREE_ADDRESSABLE of NODE to true.
636 Helper for call_for_symbol_thunks_and_aliases. */
639 set_addressable (varpool_node
*node
, void *)
641 TREE_ADDRESSABLE (node
->decl
) = 1;
645 /* Clear DECL_RTL of NODE.
646 Helper for call_for_symbol_thunks_and_aliases. */
649 clear_decl_rtl (symtab_node
*node
, void *)
651 SET_DECL_RTL (node
->decl
, NULL
);
655 /* Redirect all callers of N and its aliases to TO. Remove aliases if
656 possible. Return number of redirections made. */
659 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
666 cgraph_edge
*e
= n
->callers
;
667 e
->redirect_callee (to
);
670 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
672 bool removed
= false;
673 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
675 if ((DECL_COMDAT_GROUP (n
->decl
)
676 && (DECL_COMDAT_GROUP (n
->decl
)
677 == DECL_COMDAT_GROUP (n_alias
->decl
)))
678 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
679 && n
->get_availability () > AVAIL_INTERPOSABLE
))
681 nredirected
+= redirect_all_callers (n_alias
, to
);
682 if (n_alias
->can_remove_if_no_direct_calls_p ()
683 && !n_alias
->has_aliases_p ())
692 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
696 sem_function::merge (sem_item
*alias_item
)
698 gcc_assert (alias_item
->type
== FUNC
);
700 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
702 cgraph_node
*original
= get_node ();
703 cgraph_node
*local_original
= NULL
;
704 cgraph_node
*alias
= alias_func
->get_node ();
706 bool create_wrapper
= false;
707 bool create_alias
= false;
708 bool redirect_callers
= false;
711 bool original_discardable
= false;
713 bool original_address_matters
= original
->address_matters_p ();
714 bool alias_address_matters
= alias
->address_matters_p ();
716 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
717 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
722 "DECL_NO_INLINE_WARNING mismatch.\n\n");
726 /* Do not attempt to mix functions from different user sections;
727 we do not know what user intends with those. */
728 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
729 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
730 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
735 "original and alias are in different sections.\n\n");
739 /* See if original is in a section that can be discarded if the main
742 Also consider case where we have resolution info and we know that
743 original's definition is not going to be used. In this case we can not
744 create alias to original. */
745 if (original
->can_be_discarded_p ()
746 || (node
->resolution
!= LDPR_UNKNOWN
747 && !decl_binds_to_current_def_p (node
->decl
)))
748 original_discardable
= true;
750 /* Creating a symtab alias is the optimal way to merge.
751 It however can not be used in the following cases:
753 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
754 2) if ORIGINAL is in a section that may be discarded by linker or if
755 it is an external functions where we can not create an alias
756 (ORIGINAL_DISCARDABLE)
757 3) if target do not support symbol aliases.
758 4) original and alias lie in different comdat groups.
760 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
761 and/or redirect all callers from ALIAS to ORIGINAL. */
762 if ((original_address_matters
&& alias_address_matters
)
763 || (original_discardable
764 && (!DECL_COMDAT_GROUP (alias
->decl
)
765 || (DECL_COMDAT_GROUP (alias
->decl
)
766 != DECL_COMDAT_GROUP (original
->decl
))))
767 || !sem_item::target_supports_symbol_aliases_p ()
768 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
770 /* First see if we can produce wrapper. */
772 /* Do not turn function in one comdat group into wrapper to another
773 comdat group. Other compiler producing the body of the
774 another comdat group may make opossite decision and with unfortunate
775 linker choices this may close a loop. */
776 if (DECL_COMDAT_GROUP (alias
->decl
)
777 && (DECL_COMDAT_GROUP (alias
->decl
)
778 != DECL_COMDAT_GROUP (original
->decl
)))
782 "Wrapper cannot be created because of COMDAT\n");
784 else if (DECL_STATIC_CHAIN (alias
->decl
))
788 "Can not create wrapper of nested functions.\n");
790 /* TODO: We can also deal with variadic functions never calling
792 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
796 "can not create wrapper of stdarg function.\n");
798 else if (inline_summaries
799 && inline_summaries
->get (alias
)->self_size
<= 2)
802 fprintf (dump_file
, "Wrapper creation is not "
803 "profitable (function is too small).\n");
805 /* If user paid attention to mark function noinline, assume it is
806 somewhat special and do not try to turn it into a wrapper that can
807 not be undone by inliner. */
808 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
811 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
814 create_wrapper
= true;
816 /* We can redirect local calls in the case both alias and orignal
817 are not interposable. */
819 = alias
->get_availability () > AVAIL_INTERPOSABLE
820 && original
->get_availability () > AVAIL_INTERPOSABLE
821 && !alias
->instrumented_version
;
823 if (!redirect_callers
&& !create_wrapper
)
826 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
827 "produce wrapper\n\n");
831 /* Work out the symbol the wrapper should call.
832 If ORIGINAL is interposable, we need to call a local alias.
833 Also produce local alias (if possible) as an optimization. */
834 if (!original_discardable
835 || (DECL_COMDAT_GROUP (original
->decl
)
836 && (DECL_COMDAT_GROUP (original
->decl
)
837 == DECL_COMDAT_GROUP (alias
->decl
))))
840 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
842 && original
->get_availability () > AVAIL_INTERPOSABLE
)
843 local_original
= original
;
844 /* If original is COMDAT local, we can not really redirect external
846 if (original
->comdat_local_p ())
847 redirect_callers
= false;
849 /* If we can not use local alias, fallback to the original
851 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
852 local_original
= original
;
856 fprintf (dump_file
, "Not unifying; "
857 "can not produce local alias.\n\n");
861 if (!redirect_callers
&& !create_wrapper
)
864 fprintf (dump_file
, "Not unifying; "
865 "can not redirect callers nor produce a wrapper\n\n");
869 && !alias
->can_remove_if_no_direct_calls_p ())
872 fprintf (dump_file
, "Not unifying; can not make wrapper and "
873 "function has other uses than direct calls\n\n");
880 if (redirect_callers
)
882 int nredirected
= redirect_all_callers (alias
, local_original
);
886 alias
->icf_merged
= true;
887 local_original
->icf_merged
= true;
889 if (dump_file
&& nredirected
)
890 fprintf (dump_file
, "%i local calls have been "
891 "redirected.\n", nredirected
);
894 /* If all callers was redirected, do not produce wrapper. */
895 if (alias
->can_remove_if_no_direct_calls_p ()
896 && !alias
->has_aliases_p ())
898 create_wrapper
= false;
901 gcc_assert (!create_alias
);
903 else if (create_alias
)
905 alias
->icf_merged
= true;
907 /* Remove the function's body. */
908 ipa_merge_profiles (original
, alias
);
909 alias
->release_body (true);
911 /* Notice global symbol possibly produced RTL. */
912 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
915 /* Create the alias. */
916 cgraph_node::create_alias (alias_func
->decl
, decl
);
917 alias
->resolve_alias (original
);
919 original
->call_for_symbol_thunks_and_aliases
920 (set_local
, (void *)(size_t) original
->local_p (), true);
923 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
927 gcc_assert (!create_alias
);
928 alias
->icf_merged
= true;
929 local_original
->icf_merged
= true;
931 ipa_merge_profiles (local_original
, alias
, true);
932 alias
->create_wrapper (local_original
);
935 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
937 gcc_assert (alias
->icf_merged
|| remove
);
938 original
->icf_merged
= true;
940 /* Inform the inliner about cross-module merging. */
941 if ((original
->lto_file_data
|| alias
->lto_file_data
)
942 && original
->lto_file_data
!= alias
->lto_file_data
)
943 local_original
->merged
= original
->merged
= true;
947 ipa_merge_profiles (original
, alias
);
948 alias
->release_body ();
950 alias
->body_removed
= true;
951 alias
->icf_merged
= true;
953 fprintf (dump_file
, "Unified; Function body was removed.\n");
959 /* Semantic item initialization function. */
962 sem_function::init (void)
965 get_node ()->get_untransformed_body ();
967 tree fndecl
= node
->decl
;
968 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
971 gcc_assert (SSANAMES (func
));
973 ssa_names_size
= SSANAMES (func
)->length ();
977 region_tree
= func
->eh
->region_tree
;
979 /* iterating all function arguments. */
980 arg_count
= count_formal_params (fndecl
);
982 edge_count
= n_edges_for_fn (func
);
983 cfg_checksum
= coverage_compute_cfg_checksum (func
);
985 inchash::hash hstate
;
988 FOR_EACH_BB_FN (bb
, func
)
990 unsigned nondbg_stmt_count
= 0;
993 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
); ei_next (&ei
))
994 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
997 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1000 gimple stmt
= gsi_stmt (gsi
);
1002 if (gimple_code (stmt
) != GIMPLE_DEBUG
)
1004 hash_stmt (&hstate
, stmt
);
1005 nondbg_stmt_count
++;
1009 gcode_hash
= hstate
.end ();
1010 bb_sizes
.safe_push (nondbg_stmt_count
);
1012 /* Inserting basic block to hash table. */
1013 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1014 EDGE_COUNT (bb
->preds
) + EDGE_COUNT (bb
->succs
));
1016 bb_sorted
.safe_push (semantic_bb
);
1022 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1025 sem_function::hash_stmt (inchash::hash
*hstate
, gimple stmt
)
1027 enum gimple_code code
= gimple_code (stmt
);
1029 hstate
->add_int (code
);
1031 if (code
== GIMPLE_CALL
)
1033 /* Checking of argument. */
1034 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
1036 tree argument
= gimple_call_arg (stmt
, i
);
1038 switch (TREE_CODE (argument
))
1041 if (tree_fits_shwi_p (argument
))
1042 hstate
->add_wide_int (tree_to_shwi (argument
));
1043 else if (tree_fits_uhwi_p (argument
))
1044 hstate
->add_wide_int (tree_to_uhwi (argument
));
1050 c
= TREE_REAL_CST (argument
);
1051 n
= real_to_integer (&c
);
1053 hstate
->add_wide_int (n
);
1057 tree addr_operand
= TREE_OPERAND (argument
, 0);
1059 if (TREE_CODE (addr_operand
) == STRING_CST
)
1060 hstate
->add (TREE_STRING_POINTER (addr_operand
),
1061 TREE_STRING_LENGTH (addr_operand
));
1072 /* Return true if polymorphic comparison must be processed. */
1075 sem_function::compare_polymorphic_p (void)
1077 return get_node ()->callees
!= NULL
1078 || get_node ()->indirect_calls
!= NULL
1079 || m_compared_func
->get_node ()->callees
!= NULL
1080 || m_compared_func
->get_node ()->indirect_calls
!= NULL
;
1083 /* For a given call graph NODE, the function constructs new
1084 semantic function item. */
1087 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1089 tree fndecl
= node
->decl
;
1090 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1092 /* TODO: add support for thunks and aliases. */
1094 if (!func
|| !node
->has_gimple_body_p ())
1097 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1100 sem_function
*f
= new sem_function (node
, 0, stack
);
1107 /* Parses function arguments and result type. */
1110 sem_function::parse_tree_args (void)
1114 if (arg_types
.exists ())
1115 arg_types
.release ();
1117 arg_types
.create (4);
1118 tree fnargs
= DECL_ARGUMENTS (decl
);
1120 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
1121 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
1123 /* Function result type. */
1124 result
= DECL_RESULT (decl
);
1125 result_type
= result
? TREE_TYPE (result
) : NULL
;
1127 /* During WPA, we can get arguments by following method. */
1130 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
1131 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
1132 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
1134 result_type
= TREE_TYPE (TREE_TYPE (decl
));
1138 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1139 return true if phi nodes are semantically equivalent in these blocks . */
1142 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1144 gphi_iterator si1
, si2
;
1146 unsigned size1
, size2
, i
;
1150 gcc_assert (bb1
!= NULL
);
1151 gcc_assert (bb2
!= NULL
);
1153 si2
= gsi_start_phis (bb2
);
1154 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1157 gsi_next_nonvirtual_phi (&si1
);
1158 gsi_next_nonvirtual_phi (&si2
);
1160 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1163 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1164 return return_false();
1169 tree phi_result1
= gimple_phi_result (phi1
);
1170 tree phi_result2
= gimple_phi_result (phi2
);
1172 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1173 return return_false_with_msg ("PHI results are different");
1175 size1
= gimple_phi_num_args (phi1
);
1176 size2
= gimple_phi_num_args (phi2
);
1179 return return_false ();
1181 for (i
= 0; i
< size1
; ++i
)
1183 t1
= gimple_phi_arg (phi1
, i
)->def
;
1184 t2
= gimple_phi_arg (phi2
, i
)->def
;
1186 if (!m_checker
->compare_operand (t1
, t2
))
1187 return return_false ();
1189 e1
= gimple_phi_arg_edge (phi1
, i
);
1190 e2
= gimple_phi_arg_edge (phi2
, i
);
1192 if (!m_checker
->compare_edge (e1
, e2
))
1193 return return_false ();
1202 /* Returns true if tree T can be compared as a handled component. */
1205 sem_function::icf_handled_component_p (tree t
)
1207 tree_code tc
= TREE_CODE (t
);
1209 return ((handled_component_p (t
))
1210 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
1211 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
1214 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1215 corresponds to TARGET. */
1218 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1223 if (bb_dict
->length () <= (unsigned)source
)
1224 bb_dict
->safe_grow_cleared (source
+ 1);
1226 if ((*bb_dict
)[source
] == 0)
1228 (*bb_dict
)[source
] = target
;
1232 return (*bb_dict
)[source
] == target
;
1235 /* Iterates all tree types in T1 and T2 and returns true if all types
1236 are compatible. If COMPARE_POLYMORPHIC is set to true,
1237 more strict comparison is executed. */
1240 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
1248 while (t1
!= NULL
&& t2
!= NULL
)
1250 tv1
= TREE_VALUE (t1
);
1251 tv2
= TREE_VALUE (t2
);
1253 tc1
= TREE_CODE (tv1
);
1254 tc2
= TREE_CODE (tv2
);
1256 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
1258 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
1260 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
1263 t1
= TREE_CHAIN (t1
);
1264 t2
= TREE_CHAIN (t2
);
1271 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1273 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1277 /* Constructor based on varpool node _NODE with computed hash _HASH.
1278 Bitmap STACK is used for memory allocation. */
1280 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1281 bitmap_obstack
*stack
): sem_item(VAR
,
1284 gcc_checking_assert (node
);
1285 gcc_checking_assert (get_node ());
1288 /* Returns true if the item equals to ITEM given as argument. */
1291 sem_variable::equals (sem_item
*item
,
1292 hash_map
<symtab_node
*, sem_item
*> & ARG_UNUSED (ignored_nodes
))
1294 gcc_assert (item
->type
== VAR
);
1296 sem_variable
*v
= static_cast<sem_variable
*>(item
);
1298 if (!ctor
|| !v
->ctor
)
1299 return return_false_with_msg ("ctor is missing for semantic variable");
1301 return sem_variable::equals (ctor
, v
->ctor
);
1304 /* Compares trees T1 and T2 for semantic equality. */
1307 sem_variable::equals (tree t1
, tree t2
)
1309 tree_code tc1
= TREE_CODE (t1
);
1310 tree_code tc2
= TREE_CODE (t2
);
1319 unsigned len1
= vec_safe_length (CONSTRUCTOR_ELTS (t1
));
1320 unsigned len2
= vec_safe_length (CONSTRUCTOR_ELTS (t2
));
1325 for (unsigned i
= 0; i
< len1
; i
++)
1326 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1
, i
)->value
,
1327 CONSTRUCTOR_ELT (t2
, i
)->value
)
1328 || CONSTRUCTOR_ELT (t1
, i
)->index
!= CONSTRUCTOR_ELT (t2
, i
)->index
)
1335 tree x1
= TREE_OPERAND (t1
, 0);
1336 tree x2
= TREE_OPERAND (t2
, 0);
1337 tree y1
= TREE_OPERAND (t1
, 1);
1338 tree y2
= TREE_OPERAND (t2
, 1);
1340 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1342 return return_false ();
1344 /* Type of the offset on MEM_REF does not matter. */
1345 return sem_variable::equals (x1
, x2
)
1346 && wi::to_offset (y1
) == wi::to_offset (y2
);
1351 tree op1
= TREE_OPERAND (t1
, 0);
1352 tree op2
= TREE_OPERAND (t2
, 0);
1353 return sem_variable::equals (op1
, op2
);
1361 return func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1363 && wi::to_offset (t1
) == wi::to_offset (t2
);
1367 return operand_equal_p (t1
, t2
, OEP_ONLY_CONST
);
1370 case POINTER_PLUS_EXPR
:
1372 tree x1
= TREE_OPERAND (t1
, 0);
1373 tree x2
= TREE_OPERAND (t2
, 0);
1374 tree y1
= TREE_OPERAND (t1
, 1);
1375 tree y2
= TREE_OPERAND (t2
, 1);
1377 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1380 return return_false_with_msg ("ERROR_MARK");
1382 return return_false_with_msg ("Unknown TREE code reached");
1386 /* Parser function that visits a varpool NODE. */
1389 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1391 tree decl
= node
->decl
;
1393 bool readonly
= TYPE_P (decl
) ? TYPE_READONLY (decl
) : TREE_READONLY (decl
);
1397 bool can_handle
= DECL_VIRTUAL_P (decl
)
1398 || flag_merge_constants
>= 2
1399 || (!TREE_ADDRESSABLE (decl
) && !node
->externally_visible
);
1401 if (!can_handle
|| DECL_EXTERNAL (decl
))
1404 tree ctor
= ctor_for_folding (decl
);
1408 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1415 /* References independent hash function. */
1418 sem_variable::get_hash (void)
1423 inchash::hash hstate
;
1425 hstate
.add_int (456346417);
1426 hstate
.add_int (TREE_CODE (ctor
));
1428 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
1430 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (ctor
));
1431 hstate
.add_int (length
);
1434 hash
= hstate
.end ();
1439 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1443 sem_variable::merge (sem_item
*alias_item
)
1445 gcc_assert (alias_item
->type
== VAR
);
1447 if (!sem_item::target_supports_symbol_aliases_p ())
1450 fprintf (dump_file
, "Not unifying; "
1451 "Symbol aliases are not supported by target\n\n");
1455 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1457 varpool_node
*original
= get_node ();
1458 varpool_node
*alias
= alias_var
->get_node ();
1459 bool original_discardable
= false;
1461 bool original_address_matters
= original
->address_matters_p ();
1462 bool alias_address_matters
= alias
->address_matters_p ();
1464 /* See if original is in a section that can be discarded if the main
1466 Also consider case where we have resolution info and we know that
1467 original's definition is not going to be used. In this case we can not
1468 create alias to original. */
1469 if (original
->can_be_discarded_p ()
1470 || (node
->resolution
!= LDPR_UNKNOWN
1471 && !decl_binds_to_current_def_p (node
->decl
)))
1472 original_discardable
= true;
1474 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1476 /* Constant pool machinery is not quite ready for aliases.
1477 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
1478 For LTO merging does not happen that is an important missing feature.
1479 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
1480 flag is dropped and non-local symbol name is assigned. */
1481 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
1482 || DECL_IN_CONSTANT_POOL (original
->decl
))
1486 "Not unifying; constant pool variables.\n\n");
1490 /* Do not attempt to mix functions from different user sections;
1491 we do not know what user intends with those. */
1492 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1493 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1494 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1499 "original and alias are in different sections.\n\n");
1503 /* We can not merge if address comparsion metters. */
1504 if (original_address_matters
&& alias_address_matters
1505 && flag_merge_constants
< 2)
1510 "adress of original and alias may be compared.\n\n");
1514 if (original_discardable
1515 && (!DECL_COMDAT_GROUP (original
->decl
)
1516 || (DECL_COMDAT_GROUP (original
->decl
)
1517 != DECL_COMDAT_GROUP (alias
->decl
))))
1520 fprintf (dump_file
, "Not unifying; alias cannot be created; "
1521 "target is discardable\n\n");
1527 gcc_assert (!original
->alias
);
1528 gcc_assert (!alias
->alias
);
1530 alias
->analyzed
= false;
1532 DECL_INITIAL (alias
->decl
) = NULL
;
1533 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1535 alias
->need_bounds_init
= false;
1536 alias
->remove_all_references ();
1537 if (TREE_ADDRESSABLE (alias
->decl
))
1538 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
1540 varpool_node::create_alias (alias_var
->decl
, decl
);
1541 alias
->resolve_alias (original
);
1544 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
1550 /* Dump symbol to FILE. */
1553 sem_variable::dump_to_file (FILE *file
)
1557 print_node (file
, "", decl
, 0);
1558 fprintf (file
, "\n\n");
1561 /* Iterates though a constructor and identifies tree references
1562 we are interested in semantic function equality. */
1565 sem_variable::parse_tree_refs (tree t
)
1567 switch (TREE_CODE (t
))
1571 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1573 for (unsigned i
= 0; i
< length
; i
++)
1574 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1581 tree op
= TREE_OPERAND (t
, 0);
1582 parse_tree_refs (op
);
1587 tree_refs
.safe_push (t
);
1595 unsigned int sem_item_optimizer::class_id
= 0;
1597 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1598 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1601 bitmap_obstack_initialize (&m_bmstack
);
1604 sem_item_optimizer::~sem_item_optimizer ()
1606 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1609 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1610 it
!= m_classes
.end (); ++it
)
1612 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1613 delete (*it
)->classes
[i
];
1615 (*it
)->classes
.release ();
1621 bitmap_obstack_release (&m_bmstack
);
1624 /* Write IPA ICF summary for symbols. */
1627 sem_item_optimizer::write_summary (void)
1629 unsigned int count
= 0;
1631 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1632 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1635 /* Calculate number of symbols to be serialized. */
1636 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1638 lsei_next_in_partition (&lsei
))
1640 symtab_node
*node
= lsei_node (lsei
);
1642 if (m_symtab_node_map
.get (node
))
1646 streamer_write_uhwi (ob
, count
);
1648 /* Process all of the symbols. */
1649 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1651 lsei_next_in_partition (&lsei
))
1653 symtab_node
*node
= lsei_node (lsei
);
1655 sem_item
**item
= m_symtab_node_map
.get (node
);
1659 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1660 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1662 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1666 streamer_write_char_stream (ob
->main_stream
, 0);
1667 produce_asm (ob
, NULL
);
1668 destroy_output_block (ob
);
1671 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1672 contains LEN bytes. */
1675 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1676 const char *data
, size_t len
)
1678 const lto_function_header
*header
=
1679 (const lto_function_header
*) data
;
1680 const int cfg_offset
= sizeof (lto_function_header
);
1681 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1682 const int string_offset
= main_offset
+ header
->main_size
;
1687 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1688 header
->main_size
, file_data
->mode_table
);
1691 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1692 header
->string_size
, vNULL
);
1694 count
= streamer_read_uhwi (&ib_main
);
1696 for (i
= 0; i
< count
; i
++)
1700 lto_symtab_encoder_t encoder
;
1702 index
= streamer_read_uhwi (&ib_main
);
1703 encoder
= file_data
->symtab_node_encoder
;
1704 node
= lto_symtab_encoder_deref (encoder
, index
);
1706 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1708 gcc_assert (node
->definition
);
1711 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1712 (void *) node
->decl
, node
->order
);
1714 if (is_a
<cgraph_node
*> (node
))
1716 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1718 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
1722 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
1724 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
1728 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
1730 lto_data_in_delete (data_in
);
1733 /* Read IPA IPA ICF summary for symbols. */
1736 sem_item_optimizer::read_summary (void)
1738 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1739 lto_file_decl_data
*file_data
;
1742 while ((file_data
= file_data_vec
[j
++]))
1745 const char *data
= lto_get_section_data (file_data
,
1746 LTO_section_ipa_icf
, NULL
, &len
);
1749 read_section (file_data
, data
, len
);
1753 /* Register callgraph and varpool hooks. */
1756 sem_item_optimizer::register_hooks (void)
1758 if (!m_cgraph_node_hooks
)
1759 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
1760 (&sem_item_optimizer::cgraph_removal_hook
, this);
1762 if (!m_varpool_node_hooks
)
1763 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
1764 (&sem_item_optimizer::varpool_removal_hook
, this);
1767 /* Unregister callgraph and varpool hooks. */
1770 sem_item_optimizer::unregister_hooks (void)
1772 if (m_cgraph_node_hooks
)
1773 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
1775 if (m_varpool_node_hooks
)
1776 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
1779 /* Adds a CLS to hashtable associated by hash value. */
1782 sem_item_optimizer::add_class (congruence_class
*cls
)
1784 gcc_assert (cls
->members
.length ());
1786 congruence_class_group
*group
= get_group_by_hash (
1787 cls
->members
[0]->get_hash (),
1788 cls
->members
[0]->type
);
1789 group
->classes
.safe_push (cls
);
1792 /* Gets a congruence class group based on given HASH value and TYPE. */
1794 congruence_class_group
*
1795 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
1797 congruence_class_group
*item
= XNEW (congruence_class_group
);
1801 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
1807 item
->classes
.create (1);
1814 /* Callgraph removal hook called for a NODE with a custom DATA. */
1817 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
1819 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1820 optimizer
->remove_symtab_node (node
);
1823 /* Varpool removal hook called for a NODE with a custom DATA. */
1826 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
1828 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1829 optimizer
->remove_symtab_node (node
);
1832 /* Remove symtab NODE triggered by symtab removal hooks. */
1835 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
1837 gcc_assert (!m_classes
.elements());
1839 m_removed_items_set
.add (node
);
1843 sem_item_optimizer::remove_item (sem_item
*item
)
1845 if (m_symtab_node_map
.get (item
->node
))
1846 m_symtab_node_map
.remove (item
->node
);
1850 /* Removes all callgraph and varpool nodes that are marked by symtab
1854 sem_item_optimizer::filter_removed_items (void)
1856 auto_vec
<sem_item
*> filtered
;
1858 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1860 sem_item
*item
= m_items
[i
];
1862 if (m_removed_items_set
.contains (item
->node
))
1868 if (item
->type
== FUNC
)
1870 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
1872 bool no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
1873 if (no_body_function
|| !opt_for_fn (item
->decl
, flag_ipa_icf_functions
)
1874 || DECL_CXX_CONSTRUCTOR_P (item
->decl
)
1875 || DECL_CXX_DESTRUCTOR_P (item
->decl
))
1878 filtered
.safe_push (item
);
1882 if (!flag_ipa_icf_variables
)
1885 filtered
.safe_push (item
);
1889 /* Clean-up of released semantic items. */
1892 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
1893 m_items
.safe_push (filtered
[i
]);
1896 /* Optimizer entry point. */
1899 sem_item_optimizer::execute (void)
1901 filter_removed_items ();
1902 unregister_hooks ();
1904 build_hash_based_classes ();
1907 fprintf (dump_file
, "Dump after hash based groups\n");
1908 dump_cong_classes ();
1910 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1911 m_items
[i
]->init_wpa ();
1915 subdivide_classes_by_equality (true);
1918 fprintf (dump_file
, "Dump after WPA based types groups\n");
1920 dump_cong_classes ();
1922 process_cong_reduction ();
1926 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
1928 dump_cong_classes ();
1930 parse_nonsingleton_classes ();
1931 subdivide_classes_by_equality ();
1934 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
1936 dump_cong_classes ();
1938 unsigned int prev_class_count
= m_classes_count
;
1940 process_cong_reduction ();
1941 dump_cong_classes ();
1943 merge_classes (prev_class_count
);
1945 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1946 symtab_node::dump_table (dump_file
);
1949 /* Function responsible for visiting all potential functions and
1950 read-only variables that can be merged. */
1953 sem_item_optimizer::parse_funcs_and_vars (void)
1957 if (flag_ipa_icf_functions
)
1958 FOR_EACH_DEFINED_FUNCTION (cnode
)
1960 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
1963 m_items
.safe_push (f
);
1964 m_symtab_node_map
.put (cnode
, f
);
1967 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
1969 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1970 f
->dump_to_file (dump_file
);
1973 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
1976 varpool_node
*vnode
;
1978 if (flag_ipa_icf_variables
)
1979 FOR_EACH_DEFINED_VARIABLE (vnode
)
1981 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
1985 m_items
.safe_push (v
);
1986 m_symtab_node_map
.put (vnode
, v
);
1991 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1994 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
1996 item
->index_in_class
= cls
->members
.length ();
1997 cls
->members
.safe_push (item
);
2001 /* Congruence classes are built by hash value. */
2004 sem_item_optimizer::build_hash_based_classes (void)
2006 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2008 sem_item
*item
= m_items
[i
];
2010 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
2013 if (!group
->classes
.length ())
2016 group
->classes
.safe_push (new congruence_class (class_id
++));
2019 add_item_to_class (group
->classes
[0], item
);
2023 /* Build references according to call graph. */
2026 sem_item_optimizer::build_graph (void)
2028 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2030 sem_item
*item
= m_items
[i
];
2031 m_symtab_node_map
.put (item
->node
, item
);
2034 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2036 sem_item
*item
= m_items
[i
];
2038 if (item
->type
== FUNC
)
2040 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2042 cgraph_edge
*e
= cnode
->callees
;
2045 sem_item
**slot
= m_symtab_node_map
.get (e
->callee
);
2047 item
->add_reference (*slot
);
2053 ipa_ref
*ref
= NULL
;
2054 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2056 sem_item
**slot
= m_symtab_node_map
.get (ref
->referred
);
2058 item
->add_reference (*slot
);
2063 /* Semantic items in classes having more than one element and initialized.
2064 In case of WPA, we load function body. */
2067 sem_item_optimizer::parse_nonsingleton_classes (void)
2069 unsigned int init_called_count
= 0;
2071 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2072 if (m_items
[i
]->cls
->members
.length () > 1)
2074 m_items
[i
]->init ();
2075 init_called_count
++;
2079 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2080 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2083 /* Equality function for semantic items is used to subdivide existing
2084 classes. If IN_WPA, fast equality function is invoked. */
2087 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2089 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2090 it
!= m_classes
.end (); ++it
)
2092 unsigned int class_count
= (*it
)->classes
.length ();
2094 for (unsigned i
= 0; i
< class_count
; i
++)
2096 congruence_class
*c
= (*it
)->classes
[i
];
2098 if (c
->members
.length() > 1)
2100 auto_vec
<sem_item
*> new_vector
;
2102 sem_item
*first
= c
->members
[0];
2103 new_vector
.safe_push (first
);
2105 unsigned class_split_first
= (*it
)->classes
.length ();
2107 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2109 sem_item
*item
= c
->members
[j
];
2111 bool equals
= in_wpa
? first
->equals_wpa (item
,
2112 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2115 new_vector
.safe_push (item
);
2118 bool integrated
= false;
2120 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2122 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2123 bool equals
= in_wpa
? x
->equals_wpa (item
,
2124 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2129 add_item_to_class ((*it
)->classes
[k
], item
);
2137 congruence_class
*c
= new congruence_class (class_id
++);
2139 add_item_to_class (c
, item
);
2141 (*it
)->classes
.safe_push (c
);
2146 // we replace newly created new_vector for the class we've just splitted
2147 c
->members
.release ();
2148 c
->members
.create (new_vector
.length ());
2150 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2151 add_item_to_class (c
, new_vector
[j
]);
2159 /* Subdivide classes by address references that members of the class
2160 reference. Example can be a pair of functions that have an address
2161 taken from a function. If these addresses are different the class
2165 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2167 unsigned newly_created_classes
= 0;
2169 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2170 it
!= m_classes
.end (); ++it
)
2172 unsigned int class_count
= (*it
)->classes
.length ();
2173 auto_vec
<congruence_class
*> new_classes
;
2175 for (unsigned i
= 0; i
< class_count
; i
++)
2177 congruence_class
*c
= (*it
)->classes
[i
];
2179 if (c
->members
.length() > 1)
2181 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2182 symbol_compare_hashmap_traits
> split_map
;
2184 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2186 sem_item
*source_node
= c
->members
[j
];
2188 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2190 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
);
2191 gcc_checking_assert (slot
);
2193 slot
->safe_push (source_node
);
2196 /* If the map contains more than one key, we have to split the map
2198 if (split_map
.elements () != 1)
2200 bool first_class
= true;
2202 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2203 symbol_compare_hashmap_traits
>::iterator it2
= split_map
.begin ();
2204 for (; it2
!= split_map
.end (); ++it2
)
2206 congruence_class
*new_cls
;
2207 new_cls
= new congruence_class (class_id
++);
2209 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2210 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2212 worklist_push (new_cls
);
2213 newly_created_classes
++;
2217 (*it
)->classes
[i
] = new_cls
;
2218 first_class
= false;
2222 new_classes
.safe_push (new_cls
);
2230 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2231 (*it
)->classes
.safe_push (new_classes
[i
]);
2234 return newly_created_classes
;
2237 /* Verify congruence classes if checking is enabled. */
2240 sem_item_optimizer::verify_classes (void)
2243 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2244 it
!= m_classes
.end (); ++it
)
2246 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2248 congruence_class
*cls
= (*it
)->classes
[i
];
2250 gcc_checking_assert (cls
);
2251 gcc_checking_assert (cls
->members
.length () > 0);
2253 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
2255 sem_item
*item
= cls
->members
[j
];
2257 gcc_checking_assert (item
);
2258 gcc_checking_assert (item
->cls
== cls
);
2260 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
2262 sem_usage_pair
*usage
= item
->usages
[k
];
2263 gcc_checking_assert (usage
->item
->index_in_class
<
2264 usage
->item
->cls
->members
.length ());
2272 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2273 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2274 but unused argument. */
2277 sem_item_optimizer::release_split_map (congruence_class
* const &,
2278 bitmap
const &b
, traverse_split_pair
*)
2287 /* Process split operation for a class given as pointer CLS_PTR,
2288 where bitmap B splits congruence class members. DATA is used
2289 as argument of split pair. */
2292 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2293 bitmap
const &b
, traverse_split_pair
*pair
)
2295 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2296 const congruence_class
*splitter_cls
= pair
->cls
;
2298 /* If counted bits are greater than zero and less than the number of members
2299 a group will be splitted. */
2300 unsigned popcount
= bitmap_count_bits (b
);
2302 if (popcount
> 0 && popcount
< cls
->members
.length ())
2304 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
2306 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2308 int target
= bitmap_bit_p (b
, i
);
2309 congruence_class
*tc
= newclasses
[target
];
2311 add_item_to_class (tc
, cls
->members
[i
]);
2314 #ifdef ENABLE_CHECKING
2315 for (unsigned int i
= 0; i
< 2; i
++)
2316 gcc_checking_assert (newclasses
[i
]->members
.length ());
2319 if (splitter_cls
== cls
)
2320 optimizer
->splitter_class_removed
= true;
2322 /* Remove old class from worklist if presented. */
2323 bool in_worklist
= cls
->in_worklist
;
2326 cls
->in_worklist
= false;
2328 congruence_class_group g
;
2329 g
.hash
= cls
->members
[0]->get_hash ();
2330 g
.type
= cls
->members
[0]->type
;
2332 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
2334 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2335 if (slot
->classes
[i
] == cls
)
2337 slot
->classes
.ordered_remove (i
);
2341 /* New class will be inserted and integrated to work list. */
2342 for (unsigned int i
= 0; i
< 2; i
++)
2343 optimizer
->add_class (newclasses
[i
]);
2345 /* Two classes replace one, so that increment just by one. */
2346 optimizer
->m_classes_count
++;
2348 /* If OLD class was presented in the worklist, we remove the class
2349 and replace it will both newly created classes. */
2351 for (unsigned int i
= 0; i
< 2; i
++)
2352 optimizer
->worklist_push (newclasses
[i
]);
2353 else /* Just smaller class is inserted. */
2355 unsigned int smaller_index
= newclasses
[0]->members
.length () <
2356 newclasses
[1]->members
.length () ?
2358 optimizer
->worklist_push (newclasses
[smaller_index
]);
2361 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2363 fprintf (dump_file
, " congruence class splitted:\n");
2364 cls
->dump (dump_file
, 4);
2366 fprintf (dump_file
, " newly created groups:\n");
2367 for (unsigned int i
= 0; i
< 2; i
++)
2368 newclasses
[i
]->dump (dump_file
, 4);
2371 /* Release class if not presented in work list. */
2380 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2381 Bitmap stack BMSTACK is used for bitmap allocation. */
2384 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2387 hash_map
<congruence_class
*, bitmap
> split_map
;
2389 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2391 sem_item
*item
= cls
->members
[i
];
2393 /* Iterate all usages that have INDEX as usage of the item. */
2394 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2396 sem_usage_pair
*usage
= item
->usages
[j
];
2398 if (usage
->index
!= index
)
2401 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2406 b
= BITMAP_ALLOC (&m_bmstack
);
2407 split_map
.put (usage
->item
->cls
, b
);
2413 gcc_checking_assert (usage
->item
->cls
);
2414 gcc_checking_assert (usage
->item
->index_in_class
<
2415 usage
->item
->cls
->members
.length ());
2418 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2422 traverse_split_pair pair
;
2423 pair
.optimizer
= this;
2426 splitter_class_removed
= false;
2428 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2430 /* Bitmap clean-up. */
2432 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2435 /* Every usage of a congruence class CLS is a candidate that can split the
2436 collection of classes. Bitmap stack BMSTACK is used for bitmap
2440 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2445 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2447 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2448 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2450 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2452 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2453 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2456 do_congruence_step_for_index (cls
, i
);
2458 if (splitter_class_removed
)
2462 BITMAP_FREE (usage
);
2465 /* Adds a newly created congruence class CLS to worklist. */
2468 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2470 /* Return if the class CLS is already presented in work list. */
2471 if (cls
->in_worklist
)
2474 cls
->in_worklist
= true;
2475 worklist
.push_back (cls
);
2478 /* Pops a class from worklist. */
2481 sem_item_optimizer::worklist_pop (void)
2483 congruence_class
*cls
;
2485 while (!worklist
.empty ())
2487 cls
= worklist
.front ();
2488 worklist
.pop_front ();
2489 if (cls
->in_worklist
)
2491 cls
->in_worklist
= false;
2497 /* Work list item was already intended to be removed.
2498 The only reason for doing it is to split a class.
2499 Thus, the class CLS is deleted. */
2507 /* Iterative congruence reduction function. */
2510 sem_item_optimizer::process_cong_reduction (void)
2512 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2513 it
!= m_classes
.end (); ++it
)
2514 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2515 if ((*it
)->classes
[i
]->is_class_used ())
2516 worklist_push ((*it
)->classes
[i
]);
2519 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2520 (unsigned long) worklist
.size ());
2522 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2523 fprintf (dump_file
, "Congruence class reduction\n");
2525 congruence_class
*cls
;
2527 /* Process complete congruence reduction. */
2528 while ((cls
= worklist_pop ()) != NULL
)
2529 do_congruence_step (cls
);
2531 /* Subdivide newly created classes according to references. */
2532 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
2535 fprintf (dump_file
, "Address reference subdivision created: %u "
2536 "new classes.\n", new_classes
);
2539 /* Debug function prints all informations about congruence classes. */
2542 sem_item_optimizer::dump_cong_classes (void)
2548 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2549 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2551 /* Histogram calculation. */
2552 unsigned int max_index
= 0;
2553 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2555 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2556 it
!= m_classes
.end (); ++it
)
2558 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2560 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2568 "Class size histogram [num of members]: number of classe number of classess\n");
2570 for (unsigned int i
= 0; i
<= max_index
; i
++)
2572 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2574 fprintf (dump_file
, "\n\n");
2577 if (dump_flags
& TDF_DETAILS
)
2578 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2579 it
!= m_classes
.end (); ++it
)
2581 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2583 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2585 (*it
)->classes
[i
]->dump (dump_file
, 4);
2587 if(i
< (*it
)->classes
.length () - 1)
2588 fprintf (dump_file
, " ");
2595 /* After reduction is done, we can declare all items in a group
2596 to be equal. PREV_CLASS_COUNT is start number of classes
2597 before reduction. */
2600 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2602 unsigned int item_count
= m_items
.length ();
2603 unsigned int class_count
= m_classes_count
;
2604 unsigned int equal_items
= item_count
- class_count
;
2606 unsigned int non_singular_classes_count
= 0;
2607 unsigned int non_singular_classes_sum
= 0;
2609 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2610 it
!= m_classes
.end (); ++it
)
2611 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2613 congruence_class
*c
= (*it
)->classes
[i
];
2614 if (c
->members
.length () > 1)
2616 non_singular_classes_count
++;
2617 non_singular_classes_sum
+= c
->members
.length ();
2623 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2624 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2625 prev_class_count
, class_count
);
2626 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2627 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2628 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2629 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2630 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2631 non_singular_classes_count
: 0.0f
,
2632 non_singular_classes_count
);
2633 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2634 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2635 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2638 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2639 it
!= m_classes
.end (); ++it
)
2640 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2642 congruence_class
*c
= (*it
)->classes
[i
];
2644 if (c
->members
.length () == 1)
2647 gcc_assert (c
->members
.length ());
2649 sem_item
*source
= c
->members
[0];
2651 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2653 sem_item
*alias
= c
->members
[j
];
2657 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2658 source
->name (), alias
->name ());
2659 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2660 source
->asm_name (), alias
->asm_name ());
2663 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
2667 "Merge operation is skipped due to no_icf "
2673 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2675 source
->dump_to_file (dump_file
);
2676 alias
->dump_to_file (dump_file
);
2679 source
->merge (alias
);
2684 /* Dump function prints all class members to a FILE with an INDENT. */
2687 congruence_class::dump (FILE *file
, unsigned int indent
) const
2689 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2690 id
, members
[0]->get_hash (), members
.length ());
2692 FPUTS_SPACES (file
, indent
+ 2, "");
2693 for (unsigned i
= 0; i
< members
.length (); i
++)
2694 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2695 members
[i
]->node
->order
);
2697 fprintf (file
, "\n");
2700 /* Returns true if there's a member that is used from another group. */
2703 congruence_class::is_class_used (void)
2705 for (unsigned int i
= 0; i
< members
.length (); i
++)
2706 if (members
[i
]->usages
.length ())
2712 /* Initialization and computation of symtab node hash, there data
2713 are propagated later on. */
2715 static sem_item_optimizer
*optimizer
= NULL
;
2717 /* Generate pass summary for IPA ICF pass. */
2720 ipa_icf_generate_summary (void)
2723 optimizer
= new sem_item_optimizer ();
2725 optimizer
->register_hooks ();
2726 optimizer
->parse_funcs_and_vars ();
2729 /* Write pass summary for IPA ICF pass. */
2732 ipa_icf_write_summary (void)
2734 gcc_assert (optimizer
);
2736 optimizer
->write_summary ();
2739 /* Read pass summary for IPA ICF pass. */
2742 ipa_icf_read_summary (void)
2745 optimizer
= new sem_item_optimizer ();
2747 optimizer
->read_summary ();
2748 optimizer
->register_hooks ();
2751 /* Semantic equality exection function. */
2754 ipa_icf_driver (void)
2756 gcc_assert (optimizer
);
2758 optimizer
->execute ();
2766 const pass_data pass_data_ipa_icf
=
2768 IPA_PASS
, /* type */
2770 OPTGROUP_IPA
, /* optinfo_flags */
2771 TV_IPA_ICF
, /* tv_id */
2772 0, /* properties_required */
2773 0, /* properties_provided */
2774 0, /* properties_destroyed */
2775 0, /* todo_flags_start */
2776 0, /* todo_flags_finish */
2779 class pass_ipa_icf
: public ipa_opt_pass_d
2782 pass_ipa_icf (gcc::context
*ctxt
)
2783 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
2784 ipa_icf_generate_summary
, /* generate_summary */
2785 ipa_icf_write_summary
, /* write_summary */
2786 ipa_icf_read_summary
, /* read_summary */
2788 write_optimization_summary */
2790 read_optimization_summary */
2791 NULL
, /* stmt_fixup */
2792 0, /* function_transform_todo_flags_start */
2793 NULL
, /* function_transform */
2794 NULL
) /* variable_transform */
2797 /* opt_pass methods: */
2798 virtual bool gate (function
*)
2800 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
2803 virtual unsigned int execute (function
*)
2805 return ipa_icf_driver();
2807 }; // class pass_ipa_icf
2809 } // ipa_icf namespace
2812 make_pass_ipa_icf (gcc::context
*ctxt
)
2814 return new ipa_icf::pass_ipa_icf (ctxt
);