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
)
276 arg_types
.create (0);
278 bb_sorted
.create (0);
281 /* Constructor based on callgraph node _NODE with computed hash _HASH.
282 Bitmap STACK is used for memory allocation. */
283 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
284 bitmap_obstack
*stack
):
285 sem_item (FUNC
, node
, hash
, stack
),
286 m_checker (NULL
), m_compared_func (NULL
)
288 arg_types
.create (0);
290 bb_sorted
.create (0);
293 sem_function::~sem_function ()
295 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
296 delete (bb_sorted
[i
]);
298 arg_types
.release ();
300 bb_sorted
.release ();
303 /* Calculates hash value based on a BASIC_BLOCK. */
306 sem_function::get_bb_hash (const sem_bb
*basic_block
)
308 inchash::hash hstate
;
310 hstate
.add_int (basic_block
->nondbg_stmt_count
);
311 hstate
.add_int (basic_block
->edge_count
);
313 return hstate
.end ();
316 /* References independent hash function. */
319 sem_function::get_hash (void)
323 inchash::hash hstate
;
324 hstate
.add_int (177454); /* Random number for function type. */
326 hstate
.add_int (arg_count
);
327 hstate
.add_int (cfg_checksum
);
328 hstate
.add_int (gcode_hash
);
330 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
331 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
333 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
334 hstate
.add_int (bb_sizes
[i
]);
337 /* Add common features of declaration itself. */
338 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
340 (cl_target_option_hash
341 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
342 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
343 (cl_optimization_hash
344 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
345 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (decl
));
346 hstate
.add_flag (DECL_DECLARED_INLINE_P (decl
));
347 hstate
.add_flag (DECL_IS_OPERATOR_NEW (decl
));
348 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
349 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
351 hash
= hstate
.end ();
357 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
358 point to a same function. Comparison can be skipped if IGNORED_NODES
359 contains these nodes. ADDRESS indicate if address is taken. */
362 sem_item::compare_cgraph_references (
363 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
364 symtab_node
*n1
, symtab_node
*n2
, bool address
)
366 enum availability avail1
, avail2
;
371 /* Never match variable and function. */
372 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
375 /* Merging two definitions with a reference to equivalent vtables, but
376 belonging to a different type may result in ipa-polymorphic-call analysis
377 giving a wrong answer about the dynamic type of instance. */
378 if (is_a
<varpool_node
*> (n1
)
379 && (DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
380 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
381 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
382 DECL_CONTEXT (n2
->decl
))))
383 return return_false_with_msg
384 ("references to virtual tables can not be merged");
386 if (address
&& n1
->equal_address_to (n2
) == 1)
388 if (!address
&& n1
->semantically_equivalent_p (n2
))
391 n1
= n1
->ultimate_alias_target (&avail1
);
392 n2
= n2
->ultimate_alias_target (&avail2
);
394 if (avail1
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
395 && avail2
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
398 return return_false_with_msg ("different references");
401 /* If cgraph edges E1 and E2 are indirect calls, verify that
402 ECF flags are the same. */
404 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
406 if (e1
->indirect_info
&& e2
->indirect_info
)
408 int e1_flags
= e1
->indirect_info
->ecf_flags
;
409 int e2_flags
= e2
->indirect_info
->ecf_flags
;
411 if (e1_flags
!= e2_flags
)
412 return return_false_with_msg ("ICF flags are different");
414 else if (e1
->indirect_info
|| e2
->indirect_info
)
420 /* Fast equality function based on knowledge known in WPA. */
423 sem_function::equals_wpa (sem_item
*item
,
424 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
426 gcc_assert (item
->type
== FUNC
);
428 m_compared_func
= static_cast<sem_function
*> (item
);
430 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
431 return return_false_with_msg ("different number of arguments");
433 /* Compare special function DECL attributes. */
434 if (DECL_FUNCTION_PERSONALITY (decl
)
435 != DECL_FUNCTION_PERSONALITY (item
->decl
))
436 return return_false_with_msg ("function personalities are different");
438 if (DECL_DISREGARD_INLINE_LIMITS (decl
)
439 != DECL_DISREGARD_INLINE_LIMITS (item
->decl
))
440 return return_false_with_msg ("DECL_DISREGARD_INLINE_LIMITS are different");
442 if (DECL_DECLARED_INLINE_P (decl
) != DECL_DECLARED_INLINE_P (item
->decl
))
443 return return_false_with_msg ("inline attributes are different");
445 if (DECL_IS_OPERATOR_NEW (decl
) != DECL_IS_OPERATOR_NEW (item
->decl
))
446 return return_false_with_msg ("operator new flags are different");
448 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
449 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
450 return return_false_with_msg ("intrument function entry exit "
451 "attributes are different");
453 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
454 return return_false_with_msg ("no stack limit attributes are different");
456 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
457 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
459 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
460 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
462 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
463 return return_false_with_msg ("decl_or_type flags are different");
465 /* Do not match polymorphic constructors of different types. They calls
466 type memory location for ipa-polymorphic-call and we do not want
467 it to get confused by wrong type. */
468 if (DECL_CXX_CONSTRUCTOR_P (decl
)
469 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
471 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
472 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
473 else if (!func_checker::compatible_polymorphic_types_p
474 (method_class_type (TREE_TYPE (decl
)),
475 method_class_type (TREE_TYPE (item
->decl
)), false))
476 return return_false_with_msg ("ctor polymorphic type mismatch");
479 /* Checking function TARGET and OPTIMIZATION flags. */
480 cl_target_option
*tar1
= target_opts_for_fn (decl
);
481 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
483 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
485 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
487 fprintf (dump_file
, "target flags difference");
488 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
491 return return_false_with_msg ("Target flags are different");
494 cl_optimization
*opt1
= opts_for_fn (decl
);
495 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
497 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
499 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
501 fprintf (dump_file
, "optimization flags difference");
502 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
505 return return_false_with_msg ("optimization flags are different");
508 /* Result type checking. */
509 if (!func_checker::compatible_types_p (result_type
,
510 m_compared_func
->result_type
))
511 return return_false_with_msg ("result types are different");
513 /* Checking types of arguments. */
514 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
516 /* This guard is here for function pointer with attributes (pr59927.c). */
517 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
518 return return_false_with_msg ("NULL argument type");
520 if (!func_checker::compatible_types_p (arg_types
[i
],
521 m_compared_func
->arg_types
[i
]))
522 return return_false_with_msg ("argument type is different");
523 if (POINTER_TYPE_P (arg_types
[i
])
524 && (TYPE_RESTRICT (arg_types
[i
])
525 != TYPE_RESTRICT (m_compared_func
->arg_types
[i
])))
526 return return_false_with_msg ("argument restrict flag mismatch");
529 if (node
->num_references () != item
->node
->num_references ())
530 return return_false_with_msg ("different number of references");
532 if (comp_type_attributes (TREE_TYPE (decl
),
533 TREE_TYPE (item
->decl
)) != 1)
534 return return_false_with_msg ("different type attributes");
536 /* The type of THIS pointer type memory location for
537 ipa-polymorphic-call-analysis. */
538 if (opt_for_fn (decl
, flag_devirtualize
)
539 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
540 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
541 && (ipa_node_params_sum
== NULL
542 || IPA_NODE_REF (get_node ())->descriptors
.is_empty ()
543 || ipa_is_param_used (IPA_NODE_REF (get_node ()),
545 && compare_polymorphic_p ())
547 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
548 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
549 if (!func_checker::compatible_polymorphic_types_p
550 (method_class_type (TREE_TYPE (decl
)),
551 method_class_type (TREE_TYPE (item
->decl
)), false))
552 return return_false_with_msg ("THIS pointer ODR type mismatch");
555 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
556 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
558 item
->node
->iterate_reference (i
, ref2
);
560 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
,
562 ref
->address_matters_p ()))
566 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
567 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
571 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
,
575 e1
= e1
->next_callee
;
576 e2
= e2
->next_callee
;
580 return return_false_with_msg ("different number of edges");
585 /* Update hash by address sensitive references. We iterate over all
586 sensitive references (address_matters_p) and we hash ultime alias
587 target of these nodes, which can improve a semantic item hash.
588 TODO: stronger SCC based hashing would be desirable here. */
591 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
592 sem_item
*> &m_symtab_node_map
)
595 inchash::hash
hstate (hash
);
596 for (unsigned i
= 0; i
< node
->num_references (); i
++)
598 ref
= node
->iterate_reference (i
, ref
);
599 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
600 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
603 if (is_a
<cgraph_node
*> (node
))
605 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
608 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
610 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
614 hash
= hstate
.end ();
617 /* Update hash by computed local hash values taken from different
621 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
622 sem_item
*> &m_symtab_node_map
)
624 inchash::hash
state (hash
);
625 for (unsigned j
= 0; j
< node
->num_references (); j
++)
628 ref
= node
->iterate_reference (j
, ref
);
629 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
631 state
.merge_hash ((*result
)->hash
);
636 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
639 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
641 state
.merge_hash ((*result
)->hash
);
645 global_hash
= state
.end ();
648 /* Returns true if the item equals to ITEM given as argument. */
651 sem_function::equals (sem_item
*item
,
652 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
654 gcc_assert (item
->type
== FUNC
);
655 bool eq
= equals_private (item
, ignored_nodes
);
657 if (m_checker
!= NULL
)
663 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
665 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
666 xstrdup_for_dump (node
->name()),
667 xstrdup_for_dump (item
->node
->name ()),
670 xstrdup_for_dump (node
->asm_name ()),
671 xstrdup_for_dump (item
->node
->asm_name ()),
672 eq
? "true" : "false");
677 /* Processes function equality comparison. */
680 sem_function::equals_private (sem_item
*item
,
681 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
683 if (item
->type
!= FUNC
)
686 basic_block bb1
, bb2
;
688 edge_iterator ei1
, ei2
;
692 m_compared_func
= static_cast<sem_function
*> (item
);
694 gcc_assert (decl
!= item
->decl
);
696 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
697 || edge_count
!= m_compared_func
->edge_count
698 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
699 return return_false ();
701 if (!equals_wpa (item
, ignored_nodes
))
704 /* Checking function arguments. */
705 tree decl1
= DECL_ATTRIBUTES (decl
);
706 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
708 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
709 compare_polymorphic_p (),
712 &m_compared_func
->refs_set
);
716 return return_false ();
718 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
719 return return_false ();
721 tree attr_value1
= TREE_VALUE (decl1
);
722 tree attr_value2
= TREE_VALUE (decl2
);
724 if (attr_value1
&& attr_value2
)
726 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
727 TREE_VALUE (attr_value2
));
729 return return_false_with_msg ("attribute values are different");
731 else if (!attr_value1
&& !attr_value2
)
734 return return_false ();
736 decl1
= TREE_CHAIN (decl1
);
737 decl2
= TREE_CHAIN (decl2
);
741 return return_false();
743 for (arg1
= DECL_ARGUMENTS (decl
),
744 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
745 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
746 if (!m_checker
->compare_decl (arg1
, arg2
))
747 return return_false ();
749 /* Fill-up label dictionary. */
750 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
752 m_checker
->parse_labels (bb_sorted
[i
]);
753 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
756 /* Checking all basic blocks. */
757 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
758 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
759 return return_false();
761 dump_message ("All BBs are equal\n");
763 auto_vec
<int> bb_dict
;
765 /* Basic block edges check. */
766 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
768 bb1
= bb_sorted
[i
]->bb
;
769 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
771 ei2
= ei_start (bb2
->preds
);
773 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
777 if (e1
->flags
!= e2
->flags
)
778 return return_false_with_msg ("flags comparison returns false");
780 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
781 return return_false_with_msg ("edge comparison returns false");
783 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
784 return return_false_with_msg ("BB comparison returns false");
786 if (!m_checker
->compare_edge (e1
, e2
))
787 return return_false_with_msg ("edge comparison returns false");
793 /* Basic block PHI nodes comparison. */
794 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
795 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
796 return return_false_with_msg ("PHI node comparison returns false");
801 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
802 Helper for call_for_symbol_thunks_and_aliases. */
805 set_local (cgraph_node
*node
, void *data
)
807 node
->local
.local
= data
!= NULL
;
811 /* TREE_ADDRESSABLE of NODE to true.
812 Helper for call_for_symbol_thunks_and_aliases. */
815 set_addressable (varpool_node
*node
, void *)
817 TREE_ADDRESSABLE (node
->decl
) = 1;
821 /* Clear DECL_RTL of NODE.
822 Helper for call_for_symbol_thunks_and_aliases. */
825 clear_decl_rtl (symtab_node
*node
, void *)
827 SET_DECL_RTL (node
->decl
, NULL
);
831 /* Redirect all callers of N and its aliases to TO. Remove aliases if
832 possible. Return number of redirections made. */
835 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
839 cgraph_edge
*e
= n
->callers
;
843 /* Redirecting thunks to interposable symbols or symbols in other sections
844 may not be supported by target output code. Play safe for now and
845 punt on redirection. */
846 if (!e
->caller
->thunk
.thunk_p
)
848 struct cgraph_edge
*nexte
= e
->next_caller
;
849 e
->redirect_callee (to
);
856 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
858 bool removed
= false;
859 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
861 if ((DECL_COMDAT_GROUP (n
->decl
)
862 && (DECL_COMDAT_GROUP (n
->decl
)
863 == DECL_COMDAT_GROUP (n_alias
->decl
)))
864 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
865 && n
->get_availability () > AVAIL_INTERPOSABLE
))
867 nredirected
+= redirect_all_callers (n_alias
, to
);
868 if (n_alias
->can_remove_if_no_direct_calls_p ()
869 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
871 && !n_alias
->has_aliases_p ())
880 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
884 sem_function::merge (sem_item
*alias_item
)
886 gcc_assert (alias_item
->type
== FUNC
);
888 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
890 cgraph_node
*original
= get_node ();
891 cgraph_node
*local_original
= NULL
;
892 cgraph_node
*alias
= alias_func
->get_node ();
894 bool create_wrapper
= false;
895 bool create_alias
= false;
896 bool redirect_callers
= false;
899 bool original_discardable
= false;
900 bool original_discarded
= false;
902 bool original_address_matters
= original
->address_matters_p ();
903 bool alias_address_matters
= alias
->address_matters_p ();
905 if (DECL_EXTERNAL (alias
->decl
))
908 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
912 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
913 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
918 "DECL_NO_INLINE_WARNING mismatch.\n\n");
922 /* Do not attempt to mix functions from different user sections;
923 we do not know what user intends with those. */
924 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
925 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
926 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
931 "original and alias are in different sections.\n\n");
935 /* See if original is in a section that can be discarded if the main
936 symbol is not used. */
938 if (original
->can_be_discarded_p ())
939 original_discardable
= true;
940 /* Also consider case where we have resolution info and we know that
941 original's definition is not going to be used. In this case we can not
942 create alias to original. */
943 if (node
->resolution
!= LDPR_UNKNOWN
944 && !decl_binds_to_current_def_p (node
->decl
))
945 original_discardable
= original_discarded
= true;
947 /* Creating a symtab alias is the optimal way to merge.
948 It however can not be used in the following cases:
950 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
951 2) if ORIGINAL is in a section that may be discarded by linker or if
952 it is an external functions where we can not create an alias
953 (ORIGINAL_DISCARDABLE)
954 3) if target do not support symbol aliases.
955 4) original and alias lie in different comdat groups.
957 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
958 and/or redirect all callers from ALIAS to ORIGINAL. */
959 if ((original_address_matters
&& alias_address_matters
)
960 || (original_discardable
961 && (!DECL_COMDAT_GROUP (alias
->decl
)
962 || (DECL_COMDAT_GROUP (alias
->decl
)
963 != DECL_COMDAT_GROUP (original
->decl
))))
964 || original_discarded
965 || !sem_item::target_supports_symbol_aliases_p ()
966 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
968 /* First see if we can produce wrapper. */
970 /* Do not turn function in one comdat group into wrapper to another
971 comdat group. Other compiler producing the body of the
972 another comdat group may make opossite decision and with unfortunate
973 linker choices this may close a loop. */
974 if (DECL_COMDAT_GROUP (original
->decl
) && DECL_COMDAT_GROUP (alias
->decl
)
975 && (DECL_COMDAT_GROUP (alias
->decl
)
976 != DECL_COMDAT_GROUP (original
->decl
)))
980 "Wrapper cannot be created because of COMDAT\n");
982 else if (DECL_STATIC_CHAIN (alias
->decl
))
986 "Can not create wrapper of nested functions.\n");
988 /* TODO: We can also deal with variadic functions never calling
990 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
994 "can not create wrapper of stdarg function.\n");
996 else if (inline_summaries
997 && inline_summaries
->get (alias
)->self_size
<= 2)
1000 fprintf (dump_file
, "Wrapper creation is not "
1001 "profitable (function is too small).\n");
1003 /* If user paid attention to mark function noinline, assume it is
1004 somewhat special and do not try to turn it into a wrapper that can
1005 not be undone by inliner. */
1006 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1009 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1012 create_wrapper
= true;
1014 /* We can redirect local calls in the case both alias and orignal
1015 are not interposable. */
1017 = alias
->get_availability () > AVAIL_INTERPOSABLE
1018 && original
->get_availability () > AVAIL_INTERPOSABLE
1019 && !alias
->instrumented_version
;
1021 if (!redirect_callers
&& !create_wrapper
)
1024 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1025 "produce wrapper\n\n");
1029 /* Work out the symbol the wrapper should call.
1030 If ORIGINAL is interposable, we need to call a local alias.
1031 Also produce local alias (if possible) as an optimization.
1033 Local aliases can not be created inside comdat groups because that
1034 prevents inlining. */
1035 if (!original_discardable
&& !original
->get_comdat_group ())
1038 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1040 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1041 local_original
= original
;
1043 /* If we can not use local alias, fallback to the original
1045 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1046 local_original
= original
;
1048 /* If original is COMDAT local, we can not really redirect calls outside
1049 of its comdat group to it. */
1050 if (original
->comdat_local_p ())
1051 redirect_callers
= false;
1052 if (!local_original
)
1055 fprintf (dump_file
, "Not unifying; "
1056 "can not produce local alias.\n\n");
1060 if (!redirect_callers
&& !create_wrapper
)
1063 fprintf (dump_file
, "Not unifying; "
1064 "can not redirect callers nor produce a wrapper\n\n");
1068 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1070 && !alias
->can_remove_if_no_direct_calls_p ())
1073 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1074 "function has other uses than direct calls\n\n");
1079 create_alias
= true;
1081 if (redirect_callers
)
1083 int nredirected
= redirect_all_callers (alias
, local_original
);
1087 alias
->icf_merged
= true;
1088 local_original
->icf_merged
= true;
1090 if (dump_file
&& nredirected
)
1091 fprintf (dump_file
, "%i local calls have been "
1092 "redirected.\n", nredirected
);
1095 /* If all callers was redirected, do not produce wrapper. */
1096 if (alias
->can_remove_if_no_direct_calls_p ()
1097 && !alias
->has_aliases_p ())
1099 create_wrapper
= false;
1102 gcc_assert (!create_alias
);
1104 else if (create_alias
)
1106 alias
->icf_merged
= true;
1108 /* Remove the function's body. */
1109 ipa_merge_profiles (original
, alias
);
1110 alias
->release_body (true);
1112 /* Notice global symbol possibly produced RTL. */
1113 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1116 /* Create the alias. */
1117 cgraph_node::create_alias (alias_func
->decl
, decl
);
1118 alias
->resolve_alias (original
);
1120 original
->call_for_symbol_thunks_and_aliases
1121 (set_local
, (void *)(size_t) original
->local_p (), true);
1124 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1128 gcc_assert (!create_alias
);
1129 alias
->icf_merged
= true;
1130 local_original
->icf_merged
= true;
1132 ipa_merge_profiles (local_original
, alias
, true);
1133 alias
->create_wrapper (local_original
);
1136 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1139 /* It's possible that redirection can hit thunks that block
1140 redirection opportunities. */
1141 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1142 original
->icf_merged
= true;
1144 /* Inform the inliner about cross-module merging. */
1145 if ((original
->lto_file_data
|| alias
->lto_file_data
)
1146 && original
->lto_file_data
!= alias
->lto_file_data
)
1147 local_original
->merged
= original
->merged
= true;
1151 ipa_merge_profiles (original
, alias
);
1152 alias
->release_body ();
1154 alias
->body_removed
= true;
1155 alias
->icf_merged
= true;
1157 fprintf (dump_file
, "Unified; Function body was removed.\n");
1163 /* Semantic item initialization function. */
1166 sem_function::init (void)
1169 get_node ()->get_untransformed_body ();
1171 tree fndecl
= node
->decl
;
1172 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1175 gcc_assert (SSANAMES (func
));
1177 ssa_names_size
= SSANAMES (func
)->length ();
1181 region_tree
= func
->eh
->region_tree
;
1183 /* iterating all function arguments. */
1184 arg_count
= count_formal_params (fndecl
);
1186 edge_count
= n_edges_for_fn (func
);
1187 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1189 inchash::hash hstate
;
1192 FOR_EACH_BB_FN (bb
, func
)
1194 unsigned nondbg_stmt_count
= 0;
1197 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1199 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1202 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1205 gimple stmt
= gsi_stmt (gsi
);
1207 if (gimple_code (stmt
) != GIMPLE_DEBUG
1208 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1210 hash_stmt (stmt
, hstate
);
1211 nondbg_stmt_count
++;
1215 gcode_hash
= hstate
.end ();
1216 bb_sizes
.safe_push (nondbg_stmt_count
);
1218 /* Inserting basic block to hash table. */
1219 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1220 EDGE_COUNT (bb
->preds
)
1221 + EDGE_COUNT (bb
->succs
));
1223 bb_sorted
.safe_push (semantic_bb
);
1229 /* Accumulate to HSTATE a hash of expression EXP.
1230 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1231 and DECL equality classes. */
1234 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1236 if (exp
== NULL_TREE
)
1238 hstate
.merge_hash (0);
1242 /* Handled component can be matched in a cureful way proving equivalence
1243 even if they syntactically differ. Just skip them. */
1245 while (handled_component_p (exp
))
1246 exp
= TREE_OPERAND (exp
, 0);
1248 enum tree_code code
= TREE_CODE (exp
);
1249 hstate
.add_int (code
);
1253 /* Use inchash::add_expr for everything that is LTO stable. */
1261 inchash::add_expr (exp
, hstate
);
1265 unsigned HOST_WIDE_INT idx
;
1268 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1270 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1272 add_expr (value
, hstate
);
1277 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1283 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1286 case POINTER_PLUS_EXPR
:
1289 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1290 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1294 inchash::hash one
, two
;
1295 add_expr (TREE_OPERAND (exp
, 0), one
);
1296 add_expr (TREE_OPERAND (exp
, 1), two
);
1297 hstate
.add_commutative (one
, two
);
1301 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1302 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1308 /* Accumulate to HSTATE a hash of type t.
1309 TYpes that may end up being compatible after LTO type merging needs to have
1313 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1315 if (type
== NULL_TREE
)
1317 hstate
.merge_hash (0);
1321 type
= TYPE_MAIN_VARIANT (type
);
1322 if (TYPE_CANONICAL (type
))
1323 type
= TYPE_CANONICAL (type
);
1325 if (!AGGREGATE_TYPE_P (type
))
1326 hstate
.add_int (TYPE_MODE (type
));
1328 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1330 hstate
.add_int (COMPLEX_TYPE
);
1331 sem_item::add_type (TREE_TYPE (type
), hstate
);
1333 else if (INTEGRAL_TYPE_P (type
))
1335 hstate
.add_int (INTEGER_TYPE
);
1336 hstate
.add_flag (TYPE_UNSIGNED (type
));
1337 hstate
.add_int (TYPE_PRECISION (type
));
1339 else if (VECTOR_TYPE_P (type
))
1341 hstate
.add_int (VECTOR_TYPE
);
1342 hstate
.add_int (TYPE_PRECISION (type
));
1343 sem_item::add_type (TREE_TYPE (type
), hstate
);
1345 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1347 hstate
.add_int (ARRAY_TYPE
);
1348 /* Do not hash size, so complete and incomplete types can match. */
1349 sem_item::add_type (TREE_TYPE (type
), hstate
);
1351 else if (RECORD_OR_UNION_TYPE_P (type
))
1353 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1357 inchash::hash hstate2
;
1362 hstate2
.add_int (RECORD_TYPE
);
1363 gcc_assert (COMPLETE_TYPE_P (type
));
1365 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1366 if (TREE_CODE (f
) == FIELD_DECL
)
1368 add_type (TREE_TYPE (f
), hstate2
);
1372 hstate2
.add_int (nf
);
1373 hash
= hstate2
.end ();
1374 hstate
.add_wide_int (hash
);
1375 optimizer
->m_type_hash_cache
.put (type
, hash
);
1378 hstate
.add_wide_int (*val
);
1382 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1385 sem_function::hash_stmt (gimple stmt
, inchash::hash
&hstate
)
1387 enum gimple_code code
= gimple_code (stmt
);
1389 hstate
.add_int (code
);
1394 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1397 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1398 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1399 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1401 inchash::hash one
, two
;
1403 add_expr (gimple_assign_rhs1 (stmt
), one
);
1404 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1405 add_expr (gimple_assign_rhs2 (stmt
), two
);
1406 hstate
.add_commutative (one
, two
);
1407 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1409 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1410 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1412 add_expr (gimple_assign_lhs (stmt
), hstate
);
1413 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1416 /* ... fall through ... */
1422 /* All these statements are equivalent if their operands are. */
1423 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1425 add_expr (gimple_op (stmt
, i
), hstate
);
1426 if (gimple_op (stmt
, i
))
1427 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1435 /* Return true if polymorphic comparison must be processed. */
1438 sem_function::compare_polymorphic_p (void)
1440 struct cgraph_edge
*e
;
1442 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1444 if (get_node ()->indirect_calls
!= NULL
)
1446 /* TODO: We can do simple propagation determining what calls may lead to
1447 a polymorphic call. */
1448 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1449 if (e
->callee
->definition
1450 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1455 /* For a given call graph NODE, the function constructs new
1456 semantic function item. */
1459 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1461 tree fndecl
= node
->decl
;
1462 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1464 /* TODO: add support for thunks. */
1466 if (!func
|| !node
->has_gimple_body_p ())
1469 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1472 sem_function
*f
= new sem_function (node
, 0, stack
);
1479 /* Parses function arguments and result type. */
1482 sem_function::parse_tree_args (void)
1486 if (arg_types
.exists ())
1487 arg_types
.release ();
1489 arg_types
.create (4);
1490 tree fnargs
= DECL_ARGUMENTS (decl
);
1492 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
1493 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
1495 /* Function result type. */
1496 result
= DECL_RESULT (decl
);
1497 result_type
= result
? TREE_TYPE (result
) : NULL
;
1499 /* During WPA, we can get arguments by following method. */
1502 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
1503 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
1504 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
1506 result_type
= TREE_TYPE (TREE_TYPE (decl
));
1510 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1511 return true if phi nodes are semantically equivalent in these blocks . */
1514 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1516 gphi_iterator si1
, si2
;
1518 unsigned size1
, size2
, i
;
1522 gcc_assert (bb1
!= NULL
);
1523 gcc_assert (bb2
!= NULL
);
1525 si2
= gsi_start_phis (bb2
);
1526 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1529 gsi_next_nonvirtual_phi (&si1
);
1530 gsi_next_nonvirtual_phi (&si2
);
1532 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1535 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1536 return return_false();
1541 tree phi_result1
= gimple_phi_result (phi1
);
1542 tree phi_result2
= gimple_phi_result (phi2
);
1544 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1545 return return_false_with_msg ("PHI results are different");
1547 size1
= gimple_phi_num_args (phi1
);
1548 size2
= gimple_phi_num_args (phi2
);
1551 return return_false ();
1553 for (i
= 0; i
< size1
; ++i
)
1555 t1
= gimple_phi_arg (phi1
, i
)->def
;
1556 t2
= gimple_phi_arg (phi2
, i
)->def
;
1558 if (!m_checker
->compare_operand (t1
, t2
))
1559 return return_false ();
1561 e1
= gimple_phi_arg_edge (phi1
, i
);
1562 e2
= gimple_phi_arg_edge (phi2
, i
);
1564 if (!m_checker
->compare_edge (e1
, e2
))
1565 return return_false ();
1574 /* Returns true if tree T can be compared as a handled component. */
1577 sem_function::icf_handled_component_p (tree t
)
1579 tree_code tc
= TREE_CODE (t
);
1581 return ((handled_component_p (t
))
1582 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
1583 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
1586 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1587 corresponds to TARGET. */
1590 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1595 if (bb_dict
->length () <= (unsigned)source
)
1596 bb_dict
->safe_grow_cleared (source
+ 1);
1598 if ((*bb_dict
)[source
] == 0)
1600 (*bb_dict
)[source
] = target
;
1604 return (*bb_dict
)[source
] == target
;
1608 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1610 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1614 /* Constructor based on varpool node _NODE with computed hash _HASH.
1615 Bitmap STACK is used for memory allocation. */
1617 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1618 bitmap_obstack
*stack
): sem_item(VAR
,
1621 gcc_checking_assert (node
);
1622 gcc_checking_assert (get_node ());
1625 /* Fast equality function based on knowledge known in WPA. */
1628 sem_variable::equals_wpa (sem_item
*item
,
1629 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1631 gcc_assert (item
->type
== VAR
);
1633 if (node
->num_references () != item
->node
->num_references ())
1634 return return_false_with_msg ("different number of references");
1636 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1637 return return_false_with_msg ("TLS model");
1639 if (DECL_ALIGN (decl
) != DECL_ALIGN (item
->decl
))
1640 return return_false_with_msg ("alignment mismatch");
1642 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1643 return return_false_with_msg ("Virtual flag mismatch");
1645 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1646 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1647 || !operand_equal_p (DECL_SIZE (decl
),
1648 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1649 return return_false_with_msg ("size mismatch");
1651 /* Do not attempt to mix data from different user sections;
1652 we do not know what user intends with those. */
1653 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1654 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1655 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1656 return return_false_with_msg ("user section mismatch");
1658 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1659 return return_false_with_msg ("text section");
1661 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1662 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1664 item
->node
->iterate_reference (i
, ref2
);
1666 if (!compare_cgraph_references (ignored_nodes
,
1667 ref
->referred
, ref2
->referred
,
1668 ref
->address_matters_p ()))
1671 /* When matching virtual tables, be sure to also match information
1672 relevant for polymorphic call analysis. */
1673 if (DECL_VIRTUAL_P (decl
) || DECL_VIRTUAL_P (item
->decl
))
1675 if (DECL_VIRTUAL_P (ref
->referred
->decl
)
1676 != DECL_VIRTUAL_P (ref2
->referred
->decl
))
1677 return return_false_with_msg ("virtual flag mismatch");
1678 if (DECL_VIRTUAL_P (ref
->referred
->decl
)
1679 && is_a
<cgraph_node
*> (ref
->referred
)
1680 && (DECL_FINAL_P (ref
->referred
->decl
)
1681 != DECL_FINAL_P (ref2
->referred
->decl
)))
1682 return return_false_with_msg ("final flag mismatch");
1689 /* Returns true if the item equals to ITEM given as argument. */
1691 /* Returns true if the item equals to ITEM given as argument. */
1694 sem_variable::equals (sem_item
*item
,
1695 hash_map
<symtab_node
*, sem_item
*> &)
1697 gcc_assert (item
->type
== VAR
);
1700 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1701 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1702 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1703 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1705 /* As seen in PR ipa/65303 we have to compare variables types. */
1706 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1707 TREE_TYPE (item
->decl
)))
1708 return return_false_with_msg ("variables types are different");
1710 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1711 DECL_INITIAL (item
->node
->decl
));
1712 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1714 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1715 xstrdup_for_dump (node
->name()),
1716 xstrdup_for_dump (item
->node
->name ()),
1717 node
->order
, item
->node
->order
,
1718 xstrdup_for_dump (node
->asm_name ()),
1719 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1724 /* Compares trees T1 and T2 for semantic equality. */
1727 sem_variable::equals (tree t1
, tree t2
)
1730 return return_with_debug (t1
== t2
);
1733 tree_code tc1
= TREE_CODE (t1
);
1734 tree_code tc2
= TREE_CODE (t2
);
1737 return return_false_with_msg ("TREE_CODE mismatch");
1743 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1744 unsigned HOST_WIDE_INT idx
;
1746 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1747 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1748 return return_false_with_msg ("constructor type mismatch");
1750 if (typecode
== ARRAY_TYPE
)
1752 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1753 /* For arrays, check that the sizes all match. */
1754 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1756 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1757 return return_false_with_msg ("constructor array size mismatch");
1759 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1761 return return_false_with_msg ("constructor type incompatible");
1763 v1
= CONSTRUCTOR_ELTS (t1
);
1764 v2
= CONSTRUCTOR_ELTS (t2
);
1765 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1766 return return_false_with_msg ("constructor number of elts mismatch");
1768 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1770 constructor_elt
*c1
= &(*v1
)[idx
];
1771 constructor_elt
*c2
= &(*v2
)[idx
];
1773 /* Check that each value is the same... */
1774 if (!sem_variable::equals (c1
->value
, c2
->value
))
1776 /* ... and that they apply to the same fields! */
1777 if (!sem_variable::equals (c1
->index
, c2
->index
))
1784 tree x1
= TREE_OPERAND (t1
, 0);
1785 tree x2
= TREE_OPERAND (t2
, 0);
1786 tree y1
= TREE_OPERAND (t1
, 1);
1787 tree y2
= TREE_OPERAND (t2
, 1);
1789 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1790 return return_false ();
1792 /* Type of the offset on MEM_REF does not matter. */
1793 return return_with_debug (sem_variable::equals (x1
, x2
)
1794 && wi::to_offset (y1
)
1795 == wi::to_offset (y2
));
1800 tree op1
= TREE_OPERAND (t1
, 0);
1801 tree op2
= TREE_OPERAND (t2
, 0);
1802 return sem_variable::equals (op1
, op2
);
1804 /* References to other vars/decls are compared using ipa-ref. */
1807 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1809 return return_false_with_msg ("Declaration mismatch");
1811 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1812 need to process its VAR/FUNCTION references without relying on ipa-ref
1816 return return_false_with_msg ("Declaration mismatch");
1818 /* Integer constants are the same only if the same width of type. */
1819 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1820 return return_false_with_msg ("INTEGER_CST precision mismatch");
1821 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1822 return return_false_with_msg ("INTEGER_CST mode mismatch");
1823 return return_with_debug (tree_int_cst_equal (t1
, t2
));
1825 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1826 return return_false_with_msg ("STRING_CST mode mismatch");
1827 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
1828 return return_false_with_msg ("STRING_CST length mismatch");
1829 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
1830 TREE_STRING_LENGTH (t1
)))
1831 return return_false_with_msg ("STRING_CST mismatch");
1834 /* Fixed constants are the same only if the same width of type. */
1835 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1836 return return_false_with_msg ("FIXED_CST precision mismatch");
1838 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
1839 TREE_FIXED_CST (t2
)));
1841 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
1842 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
1844 /* Real constants are the same only if the same width of type. */
1845 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1846 return return_false_with_msg ("REAL_CST precision mismatch");
1847 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1
),
1848 TREE_REAL_CST (t2
)));
1853 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
1854 return return_false_with_msg ("VECTOR_CST nelts mismatch");
1856 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
1857 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
1858 VECTOR_CST_ELT (t2
, i
)))
1864 case ARRAY_RANGE_REF
:
1866 tree x1
= TREE_OPERAND (t1
, 0);
1867 tree x2
= TREE_OPERAND (t2
, 0);
1868 tree y1
= TREE_OPERAND (t1
, 1);
1869 tree y2
= TREE_OPERAND (t2
, 1);
1871 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
1873 if (!sem_variable::equals (array_ref_low_bound (t1
),
1874 array_ref_low_bound (t2
)))
1876 if (!sem_variable::equals (array_ref_element_size (t1
),
1877 array_ref_element_size (t2
)))
1883 case POINTER_PLUS_EXPR
:
1888 tree x1
= TREE_OPERAND (t1
, 0);
1889 tree x2
= TREE_OPERAND (t2
, 0);
1890 tree y1
= TREE_OPERAND (t1
, 1);
1891 tree y2
= TREE_OPERAND (t2
, 1);
1893 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1897 case VIEW_CONVERT_EXPR
:
1898 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
1899 return return_false ();
1900 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
1902 return return_false_with_msg ("ERROR_MARK");
1904 return return_false_with_msg ("Unknown TREE code reached");
1908 /* Parser function that visits a varpool NODE. */
1911 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1913 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
1917 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1924 /* References independent hash function. */
1927 sem_variable::get_hash (void)
1932 /* All WPA streamed in symbols should have their hashes computed at compile
1933 time. At this point, the constructor may not be in memory at all.
1934 DECL_INITIAL (decl) would be error_mark_node in that case. */
1935 gcc_assert (!node
->lto_file_data
);
1936 tree ctor
= DECL_INITIAL (decl
);
1937 inchash::hash hstate
;
1939 hstate
.add_int (456346417);
1940 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
1941 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
1942 add_expr (ctor
, hstate
);
1943 hash
= hstate
.end ();
1948 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1952 sem_variable::merge (sem_item
*alias_item
)
1954 gcc_assert (alias_item
->type
== VAR
);
1956 if (!sem_item::target_supports_symbol_aliases_p ())
1959 fprintf (dump_file
, "Not unifying; "
1960 "Symbol aliases are not supported by target\n\n");
1964 if (DECL_EXTERNAL (alias_item
->decl
))
1967 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1971 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1973 varpool_node
*original
= get_node ();
1974 varpool_node
*alias
= alias_var
->get_node ();
1975 bool original_discardable
= false;
1977 bool original_address_matters
= original
->address_matters_p ();
1978 bool alias_address_matters
= alias
->address_matters_p ();
1980 /* See if original is in a section that can be discarded if the main
1982 Also consider case where we have resolution info and we know that
1983 original's definition is not going to be used. In this case we can not
1984 create alias to original. */
1985 if (original
->can_be_discarded_p ()
1986 || (node
->resolution
!= LDPR_UNKNOWN
1987 && !decl_binds_to_current_def_p (node
->decl
)))
1988 original_discardable
= true;
1990 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1992 /* Constant pool machinery is not quite ready for aliases.
1993 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
1994 For LTO merging does not happen that is an important missing feature.
1995 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
1996 flag is dropped and non-local symbol name is assigned. */
1997 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
1998 || DECL_IN_CONSTANT_POOL (original
->decl
))
2002 "Not unifying; constant pool variables.\n\n");
2006 /* Do not attempt to mix functions from different user sections;
2007 we do not know what user intends with those. */
2008 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2009 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2010 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2015 "original and alias are in different sections.\n\n");
2019 /* We can not merge if address comparsion metters. */
2020 if (original_address_matters
&& alias_address_matters
2021 && flag_merge_constants
< 2)
2026 "adress of original and alias may be compared.\n\n");
2029 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2032 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2033 "across comdat group boundary\n\n");
2038 if (original_discardable
)
2041 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2042 "target is discardable\n\n");
2048 gcc_assert (!original
->alias
);
2049 gcc_assert (!alias
->alias
);
2051 alias
->analyzed
= false;
2053 DECL_INITIAL (alias
->decl
) = NULL
;
2054 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2056 alias
->need_bounds_init
= false;
2057 alias
->remove_all_references ();
2058 if (TREE_ADDRESSABLE (alias
->decl
))
2059 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2061 varpool_node::create_alias (alias_var
->decl
, decl
);
2062 alias
->resolve_alias (original
);
2065 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
2071 /* Dump symbol to FILE. */
2074 sem_variable::dump_to_file (FILE *file
)
2078 print_node (file
, "", decl
, 0);
2079 fprintf (file
, "\n\n");
2082 unsigned int sem_item_optimizer::class_id
= 0;
2084 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2085 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
2088 bitmap_obstack_initialize (&m_bmstack
);
2091 sem_item_optimizer::~sem_item_optimizer ()
2093 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2096 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2097 it
!= m_classes
.end (); ++it
)
2099 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2100 delete (*it
)->classes
[i
];
2102 (*it
)->classes
.release ();
2108 bitmap_obstack_release (&m_bmstack
);
2111 /* Write IPA ICF summary for symbols. */
2114 sem_item_optimizer::write_summary (void)
2116 unsigned int count
= 0;
2118 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2119 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2122 /* Calculate number of symbols to be serialized. */
2123 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2125 lsei_next_in_partition (&lsei
))
2127 symtab_node
*node
= lsei_node (lsei
);
2129 if (m_symtab_node_map
.get (node
))
2133 streamer_write_uhwi (ob
, count
);
2135 /* Process all of the symbols. */
2136 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2138 lsei_next_in_partition (&lsei
))
2140 symtab_node
*node
= lsei_node (lsei
);
2142 sem_item
**item
= m_symtab_node_map
.get (node
);
2146 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2147 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2149 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2153 streamer_write_char_stream (ob
->main_stream
, 0);
2154 produce_asm (ob
, NULL
);
2155 destroy_output_block (ob
);
2158 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2159 contains LEN bytes. */
2162 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2163 const char *data
, size_t len
)
2165 const lto_function_header
*header
=
2166 (const lto_function_header
*) data
;
2167 const int cfg_offset
= sizeof (lto_function_header
);
2168 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2169 const int string_offset
= main_offset
+ header
->main_size
;
2174 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2175 header
->main_size
, file_data
->mode_table
);
2178 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2179 header
->string_size
, vNULL
);
2181 count
= streamer_read_uhwi (&ib_main
);
2183 for (i
= 0; i
< count
; i
++)
2187 lto_symtab_encoder_t encoder
;
2189 index
= streamer_read_uhwi (&ib_main
);
2190 encoder
= file_data
->symtab_node_encoder
;
2191 node
= lto_symtab_encoder_deref (encoder
, index
);
2193 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2195 gcc_assert (node
->definition
);
2198 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2199 node
->asm_name (), (void *) node
->decl
, node
->order
);
2201 if (is_a
<cgraph_node
*> (node
))
2203 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2205 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2209 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2211 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2215 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2217 lto_data_in_delete (data_in
);
2220 /* Read IPA IPA ICF summary for symbols. */
2223 sem_item_optimizer::read_summary (void)
2225 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2226 lto_file_decl_data
*file_data
;
2229 while ((file_data
= file_data_vec
[j
++]))
2232 const char *data
= lto_get_section_data (file_data
,
2233 LTO_section_ipa_icf
, NULL
, &len
);
2236 read_section (file_data
, data
, len
);
2240 /* Register callgraph and varpool hooks. */
2243 sem_item_optimizer::register_hooks (void)
2245 if (!m_cgraph_node_hooks
)
2246 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2247 (&sem_item_optimizer::cgraph_removal_hook
, this);
2249 if (!m_varpool_node_hooks
)
2250 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2251 (&sem_item_optimizer::varpool_removal_hook
, this);
2254 /* Unregister callgraph and varpool hooks. */
2257 sem_item_optimizer::unregister_hooks (void)
2259 if (m_cgraph_node_hooks
)
2260 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2262 if (m_varpool_node_hooks
)
2263 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2266 /* Adds a CLS to hashtable associated by hash value. */
2269 sem_item_optimizer::add_class (congruence_class
*cls
)
2271 gcc_assert (cls
->members
.length ());
2273 congruence_class_group
*group
= get_group_by_hash (
2274 cls
->members
[0]->get_hash (),
2275 cls
->members
[0]->type
);
2276 group
->classes
.safe_push (cls
);
2279 /* Gets a congruence class group based on given HASH value and TYPE. */
2281 congruence_class_group
*
2282 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2284 congruence_class_group
*item
= XNEW (congruence_class_group
);
2288 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2294 item
->classes
.create (1);
2301 /* Callgraph removal hook called for a NODE with a custom DATA. */
2304 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2306 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2307 optimizer
->remove_symtab_node (node
);
2310 /* Varpool removal hook called for a NODE with a custom DATA. */
2313 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2315 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2316 optimizer
->remove_symtab_node (node
);
2319 /* Remove symtab NODE triggered by symtab removal hooks. */
2322 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2324 gcc_assert (!m_classes
.elements());
2326 m_removed_items_set
.add (node
);
2330 sem_item_optimizer::remove_item (sem_item
*item
)
2332 if (m_symtab_node_map
.get (item
->node
))
2333 m_symtab_node_map
.remove (item
->node
);
2337 /* Removes all callgraph and varpool nodes that are marked by symtab
2341 sem_item_optimizer::filter_removed_items (void)
2343 auto_vec
<sem_item
*> filtered
;
2345 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2347 sem_item
*item
= m_items
[i
];
2349 if (m_removed_items_set
.contains (item
->node
))
2355 if (item
->type
== FUNC
)
2357 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2359 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2362 filtered
.safe_push (item
);
2366 if (!flag_ipa_icf_variables
)
2370 /* Filter out non-readonly variables. */
2371 tree decl
= item
->decl
;
2372 if (TREE_READONLY (decl
))
2373 filtered
.safe_push (item
);
2380 /* Clean-up of released semantic items. */
2383 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2384 m_items
.safe_push (filtered
[i
]);
2387 /* Optimizer entry point which returns true in case it processes
2388 a merge operation. True is returned if there's a merge operation
2392 sem_item_optimizer::execute (void)
2394 filter_removed_items ();
2395 unregister_hooks ();
2398 update_hash_by_addr_refs ();
2399 build_hash_based_classes ();
2402 fprintf (dump_file
, "Dump after hash based groups\n");
2403 dump_cong_classes ();
2405 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2406 m_items
[i
]->init_wpa ();
2408 subdivide_classes_by_equality (true);
2411 fprintf (dump_file
, "Dump after WPA based types groups\n");
2413 dump_cong_classes ();
2415 process_cong_reduction ();
2419 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2421 dump_cong_classes ();
2423 parse_nonsingleton_classes ();
2424 subdivide_classes_by_equality ();
2427 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2429 dump_cong_classes ();
2431 unsigned int prev_class_count
= m_classes_count
;
2433 process_cong_reduction ();
2434 dump_cong_classes ();
2436 bool merged_p
= merge_classes (prev_class_count
);
2438 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2439 symtab_node::dump_table (dump_file
);
2444 /* Function responsible for visiting all potential functions and
2445 read-only variables that can be merged. */
2448 sem_item_optimizer::parse_funcs_and_vars (void)
2452 if (flag_ipa_icf_functions
)
2453 FOR_EACH_DEFINED_FUNCTION (cnode
)
2455 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2458 m_items
.safe_push (f
);
2459 m_symtab_node_map
.put (cnode
, f
);
2462 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2464 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2465 f
->dump_to_file (dump_file
);
2468 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2471 varpool_node
*vnode
;
2473 if (flag_ipa_icf_variables
)
2474 FOR_EACH_DEFINED_VARIABLE (vnode
)
2476 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2480 m_items
.safe_push (v
);
2481 m_symtab_node_map
.put (vnode
, v
);
2486 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2489 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2491 item
->index_in_class
= cls
->members
.length ();
2492 cls
->members
.safe_push (item
);
2496 /* For each semantic item, append hash values of references. */
2499 sem_item_optimizer::update_hash_by_addr_refs ()
2501 /* First, append to hash sensitive references and class type if it need to
2502 be matched for ODR. */
2503 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2505 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2506 if (m_items
[i
]->type
== FUNC
)
2508 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (m_items
[i
]->node
);
2510 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2511 && contains_polymorphic_type_p
2512 (method_class_type (TREE_TYPE (m_items
[i
]->decl
)))
2513 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2514 || ((ipa_node_params_sum
== NULL
2515 || IPA_NODE_REF (cnode
)->descriptors
.is_empty ()
2516 || ipa_is_param_used (IPA_NODE_REF (cnode
), 0))
2517 && static_cast<sem_function
*> (m_items
[i
])
2518 ->compare_polymorphic_p ())))
2521 = method_class_type (TREE_TYPE (m_items
[i
]->decl
));
2522 inchash::hash
hstate (m_items
[i
]->hash
);
2524 if (TYPE_NAME (class_type
)
2525 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2527 (IDENTIFIER_HASH_VALUE
2528 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2530 m_items
[i
]->hash
= hstate
.end ();
2535 /* Once all symbols have enhanced hash value, we can append
2536 hash values of symbols that are seen by IPA ICF and are
2537 references by a semantic item. Newly computed values
2538 are saved to global_hash member variable. */
2539 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2540 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2542 /* Global hash value replace current hash values. */
2543 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2544 m_items
[i
]->hash
= m_items
[i
]->global_hash
;
2547 /* Congruence classes are built by hash value. */
2550 sem_item_optimizer::build_hash_based_classes (void)
2552 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2554 sem_item
*item
= m_items
[i
];
2556 congruence_class_group
*group
= get_group_by_hash (item
->hash
,
2559 if (!group
->classes
.length ())
2562 group
->classes
.safe_push (new congruence_class (class_id
++));
2565 add_item_to_class (group
->classes
[0], item
);
2569 /* Build references according to call graph. */
2572 sem_item_optimizer::build_graph (void)
2574 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2576 sem_item
*item
= m_items
[i
];
2577 m_symtab_node_map
.put (item
->node
, item
);
2580 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2582 sem_item
*item
= m_items
[i
];
2584 if (item
->type
== FUNC
)
2586 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2588 cgraph_edge
*e
= cnode
->callees
;
2591 sem_item
**slot
= m_symtab_node_map
.get
2592 (e
->callee
->ultimate_alias_target ());
2594 item
->add_reference (*slot
);
2600 ipa_ref
*ref
= NULL
;
2601 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2603 sem_item
**slot
= m_symtab_node_map
.get
2604 (ref
->referred
->ultimate_alias_target ());
2606 item
->add_reference (*slot
);
2611 /* Semantic items in classes having more than one element and initialized.
2612 In case of WPA, we load function body. */
2615 sem_item_optimizer::parse_nonsingleton_classes (void)
2617 unsigned int init_called_count
= 0;
2619 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2620 if (m_items
[i
]->cls
->members
.length () > 1)
2622 m_items
[i
]->init ();
2623 init_called_count
++;
2627 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2628 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2631 /* Equality function for semantic items is used to subdivide existing
2632 classes. If IN_WPA, fast equality function is invoked. */
2635 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2637 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2638 it
!= m_classes
.end (); ++it
)
2640 unsigned int class_count
= (*it
)->classes
.length ();
2642 for (unsigned i
= 0; i
< class_count
; i
++)
2644 congruence_class
*c
= (*it
)->classes
[i
];
2646 if (c
->members
.length() > 1)
2648 auto_vec
<sem_item
*> new_vector
;
2650 sem_item
*first
= c
->members
[0];
2651 new_vector
.safe_push (first
);
2653 unsigned class_split_first
= (*it
)->classes
.length ();
2655 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2657 sem_item
*item
= c
->members
[j
];
2659 bool equals
= in_wpa
? first
->equals_wpa (item
,
2660 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2663 new_vector
.safe_push (item
);
2666 bool integrated
= false;
2668 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2670 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2671 bool equals
= in_wpa
? x
->equals_wpa (item
,
2672 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2677 add_item_to_class ((*it
)->classes
[k
], item
);
2685 congruence_class
*c
= new congruence_class (class_id
++);
2687 add_item_to_class (c
, item
);
2689 (*it
)->classes
.safe_push (c
);
2694 // we replace newly created new_vector for the class we've just splitted
2695 c
->members
.release ();
2696 c
->members
.create (new_vector
.length ());
2698 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2699 add_item_to_class (c
, new_vector
[j
]);
2707 /* Subdivide classes by address references that members of the class
2708 reference. Example can be a pair of functions that have an address
2709 taken from a function. If these addresses are different the class
2713 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2715 typedef hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2716 symbol_compare_hashmap_traits
> subdivide_hash_map
;
2718 unsigned newly_created_classes
= 0;
2720 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2721 it
!= m_classes
.end (); ++it
)
2723 unsigned int class_count
= (*it
)->classes
.length ();
2724 auto_vec
<congruence_class
*> new_classes
;
2726 for (unsigned i
= 0; i
< class_count
; i
++)
2728 congruence_class
*c
= (*it
)->classes
[i
];
2730 if (c
->members
.length() > 1)
2732 subdivide_hash_map split_map
;
2734 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2736 sem_item
*source_node
= c
->members
[j
];
2738 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2741 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
,
2743 gcc_checking_assert (slot
);
2745 slot
->safe_push (source_node
);
2751 /* If the map contains more than one key, we have to split the map
2753 if (split_map
.elements () != 1)
2755 bool first_class
= true;
2757 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2758 it2
!= split_map
.end (); ++it2
)
2760 congruence_class
*new_cls
;
2761 new_cls
= new congruence_class (class_id
++);
2763 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2764 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2766 worklist_push (new_cls
);
2767 newly_created_classes
++;
2771 (*it
)->classes
[i
] = new_cls
;
2772 first_class
= false;
2776 new_classes
.safe_push (new_cls
);
2782 /* Release memory. */
2783 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2784 it2
!= split_map
.end (); ++it2
)
2786 delete (*it2
).first
;
2787 (*it2
).second
.release ();
2792 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2793 (*it
)->classes
.safe_push (new_classes
[i
]);
2796 return newly_created_classes
;
2799 /* Verify congruence classes if checking is enabled. */
2802 sem_item_optimizer::verify_classes (void)
2805 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2806 it
!= m_classes
.end (); ++it
)
2808 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2810 congruence_class
*cls
= (*it
)->classes
[i
];
2812 gcc_checking_assert (cls
);
2813 gcc_checking_assert (cls
->members
.length () > 0);
2815 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
2817 sem_item
*item
= cls
->members
[j
];
2819 gcc_checking_assert (item
);
2820 gcc_checking_assert (item
->cls
== cls
);
2822 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
2824 sem_usage_pair
*usage
= item
->usages
[k
];
2825 gcc_checking_assert (usage
->item
->index_in_class
<
2826 usage
->item
->cls
->members
.length ());
2834 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2835 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2836 but unused argument. */
2839 sem_item_optimizer::release_split_map (congruence_class
* const &,
2840 bitmap
const &b
, traverse_split_pair
*)
2849 /* Process split operation for a class given as pointer CLS_PTR,
2850 where bitmap B splits congruence class members. DATA is used
2851 as argument of split pair. */
2854 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2855 bitmap
const &b
, traverse_split_pair
*pair
)
2857 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2858 const congruence_class
*splitter_cls
= pair
->cls
;
2860 /* If counted bits are greater than zero and less than the number of members
2861 a group will be splitted. */
2862 unsigned popcount
= bitmap_count_bits (b
);
2864 if (popcount
> 0 && popcount
< cls
->members
.length ())
2866 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
2868 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2870 int target
= bitmap_bit_p (b
, i
);
2871 congruence_class
*tc
= newclasses
[target
];
2873 add_item_to_class (tc
, cls
->members
[i
]);
2876 #ifdef ENABLE_CHECKING
2877 for (unsigned int i
= 0; i
< 2; i
++)
2878 gcc_checking_assert (newclasses
[i
]->members
.length ());
2881 if (splitter_cls
== cls
)
2882 optimizer
->splitter_class_removed
= true;
2884 /* Remove old class from worklist if presented. */
2885 bool in_worklist
= cls
->in_worklist
;
2888 cls
->in_worklist
= false;
2890 congruence_class_group g
;
2891 g
.hash
= cls
->members
[0]->get_hash ();
2892 g
.type
= cls
->members
[0]->type
;
2894 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
2896 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2897 if (slot
->classes
[i
] == cls
)
2899 slot
->classes
.ordered_remove (i
);
2903 /* New class will be inserted and integrated to work list. */
2904 for (unsigned int i
= 0; i
< 2; i
++)
2905 optimizer
->add_class (newclasses
[i
]);
2907 /* Two classes replace one, so that increment just by one. */
2908 optimizer
->m_classes_count
++;
2910 /* If OLD class was presented in the worklist, we remove the class
2911 and replace it will both newly created classes. */
2913 for (unsigned int i
= 0; i
< 2; i
++)
2914 optimizer
->worklist_push (newclasses
[i
]);
2915 else /* Just smaller class is inserted. */
2917 unsigned int smaller_index
= newclasses
[0]->members
.length () <
2918 newclasses
[1]->members
.length () ?
2920 optimizer
->worklist_push (newclasses
[smaller_index
]);
2923 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2925 fprintf (dump_file
, " congruence class splitted:\n");
2926 cls
->dump (dump_file
, 4);
2928 fprintf (dump_file
, " newly created groups:\n");
2929 for (unsigned int i
= 0; i
< 2; i
++)
2930 newclasses
[i
]->dump (dump_file
, 4);
2933 /* Release class if not presented in work list. */
2942 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2943 Bitmap stack BMSTACK is used for bitmap allocation. */
2946 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2949 hash_map
<congruence_class
*, bitmap
> split_map
;
2951 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2953 sem_item
*item
= cls
->members
[i
];
2955 /* Iterate all usages that have INDEX as usage of the item. */
2956 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2958 sem_usage_pair
*usage
= item
->usages
[j
];
2960 if (usage
->index
!= index
)
2963 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2968 b
= BITMAP_ALLOC (&m_bmstack
);
2969 split_map
.put (usage
->item
->cls
, b
);
2975 gcc_checking_assert (usage
->item
->cls
);
2976 gcc_checking_assert (usage
->item
->index_in_class
<
2977 usage
->item
->cls
->members
.length ());
2980 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2984 traverse_split_pair pair
;
2985 pair
.optimizer
= this;
2988 splitter_class_removed
= false;
2990 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2992 /* Bitmap clean-up. */
2994 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2997 /* Every usage of a congruence class CLS is a candidate that can split the
2998 collection of classes. Bitmap stack BMSTACK is used for bitmap
3002 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3007 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3009 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3010 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3012 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3014 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3015 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
3018 do_congruence_step_for_index (cls
, i
);
3020 if (splitter_class_removed
)
3024 BITMAP_FREE (usage
);
3027 /* Adds a newly created congruence class CLS to worklist. */
3030 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3032 /* Return if the class CLS is already presented in work list. */
3033 if (cls
->in_worklist
)
3036 cls
->in_worklist
= true;
3037 worklist
.push_back (cls
);
3040 /* Pops a class from worklist. */
3043 sem_item_optimizer::worklist_pop (void)
3045 congruence_class
*cls
;
3047 while (!worklist
.empty ())
3049 cls
= worklist
.front ();
3050 worklist
.pop_front ();
3051 if (cls
->in_worklist
)
3053 cls
->in_worklist
= false;
3059 /* Work list item was already intended to be removed.
3060 The only reason for doing it is to split a class.
3061 Thus, the class CLS is deleted. */
3069 /* Iterative congruence reduction function. */
3072 sem_item_optimizer::process_cong_reduction (void)
3074 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3075 it
!= m_classes
.end (); ++it
)
3076 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3077 if ((*it
)->classes
[i
]->is_class_used ())
3078 worklist_push ((*it
)->classes
[i
]);
3081 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3082 (unsigned long) worklist
.size ());
3084 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3085 fprintf (dump_file
, "Congruence class reduction\n");
3087 congruence_class
*cls
;
3089 /* Process complete congruence reduction. */
3090 while ((cls
= worklist_pop ()) != NULL
)
3091 do_congruence_step (cls
);
3093 /* Subdivide newly created classes according to references. */
3094 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3097 fprintf (dump_file
, "Address reference subdivision created: %u "
3098 "new classes.\n", new_classes
);
3101 /* Debug function prints all informations about congruence classes. */
3104 sem_item_optimizer::dump_cong_classes (void)
3110 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3111 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
3113 /* Histogram calculation. */
3114 unsigned int max_index
= 0;
3115 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3117 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3118 it
!= m_classes
.end (); ++it
)
3120 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3122 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3130 "Class size histogram [num of members]: number of classe number of classess\n");
3132 for (unsigned int i
= 0; i
<= max_index
; i
++)
3134 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3136 fprintf (dump_file
, "\n\n");
3139 if (dump_flags
& TDF_DETAILS
)
3140 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3141 it
!= m_classes
.end (); ++it
)
3143 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
3145 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3147 (*it
)->classes
[i
]->dump (dump_file
, 4);
3149 if(i
< (*it
)->classes
.length () - 1)
3150 fprintf (dump_file
, " ");
3157 /* After reduction is done, we can declare all items in a group
3158 to be equal. PREV_CLASS_COUNT is start number of classes
3159 before reduction. True is returned if there's a merge operation
3163 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3165 unsigned int item_count
= m_items
.length ();
3166 unsigned int class_count
= m_classes_count
;
3167 unsigned int equal_items
= item_count
- class_count
;
3169 unsigned int non_singular_classes_count
= 0;
3170 unsigned int non_singular_classes_sum
= 0;
3172 bool merged_p
= false;
3174 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3175 it
!= m_classes
.end (); ++it
)
3176 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3178 congruence_class
*c
= (*it
)->classes
[i
];
3179 if (c
->members
.length () > 1)
3181 non_singular_classes_count
++;
3182 non_singular_classes_sum
+= c
->members
.length ();
3188 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3189 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3190 prev_class_count
, class_count
);
3191 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3192 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3193 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3194 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3195 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3196 non_singular_classes_count
: 0.0f
,
3197 non_singular_classes_count
);
3198 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3199 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3200 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3203 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3204 it
!= m_classes
.end (); ++it
)
3205 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3207 congruence_class
*c
= (*it
)->classes
[i
];
3209 if (c
->members
.length () == 1)
3212 gcc_assert (c
->members
.length ());
3214 sem_item
*source
= c
->members
[0];
3216 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
3218 sem_item
*alias
= c
->members
[j
];
3222 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3223 xstrdup_for_dump (source
->node
->name ()),
3224 xstrdup_for_dump (alias
->node
->name ()));
3225 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3226 xstrdup_for_dump (source
->node
->asm_name ()),
3227 xstrdup_for_dump (alias
->node
->asm_name ()));
3230 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3234 "Merge operation is skipped due to no_icf "
3240 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3242 source
->dump_to_file (dump_file
);
3243 alias
->dump_to_file (dump_file
);
3246 merged_p
|= source
->merge (alias
);
3253 /* Dump function prints all class members to a FILE with an INDENT. */
3256 congruence_class::dump (FILE *file
, unsigned int indent
) const
3258 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3259 id
, members
[0]->get_hash (), members
.length ());
3261 FPUTS_SPACES (file
, indent
+ 2, "");
3262 for (unsigned i
= 0; i
< members
.length (); i
++)
3263 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3264 (void *) members
[i
]->decl
,
3265 members
[i
]->node
->order
);
3267 fprintf (file
, "\n");
3270 /* Returns true if there's a member that is used from another group. */
3273 congruence_class::is_class_used (void)
3275 for (unsigned int i
= 0; i
< members
.length (); i
++)
3276 if (members
[i
]->usages
.length ())
3282 /* Generate pass summary for IPA ICF pass. */
3285 ipa_icf_generate_summary (void)
3288 optimizer
= new sem_item_optimizer ();
3290 optimizer
->register_hooks ();
3291 optimizer
->parse_funcs_and_vars ();
3294 /* Write pass summary for IPA ICF pass. */
3297 ipa_icf_write_summary (void)
3299 gcc_assert (optimizer
);
3301 optimizer
->write_summary ();
3304 /* Read pass summary for IPA ICF pass. */
3307 ipa_icf_read_summary (void)
3310 optimizer
= new sem_item_optimizer ();
3312 optimizer
->read_summary ();
3313 optimizer
->register_hooks ();
3316 /* Semantic equality exection function. */
3319 ipa_icf_driver (void)
3321 gcc_assert (optimizer
);
3323 bool merged_p
= optimizer
->execute ();
3328 return merged_p
? TODO_remove_functions
: 0;
3331 const pass_data pass_data_ipa_icf
=
3333 IPA_PASS
, /* type */
3335 OPTGROUP_IPA
, /* optinfo_flags */
3336 TV_IPA_ICF
, /* tv_id */
3337 0, /* properties_required */
3338 0, /* properties_provided */
3339 0, /* properties_destroyed */
3340 0, /* todo_flags_start */
3341 0, /* todo_flags_finish */
3344 class pass_ipa_icf
: public ipa_opt_pass_d
3347 pass_ipa_icf (gcc::context
*ctxt
)
3348 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3349 ipa_icf_generate_summary
, /* generate_summary */
3350 ipa_icf_write_summary
, /* write_summary */
3351 ipa_icf_read_summary
, /* read_summary */
3353 write_optimization_summary */
3355 read_optimization_summary */
3356 NULL
, /* stmt_fixup */
3357 0, /* function_transform_todo_flags_start */
3358 NULL
, /* function_transform */
3359 NULL
) /* variable_transform */
3362 /* opt_pass methods: */
3363 virtual bool gate (function
*)
3365 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3368 virtual unsigned int execute (function
*)
3370 return ipa_icf_driver();
3372 }; // class pass_ipa_icf
3374 } // ipa_icf namespace
3377 make_pass_ipa_icf (gcc::context
*ctxt
)
3379 return new ipa_icf::pass_ipa_icf (ctxt
);