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.
759 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
760 and/or redirect all callers from ALIAS to ORIGINAL. */
761 if ((original_address_matters
&& alias_address_matters
)
762 || original_discardable
763 || !sem_item::target_supports_symbol_aliases_p ())
765 /* First see if we can produce wrapper. */
767 /* Do not turn function in one comdat group into wrapper to another
768 comdat group. Other compiler producing the body of the
769 another comdat group may make opossite decision and with unfortunate
770 linker choices this may close a loop. */
771 if (DECL_COMDAT_GROUP (alias
->decl
)
772 && (DECL_COMDAT_GROUP (alias
->decl
)
773 != DECL_COMDAT_GROUP (original
->decl
)))
777 "Wrapper cannot be created because of COMDAT\n");
779 else if (DECL_STATIC_CHAIN (alias
->decl
))
783 "Can not create wrapper of nested functions.\n");
785 /* TODO: We can also deal with variadic functions never calling
787 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
791 "can not create wrapper of stdarg function.\n");
793 else if (inline_summaries
794 && inline_summaries
->get (alias
)->self_size
<= 2)
797 fprintf (dump_file
, "Wrapper creation is not "
798 "profitable (function is too small).\n");
800 /* If user paid attention to mark function noinline, assume it is
801 somewhat special and do not try to turn it into a wrapper that can
802 not be undone by inliner. */
803 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
806 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
809 create_wrapper
= true;
811 /* We can redirect local calls in the case both alias and orignal
812 are not interposable. */
814 = alias
->get_availability () > AVAIL_INTERPOSABLE
815 && original
->get_availability () > AVAIL_INTERPOSABLE
816 && !alias
->instrumented_version
;
818 if (!redirect_callers
&& !create_wrapper
)
821 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
822 "produce wrapper\n\n");
826 /* Work out the symbol the wrapper should call.
827 If ORIGINAL is interposable, we need to call a local alias.
828 Also produce local alias (if possible) as an optimization. */
829 if (!original_discardable
830 || (DECL_COMDAT_GROUP (original
->decl
)
831 && (DECL_COMDAT_GROUP (original
->decl
)
832 == DECL_COMDAT_GROUP (alias
->decl
))))
835 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
837 && original
->get_availability () > AVAIL_INTERPOSABLE
)
838 local_original
= original
;
839 /* If original is COMDAT local, we can not really redirect external
841 if (original
->comdat_local_p ())
842 redirect_callers
= false;
844 /* If we can not use local alias, fallback to the original
846 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
847 local_original
= original
;
851 fprintf (dump_file
, "Not unifying; "
852 "can not produce local alias.\n\n");
856 if (!redirect_callers
&& !create_wrapper
)
859 fprintf (dump_file
, "Not unifying; "
860 "can not redirect callers nor produce a wrapper\n\n");
864 && !alias
->can_remove_if_no_direct_calls_p ())
867 fprintf (dump_file
, "Not unifying; can not make wrapper and "
868 "function has other uses than direct calls\n\n");
875 if (redirect_callers
)
877 int nredirected
= redirect_all_callers (alias
, local_original
);
881 alias
->icf_merged
= true;
882 local_original
->icf_merged
= true;
884 if (dump_file
&& nredirected
)
885 fprintf (dump_file
, "%i local calls have been "
886 "redirected.\n", nredirected
);
889 /* If all callers was redirected, do not produce wrapper. */
890 if (alias
->can_remove_if_no_direct_calls_p ()
891 && !alias
->has_aliases_p ())
893 create_wrapper
= false;
896 gcc_assert (!create_alias
);
898 else if (create_alias
)
900 alias
->icf_merged
= true;
902 /* Remove the function's body. */
903 ipa_merge_profiles (original
, alias
);
904 alias
->release_body (true);
906 /* Notice global symbol possibly produced RTL. */
907 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
910 /* Create the alias. */
911 cgraph_node::create_alias (alias_func
->decl
, decl
);
912 alias
->resolve_alias (original
);
914 original
->call_for_symbol_thunks_and_aliases
915 (set_local
, (void *)(size_t) original
->local_p (), true);
918 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
922 gcc_assert (!create_alias
);
923 alias
->icf_merged
= true;
924 local_original
->icf_merged
= true;
926 ipa_merge_profiles (local_original
, alias
, true);
927 alias
->create_wrapper (local_original
);
930 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
932 gcc_assert (alias
->icf_merged
|| remove
);
933 original
->icf_merged
= true;
935 /* Inform the inliner about cross-module merging. */
936 if ((original
->lto_file_data
|| alias
->lto_file_data
)
937 && original
->lto_file_data
!= alias
->lto_file_data
)
938 local_original
->merged
= original
->merged
= true;
942 ipa_merge_profiles (original
, alias
);
943 alias
->release_body ();
945 alias
->body_removed
= true;
946 alias
->icf_merged
= true;
948 fprintf (dump_file
, "Unified; Function body was removed.\n");
954 /* Semantic item initialization function. */
957 sem_function::init (void)
960 get_node ()->get_untransformed_body ();
962 tree fndecl
= node
->decl
;
963 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
966 gcc_assert (SSANAMES (func
));
968 ssa_names_size
= SSANAMES (func
)->length ();
972 region_tree
= func
->eh
->region_tree
;
974 /* iterating all function arguments. */
975 arg_count
= count_formal_params (fndecl
);
977 edge_count
= n_edges_for_fn (func
);
978 cfg_checksum
= coverage_compute_cfg_checksum (func
);
980 inchash::hash hstate
;
983 FOR_EACH_BB_FN (bb
, func
)
985 unsigned nondbg_stmt_count
= 0;
988 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
); ei_next (&ei
))
989 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
992 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
995 gimple stmt
= gsi_stmt (gsi
);
997 if (gimple_code (stmt
) != GIMPLE_DEBUG
)
999 hash_stmt (&hstate
, stmt
);
1000 nondbg_stmt_count
++;
1004 gcode_hash
= hstate
.end ();
1005 bb_sizes
.safe_push (nondbg_stmt_count
);
1007 /* Inserting basic block to hash table. */
1008 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1009 EDGE_COUNT (bb
->preds
) + EDGE_COUNT (bb
->succs
));
1011 bb_sorted
.safe_push (semantic_bb
);
1017 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1020 sem_function::hash_stmt (inchash::hash
*hstate
, gimple stmt
)
1022 enum gimple_code code
= gimple_code (stmt
);
1024 hstate
->add_int (code
);
1026 if (code
== GIMPLE_CALL
)
1028 /* Checking of argument. */
1029 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
1031 tree argument
= gimple_call_arg (stmt
, i
);
1033 switch (TREE_CODE (argument
))
1036 if (tree_fits_shwi_p (argument
))
1037 hstate
->add_wide_int (tree_to_shwi (argument
));
1038 else if (tree_fits_uhwi_p (argument
))
1039 hstate
->add_wide_int (tree_to_uhwi (argument
));
1045 c
= TREE_REAL_CST (argument
);
1046 n
= real_to_integer (&c
);
1048 hstate
->add_wide_int (n
);
1052 tree addr_operand
= TREE_OPERAND (argument
, 0);
1054 if (TREE_CODE (addr_operand
) == STRING_CST
)
1055 hstate
->add (TREE_STRING_POINTER (addr_operand
),
1056 TREE_STRING_LENGTH (addr_operand
));
1067 /* Return true if polymorphic comparison must be processed. */
1070 sem_function::compare_polymorphic_p (void)
1072 return get_node ()->callees
!= NULL
1073 || get_node ()->indirect_calls
!= NULL
1074 || m_compared_func
->get_node ()->callees
!= NULL
1075 || m_compared_func
->get_node ()->indirect_calls
!= NULL
;
1078 /* For a given call graph NODE, the function constructs new
1079 semantic function item. */
1082 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1084 tree fndecl
= node
->decl
;
1085 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1087 /* TODO: add support for thunks and aliases. */
1089 if (!func
|| !node
->has_gimple_body_p ())
1092 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1095 sem_function
*f
= new sem_function (node
, 0, stack
);
1102 /* Parses function arguments and result type. */
1105 sem_function::parse_tree_args (void)
1109 if (arg_types
.exists ())
1110 arg_types
.release ();
1112 arg_types
.create (4);
1113 tree fnargs
= DECL_ARGUMENTS (decl
);
1115 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
1116 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
1118 /* Function result type. */
1119 result
= DECL_RESULT (decl
);
1120 result_type
= result
? TREE_TYPE (result
) : NULL
;
1122 /* During WPA, we can get arguments by following method. */
1125 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
1126 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
1127 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
1129 result_type
= TREE_TYPE (TREE_TYPE (decl
));
1133 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1134 return true if phi nodes are semantically equivalent in these blocks . */
1137 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1139 gphi_iterator si1
, si2
;
1141 unsigned size1
, size2
, i
;
1145 gcc_assert (bb1
!= NULL
);
1146 gcc_assert (bb2
!= NULL
);
1148 si2
= gsi_start_phis (bb2
);
1149 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1152 gsi_next_nonvirtual_phi (&si1
);
1153 gsi_next_nonvirtual_phi (&si2
);
1155 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1158 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1159 return return_false();
1164 tree phi_result1
= gimple_phi_result (phi1
);
1165 tree phi_result2
= gimple_phi_result (phi2
);
1167 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1168 return return_false_with_msg ("PHI results are different");
1170 size1
= gimple_phi_num_args (phi1
);
1171 size2
= gimple_phi_num_args (phi2
);
1174 return return_false ();
1176 for (i
= 0; i
< size1
; ++i
)
1178 t1
= gimple_phi_arg (phi1
, i
)->def
;
1179 t2
= gimple_phi_arg (phi2
, i
)->def
;
1181 if (!m_checker
->compare_operand (t1
, t2
))
1182 return return_false ();
1184 e1
= gimple_phi_arg_edge (phi1
, i
);
1185 e2
= gimple_phi_arg_edge (phi2
, i
);
1187 if (!m_checker
->compare_edge (e1
, e2
))
1188 return return_false ();
1197 /* Returns true if tree T can be compared as a handled component. */
1200 sem_function::icf_handled_component_p (tree t
)
1202 tree_code tc
= TREE_CODE (t
);
1204 return ((handled_component_p (t
))
1205 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
1206 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
1209 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1210 corresponds to TARGET. */
1213 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1218 if (bb_dict
->length () <= (unsigned)source
)
1219 bb_dict
->safe_grow_cleared (source
+ 1);
1221 if ((*bb_dict
)[source
] == 0)
1223 (*bb_dict
)[source
] = target
;
1227 return (*bb_dict
)[source
] == target
;
1230 /* Iterates all tree types in T1 and T2 and returns true if all types
1231 are compatible. If COMPARE_POLYMORPHIC is set to true,
1232 more strict comparison is executed. */
1235 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
1243 while (t1
!= NULL
&& t2
!= NULL
)
1245 tv1
= TREE_VALUE (t1
);
1246 tv2
= TREE_VALUE (t2
);
1248 tc1
= TREE_CODE (tv1
);
1249 tc2
= TREE_CODE (tv2
);
1251 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
1253 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
1255 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
1258 t1
= TREE_CHAIN (t1
);
1259 t2
= TREE_CHAIN (t2
);
1266 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1268 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1272 /* Constructor based on varpool node _NODE with computed hash _HASH.
1273 Bitmap STACK is used for memory allocation. */
1275 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1276 bitmap_obstack
*stack
): sem_item(VAR
,
1279 gcc_checking_assert (node
);
1280 gcc_checking_assert (get_node ());
1283 /* Returns true if the item equals to ITEM given as argument. */
1286 sem_variable::equals (sem_item
*item
,
1287 hash_map
<symtab_node
*, sem_item
*> & ARG_UNUSED (ignored_nodes
))
1289 gcc_assert (item
->type
== VAR
);
1291 sem_variable
*v
= static_cast<sem_variable
*>(item
);
1293 if (!ctor
|| !v
->ctor
)
1294 return return_false_with_msg ("ctor is missing for semantic variable");
1296 return sem_variable::equals (ctor
, v
->ctor
);
1299 /* Compares trees T1 and T2 for semantic equality. */
1302 sem_variable::equals (tree t1
, tree t2
)
1304 tree_code tc1
= TREE_CODE (t1
);
1305 tree_code tc2
= TREE_CODE (t2
);
1314 unsigned len1
= vec_safe_length (CONSTRUCTOR_ELTS (t1
));
1315 unsigned len2
= vec_safe_length (CONSTRUCTOR_ELTS (t2
));
1320 for (unsigned i
= 0; i
< len1
; i
++)
1321 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1
, i
)->value
,
1322 CONSTRUCTOR_ELT (t2
, i
)->value
)
1323 || CONSTRUCTOR_ELT (t1
, i
)->index
!= CONSTRUCTOR_ELT (t2
, i
)->index
)
1330 tree x1
= TREE_OPERAND (t1
, 0);
1331 tree x2
= TREE_OPERAND (t2
, 0);
1332 tree y1
= TREE_OPERAND (t1
, 1);
1333 tree y2
= TREE_OPERAND (t2
, 1);
1335 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1337 return return_false ();
1339 /* Type of the offset on MEM_REF does not matter. */
1340 return sem_variable::equals (x1
, x2
)
1341 && wi::to_offset (y1
) == wi::to_offset (y2
);
1346 tree op1
= TREE_OPERAND (t1
, 0);
1347 tree op2
= TREE_OPERAND (t2
, 0);
1348 return sem_variable::equals (op1
, op2
);
1356 return func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1358 && wi::to_offset (t1
) == wi::to_offset (t2
);
1362 return operand_equal_p (t1
, t2
, OEP_ONLY_CONST
);
1365 case POINTER_PLUS_EXPR
:
1367 tree x1
= TREE_OPERAND (t1
, 0);
1368 tree x2
= TREE_OPERAND (t2
, 0);
1369 tree y1
= TREE_OPERAND (t1
, 1);
1370 tree y2
= TREE_OPERAND (t2
, 1);
1372 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1375 return return_false_with_msg ("ERROR_MARK");
1377 return return_false_with_msg ("Unknown TREE code reached");
1381 /* Parser function that visits a varpool NODE. */
1384 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1386 tree decl
= node
->decl
;
1388 bool readonly
= TYPE_P (decl
) ? TYPE_READONLY (decl
) : TREE_READONLY (decl
);
1392 bool can_handle
= DECL_VIRTUAL_P (decl
)
1393 || flag_merge_constants
>= 2
1394 || (!TREE_ADDRESSABLE (decl
) && !node
->externally_visible
);
1396 if (!can_handle
|| DECL_EXTERNAL (decl
))
1399 tree ctor
= ctor_for_folding (decl
);
1403 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1410 /* References independent hash function. */
1413 sem_variable::get_hash (void)
1418 inchash::hash hstate
;
1420 hstate
.add_int (456346417);
1421 hstate
.add_int (TREE_CODE (ctor
));
1423 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
1425 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (ctor
));
1426 hstate
.add_int (length
);
1429 hash
= hstate
.end ();
1434 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1438 sem_variable::merge (sem_item
*alias_item
)
1440 gcc_assert (alias_item
->type
== VAR
);
1442 if (!sem_item::target_supports_symbol_aliases_p ())
1445 fprintf (dump_file
, "Not unifying; "
1446 "Symbol aliases are not supported by target\n\n");
1450 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1452 varpool_node
*original
= get_node ();
1453 varpool_node
*alias
= alias_var
->get_node ();
1454 bool original_discardable
= false;
1456 bool original_address_matters
= original
->address_matters_p ();
1457 bool alias_address_matters
= alias
->address_matters_p ();
1459 /* See if original is in a section that can be discarded if the main
1461 Also consider case where we have resolution info and we know that
1462 original's definition is not going to be used. In this case we can not
1463 create alias to original. */
1464 if (original
->can_be_discarded_p ()
1465 || (node
->resolution
!= LDPR_UNKNOWN
1466 && !decl_binds_to_current_def_p (node
->decl
)))
1467 original_discardable
= true;
1469 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1471 /* Constant pool machinery is not quite ready for aliases.
1472 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
1473 For LTO merging does not happen that is an important missing feature.
1474 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
1475 flag is dropped and non-local symbol name is assigned. */
1476 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
1477 || DECL_IN_CONSTANT_POOL (original
->decl
))
1481 "Not unifying; constant pool variables.\n\n");
1485 /* Do not attempt to mix functions from different user sections;
1486 we do not know what user intends with those. */
1487 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1488 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1489 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1494 "original and alias are in different sections.\n\n");
1498 /* We can not merge if address comparsion metters. */
1499 if (original_address_matters
&& alias_address_matters
1500 && flag_merge_constants
< 2)
1505 "adress of original and alias may be compared.\n\n");
1509 if (original_discardable
1510 && (!DECL_COMDAT_GROUP (original
->decl
)
1511 || (DECL_COMDAT_GROUP (original
->decl
)
1512 != DECL_COMDAT_GROUP (alias
->decl
))))
1515 fprintf (dump_file
, "Not unifying; alias cannot be created; "
1516 "target is discardable\n\n");
1522 gcc_assert (!original
->alias
);
1523 gcc_assert (!alias
->alias
);
1525 alias
->analyzed
= false;
1527 DECL_INITIAL (alias
->decl
) = NULL
;
1528 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1530 alias
->need_bounds_init
= false;
1531 alias
->remove_all_references ();
1532 if (TREE_ADDRESSABLE (alias
->decl
))
1533 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
1535 varpool_node::create_alias (alias_var
->decl
, decl
);
1536 alias
->resolve_alias (original
);
1539 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
1545 /* Dump symbol to FILE. */
1548 sem_variable::dump_to_file (FILE *file
)
1552 print_node (file
, "", decl
, 0);
1553 fprintf (file
, "\n\n");
1556 /* Iterates though a constructor and identifies tree references
1557 we are interested in semantic function equality. */
1560 sem_variable::parse_tree_refs (tree t
)
1562 switch (TREE_CODE (t
))
1566 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1568 for (unsigned i
= 0; i
< length
; i
++)
1569 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1576 tree op
= TREE_OPERAND (t
, 0);
1577 parse_tree_refs (op
);
1582 tree_refs
.safe_push (t
);
1590 unsigned int sem_item_optimizer::class_id
= 0;
1592 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1593 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1596 bitmap_obstack_initialize (&m_bmstack
);
1599 sem_item_optimizer::~sem_item_optimizer ()
1601 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1604 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1605 it
!= m_classes
.end (); ++it
)
1607 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1608 delete (*it
)->classes
[i
];
1610 (*it
)->classes
.release ();
1616 bitmap_obstack_release (&m_bmstack
);
1619 /* Write IPA ICF summary for symbols. */
1622 sem_item_optimizer::write_summary (void)
1624 unsigned int count
= 0;
1626 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1627 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1630 /* Calculate number of symbols to be serialized. */
1631 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1633 lsei_next_in_partition (&lsei
))
1635 symtab_node
*node
= lsei_node (lsei
);
1637 if (m_symtab_node_map
.get (node
))
1641 streamer_write_uhwi (ob
, count
);
1643 /* Process all of the symbols. */
1644 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1646 lsei_next_in_partition (&lsei
))
1648 symtab_node
*node
= lsei_node (lsei
);
1650 sem_item
**item
= m_symtab_node_map
.get (node
);
1654 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1655 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1657 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1661 streamer_write_char_stream (ob
->main_stream
, 0);
1662 produce_asm (ob
, NULL
);
1663 destroy_output_block (ob
);
1666 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1667 contains LEN bytes. */
1670 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1671 const char *data
, size_t len
)
1673 const lto_function_header
*header
=
1674 (const lto_function_header
*) data
;
1675 const int cfg_offset
= sizeof (lto_function_header
);
1676 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1677 const int string_offset
= main_offset
+ header
->main_size
;
1682 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1683 header
->main_size
, file_data
->mode_table
);
1686 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1687 header
->string_size
, vNULL
);
1689 count
= streamer_read_uhwi (&ib_main
);
1691 for (i
= 0; i
< count
; i
++)
1695 lto_symtab_encoder_t encoder
;
1697 index
= streamer_read_uhwi (&ib_main
);
1698 encoder
= file_data
->symtab_node_encoder
;
1699 node
= lto_symtab_encoder_deref (encoder
, index
);
1701 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1703 gcc_assert (node
->definition
);
1706 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1707 (void *) node
->decl
, node
->order
);
1709 if (is_a
<cgraph_node
*> (node
))
1711 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1713 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
1717 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
1719 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
1723 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
1725 lto_data_in_delete (data_in
);
1728 /* Read IPA IPA ICF summary for symbols. */
1731 sem_item_optimizer::read_summary (void)
1733 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1734 lto_file_decl_data
*file_data
;
1737 while ((file_data
= file_data_vec
[j
++]))
1740 const char *data
= lto_get_section_data (file_data
,
1741 LTO_section_ipa_icf
, NULL
, &len
);
1744 read_section (file_data
, data
, len
);
1748 /* Register callgraph and varpool hooks. */
1751 sem_item_optimizer::register_hooks (void)
1753 if (!m_cgraph_node_hooks
)
1754 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
1755 (&sem_item_optimizer::cgraph_removal_hook
, this);
1757 if (!m_varpool_node_hooks
)
1758 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
1759 (&sem_item_optimizer::varpool_removal_hook
, this);
1762 /* Unregister callgraph and varpool hooks. */
1765 sem_item_optimizer::unregister_hooks (void)
1767 if (m_cgraph_node_hooks
)
1768 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
1770 if (m_varpool_node_hooks
)
1771 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
1774 /* Adds a CLS to hashtable associated by hash value. */
1777 sem_item_optimizer::add_class (congruence_class
*cls
)
1779 gcc_assert (cls
->members
.length ());
1781 congruence_class_group
*group
= get_group_by_hash (
1782 cls
->members
[0]->get_hash (),
1783 cls
->members
[0]->type
);
1784 group
->classes
.safe_push (cls
);
1787 /* Gets a congruence class group based on given HASH value and TYPE. */
1789 congruence_class_group
*
1790 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
1792 congruence_class_group
*item
= XNEW (congruence_class_group
);
1796 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
1802 item
->classes
.create (1);
1809 /* Callgraph removal hook called for a NODE with a custom DATA. */
1812 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
1814 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1815 optimizer
->remove_symtab_node (node
);
1818 /* Varpool removal hook called for a NODE with a custom DATA. */
1821 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
1823 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1824 optimizer
->remove_symtab_node (node
);
1827 /* Remove symtab NODE triggered by symtab removal hooks. */
1830 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
1832 gcc_assert (!m_classes
.elements());
1834 m_removed_items_set
.add (node
);
1838 sem_item_optimizer::remove_item (sem_item
*item
)
1840 if (m_symtab_node_map
.get (item
->node
))
1841 m_symtab_node_map
.remove (item
->node
);
1845 /* Removes all callgraph and varpool nodes that are marked by symtab
1849 sem_item_optimizer::filter_removed_items (void)
1851 auto_vec
<sem_item
*> filtered
;
1853 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1855 sem_item
*item
= m_items
[i
];
1857 if (m_removed_items_set
.contains (item
->node
))
1863 if (item
->type
== FUNC
)
1865 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
1867 bool no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
1868 if (no_body_function
|| !opt_for_fn (item
->decl
, flag_ipa_icf_functions
)
1869 || DECL_CXX_CONSTRUCTOR_P (item
->decl
)
1870 || DECL_CXX_DESTRUCTOR_P (item
->decl
))
1873 filtered
.safe_push (item
);
1877 if (!flag_ipa_icf_variables
)
1880 filtered
.safe_push (item
);
1884 /* Clean-up of released semantic items. */
1887 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
1888 m_items
.safe_push (filtered
[i
]);
1891 /* Optimizer entry point. */
1894 sem_item_optimizer::execute (void)
1896 filter_removed_items ();
1897 unregister_hooks ();
1899 build_hash_based_classes ();
1902 fprintf (dump_file
, "Dump after hash based groups\n");
1903 dump_cong_classes ();
1905 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1906 m_items
[i
]->init_wpa ();
1910 subdivide_classes_by_equality (true);
1913 fprintf (dump_file
, "Dump after WPA based types groups\n");
1915 dump_cong_classes ();
1917 process_cong_reduction ();
1921 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
1923 dump_cong_classes ();
1925 parse_nonsingleton_classes ();
1926 subdivide_classes_by_equality ();
1929 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
1931 dump_cong_classes ();
1933 unsigned int prev_class_count
= m_classes_count
;
1935 process_cong_reduction ();
1936 dump_cong_classes ();
1938 merge_classes (prev_class_count
);
1940 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1941 symtab_node::dump_table (dump_file
);
1944 /* Function responsible for visiting all potential functions and
1945 read-only variables that can be merged. */
1948 sem_item_optimizer::parse_funcs_and_vars (void)
1952 if (flag_ipa_icf_functions
)
1953 FOR_EACH_DEFINED_FUNCTION (cnode
)
1955 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
1958 m_items
.safe_push (f
);
1959 m_symtab_node_map
.put (cnode
, f
);
1962 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
1964 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1965 f
->dump_to_file (dump_file
);
1968 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
1971 varpool_node
*vnode
;
1973 if (flag_ipa_icf_variables
)
1974 FOR_EACH_DEFINED_VARIABLE (vnode
)
1976 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
1980 m_items
.safe_push (v
);
1981 m_symtab_node_map
.put (vnode
, v
);
1986 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1989 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
1991 item
->index_in_class
= cls
->members
.length ();
1992 cls
->members
.safe_push (item
);
1996 /* Congruence classes are built by hash value. */
1999 sem_item_optimizer::build_hash_based_classes (void)
2001 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2003 sem_item
*item
= m_items
[i
];
2005 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
2008 if (!group
->classes
.length ())
2011 group
->classes
.safe_push (new congruence_class (class_id
++));
2014 add_item_to_class (group
->classes
[0], item
);
2018 /* Build references according to call graph. */
2021 sem_item_optimizer::build_graph (void)
2023 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2025 sem_item
*item
= m_items
[i
];
2026 m_symtab_node_map
.put (item
->node
, item
);
2029 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2031 sem_item
*item
= m_items
[i
];
2033 if (item
->type
== FUNC
)
2035 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2037 cgraph_edge
*e
= cnode
->callees
;
2040 sem_item
**slot
= m_symtab_node_map
.get (e
->callee
);
2042 item
->add_reference (*slot
);
2048 ipa_ref
*ref
= NULL
;
2049 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2051 sem_item
**slot
= m_symtab_node_map
.get (ref
->referred
);
2053 item
->add_reference (*slot
);
2058 /* Semantic items in classes having more than one element and initialized.
2059 In case of WPA, we load function body. */
2062 sem_item_optimizer::parse_nonsingleton_classes (void)
2064 unsigned int init_called_count
= 0;
2066 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2067 if (m_items
[i
]->cls
->members
.length () > 1)
2069 m_items
[i
]->init ();
2070 init_called_count
++;
2074 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2075 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2078 /* Equality function for semantic items is used to subdivide existing
2079 classes. If IN_WPA, fast equality function is invoked. */
2082 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2084 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2085 it
!= m_classes
.end (); ++it
)
2087 unsigned int class_count
= (*it
)->classes
.length ();
2089 for (unsigned i
= 0; i
< class_count
; i
++)
2091 congruence_class
*c
= (*it
)->classes
[i
];
2093 if (c
->members
.length() > 1)
2095 auto_vec
<sem_item
*> new_vector
;
2097 sem_item
*first
= c
->members
[0];
2098 new_vector
.safe_push (first
);
2100 unsigned class_split_first
= (*it
)->classes
.length ();
2102 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2104 sem_item
*item
= c
->members
[j
];
2106 bool equals
= in_wpa
? first
->equals_wpa (item
,
2107 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2110 new_vector
.safe_push (item
);
2113 bool integrated
= false;
2115 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2117 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2118 bool equals
= in_wpa
? x
->equals_wpa (item
,
2119 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2124 add_item_to_class ((*it
)->classes
[k
], item
);
2132 congruence_class
*c
= new congruence_class (class_id
++);
2134 add_item_to_class (c
, item
);
2136 (*it
)->classes
.safe_push (c
);
2141 // we replace newly created new_vector for the class we've just splitted
2142 c
->members
.release ();
2143 c
->members
.create (new_vector
.length ());
2145 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2146 add_item_to_class (c
, new_vector
[j
]);
2154 /* Subdivide classes by address references that members of the class
2155 reference. Example can be a pair of functions that have an address
2156 taken from a function. If these addresses are different the class
2160 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2162 unsigned newly_created_classes
= 0;
2164 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2165 it
!= m_classes
.end (); ++it
)
2167 unsigned int class_count
= (*it
)->classes
.length ();
2168 auto_vec
<congruence_class
*> new_classes
;
2170 for (unsigned i
= 0; i
< class_count
; i
++)
2172 congruence_class
*c
= (*it
)->classes
[i
];
2174 if (c
->members
.length() > 1)
2176 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2177 symbol_compare_hashmap_traits
> split_map
;
2179 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2181 sem_item
*source_node
= c
->members
[j
];
2183 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2185 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
);
2186 gcc_checking_assert (slot
);
2188 slot
->safe_push (source_node
);
2191 /* If the map contains more than one key, we have to split the map
2193 if (split_map
.elements () != 1)
2195 bool first_class
= true;
2197 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2198 symbol_compare_hashmap_traits
>::iterator it2
= split_map
.begin ();
2199 for (; it2
!= split_map
.end (); ++it2
)
2201 congruence_class
*new_cls
;
2202 new_cls
= new congruence_class (class_id
++);
2204 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2205 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2207 worklist_push (new_cls
);
2208 newly_created_classes
++;
2212 (*it
)->classes
[i
] = new_cls
;
2213 first_class
= false;
2217 new_classes
.safe_push (new_cls
);
2225 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2226 (*it
)->classes
.safe_push (new_classes
[i
]);
2229 return newly_created_classes
;
2232 /* Verify congruence classes if checking is enabled. */
2235 sem_item_optimizer::verify_classes (void)
2238 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2239 it
!= m_classes
.end (); ++it
)
2241 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2243 congruence_class
*cls
= (*it
)->classes
[i
];
2245 gcc_checking_assert (cls
);
2246 gcc_checking_assert (cls
->members
.length () > 0);
2248 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
2250 sem_item
*item
= cls
->members
[j
];
2252 gcc_checking_assert (item
);
2253 gcc_checking_assert (item
->cls
== cls
);
2255 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
2257 sem_usage_pair
*usage
= item
->usages
[k
];
2258 gcc_checking_assert (usage
->item
->index_in_class
<
2259 usage
->item
->cls
->members
.length ());
2267 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2268 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2269 but unused argument. */
2272 sem_item_optimizer::release_split_map (congruence_class
* const &,
2273 bitmap
const &b
, traverse_split_pair
*)
2282 /* Process split operation for a class given as pointer CLS_PTR,
2283 where bitmap B splits congruence class members. DATA is used
2284 as argument of split pair. */
2287 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2288 bitmap
const &b
, traverse_split_pair
*pair
)
2290 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2291 const congruence_class
*splitter_cls
= pair
->cls
;
2293 /* If counted bits are greater than zero and less than the number of members
2294 a group will be splitted. */
2295 unsigned popcount
= bitmap_count_bits (b
);
2297 if (popcount
> 0 && popcount
< cls
->members
.length ())
2299 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
2301 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2303 int target
= bitmap_bit_p (b
, i
);
2304 congruence_class
*tc
= newclasses
[target
];
2306 add_item_to_class (tc
, cls
->members
[i
]);
2309 #ifdef ENABLE_CHECKING
2310 for (unsigned int i
= 0; i
< 2; i
++)
2311 gcc_checking_assert (newclasses
[i
]->members
.length ());
2314 if (splitter_cls
== cls
)
2315 optimizer
->splitter_class_removed
= true;
2317 /* Remove old class from worklist if presented. */
2318 bool in_worklist
= cls
->in_worklist
;
2321 cls
->in_worklist
= false;
2323 congruence_class_group g
;
2324 g
.hash
= cls
->members
[0]->get_hash ();
2325 g
.type
= cls
->members
[0]->type
;
2327 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
2329 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2330 if (slot
->classes
[i
] == cls
)
2332 slot
->classes
.ordered_remove (i
);
2336 /* New class will be inserted and integrated to work list. */
2337 for (unsigned int i
= 0; i
< 2; i
++)
2338 optimizer
->add_class (newclasses
[i
]);
2340 /* Two classes replace one, so that increment just by one. */
2341 optimizer
->m_classes_count
++;
2343 /* If OLD class was presented in the worklist, we remove the class
2344 and replace it will both newly created classes. */
2346 for (unsigned int i
= 0; i
< 2; i
++)
2347 optimizer
->worklist_push (newclasses
[i
]);
2348 else /* Just smaller class is inserted. */
2350 unsigned int smaller_index
= newclasses
[0]->members
.length () <
2351 newclasses
[1]->members
.length () ?
2353 optimizer
->worklist_push (newclasses
[smaller_index
]);
2356 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2358 fprintf (dump_file
, " congruence class splitted:\n");
2359 cls
->dump (dump_file
, 4);
2361 fprintf (dump_file
, " newly created groups:\n");
2362 for (unsigned int i
= 0; i
< 2; i
++)
2363 newclasses
[i
]->dump (dump_file
, 4);
2366 /* Release class if not presented in work list. */
2375 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2376 Bitmap stack BMSTACK is used for bitmap allocation. */
2379 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2382 hash_map
<congruence_class
*, bitmap
> split_map
;
2384 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2386 sem_item
*item
= cls
->members
[i
];
2388 /* Iterate all usages that have INDEX as usage of the item. */
2389 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2391 sem_usage_pair
*usage
= item
->usages
[j
];
2393 if (usage
->index
!= index
)
2396 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2401 b
= BITMAP_ALLOC (&m_bmstack
);
2402 split_map
.put (usage
->item
->cls
, b
);
2408 gcc_checking_assert (usage
->item
->cls
);
2409 gcc_checking_assert (usage
->item
->index_in_class
<
2410 usage
->item
->cls
->members
.length ());
2413 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2417 traverse_split_pair pair
;
2418 pair
.optimizer
= this;
2421 splitter_class_removed
= false;
2423 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2425 /* Bitmap clean-up. */
2427 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2430 /* Every usage of a congruence class CLS is a candidate that can split the
2431 collection of classes. Bitmap stack BMSTACK is used for bitmap
2435 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2440 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2442 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2443 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2445 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2447 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2448 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2451 do_congruence_step_for_index (cls
, i
);
2453 if (splitter_class_removed
)
2457 BITMAP_FREE (usage
);
2460 /* Adds a newly created congruence class CLS to worklist. */
2463 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2465 /* Return if the class CLS is already presented in work list. */
2466 if (cls
->in_worklist
)
2469 cls
->in_worklist
= true;
2470 worklist
.push_back (cls
);
2473 /* Pops a class from worklist. */
2476 sem_item_optimizer::worklist_pop (void)
2478 congruence_class
*cls
;
2480 while (!worklist
.empty ())
2482 cls
= worklist
.front ();
2483 worklist
.pop_front ();
2484 if (cls
->in_worklist
)
2486 cls
->in_worklist
= false;
2492 /* Work list item was already intended to be removed.
2493 The only reason for doing it is to split a class.
2494 Thus, the class CLS is deleted. */
2502 /* Iterative congruence reduction function. */
2505 sem_item_optimizer::process_cong_reduction (void)
2507 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2508 it
!= m_classes
.end (); ++it
)
2509 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2510 if ((*it
)->classes
[i
]->is_class_used ())
2511 worklist_push ((*it
)->classes
[i
]);
2514 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2515 (unsigned long) worklist
.size ());
2517 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2518 fprintf (dump_file
, "Congruence class reduction\n");
2520 congruence_class
*cls
;
2522 /* Process complete congruence reduction. */
2523 while ((cls
= worklist_pop ()) != NULL
)
2524 do_congruence_step (cls
);
2526 /* Subdivide newly created classes according to references. */
2527 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
2530 fprintf (dump_file
, "Address reference subdivision created: %u "
2531 "new classes.\n", new_classes
);
2534 /* Debug function prints all informations about congruence classes. */
2537 sem_item_optimizer::dump_cong_classes (void)
2543 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2544 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2546 /* Histogram calculation. */
2547 unsigned int max_index
= 0;
2548 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2550 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2551 it
!= m_classes
.end (); ++it
)
2553 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2555 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2563 "Class size histogram [num of members]: number of classe number of classess\n");
2565 for (unsigned int i
= 0; i
<= max_index
; i
++)
2567 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2569 fprintf (dump_file
, "\n\n");
2572 if (dump_flags
& TDF_DETAILS
)
2573 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2574 it
!= m_classes
.end (); ++it
)
2576 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2578 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2580 (*it
)->classes
[i
]->dump (dump_file
, 4);
2582 if(i
< (*it
)->classes
.length () - 1)
2583 fprintf (dump_file
, " ");
2590 /* After reduction is done, we can declare all items in a group
2591 to be equal. PREV_CLASS_COUNT is start number of classes
2592 before reduction. */
2595 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2597 unsigned int item_count
= m_items
.length ();
2598 unsigned int class_count
= m_classes_count
;
2599 unsigned int equal_items
= item_count
- class_count
;
2601 unsigned int non_singular_classes_count
= 0;
2602 unsigned int non_singular_classes_sum
= 0;
2604 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2605 it
!= m_classes
.end (); ++it
)
2606 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2608 congruence_class
*c
= (*it
)->classes
[i
];
2609 if (c
->members
.length () > 1)
2611 non_singular_classes_count
++;
2612 non_singular_classes_sum
+= c
->members
.length ();
2618 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2619 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2620 prev_class_count
, class_count
);
2621 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2622 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2623 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2624 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2625 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2626 non_singular_classes_count
: 0.0f
,
2627 non_singular_classes_count
);
2628 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2629 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2630 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2633 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2634 it
!= m_classes
.end (); ++it
)
2635 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2637 congruence_class
*c
= (*it
)->classes
[i
];
2639 if (c
->members
.length () == 1)
2642 gcc_assert (c
->members
.length ());
2644 sem_item
*source
= c
->members
[0];
2646 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2648 sem_item
*alias
= c
->members
[j
];
2652 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2653 source
->name (), alias
->name ());
2654 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2655 source
->asm_name (), alias
->asm_name ());
2658 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
2662 "Merge operation is skipped due to no_icf "
2668 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2670 source
->dump_to_file (dump_file
);
2671 alias
->dump_to_file (dump_file
);
2674 source
->merge (alias
);
2679 /* Dump function prints all class members to a FILE with an INDENT. */
2682 congruence_class::dump (FILE *file
, unsigned int indent
) const
2684 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2685 id
, members
[0]->get_hash (), members
.length ());
2687 FPUTS_SPACES (file
, indent
+ 2, "");
2688 for (unsigned i
= 0; i
< members
.length (); i
++)
2689 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2690 members
[i
]->node
->order
);
2692 fprintf (file
, "\n");
2695 /* Returns true if there's a member that is used from another group. */
2698 congruence_class::is_class_used (void)
2700 for (unsigned int i
= 0; i
< members
.length (); i
++)
2701 if (members
[i
]->usages
.length ())
2707 /* Initialization and computation of symtab node hash, there data
2708 are propagated later on. */
2710 static sem_item_optimizer
*optimizer
= NULL
;
2712 /* Generate pass summary for IPA ICF pass. */
2715 ipa_icf_generate_summary (void)
2718 optimizer
= new sem_item_optimizer ();
2720 optimizer
->register_hooks ();
2721 optimizer
->parse_funcs_and_vars ();
2724 /* Write pass summary for IPA ICF pass. */
2727 ipa_icf_write_summary (void)
2729 gcc_assert (optimizer
);
2731 optimizer
->write_summary ();
2734 /* Read pass summary for IPA ICF pass. */
2737 ipa_icf_read_summary (void)
2740 optimizer
= new sem_item_optimizer ();
2742 optimizer
->read_summary ();
2743 optimizer
->register_hooks ();
2746 /* Semantic equality exection function. */
2749 ipa_icf_driver (void)
2751 gcc_assert (optimizer
);
2753 optimizer
->execute ();
2761 const pass_data pass_data_ipa_icf
=
2763 IPA_PASS
, /* type */
2765 OPTGROUP_IPA
, /* optinfo_flags */
2766 TV_IPA_ICF
, /* tv_id */
2767 0, /* properties_required */
2768 0, /* properties_provided */
2769 0, /* properties_destroyed */
2770 0, /* todo_flags_start */
2771 0, /* todo_flags_finish */
2774 class pass_ipa_icf
: public ipa_opt_pass_d
2777 pass_ipa_icf (gcc::context
*ctxt
)
2778 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
2779 ipa_icf_generate_summary
, /* generate_summary */
2780 ipa_icf_write_summary
, /* write_summary */
2781 ipa_icf_read_summary
, /* read_summary */
2783 write_optimization_summary */
2785 read_optimization_summary */
2786 NULL
, /* stmt_fixup */
2787 0, /* function_transform_todo_flags_start */
2788 NULL
, /* function_transform */
2789 NULL
) /* variable_transform */
2792 /* opt_pass methods: */
2793 virtual bool gate (function
*)
2795 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
2798 virtual unsigned int execute (function
*)
2800 return ipa_icf_driver();
2802 }; // class pass_ipa_icf
2804 } // ipa_icf namespace
2807 make_pass_ipa_icf (gcc::context
*ctxt
)
2809 return new ipa_icf::pass_ipa_icf (ctxt
);