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
;
131 /* Initialization and computation of symtab node hash, there data
132 are propagated later on. */
134 static sem_item_optimizer
*optimizer
= NULL
;
138 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
140 m_references
.create (0);
141 m_interposables
.create (0);
145 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
148 for (unsigned i
= 0; i
< node
->num_references (); i
++)
150 ref
= node
->iterate_reference (i
, ref
);
151 if (ref
->address_matters_p ())
152 m_references
.safe_push (ref
->referred
);
154 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
156 if (ref
->address_matters_p ())
157 m_references
.safe_push (ref
->referred
);
159 m_interposables
.safe_push (ref
->referred
);
163 if (is_a
<cgraph_node
*> (node
))
165 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
167 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
168 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
169 m_interposables
.safe_push (e
->callee
);
173 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
175 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
176 item (_item
), index (_index
)
180 /* Semantic item constructor for a node of _TYPE, where STACK is used
181 for bitmap memory allocation. */
183 sem_item::sem_item (sem_item_type _type
,
184 bitmap_obstack
*stack
): type(_type
), hash(0)
189 /* Semantic item constructor for a node of _TYPE, where STACK is used
190 for bitmap memory allocation. The item is based on symtab node _NODE
191 with computed _HASH. */
193 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
194 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
195 node (_node
), hash (_hash
)
201 /* Add reference to a semantic TARGET. */
204 sem_item::add_reference (sem_item
*target
)
206 refs
.safe_push (target
);
207 unsigned index
= refs
.length ();
208 target
->usages
.safe_push (new sem_usage_pair(this, index
));
209 bitmap_set_bit (target
->usage_index_bitmap
, index
);
210 refs_set
.add (target
->node
);
213 /* Initialize internal data structures. Bitmap STACK is used for
214 bitmap memory allocation process. */
217 sem_item::setup (bitmap_obstack
*stack
)
219 gcc_checking_assert (node
);
222 tree_refs
.create (0);
224 usage_index_bitmap
= BITMAP_ALLOC (stack
);
227 sem_item::~sem_item ()
229 for (unsigned i
= 0; i
< usages
.length (); i
++)
233 tree_refs
.release ();
236 BITMAP_FREE (usage_index_bitmap
);
239 /* Dump function for debugging purpose. */
242 sem_item::dump (void)
246 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
247 node
->name(), node
->order
, (void *) node
->decl
);
248 fprintf (dump_file
, " hash: %u\n", get_hash ());
249 fprintf (dump_file
, " references: ");
251 for (unsigned i
= 0; i
< refs
.length (); i
++)
252 fprintf (dump_file
, "%s%s ", refs
[i
]->node
->name (),
253 i
< refs
.length() - 1 ? "," : "");
255 fprintf (dump_file
, "\n");
259 /* Return true if target supports alias symbols. */
262 sem_item::target_supports_symbol_aliases_p (void)
264 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
271 /* Semantic function constructor that uses STACK as bitmap memory stack. */
273 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
274 m_checker (NULL
), m_compared_func (NULL
)
277 bb_sorted
.create (0);
280 /* Constructor based on callgraph node _NODE with computed hash _HASH.
281 Bitmap STACK is used for memory allocation. */
282 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
283 bitmap_obstack
*stack
):
284 sem_item (FUNC
, node
, hash
, stack
),
285 m_checker (NULL
), m_compared_func (NULL
)
288 bb_sorted
.create (0);
291 sem_function::~sem_function ()
293 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
294 delete (bb_sorted
[i
]);
297 bb_sorted
.release ();
300 /* Calculates hash value based on a BASIC_BLOCK. */
303 sem_function::get_bb_hash (const sem_bb
*basic_block
)
305 inchash::hash hstate
;
307 hstate
.add_int (basic_block
->nondbg_stmt_count
);
308 hstate
.add_int (basic_block
->edge_count
);
310 return hstate
.end ();
313 /* References independent hash function. */
316 sem_function::get_hash (void)
320 inchash::hash hstate
;
321 hstate
.add_int (177454); /* Random number for function type. */
323 hstate
.add_int (arg_count
);
324 hstate
.add_int (cfg_checksum
);
325 hstate
.add_int (gcode_hash
);
327 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
328 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
330 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
331 hstate
.add_int (bb_sizes
[i
]);
334 /* Add common features of declaration itself. */
335 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
337 (cl_target_option_hash
338 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
339 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
340 (cl_optimization_hash
341 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
342 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (decl
));
343 hstate
.add_flag (DECL_DECLARED_INLINE_P (decl
));
344 hstate
.add_flag (DECL_IS_OPERATOR_NEW (decl
));
345 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
346 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
348 hash
= hstate
.end ();
354 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
355 point to a same function. Comparison can be skipped if IGNORED_NODES
356 contains these nodes. ADDRESS indicate if address is taken. */
359 sem_item::compare_cgraph_references (
360 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
361 symtab_node
*n1
, symtab_node
*n2
, bool address
)
363 enum availability avail1
, avail2
;
368 /* Never match variable and function. */
369 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
372 /* Merging two definitions with a reference to equivalent vtables, but
373 belonging to a different type may result in ipa-polymorphic-call analysis
374 giving a wrong answer about the dynamic type of instance. */
375 if (is_a
<varpool_node
*> (n1
)
376 && (DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
377 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
378 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
379 DECL_CONTEXT (n2
->decl
))))
380 return return_false_with_msg
381 ("references to virtual tables can not be merged");
383 if (address
&& n1
->equal_address_to (n2
) == 1)
385 if (!address
&& n1
->semantically_equivalent_p (n2
))
388 n1
= n1
->ultimate_alias_target (&avail1
);
389 n2
= n2
->ultimate_alias_target (&avail2
);
391 if (avail1
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
392 && avail2
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
395 return return_false_with_msg ("different references");
398 /* If cgraph edges E1 and E2 are indirect calls, verify that
399 ECF flags are the same. */
401 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
403 if (e1
->indirect_info
&& e2
->indirect_info
)
405 int e1_flags
= e1
->indirect_info
->ecf_flags
;
406 int e2_flags
= e2
->indirect_info
->ecf_flags
;
408 if (e1_flags
!= e2_flags
)
409 return return_false_with_msg ("ICF flags are different");
411 else if (e1
->indirect_info
|| e2
->indirect_info
)
417 /* Perform additional check needed to match types function parameters that are
418 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
419 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
422 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
424 /* Be sure that parameters are TBAA compatible. */
425 if (!func_checker::compatible_types_p (parm1
, parm2
))
426 return return_false_with_msg ("parameter type is not compatible");
428 if (POINTER_TYPE_P (parm1
)
429 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
430 return return_false_with_msg ("argument restrict flag mismatch");
432 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
433 if (POINTER_TYPE_P (parm1
)
434 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
435 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
436 return return_false_with_msg ("pointer wrt reference mismatch");
441 /* Return true if parameter I may be used. */
444 sem_function::param_used_p (unsigned int i
)
446 if (ipa_node_params_sum
== NULL
)
449 struct ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
451 if (parms_info
->descriptors
.is_empty ()
452 || parms_info
->descriptors
.length () <= i
)
455 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
458 /* Fast equality function based on knowledge known in WPA. */
461 sem_function::equals_wpa (sem_item
*item
,
462 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
464 gcc_assert (item
->type
== FUNC
);
466 m_compared_func
= static_cast<sem_function
*> (item
);
468 /* Compare special function DECL attributes. */
469 if (DECL_FUNCTION_PERSONALITY (decl
)
470 != DECL_FUNCTION_PERSONALITY (item
->decl
))
471 return return_false_with_msg ("function personalities are different");
473 if (DECL_DISREGARD_INLINE_LIMITS (decl
)
474 != DECL_DISREGARD_INLINE_LIMITS (item
->decl
))
475 return return_false_with_msg ("DECL_DISREGARD_INLINE_LIMITS are different");
477 if (DECL_DECLARED_INLINE_P (decl
) != DECL_DECLARED_INLINE_P (item
->decl
))
478 return return_false_with_msg ("inline attributes are different");
480 if (DECL_IS_OPERATOR_NEW (decl
) != DECL_IS_OPERATOR_NEW (item
->decl
))
481 return return_false_with_msg ("operator new flags are different");
483 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
484 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
485 return return_false_with_msg ("intrument function entry exit "
486 "attributes are different");
488 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
489 return return_false_with_msg ("no stack limit attributes are different");
491 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
492 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
494 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
495 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
497 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
498 return return_false_with_msg ("decl_or_type flags are different");
500 /* Do not match polymorphic constructors of different types. They calls
501 type memory location for ipa-polymorphic-call and we do not want
502 it to get confused by wrong type. */
503 if (DECL_CXX_CONSTRUCTOR_P (decl
)
504 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
506 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
507 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
508 else if (!func_checker::compatible_polymorphic_types_p
509 (method_class_type (TREE_TYPE (decl
)),
510 method_class_type (TREE_TYPE (item
->decl
)), false))
511 return return_false_with_msg ("ctor polymorphic type mismatch");
514 /* Checking function TARGET and OPTIMIZATION flags. */
515 cl_target_option
*tar1
= target_opts_for_fn (decl
);
516 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
518 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
520 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
522 fprintf (dump_file
, "target flags difference");
523 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
526 return return_false_with_msg ("Target flags are different");
529 cl_optimization
*opt1
= opts_for_fn (decl
);
530 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
532 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
534 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
536 fprintf (dump_file
, "optimization flags difference");
537 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
540 return return_false_with_msg ("optimization flags are different");
543 /* Result type checking. */
544 if (!func_checker::compatible_types_p
545 (TREE_TYPE (TREE_TYPE (decl
)),
546 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
547 return return_false_with_msg ("result types are different");
549 /* Checking types of arguments. */
550 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
551 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
552 for (unsigned i
= 0; list1
&& list2
;
553 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
555 tree parm1
= TREE_VALUE (list1
);
556 tree parm2
= TREE_VALUE (list2
);
558 /* This guard is here for function pointer with attributes (pr59927.c). */
559 if (!parm1
|| !parm2
)
560 return return_false_with_msg ("NULL argument type");
562 /* Verify that types are compatible to ensure that both functions
563 have same calling conventions. */
564 if (!types_compatible_p (parm1
, parm2
))
565 return return_false_with_msg ("parameter types are not compatible");
567 if (!param_used_p (i
))
570 /* Perform additional checks for used parameters. */
571 if (!compatible_parm_types_p (parm1
, parm2
))
576 return return_false_with_msg ("Mismatched number of parameters");
578 if (node
->num_references () != item
->node
->num_references ())
579 return return_false_with_msg ("different number of references");
581 if (comp_type_attributes (TREE_TYPE (decl
),
582 TREE_TYPE (item
->decl
)) != 1)
583 return return_false_with_msg ("different type attributes");
585 /* The type of THIS pointer type memory location for
586 ipa-polymorphic-call-analysis. */
587 if (opt_for_fn (decl
, flag_devirtualize
)
588 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
589 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
590 && (ipa_node_params_sum
== NULL
591 || IPA_NODE_REF (get_node ())->descriptors
.is_empty ()
592 || ipa_is_param_used (IPA_NODE_REF (get_node ()),
594 && compare_polymorphic_p ())
596 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
597 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
598 if (!func_checker::compatible_polymorphic_types_p
599 (method_class_type (TREE_TYPE (decl
)),
600 method_class_type (TREE_TYPE (item
->decl
)), false))
601 return return_false_with_msg ("THIS pointer ODR type mismatch");
604 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
605 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
607 item
->node
->iterate_reference (i
, ref2
);
609 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
,
611 ref
->address_matters_p ()))
615 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
616 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
620 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
,
624 e1
= e1
->next_callee
;
625 e2
= e2
->next_callee
;
629 return return_false_with_msg ("different number of edges");
634 /* Update hash by address sensitive references. We iterate over all
635 sensitive references (address_matters_p) and we hash ultime alias
636 target of these nodes, which can improve a semantic item hash.
637 TODO: stronger SCC based hashing would be desirable here. */
640 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
641 sem_item
*> &m_symtab_node_map
)
644 inchash::hash
hstate (hash
);
645 for (unsigned i
= 0; i
< node
->num_references (); i
++)
647 ref
= node
->iterate_reference (i
, ref
);
648 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
649 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
652 if (is_a
<cgraph_node
*> (node
))
654 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
657 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
659 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
663 hash
= hstate
.end ();
666 /* Update hash by computed local hash values taken from different
670 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
671 sem_item
*> &m_symtab_node_map
)
673 inchash::hash
state (hash
);
674 for (unsigned j
= 0; j
< node
->num_references (); j
++)
677 ref
= node
->iterate_reference (j
, ref
);
678 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
680 state
.merge_hash ((*result
)->hash
);
685 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
688 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
690 state
.merge_hash ((*result
)->hash
);
694 global_hash
= state
.end ();
697 /* Returns true if the item equals to ITEM given as argument. */
700 sem_function::equals (sem_item
*item
,
701 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
703 gcc_assert (item
->type
== FUNC
);
704 bool eq
= equals_private (item
, ignored_nodes
);
706 if (m_checker
!= NULL
)
712 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
714 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
715 xstrdup_for_dump (node
->name()),
716 xstrdup_for_dump (item
->node
->name ()),
719 xstrdup_for_dump (node
->asm_name ()),
720 xstrdup_for_dump (item
->node
->asm_name ()),
721 eq
? "true" : "false");
726 /* Processes function equality comparison. */
729 sem_function::equals_private (sem_item
*item
,
730 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
732 if (item
->type
!= FUNC
)
735 basic_block bb1
, bb2
;
737 edge_iterator ei1
, ei2
;
741 m_compared_func
= static_cast<sem_function
*> (item
);
743 gcc_assert (decl
!= item
->decl
);
745 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
746 || edge_count
!= m_compared_func
->edge_count
747 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
748 return return_false ();
750 if (!equals_wpa (item
, ignored_nodes
))
753 /* Checking function arguments. */
754 tree decl1
= DECL_ATTRIBUTES (decl
);
755 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
757 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
758 compare_polymorphic_p (),
761 &m_compared_func
->refs_set
);
765 return return_false ();
767 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
768 return return_false ();
770 tree attr_value1
= TREE_VALUE (decl1
);
771 tree attr_value2
= TREE_VALUE (decl2
);
773 if (attr_value1
&& attr_value2
)
775 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
776 TREE_VALUE (attr_value2
));
778 return return_false_with_msg ("attribute values are different");
780 else if (!attr_value1
&& !attr_value2
)
783 return return_false ();
785 decl1
= TREE_CHAIN (decl1
);
786 decl2
= TREE_CHAIN (decl2
);
790 return return_false();
792 arg1
= DECL_ARGUMENTS (decl
);
793 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
795 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
797 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
798 return return_false_with_msg ("argument types are not compatible");
799 if (!param_used_p (i
))
801 /* Perform additional checks for used parameters. */
802 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
804 if (!m_checker
->compare_decl (arg1
, arg2
))
805 return return_false ();
808 return return_false_with_msg ("Mismatched number of arguments");
810 /* Fill-up label dictionary. */
811 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
813 m_checker
->parse_labels (bb_sorted
[i
]);
814 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
817 /* Checking all basic blocks. */
818 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
819 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
820 return return_false();
822 dump_message ("All BBs are equal\n");
824 auto_vec
<int> bb_dict
;
826 /* Basic block edges check. */
827 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
829 bb1
= bb_sorted
[i
]->bb
;
830 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
832 ei2
= ei_start (bb2
->preds
);
834 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
838 if (e1
->flags
!= e2
->flags
)
839 return return_false_with_msg ("flags comparison returns false");
841 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
842 return return_false_with_msg ("edge comparison returns false");
844 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
845 return return_false_with_msg ("BB comparison returns false");
847 if (!m_checker
->compare_edge (e1
, e2
))
848 return return_false_with_msg ("edge comparison returns false");
854 /* Basic block PHI nodes comparison. */
855 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
856 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
857 return return_false_with_msg ("PHI node comparison returns false");
862 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
863 Helper for call_for_symbol_thunks_and_aliases. */
866 set_local (cgraph_node
*node
, void *data
)
868 node
->local
.local
= data
!= NULL
;
872 /* TREE_ADDRESSABLE of NODE to true.
873 Helper for call_for_symbol_thunks_and_aliases. */
876 set_addressable (varpool_node
*node
, void *)
878 TREE_ADDRESSABLE (node
->decl
) = 1;
882 /* Clear DECL_RTL of NODE.
883 Helper for call_for_symbol_thunks_and_aliases. */
886 clear_decl_rtl (symtab_node
*node
, void *)
888 SET_DECL_RTL (node
->decl
, NULL
);
892 /* Redirect all callers of N and its aliases to TO. Remove aliases if
893 possible. Return number of redirections made. */
896 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
900 cgraph_edge
*e
= n
->callers
;
904 /* Redirecting thunks to interposable symbols or symbols in other sections
905 may not be supported by target output code. Play safe for now and
906 punt on redirection. */
907 if (!e
->caller
->thunk
.thunk_p
)
909 struct cgraph_edge
*nexte
= e
->next_caller
;
910 e
->redirect_callee (to
);
917 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
919 bool removed
= false;
920 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
922 if ((DECL_COMDAT_GROUP (n
->decl
)
923 && (DECL_COMDAT_GROUP (n
->decl
)
924 == DECL_COMDAT_GROUP (n_alias
->decl
)))
925 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
926 && n
->get_availability () > AVAIL_INTERPOSABLE
))
928 nredirected
+= redirect_all_callers (n_alias
, to
);
929 if (n_alias
->can_remove_if_no_direct_calls_p ()
930 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
932 && !n_alias
->has_aliases_p ())
941 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
945 sem_function::merge (sem_item
*alias_item
)
947 gcc_assert (alias_item
->type
== FUNC
);
949 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
951 cgraph_node
*original
= get_node ();
952 cgraph_node
*local_original
= NULL
;
953 cgraph_node
*alias
= alias_func
->get_node ();
955 bool create_wrapper
= false;
956 bool create_alias
= false;
957 bool redirect_callers
= false;
960 bool original_discardable
= false;
961 bool original_discarded
= false;
963 bool original_address_matters
= original
->address_matters_p ();
964 bool alias_address_matters
= alias
->address_matters_p ();
966 if (DECL_EXTERNAL (alias
->decl
))
969 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
973 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
974 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
979 "DECL_NO_INLINE_WARNING mismatch.\n\n");
983 /* Do not attempt to mix functions from different user sections;
984 we do not know what user intends with those. */
985 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
986 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
987 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
992 "original and alias are in different sections.\n\n");
996 /* See if original is in a section that can be discarded if the main
997 symbol is not used. */
999 if (original
->can_be_discarded_p ())
1000 original_discardable
= true;
1001 /* Also consider case where we have resolution info and we know that
1002 original's definition is not going to be used. In this case we can not
1003 create alias to original. */
1004 if (node
->resolution
!= LDPR_UNKNOWN
1005 && !decl_binds_to_current_def_p (node
->decl
))
1006 original_discardable
= original_discarded
= true;
1008 /* Creating a symtab alias is the optimal way to merge.
1009 It however can not be used in the following cases:
1011 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1012 2) if ORIGINAL is in a section that may be discarded by linker or if
1013 it is an external functions where we can not create an alias
1014 (ORIGINAL_DISCARDABLE)
1015 3) if target do not support symbol aliases.
1016 4) original and alias lie in different comdat groups.
1018 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1019 and/or redirect all callers from ALIAS to ORIGINAL. */
1020 if ((original_address_matters
&& alias_address_matters
)
1021 || (original_discardable
1022 && (!DECL_COMDAT_GROUP (alias
->decl
)
1023 || (DECL_COMDAT_GROUP (alias
->decl
)
1024 != DECL_COMDAT_GROUP (original
->decl
))))
1025 || original_discarded
1026 || !sem_item::target_supports_symbol_aliases_p ()
1027 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1029 /* First see if we can produce wrapper. */
1031 /* Do not turn function in one comdat group into wrapper to another
1032 comdat group. Other compiler producing the body of the
1033 another comdat group may make opossite decision and with unfortunate
1034 linker choices this may close a loop. */
1035 if (DECL_COMDAT_GROUP (original
->decl
) && DECL_COMDAT_GROUP (alias
->decl
)
1036 && (DECL_COMDAT_GROUP (alias
->decl
)
1037 != DECL_COMDAT_GROUP (original
->decl
)))
1041 "Wrapper cannot be created because of COMDAT\n");
1043 else if (DECL_STATIC_CHAIN (alias
->decl
))
1047 "Can not create wrapper of nested functions.\n");
1049 /* TODO: We can also deal with variadic functions never calling
1051 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1055 "can not create wrapper of stdarg function.\n");
1057 else if (inline_summaries
1058 && inline_summaries
->get (alias
)->self_size
<= 2)
1061 fprintf (dump_file
, "Wrapper creation is not "
1062 "profitable (function is too small).\n");
1064 /* If user paid attention to mark function noinline, assume it is
1065 somewhat special and do not try to turn it into a wrapper that can
1066 not be undone by inliner. */
1067 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1070 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1073 create_wrapper
= true;
1075 /* We can redirect local calls in the case both alias and orignal
1076 are not interposable. */
1078 = alias
->get_availability () > AVAIL_INTERPOSABLE
1079 && original
->get_availability () > AVAIL_INTERPOSABLE
1080 && !alias
->instrumented_version
;
1082 if (!redirect_callers
&& !create_wrapper
)
1085 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1086 "produce wrapper\n\n");
1090 /* Work out the symbol the wrapper should call.
1091 If ORIGINAL is interposable, we need to call a local alias.
1092 Also produce local alias (if possible) as an optimization.
1094 Local aliases can not be created inside comdat groups because that
1095 prevents inlining. */
1096 if (!original_discardable
&& !original
->get_comdat_group ())
1099 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1101 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1102 local_original
= original
;
1104 /* If we can not use local alias, fallback to the original
1106 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1107 local_original
= original
;
1109 /* If original is COMDAT local, we can not really redirect calls outside
1110 of its comdat group to it. */
1111 if (original
->comdat_local_p ())
1112 redirect_callers
= false;
1113 if (!local_original
)
1116 fprintf (dump_file
, "Not unifying; "
1117 "can not produce local alias.\n\n");
1121 if (!redirect_callers
&& !create_wrapper
)
1124 fprintf (dump_file
, "Not unifying; "
1125 "can not redirect callers nor produce a wrapper\n\n");
1129 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1131 && !alias
->can_remove_if_no_direct_calls_p ())
1134 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1135 "function has other uses than direct calls\n\n");
1140 create_alias
= true;
1142 if (redirect_callers
)
1144 int nredirected
= redirect_all_callers (alias
, local_original
);
1148 alias
->icf_merged
= true;
1149 local_original
->icf_merged
= true;
1151 if (dump_file
&& nredirected
)
1152 fprintf (dump_file
, "%i local calls have been "
1153 "redirected.\n", nredirected
);
1156 /* If all callers was redirected, do not produce wrapper. */
1157 if (alias
->can_remove_if_no_direct_calls_p ()
1158 && !alias
->has_aliases_p ())
1160 create_wrapper
= false;
1163 gcc_assert (!create_alias
);
1165 else if (create_alias
)
1167 alias
->icf_merged
= true;
1169 /* Remove the function's body. */
1170 ipa_merge_profiles (original
, alias
);
1171 alias
->release_body (true);
1173 /* Notice global symbol possibly produced RTL. */
1174 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1177 /* Create the alias. */
1178 cgraph_node::create_alias (alias_func
->decl
, decl
);
1179 alias
->resolve_alias (original
);
1181 original
->call_for_symbol_thunks_and_aliases
1182 (set_local
, (void *)(size_t) original
->local_p (), true);
1185 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1189 gcc_assert (!create_alias
);
1190 alias
->icf_merged
= true;
1191 local_original
->icf_merged
= true;
1193 ipa_merge_profiles (local_original
, alias
, true);
1194 alias
->create_wrapper (local_original
);
1197 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1200 /* It's possible that redirection can hit thunks that block
1201 redirection opportunities. */
1202 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1203 original
->icf_merged
= true;
1205 /* Inform the inliner about cross-module merging. */
1206 if ((original
->lto_file_data
|| alias
->lto_file_data
)
1207 && original
->lto_file_data
!= alias
->lto_file_data
)
1208 local_original
->merged
= original
->merged
= true;
1212 ipa_merge_profiles (original
, alias
);
1213 alias
->release_body ();
1215 alias
->body_removed
= true;
1216 alias
->icf_merged
= true;
1218 fprintf (dump_file
, "Unified; Function body was removed.\n");
1224 /* Semantic item initialization function. */
1227 sem_function::init (void)
1230 get_node ()->get_untransformed_body ();
1232 tree fndecl
= node
->decl
;
1233 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1236 gcc_assert (SSANAMES (func
));
1238 ssa_names_size
= SSANAMES (func
)->length ();
1242 region_tree
= func
->eh
->region_tree
;
1244 /* iterating all function arguments. */
1245 arg_count
= count_formal_params (fndecl
);
1247 edge_count
= n_edges_for_fn (func
);
1248 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1250 inchash::hash hstate
;
1253 FOR_EACH_BB_FN (bb
, func
)
1255 unsigned nondbg_stmt_count
= 0;
1258 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1260 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1263 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1266 gimple stmt
= gsi_stmt (gsi
);
1268 if (gimple_code (stmt
) != GIMPLE_DEBUG
1269 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1271 hash_stmt (stmt
, hstate
);
1272 nondbg_stmt_count
++;
1276 gcode_hash
= hstate
.end ();
1277 bb_sizes
.safe_push (nondbg_stmt_count
);
1279 /* Inserting basic block to hash table. */
1280 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1281 EDGE_COUNT (bb
->preds
)
1282 + EDGE_COUNT (bb
->succs
));
1284 bb_sorted
.safe_push (semantic_bb
);
1288 /* Accumulate to HSTATE a hash of expression EXP.
1289 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1290 and DECL equality classes. */
1293 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1295 if (exp
== NULL_TREE
)
1297 hstate
.merge_hash (0);
1301 /* Handled component can be matched in a cureful way proving equivalence
1302 even if they syntactically differ. Just skip them. */
1304 while (handled_component_p (exp
))
1305 exp
= TREE_OPERAND (exp
, 0);
1307 enum tree_code code
= TREE_CODE (exp
);
1308 hstate
.add_int (code
);
1312 /* Use inchash::add_expr for everything that is LTO stable. */
1320 inchash::add_expr (exp
, hstate
);
1324 unsigned HOST_WIDE_INT idx
;
1327 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1329 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1331 add_expr (value
, hstate
);
1336 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1342 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1345 case POINTER_PLUS_EXPR
:
1348 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1349 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1353 inchash::hash one
, two
;
1354 add_expr (TREE_OPERAND (exp
, 0), one
);
1355 add_expr (TREE_OPERAND (exp
, 1), two
);
1356 hstate
.add_commutative (one
, two
);
1360 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1361 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1367 /* Accumulate to HSTATE a hash of type t.
1368 TYpes that may end up being compatible after LTO type merging needs to have
1372 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1374 if (type
== NULL_TREE
)
1376 hstate
.merge_hash (0);
1380 type
= TYPE_MAIN_VARIANT (type
);
1381 if (TYPE_CANONICAL (type
))
1382 type
= TYPE_CANONICAL (type
);
1384 if (!AGGREGATE_TYPE_P (type
))
1385 hstate
.add_int (TYPE_MODE (type
));
1387 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1389 hstate
.add_int (COMPLEX_TYPE
);
1390 sem_item::add_type (TREE_TYPE (type
), hstate
);
1392 else if (INTEGRAL_TYPE_P (type
))
1394 hstate
.add_int (INTEGER_TYPE
);
1395 hstate
.add_flag (TYPE_UNSIGNED (type
));
1396 hstate
.add_int (TYPE_PRECISION (type
));
1398 else if (VECTOR_TYPE_P (type
))
1400 hstate
.add_int (VECTOR_TYPE
);
1401 hstate
.add_int (TYPE_PRECISION (type
));
1402 sem_item::add_type (TREE_TYPE (type
), hstate
);
1404 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1406 hstate
.add_int (ARRAY_TYPE
);
1407 /* Do not hash size, so complete and incomplete types can match. */
1408 sem_item::add_type (TREE_TYPE (type
), hstate
);
1410 else if (RECORD_OR_UNION_TYPE_P (type
))
1412 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1416 inchash::hash hstate2
;
1421 hstate2
.add_int (RECORD_TYPE
);
1422 gcc_assert (COMPLETE_TYPE_P (type
));
1424 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1425 if (TREE_CODE (f
) == FIELD_DECL
)
1427 add_type (TREE_TYPE (f
), hstate2
);
1431 hstate2
.add_int (nf
);
1432 hash
= hstate2
.end ();
1433 hstate
.add_wide_int (hash
);
1434 optimizer
->m_type_hash_cache
.put (type
, hash
);
1437 hstate
.add_wide_int (*val
);
1441 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1444 sem_function::hash_stmt (gimple stmt
, inchash::hash
&hstate
)
1446 enum gimple_code code
= gimple_code (stmt
);
1448 hstate
.add_int (code
);
1453 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1456 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1457 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1458 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1460 inchash::hash one
, two
;
1462 add_expr (gimple_assign_rhs1 (stmt
), one
);
1463 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1464 add_expr (gimple_assign_rhs2 (stmt
), two
);
1465 hstate
.add_commutative (one
, two
);
1466 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1468 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1469 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1471 add_expr (gimple_assign_lhs (stmt
), hstate
);
1472 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1475 /* ... fall through ... */
1481 /* All these statements are equivalent if their operands are. */
1482 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1484 add_expr (gimple_op (stmt
, i
), hstate
);
1485 if (gimple_op (stmt
, i
))
1486 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1494 /* Return true if polymorphic comparison must be processed. */
1497 sem_function::compare_polymorphic_p (void)
1499 struct cgraph_edge
*e
;
1501 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1503 if (get_node ()->indirect_calls
!= NULL
)
1505 /* TODO: We can do simple propagation determining what calls may lead to
1506 a polymorphic call. */
1507 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1508 if (e
->callee
->definition
1509 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1514 /* For a given call graph NODE, the function constructs new
1515 semantic function item. */
1518 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1520 tree fndecl
= node
->decl
;
1521 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1523 /* TODO: add support for thunks. */
1525 if (!func
|| !node
->has_gimple_body_p ())
1528 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1531 sem_function
*f
= new sem_function (node
, 0, stack
);
1538 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1539 return true if phi nodes are semantically equivalent in these blocks . */
1542 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1544 gphi_iterator si1
, si2
;
1546 unsigned size1
, size2
, i
;
1550 gcc_assert (bb1
!= NULL
);
1551 gcc_assert (bb2
!= NULL
);
1553 si2
= gsi_start_phis (bb2
);
1554 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1557 gsi_next_nonvirtual_phi (&si1
);
1558 gsi_next_nonvirtual_phi (&si2
);
1560 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1563 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1564 return return_false();
1569 tree phi_result1
= gimple_phi_result (phi1
);
1570 tree phi_result2
= gimple_phi_result (phi2
);
1572 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1573 return return_false_with_msg ("PHI results are different");
1575 size1
= gimple_phi_num_args (phi1
);
1576 size2
= gimple_phi_num_args (phi2
);
1579 return return_false ();
1581 for (i
= 0; i
< size1
; ++i
)
1583 t1
= gimple_phi_arg (phi1
, i
)->def
;
1584 t2
= gimple_phi_arg (phi2
, i
)->def
;
1586 if (!m_checker
->compare_operand (t1
, t2
))
1587 return return_false ();
1589 e1
= gimple_phi_arg_edge (phi1
, i
);
1590 e2
= gimple_phi_arg_edge (phi2
, i
);
1592 if (!m_checker
->compare_edge (e1
, e2
))
1593 return return_false ();
1602 /* Returns true if tree T can be compared as a handled component. */
1605 sem_function::icf_handled_component_p (tree t
)
1607 tree_code tc
= TREE_CODE (t
);
1609 return ((handled_component_p (t
))
1610 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
1611 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
1614 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1615 corresponds to TARGET. */
1618 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1623 if (bb_dict
->length () <= (unsigned)source
)
1624 bb_dict
->safe_grow_cleared (source
+ 1);
1626 if ((*bb_dict
)[source
] == 0)
1628 (*bb_dict
)[source
] = target
;
1632 return (*bb_dict
)[source
] == target
;
1636 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1638 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1642 /* Constructor based on varpool node _NODE with computed hash _HASH.
1643 Bitmap STACK is used for memory allocation. */
1645 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1646 bitmap_obstack
*stack
): sem_item(VAR
,
1649 gcc_checking_assert (node
);
1650 gcc_checking_assert (get_node ());
1653 /* Fast equality function based on knowledge known in WPA. */
1656 sem_variable::equals_wpa (sem_item
*item
,
1657 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1659 gcc_assert (item
->type
== VAR
);
1661 if (node
->num_references () != item
->node
->num_references ())
1662 return return_false_with_msg ("different number of references");
1664 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1665 return return_false_with_msg ("TLS model");
1667 if (DECL_ALIGN (decl
) != DECL_ALIGN (item
->decl
))
1668 return return_false_with_msg ("alignment mismatch");
1670 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1671 return return_false_with_msg ("Virtual flag mismatch");
1673 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1674 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1675 || !operand_equal_p (DECL_SIZE (decl
),
1676 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1677 return return_false_with_msg ("size mismatch");
1679 /* Do not attempt to mix data from different user sections;
1680 we do not know what user intends with those. */
1681 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1682 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1683 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1684 return return_false_with_msg ("user section mismatch");
1686 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1687 return return_false_with_msg ("text section");
1689 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1690 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1692 item
->node
->iterate_reference (i
, ref2
);
1694 if (!compare_cgraph_references (ignored_nodes
,
1695 ref
->referred
, ref2
->referred
,
1696 ref
->address_matters_p ()))
1699 /* When matching virtual tables, be sure to also match information
1700 relevant for polymorphic call analysis. */
1701 if (DECL_VIRTUAL_P (decl
) || DECL_VIRTUAL_P (item
->decl
))
1703 if (DECL_VIRTUAL_P (ref
->referred
->decl
)
1704 != DECL_VIRTUAL_P (ref2
->referred
->decl
))
1705 return return_false_with_msg ("virtual flag mismatch");
1706 if (DECL_VIRTUAL_P (ref
->referred
->decl
)
1707 && is_a
<cgraph_node
*> (ref
->referred
)
1708 && (DECL_FINAL_P (ref
->referred
->decl
)
1709 != DECL_FINAL_P (ref2
->referred
->decl
)))
1710 return return_false_with_msg ("final flag mismatch");
1717 /* Returns true if the item equals to ITEM given as argument. */
1719 /* Returns true if the item equals to ITEM given as argument. */
1722 sem_variable::equals (sem_item
*item
,
1723 hash_map
<symtab_node
*, sem_item
*> &)
1725 gcc_assert (item
->type
== VAR
);
1728 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1729 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1730 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1731 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1733 /* As seen in PR ipa/65303 we have to compare variables types. */
1734 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1735 TREE_TYPE (item
->decl
)))
1736 return return_false_with_msg ("variables types are different");
1738 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1739 DECL_INITIAL (item
->node
->decl
));
1740 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1742 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1743 xstrdup_for_dump (node
->name()),
1744 xstrdup_for_dump (item
->node
->name ()),
1745 node
->order
, item
->node
->order
,
1746 xstrdup_for_dump (node
->asm_name ()),
1747 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1752 /* Compares trees T1 and T2 for semantic equality. */
1755 sem_variable::equals (tree t1
, tree t2
)
1758 return return_with_debug (t1
== t2
);
1761 tree_code tc1
= TREE_CODE (t1
);
1762 tree_code tc2
= TREE_CODE (t2
);
1765 return return_false_with_msg ("TREE_CODE mismatch");
1771 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1772 unsigned HOST_WIDE_INT idx
;
1774 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1775 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1776 return return_false_with_msg ("constructor type mismatch");
1778 if (typecode
== ARRAY_TYPE
)
1780 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1781 /* For arrays, check that the sizes all match. */
1782 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1784 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1785 return return_false_with_msg ("constructor array size mismatch");
1787 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1789 return return_false_with_msg ("constructor type incompatible");
1791 v1
= CONSTRUCTOR_ELTS (t1
);
1792 v2
= CONSTRUCTOR_ELTS (t2
);
1793 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1794 return return_false_with_msg ("constructor number of elts mismatch");
1796 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1798 constructor_elt
*c1
= &(*v1
)[idx
];
1799 constructor_elt
*c2
= &(*v2
)[idx
];
1801 /* Check that each value is the same... */
1802 if (!sem_variable::equals (c1
->value
, c2
->value
))
1804 /* ... and that they apply to the same fields! */
1805 if (!sem_variable::equals (c1
->index
, c2
->index
))
1812 tree x1
= TREE_OPERAND (t1
, 0);
1813 tree x2
= TREE_OPERAND (t2
, 0);
1814 tree y1
= TREE_OPERAND (t1
, 1);
1815 tree y2
= TREE_OPERAND (t2
, 1);
1817 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1818 return return_false ();
1820 /* Type of the offset on MEM_REF does not matter. */
1821 return return_with_debug (sem_variable::equals (x1
, x2
)
1822 && wi::to_offset (y1
)
1823 == wi::to_offset (y2
));
1828 tree op1
= TREE_OPERAND (t1
, 0);
1829 tree op2
= TREE_OPERAND (t2
, 0);
1830 return sem_variable::equals (op1
, op2
);
1832 /* References to other vars/decls are compared using ipa-ref. */
1835 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1837 return return_false_with_msg ("Declaration mismatch");
1839 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1840 need to process its VAR/FUNCTION references without relying on ipa-ref
1844 return return_false_with_msg ("Declaration mismatch");
1846 /* Integer constants are the same only if the same width of type. */
1847 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1848 return return_false_with_msg ("INTEGER_CST precision mismatch");
1849 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1850 return return_false_with_msg ("INTEGER_CST mode mismatch");
1851 return return_with_debug (tree_int_cst_equal (t1
, t2
));
1853 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1854 return return_false_with_msg ("STRING_CST mode mismatch");
1855 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
1856 return return_false_with_msg ("STRING_CST length mismatch");
1857 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
1858 TREE_STRING_LENGTH (t1
)))
1859 return return_false_with_msg ("STRING_CST mismatch");
1862 /* Fixed constants are the same only if the same width of type. */
1863 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1864 return return_false_with_msg ("FIXED_CST precision mismatch");
1866 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
1867 TREE_FIXED_CST (t2
)));
1869 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
1870 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
1872 /* Real constants are the same only if the same width of type. */
1873 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1874 return return_false_with_msg ("REAL_CST precision mismatch");
1875 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1
),
1876 TREE_REAL_CST (t2
)));
1881 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
1882 return return_false_with_msg ("VECTOR_CST nelts mismatch");
1884 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
1885 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
1886 VECTOR_CST_ELT (t2
, i
)))
1892 case ARRAY_RANGE_REF
:
1894 tree x1
= TREE_OPERAND (t1
, 0);
1895 tree x2
= TREE_OPERAND (t2
, 0);
1896 tree y1
= TREE_OPERAND (t1
, 1);
1897 tree y2
= TREE_OPERAND (t2
, 1);
1899 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
1901 if (!sem_variable::equals (array_ref_low_bound (t1
),
1902 array_ref_low_bound (t2
)))
1904 if (!sem_variable::equals (array_ref_element_size (t1
),
1905 array_ref_element_size (t2
)))
1911 case POINTER_PLUS_EXPR
:
1916 tree x1
= TREE_OPERAND (t1
, 0);
1917 tree x2
= TREE_OPERAND (t2
, 0);
1918 tree y1
= TREE_OPERAND (t1
, 1);
1919 tree y2
= TREE_OPERAND (t2
, 1);
1921 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1925 case VIEW_CONVERT_EXPR
:
1926 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
1927 return return_false ();
1928 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
1930 return return_false_with_msg ("ERROR_MARK");
1932 return return_false_with_msg ("Unknown TREE code reached");
1936 /* Parser function that visits a varpool NODE. */
1939 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1941 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
1945 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1952 /* References independent hash function. */
1955 sem_variable::get_hash (void)
1960 /* All WPA streamed in symbols should have their hashes computed at compile
1961 time. At this point, the constructor may not be in memory at all.
1962 DECL_INITIAL (decl) would be error_mark_node in that case. */
1963 gcc_assert (!node
->lto_file_data
);
1964 tree ctor
= DECL_INITIAL (decl
);
1965 inchash::hash hstate
;
1967 hstate
.add_int (456346417);
1968 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
1969 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
1970 add_expr (ctor
, hstate
);
1971 hash
= hstate
.end ();
1976 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1980 sem_variable::merge (sem_item
*alias_item
)
1982 gcc_assert (alias_item
->type
== VAR
);
1984 if (!sem_item::target_supports_symbol_aliases_p ())
1987 fprintf (dump_file
, "Not unifying; "
1988 "Symbol aliases are not supported by target\n\n");
1992 if (DECL_EXTERNAL (alias_item
->decl
))
1995 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1999 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2001 varpool_node
*original
= get_node ();
2002 varpool_node
*alias
= alias_var
->get_node ();
2003 bool original_discardable
= false;
2005 bool original_address_matters
= original
->address_matters_p ();
2006 bool alias_address_matters
= alias
->address_matters_p ();
2008 /* See if original is in a section that can be discarded if the main
2010 Also consider case where we have resolution info and we know that
2011 original's definition is not going to be used. In this case we can not
2012 create alias to original. */
2013 if (original
->can_be_discarded_p ()
2014 || (node
->resolution
!= LDPR_UNKNOWN
2015 && !decl_binds_to_current_def_p (node
->decl
)))
2016 original_discardable
= true;
2018 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2020 /* Constant pool machinery is not quite ready for aliases.
2021 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2022 For LTO merging does not happen that is an important missing feature.
2023 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2024 flag is dropped and non-local symbol name is assigned. */
2025 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2026 || DECL_IN_CONSTANT_POOL (original
->decl
))
2030 "Not unifying; constant pool variables.\n\n");
2034 /* Do not attempt to mix functions from different user sections;
2035 we do not know what user intends with those. */
2036 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2037 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2038 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2043 "original and alias are in different sections.\n\n");
2047 /* We can not merge if address comparsion metters. */
2048 if (original_address_matters
&& alias_address_matters
2049 && flag_merge_constants
< 2)
2054 "adress of original and alias may be compared.\n\n");
2057 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2060 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2061 "across comdat group boundary\n\n");
2066 if (original_discardable
)
2069 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2070 "target is discardable\n\n");
2076 gcc_assert (!original
->alias
);
2077 gcc_assert (!alias
->alias
);
2079 alias
->analyzed
= false;
2081 DECL_INITIAL (alias
->decl
) = NULL
;
2082 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2084 alias
->need_bounds_init
= false;
2085 alias
->remove_all_references ();
2086 if (TREE_ADDRESSABLE (alias
->decl
))
2087 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2089 varpool_node::create_alias (alias_var
->decl
, decl
);
2090 alias
->resolve_alias (original
);
2093 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
2099 /* Dump symbol to FILE. */
2102 sem_variable::dump_to_file (FILE *file
)
2106 print_node (file
, "", decl
, 0);
2107 fprintf (file
, "\n\n");
2110 unsigned int sem_item_optimizer::class_id
= 0;
2112 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2113 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
2116 bitmap_obstack_initialize (&m_bmstack
);
2119 sem_item_optimizer::~sem_item_optimizer ()
2121 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2124 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2125 it
!= m_classes
.end (); ++it
)
2127 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2128 delete (*it
)->classes
[i
];
2130 (*it
)->classes
.release ();
2136 bitmap_obstack_release (&m_bmstack
);
2139 /* Write IPA ICF summary for symbols. */
2142 sem_item_optimizer::write_summary (void)
2144 unsigned int count
= 0;
2146 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2147 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2150 /* Calculate number of symbols to be serialized. */
2151 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2153 lsei_next_in_partition (&lsei
))
2155 symtab_node
*node
= lsei_node (lsei
);
2157 if (m_symtab_node_map
.get (node
))
2161 streamer_write_uhwi (ob
, count
);
2163 /* Process all of the symbols. */
2164 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2166 lsei_next_in_partition (&lsei
))
2168 symtab_node
*node
= lsei_node (lsei
);
2170 sem_item
**item
= m_symtab_node_map
.get (node
);
2174 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2175 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2177 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2181 streamer_write_char_stream (ob
->main_stream
, 0);
2182 produce_asm (ob
, NULL
);
2183 destroy_output_block (ob
);
2186 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2187 contains LEN bytes. */
2190 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2191 const char *data
, size_t len
)
2193 const lto_function_header
*header
=
2194 (const lto_function_header
*) data
;
2195 const int cfg_offset
= sizeof (lto_function_header
);
2196 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2197 const int string_offset
= main_offset
+ header
->main_size
;
2202 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2203 header
->main_size
, file_data
->mode_table
);
2206 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2207 header
->string_size
, vNULL
);
2209 count
= streamer_read_uhwi (&ib_main
);
2211 for (i
= 0; i
< count
; i
++)
2215 lto_symtab_encoder_t encoder
;
2217 index
= streamer_read_uhwi (&ib_main
);
2218 encoder
= file_data
->symtab_node_encoder
;
2219 node
= lto_symtab_encoder_deref (encoder
, index
);
2221 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2223 gcc_assert (node
->definition
);
2226 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2227 node
->asm_name (), (void *) node
->decl
, node
->order
);
2229 if (is_a
<cgraph_node
*> (node
))
2231 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2233 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2237 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2239 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2243 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2245 lto_data_in_delete (data_in
);
2248 /* Read IPA IPA ICF summary for symbols. */
2251 sem_item_optimizer::read_summary (void)
2253 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2254 lto_file_decl_data
*file_data
;
2257 while ((file_data
= file_data_vec
[j
++]))
2260 const char *data
= lto_get_section_data (file_data
,
2261 LTO_section_ipa_icf
, NULL
, &len
);
2264 read_section (file_data
, data
, len
);
2268 /* Register callgraph and varpool hooks. */
2271 sem_item_optimizer::register_hooks (void)
2273 if (!m_cgraph_node_hooks
)
2274 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2275 (&sem_item_optimizer::cgraph_removal_hook
, this);
2277 if (!m_varpool_node_hooks
)
2278 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2279 (&sem_item_optimizer::varpool_removal_hook
, this);
2282 /* Unregister callgraph and varpool hooks. */
2285 sem_item_optimizer::unregister_hooks (void)
2287 if (m_cgraph_node_hooks
)
2288 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2290 if (m_varpool_node_hooks
)
2291 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2294 /* Adds a CLS to hashtable associated by hash value. */
2297 sem_item_optimizer::add_class (congruence_class
*cls
)
2299 gcc_assert (cls
->members
.length ());
2301 congruence_class_group
*group
= get_group_by_hash (
2302 cls
->members
[0]->get_hash (),
2303 cls
->members
[0]->type
);
2304 group
->classes
.safe_push (cls
);
2307 /* Gets a congruence class group based on given HASH value and TYPE. */
2309 congruence_class_group
*
2310 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2312 congruence_class_group
*item
= XNEW (congruence_class_group
);
2316 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2322 item
->classes
.create (1);
2329 /* Callgraph removal hook called for a NODE with a custom DATA. */
2332 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2334 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2335 optimizer
->remove_symtab_node (node
);
2338 /* Varpool removal hook called for a NODE with a custom DATA. */
2341 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2343 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2344 optimizer
->remove_symtab_node (node
);
2347 /* Remove symtab NODE triggered by symtab removal hooks. */
2350 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2352 gcc_assert (!m_classes
.elements());
2354 m_removed_items_set
.add (node
);
2358 sem_item_optimizer::remove_item (sem_item
*item
)
2360 if (m_symtab_node_map
.get (item
->node
))
2361 m_symtab_node_map
.remove (item
->node
);
2365 /* Removes all callgraph and varpool nodes that are marked by symtab
2369 sem_item_optimizer::filter_removed_items (void)
2371 auto_vec
<sem_item
*> filtered
;
2373 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2375 sem_item
*item
= m_items
[i
];
2377 if (m_removed_items_set
.contains (item
->node
))
2383 if (item
->type
== FUNC
)
2385 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2387 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2390 filtered
.safe_push (item
);
2394 if (!flag_ipa_icf_variables
)
2398 /* Filter out non-readonly variables. */
2399 tree decl
= item
->decl
;
2400 if (TREE_READONLY (decl
))
2401 filtered
.safe_push (item
);
2408 /* Clean-up of released semantic items. */
2411 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2412 m_items
.safe_push (filtered
[i
]);
2415 /* Optimizer entry point which returns true in case it processes
2416 a merge operation. True is returned if there's a merge operation
2420 sem_item_optimizer::execute (void)
2422 filter_removed_items ();
2423 unregister_hooks ();
2426 update_hash_by_addr_refs ();
2427 build_hash_based_classes ();
2430 fprintf (dump_file
, "Dump after hash based groups\n");
2431 dump_cong_classes ();
2433 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2434 m_items
[i
]->init_wpa ();
2436 subdivide_classes_by_equality (true);
2439 fprintf (dump_file
, "Dump after WPA based types groups\n");
2441 dump_cong_classes ();
2443 process_cong_reduction ();
2447 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2449 dump_cong_classes ();
2451 parse_nonsingleton_classes ();
2452 subdivide_classes_by_equality ();
2455 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2457 dump_cong_classes ();
2459 unsigned int prev_class_count
= m_classes_count
;
2461 process_cong_reduction ();
2462 dump_cong_classes ();
2464 bool merged_p
= merge_classes (prev_class_count
);
2466 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2467 symtab_node::dump_table (dump_file
);
2472 /* Function responsible for visiting all potential functions and
2473 read-only variables that can be merged. */
2476 sem_item_optimizer::parse_funcs_and_vars (void)
2480 if (flag_ipa_icf_functions
)
2481 FOR_EACH_DEFINED_FUNCTION (cnode
)
2483 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2486 m_items
.safe_push (f
);
2487 m_symtab_node_map
.put (cnode
, f
);
2490 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2492 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2493 f
->dump_to_file (dump_file
);
2496 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2499 varpool_node
*vnode
;
2501 if (flag_ipa_icf_variables
)
2502 FOR_EACH_DEFINED_VARIABLE (vnode
)
2504 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2508 m_items
.safe_push (v
);
2509 m_symtab_node_map
.put (vnode
, v
);
2514 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2517 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2519 item
->index_in_class
= cls
->members
.length ();
2520 cls
->members
.safe_push (item
);
2524 /* For each semantic item, append hash values of references. */
2527 sem_item_optimizer::update_hash_by_addr_refs ()
2529 /* First, append to hash sensitive references and class type if it need to
2530 be matched for ODR. */
2531 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2533 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2534 if (m_items
[i
]->type
== FUNC
)
2536 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (m_items
[i
]->node
);
2538 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2539 && contains_polymorphic_type_p
2540 (method_class_type (TREE_TYPE (m_items
[i
]->decl
)))
2541 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2542 || ((ipa_node_params_sum
== NULL
2543 || IPA_NODE_REF (cnode
)->descriptors
.is_empty ()
2544 || ipa_is_param_used (IPA_NODE_REF (cnode
), 0))
2545 && static_cast<sem_function
*> (m_items
[i
])
2546 ->compare_polymorphic_p ())))
2549 = method_class_type (TREE_TYPE (m_items
[i
]->decl
));
2550 inchash::hash
hstate (m_items
[i
]->hash
);
2552 if (TYPE_NAME (class_type
)
2553 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2555 (IDENTIFIER_HASH_VALUE
2556 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2558 m_items
[i
]->hash
= hstate
.end ();
2563 /* Once all symbols have enhanced hash value, we can append
2564 hash values of symbols that are seen by IPA ICF and are
2565 references by a semantic item. Newly computed values
2566 are saved to global_hash member variable. */
2567 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2568 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2570 /* Global hash value replace current hash values. */
2571 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2572 m_items
[i
]->hash
= m_items
[i
]->global_hash
;
2575 /* Congruence classes are built by hash value. */
2578 sem_item_optimizer::build_hash_based_classes (void)
2580 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2582 sem_item
*item
= m_items
[i
];
2584 congruence_class_group
*group
= get_group_by_hash (item
->hash
,
2587 if (!group
->classes
.length ())
2590 group
->classes
.safe_push (new congruence_class (class_id
++));
2593 add_item_to_class (group
->classes
[0], item
);
2597 /* Build references according to call graph. */
2600 sem_item_optimizer::build_graph (void)
2602 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2604 sem_item
*item
= m_items
[i
];
2605 m_symtab_node_map
.put (item
->node
, item
);
2608 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2610 sem_item
*item
= m_items
[i
];
2612 if (item
->type
== FUNC
)
2614 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2616 cgraph_edge
*e
= cnode
->callees
;
2619 sem_item
**slot
= m_symtab_node_map
.get
2620 (e
->callee
->ultimate_alias_target ());
2622 item
->add_reference (*slot
);
2628 ipa_ref
*ref
= NULL
;
2629 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2631 sem_item
**slot
= m_symtab_node_map
.get
2632 (ref
->referred
->ultimate_alias_target ());
2634 item
->add_reference (*slot
);
2639 /* Semantic items in classes having more than one element and initialized.
2640 In case of WPA, we load function body. */
2643 sem_item_optimizer::parse_nonsingleton_classes (void)
2645 unsigned int init_called_count
= 0;
2647 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2648 if (m_items
[i
]->cls
->members
.length () > 1)
2650 m_items
[i
]->init ();
2651 init_called_count
++;
2655 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2656 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2659 /* Equality function for semantic items is used to subdivide existing
2660 classes. If IN_WPA, fast equality function is invoked. */
2663 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2665 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2666 it
!= m_classes
.end (); ++it
)
2668 unsigned int class_count
= (*it
)->classes
.length ();
2670 for (unsigned i
= 0; i
< class_count
; i
++)
2672 congruence_class
*c
= (*it
)->classes
[i
];
2674 if (c
->members
.length() > 1)
2676 auto_vec
<sem_item
*> new_vector
;
2678 sem_item
*first
= c
->members
[0];
2679 new_vector
.safe_push (first
);
2681 unsigned class_split_first
= (*it
)->classes
.length ();
2683 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2685 sem_item
*item
= c
->members
[j
];
2687 bool equals
= in_wpa
? first
->equals_wpa (item
,
2688 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2691 new_vector
.safe_push (item
);
2694 bool integrated
= false;
2696 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2698 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2699 bool equals
= in_wpa
? x
->equals_wpa (item
,
2700 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2705 add_item_to_class ((*it
)->classes
[k
], item
);
2713 congruence_class
*c
= new congruence_class (class_id
++);
2715 add_item_to_class (c
, item
);
2717 (*it
)->classes
.safe_push (c
);
2722 // we replace newly created new_vector for the class we've just splitted
2723 c
->members
.release ();
2724 c
->members
.create (new_vector
.length ());
2726 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2727 add_item_to_class (c
, new_vector
[j
]);
2735 /* Subdivide classes by address references that members of the class
2736 reference. Example can be a pair of functions that have an address
2737 taken from a function. If these addresses are different the class
2741 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2743 unsigned newly_created_classes
= 0;
2745 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2746 it
!= m_classes
.end (); ++it
)
2748 unsigned int class_count
= (*it
)->classes
.length ();
2749 auto_vec
<congruence_class
*> new_classes
;
2751 for (unsigned i
= 0; i
< class_count
; i
++)
2753 congruence_class
*c
= (*it
)->classes
[i
];
2755 if (c
->members
.length() > 1)
2757 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2758 symbol_compare_hashmap_traits
> split_map
;
2760 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2762 sem_item
*source_node
= c
->members
[j
];
2764 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2766 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
);
2767 gcc_checking_assert (slot
);
2769 slot
->safe_push (source_node
);
2772 /* If the map contains more than one key, we have to split the map
2774 if (split_map
.elements () != 1)
2776 bool first_class
= true;
2778 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2779 symbol_compare_hashmap_traits
>::iterator it2
= split_map
.begin ();
2780 for (; it2
!= split_map
.end (); ++it2
)
2782 congruence_class
*new_cls
;
2783 new_cls
= new congruence_class (class_id
++);
2785 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2786 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2788 worklist_push (new_cls
);
2789 newly_created_classes
++;
2793 (*it
)->classes
[i
] = new_cls
;
2794 first_class
= false;
2798 new_classes
.safe_push (new_cls
);
2806 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2807 (*it
)->classes
.safe_push (new_classes
[i
]);
2810 return newly_created_classes
;
2813 /* Verify congruence classes if checking is enabled. */
2816 sem_item_optimizer::verify_classes (void)
2819 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2820 it
!= m_classes
.end (); ++it
)
2822 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2824 congruence_class
*cls
= (*it
)->classes
[i
];
2826 gcc_checking_assert (cls
);
2827 gcc_checking_assert (cls
->members
.length () > 0);
2829 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
2831 sem_item
*item
= cls
->members
[j
];
2833 gcc_checking_assert (item
);
2834 gcc_checking_assert (item
->cls
== cls
);
2836 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
2838 sem_usage_pair
*usage
= item
->usages
[k
];
2839 gcc_checking_assert (usage
->item
->index_in_class
<
2840 usage
->item
->cls
->members
.length ());
2848 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2849 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2850 but unused argument. */
2853 sem_item_optimizer::release_split_map (congruence_class
* const &,
2854 bitmap
const &b
, traverse_split_pair
*)
2863 /* Process split operation for a class given as pointer CLS_PTR,
2864 where bitmap B splits congruence class members. DATA is used
2865 as argument of split pair. */
2868 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2869 bitmap
const &b
, traverse_split_pair
*pair
)
2871 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2872 const congruence_class
*splitter_cls
= pair
->cls
;
2874 /* If counted bits are greater than zero and less than the number of members
2875 a group will be splitted. */
2876 unsigned popcount
= bitmap_count_bits (b
);
2878 if (popcount
> 0 && popcount
< cls
->members
.length ())
2880 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
2882 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2884 int target
= bitmap_bit_p (b
, i
);
2885 congruence_class
*tc
= newclasses
[target
];
2887 add_item_to_class (tc
, cls
->members
[i
]);
2890 #ifdef ENABLE_CHECKING
2891 for (unsigned int i
= 0; i
< 2; i
++)
2892 gcc_checking_assert (newclasses
[i
]->members
.length ());
2895 if (splitter_cls
== cls
)
2896 optimizer
->splitter_class_removed
= true;
2898 /* Remove old class from worklist if presented. */
2899 bool in_worklist
= cls
->in_worklist
;
2902 cls
->in_worklist
= false;
2904 congruence_class_group g
;
2905 g
.hash
= cls
->members
[0]->get_hash ();
2906 g
.type
= cls
->members
[0]->type
;
2908 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
2910 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2911 if (slot
->classes
[i
] == cls
)
2913 slot
->classes
.ordered_remove (i
);
2917 /* New class will be inserted and integrated to work list. */
2918 for (unsigned int i
= 0; i
< 2; i
++)
2919 optimizer
->add_class (newclasses
[i
]);
2921 /* Two classes replace one, so that increment just by one. */
2922 optimizer
->m_classes_count
++;
2924 /* If OLD class was presented in the worklist, we remove the class
2925 and replace it will both newly created classes. */
2927 for (unsigned int i
= 0; i
< 2; i
++)
2928 optimizer
->worklist_push (newclasses
[i
]);
2929 else /* Just smaller class is inserted. */
2931 unsigned int smaller_index
= newclasses
[0]->members
.length () <
2932 newclasses
[1]->members
.length () ?
2934 optimizer
->worklist_push (newclasses
[smaller_index
]);
2937 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2939 fprintf (dump_file
, " congruence class splitted:\n");
2940 cls
->dump (dump_file
, 4);
2942 fprintf (dump_file
, " newly created groups:\n");
2943 for (unsigned int i
= 0; i
< 2; i
++)
2944 newclasses
[i
]->dump (dump_file
, 4);
2947 /* Release class if not presented in work list. */
2956 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2957 Bitmap stack BMSTACK is used for bitmap allocation. */
2960 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2963 hash_map
<congruence_class
*, bitmap
> split_map
;
2965 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2967 sem_item
*item
= cls
->members
[i
];
2969 /* Iterate all usages that have INDEX as usage of the item. */
2970 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2972 sem_usage_pair
*usage
= item
->usages
[j
];
2974 if (usage
->index
!= index
)
2977 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2982 b
= BITMAP_ALLOC (&m_bmstack
);
2983 split_map
.put (usage
->item
->cls
, b
);
2989 gcc_checking_assert (usage
->item
->cls
);
2990 gcc_checking_assert (usage
->item
->index_in_class
<
2991 usage
->item
->cls
->members
.length ());
2994 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2998 traverse_split_pair pair
;
2999 pair
.optimizer
= this;
3002 splitter_class_removed
= false;
3004 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
3006 /* Bitmap clean-up. */
3008 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
3011 /* Every usage of a congruence class CLS is a candidate that can split the
3012 collection of classes. Bitmap stack BMSTACK is used for bitmap
3016 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3021 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3023 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3024 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3026 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3028 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3029 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
3032 do_congruence_step_for_index (cls
, i
);
3034 if (splitter_class_removed
)
3038 BITMAP_FREE (usage
);
3041 /* Adds a newly created congruence class CLS to worklist. */
3044 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3046 /* Return if the class CLS is already presented in work list. */
3047 if (cls
->in_worklist
)
3050 cls
->in_worklist
= true;
3051 worklist
.push_back (cls
);
3054 /* Pops a class from worklist. */
3057 sem_item_optimizer::worklist_pop (void)
3059 congruence_class
*cls
;
3061 while (!worklist
.empty ())
3063 cls
= worklist
.front ();
3064 worklist
.pop_front ();
3065 if (cls
->in_worklist
)
3067 cls
->in_worklist
= false;
3073 /* Work list item was already intended to be removed.
3074 The only reason for doing it is to split a class.
3075 Thus, the class CLS is deleted. */
3083 /* Iterative congruence reduction function. */
3086 sem_item_optimizer::process_cong_reduction (void)
3088 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3089 it
!= m_classes
.end (); ++it
)
3090 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3091 if ((*it
)->classes
[i
]->is_class_used ())
3092 worklist_push ((*it
)->classes
[i
]);
3095 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3096 (unsigned long) worklist
.size ());
3098 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3099 fprintf (dump_file
, "Congruence class reduction\n");
3101 congruence_class
*cls
;
3103 /* Process complete congruence reduction. */
3104 while ((cls
= worklist_pop ()) != NULL
)
3105 do_congruence_step (cls
);
3107 /* Subdivide newly created classes according to references. */
3108 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3111 fprintf (dump_file
, "Address reference subdivision created: %u "
3112 "new classes.\n", new_classes
);
3115 /* Debug function prints all informations about congruence classes. */
3118 sem_item_optimizer::dump_cong_classes (void)
3124 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3125 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
3127 /* Histogram calculation. */
3128 unsigned int max_index
= 0;
3129 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3131 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3132 it
!= m_classes
.end (); ++it
)
3134 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3136 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3144 "Class size histogram [num of members]: number of classe number of classess\n");
3146 for (unsigned int i
= 0; i
<= max_index
; i
++)
3148 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3150 fprintf (dump_file
, "\n\n");
3153 if (dump_flags
& TDF_DETAILS
)
3154 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3155 it
!= m_classes
.end (); ++it
)
3157 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
3159 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3161 (*it
)->classes
[i
]->dump (dump_file
, 4);
3163 if(i
< (*it
)->classes
.length () - 1)
3164 fprintf (dump_file
, " ");
3171 /* After reduction is done, we can declare all items in a group
3172 to be equal. PREV_CLASS_COUNT is start number of classes
3173 before reduction. True is returned if there's a merge operation
3177 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3179 unsigned int item_count
= m_items
.length ();
3180 unsigned int class_count
= m_classes_count
;
3181 unsigned int equal_items
= item_count
- class_count
;
3183 unsigned int non_singular_classes_count
= 0;
3184 unsigned int non_singular_classes_sum
= 0;
3186 bool merged_p
= false;
3188 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3189 it
!= m_classes
.end (); ++it
)
3190 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3192 congruence_class
*c
= (*it
)->classes
[i
];
3193 if (c
->members
.length () > 1)
3195 non_singular_classes_count
++;
3196 non_singular_classes_sum
+= c
->members
.length ();
3202 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3203 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3204 prev_class_count
, class_count
);
3205 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3206 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3207 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3208 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3209 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3210 non_singular_classes_count
: 0.0f
,
3211 non_singular_classes_count
);
3212 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3213 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3214 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3217 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3218 it
!= m_classes
.end (); ++it
)
3219 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3221 congruence_class
*c
= (*it
)->classes
[i
];
3223 if (c
->members
.length () == 1)
3226 gcc_assert (c
->members
.length ());
3228 sem_item
*source
= c
->members
[0];
3230 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
3232 sem_item
*alias
= c
->members
[j
];
3236 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3237 xstrdup_for_dump (source
->node
->name ()),
3238 xstrdup_for_dump (alias
->node
->name ()));
3239 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3240 xstrdup_for_dump (source
->node
->asm_name ()),
3241 xstrdup_for_dump (alias
->node
->asm_name ()));
3244 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3248 "Merge operation is skipped due to no_icf "
3254 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3256 source
->dump_to_file (dump_file
);
3257 alias
->dump_to_file (dump_file
);
3260 merged_p
|= source
->merge (alias
);
3267 /* Dump function prints all class members to a FILE with an INDENT. */
3270 congruence_class::dump (FILE *file
, unsigned int indent
) const
3272 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3273 id
, members
[0]->get_hash (), members
.length ());
3275 FPUTS_SPACES (file
, indent
+ 2, "");
3276 for (unsigned i
= 0; i
< members
.length (); i
++)
3277 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3278 (void *) members
[i
]->decl
,
3279 members
[i
]->node
->order
);
3281 fprintf (file
, "\n");
3284 /* Returns true if there's a member that is used from another group. */
3287 congruence_class::is_class_used (void)
3289 for (unsigned int i
= 0; i
< members
.length (); i
++)
3290 if (members
[i
]->usages
.length ())
3296 /* Generate pass summary for IPA ICF pass. */
3299 ipa_icf_generate_summary (void)
3302 optimizer
= new sem_item_optimizer ();
3304 optimizer
->register_hooks ();
3305 optimizer
->parse_funcs_and_vars ();
3308 /* Write pass summary for IPA ICF pass. */
3311 ipa_icf_write_summary (void)
3313 gcc_assert (optimizer
);
3315 optimizer
->write_summary ();
3318 /* Read pass summary for IPA ICF pass. */
3321 ipa_icf_read_summary (void)
3324 optimizer
= new sem_item_optimizer ();
3326 optimizer
->read_summary ();
3327 optimizer
->register_hooks ();
3330 /* Semantic equality exection function. */
3333 ipa_icf_driver (void)
3335 gcc_assert (optimizer
);
3337 bool merged_p
= optimizer
->execute ();
3342 return merged_p
? TODO_remove_functions
: 0;
3345 const pass_data pass_data_ipa_icf
=
3347 IPA_PASS
, /* type */
3349 OPTGROUP_IPA
, /* optinfo_flags */
3350 TV_IPA_ICF
, /* tv_id */
3351 0, /* properties_required */
3352 0, /* properties_provided */
3353 0, /* properties_destroyed */
3354 0, /* todo_flags_start */
3355 0, /* todo_flags_finish */
3358 class pass_ipa_icf
: public ipa_opt_pass_d
3361 pass_ipa_icf (gcc::context
*ctxt
)
3362 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3363 ipa_icf_generate_summary
, /* generate_summary */
3364 ipa_icf_write_summary
, /* write_summary */
3365 ipa_icf_read_summary
, /* read_summary */
3367 write_optimization_summary */
3369 read_optimization_summary */
3370 NULL
, /* stmt_fixup */
3371 0, /* function_transform_todo_flags_start */
3372 NULL
, /* function_transform */
3373 NULL
) /* variable_transform */
3376 /* opt_pass methods: */
3377 virtual bool gate (function
*)
3379 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3382 virtual unsigned int execute (function
*)
3384 return ipa_icf_driver();
3386 }; // class pass_ipa_icf
3388 } // ipa_icf namespace
3391 make_pass_ipa_icf (gcc::context
*ctxt
)
3393 return new ipa_icf::pass_ipa_icf (ctxt
);