1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2015 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
57 #include "coretypes.h"
61 #include "double-int.h"
69 #include "fold-const.h"
72 #include "hard-reg-set.h"
74 #include "dominance.h"
76 #include "basic-block.h"
77 #include "tree-ssa-alias.h"
78 #include "internal-fn.h"
79 #include "gimple-expr.h"
85 #include "statistics.h"
87 #include "fixed-value.h"
88 #include "insn-config.h"
97 #include "gimple-iterator.h"
98 #include "gimple-ssa.h"
100 #include "tree-phinodes.h"
101 #include "stringpool.h"
102 #include "tree-ssanames.h"
103 #include "tree-dfa.h"
104 #include "tree-pass.h"
105 #include "gimple-pretty-print.h"
106 #include "hash-map.h"
107 #include "plugin-api.h"
110 #include "alloc-pool.h"
111 #include "symbol-summary.h"
112 #include "ipa-prop.h"
113 #include "ipa-inline.h"
116 #include "hash-table.h"
117 #include "coverage.h"
119 #include "print-tree.h"
120 #include "lto-streamer.h"
121 #include "data-streamer.h"
122 #include "ipa-utils.h"
123 #include "ipa-icf-gimple.h"
125 #include "stor-layout.h"
127 using namespace ipa_icf_gimple
;
133 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
135 m_references
.create (0);
136 m_interposables
.create (0);
140 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
143 for (unsigned i
= 0; i
< node
->num_references (); i
++)
145 ref
= node
->iterate_reference (i
, ref
);
146 if (ref
->address_matters_p ())
147 m_references
.safe_push (ref
->referred
);
149 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
151 if (ref
->address_matters_p ())
152 m_references
.safe_push (ref
->referred
);
154 m_interposables
.safe_push (ref
->referred
);
158 if (is_a
<cgraph_node
*> (node
))
160 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
162 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
163 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
164 m_interposables
.safe_push (e
->callee
);
168 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
170 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
171 item (_item
), index (_index
)
175 /* Semantic item constructor for a node of _TYPE, where STACK is used
176 for bitmap memory allocation. */
178 sem_item::sem_item (sem_item_type _type
,
179 bitmap_obstack
*stack
): type(_type
), hash(0)
184 /* Semantic item constructor for a node of _TYPE, where STACK is used
185 for bitmap memory allocation. The item is based on symtab node _NODE
186 with computed _HASH. */
188 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
189 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
190 node (_node
), hash (_hash
)
196 /* Add reference to a semantic TARGET. */
199 sem_item::add_reference (sem_item
*target
)
201 refs
.safe_push (target
);
202 unsigned index
= refs
.length ();
203 target
->usages
.safe_push (new sem_usage_pair(this, index
));
204 bitmap_set_bit (target
->usage_index_bitmap
, index
);
205 refs_set
.add (target
->node
);
208 /* Initialize internal data structures. Bitmap STACK is used for
209 bitmap memory allocation process. */
212 sem_item::setup (bitmap_obstack
*stack
)
214 gcc_checking_assert (node
);
217 tree_refs
.create (0);
219 usage_index_bitmap
= BITMAP_ALLOC (stack
);
222 sem_item::~sem_item ()
224 for (unsigned i
= 0; i
< usages
.length (); i
++)
228 tree_refs
.release ();
231 BITMAP_FREE (usage_index_bitmap
);
234 /* Dump function for debugging purpose. */
237 sem_item::dump (void)
241 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
242 name(), node
->order
, (void *) node
->decl
);
243 fprintf (dump_file
, " hash: %u\n", get_hash ());
244 fprintf (dump_file
, " references: ");
246 for (unsigned i
= 0; i
< refs
.length (); i
++)
247 fprintf (dump_file
, "%s%s ", refs
[i
]->name (),
248 i
< refs
.length() - 1 ? "," : "");
250 fprintf (dump_file
, "\n");
254 /* Return true if target supports alias symbols. */
257 sem_item::target_supports_symbol_aliases_p (void)
259 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
266 /* Semantic function constructor that uses STACK as bitmap memory stack. */
268 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
269 m_checker (NULL
), m_compared_func (NULL
)
271 arg_types
.create (0);
273 bb_sorted
.create (0);
276 /* Constructor based on callgraph node _NODE with computed hash _HASH.
277 Bitmap STACK is used for memory allocation. */
278 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
279 bitmap_obstack
*stack
):
280 sem_item (FUNC
, node
, hash
, stack
),
281 m_checker (NULL
), m_compared_func (NULL
)
283 arg_types
.create (0);
285 bb_sorted
.create (0);
288 sem_function::~sem_function ()
290 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
291 delete (bb_sorted
[i
]);
293 arg_types
.release ();
295 bb_sorted
.release ();
298 /* Calculates hash value based on a BASIC_BLOCK. */
301 sem_function::get_bb_hash (const sem_bb
*basic_block
)
303 inchash::hash hstate
;
305 hstate
.add_int (basic_block
->nondbg_stmt_count
);
306 hstate
.add_int (basic_block
->edge_count
);
308 return hstate
.end ();
311 /* References independent hash function. */
314 sem_function::get_hash (void)
318 inchash::hash hstate
;
319 hstate
.add_int (177454); /* Random number for function type. */
321 hstate
.add_int (arg_count
);
322 hstate
.add_int (cfg_checksum
);
323 hstate
.add_int (gcode_hash
);
325 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
326 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
328 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
329 hstate
.add_int (bb_sizes
[i
]);
331 hash
= hstate
.end ();
337 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
338 point to a same function. Comparison can be skipped if IGNORED_NODES
339 contains these nodes. ADDRESS indicate if address is taken. */
342 sem_item::compare_cgraph_references (
343 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
344 symtab_node
*n1
, symtab_node
*n2
, bool address
)
346 enum availability avail1
, avail2
;
348 if (address
&& n1
->equal_address_to (n2
) == 1)
350 if (!address
&& n1
->semantically_equivalent_p (n2
))
353 n1
= n1
->ultimate_alias_target (&avail1
);
354 n2
= n2
->ultimate_alias_target (&avail2
);
356 if (avail1
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
357 && avail2
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
360 return return_false_with_msg ("different references");
363 /* If cgraph edges E1 and E2 are indirect calls, verify that
364 ECF flags are the same. */
366 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
368 if (e1
->indirect_info
&& e2
->indirect_info
)
370 int e1_flags
= e1
->indirect_info
->ecf_flags
;
371 int e2_flags
= e2
->indirect_info
->ecf_flags
;
373 if (e1_flags
!= e2_flags
)
374 return return_false_with_msg ("ICF flags are different");
376 else if (e1
->indirect_info
|| e2
->indirect_info
)
382 /* Fast equality function based on knowledge known in WPA. */
385 sem_function::equals_wpa (sem_item
*item
,
386 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
388 gcc_assert (item
->type
== FUNC
);
390 m_compared_func
= static_cast<sem_function
*> (item
);
392 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
393 return return_false_with_msg ("different number of arguments");
395 /* Checking types of arguments. */
396 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
398 /* This guard is here for function pointer with attributes (pr59927.c). */
399 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
400 return return_false_with_msg ("NULL argument type");
402 /* Polymorphic comparison is executed just for non-leaf functions. */
403 bool is_not_leaf
= get_node ()->callees
!= NULL
404 || get_node ()->indirect_calls
!= NULL
;
406 if (!func_checker::compatible_types_p (arg_types
[i
],
407 m_compared_func
->arg_types
[i
],
408 is_not_leaf
, i
== 0))
409 return return_false_with_msg ("argument type is different");
412 /* Result type checking. */
413 if (!func_checker::compatible_types_p (result_type
,
414 m_compared_func
->result_type
))
415 return return_false_with_msg ("result types are different");
417 if (node
->num_references () != item
->node
->num_references ())
418 return return_false_with_msg ("different number of references");
420 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
421 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
423 item
->node
->iterate_reference (i
, ref2
);
425 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
,
427 ref
->address_matters_p ()))
431 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
432 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
436 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
,
440 e1
= e1
->next_callee
;
441 e2
= e2
->next_callee
;
445 return return_false_with_msg ("different number of edges");
450 /* Returns true if the item equals to ITEM given as argument. */
453 sem_function::equals (sem_item
*item
,
454 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
456 gcc_assert (item
->type
== FUNC
);
457 bool eq
= equals_private (item
, ignored_nodes
);
459 if (m_checker
!= NULL
)
465 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
467 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
468 name(), item
->name (), node
->order
, item
->node
->order
, asm_name (),
469 item
->asm_name (), eq
? "true" : "false");
474 /* Processes function equality comparison. */
477 sem_function::equals_private (sem_item
*item
,
478 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
480 if (item
->type
!= FUNC
)
483 basic_block bb1
, bb2
;
485 edge_iterator ei1
, ei2
;
489 m_compared_func
= static_cast<sem_function
*> (item
);
491 gcc_assert (decl
!= item
->decl
);
493 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
494 || edge_count
!= m_compared_func
->edge_count
495 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
496 return return_false ();
498 if (!equals_wpa (item
, ignored_nodes
))
501 /* Checking function TARGET and OPTIMIZATION flags. */
502 cl_target_option
*tar1
= target_opts_for_fn (decl
);
503 cl_target_option
*tar2
= target_opts_for_fn (m_compared_func
->decl
);
505 if (tar1
!= NULL
&& tar2
!= NULL
)
507 if (!cl_target_option_eq (tar1
, tar2
))
509 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
511 fprintf (dump_file
, "target flags difference");
512 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
515 return return_false_with_msg ("Target flags are different");
518 else if (tar1
!= NULL
|| tar2
!= NULL
)
519 return return_false_with_msg ("Target flags are different");
521 cl_optimization
*opt1
= opts_for_fn (decl
);
522 cl_optimization
*opt2
= opts_for_fn (m_compared_func
->decl
);
524 if (opt1
!= NULL
&& opt2
!= NULL
)
526 if (memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
528 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
530 fprintf (dump_file
, "optimization flags difference");
531 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
534 return return_false_with_msg ("optimization flags are different");
537 else if (opt1
!= NULL
|| opt2
!= NULL
)
538 return return_false_with_msg ("optimization flags are different");
540 /* Checking function arguments. */
541 tree decl1
= DECL_ATTRIBUTES (decl
);
542 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
544 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
545 compare_polymorphic_p (),
548 &m_compared_func
->refs_set
);
552 return return_false ();
554 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
555 return return_false ();
557 tree attr_value1
= TREE_VALUE (decl1
);
558 tree attr_value2
= TREE_VALUE (decl2
);
560 if (attr_value1
&& attr_value2
)
562 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
563 TREE_VALUE (attr_value2
));
565 return return_false_with_msg ("attribute values are different");
567 else if (!attr_value1
&& !attr_value2
)
570 return return_false ();
572 decl1
= TREE_CHAIN (decl1
);
573 decl2
= TREE_CHAIN (decl2
);
577 return return_false();
580 for (arg1
= DECL_ARGUMENTS (decl
),
581 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
582 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
583 if (!m_checker
->compare_decl (arg1
, arg2
))
584 return return_false ();
586 /* Fill-up label dictionary. */
587 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
589 m_checker
->parse_labels (bb_sorted
[i
]);
590 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
593 /* Checking all basic blocks. */
594 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
595 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
596 return return_false();
598 dump_message ("All BBs are equal\n");
600 auto_vec
<int> bb_dict
;
602 /* Basic block edges check. */
603 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
605 bb1
= bb_sorted
[i
]->bb
;
606 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
608 ei2
= ei_start (bb2
->preds
);
610 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
614 if (e1
->flags
!= e2
->flags
)
615 return return_false_with_msg ("flags comparison returns false");
617 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
618 return return_false_with_msg ("edge comparison returns false");
620 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
621 return return_false_with_msg ("BB comparison returns false");
623 if (!m_checker
->compare_edge (e1
, e2
))
624 return return_false_with_msg ("edge comparison returns false");
630 /* Basic block PHI nodes comparison. */
631 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
632 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
633 return return_false_with_msg ("PHI node comparison returns false");
635 /* Compare special function DECL attributes. */
636 if (DECL_FUNCTION_PERSONALITY (decl
) != DECL_FUNCTION_PERSONALITY (item
->decl
))
637 return return_false_with_msg ("function personalities are different");
639 if (DECL_DISREGARD_INLINE_LIMITS (decl
) != DECL_DISREGARD_INLINE_LIMITS (item
->decl
))
640 return return_false_with_msg ("DECL_DISREGARD_INLINE_LIMITS are different");
642 if (DECL_DECLARED_INLINE_P (decl
) != DECL_DECLARED_INLINE_P (item
->decl
))
643 return return_false_with_msg ("inline attributes are different");
645 if (DECL_IS_OPERATOR_NEW (decl
) != DECL_IS_OPERATOR_NEW (item
->decl
))
646 return return_false_with_msg ("operator new flags are different");
648 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
649 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
650 return return_false_with_msg ("intrument function entry exit "
651 "attributes are different");
653 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
654 return return_false_with_msg ("no stack limit attributes are different");
656 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
657 return return_false_with_msg ("decl_or_type flags are different");
662 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
663 Helper for call_for_symbol_thunks_and_aliases. */
666 set_local (cgraph_node
*node
, void *data
)
668 node
->local
.local
= data
!= NULL
;
672 /* TREE_ADDRESSABLE of NODE to true.
673 Helper for call_for_symbol_thunks_and_aliases. */
676 set_addressable (varpool_node
*node
, void *)
678 TREE_ADDRESSABLE (node
->decl
) = 1;
682 /* Clear DECL_RTL of NODE.
683 Helper for call_for_symbol_thunks_and_aliases. */
686 clear_decl_rtl (symtab_node
*node
, void *)
688 SET_DECL_RTL (node
->decl
, NULL
);
692 /* Redirect all callers of N and its aliases to TO. Remove aliases if
693 possible. Return number of redirections made. */
696 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
700 cgraph_edge
*e
= n
->callers
;
704 /* Redirecting thunks to interposable symbols or symbols in other sections
705 may not be supported by target output code. Play safe for now and
706 punt on redirection. */
707 if (!e
->caller
->thunk
.thunk_p
)
709 struct cgraph_edge
*nexte
= e
->next_caller
;
710 e
->redirect_callee (to
);
717 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
719 bool removed
= false;
720 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
722 if ((DECL_COMDAT_GROUP (n
->decl
)
723 && (DECL_COMDAT_GROUP (n
->decl
)
724 == DECL_COMDAT_GROUP (n_alias
->decl
)))
725 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
726 && n
->get_availability () > AVAIL_INTERPOSABLE
))
728 nredirected
+= redirect_all_callers (n_alias
, to
);
729 if (n_alias
->can_remove_if_no_direct_calls_p ()
730 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
732 && !n_alias
->has_aliases_p ())
741 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
745 sem_function::merge (sem_item
*alias_item
)
747 gcc_assert (alias_item
->type
== FUNC
);
749 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
751 cgraph_node
*original
= get_node ();
752 cgraph_node
*local_original
= NULL
;
753 cgraph_node
*alias
= alias_func
->get_node ();
755 bool create_wrapper
= false;
756 bool create_alias
= false;
757 bool redirect_callers
= false;
760 bool original_discardable
= false;
761 bool original_discarded
= false;
763 bool original_address_matters
= original
->address_matters_p ();
764 bool alias_address_matters
= alias
->address_matters_p ();
766 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
767 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
772 "DECL_NO_INLINE_WARNING mismatch.\n\n");
776 /* Do not attempt to mix functions from different user sections;
777 we do not know what user intends with those. */
778 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
779 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
780 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
785 "original and alias are in different sections.\n\n");
789 /* See if original is in a section that can be discarded if the main
790 symbol is not used. */
792 if (original
->can_be_discarded_p ())
793 original_discardable
= true;
794 /* Also consider case where we have resolution info and we know that
795 original's definition is not going to be used. In this case we can not
796 create alias to original. */
797 if (node
->resolution
!= LDPR_UNKNOWN
798 && !decl_binds_to_current_def_p (node
->decl
))
799 original_discardable
= original_discarded
= true;
801 /* Creating a symtab alias is the optimal way to merge.
802 It however can not be used in the following cases:
804 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
805 2) if ORIGINAL is in a section that may be discarded by linker or if
806 it is an external functions where we can not create an alias
807 (ORIGINAL_DISCARDABLE)
808 3) if target do not support symbol aliases.
809 4) original and alias lie in different comdat groups.
811 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
812 and/or redirect all callers from ALIAS to ORIGINAL. */
813 if ((original_address_matters
&& alias_address_matters
)
814 || (original_discardable
815 && (!DECL_COMDAT_GROUP (alias
->decl
)
816 || (DECL_COMDAT_GROUP (alias
->decl
)
817 != DECL_COMDAT_GROUP (original
->decl
))))
818 || original_discarded
819 || !sem_item::target_supports_symbol_aliases_p ()
820 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
822 /* First see if we can produce wrapper. */
824 /* Do not turn function in one comdat group into wrapper to another
825 comdat group. Other compiler producing the body of the
826 another comdat group may make opossite decision and with unfortunate
827 linker choices this may close a loop. */
828 if (DECL_COMDAT_GROUP (original
->decl
) && DECL_COMDAT_GROUP (alias
->decl
)
829 && (DECL_COMDAT_GROUP (alias
->decl
)
830 != DECL_COMDAT_GROUP (original
->decl
)))
834 "Wrapper cannot be created because of COMDAT\n");
836 else if (DECL_STATIC_CHAIN (alias
->decl
))
840 "Can not create wrapper of nested functions.\n");
842 /* TODO: We can also deal with variadic functions never calling
844 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
848 "can not create wrapper of stdarg function.\n");
850 else if (inline_summaries
851 && inline_summaries
->get (alias
)->self_size
<= 2)
854 fprintf (dump_file
, "Wrapper creation is not "
855 "profitable (function is too small).\n");
857 /* If user paid attention to mark function noinline, assume it is
858 somewhat special and do not try to turn it into a wrapper that can
859 not be undone by inliner. */
860 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
863 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
866 create_wrapper
= true;
868 /* We can redirect local calls in the case both alias and orignal
869 are not interposable. */
871 = alias
->get_availability () > AVAIL_INTERPOSABLE
872 && original
->get_availability () > AVAIL_INTERPOSABLE
873 && !alias
->instrumented_version
;
875 if (!redirect_callers
&& !create_wrapper
)
878 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
879 "produce wrapper\n\n");
883 /* Work out the symbol the wrapper should call.
884 If ORIGINAL is interposable, we need to call a local alias.
885 Also produce local alias (if possible) as an optimization.
887 Local aliases can not be created inside comdat groups because that
888 prevents inlining. */
889 if (!original_discardable
&& !original
->get_comdat_group ())
892 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
894 && original
->get_availability () > AVAIL_INTERPOSABLE
)
895 local_original
= original
;
897 /* If we can not use local alias, fallback to the original
899 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
900 local_original
= original
;
902 /* If original is COMDAT local, we can not really redirect calls outside
903 of its comdat group to it. */
904 if (original
->comdat_local_p ())
905 redirect_callers
= false;
909 fprintf (dump_file
, "Not unifying; "
910 "can not produce local alias.\n\n");
914 if (!redirect_callers
&& !create_wrapper
)
917 fprintf (dump_file
, "Not unifying; "
918 "can not redirect callers nor produce a wrapper\n\n");
922 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
924 && !alias
->can_remove_if_no_direct_calls_p ())
927 fprintf (dump_file
, "Not unifying; can not make wrapper and "
928 "function has other uses than direct calls\n\n");
935 if (redirect_callers
)
937 int nredirected
= redirect_all_callers (alias
, local_original
);
941 alias
->icf_merged
= true;
942 local_original
->icf_merged
= true;
944 if (dump_file
&& nredirected
)
945 fprintf (dump_file
, "%i local calls have been "
946 "redirected.\n", nredirected
);
949 /* If all callers was redirected, do not produce wrapper. */
950 if (alias
->can_remove_if_no_direct_calls_p ()
951 && !alias
->has_aliases_p ())
953 create_wrapper
= false;
956 gcc_assert (!create_alias
);
958 else if (create_alias
)
960 alias
->icf_merged
= true;
962 /* Remove the function's body. */
963 ipa_merge_profiles (original
, alias
);
964 alias
->release_body (true);
966 /* Notice global symbol possibly produced RTL. */
967 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
970 /* Create the alias. */
971 cgraph_node::create_alias (alias_func
->decl
, decl
);
972 alias
->resolve_alias (original
);
974 original
->call_for_symbol_thunks_and_aliases
975 (set_local
, (void *)(size_t) original
->local_p (), true);
978 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
982 gcc_assert (!create_alias
);
983 alias
->icf_merged
= true;
984 local_original
->icf_merged
= true;
986 ipa_merge_profiles (local_original
, alias
, true);
987 alias
->create_wrapper (local_original
);
990 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
993 /* It's possible that redirection can hit thunks that block
994 redirection opportunities. */
995 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
996 original
->icf_merged
= true;
998 /* Inform the inliner about cross-module merging. */
999 if ((original
->lto_file_data
|| alias
->lto_file_data
)
1000 && original
->lto_file_data
!= alias
->lto_file_data
)
1001 local_original
->merged
= original
->merged
= true;
1005 ipa_merge_profiles (original
, alias
);
1006 alias
->release_body ();
1008 alias
->body_removed
= true;
1009 alias
->icf_merged
= true;
1011 fprintf (dump_file
, "Unified; Function body was removed.\n");
1017 /* Semantic item initialization function. */
1020 sem_function::init (void)
1023 get_node ()->get_untransformed_body ();
1025 tree fndecl
= node
->decl
;
1026 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1029 gcc_assert (SSANAMES (func
));
1031 ssa_names_size
= SSANAMES (func
)->length ();
1035 region_tree
= func
->eh
->region_tree
;
1037 /* iterating all function arguments. */
1038 arg_count
= count_formal_params (fndecl
);
1040 edge_count
= n_edges_for_fn (func
);
1041 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1043 inchash::hash hstate
;
1046 FOR_EACH_BB_FN (bb
, func
)
1048 unsigned nondbg_stmt_count
= 0;
1051 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1053 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1056 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1059 gimple stmt
= gsi_stmt (gsi
);
1061 if (gimple_code (stmt
) != GIMPLE_DEBUG
1062 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1064 hash_stmt (stmt
, hstate
);
1065 nondbg_stmt_count
++;
1069 gcode_hash
= hstate
.end ();
1070 bb_sizes
.safe_push (nondbg_stmt_count
);
1072 /* Inserting basic block to hash table. */
1073 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1074 EDGE_COUNT (bb
->preds
)
1075 + EDGE_COUNT (bb
->succs
));
1077 bb_sorted
.safe_push (semantic_bb
);
1083 /* Accumulate to HSTATE a hash of expression EXP.
1084 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1085 and DECL equality classes. */
1088 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1090 if (exp
== NULL_TREE
)
1092 hstate
.merge_hash (0);
1096 /* Handled component can be matched in a cureful way proving equivalence
1097 even if they syntactically differ. Just skip them. */
1099 while (handled_component_p (exp
))
1100 exp
= TREE_OPERAND (exp
, 0);
1102 enum tree_code code
= TREE_CODE (exp
);
1103 hstate
.add_int (code
);
1107 /* Use inchash::add_expr for everything that is LTO stable. */
1115 inchash::add_expr (exp
, hstate
);
1119 unsigned HOST_WIDE_INT idx
;
1122 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1124 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1126 add_expr (value
, hstate
);
1131 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1137 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1140 case POINTER_PLUS_EXPR
:
1143 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1144 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1148 inchash::hash one
, two
;
1149 add_expr (TREE_OPERAND (exp
, 0), one
);
1150 add_expr (TREE_OPERAND (exp
, 1), two
);
1151 hstate
.add_commutative (one
, two
);
1155 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1156 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1162 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1165 sem_function::hash_stmt (gimple stmt
, inchash::hash
&hstate
)
1167 enum gimple_code code
= gimple_code (stmt
);
1169 hstate
.add_int (code
);
1174 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1175 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1177 inchash::hash one
, two
;
1179 add_expr (gimple_assign_rhs1 (stmt
), one
);
1180 add_expr (gimple_assign_rhs2 (stmt
), two
);
1181 hstate
.add_commutative (one
, two
);
1182 add_expr (gimple_assign_lhs (stmt
), hstate
);
1185 /* ... fall through ... */
1191 /* All these statements are equivalent if their operands are. */
1192 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1193 add_expr (gimple_op (stmt
, i
), hstate
);
1200 /* Return true if polymorphic comparison must be processed. */
1203 sem_function::compare_polymorphic_p (void)
1205 return get_node ()->callees
!= NULL
1206 || get_node ()->indirect_calls
!= NULL
1207 || m_compared_func
->get_node ()->callees
!= NULL
1208 || m_compared_func
->get_node ()->indirect_calls
!= NULL
;
1211 /* For a given call graph NODE, the function constructs new
1212 semantic function item. */
1215 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1217 tree fndecl
= node
->decl
;
1218 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1220 /* TODO: add support for thunks. */
1222 if (!func
|| !node
->has_gimple_body_p ())
1225 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1228 sem_function
*f
= new sem_function (node
, 0, stack
);
1235 /* Parses function arguments and result type. */
1238 sem_function::parse_tree_args (void)
1242 if (arg_types
.exists ())
1243 arg_types
.release ();
1245 arg_types
.create (4);
1246 tree fnargs
= DECL_ARGUMENTS (decl
);
1248 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
1249 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
1251 /* Function result type. */
1252 result
= DECL_RESULT (decl
);
1253 result_type
= result
? TREE_TYPE (result
) : NULL
;
1255 /* During WPA, we can get arguments by following method. */
1258 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
1259 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
1260 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
1262 result_type
= TREE_TYPE (TREE_TYPE (decl
));
1266 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1267 return true if phi nodes are semantically equivalent in these blocks . */
1270 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1272 gphi_iterator si1
, si2
;
1274 unsigned size1
, size2
, i
;
1278 gcc_assert (bb1
!= NULL
);
1279 gcc_assert (bb2
!= NULL
);
1281 si2
= gsi_start_phis (bb2
);
1282 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1285 gsi_next_nonvirtual_phi (&si1
);
1286 gsi_next_nonvirtual_phi (&si2
);
1288 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1291 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1292 return return_false();
1297 tree phi_result1
= gimple_phi_result (phi1
);
1298 tree phi_result2
= gimple_phi_result (phi2
);
1300 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1301 return return_false_with_msg ("PHI results are different");
1303 size1
= gimple_phi_num_args (phi1
);
1304 size2
= gimple_phi_num_args (phi2
);
1307 return return_false ();
1309 for (i
= 0; i
< size1
; ++i
)
1311 t1
= gimple_phi_arg (phi1
, i
)->def
;
1312 t2
= gimple_phi_arg (phi2
, i
)->def
;
1314 if (!m_checker
->compare_operand (t1
, t2
))
1315 return return_false ();
1317 e1
= gimple_phi_arg_edge (phi1
, i
);
1318 e2
= gimple_phi_arg_edge (phi2
, i
);
1320 if (!m_checker
->compare_edge (e1
, e2
))
1321 return return_false ();
1330 /* Returns true if tree T can be compared as a handled component. */
1333 sem_function::icf_handled_component_p (tree t
)
1335 tree_code tc
= TREE_CODE (t
);
1337 return ((handled_component_p (t
))
1338 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
1339 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
1342 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1343 corresponds to TARGET. */
1346 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1351 if (bb_dict
->length () <= (unsigned)source
)
1352 bb_dict
->safe_grow_cleared (source
+ 1);
1354 if ((*bb_dict
)[source
] == 0)
1356 (*bb_dict
)[source
] = target
;
1360 return (*bb_dict
)[source
] == target
;
1363 /* Iterates all tree types in T1 and T2 and returns true if all types
1364 are compatible. If COMPARE_POLYMORPHIC is set to true,
1365 more strict comparison is executed. */
1368 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
1376 while (t1
!= NULL
&& t2
!= NULL
)
1378 tv1
= TREE_VALUE (t1
);
1379 tv2
= TREE_VALUE (t2
);
1381 tc1
= TREE_CODE (tv1
);
1382 tc2
= TREE_CODE (tv2
);
1384 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
1386 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
1388 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
1391 t1
= TREE_CHAIN (t1
);
1392 t2
= TREE_CHAIN (t2
);
1399 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1401 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1405 /* Constructor based on varpool node _NODE with computed hash _HASH.
1406 Bitmap STACK is used for memory allocation. */
1408 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1409 bitmap_obstack
*stack
): sem_item(VAR
,
1412 gcc_checking_assert (node
);
1413 gcc_checking_assert (get_node ());
1416 /* Fast equality function based on knowledge known in WPA. */
1419 sem_variable::equals_wpa (sem_item
*item
,
1420 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1422 gcc_assert (item
->type
== VAR
);
1424 if (node
->num_references () != item
->node
->num_references ())
1425 return return_false_with_msg ("different number of references");
1427 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1428 return return_false_with_msg ("TLS model");
1430 if (DECL_ALIGN (decl
) != DECL_ALIGN (item
->decl
))
1431 return return_false_with_msg ("alignment mismatch");
1433 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1434 return return_false_with_msg ("Virtual flag mismatch");
1436 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1437 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1438 || !operand_equal_p (DECL_SIZE (decl
),
1439 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1440 return return_false_with_msg ("size mismatch");
1442 /* Do not attempt to mix data from different user sections;
1443 we do not know what user intends with those. */
1444 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1445 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1446 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1447 return return_false_with_msg ("user section mismatch");
1449 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1450 return return_false_with_msg ("text section");
1452 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1453 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1455 item
->node
->iterate_reference (i
, ref2
);
1457 if (!compare_cgraph_references (ignored_nodes
,
1458 ref
->referred
, ref2
->referred
,
1459 ref
->address_matters_p ()))
1466 /* Returns true if the item equals to ITEM given as argument. */
1468 /* Returns true if the item equals to ITEM given as argument. */
1471 sem_variable::equals (sem_item
*item
,
1472 hash_map
<symtab_node
*, sem_item
*> &)
1474 gcc_assert (item
->type
== VAR
);
1477 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1478 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1479 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1480 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1482 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1483 DECL_INITIAL (item
->node
->decl
));
1484 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1486 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1487 name(), item
->name (), node
->order
, item
->node
->order
, asm_name (),
1488 item
->asm_name (), ret
? "true" : "false");
1493 /* Compares trees T1 and T2 for semantic equality. */
1496 sem_variable::equals (tree t1
, tree t2
)
1499 return return_with_debug (t1
== t2
);
1502 tree_code tc1
= TREE_CODE (t1
);
1503 tree_code tc2
= TREE_CODE (t2
);
1506 return return_false_with_msg ("TREE_CODE mismatch");
1512 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1513 unsigned HOST_WIDE_INT idx
;
1515 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1516 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1517 return return_false_with_msg ("constructor type mismatch");
1519 if (typecode
== ARRAY_TYPE
)
1521 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1522 /* For arrays, check that the sizes all match. */
1523 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1525 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1526 return return_false_with_msg ("constructor array size mismatch");
1528 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1530 return return_false_with_msg ("constructor type incompatible");
1532 v1
= CONSTRUCTOR_ELTS (t1
);
1533 v2
= CONSTRUCTOR_ELTS (t2
);
1534 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1535 return return_false_with_msg ("constructor number of elts mismatch");
1537 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1539 constructor_elt
*c1
= &(*v1
)[idx
];
1540 constructor_elt
*c2
= &(*v2
)[idx
];
1542 /* Check that each value is the same... */
1543 if (!sem_variable::equals (c1
->value
, c2
->value
))
1545 /* ... and that they apply to the same fields! */
1546 if (!sem_variable::equals (c1
->index
, c2
->index
))
1553 tree x1
= TREE_OPERAND (t1
, 0);
1554 tree x2
= TREE_OPERAND (t2
, 0);
1555 tree y1
= TREE_OPERAND (t1
, 1);
1556 tree y2
= TREE_OPERAND (t2
, 1);
1558 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1560 return return_false ();
1562 /* Type of the offset on MEM_REF does not matter. */
1563 return return_with_debug (sem_variable::equals (x1
, x2
)
1564 && wi::to_offset (y1
)
1565 == wi::to_offset (y2
));
1570 tree op1
= TREE_OPERAND (t1
, 0);
1571 tree op2
= TREE_OPERAND (t2
, 0);
1572 return sem_variable::equals (op1
, op2
);
1574 /* References to other vars/decls are compared using ipa-ref. */
1577 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1579 return return_false_with_msg ("Declaration mismatch");
1581 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1582 need to process its VAR/FUNCTION references without relying on ipa-ref
1586 return return_false_with_msg ("Declaration mismatch");
1588 /* Integer constants are the same only if the same width of type. */
1589 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1590 return return_false_with_msg ("INTEGER_CST precision mismatch");
1591 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1592 return return_false_with_msg ("INTEGER_CST mode mismatch");
1593 return return_with_debug (tree_int_cst_equal (t1
, t2
));
1595 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1596 return return_false_with_msg ("STRING_CST mode mismatch");
1597 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
1598 return return_false_with_msg ("STRING_CST length mismatch");
1599 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
1600 TREE_STRING_LENGTH (t1
)))
1601 return return_false_with_msg ("STRING_CST mismatch");
1604 /* Fixed constants are the same only if the same width of type. */
1605 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1606 return return_false_with_msg ("FIXED_CST precision mismatch");
1608 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
1609 TREE_FIXED_CST (t2
)));
1611 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
1612 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
1614 /* Real constants are the same only if the same width of type. */
1615 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1616 return return_false_with_msg ("REAL_CST precision mismatch");
1617 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1
),
1618 TREE_REAL_CST (t2
)));
1623 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
1624 return return_false_with_msg ("VECTOR_CST nelts mismatch");
1626 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
1627 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
1628 VECTOR_CST_ELT (t2
, i
)))
1634 case ARRAY_RANGE_REF
:
1636 tree x1
= TREE_OPERAND (t1
, 0);
1637 tree x2
= TREE_OPERAND (t2
, 0);
1638 tree y1
= TREE_OPERAND (t1
, 1);
1639 tree y2
= TREE_OPERAND (t2
, 1);
1641 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
1643 if (!sem_variable::equals (array_ref_low_bound (t1
),
1644 array_ref_low_bound (t2
)))
1646 if (!sem_variable::equals (array_ref_element_size (t1
),
1647 array_ref_element_size (t2
)))
1653 case POINTER_PLUS_EXPR
:
1658 tree x1
= TREE_OPERAND (t1
, 0);
1659 tree x2
= TREE_OPERAND (t2
, 0);
1660 tree y1
= TREE_OPERAND (t1
, 1);
1661 tree y2
= TREE_OPERAND (t2
, 1);
1663 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1667 case VIEW_CONVERT_EXPR
:
1668 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1670 return return_false ();
1671 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
1673 return return_false_with_msg ("ERROR_MARK");
1675 return return_false_with_msg ("Unknown TREE code reached");
1679 /* Parser function that visits a varpool NODE. */
1682 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1684 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
1688 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1695 /* References independent hash function. */
1698 sem_variable::get_hash (void)
1703 /* All WPA streamed in symbols should have their hashes computed at compile
1704 time. At this point, the constructor may not be in memory at all.
1705 DECL_INITIAL (decl) would be error_mark_node in that case. */
1706 gcc_assert (!node
->lto_file_data
);
1707 tree ctor
= DECL_INITIAL (decl
);
1708 inchash::hash hstate
;
1710 hstate
.add_int (456346417);
1711 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
1712 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
1713 add_expr (ctor
, hstate
);
1714 hash
= hstate
.end ();
1719 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1723 sem_variable::merge (sem_item
*alias_item
)
1725 gcc_assert (alias_item
->type
== VAR
);
1727 if (!sem_item::target_supports_symbol_aliases_p ())
1730 fprintf (dump_file
, "Not unifying; "
1731 "Symbol aliases are not supported by target\n\n");
1735 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1737 varpool_node
*original
= get_node ();
1738 varpool_node
*alias
= alias_var
->get_node ();
1739 bool original_discardable
= false;
1741 bool original_address_matters
= original
->address_matters_p ();
1742 bool alias_address_matters
= alias
->address_matters_p ();
1744 /* See if original is in a section that can be discarded if the main
1746 Also consider case where we have resolution info and we know that
1747 original's definition is not going to be used. In this case we can not
1748 create alias to original. */
1749 if (original
->can_be_discarded_p ()
1750 || (node
->resolution
!= LDPR_UNKNOWN
1751 && !decl_binds_to_current_def_p (node
->decl
)))
1752 original_discardable
= true;
1754 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1756 /* Constant pool machinery is not quite ready for aliases.
1757 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
1758 For LTO merging does not happen that is an important missing feature.
1759 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
1760 flag is dropped and non-local symbol name is assigned. */
1761 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
1762 || DECL_IN_CONSTANT_POOL (original
->decl
))
1766 "Not unifying; constant pool variables.\n\n");
1770 /* Do not attempt to mix functions from different user sections;
1771 we do not know what user intends with those. */
1772 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1773 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1774 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1779 "original and alias are in different sections.\n\n");
1783 /* We can not merge if address comparsion metters. */
1784 if (original_address_matters
&& alias_address_matters
1785 && flag_merge_constants
< 2)
1790 "adress of original and alias may be compared.\n\n");
1793 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
1796 fprintf (dump_file
, "Not unifying; alias cannot be created; "
1797 "across comdat group boundary\n\n");
1802 if (original_discardable
)
1805 fprintf (dump_file
, "Not unifying; alias cannot be created; "
1806 "target is discardable\n\n");
1812 gcc_assert (!original
->alias
);
1813 gcc_assert (!alias
->alias
);
1815 alias
->analyzed
= false;
1817 DECL_INITIAL (alias
->decl
) = NULL
;
1818 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1820 alias
->need_bounds_init
= false;
1821 alias
->remove_all_references ();
1822 if (TREE_ADDRESSABLE (alias
->decl
))
1823 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
1825 varpool_node::create_alias (alias_var
->decl
, decl
);
1826 alias
->resolve_alias (original
);
1829 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
1835 /* Dump symbol to FILE. */
1838 sem_variable::dump_to_file (FILE *file
)
1842 print_node (file
, "", decl
, 0);
1843 fprintf (file
, "\n\n");
1846 /* Iterates though a constructor and identifies tree references
1847 we are interested in semantic function equality. */
1850 sem_variable::parse_tree_refs (tree t
)
1852 switch (TREE_CODE (t
))
1856 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1858 for (unsigned i
= 0; i
< length
; i
++)
1859 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1866 tree op
= TREE_OPERAND (t
, 0);
1867 parse_tree_refs (op
);
1872 tree_refs
.safe_push (t
);
1880 unsigned int sem_item_optimizer::class_id
= 0;
1882 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1883 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1886 bitmap_obstack_initialize (&m_bmstack
);
1889 sem_item_optimizer::~sem_item_optimizer ()
1891 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1894 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1895 it
!= m_classes
.end (); ++it
)
1897 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1898 delete (*it
)->classes
[i
];
1900 (*it
)->classes
.release ();
1906 bitmap_obstack_release (&m_bmstack
);
1909 /* Write IPA ICF summary for symbols. */
1912 sem_item_optimizer::write_summary (void)
1914 unsigned int count
= 0;
1916 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1917 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1920 /* Calculate number of symbols to be serialized. */
1921 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1923 lsei_next_in_partition (&lsei
))
1925 symtab_node
*node
= lsei_node (lsei
);
1927 if (m_symtab_node_map
.get (node
))
1931 streamer_write_uhwi (ob
, count
);
1933 /* Process all of the symbols. */
1934 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1936 lsei_next_in_partition (&lsei
))
1938 symtab_node
*node
= lsei_node (lsei
);
1940 sem_item
**item
= m_symtab_node_map
.get (node
);
1944 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1945 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1947 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1951 streamer_write_char_stream (ob
->main_stream
, 0);
1952 produce_asm (ob
, NULL
);
1953 destroy_output_block (ob
);
1956 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1957 contains LEN bytes. */
1960 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1961 const char *data
, size_t len
)
1963 const lto_function_header
*header
=
1964 (const lto_function_header
*) data
;
1965 const int cfg_offset
= sizeof (lto_function_header
);
1966 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1967 const int string_offset
= main_offset
+ header
->main_size
;
1972 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1973 header
->main_size
, file_data
->mode_table
);
1976 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1977 header
->string_size
, vNULL
);
1979 count
= streamer_read_uhwi (&ib_main
);
1981 for (i
= 0; i
< count
; i
++)
1985 lto_symtab_encoder_t encoder
;
1987 index
= streamer_read_uhwi (&ib_main
);
1988 encoder
= file_data
->symtab_node_encoder
;
1989 node
= lto_symtab_encoder_deref (encoder
, index
);
1991 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1993 gcc_assert (node
->definition
);
1996 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1997 (void *) node
->decl
, node
->order
);
1999 if (is_a
<cgraph_node
*> (node
))
2001 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2003 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2007 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2009 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2013 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2015 lto_data_in_delete (data_in
);
2018 /* Read IPA IPA ICF summary for symbols. */
2021 sem_item_optimizer::read_summary (void)
2023 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2024 lto_file_decl_data
*file_data
;
2027 while ((file_data
= file_data_vec
[j
++]))
2030 const char *data
= lto_get_section_data (file_data
,
2031 LTO_section_ipa_icf
, NULL
, &len
);
2034 read_section (file_data
, data
, len
);
2038 /* Register callgraph and varpool hooks. */
2041 sem_item_optimizer::register_hooks (void)
2043 if (!m_cgraph_node_hooks
)
2044 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2045 (&sem_item_optimizer::cgraph_removal_hook
, this);
2047 if (!m_varpool_node_hooks
)
2048 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2049 (&sem_item_optimizer::varpool_removal_hook
, this);
2052 /* Unregister callgraph and varpool hooks. */
2055 sem_item_optimizer::unregister_hooks (void)
2057 if (m_cgraph_node_hooks
)
2058 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2060 if (m_varpool_node_hooks
)
2061 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2064 /* Adds a CLS to hashtable associated by hash value. */
2067 sem_item_optimizer::add_class (congruence_class
*cls
)
2069 gcc_assert (cls
->members
.length ());
2071 congruence_class_group
*group
= get_group_by_hash (
2072 cls
->members
[0]->get_hash (),
2073 cls
->members
[0]->type
);
2074 group
->classes
.safe_push (cls
);
2077 /* Gets a congruence class group based on given HASH value and TYPE. */
2079 congruence_class_group
*
2080 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2082 congruence_class_group
*item
= XNEW (congruence_class_group
);
2086 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2092 item
->classes
.create (1);
2099 /* Callgraph removal hook called for a NODE with a custom DATA. */
2102 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2104 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2105 optimizer
->remove_symtab_node (node
);
2108 /* Varpool removal hook called for a NODE with a custom DATA. */
2111 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2113 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2114 optimizer
->remove_symtab_node (node
);
2117 /* Remove symtab NODE triggered by symtab removal hooks. */
2120 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2122 gcc_assert (!m_classes
.elements());
2124 m_removed_items_set
.add (node
);
2128 sem_item_optimizer::remove_item (sem_item
*item
)
2130 if (m_symtab_node_map
.get (item
->node
))
2131 m_symtab_node_map
.remove (item
->node
);
2135 /* Removes all callgraph and varpool nodes that are marked by symtab
2139 sem_item_optimizer::filter_removed_items (void)
2141 auto_vec
<sem_item
*> filtered
;
2143 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2145 sem_item
*item
= m_items
[i
];
2147 if (m_removed_items_set
.contains (item
->node
))
2153 if (item
->type
== FUNC
)
2155 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2157 bool no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
2158 if (no_body_function
|| !opt_for_fn (item
->decl
, flag_ipa_icf_functions
)
2159 || DECL_CXX_CONSTRUCTOR_P (item
->decl
)
2160 || DECL_CXX_DESTRUCTOR_P (item
->decl
))
2163 filtered
.safe_push (item
);
2167 if (!flag_ipa_icf_variables
)
2171 /* Filter out non-readonly variables. */
2172 tree decl
= item
->decl
;
2173 if (TREE_READONLY (decl
))
2174 filtered
.safe_push (item
);
2181 /* Clean-up of released semantic items. */
2184 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2185 m_items
.safe_push (filtered
[i
]);
2188 /* Optimizer entry point which returns true in case it processes
2189 a merge operation. True is returned if there's a merge operation
2193 sem_item_optimizer::execute (void)
2195 filter_removed_items ();
2196 unregister_hooks ();
2198 build_hash_based_classes ();
2201 fprintf (dump_file
, "Dump after hash based groups\n");
2202 dump_cong_classes ();
2204 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2205 m_items
[i
]->init_wpa ();
2209 subdivide_classes_by_equality (true);
2212 fprintf (dump_file
, "Dump after WPA based types groups\n");
2214 dump_cong_classes ();
2216 process_cong_reduction ();
2220 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2222 dump_cong_classes ();
2224 parse_nonsingleton_classes ();
2225 subdivide_classes_by_equality ();
2228 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2230 dump_cong_classes ();
2232 unsigned int prev_class_count
= m_classes_count
;
2234 process_cong_reduction ();
2235 dump_cong_classes ();
2237 bool merged_p
= merge_classes (prev_class_count
);
2239 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2240 symtab_node::dump_table (dump_file
);
2245 /* Function responsible for visiting all potential functions and
2246 read-only variables that can be merged. */
2249 sem_item_optimizer::parse_funcs_and_vars (void)
2253 if (flag_ipa_icf_functions
)
2254 FOR_EACH_DEFINED_FUNCTION (cnode
)
2256 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2259 m_items
.safe_push (f
);
2260 m_symtab_node_map
.put (cnode
, f
);
2263 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
2265 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2266 f
->dump_to_file (dump_file
);
2269 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2272 varpool_node
*vnode
;
2274 if (flag_ipa_icf_variables
)
2275 FOR_EACH_DEFINED_VARIABLE (vnode
)
2277 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2281 m_items
.safe_push (v
);
2282 m_symtab_node_map
.put (vnode
, v
);
2287 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2290 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2292 item
->index_in_class
= cls
->members
.length ();
2293 cls
->members
.safe_push (item
);
2297 /* Congruence classes are built by hash value. */
2300 sem_item_optimizer::build_hash_based_classes (void)
2302 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2304 sem_item
*item
= m_items
[i
];
2306 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
2309 if (!group
->classes
.length ())
2312 group
->classes
.safe_push (new congruence_class (class_id
++));
2315 add_item_to_class (group
->classes
[0], item
);
2319 /* Build references according to call graph. */
2322 sem_item_optimizer::build_graph (void)
2324 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2326 sem_item
*item
= m_items
[i
];
2327 m_symtab_node_map
.put (item
->node
, item
);
2330 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2332 sem_item
*item
= m_items
[i
];
2334 if (item
->type
== FUNC
)
2336 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2338 cgraph_edge
*e
= cnode
->callees
;
2341 sem_item
**slot
= m_symtab_node_map
.get
2342 (e
->callee
->ultimate_alias_target ());
2344 item
->add_reference (*slot
);
2350 ipa_ref
*ref
= NULL
;
2351 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2353 sem_item
**slot
= m_symtab_node_map
.get
2354 (ref
->referred
->ultimate_alias_target ());
2356 item
->add_reference (*slot
);
2361 /* Semantic items in classes having more than one element and initialized.
2362 In case of WPA, we load function body. */
2365 sem_item_optimizer::parse_nonsingleton_classes (void)
2367 unsigned int init_called_count
= 0;
2369 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2370 if (m_items
[i
]->cls
->members
.length () > 1)
2372 m_items
[i
]->init ();
2373 init_called_count
++;
2377 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2378 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2381 /* Equality function for semantic items is used to subdivide existing
2382 classes. If IN_WPA, fast equality function is invoked. */
2385 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2387 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2388 it
!= m_classes
.end (); ++it
)
2390 unsigned int class_count
= (*it
)->classes
.length ();
2392 for (unsigned i
= 0; i
< class_count
; i
++)
2394 congruence_class
*c
= (*it
)->classes
[i
];
2396 if (c
->members
.length() > 1)
2398 auto_vec
<sem_item
*> new_vector
;
2400 sem_item
*first
= c
->members
[0];
2401 new_vector
.safe_push (first
);
2403 unsigned class_split_first
= (*it
)->classes
.length ();
2405 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2407 sem_item
*item
= c
->members
[j
];
2409 bool equals
= in_wpa
? first
->equals_wpa (item
,
2410 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2413 new_vector
.safe_push (item
);
2416 bool integrated
= false;
2418 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2420 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2421 bool equals
= in_wpa
? x
->equals_wpa (item
,
2422 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2427 add_item_to_class ((*it
)->classes
[k
], item
);
2435 congruence_class
*c
= new congruence_class (class_id
++);
2437 add_item_to_class (c
, item
);
2439 (*it
)->classes
.safe_push (c
);
2444 // we replace newly created new_vector for the class we've just splitted
2445 c
->members
.release ();
2446 c
->members
.create (new_vector
.length ());
2448 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2449 add_item_to_class (c
, new_vector
[j
]);
2457 /* Subdivide classes by address references that members of the class
2458 reference. Example can be a pair of functions that have an address
2459 taken from a function. If these addresses are different the class
2463 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2465 unsigned newly_created_classes
= 0;
2467 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2468 it
!= m_classes
.end (); ++it
)
2470 unsigned int class_count
= (*it
)->classes
.length ();
2471 auto_vec
<congruence_class
*> new_classes
;
2473 for (unsigned i
= 0; i
< class_count
; i
++)
2475 congruence_class
*c
= (*it
)->classes
[i
];
2477 if (c
->members
.length() > 1)
2479 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2480 symbol_compare_hashmap_traits
> split_map
;
2482 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2484 sem_item
*source_node
= c
->members
[j
];
2486 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2488 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
);
2489 gcc_checking_assert (slot
);
2491 slot
->safe_push (source_node
);
2494 /* If the map contains more than one key, we have to split the map
2496 if (split_map
.elements () != 1)
2498 bool first_class
= true;
2500 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2501 symbol_compare_hashmap_traits
>::iterator it2
= split_map
.begin ();
2502 for (; it2
!= split_map
.end (); ++it2
)
2504 congruence_class
*new_cls
;
2505 new_cls
= new congruence_class (class_id
++);
2507 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2508 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2510 worklist_push (new_cls
);
2511 newly_created_classes
++;
2515 (*it
)->classes
[i
] = new_cls
;
2516 first_class
= false;
2520 new_classes
.safe_push (new_cls
);
2528 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2529 (*it
)->classes
.safe_push (new_classes
[i
]);
2532 return newly_created_classes
;
2535 /* Verify congruence classes if checking is enabled. */
2538 sem_item_optimizer::verify_classes (void)
2541 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2542 it
!= m_classes
.end (); ++it
)
2544 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2546 congruence_class
*cls
= (*it
)->classes
[i
];
2548 gcc_checking_assert (cls
);
2549 gcc_checking_assert (cls
->members
.length () > 0);
2551 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
2553 sem_item
*item
= cls
->members
[j
];
2555 gcc_checking_assert (item
);
2556 gcc_checking_assert (item
->cls
== cls
);
2558 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
2560 sem_usage_pair
*usage
= item
->usages
[k
];
2561 gcc_checking_assert (usage
->item
->index_in_class
<
2562 usage
->item
->cls
->members
.length ());
2570 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2571 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2572 but unused argument. */
2575 sem_item_optimizer::release_split_map (congruence_class
* const &,
2576 bitmap
const &b
, traverse_split_pair
*)
2585 /* Process split operation for a class given as pointer CLS_PTR,
2586 where bitmap B splits congruence class members. DATA is used
2587 as argument of split pair. */
2590 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2591 bitmap
const &b
, traverse_split_pair
*pair
)
2593 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2594 const congruence_class
*splitter_cls
= pair
->cls
;
2596 /* If counted bits are greater than zero and less than the number of members
2597 a group will be splitted. */
2598 unsigned popcount
= bitmap_count_bits (b
);
2600 if (popcount
> 0 && popcount
< cls
->members
.length ())
2602 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
2604 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2606 int target
= bitmap_bit_p (b
, i
);
2607 congruence_class
*tc
= newclasses
[target
];
2609 add_item_to_class (tc
, cls
->members
[i
]);
2612 #ifdef ENABLE_CHECKING
2613 for (unsigned int i
= 0; i
< 2; i
++)
2614 gcc_checking_assert (newclasses
[i
]->members
.length ());
2617 if (splitter_cls
== cls
)
2618 optimizer
->splitter_class_removed
= true;
2620 /* Remove old class from worklist if presented. */
2621 bool in_worklist
= cls
->in_worklist
;
2624 cls
->in_worklist
= false;
2626 congruence_class_group g
;
2627 g
.hash
= cls
->members
[0]->get_hash ();
2628 g
.type
= cls
->members
[0]->type
;
2630 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
2632 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2633 if (slot
->classes
[i
] == cls
)
2635 slot
->classes
.ordered_remove (i
);
2639 /* New class will be inserted and integrated to work list. */
2640 for (unsigned int i
= 0; i
< 2; i
++)
2641 optimizer
->add_class (newclasses
[i
]);
2643 /* Two classes replace one, so that increment just by one. */
2644 optimizer
->m_classes_count
++;
2646 /* If OLD class was presented in the worklist, we remove the class
2647 and replace it will both newly created classes. */
2649 for (unsigned int i
= 0; i
< 2; i
++)
2650 optimizer
->worklist_push (newclasses
[i
]);
2651 else /* Just smaller class is inserted. */
2653 unsigned int smaller_index
= newclasses
[0]->members
.length () <
2654 newclasses
[1]->members
.length () ?
2656 optimizer
->worklist_push (newclasses
[smaller_index
]);
2659 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2661 fprintf (dump_file
, " congruence class splitted:\n");
2662 cls
->dump (dump_file
, 4);
2664 fprintf (dump_file
, " newly created groups:\n");
2665 for (unsigned int i
= 0; i
< 2; i
++)
2666 newclasses
[i
]->dump (dump_file
, 4);
2669 /* Release class if not presented in work list. */
2678 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2679 Bitmap stack BMSTACK is used for bitmap allocation. */
2682 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2685 hash_map
<congruence_class
*, bitmap
> split_map
;
2687 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2689 sem_item
*item
= cls
->members
[i
];
2691 /* Iterate all usages that have INDEX as usage of the item. */
2692 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2694 sem_usage_pair
*usage
= item
->usages
[j
];
2696 if (usage
->index
!= index
)
2699 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2704 b
= BITMAP_ALLOC (&m_bmstack
);
2705 split_map
.put (usage
->item
->cls
, b
);
2711 gcc_checking_assert (usage
->item
->cls
);
2712 gcc_checking_assert (usage
->item
->index_in_class
<
2713 usage
->item
->cls
->members
.length ());
2716 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2720 traverse_split_pair pair
;
2721 pair
.optimizer
= this;
2724 splitter_class_removed
= false;
2726 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2728 /* Bitmap clean-up. */
2730 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2733 /* Every usage of a congruence class CLS is a candidate that can split the
2734 collection of classes. Bitmap stack BMSTACK is used for bitmap
2738 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2743 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2745 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2746 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2748 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2750 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2751 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2754 do_congruence_step_for_index (cls
, i
);
2756 if (splitter_class_removed
)
2760 BITMAP_FREE (usage
);
2763 /* Adds a newly created congruence class CLS to worklist. */
2766 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2768 /* Return if the class CLS is already presented in work list. */
2769 if (cls
->in_worklist
)
2772 cls
->in_worklist
= true;
2773 worklist
.push_back (cls
);
2776 /* Pops a class from worklist. */
2779 sem_item_optimizer::worklist_pop (void)
2781 congruence_class
*cls
;
2783 while (!worklist
.empty ())
2785 cls
= worklist
.front ();
2786 worklist
.pop_front ();
2787 if (cls
->in_worklist
)
2789 cls
->in_worklist
= false;
2795 /* Work list item was already intended to be removed.
2796 The only reason for doing it is to split a class.
2797 Thus, the class CLS is deleted. */
2805 /* Iterative congruence reduction function. */
2808 sem_item_optimizer::process_cong_reduction (void)
2810 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2811 it
!= m_classes
.end (); ++it
)
2812 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2813 if ((*it
)->classes
[i
]->is_class_used ())
2814 worklist_push ((*it
)->classes
[i
]);
2817 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2818 (unsigned long) worklist
.size ());
2820 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2821 fprintf (dump_file
, "Congruence class reduction\n");
2823 congruence_class
*cls
;
2825 /* Process complete congruence reduction. */
2826 while ((cls
= worklist_pop ()) != NULL
)
2827 do_congruence_step (cls
);
2829 /* Subdivide newly created classes according to references. */
2830 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
2833 fprintf (dump_file
, "Address reference subdivision created: %u "
2834 "new classes.\n", new_classes
);
2837 /* Debug function prints all informations about congruence classes. */
2840 sem_item_optimizer::dump_cong_classes (void)
2846 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2847 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2849 /* Histogram calculation. */
2850 unsigned int max_index
= 0;
2851 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2853 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2854 it
!= m_classes
.end (); ++it
)
2856 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2858 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2866 "Class size histogram [num of members]: number of classe number of classess\n");
2868 for (unsigned int i
= 0; i
<= max_index
; i
++)
2870 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2872 fprintf (dump_file
, "\n\n");
2875 if (dump_flags
& TDF_DETAILS
)
2876 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2877 it
!= m_classes
.end (); ++it
)
2879 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2881 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2883 (*it
)->classes
[i
]->dump (dump_file
, 4);
2885 if(i
< (*it
)->classes
.length () - 1)
2886 fprintf (dump_file
, " ");
2893 /* After reduction is done, we can declare all items in a group
2894 to be equal. PREV_CLASS_COUNT is start number of classes
2895 before reduction. True is returned if there's a merge operation
2899 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2901 unsigned int item_count
= m_items
.length ();
2902 unsigned int class_count
= m_classes_count
;
2903 unsigned int equal_items
= item_count
- class_count
;
2905 unsigned int non_singular_classes_count
= 0;
2906 unsigned int non_singular_classes_sum
= 0;
2908 bool merged_p
= false;
2910 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2911 it
!= m_classes
.end (); ++it
)
2912 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2914 congruence_class
*c
= (*it
)->classes
[i
];
2915 if (c
->members
.length () > 1)
2917 non_singular_classes_count
++;
2918 non_singular_classes_sum
+= c
->members
.length ();
2924 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2925 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2926 prev_class_count
, class_count
);
2927 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2928 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2929 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2930 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2931 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2932 non_singular_classes_count
: 0.0f
,
2933 non_singular_classes_count
);
2934 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2935 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2936 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2939 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2940 it
!= m_classes
.end (); ++it
)
2941 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2943 congruence_class
*c
= (*it
)->classes
[i
];
2945 if (c
->members
.length () == 1)
2948 gcc_assert (c
->members
.length ());
2950 sem_item
*source
= c
->members
[0];
2952 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2954 sem_item
*alias
= c
->members
[j
];
2958 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2959 source
->name (), alias
->name ());
2960 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2961 source
->asm_name (), alias
->asm_name ());
2964 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
2968 "Merge operation is skipped due to no_icf "
2974 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2976 source
->dump_to_file (dump_file
);
2977 alias
->dump_to_file (dump_file
);
2980 merged_p
|= source
->merge (alias
);
2987 /* Dump function prints all class members to a FILE with an INDENT. */
2990 congruence_class::dump (FILE *file
, unsigned int indent
) const
2992 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2993 id
, members
[0]->get_hash (), members
.length ());
2995 FPUTS_SPACES (file
, indent
+ 2, "");
2996 for (unsigned i
= 0; i
< members
.length (); i
++)
2997 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2998 members
[i
]->node
->order
);
3000 fprintf (file
, "\n");
3003 /* Returns true if there's a member that is used from another group. */
3006 congruence_class::is_class_used (void)
3008 for (unsigned int i
= 0; i
< members
.length (); i
++)
3009 if (members
[i
]->usages
.length ())
3015 /* Initialization and computation of symtab node hash, there data
3016 are propagated later on. */
3018 static sem_item_optimizer
*optimizer
= NULL
;
3020 /* Generate pass summary for IPA ICF pass. */
3023 ipa_icf_generate_summary (void)
3026 optimizer
= new sem_item_optimizer ();
3028 optimizer
->register_hooks ();
3029 optimizer
->parse_funcs_and_vars ();
3032 /* Write pass summary for IPA ICF pass. */
3035 ipa_icf_write_summary (void)
3037 gcc_assert (optimizer
);
3039 optimizer
->write_summary ();
3042 /* Read pass summary for IPA ICF pass. */
3045 ipa_icf_read_summary (void)
3048 optimizer
= new sem_item_optimizer ();
3050 optimizer
->read_summary ();
3051 optimizer
->register_hooks ();
3054 /* Semantic equality exection function. */
3057 ipa_icf_driver (void)
3059 gcc_assert (optimizer
);
3061 bool merged_p
= optimizer
->execute ();
3066 return merged_p
? TODO_remove_functions
: 0;
3069 const pass_data pass_data_ipa_icf
=
3071 IPA_PASS
, /* type */
3073 OPTGROUP_IPA
, /* optinfo_flags */
3074 TV_IPA_ICF
, /* tv_id */
3075 0, /* properties_required */
3076 0, /* properties_provided */
3077 0, /* properties_destroyed */
3078 0, /* todo_flags_start */
3079 0, /* todo_flags_finish */
3082 class pass_ipa_icf
: public ipa_opt_pass_d
3085 pass_ipa_icf (gcc::context
*ctxt
)
3086 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3087 ipa_icf_generate_summary
, /* generate_summary */
3088 ipa_icf_write_summary
, /* write_summary */
3089 ipa_icf_read_summary
, /* read_summary */
3091 write_optimization_summary */
3093 read_optimization_summary */
3094 NULL
, /* stmt_fixup */
3095 0, /* function_transform_todo_flags_start */
3096 NULL
, /* function_transform */
3097 NULL
) /* variable_transform */
3100 /* opt_pass methods: */
3101 virtual bool gate (function
*)
3103 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3106 virtual unsigned int execute (function
*)
3108 return ipa_icf_driver();
3110 }; // class pass_ipa_icf
3112 } // ipa_icf namespace
3115 make_pass_ipa_icf (gcc::context
*ctxt
)
3117 return new ipa_icf::pass_ipa_icf (ctxt
);