Daily bump.
[official-gcc.git] / gcc / ipa-icf.c
blob3597b3a185ef14c97ffa3456bcec416e4fbd2892
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
11 version.
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
16 for more details.
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
23 read-only variables.
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
28 In case of functions,
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
32 aliases if possible.
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
45 correspond.
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.
54 #include "config.h"
55 #include "system.h"
56 #include <list>
57 #include "coretypes.h"
58 #include "alias.h"
59 #include "backend.h"
60 #include "tree.h"
61 #include "gimple.h"
62 #include "rtl.h"
63 #include "ssa.h"
64 #include "options.h"
65 #include "fold-const.h"
66 #include "internal-fn.h"
67 #include "flags.h"
68 #include "insn-config.h"
69 #include "expmed.h"
70 #include "dojump.h"
71 #include "explow.h"
72 #include "calls.h"
73 #include "emit-rtl.h"
74 #include "varasm.h"
75 #include "stmt.h"
76 #include "expr.h"
77 #include "gimple-iterator.h"
78 #include "tree-cfg.h"
79 #include "tree-dfa.h"
80 #include "tree-pass.h"
81 #include "gimple-pretty-print.h"
82 #include "cgraph.h"
83 #include "alloc-pool.h"
84 #include "symbol-summary.h"
85 #include "ipa-prop.h"
86 #include "ipa-inline.h"
87 #include "cfgloop.h"
88 #include "except.h"
89 #include "coverage.h"
90 #include "attribs.h"
91 #include "print-tree.h"
92 #include "target.h"
93 #include "data-streamer.h"
94 #include "ipa-utils.h"
95 #include "ipa-icf-gimple.h"
96 #include "ipa-icf.h"
97 #include "stor-layout.h"
98 #include "dbgcnt.h"
100 using namespace ipa_icf_gimple;
102 namespace ipa_icf {
104 /* Initialization and computation of symtab node hash, there data
105 are propagated later on. */
107 static sem_item_optimizer *optimizer = NULL;
109 /* Constructor. */
111 symbol_compare_collection::symbol_compare_collection (symtab_node *node)
113 m_references.create (0);
114 m_interposables.create (0);
116 ipa_ref *ref;
118 if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
119 return;
121 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
123 if (ref->address_matters_p ())
124 m_references.safe_push (ref->referred);
126 if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE)
128 if (ref->address_matters_p ())
129 m_references.safe_push (ref->referred);
130 else
131 m_interposables.safe_push (ref->referred);
135 if (is_a <cgraph_node *> (node))
137 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
139 for (cgraph_edge *e = cnode->callees; e; e = e->next_callee)
140 if (e->callee->get_availability () <= AVAIL_INTERPOSABLE)
141 m_interposables.safe_push (e->callee);
145 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
147 sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index):
148 item (_item), index (_index)
152 /* Semantic item constructor for a node of _TYPE, where STACK is used
153 for bitmap memory allocation. */
155 sem_item::sem_item (sem_item_type _type,
156 bitmap_obstack *stack): type(_type), hash(0)
158 setup (stack);
161 /* Semantic item constructor for a node of _TYPE, where STACK is used
162 for bitmap memory allocation. The item is based on symtab node _NODE
163 with computed _HASH. */
165 sem_item::sem_item (sem_item_type _type, symtab_node *_node,
166 hashval_t _hash, bitmap_obstack *stack): type(_type),
167 node (_node), hash (_hash)
169 decl = node->decl;
170 setup (stack);
173 /* Add reference to a semantic TARGET. */
175 void
176 sem_item::add_reference (sem_item *target)
178 refs.safe_push (target);
179 unsigned index = refs.length ();
180 target->usages.safe_push (new sem_usage_pair(this, index));
181 bitmap_set_bit (target->usage_index_bitmap, index);
182 refs_set.add (target->node);
185 /* Initialize internal data structures. Bitmap STACK is used for
186 bitmap memory allocation process. */
188 void
189 sem_item::setup (bitmap_obstack *stack)
191 gcc_checking_assert (node);
193 refs.create (0);
194 tree_refs.create (0);
195 usages.create (0);
196 usage_index_bitmap = BITMAP_ALLOC (stack);
199 sem_item::~sem_item ()
201 for (unsigned i = 0; i < usages.length (); i++)
202 delete usages[i];
204 refs.release ();
205 tree_refs.release ();
206 usages.release ();
208 BITMAP_FREE (usage_index_bitmap);
211 /* Dump function for debugging purpose. */
213 DEBUG_FUNCTION void
214 sem_item::dump (void)
216 if (dump_file)
218 fprintf (dump_file, "[%s] %s (%u) (tree:%p)\n", type == FUNC ? "func" : "var",
219 node->name(), node->order, (void *) node->decl);
220 fprintf (dump_file, " hash: %u\n", get_hash ());
221 fprintf (dump_file, " references: ");
223 for (unsigned i = 0; i < refs.length (); i++)
224 fprintf (dump_file, "%s%s ", refs[i]->node->name (),
225 i < refs.length() - 1 ? "," : "");
227 fprintf (dump_file, "\n");
231 /* Return true if target supports alias symbols. */
233 bool
234 sem_item::target_supports_symbol_aliases_p (void)
236 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
237 return false;
238 #else
239 return true;
240 #endif
243 /* Semantic function constructor that uses STACK as bitmap memory stack. */
245 sem_function::sem_function (bitmap_obstack *stack): sem_item (FUNC, stack),
246 m_checker (NULL), m_compared_func (NULL)
248 bb_sizes.create (0);
249 bb_sorted.create (0);
252 /* Constructor based on callgraph node _NODE with computed hash _HASH.
253 Bitmap STACK is used for memory allocation. */
254 sem_function::sem_function (cgraph_node *node, hashval_t hash,
255 bitmap_obstack *stack):
256 sem_item (FUNC, node, hash, stack),
257 m_checker (NULL), m_compared_func (NULL)
259 bb_sizes.create (0);
260 bb_sorted.create (0);
263 sem_function::~sem_function ()
265 for (unsigned i = 0; i < bb_sorted.length (); i++)
266 delete (bb_sorted[i]);
268 bb_sizes.release ();
269 bb_sorted.release ();
272 /* Calculates hash value based on a BASIC_BLOCK. */
274 hashval_t
275 sem_function::get_bb_hash (const sem_bb *basic_block)
277 inchash::hash hstate;
279 hstate.add_int (basic_block->nondbg_stmt_count);
280 hstate.add_int (basic_block->edge_count);
282 return hstate.end ();
285 /* References independent hash function. */
287 hashval_t
288 sem_function::get_hash (void)
290 if(!hash)
292 inchash::hash hstate;
293 hstate.add_int (177454); /* Random number for function type. */
295 hstate.add_int (arg_count);
296 hstate.add_int (cfg_checksum);
297 hstate.add_int (gcode_hash);
299 for (unsigned i = 0; i < bb_sorted.length (); i++)
300 hstate.merge_hash (get_bb_hash (bb_sorted[i]));
302 for (unsigned i = 0; i < bb_sizes.length (); i++)
303 hstate.add_int (bb_sizes[i]);
306 /* Add common features of declaration itself. */
307 if (DECL_FUNCTION_SPECIFIC_TARGET (decl))
308 hstate.add_wide_int
309 (cl_target_option_hash
310 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl))));
311 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))
312 (cl_optimization_hash
313 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))));
314 hstate.add_flag (DECL_CXX_CONSTRUCTOR_P (decl));
315 hstate.add_flag (DECL_CXX_DESTRUCTOR_P (decl));
317 hash = hstate.end ();
320 return hash;
323 /* Return ture if A1 and A2 represent equivalent function attribute lists.
324 Based on comp_type_attributes. */
326 bool
327 sem_item::compare_attributes (const_tree a1, const_tree a2)
329 const_tree a;
330 if (a1 == a2)
331 return true;
332 for (a = a1; a != NULL_TREE; a = TREE_CHAIN (a))
334 const struct attribute_spec *as;
335 const_tree attr;
337 as = lookup_attribute_spec (get_attribute_name (a));
338 /* TODO: We can introduce as->affects_decl_identity
339 and as->affects_decl_reference_identity if attribute mismatch
340 gets a common reason to give up on merging. It may not be worth
341 the effort.
342 For example returns_nonnull affects only references, while
343 optimize attribute can be ignored because it is already lowered
344 into flags representation and compared separately. */
345 if (!as)
346 continue;
348 attr = lookup_attribute (as->name, CONST_CAST_TREE (a2));
349 if (!attr || !attribute_value_equal (a, attr))
350 break;
352 if (!a)
354 for (a = a2; a != NULL_TREE; a = TREE_CHAIN (a))
356 const struct attribute_spec *as;
358 as = lookup_attribute_spec (get_attribute_name (a));
359 if (!as)
360 continue;
362 if (!lookup_attribute (as->name, CONST_CAST_TREE (a1)))
363 break;
364 /* We don't need to compare trees again, as we did this
365 already in first loop. */
367 if (!a)
368 return true;
370 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
371 return false;
374 /* Compare properties of symbols N1 and N2 that does not affect semantics of
375 symbol itself but affects semantics of its references from USED_BY (which
376 may be NULL if it is unknown). If comparsion is false, symbols
377 can still be merged but any symbols referring them can't.
379 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
381 TODO: We can also split attributes to those that determine codegen of
382 a function body/variable constructor itself and those that are used when
383 referring to it. */
385 bool
386 sem_item::compare_referenced_symbol_properties (symtab_node *used_by,
387 symtab_node *n1,
388 symtab_node *n2,
389 bool address)
391 if (is_a <cgraph_node *> (n1))
393 /* Inline properties matters: we do now want to merge uses of inline
394 function to uses of normal function because inline hint would be lost.
395 We however can merge inline function to noinline because the alias
396 will keep its DECL_DECLARED_INLINE flag.
398 Also ignore inline flag when optimizing for size or when function
399 is known to not be inlinable.
401 TODO: the optimize_size checks can also be assumed to be true if
402 unit has no !optimize_size functions. */
404 if ((!used_by || address || !is_a <cgraph_node *> (used_by)
405 || !opt_for_fn (used_by->decl, optimize_size))
406 && !opt_for_fn (n1->decl, optimize_size)
407 && n1->get_availability () > AVAIL_INTERPOSABLE
408 && (!DECL_UNINLINABLE (n1->decl) || !DECL_UNINLINABLE (n2->decl)))
410 if (DECL_DISREGARD_INLINE_LIMITS (n1->decl)
411 != DECL_DISREGARD_INLINE_LIMITS (n2->decl))
412 return return_false_with_msg
413 ("DECL_DISREGARD_INLINE_LIMITS are different");
415 if (DECL_DECLARED_INLINE_P (n1->decl)
416 != DECL_DECLARED_INLINE_P (n2->decl))
417 return return_false_with_msg ("inline attributes are different");
420 if (DECL_IS_OPERATOR_NEW (n1->decl)
421 != DECL_IS_OPERATOR_NEW (n2->decl))
422 return return_false_with_msg ("operator new flags are different");
425 /* Merging two definitions with a reference to equivalent vtables, but
426 belonging to a different type may result in ipa-polymorphic-call analysis
427 giving a wrong answer about the dynamic type of instance. */
428 if (is_a <varpool_node *> (n1))
430 if ((DECL_VIRTUAL_P (n1->decl) || DECL_VIRTUAL_P (n2->decl))
431 && (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl)
432 || !types_must_be_same_for_odr (DECL_CONTEXT (n1->decl),
433 DECL_CONTEXT (n2->decl)))
434 && (!used_by || !is_a <cgraph_node *> (used_by) || address
435 || opt_for_fn (used_by->decl, flag_devirtualize)))
436 return return_false_with_msg
437 ("references to virtual tables can not be merged");
439 if (address && DECL_ALIGN (n1->decl) != DECL_ALIGN (n2->decl))
440 return return_false_with_msg ("alignment mismatch");
442 /* For functions we compare attributes in equals_wpa, because we do
443 not know what attributes may cause codegen differences, but for
444 variables just compare attributes for references - the codegen
445 for constructors is affected only by those attributes that we lower
446 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
447 if (!compare_attributes (DECL_ATTRIBUTES (n1->decl),
448 DECL_ATTRIBUTES (n2->decl)))
449 return return_false_with_msg ("different var decl attributes");
450 if (comp_type_attributes (TREE_TYPE (n1->decl),
451 TREE_TYPE (n2->decl)) != 1)
452 return return_false_with_msg ("different var type attributes");
455 /* When matching virtual tables, be sure to also match information
456 relevant for polymorphic call analysis. */
457 if (used_by && is_a <varpool_node *> (used_by)
458 && DECL_VIRTUAL_P (used_by->decl))
460 if (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl))
461 return return_false_with_msg ("virtual flag mismatch");
462 if (DECL_VIRTUAL_P (n1->decl) && is_a <cgraph_node *> (n1)
463 && (DECL_FINAL_P (n1->decl) != DECL_FINAL_P (n2->decl)))
464 return return_false_with_msg ("final flag mismatch");
466 return true;
469 /* Hash properties that are compared by compare_referenced_symbol_properties. */
471 void
472 sem_item::hash_referenced_symbol_properties (symtab_node *ref,
473 inchash::hash &hstate,
474 bool address)
476 if (is_a <cgraph_node *> (ref))
478 if ((type != FUNC || address || !opt_for_fn (decl, optimize_size))
479 && !opt_for_fn (ref->decl, optimize_size)
480 && !DECL_UNINLINABLE (ref->decl))
482 hstate.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref->decl));
483 hstate.add_flag (DECL_DECLARED_INLINE_P (ref->decl));
485 hstate.add_flag (DECL_IS_OPERATOR_NEW (ref->decl));
487 else if (is_a <varpool_node *> (ref))
489 hstate.add_flag (DECL_VIRTUAL_P (ref->decl));
490 if (address)
491 hstate.add_int (DECL_ALIGN (ref->decl));
496 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
497 point to a same function. Comparison can be skipped if IGNORED_NODES
498 contains these nodes. ADDRESS indicate if address is taken. */
500 bool
501 sem_item::compare_symbol_references (
502 hash_map <symtab_node *, sem_item *> &ignored_nodes,
503 symtab_node *n1, symtab_node *n2, bool address)
505 enum availability avail1, avail2;
507 if (n1 == n2)
508 return true;
510 /* Never match variable and function. */
511 if (is_a <varpool_node *> (n1) != is_a <varpool_node *> (n2))
512 return false;
514 if (!compare_referenced_symbol_properties (node, n1, n2, address))
515 return false;
516 if (address && n1->equal_address_to (n2) == 1)
517 return true;
518 if (!address && n1->semantically_equivalent_p (n2))
519 return true;
521 n1 = n1->ultimate_alias_target (&avail1);
522 n2 = n2->ultimate_alias_target (&avail2);
524 if (avail1 >= AVAIL_INTERPOSABLE && ignored_nodes.get (n1)
525 && avail2 >= AVAIL_INTERPOSABLE && ignored_nodes.get (n2))
526 return true;
528 return return_false_with_msg ("different references");
531 /* If cgraph edges E1 and E2 are indirect calls, verify that
532 ECF flags are the same. */
534 bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
536 if (e1->indirect_info && e2->indirect_info)
538 int e1_flags = e1->indirect_info->ecf_flags;
539 int e2_flags = e2->indirect_info->ecf_flags;
541 if (e1_flags != e2_flags)
542 return return_false_with_msg ("ICF flags are different");
544 else if (e1->indirect_info || e2->indirect_info)
545 return false;
547 return true;
550 /* Return true if parameter I may be used. */
552 bool
553 sem_function::param_used_p (unsigned int i)
555 if (ipa_node_params_sum == NULL)
556 return false;
558 struct ipa_node_params *parms_info = IPA_NODE_REF (get_node ());
560 if (parms_info->descriptors.is_empty ()
561 || parms_info->descriptors.length () <= i)
562 return true;
564 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i);
567 /* Perform additional check needed to match types function parameters that are
568 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
569 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
571 bool
572 sem_function::compatible_parm_types_p (tree parm1, tree parm2)
574 /* Be sure that parameters are TBAA compatible. */
575 if (!func_checker::compatible_types_p (parm1, parm2))
576 return return_false_with_msg ("parameter type is not compatible");
578 if (POINTER_TYPE_P (parm1)
579 && (TYPE_RESTRICT (parm1) != TYPE_RESTRICT (parm2)))
580 return return_false_with_msg ("argument restrict flag mismatch");
582 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
583 if (POINTER_TYPE_P (parm1)
584 && TREE_CODE (parm1) != TREE_CODE (parm2)
585 && opt_for_fn (decl, flag_delete_null_pointer_checks))
586 return return_false_with_msg ("pointer wrt reference mismatch");
588 return true;
591 /* Fast equality function based on knowledge known in WPA. */
593 bool
594 sem_function::equals_wpa (sem_item *item,
595 hash_map <symtab_node *, sem_item *> &ignored_nodes)
597 gcc_assert (item->type == FUNC);
598 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
599 cgraph_node *cnode2 = dyn_cast <cgraph_node *> (item->node);
601 m_compared_func = static_cast<sem_function *> (item);
603 if (cnode->thunk.thunk_p != cnode2->thunk.thunk_p)
604 return return_false_with_msg ("thunk_p mismatch");
606 if (cnode->thunk.thunk_p)
608 if (cnode->thunk.fixed_offset != cnode2->thunk.fixed_offset)
609 return return_false_with_msg ("thunk fixed_offset mismatch");
610 if (cnode->thunk.virtual_value != cnode2->thunk.virtual_value)
611 return return_false_with_msg ("thunk virtual_value mismatch");
612 if (cnode->thunk.this_adjusting != cnode2->thunk.this_adjusting)
613 return return_false_with_msg ("thunk this_adjusting mismatch");
614 if (cnode->thunk.virtual_offset_p != cnode2->thunk.virtual_offset_p)
615 return return_false_with_msg ("thunk virtual_offset_p mismatch");
616 if (cnode->thunk.add_pointer_bounds_args
617 != cnode2->thunk.add_pointer_bounds_args)
618 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
621 /* Compare special function DECL attributes. */
622 if (DECL_FUNCTION_PERSONALITY (decl)
623 != DECL_FUNCTION_PERSONALITY (item->decl))
624 return return_false_with_msg ("function personalities are different");
626 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
627 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item->decl))
628 return return_false_with_msg ("intrument function entry exit "
629 "attributes are different");
631 if (DECL_NO_LIMIT_STACK (decl) != DECL_NO_LIMIT_STACK (item->decl))
632 return return_false_with_msg ("no stack limit attributes are different");
634 if (DECL_CXX_CONSTRUCTOR_P (decl) != DECL_CXX_CONSTRUCTOR_P (item->decl))
635 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
637 if (DECL_CXX_DESTRUCTOR_P (decl) != DECL_CXX_DESTRUCTOR_P (item->decl))
638 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
640 /* TODO: pure/const flags mostly matters only for references, except for
641 the fact that codegen takes LOOPING flag as a hint that loops are
642 finite. We may arrange the code to always pick leader that has least
643 specified flags and then this can go into comparing symbol properties. */
644 if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
645 return return_false_with_msg ("decl_or_type flags are different");
647 /* Do not match polymorphic constructors of different types. They calls
648 type memory location for ipa-polymorphic-call and we do not want
649 it to get confused by wrong type. */
650 if (DECL_CXX_CONSTRUCTOR_P (decl)
651 && TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE)
653 if (TREE_CODE (TREE_TYPE (item->decl)) != METHOD_TYPE)
654 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
655 else if (!func_checker::compatible_polymorphic_types_p
656 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
657 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
658 return return_false_with_msg ("ctor polymorphic type mismatch");
661 /* Checking function TARGET and OPTIMIZATION flags. */
662 cl_target_option *tar1 = target_opts_for_fn (decl);
663 cl_target_option *tar2 = target_opts_for_fn (item->decl);
665 if (tar1 != tar2 && !cl_target_option_eq (tar1, tar2))
667 if (dump_file && (dump_flags & TDF_DETAILS))
669 fprintf (dump_file, "target flags difference");
670 cl_target_option_print_diff (dump_file, 2, tar1, tar2);
673 return return_false_with_msg ("Target flags are different");
676 cl_optimization *opt1 = opts_for_fn (decl);
677 cl_optimization *opt2 = opts_for_fn (item->decl);
679 if (opt1 != opt2 && memcmp (opt1, opt2, sizeof(cl_optimization)))
681 if (dump_file && (dump_flags & TDF_DETAILS))
683 fprintf (dump_file, "optimization flags difference");
684 cl_optimization_print_diff (dump_file, 2, opt1, opt2);
687 return return_false_with_msg ("optimization flags are different");
690 /* Result type checking. */
691 if (!func_checker::compatible_types_p
692 (TREE_TYPE (TREE_TYPE (decl)),
693 TREE_TYPE (TREE_TYPE (m_compared_func->decl))))
694 return return_false_with_msg ("result types are different");
696 /* Checking types of arguments. */
697 tree list1 = TYPE_ARG_TYPES (TREE_TYPE (decl)),
698 list2 = TYPE_ARG_TYPES (TREE_TYPE (m_compared_func->decl));
699 for (unsigned i = 0; list1 && list2;
700 list1 = TREE_CHAIN (list1), list2 = TREE_CHAIN (list2), i++)
702 tree parm1 = TREE_VALUE (list1);
703 tree parm2 = TREE_VALUE (list2);
705 /* This guard is here for function pointer with attributes (pr59927.c). */
706 if (!parm1 || !parm2)
707 return return_false_with_msg ("NULL argument type");
709 /* Verify that types are compatible to ensure that both functions
710 have same calling conventions. */
711 if (!types_compatible_p (parm1, parm2))
712 return return_false_with_msg ("parameter types are not compatible");
714 if (!param_used_p (i))
715 continue;
717 /* Perform additional checks for used parameters. */
718 if (!compatible_parm_types_p (parm1, parm2))
719 return false;
722 if (list1 || list2)
723 return return_false_with_msg ("Mismatched number of parameters");
725 if (node->num_references () != item->node->num_references ())
726 return return_false_with_msg ("different number of references");
728 /* Checking function attributes.
729 This is quadratic in number of attributes */
730 if (comp_type_attributes (TREE_TYPE (decl),
731 TREE_TYPE (item->decl)) != 1)
732 return return_false_with_msg ("different type attributes");
733 if (!compare_attributes (DECL_ATTRIBUTES (decl),
734 DECL_ATTRIBUTES (item->decl)))
735 return return_false_with_msg ("different decl attributes");
737 /* The type of THIS pointer type memory location for
738 ipa-polymorphic-call-analysis. */
739 if (opt_for_fn (decl, flag_devirtualize)
740 && (TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE
741 || TREE_CODE (TREE_TYPE (item->decl)) == METHOD_TYPE)
742 && param_used_p (0)
743 && compare_polymorphic_p ())
745 if (TREE_CODE (TREE_TYPE (decl)) != TREE_CODE (TREE_TYPE (item->decl)))
746 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
747 if (!func_checker::compatible_polymorphic_types_p
748 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
749 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
750 return return_false_with_msg ("THIS pointer ODR type mismatch");
753 ipa_ref *ref = NULL, *ref2 = NULL;
754 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
756 item->node->iterate_reference (i, ref2);
758 if (ref->use != ref2->use)
759 return return_false_with_msg ("reference use mismatch");
761 if (!compare_symbol_references (ignored_nodes, ref->referred,
762 ref2->referred,
763 ref->address_matters_p ()))
764 return false;
767 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
768 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
770 while (e1 && e2)
772 if (!compare_symbol_references (ignored_nodes, e1->callee,
773 e2->callee, false))
774 return false;
775 if (!compare_edge_flags (e1, e2))
776 return false;
778 e1 = e1->next_callee;
779 e2 = e2->next_callee;
782 if (e1 || e2)
783 return return_false_with_msg ("different number of calls");
785 e1 = dyn_cast <cgraph_node *> (node)->indirect_calls;
786 e2 = dyn_cast <cgraph_node *> (item->node)->indirect_calls;
788 while (e1 && e2)
790 if (!compare_edge_flags (e1, e2))
791 return false;
793 e1 = e1->next_callee;
794 e2 = e2->next_callee;
797 if (e1 || e2)
798 return return_false_with_msg ("different number of indirect calls");
800 return true;
803 /* Update hash by address sensitive references. We iterate over all
804 sensitive references (address_matters_p) and we hash ultime alias
805 target of these nodes, which can improve a semantic item hash.
807 Also hash in referenced symbols properties. This can be done at any time
808 (as the properties should not change), but it is convenient to do it here
809 while we walk the references anyway. */
811 void
812 sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
813 sem_item *> &m_symtab_node_map)
815 ipa_ref* ref;
816 inchash::hash hstate (hash);
818 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
820 hstate.add_int (ref->use);
821 hash_referenced_symbol_properties (ref->referred, hstate,
822 ref->use == IPA_REF_ADDR);
823 if (ref->address_matters_p () || !m_symtab_node_map.get (ref->referred))
824 hstate.add_int (ref->referred->ultimate_alias_target ()->order);
827 if (is_a <cgraph_node *> (node))
829 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
830 e = e->next_caller)
832 sem_item **result = m_symtab_node_map.get (e->callee);
833 hash_referenced_symbol_properties (e->callee, hstate, false);
834 if (!result)
835 hstate.add_int (e->callee->ultimate_alias_target ()->order);
839 hash = hstate.end ();
842 /* Update hash by computed local hash values taken from different
843 semantic items.
844 TODO: stronger SCC based hashing would be desirable here. */
846 void
847 sem_item::update_hash_by_local_refs (hash_map <symtab_node *,
848 sem_item *> &m_symtab_node_map)
850 ipa_ref* ref;
851 inchash::hash state (hash);
853 for (unsigned j = 0; node->iterate_reference (j, ref); j++)
855 sem_item **result = m_symtab_node_map.get (ref->referring);
856 if (result)
857 state.merge_hash ((*result)->hash);
860 if (type == FUNC)
862 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e;
863 e = e->next_callee)
865 sem_item **result = m_symtab_node_map.get (e->caller);
866 if (result)
867 state.merge_hash ((*result)->hash);
871 global_hash = state.end ();
874 /* Returns true if the item equals to ITEM given as argument. */
876 bool
877 sem_function::equals (sem_item *item,
878 hash_map <symtab_node *, sem_item *> &)
880 gcc_assert (item->type == FUNC);
881 bool eq = equals_private (item);
883 if (m_checker != NULL)
885 delete m_checker;
886 m_checker = NULL;
889 if (dump_file && (dump_flags & TDF_DETAILS))
890 fprintf (dump_file,
891 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
892 xstrdup_for_dump (node->name()),
893 xstrdup_for_dump (item->node->name ()),
894 node->order,
895 item->node->order,
896 xstrdup_for_dump (node->asm_name ()),
897 xstrdup_for_dump (item->node->asm_name ()),
898 eq ? "true" : "false");
900 return eq;
903 /* Processes function equality comparison. */
905 bool
906 sem_function::equals_private (sem_item *item)
908 if (item->type != FUNC)
909 return false;
911 basic_block bb1, bb2;
912 edge e1, e2;
913 edge_iterator ei1, ei2;
914 bool result = true;
915 tree arg1, arg2;
917 m_compared_func = static_cast<sem_function *> (item);
919 gcc_assert (decl != item->decl);
921 if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
922 || edge_count != m_compared_func->edge_count
923 || cfg_checksum != m_compared_func->cfg_checksum)
924 return return_false ();
926 m_checker = new func_checker (decl, m_compared_func->decl,
927 compare_polymorphic_p (),
928 false,
929 &refs_set,
930 &m_compared_func->refs_set);
931 arg1 = DECL_ARGUMENTS (decl);
932 arg2 = DECL_ARGUMENTS (m_compared_func->decl);
933 for (unsigned i = 0;
934 arg1 && arg2; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2), i++)
936 if (!types_compatible_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
937 return return_false_with_msg ("argument types are not compatible");
938 if (!param_used_p (i))
939 continue;
940 /* Perform additional checks for used parameters. */
941 if (!compatible_parm_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
942 return false;
943 if (!m_checker->compare_decl (arg1, arg2))
944 return return_false ();
946 if (arg1 || arg2)
947 return return_false_with_msg ("Mismatched number of arguments");
949 if (!dyn_cast <cgraph_node *> (node)->has_gimple_body_p ())
950 return true;
952 /* Fill-up label dictionary. */
953 for (unsigned i = 0; i < bb_sorted.length (); ++i)
955 m_checker->parse_labels (bb_sorted[i]);
956 m_checker->parse_labels (m_compared_func->bb_sorted[i]);
959 /* Checking all basic blocks. */
960 for (unsigned i = 0; i < bb_sorted.length (); ++i)
961 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
962 return return_false();
964 dump_message ("All BBs are equal\n");
966 auto_vec <int> bb_dict;
968 /* Basic block edges check. */
969 for (unsigned i = 0; i < bb_sorted.length (); ++i)
971 bb1 = bb_sorted[i]->bb;
972 bb2 = m_compared_func->bb_sorted[i]->bb;
974 ei2 = ei_start (bb2->preds);
976 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
978 ei_cond (ei2, &e2);
980 if (e1->flags != e2->flags)
981 return return_false_with_msg ("flags comparison returns false");
983 if (!bb_dict_test (&bb_dict, e1->src->index, e2->src->index))
984 return return_false_with_msg ("edge comparison returns false");
986 if (!bb_dict_test (&bb_dict, e1->dest->index, e2->dest->index))
987 return return_false_with_msg ("BB comparison returns false");
989 if (!m_checker->compare_edge (e1, e2))
990 return return_false_with_msg ("edge comparison returns false");
992 ei_next (&ei2);
996 /* Basic block PHI nodes comparison. */
997 for (unsigned i = 0; i < bb_sorted.length (); i++)
998 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
999 return return_false_with_msg ("PHI node comparison returns false");
1001 return result;
1004 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
1005 Helper for call_for_symbol_thunks_and_aliases. */
1007 static bool
1008 set_local (cgraph_node *node, void *data)
1010 node->local.local = data != NULL;
1011 return false;
1014 /* TREE_ADDRESSABLE of NODE to true.
1015 Helper for call_for_symbol_thunks_and_aliases. */
1017 static bool
1018 set_addressable (varpool_node *node, void *)
1020 TREE_ADDRESSABLE (node->decl) = 1;
1021 return false;
1024 /* Clear DECL_RTL of NODE.
1025 Helper for call_for_symbol_thunks_and_aliases. */
1027 static bool
1028 clear_decl_rtl (symtab_node *node, void *)
1030 SET_DECL_RTL (node->decl, NULL);
1031 return false;
1034 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1035 possible. Return number of redirections made. */
1037 static int
1038 redirect_all_callers (cgraph_node *n, cgraph_node *to)
1040 int nredirected = 0;
1041 ipa_ref *ref;
1042 cgraph_edge *e = n->callers;
1044 while (e)
1046 /* Redirecting thunks to interposable symbols or symbols in other sections
1047 may not be supported by target output code. Play safe for now and
1048 punt on redirection. */
1049 if (!e->caller->thunk.thunk_p)
1051 struct cgraph_edge *nexte = e->next_caller;
1052 e->redirect_callee (to);
1053 e = nexte;
1054 nredirected++;
1056 else
1057 e = e->next_callee;
1059 for (unsigned i = 0; n->iterate_direct_aliases (i, ref);)
1061 bool removed = false;
1062 cgraph_node *n_alias = dyn_cast <cgraph_node *> (ref->referring);
1064 if ((DECL_COMDAT_GROUP (n->decl)
1065 && (DECL_COMDAT_GROUP (n->decl)
1066 == DECL_COMDAT_GROUP (n_alias->decl)))
1067 || (n_alias->get_availability () > AVAIL_INTERPOSABLE
1068 && n->get_availability () > AVAIL_INTERPOSABLE))
1070 nredirected += redirect_all_callers (n_alias, to);
1071 if (n_alias->can_remove_if_no_direct_calls_p ()
1072 && !n_alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1073 NULL, true)
1074 && !n_alias->has_aliases_p ())
1075 n_alias->remove ();
1077 if (!removed)
1078 i++;
1080 return nredirected;
1083 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1084 be applied. */
1086 bool
1087 sem_function::merge (sem_item *alias_item)
1089 gcc_assert (alias_item->type == FUNC);
1091 sem_function *alias_func = static_cast<sem_function *> (alias_item);
1093 cgraph_node *original = get_node ();
1094 cgraph_node *local_original = NULL;
1095 cgraph_node *alias = alias_func->get_node ();
1097 bool create_wrapper = false;
1098 bool create_alias = false;
1099 bool redirect_callers = false;
1100 bool remove = false;
1102 bool original_discardable = false;
1103 bool original_discarded = false;
1105 bool original_address_matters = original->address_matters_p ();
1106 bool alias_address_matters = alias->address_matters_p ();
1108 if (DECL_EXTERNAL (alias->decl))
1110 if (dump_file)
1111 fprintf (dump_file, "Not unifying; alias is external.\n\n");
1112 return false;
1115 if (DECL_NO_INLINE_WARNING_P (original->decl)
1116 != DECL_NO_INLINE_WARNING_P (alias->decl))
1118 if (dump_file)
1119 fprintf (dump_file,
1120 "Not unifying; "
1121 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1122 return false;
1125 /* Do not attempt to mix functions from different user sections;
1126 we do not know what user intends with those. */
1127 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
1128 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
1129 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
1131 if (dump_file)
1132 fprintf (dump_file,
1133 "Not unifying; "
1134 "original and alias are in different sections.\n\n");
1135 return false;
1138 /* See if original is in a section that can be discarded if the main
1139 symbol is not used. */
1141 if (original->can_be_discarded_p ())
1142 original_discardable = true;
1143 /* Also consider case where we have resolution info and we know that
1144 original's definition is not going to be used. In this case we can not
1145 create alias to original. */
1146 if (node->resolution != LDPR_UNKNOWN
1147 && !decl_binds_to_current_def_p (node->decl))
1148 original_discardable = original_discarded = true;
1150 /* Creating a symtab alias is the optimal way to merge.
1151 It however can not be used in the following cases:
1153 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1154 2) if ORIGINAL is in a section that may be discarded by linker or if
1155 it is an external functions where we can not create an alias
1156 (ORIGINAL_DISCARDABLE)
1157 3) if target do not support symbol aliases.
1158 4) original and alias lie in different comdat groups.
1160 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1161 and/or redirect all callers from ALIAS to ORIGINAL. */
1162 if ((original_address_matters && alias_address_matters)
1163 || (original_discardable
1164 && (!DECL_COMDAT_GROUP (alias->decl)
1165 || (DECL_COMDAT_GROUP (alias->decl)
1166 != DECL_COMDAT_GROUP (original->decl))))
1167 || original_discarded
1168 || !sem_item::target_supports_symbol_aliases_p ()
1169 || DECL_COMDAT_GROUP (alias->decl) != DECL_COMDAT_GROUP (original->decl))
1171 /* First see if we can produce wrapper. */
1173 /* Symbol properties that matter for references must be preserved.
1174 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1175 with proper properties. */
1176 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1177 alias->address_taken))
1179 if (dump_file)
1180 fprintf (dump_file,
1181 "Wrapper cannot be created because referenced symbol "
1182 "properties mismatch\n");
1184 /* Do not turn function in one comdat group into wrapper to another
1185 comdat group. Other compiler producing the body of the
1186 another comdat group may make opossite decision and with unfortunate
1187 linker choices this may close a loop. */
1188 else if (DECL_COMDAT_GROUP (original->decl)
1189 && DECL_COMDAT_GROUP (alias->decl)
1190 && (DECL_COMDAT_GROUP (alias->decl)
1191 != DECL_COMDAT_GROUP (original->decl)))
1193 if (dump_file)
1194 fprintf (dump_file,
1195 "Wrapper cannot be created because of COMDAT\n");
1197 else if (DECL_STATIC_CHAIN (alias->decl))
1199 if (dump_file)
1200 fprintf (dump_file,
1201 "Can not create wrapper of nested functions.\n");
1203 /* TODO: We can also deal with variadic functions never calling
1204 VA_START. */
1205 else if (stdarg_p (TREE_TYPE (alias->decl)))
1207 if (dump_file)
1208 fprintf (dump_file,
1209 "can not create wrapper of stdarg function.\n");
1211 else if (inline_summaries
1212 && inline_summaries->get (alias)->self_size <= 2)
1214 if (dump_file)
1215 fprintf (dump_file, "Wrapper creation is not "
1216 "profitable (function is too small).\n");
1218 /* If user paid attention to mark function noinline, assume it is
1219 somewhat special and do not try to turn it into a wrapper that can
1220 not be undone by inliner. */
1221 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
1223 if (dump_file)
1224 fprintf (dump_file, "Wrappers are not created for noinline.\n");
1226 else
1227 create_wrapper = true;
1229 /* We can redirect local calls in the case both alias and orignal
1230 are not interposable. */
1231 redirect_callers
1232 = alias->get_availability () > AVAIL_INTERPOSABLE
1233 && original->get_availability () > AVAIL_INTERPOSABLE
1234 && !alias->instrumented_version;
1235 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1236 with proper properties. */
1237 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1238 alias->address_taken))
1239 redirect_callers = false;
1241 if (!redirect_callers && !create_wrapper)
1243 if (dump_file)
1244 fprintf (dump_file, "Not unifying; can not redirect callers nor "
1245 "produce wrapper\n\n");
1246 return false;
1249 /* Work out the symbol the wrapper should call.
1250 If ORIGINAL is interposable, we need to call a local alias.
1251 Also produce local alias (if possible) as an optimization.
1253 Local aliases can not be created inside comdat groups because that
1254 prevents inlining. */
1255 if (!original_discardable && !original->get_comdat_group ())
1257 local_original
1258 = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
1259 if (!local_original
1260 && original->get_availability () > AVAIL_INTERPOSABLE)
1261 local_original = original;
1263 /* If we can not use local alias, fallback to the original
1264 when possible. */
1265 else if (original->get_availability () > AVAIL_INTERPOSABLE)
1266 local_original = original;
1268 /* If original is COMDAT local, we can not really redirect calls outside
1269 of its comdat group to it. */
1270 if (original->comdat_local_p ())
1271 redirect_callers = false;
1272 if (!local_original)
1274 if (dump_file)
1275 fprintf (dump_file, "Not unifying; "
1276 "can not produce local alias.\n\n");
1277 return false;
1280 if (!redirect_callers && !create_wrapper)
1282 if (dump_file)
1283 fprintf (dump_file, "Not unifying; "
1284 "can not redirect callers nor produce a wrapper\n\n");
1285 return false;
1287 if (!create_wrapper
1288 && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1289 NULL, true)
1290 && !alias->can_remove_if_no_direct_calls_p ())
1292 if (dump_file)
1293 fprintf (dump_file, "Not unifying; can not make wrapper and "
1294 "function has other uses than direct calls\n\n");
1295 return false;
1298 else
1299 create_alias = true;
1301 if (redirect_callers)
1303 int nredirected = redirect_all_callers (alias, local_original);
1305 if (nredirected)
1307 alias->icf_merged = true;
1308 local_original->icf_merged = true;
1310 if (dump_file && nredirected)
1311 fprintf (dump_file, "%i local calls have been "
1312 "redirected.\n", nredirected);
1315 /* If all callers was redirected, do not produce wrapper. */
1316 if (alias->can_remove_if_no_direct_calls_p ()
1317 && !alias->has_aliases_p ())
1319 create_wrapper = false;
1320 remove = true;
1322 gcc_assert (!create_alias);
1324 else if (create_alias)
1326 alias->icf_merged = true;
1328 /* Remove the function's body. */
1329 ipa_merge_profiles (original, alias);
1330 alias->release_body (true);
1331 alias->reset ();
1332 /* Notice global symbol possibly produced RTL. */
1333 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
1334 NULL, true);
1336 /* Create the alias. */
1337 cgraph_node::create_alias (alias_func->decl, decl);
1338 alias->resolve_alias (original);
1340 original->call_for_symbol_thunks_and_aliases
1341 (set_local, (void *)(size_t) original->local_p (), true);
1343 if (dump_file)
1344 fprintf (dump_file, "Unified; Function alias has been created.\n\n");
1346 if (create_wrapper)
1348 gcc_assert (!create_alias);
1349 alias->icf_merged = true;
1350 local_original->icf_merged = true;
1352 ipa_merge_profiles (local_original, alias, true);
1353 alias->create_wrapper (local_original);
1355 if (dump_file)
1356 fprintf (dump_file, "Unified; Wrapper has been created.\n\n");
1359 /* It's possible that redirection can hit thunks that block
1360 redirection opportunities. */
1361 gcc_assert (alias->icf_merged || remove || redirect_callers);
1362 original->icf_merged = true;
1364 /* Inform the inliner about cross-module merging. */
1365 if ((original->lto_file_data || alias->lto_file_data)
1366 && original->lto_file_data != alias->lto_file_data)
1367 local_original->merged = original->merged = true;
1369 if (remove)
1371 ipa_merge_profiles (original, alias);
1372 alias->release_body ();
1373 alias->reset ();
1374 alias->body_removed = true;
1375 alias->icf_merged = true;
1376 if (dump_file)
1377 fprintf (dump_file, "Unified; Function body was removed.\n");
1380 return true;
1383 /* Semantic item initialization function. */
1385 void
1386 sem_function::init (void)
1388 if (in_lto_p)
1389 get_node ()->get_untransformed_body ();
1391 tree fndecl = node->decl;
1392 function *func = DECL_STRUCT_FUNCTION (fndecl);
1394 gcc_assert (func);
1395 gcc_assert (SSANAMES (func));
1397 ssa_names_size = SSANAMES (func)->length ();
1398 node = node;
1400 decl = fndecl;
1401 region_tree = func->eh->region_tree;
1403 /* iterating all function arguments. */
1404 arg_count = count_formal_params (fndecl);
1406 edge_count = n_edges_for_fn (func);
1407 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1408 if (!cnode->thunk.thunk_p)
1410 cfg_checksum = coverage_compute_cfg_checksum (func);
1412 inchash::hash hstate;
1414 basic_block bb;
1415 FOR_EACH_BB_FN (bb, func)
1417 unsigned nondbg_stmt_count = 0;
1419 edge e;
1420 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
1421 ei_next (&ei))
1422 cfg_checksum = iterative_hash_host_wide_int (e->flags,
1423 cfg_checksum);
1425 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1426 gsi_next (&gsi))
1428 gimple stmt = gsi_stmt (gsi);
1430 if (gimple_code (stmt) != GIMPLE_DEBUG
1431 && gimple_code (stmt) != GIMPLE_PREDICT)
1433 hash_stmt (stmt, hstate);
1434 nondbg_stmt_count++;
1438 gcode_hash = hstate.end ();
1439 bb_sizes.safe_push (nondbg_stmt_count);
1441 /* Inserting basic block to hash table. */
1442 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
1443 EDGE_COUNT (bb->preds)
1444 + EDGE_COUNT (bb->succs));
1446 bb_sorted.safe_push (semantic_bb);
1449 else
1451 cfg_checksum = 0;
1452 inchash::hash hstate;
1453 hstate.add_wide_int (cnode->thunk.fixed_offset);
1454 hstate.add_wide_int (cnode->thunk.virtual_value);
1455 hstate.add_flag (cnode->thunk.this_adjusting);
1456 hstate.add_flag (cnode->thunk.virtual_offset_p);
1457 hstate.add_flag (cnode->thunk.add_pointer_bounds_args);
1458 gcode_hash = hstate.end ();
1462 /* Accumulate to HSTATE a hash of expression EXP.
1463 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1464 and DECL equality classes. */
1466 void
1467 sem_item::add_expr (const_tree exp, inchash::hash &hstate)
1469 if (exp == NULL_TREE)
1471 hstate.merge_hash (0);
1472 return;
1475 /* Handled component can be matched in a cureful way proving equivalence
1476 even if they syntactically differ. Just skip them. */
1477 STRIP_NOPS (exp);
1478 while (handled_component_p (exp))
1479 exp = TREE_OPERAND (exp, 0);
1481 enum tree_code code = TREE_CODE (exp);
1482 hstate.add_int (code);
1484 switch (code)
1486 /* Use inchash::add_expr for everything that is LTO stable. */
1487 case VOID_CST:
1488 case INTEGER_CST:
1489 case REAL_CST:
1490 case FIXED_CST:
1491 case STRING_CST:
1492 case COMPLEX_CST:
1493 case VECTOR_CST:
1494 inchash::add_expr (exp, hstate);
1495 break;
1496 case CONSTRUCTOR:
1498 unsigned HOST_WIDE_INT idx;
1499 tree value;
1501 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1503 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp), idx, value)
1504 if (value)
1505 add_expr (value, hstate);
1506 break;
1508 case ADDR_EXPR:
1509 case FDESC_EXPR:
1510 add_expr (get_base_address (TREE_OPERAND (exp, 0)), hstate);
1511 break;
1512 case SSA_NAME:
1513 case VAR_DECL:
1514 case CONST_DECL:
1515 case PARM_DECL:
1516 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1517 break;
1518 case MEM_REF:
1519 case POINTER_PLUS_EXPR:
1520 case MINUS_EXPR:
1521 case RANGE_EXPR:
1522 add_expr (TREE_OPERAND (exp, 0), hstate);
1523 add_expr (TREE_OPERAND (exp, 1), hstate);
1524 break;
1525 case PLUS_EXPR:
1527 inchash::hash one, two;
1528 add_expr (TREE_OPERAND (exp, 0), one);
1529 add_expr (TREE_OPERAND (exp, 1), two);
1530 hstate.add_commutative (one, two);
1532 break;
1533 CASE_CONVERT:
1534 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1535 return add_expr (TREE_OPERAND (exp, 0), hstate);
1536 default:
1537 break;
1541 /* Accumulate to HSTATE a hash of type t.
1542 TYpes that may end up being compatible after LTO type merging needs to have
1543 the same hash. */
1545 void
1546 sem_item::add_type (const_tree type, inchash::hash &hstate)
1548 if (type == NULL_TREE)
1550 hstate.merge_hash (0);
1551 return;
1554 type = TYPE_MAIN_VARIANT (type);
1555 if (TYPE_CANONICAL (type))
1556 type = TYPE_CANONICAL (type);
1558 if (!AGGREGATE_TYPE_P (type))
1559 hstate.add_int (TYPE_MODE (type));
1561 if (TREE_CODE (type) == COMPLEX_TYPE)
1563 hstate.add_int (COMPLEX_TYPE);
1564 sem_item::add_type (TREE_TYPE (type), hstate);
1566 else if (INTEGRAL_TYPE_P (type))
1568 hstate.add_int (INTEGER_TYPE);
1569 hstate.add_flag (TYPE_UNSIGNED (type));
1570 hstate.add_int (TYPE_PRECISION (type));
1572 else if (VECTOR_TYPE_P (type))
1574 hstate.add_int (VECTOR_TYPE);
1575 hstate.add_int (TYPE_PRECISION (type));
1576 sem_item::add_type (TREE_TYPE (type), hstate);
1578 else if (TREE_CODE (type) == ARRAY_TYPE)
1580 hstate.add_int (ARRAY_TYPE);
1581 /* Do not hash size, so complete and incomplete types can match. */
1582 sem_item::add_type (TREE_TYPE (type), hstate);
1584 else if (RECORD_OR_UNION_TYPE_P (type))
1586 hashval_t *val = optimizer->m_type_hash_cache.get (type);
1588 if (!val)
1590 inchash::hash hstate2;
1591 unsigned nf;
1592 tree f;
1593 hashval_t hash;
1595 hstate2.add_int (RECORD_TYPE);
1596 gcc_assert (COMPLETE_TYPE_P (type));
1598 for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
1599 if (TREE_CODE (f) == FIELD_DECL)
1601 add_type (TREE_TYPE (f), hstate2);
1602 nf++;
1605 hstate2.add_int (nf);
1606 hash = hstate2.end ();
1607 hstate.add_wide_int (hash);
1608 optimizer->m_type_hash_cache.put (type, hash);
1610 else
1611 hstate.add_wide_int (*val);
1615 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1617 void
1618 sem_function::hash_stmt (gimple stmt, inchash::hash &hstate)
1620 enum gimple_code code = gimple_code (stmt);
1622 hstate.add_int (code);
1624 switch (code)
1626 case GIMPLE_SWITCH:
1627 add_expr (gimple_switch_index (as_a <gswitch *> (stmt)), hstate);
1628 break;
1629 case GIMPLE_ASSIGN:
1630 hstate.add_int (gimple_assign_rhs_code (stmt));
1631 if (commutative_tree_code (gimple_assign_rhs_code (stmt))
1632 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1634 inchash::hash one, two;
1636 add_expr (gimple_assign_rhs1 (stmt), one);
1637 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt)), one);
1638 add_expr (gimple_assign_rhs2 (stmt), two);
1639 hstate.add_commutative (one, two);
1640 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1642 add_expr (gimple_assign_rhs3 (stmt), hstate);
1643 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt)), hstate);
1645 add_expr (gimple_assign_lhs (stmt), hstate);
1646 add_type (TREE_TYPE (gimple_assign_lhs (stmt)), two);
1647 break;
1649 /* ... fall through ... */
1650 case GIMPLE_CALL:
1651 case GIMPLE_ASM:
1652 case GIMPLE_COND:
1653 case GIMPLE_GOTO:
1654 case GIMPLE_RETURN:
1655 /* All these statements are equivalent if their operands are. */
1656 for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1658 add_expr (gimple_op (stmt, i), hstate);
1659 if (gimple_op (stmt, i))
1660 add_type (TREE_TYPE (gimple_op (stmt, i)), hstate);
1662 default:
1663 break;
1668 /* Return true if polymorphic comparison must be processed. */
1670 bool
1671 sem_function::compare_polymorphic_p (void)
1673 struct cgraph_edge *e;
1675 if (!opt_for_fn (get_node ()->decl, flag_devirtualize))
1676 return false;
1677 if (get_node ()->indirect_calls != NULL)
1678 return true;
1679 /* TODO: We can do simple propagation determining what calls may lead to
1680 a polymorphic call. */
1681 for (e = get_node ()->callees; e; e = e->next_callee)
1682 if (e->callee->definition
1683 && opt_for_fn (e->callee->decl, flag_devirtualize))
1684 return true;
1685 return false;
1688 /* For a given call graph NODE, the function constructs new
1689 semantic function item. */
1691 sem_function *
1692 sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
1694 tree fndecl = node->decl;
1695 function *func = DECL_STRUCT_FUNCTION (fndecl);
1697 if (!func || (!node->has_gimple_body_p () && !node->thunk.thunk_p))
1698 return NULL;
1700 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
1701 return NULL;
1703 sem_function *f = new sem_function (node, 0, stack);
1705 f->init ();
1707 return f;
1710 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1711 return true if phi nodes are semantically equivalent in these blocks . */
1713 bool
1714 sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
1716 gphi_iterator si1, si2;
1717 gphi *phi1, *phi2;
1718 unsigned size1, size2, i;
1719 tree t1, t2;
1720 edge e1, e2;
1722 gcc_assert (bb1 != NULL);
1723 gcc_assert (bb2 != NULL);
1725 si2 = gsi_start_phis (bb2);
1726 for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
1727 gsi_next (&si1))
1729 gsi_next_nonvirtual_phi (&si1);
1730 gsi_next_nonvirtual_phi (&si2);
1732 if (gsi_end_p (si1) && gsi_end_p (si2))
1733 break;
1735 if (gsi_end_p (si1) || gsi_end_p (si2))
1736 return return_false();
1738 phi1 = si1.phi ();
1739 phi2 = si2.phi ();
1741 tree phi_result1 = gimple_phi_result (phi1);
1742 tree phi_result2 = gimple_phi_result (phi2);
1744 if (!m_checker->compare_operand (phi_result1, phi_result2))
1745 return return_false_with_msg ("PHI results are different");
1747 size1 = gimple_phi_num_args (phi1);
1748 size2 = gimple_phi_num_args (phi2);
1750 if (size1 != size2)
1751 return return_false ();
1753 for (i = 0; i < size1; ++i)
1755 t1 = gimple_phi_arg (phi1, i)->def;
1756 t2 = gimple_phi_arg (phi2, i)->def;
1758 if (!m_checker->compare_operand (t1, t2))
1759 return return_false ();
1761 e1 = gimple_phi_arg_edge (phi1, i);
1762 e2 = gimple_phi_arg_edge (phi2, i);
1764 if (!m_checker->compare_edge (e1, e2))
1765 return return_false ();
1768 gsi_next (&si2);
1771 return true;
1774 /* Returns true if tree T can be compared as a handled component. */
1776 bool
1777 sem_function::icf_handled_component_p (tree t)
1779 tree_code tc = TREE_CODE (t);
1781 return (handled_component_p (t)
1782 || tc == ADDR_EXPR || tc == MEM_REF || tc == OBJ_TYPE_REF);
1785 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1786 corresponds to TARGET. */
1788 bool
1789 sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
1791 source++;
1792 target++;
1794 if (bb_dict->length () <= (unsigned)source)
1795 bb_dict->safe_grow_cleared (source + 1);
1797 if ((*bb_dict)[source] == 0)
1799 (*bb_dict)[source] = target;
1800 return true;
1802 else
1803 return (*bb_dict)[source] == target;
1807 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1809 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
1813 /* Constructor based on varpool node _NODE with computed hash _HASH.
1814 Bitmap STACK is used for memory allocation. */
1816 sem_variable::sem_variable (varpool_node *node, hashval_t _hash,
1817 bitmap_obstack *stack): sem_item(VAR,
1818 node, _hash, stack)
1820 gcc_checking_assert (node);
1821 gcc_checking_assert (get_node ());
1824 /* Fast equality function based on knowledge known in WPA. */
1826 bool
1827 sem_variable::equals_wpa (sem_item *item,
1828 hash_map <symtab_node *, sem_item *> &ignored_nodes)
1830 gcc_assert (item->type == VAR);
1832 if (node->num_references () != item->node->num_references ())
1833 return return_false_with_msg ("different number of references");
1835 if (DECL_TLS_MODEL (decl) || DECL_TLS_MODEL (item->decl))
1836 return return_false_with_msg ("TLS model");
1838 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1839 alignment out of all aliases. */
1841 if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
1842 return return_false_with_msg ("Virtual flag mismatch");
1844 if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
1845 && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
1846 || !operand_equal_p (DECL_SIZE (decl),
1847 DECL_SIZE (item->decl), OEP_ONLY_CONST)))
1848 return return_false_with_msg ("size mismatch");
1850 /* Do not attempt to mix data from different user sections;
1851 we do not know what user intends with those. */
1852 if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
1853 || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
1854 && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
1855 return return_false_with_msg ("user section mismatch");
1857 if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
1858 return return_false_with_msg ("text section");
1860 ipa_ref *ref = NULL, *ref2 = NULL;
1861 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
1863 item->node->iterate_reference (i, ref2);
1865 if (ref->use != ref2->use)
1866 return return_false_with_msg ("reference use mismatch");
1868 if (!compare_symbol_references (ignored_nodes,
1869 ref->referred, ref2->referred,
1870 ref->address_matters_p ()))
1871 return false;
1874 return true;
1877 /* Returns true if the item equals to ITEM given as argument. */
1879 bool
1880 sem_variable::equals (sem_item *item,
1881 hash_map <symtab_node *, sem_item *> &)
1883 gcc_assert (item->type == VAR);
1884 bool ret;
1886 if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
1887 dyn_cast <varpool_node *>(node)->get_constructor ();
1888 if (DECL_INITIAL (item->decl) == error_mark_node && in_lto_p)
1889 dyn_cast <varpool_node *>(item->node)->get_constructor ();
1891 /* As seen in PR ipa/65303 we have to compare variables types. */
1892 if (!func_checker::compatible_types_p (TREE_TYPE (decl),
1893 TREE_TYPE (item->decl)))
1894 return return_false_with_msg ("variables types are different");
1896 ret = sem_variable::equals (DECL_INITIAL (decl),
1897 DECL_INITIAL (item->node->decl));
1898 if (dump_file && (dump_flags & TDF_DETAILS))
1899 fprintf (dump_file,
1900 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1901 xstrdup_for_dump (node->name()),
1902 xstrdup_for_dump (item->node->name ()),
1903 node->order, item->node->order,
1904 xstrdup_for_dump (node->asm_name ()),
1905 xstrdup_for_dump (item->node->asm_name ()), ret ? "true" : "false");
1907 return ret;
1910 /* Compares trees T1 and T2 for semantic equality. */
1912 bool
1913 sem_variable::equals (tree t1, tree t2)
1915 if (!t1 || !t2)
1916 return return_with_debug (t1 == t2);
1917 if (t1 == t2)
1918 return true;
1919 tree_code tc1 = TREE_CODE (t1);
1920 tree_code tc2 = TREE_CODE (t2);
1922 if (tc1 != tc2)
1923 return return_false_with_msg ("TREE_CODE mismatch");
1925 switch (tc1)
1927 case CONSTRUCTOR:
1929 vec<constructor_elt, va_gc> *v1, *v2;
1930 unsigned HOST_WIDE_INT idx;
1932 enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
1933 if (typecode != TREE_CODE (TREE_TYPE (t2)))
1934 return return_false_with_msg ("constructor type mismatch");
1936 if (typecode == ARRAY_TYPE)
1938 HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
1939 /* For arrays, check that the sizes all match. */
1940 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
1941 || size_1 == -1
1942 || size_1 != int_size_in_bytes (TREE_TYPE (t2)))
1943 return return_false_with_msg ("constructor array size mismatch");
1945 else if (!func_checker::compatible_types_p (TREE_TYPE (t1),
1946 TREE_TYPE (t2)))
1947 return return_false_with_msg ("constructor type incompatible");
1949 v1 = CONSTRUCTOR_ELTS (t1);
1950 v2 = CONSTRUCTOR_ELTS (t2);
1951 if (vec_safe_length (v1) != vec_safe_length (v2))
1952 return return_false_with_msg ("constructor number of elts mismatch");
1954 for (idx = 0; idx < vec_safe_length (v1); ++idx)
1956 constructor_elt *c1 = &(*v1)[idx];
1957 constructor_elt *c2 = &(*v2)[idx];
1959 /* Check that each value is the same... */
1960 if (!sem_variable::equals (c1->value, c2->value))
1961 return false;
1962 /* ... and that they apply to the same fields! */
1963 if (!sem_variable::equals (c1->index, c2->index))
1964 return false;
1966 return true;
1968 case MEM_REF:
1970 tree x1 = TREE_OPERAND (t1, 0);
1971 tree x2 = TREE_OPERAND (t2, 0);
1972 tree y1 = TREE_OPERAND (t1, 1);
1973 tree y2 = TREE_OPERAND (t2, 1);
1975 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
1976 return return_false ();
1978 /* Type of the offset on MEM_REF does not matter. */
1979 return return_with_debug (sem_variable::equals (x1, x2)
1980 && wi::to_offset (y1)
1981 == wi::to_offset (y2));
1983 case ADDR_EXPR:
1984 case FDESC_EXPR:
1986 tree op1 = TREE_OPERAND (t1, 0);
1987 tree op2 = TREE_OPERAND (t2, 0);
1988 return sem_variable::equals (op1, op2);
1990 /* References to other vars/decls are compared using ipa-ref. */
1991 case FUNCTION_DECL:
1992 case VAR_DECL:
1993 if (decl_in_symtab_p (t1) && decl_in_symtab_p (t2))
1994 return true;
1995 return return_false_with_msg ("Declaration mismatch");
1996 case CONST_DECL:
1997 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1998 need to process its VAR/FUNCTION references without relying on ipa-ref
1999 compare. */
2000 case FIELD_DECL:
2001 case LABEL_DECL:
2002 return return_false_with_msg ("Declaration mismatch");
2003 case INTEGER_CST:
2004 /* Integer constants are the same only if the same width of type. */
2005 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2006 return return_false_with_msg ("INTEGER_CST precision mismatch");
2007 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
2008 return return_false_with_msg ("INTEGER_CST mode mismatch");
2009 return return_with_debug (tree_int_cst_equal (t1, t2));
2010 case STRING_CST:
2011 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
2012 return return_false_with_msg ("STRING_CST mode mismatch");
2013 if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
2014 return return_false_with_msg ("STRING_CST length mismatch");
2015 if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
2016 TREE_STRING_LENGTH (t1)))
2017 return return_false_with_msg ("STRING_CST mismatch");
2018 return true;
2019 case FIXED_CST:
2020 /* Fixed constants are the same only if the same width of type. */
2021 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2022 return return_false_with_msg ("FIXED_CST precision mismatch");
2024 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
2025 TREE_FIXED_CST (t2)));
2026 case COMPLEX_CST:
2027 return (sem_variable::equals (TREE_REALPART (t1), TREE_REALPART (t2))
2028 && sem_variable::equals (TREE_IMAGPART (t1), TREE_IMAGPART (t2)));
2029 case REAL_CST:
2030 /* Real constants are the same only if the same width of type. */
2031 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2032 return return_false_with_msg ("REAL_CST precision mismatch");
2033 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1),
2034 TREE_REAL_CST (t2)));
2035 case VECTOR_CST:
2037 unsigned i;
2039 if (VECTOR_CST_NELTS (t1) != VECTOR_CST_NELTS (t2))
2040 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2042 for (i = 0; i < VECTOR_CST_NELTS (t1); ++i)
2043 if (!sem_variable::equals (VECTOR_CST_ELT (t1, i),
2044 VECTOR_CST_ELT (t2, i)))
2045 return 0;
2047 return 1;
2049 case ARRAY_REF:
2050 case ARRAY_RANGE_REF:
2052 tree x1 = TREE_OPERAND (t1, 0);
2053 tree x2 = TREE_OPERAND (t2, 0);
2054 tree y1 = TREE_OPERAND (t1, 1);
2055 tree y2 = TREE_OPERAND (t2, 1);
2057 if (!sem_variable::equals (x1, x2) || !sem_variable::equals (y1, y2))
2058 return false;
2059 if (!sem_variable::equals (array_ref_low_bound (t1),
2060 array_ref_low_bound (t2)))
2061 return false;
2062 if (!sem_variable::equals (array_ref_element_size (t1),
2063 array_ref_element_size (t2)))
2064 return false;
2065 return true;
2068 case COMPONENT_REF:
2069 case POINTER_PLUS_EXPR:
2070 case PLUS_EXPR:
2071 case MINUS_EXPR:
2072 case RANGE_EXPR:
2074 tree x1 = TREE_OPERAND (t1, 0);
2075 tree x2 = TREE_OPERAND (t2, 0);
2076 tree y1 = TREE_OPERAND (t1, 1);
2077 tree y2 = TREE_OPERAND (t2, 1);
2079 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
2082 CASE_CONVERT:
2083 case VIEW_CONVERT_EXPR:
2084 if (!func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
2085 return return_false ();
2086 return sem_variable::equals (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
2087 case ERROR_MARK:
2088 return return_false_with_msg ("ERROR_MARK");
2089 default:
2090 return return_false_with_msg ("Unknown TREE code reached");
2094 /* Parser function that visits a varpool NODE. */
2096 sem_variable *
2097 sem_variable::parse (varpool_node *node, bitmap_obstack *stack)
2099 if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl)
2100 || node->alias)
2101 return NULL;
2103 sem_variable *v = new sem_variable (node, 0, stack);
2105 v->init ();
2107 return v;
2110 /* References independent hash function. */
2112 hashval_t
2113 sem_variable::get_hash (void)
2115 if (hash)
2116 return hash;
2118 /* All WPA streamed in symbols should have their hashes computed at compile
2119 time. At this point, the constructor may not be in memory at all.
2120 DECL_INITIAL (decl) would be error_mark_node in that case. */
2121 gcc_assert (!node->lto_file_data);
2122 tree ctor = DECL_INITIAL (decl);
2123 inchash::hash hstate;
2125 hstate.add_int (456346417);
2126 if (DECL_SIZE (decl) && tree_fits_shwi_p (DECL_SIZE (decl)))
2127 hstate.add_wide_int (tree_to_shwi (DECL_SIZE (decl)));
2128 add_expr (ctor, hstate);
2129 hash = hstate.end ();
2131 return hash;
2134 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2135 be applied. */
2137 bool
2138 sem_variable::merge (sem_item *alias_item)
2140 gcc_assert (alias_item->type == VAR);
2142 if (!sem_item::target_supports_symbol_aliases_p ())
2144 if (dump_file)
2145 fprintf (dump_file, "Not unifying; "
2146 "Symbol aliases are not supported by target\n\n");
2147 return false;
2150 if (DECL_EXTERNAL (alias_item->decl))
2152 if (dump_file)
2153 fprintf (dump_file, "Not unifying; alias is external.\n\n");
2154 return false;
2157 sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
2159 varpool_node *original = get_node ();
2160 varpool_node *alias = alias_var->get_node ();
2161 bool original_discardable = false;
2163 bool original_address_matters = original->address_matters_p ();
2164 bool alias_address_matters = alias->address_matters_p ();
2166 /* See if original is in a section that can be discarded if the main
2167 symbol is not used.
2168 Also consider case where we have resolution info and we know that
2169 original's definition is not going to be used. In this case we can not
2170 create alias to original. */
2171 if (original->can_be_discarded_p ()
2172 || (node->resolution != LDPR_UNKNOWN
2173 && !decl_binds_to_current_def_p (node->decl)))
2174 original_discardable = true;
2176 gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
2178 /* Constant pool machinery is not quite ready for aliases.
2179 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2180 For LTO merging does not happen that is an important missing feature.
2181 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2182 flag is dropped and non-local symbol name is assigned. */
2183 if (DECL_IN_CONSTANT_POOL (alias->decl)
2184 || DECL_IN_CONSTANT_POOL (original->decl))
2186 if (dump_file)
2187 fprintf (dump_file,
2188 "Not unifying; constant pool variables.\n\n");
2189 return false;
2192 /* Do not attempt to mix functions from different user sections;
2193 we do not know what user intends with those. */
2194 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
2195 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
2196 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
2198 if (dump_file)
2199 fprintf (dump_file,
2200 "Not unifying; "
2201 "original and alias are in different sections.\n\n");
2202 return false;
2205 /* We can not merge if address comparsion metters. */
2206 if (original_address_matters && alias_address_matters
2207 && flag_merge_constants < 2)
2209 if (dump_file)
2210 fprintf (dump_file,
2211 "Not unifying; "
2212 "adress of original and alias may be compared.\n\n");
2213 return false;
2215 if (DECL_COMDAT_GROUP (original->decl) != DECL_COMDAT_GROUP (alias->decl))
2217 if (dump_file)
2218 fprintf (dump_file, "Not unifying; alias cannot be created; "
2219 "across comdat group boundary\n\n");
2221 return false;
2224 if (original_discardable)
2226 if (dump_file)
2227 fprintf (dump_file, "Not unifying; alias cannot be created; "
2228 "target is discardable\n\n");
2230 return false;
2232 else
2234 gcc_assert (!original->alias);
2235 gcc_assert (!alias->alias);
2237 alias->analyzed = false;
2239 DECL_INITIAL (alias->decl) = NULL;
2240 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
2241 NULL, true);
2242 alias->need_bounds_init = false;
2243 alias->remove_all_references ();
2244 if (TREE_ADDRESSABLE (alias->decl))
2245 original->call_for_symbol_and_aliases (set_addressable, NULL, true);
2247 varpool_node::create_alias (alias_var->decl, decl);
2248 alias->resolve_alias (original);
2250 if (dump_file)
2251 fprintf (dump_file, "Unified; Variable alias has been created.\n\n");
2253 return true;
2257 /* Dump symbol to FILE. */
2259 void
2260 sem_variable::dump_to_file (FILE *file)
2262 gcc_assert (file);
2264 print_node (file, "", decl, 0);
2265 fprintf (file, "\n\n");
2268 unsigned int sem_item_optimizer::class_id = 0;
2270 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2271 m_classes_count (0), m_cgraph_node_hooks (NULL), m_varpool_node_hooks (NULL)
2273 m_items.create (0);
2274 bitmap_obstack_initialize (&m_bmstack);
2277 sem_item_optimizer::~sem_item_optimizer ()
2279 for (unsigned int i = 0; i < m_items.length (); i++)
2280 delete m_items[i];
2282 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2283 it != m_classes.end (); ++it)
2285 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2286 delete (*it)->classes[i];
2288 (*it)->classes.release ();
2289 free (*it);
2292 m_items.release ();
2294 bitmap_obstack_release (&m_bmstack);
2297 /* Write IPA ICF summary for symbols. */
2299 void
2300 sem_item_optimizer::write_summary (void)
2302 unsigned int count = 0;
2304 output_block *ob = create_output_block (LTO_section_ipa_icf);
2305 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
2306 ob->symbol = NULL;
2308 /* Calculate number of symbols to be serialized. */
2309 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2310 !lsei_end_p (lsei);
2311 lsei_next_in_partition (&lsei))
2313 symtab_node *node = lsei_node (lsei);
2315 if (m_symtab_node_map.get (node))
2316 count++;
2319 streamer_write_uhwi (ob, count);
2321 /* Process all of the symbols. */
2322 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2323 !lsei_end_p (lsei);
2324 lsei_next_in_partition (&lsei))
2326 symtab_node *node = lsei_node (lsei);
2328 sem_item **item = m_symtab_node_map.get (node);
2330 if (item && *item)
2332 int node_ref = lto_symtab_encoder_encode (encoder, node);
2333 streamer_write_uhwi_stream (ob->main_stream, node_ref);
2335 streamer_write_uhwi (ob, (*item)->get_hash ());
2339 streamer_write_char_stream (ob->main_stream, 0);
2340 produce_asm (ob, NULL);
2341 destroy_output_block (ob);
2344 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2345 contains LEN bytes. */
2347 void
2348 sem_item_optimizer::read_section (lto_file_decl_data *file_data,
2349 const char *data, size_t len)
2351 const lto_function_header *header =
2352 (const lto_function_header *) data;
2353 const int cfg_offset = sizeof (lto_function_header);
2354 const int main_offset = cfg_offset + header->cfg_size;
2355 const int string_offset = main_offset + header->main_size;
2356 data_in *data_in;
2357 unsigned int i;
2358 unsigned int count;
2360 lto_input_block ib_main ((const char *) data + main_offset, 0,
2361 header->main_size, file_data->mode_table);
2363 data_in =
2364 lto_data_in_create (file_data, (const char *) data + string_offset,
2365 header->string_size, vNULL);
2367 count = streamer_read_uhwi (&ib_main);
2369 for (i = 0; i < count; i++)
2371 unsigned int index;
2372 symtab_node *node;
2373 lto_symtab_encoder_t encoder;
2375 index = streamer_read_uhwi (&ib_main);
2376 encoder = file_data->symtab_node_encoder;
2377 node = lto_symtab_encoder_deref (encoder, index);
2379 hashval_t hash = streamer_read_uhwi (&ib_main);
2381 gcc_assert (node->definition);
2383 if (dump_file)
2384 fprintf (dump_file, "Symbol added:%s (tree: %p, uid:%u)\n",
2385 node->asm_name (), (void *) node->decl, node->order);
2387 if (is_a<cgraph_node *> (node))
2389 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
2391 m_items.safe_push (new sem_function (cnode, hash, &m_bmstack));
2393 else
2395 varpool_node *vnode = dyn_cast <varpool_node *> (node);
2397 m_items.safe_push (new sem_variable (vnode, hash, &m_bmstack));
2401 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
2402 len);
2403 lto_data_in_delete (data_in);
2406 /* Read IPA ICF summary for symbols. */
2408 void
2409 sem_item_optimizer::read_summary (void)
2411 lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2412 lto_file_decl_data *file_data;
2413 unsigned int j = 0;
2415 while ((file_data = file_data_vec[j++]))
2417 size_t len;
2418 const char *data = lto_get_section_data (file_data,
2419 LTO_section_ipa_icf, NULL, &len);
2421 if (data)
2422 read_section (file_data, data, len);
2426 /* Register callgraph and varpool hooks. */
2428 void
2429 sem_item_optimizer::register_hooks (void)
2431 if (!m_cgraph_node_hooks)
2432 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
2433 (&sem_item_optimizer::cgraph_removal_hook, this);
2435 if (!m_varpool_node_hooks)
2436 m_varpool_node_hooks = symtab->add_varpool_removal_hook
2437 (&sem_item_optimizer::varpool_removal_hook, this);
2440 /* Unregister callgraph and varpool hooks. */
2442 void
2443 sem_item_optimizer::unregister_hooks (void)
2445 if (m_cgraph_node_hooks)
2446 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
2448 if (m_varpool_node_hooks)
2449 symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
2452 /* Adds a CLS to hashtable associated by hash value. */
2454 void
2455 sem_item_optimizer::add_class (congruence_class *cls)
2457 gcc_assert (cls->members.length ());
2459 congruence_class_group *group = get_group_by_hash (
2460 cls->members[0]->get_hash (),
2461 cls->members[0]->type);
2462 group->classes.safe_push (cls);
2465 /* Gets a congruence class group based on given HASH value and TYPE. */
2467 congruence_class_group *
2468 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
2470 congruence_class_group *item = XNEW (congruence_class_group);
2471 item->hash = hash;
2472 item->type = type;
2474 congruence_class_group **slot = m_classes.find_slot (item, INSERT);
2476 if (*slot)
2477 free (item);
2478 else
2480 item->classes.create (1);
2481 *slot = item;
2484 return *slot;
2487 /* Callgraph removal hook called for a NODE with a custom DATA. */
2489 void
2490 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
2492 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2493 optimizer->remove_symtab_node (node);
2496 /* Varpool removal hook called for a NODE with a custom DATA. */
2498 void
2499 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
2501 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2502 optimizer->remove_symtab_node (node);
2505 /* Remove symtab NODE triggered by symtab removal hooks. */
2507 void
2508 sem_item_optimizer::remove_symtab_node (symtab_node *node)
2510 gcc_assert (!m_classes.elements());
2512 m_removed_items_set.add (node);
2515 void
2516 sem_item_optimizer::remove_item (sem_item *item)
2518 if (m_symtab_node_map.get (item->node))
2519 m_symtab_node_map.remove (item->node);
2520 delete item;
2523 /* Removes all callgraph and varpool nodes that are marked by symtab
2524 as deleted. */
2526 void
2527 sem_item_optimizer::filter_removed_items (void)
2529 auto_vec <sem_item *> filtered;
2531 for (unsigned int i = 0; i < m_items.length(); i++)
2533 sem_item *item = m_items[i];
2535 if (m_removed_items_set.contains (item->node))
2537 remove_item (item);
2538 continue;
2541 if (item->type == FUNC)
2543 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
2545 if (in_lto_p && (cnode->alias || cnode->body_removed))
2546 remove_item (item);
2547 else
2548 filtered.safe_push (item);
2550 else /* VAR. */
2552 if (!flag_ipa_icf_variables)
2553 remove_item (item);
2554 else
2556 /* Filter out non-readonly variables. */
2557 tree decl = item->decl;
2558 if (TREE_READONLY (decl))
2559 filtered.safe_push (item);
2560 else
2561 remove_item (item);
2566 /* Clean-up of released semantic items. */
2568 m_items.release ();
2569 for (unsigned int i = 0; i < filtered.length(); i++)
2570 m_items.safe_push (filtered[i]);
2573 /* Optimizer entry point which returns true in case it processes
2574 a merge operation. True is returned if there's a merge operation
2575 processed. */
2577 bool
2578 sem_item_optimizer::execute (void)
2580 filter_removed_items ();
2581 unregister_hooks ();
2583 build_graph ();
2584 update_hash_by_addr_refs ();
2585 build_hash_based_classes ();
2587 if (dump_file)
2588 fprintf (dump_file, "Dump after hash based groups\n");
2589 dump_cong_classes ();
2591 for (unsigned int i = 0; i < m_items.length(); i++)
2592 m_items[i]->init_wpa ();
2594 subdivide_classes_by_equality (true);
2596 if (dump_file)
2597 fprintf (dump_file, "Dump after WPA based types groups\n");
2599 dump_cong_classes ();
2601 process_cong_reduction ();
2602 verify_classes ();
2604 if (dump_file)
2605 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
2607 dump_cong_classes ();
2609 parse_nonsingleton_classes ();
2610 subdivide_classes_by_equality ();
2612 if (dump_file)
2613 fprintf (dump_file, "Dump after full equality comparison of groups\n");
2615 dump_cong_classes ();
2617 unsigned int prev_class_count = m_classes_count;
2619 process_cong_reduction ();
2620 dump_cong_classes ();
2621 verify_classes ();
2622 bool merged_p = merge_classes (prev_class_count);
2624 if (dump_file && (dump_flags & TDF_DETAILS))
2625 symtab_node::dump_table (dump_file);
2627 return merged_p;
2630 /* Function responsible for visiting all potential functions and
2631 read-only variables that can be merged. */
2633 void
2634 sem_item_optimizer::parse_funcs_and_vars (void)
2636 cgraph_node *cnode;
2638 if (flag_ipa_icf_functions)
2639 FOR_EACH_DEFINED_FUNCTION (cnode)
2641 sem_function *f = sem_function::parse (cnode, &m_bmstack);
2642 if (f)
2644 m_items.safe_push (f);
2645 m_symtab_node_map.put (cnode, f);
2647 if (dump_file)
2648 fprintf (dump_file, "Parsed function:%s\n", f->node->asm_name ());
2650 if (dump_file && (dump_flags & TDF_DETAILS))
2651 f->dump_to_file (dump_file);
2653 else if (dump_file)
2654 fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
2657 varpool_node *vnode;
2659 if (flag_ipa_icf_variables)
2660 FOR_EACH_DEFINED_VARIABLE (vnode)
2662 sem_variable *v = sem_variable::parse (vnode, &m_bmstack);
2664 if (v)
2666 m_items.safe_push (v);
2667 m_symtab_node_map.put (vnode, v);
2672 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2674 void
2675 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
2677 item->index_in_class = cls->members.length ();
2678 cls->members.safe_push (item);
2679 item->cls = cls;
2682 /* For each semantic item, append hash values of references. */
2684 void
2685 sem_item_optimizer::update_hash_by_addr_refs ()
2687 /* First, append to hash sensitive references and class type if it need to
2688 be matched for ODR. */
2689 for (unsigned i = 0; i < m_items.length (); i++)
2691 m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
2692 if (m_items[i]->type == FUNC)
2694 if (TREE_CODE (TREE_TYPE (m_items[i]->decl)) == METHOD_TYPE
2695 && contains_polymorphic_type_p
2696 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl)))
2697 && (DECL_CXX_CONSTRUCTOR_P (m_items[i]->decl)
2698 || (static_cast<sem_function *> (m_items[i])->param_used_p (0)
2699 && static_cast<sem_function *> (m_items[i])
2700 ->compare_polymorphic_p ())))
2702 tree class_type
2703 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl));
2704 inchash::hash hstate (m_items[i]->hash);
2706 if (TYPE_NAME (class_type)
2707 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type)))
2708 hstate.add_wide_int
2709 (IDENTIFIER_HASH_VALUE
2710 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type))));
2712 m_items[i]->hash = hstate.end ();
2717 /* Once all symbols have enhanced hash value, we can append
2718 hash values of symbols that are seen by IPA ICF and are
2719 references by a semantic item. Newly computed values
2720 are saved to global_hash member variable. */
2721 for (unsigned i = 0; i < m_items.length (); i++)
2722 m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
2724 /* Global hash value replace current hash values. */
2725 for (unsigned i = 0; i < m_items.length (); i++)
2726 m_items[i]->hash = m_items[i]->global_hash;
2729 /* Congruence classes are built by hash value. */
2731 void
2732 sem_item_optimizer::build_hash_based_classes (void)
2734 for (unsigned i = 0; i < m_items.length (); i++)
2736 sem_item *item = m_items[i];
2738 congruence_class_group *group = get_group_by_hash (item->hash,
2739 item->type);
2741 if (!group->classes.length ())
2743 m_classes_count++;
2744 group->classes.safe_push (new congruence_class (class_id++));
2747 add_item_to_class (group->classes[0], item);
2751 /* Build references according to call graph. */
2753 void
2754 sem_item_optimizer::build_graph (void)
2756 for (unsigned i = 0; i < m_items.length (); i++)
2758 sem_item *item = m_items[i];
2759 m_symtab_node_map.put (item->node, item);
2762 for (unsigned i = 0; i < m_items.length (); i++)
2764 sem_item *item = m_items[i];
2766 if (item->type == FUNC)
2768 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
2770 cgraph_edge *e = cnode->callees;
2771 while (e)
2773 sem_item **slot = m_symtab_node_map.get
2774 (e->callee->ultimate_alias_target ());
2775 if (slot)
2776 item->add_reference (*slot);
2778 e = e->next_callee;
2782 ipa_ref *ref = NULL;
2783 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
2785 sem_item **slot = m_symtab_node_map.get
2786 (ref->referred->ultimate_alias_target ());
2787 if (slot)
2788 item->add_reference (*slot);
2793 /* Semantic items in classes having more than one element and initialized.
2794 In case of WPA, we load function body. */
2796 void
2797 sem_item_optimizer::parse_nonsingleton_classes (void)
2799 unsigned int init_called_count = 0;
2801 for (unsigned i = 0; i < m_items.length (); i++)
2802 if (m_items[i]->cls->members.length () > 1)
2804 m_items[i]->init ();
2805 init_called_count++;
2808 if (dump_file)
2809 fprintf (dump_file, "Init called for %u items (%.2f%%).\n", init_called_count,
2810 m_items.length () ? 100.0f * init_called_count / m_items.length (): 0.0f);
2813 /* Equality function for semantic items is used to subdivide existing
2814 classes. If IN_WPA, fast equality function is invoked. */
2816 void
2817 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
2819 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2820 it != m_classes.end (); ++it)
2822 unsigned int class_count = (*it)->classes.length ();
2824 for (unsigned i = 0; i < class_count; i++)
2826 congruence_class *c = (*it)->classes [i];
2828 if (c->members.length() > 1)
2830 auto_vec <sem_item *> new_vector;
2832 sem_item *first = c->members[0];
2833 new_vector.safe_push (first);
2835 unsigned class_split_first = (*it)->classes.length ();
2837 for (unsigned j = 1; j < c->members.length (); j++)
2839 sem_item *item = c->members[j];
2841 bool equals = in_wpa ? first->equals_wpa (item,
2842 m_symtab_node_map) : first->equals (item, m_symtab_node_map);
2844 if (equals)
2845 new_vector.safe_push (item);
2846 else
2848 bool integrated = false;
2850 for (unsigned k = class_split_first; k < (*it)->classes.length (); k++)
2852 sem_item *x = (*it)->classes[k]->members[0];
2853 bool equals = in_wpa ? x->equals_wpa (item,
2854 m_symtab_node_map) : x->equals (item, m_symtab_node_map);
2856 if (equals)
2858 integrated = true;
2859 add_item_to_class ((*it)->classes[k], item);
2861 break;
2865 if (!integrated)
2867 congruence_class *c = new congruence_class (class_id++);
2868 m_classes_count++;
2869 add_item_to_class (c, item);
2871 (*it)->classes.safe_push (c);
2876 // we replace newly created new_vector for the class we've just splitted
2877 c->members.release ();
2878 c->members.create (new_vector.length ());
2880 for (unsigned int j = 0; j < new_vector.length (); j++)
2881 add_item_to_class (c, new_vector[j]);
2886 verify_classes ();
2889 /* Subdivide classes by address references that members of the class
2890 reference. Example can be a pair of functions that have an address
2891 taken from a function. If these addresses are different the class
2892 is split. */
2894 unsigned
2895 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2897 typedef hash_map <symbol_compare_hash, vec <sem_item *> > subdivide_hash_map;
2899 unsigned newly_created_classes = 0;
2901 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2902 it != m_classes.end (); ++it)
2904 unsigned int class_count = (*it)->classes.length ();
2905 auto_vec<congruence_class *> new_classes;
2907 for (unsigned i = 0; i < class_count; i++)
2909 congruence_class *c = (*it)->classes [i];
2911 if (c->members.length() > 1)
2913 subdivide_hash_map split_map;
2915 for (unsigned j = 0; j < c->members.length (); j++)
2917 sem_item *source_node = c->members[j];
2919 symbol_compare_collection *collection = new symbol_compare_collection (source_node->node);
2921 bool existed;
2922 vec <sem_item *> *slot = &split_map.get_or_insert (collection,
2923 &existed);
2924 gcc_checking_assert (slot);
2926 slot->safe_push (source_node);
2928 if (existed)
2929 delete collection;
2932 /* If the map contains more than one key, we have to split the map
2933 appropriately. */
2934 if (split_map.elements () != 1)
2936 bool first_class = true;
2938 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2939 it2 != split_map.end (); ++it2)
2941 congruence_class *new_cls;
2942 new_cls = new congruence_class (class_id++);
2944 for (unsigned k = 0; k < (*it2).second.length (); k++)
2945 add_item_to_class (new_cls, (*it2).second[k]);
2947 worklist_push (new_cls);
2948 newly_created_classes++;
2950 if (first_class)
2952 (*it)->classes[i] = new_cls;
2953 first_class = false;
2955 else
2957 new_classes.safe_push (new_cls);
2958 m_classes_count++;
2963 /* Release memory. */
2964 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2965 it2 != split_map.end (); ++it2)
2967 delete (*it2).first;
2968 (*it2).second.release ();
2973 for (unsigned i = 0; i < new_classes.length (); i++)
2974 (*it)->classes.safe_push (new_classes[i]);
2977 return newly_created_classes;
2980 /* Verify congruence classes if checking is enabled. */
2982 void
2983 sem_item_optimizer::verify_classes (void)
2985 #if ENABLE_CHECKING
2986 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2987 it != m_classes.end (); ++it)
2989 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2991 congruence_class *cls = (*it)->classes[i];
2993 gcc_checking_assert (cls);
2994 gcc_checking_assert (cls->members.length () > 0);
2996 for (unsigned int j = 0; j < cls->members.length (); j++)
2998 sem_item *item = cls->members[j];
3000 gcc_checking_assert (item);
3001 gcc_checking_assert (item->cls == cls);
3003 for (unsigned k = 0; k < item->usages.length (); k++)
3005 sem_usage_pair *usage = item->usages[k];
3006 gcc_checking_assert (usage->item->index_in_class <
3007 usage->item->cls->members.length ());
3012 #endif
3015 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3016 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3017 but unused argument. */
3019 bool
3020 sem_item_optimizer::release_split_map (congruence_class * const &,
3021 bitmap const &b, traverse_split_pair *)
3023 bitmap bmp = b;
3025 BITMAP_FREE (bmp);
3027 return true;
3030 /* Process split operation for a class given as pointer CLS_PTR,
3031 where bitmap B splits congruence class members. DATA is used
3032 as argument of split pair. */
3034 bool
3035 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
3036 bitmap const &b, traverse_split_pair *pair)
3038 sem_item_optimizer *optimizer = pair->optimizer;
3039 const congruence_class *splitter_cls = pair->cls;
3041 /* If counted bits are greater than zero and less than the number of members
3042 a group will be splitted. */
3043 unsigned popcount = bitmap_count_bits (b);
3045 if (popcount > 0 && popcount < cls->members.length ())
3047 congruence_class* newclasses[2] = { new congruence_class (class_id++), new congruence_class (class_id++) };
3049 for (unsigned int i = 0; i < cls->members.length (); i++)
3051 int target = bitmap_bit_p (b, i);
3052 congruence_class *tc = newclasses[target];
3054 add_item_to_class (tc, cls->members[i]);
3057 #ifdef ENABLE_CHECKING
3058 for (unsigned int i = 0; i < 2; i++)
3059 gcc_checking_assert (newclasses[i]->members.length ());
3060 #endif
3062 if (splitter_cls == cls)
3063 optimizer->splitter_class_removed = true;
3065 /* Remove old class from worklist if presented. */
3066 bool in_worklist = cls->in_worklist;
3068 if (in_worklist)
3069 cls->in_worklist = false;
3071 congruence_class_group g;
3072 g.hash = cls->members[0]->get_hash ();
3073 g.type = cls->members[0]->type;
3075 congruence_class_group *slot = optimizer->m_classes.find(&g);
3077 for (unsigned int i = 0; i < slot->classes.length (); i++)
3078 if (slot->classes[i] == cls)
3080 slot->classes.ordered_remove (i);
3081 break;
3084 /* New class will be inserted and integrated to work list. */
3085 for (unsigned int i = 0; i < 2; i++)
3086 optimizer->add_class (newclasses[i]);
3088 /* Two classes replace one, so that increment just by one. */
3089 optimizer->m_classes_count++;
3091 /* If OLD class was presented in the worklist, we remove the class
3092 and replace it will both newly created classes. */
3093 if (in_worklist)
3094 for (unsigned int i = 0; i < 2; i++)
3095 optimizer->worklist_push (newclasses[i]);
3096 else /* Just smaller class is inserted. */
3098 unsigned int smaller_index = newclasses[0]->members.length () <
3099 newclasses[1]->members.length () ?
3100 0 : 1;
3101 optimizer->worklist_push (newclasses[smaller_index]);
3104 if (dump_file && (dump_flags & TDF_DETAILS))
3106 fprintf (dump_file, " congruence class splitted:\n");
3107 cls->dump (dump_file, 4);
3109 fprintf (dump_file, " newly created groups:\n");
3110 for (unsigned int i = 0; i < 2; i++)
3111 newclasses[i]->dump (dump_file, 4);
3114 /* Release class if not presented in work list. */
3115 if (!in_worklist)
3116 delete cls;
3120 return true;
3123 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3124 Bitmap stack BMSTACK is used for bitmap allocation. */
3126 void
3127 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
3128 unsigned int index)
3130 hash_map <congruence_class *, bitmap> split_map;
3132 for (unsigned int i = 0; i < cls->members.length (); i++)
3134 sem_item *item = cls->members[i];
3136 /* Iterate all usages that have INDEX as usage of the item. */
3137 for (unsigned int j = 0; j < item->usages.length (); j++)
3139 sem_usage_pair *usage = item->usages[j];
3141 if (usage->index != index)
3142 continue;
3144 bitmap *slot = split_map.get (usage->item->cls);
3145 bitmap b;
3147 if(!slot)
3149 b = BITMAP_ALLOC (&m_bmstack);
3150 split_map.put (usage->item->cls, b);
3152 else
3153 b = *slot;
3155 #if ENABLE_CHECKING
3156 gcc_checking_assert (usage->item->cls);
3157 gcc_checking_assert (usage->item->index_in_class <
3158 usage->item->cls->members.length ());
3159 #endif
3161 bitmap_set_bit (b, usage->item->index_in_class);
3165 traverse_split_pair pair;
3166 pair.optimizer = this;
3167 pair.cls = cls;
3169 splitter_class_removed = false;
3170 split_map.traverse
3171 <traverse_split_pair *, sem_item_optimizer::traverse_congruence_split> (&pair);
3173 /* Bitmap clean-up. */
3174 split_map.traverse
3175 <traverse_split_pair *, sem_item_optimizer::release_split_map> (NULL);
3178 /* Every usage of a congruence class CLS is a candidate that can split the
3179 collection of classes. Bitmap stack BMSTACK is used for bitmap
3180 allocation. */
3182 void
3183 sem_item_optimizer::do_congruence_step (congruence_class *cls)
3185 bitmap_iterator bi;
3186 unsigned int i;
3188 bitmap usage = BITMAP_ALLOC (&m_bmstack);
3190 for (unsigned int i = 0; i < cls->members.length (); i++)
3191 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
3193 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
3195 if (dump_file && (dump_flags & TDF_DETAILS))
3196 fprintf (dump_file, " processing congruence step for class: %u, index: %u\n",
3197 cls->id, i);
3199 do_congruence_step_for_index (cls, i);
3201 if (splitter_class_removed)
3202 break;
3205 BITMAP_FREE (usage);
3208 /* Adds a newly created congruence class CLS to worklist. */
3210 void
3211 sem_item_optimizer::worklist_push (congruence_class *cls)
3213 /* Return if the class CLS is already presented in work list. */
3214 if (cls->in_worklist)
3215 return;
3217 cls->in_worklist = true;
3218 worklist.push_back (cls);
3221 /* Pops a class from worklist. */
3223 congruence_class *
3224 sem_item_optimizer::worklist_pop (void)
3226 congruence_class *cls;
3228 while (!worklist.empty ())
3230 cls = worklist.front ();
3231 worklist.pop_front ();
3232 if (cls->in_worklist)
3234 cls->in_worklist = false;
3236 return cls;
3238 else
3240 /* Work list item was already intended to be removed.
3241 The only reason for doing it is to split a class.
3242 Thus, the class CLS is deleted. */
3243 delete cls;
3247 return NULL;
3250 /* Iterative congruence reduction function. */
3252 void
3253 sem_item_optimizer::process_cong_reduction (void)
3255 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3256 it != m_classes.end (); ++it)
3257 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3258 if ((*it)->classes[i]->is_class_used ())
3259 worklist_push ((*it)->classes[i]);
3261 if (dump_file)
3262 fprintf (dump_file, "Worklist has been filled with: %lu\n",
3263 (unsigned long) worklist.size ());
3265 if (dump_file && (dump_flags & TDF_DETAILS))
3266 fprintf (dump_file, "Congruence class reduction\n");
3268 congruence_class *cls;
3270 /* Process complete congruence reduction. */
3271 while ((cls = worklist_pop ()) != NULL)
3272 do_congruence_step (cls);
3274 /* Subdivide newly created classes according to references. */
3275 unsigned new_classes = subdivide_classes_by_sensitive_refs ();
3277 if (dump_file)
3278 fprintf (dump_file, "Address reference subdivision created: %u "
3279 "new classes.\n", new_classes);
3282 /* Debug function prints all informations about congruence classes. */
3284 void
3285 sem_item_optimizer::dump_cong_classes (void)
3287 if (!dump_file)
3288 return;
3290 fprintf (dump_file,
3291 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3292 m_classes_count, (unsigned long) m_classes.elements(), m_items.length ());
3294 /* Histogram calculation. */
3295 unsigned int max_index = 0;
3296 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
3298 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3299 it != m_classes.end (); ++it)
3301 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3303 unsigned int c = (*it)->classes[i]->members.length ();
3304 histogram[c]++;
3306 if (c > max_index)
3307 max_index = c;
3310 fprintf (dump_file,
3311 "Class size histogram [num of members]: number of classe number of classess\n");
3313 for (unsigned int i = 0; i <= max_index; i++)
3314 if (histogram[i])
3315 fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
3317 fprintf (dump_file, "\n\n");
3320 if (dump_flags & TDF_DETAILS)
3321 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3322 it != m_classes.end (); ++it)
3324 fprintf (dump_file, " group: with %u classes:\n", (*it)->classes.length ());
3326 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3328 (*it)->classes[i]->dump (dump_file, 4);
3330 if(i < (*it)->classes.length () - 1)
3331 fprintf (dump_file, " ");
3335 free (histogram);
3338 /* After reduction is done, we can declare all items in a group
3339 to be equal. PREV_CLASS_COUNT is start number of classes
3340 before reduction. True is returned if there's a merge operation
3341 processed. */
3343 bool
3344 sem_item_optimizer::merge_classes (unsigned int prev_class_count)
3346 unsigned int item_count = m_items.length ();
3347 unsigned int class_count = m_classes_count;
3348 unsigned int equal_items = item_count - class_count;
3350 unsigned int non_singular_classes_count = 0;
3351 unsigned int non_singular_classes_sum = 0;
3353 bool merged_p = false;
3355 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3356 it != m_classes.end (); ++it)
3357 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3359 congruence_class *c = (*it)->classes[i];
3360 if (c->members.length () > 1)
3362 non_singular_classes_count++;
3363 non_singular_classes_sum += c->members.length ();
3367 if (dump_file)
3369 fprintf (dump_file, "\nItem count: %u\n", item_count);
3370 fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
3371 prev_class_count, class_count);
3372 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
3373 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
3374 class_count ? 1.0f * item_count / class_count : 0.0f);
3375 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
3376 non_singular_classes_count ? 1.0f * non_singular_classes_sum /
3377 non_singular_classes_count : 0.0f,
3378 non_singular_classes_count);
3379 fprintf (dump_file, "Equal symbols: %u\n", equal_items);
3380 fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
3381 item_count ? 100.0f * equal_items / item_count : 0.0f);
3384 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3385 it != m_classes.end (); ++it)
3386 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3388 congruence_class *c = (*it)->classes[i];
3390 if (c->members.length () == 1)
3391 continue;
3393 gcc_assert (c->members.length ());
3395 sem_item *source = c->members[0];
3397 for (unsigned int j = 1; j < c->members.length (); j++)
3399 sem_item *alias = c->members[j];
3401 if (dump_file)
3403 fprintf (dump_file, "Semantic equality hit:%s->%s\n",
3404 xstrdup_for_dump (source->node->name ()),
3405 xstrdup_for_dump (alias->node->name ()));
3406 fprintf (dump_file, "Assembler symbol names:%s->%s\n",
3407 xstrdup_for_dump (source->node->asm_name ()),
3408 xstrdup_for_dump (alias->node->asm_name ()));
3411 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl)))
3413 if (dump_file)
3414 fprintf (dump_file,
3415 "Merge operation is skipped due to no_icf "
3416 "attribute.\n\n");
3418 continue;
3421 if (dump_file && (dump_flags & TDF_DETAILS))
3423 source->dump_to_file (dump_file);
3424 alias->dump_to_file (dump_file);
3427 if (dbg_cnt (merged_ipa_icf))
3428 merged_p |= source->merge (alias);
3432 return merged_p;
3435 /* Dump function prints all class members to a FILE with an INDENT. */
3437 void
3438 congruence_class::dump (FILE *file, unsigned int indent) const
3440 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
3441 id, members[0]->get_hash (), members.length ());
3443 FPUTS_SPACES (file, indent + 2, "");
3444 for (unsigned i = 0; i < members.length (); i++)
3445 fprintf (file, "%s(%p/%u) ", members[i]->node->asm_name (),
3446 (void *) members[i]->decl,
3447 members[i]->node->order);
3449 fprintf (file, "\n");
3452 /* Returns true if there's a member that is used from another group. */
3454 bool
3455 congruence_class::is_class_used (void)
3457 for (unsigned int i = 0; i < members.length (); i++)
3458 if (members[i]->usages.length ())
3459 return true;
3461 return false;
3464 /* Generate pass summary for IPA ICF pass. */
3466 static void
3467 ipa_icf_generate_summary (void)
3469 if (!optimizer)
3470 optimizer = new sem_item_optimizer ();
3472 optimizer->register_hooks ();
3473 optimizer->parse_funcs_and_vars ();
3476 /* Write pass summary for IPA ICF pass. */
3478 static void
3479 ipa_icf_write_summary (void)
3481 gcc_assert (optimizer);
3483 optimizer->write_summary ();
3486 /* Read pass summary for IPA ICF pass. */
3488 static void
3489 ipa_icf_read_summary (void)
3491 if (!optimizer)
3492 optimizer = new sem_item_optimizer ();
3494 optimizer->read_summary ();
3495 optimizer->register_hooks ();
3498 /* Semantic equality exection function. */
3500 static unsigned int
3501 ipa_icf_driver (void)
3503 gcc_assert (optimizer);
3505 bool merged_p = optimizer->execute ();
3507 delete optimizer;
3508 optimizer = NULL;
3510 return merged_p ? TODO_remove_functions : 0;
3513 const pass_data pass_data_ipa_icf =
3515 IPA_PASS, /* type */
3516 "icf", /* name */
3517 OPTGROUP_IPA, /* optinfo_flags */
3518 TV_IPA_ICF, /* tv_id */
3519 0, /* properties_required */
3520 0, /* properties_provided */
3521 0, /* properties_destroyed */
3522 0, /* todo_flags_start */
3523 0, /* todo_flags_finish */
3526 class pass_ipa_icf : public ipa_opt_pass_d
3528 public:
3529 pass_ipa_icf (gcc::context *ctxt)
3530 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
3531 ipa_icf_generate_summary, /* generate_summary */
3532 ipa_icf_write_summary, /* write_summary */
3533 ipa_icf_read_summary, /* read_summary */
3534 NULL, /*
3535 write_optimization_summary */
3536 NULL, /*
3537 read_optimization_summary */
3538 NULL, /* stmt_fixup */
3539 0, /* function_transform_todo_flags_start */
3540 NULL, /* function_transform */
3541 NULL) /* variable_transform */
3544 /* opt_pass methods: */
3545 virtual bool gate (function *)
3547 return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
3550 virtual unsigned int execute (function *)
3552 return ipa_icf_driver();
3554 }; // class pass_ipa_icf
3556 } // ipa_icf namespace
3558 ipa_opt_pass_d *
3559 make_pass_ipa_icf (gcc::context *ctxt)
3561 return new ipa_icf::pass_ipa_icf (ctxt);