Daily bump.
[official-gcc.git] / gcc / ipa-icf.c
blob4d152ceab1e03241526b6068bec78d9e85b9e186
1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2017 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 #define INCLUDE_LIST
56 #include "system.h"
57 #include "coretypes.h"
58 #include "backend.h"
59 #include "target.h"
60 #include "rtl.h"
61 #include "tree.h"
62 #include "gimple.h"
63 #include "alloc-pool.h"
64 #include "tree-pass.h"
65 #include "ssa.h"
66 #include "cgraph.h"
67 #include "coverage.h"
68 #include "gimple-pretty-print.h"
69 #include "data-streamer.h"
70 #include "fold-const.h"
71 #include "calls.h"
72 #include "varasm.h"
73 #include "gimple-iterator.h"
74 #include "tree-cfg.h"
75 #include "symbol-summary.h"
76 #include "ipa-prop.h"
77 #include "ipa-fnsummary.h"
78 #include "except.h"
79 #include "attribs.h"
80 #include "print-tree.h"
81 #include "ipa-utils.h"
82 #include "ipa-icf-gimple.h"
83 #include "ipa-icf.h"
84 #include "stor-layout.h"
85 #include "dbgcnt.h"
87 using namespace ipa_icf_gimple;
89 namespace ipa_icf {
91 /* Initialization and computation of symtab node hash, there data
92 are propagated later on. */
94 static sem_item_optimizer *optimizer = NULL;
96 /* Constructor. */
98 symbol_compare_collection::symbol_compare_collection (symtab_node *node)
100 m_references.create (0);
101 m_interposables.create (0);
103 ipa_ref *ref;
105 if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
106 return;
108 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
110 if (ref->address_matters_p ())
111 m_references.safe_push (ref->referred);
113 if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE)
115 if (ref->address_matters_p ())
116 m_references.safe_push (ref->referred);
117 else
118 m_interposables.safe_push (ref->referred);
122 if (is_a <cgraph_node *> (node))
124 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
126 for (cgraph_edge *e = cnode->callees; e; e = e->next_callee)
127 if (e->callee->get_availability () <= AVAIL_INTERPOSABLE)
128 m_interposables.safe_push (e->callee);
132 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
134 sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index)
135 : item (_item), index (_index)
139 sem_item::sem_item (sem_item_type _type, bitmap_obstack *stack)
140 : type (_type), m_hash (-1), m_hash_set (false)
142 setup (stack);
145 sem_item::sem_item (sem_item_type _type, symtab_node *_node,
146 bitmap_obstack *stack)
147 : type (_type), node (_node), m_hash (-1), m_hash_set (false)
149 decl = node->decl;
150 setup (stack);
153 /* Add reference to a semantic TARGET. */
155 void
156 sem_item::add_reference (sem_item *target)
158 refs.safe_push (target);
159 unsigned index = refs.length ();
160 target->usages.safe_push (new sem_usage_pair(this, index));
161 bitmap_set_bit (target->usage_index_bitmap, index);
162 refs_set.add (target->node);
165 /* Initialize internal data structures. Bitmap STACK is used for
166 bitmap memory allocation process. */
168 void
169 sem_item::setup (bitmap_obstack *stack)
171 gcc_checking_assert (node);
173 refs.create (0);
174 tree_refs.create (0);
175 usages.create (0);
176 usage_index_bitmap = BITMAP_ALLOC (stack);
179 sem_item::~sem_item ()
181 for (unsigned i = 0; i < usages.length (); i++)
182 delete usages[i];
184 refs.release ();
185 tree_refs.release ();
186 usages.release ();
188 BITMAP_FREE (usage_index_bitmap);
191 /* Dump function for debugging purpose. */
193 DEBUG_FUNCTION void
194 sem_item::dump (void)
196 if (dump_file)
198 fprintf (dump_file, "[%s] %s (tree:%p)\n", type == FUNC ? "func" : "var",
199 node->dump_name (), (void *) node->decl);
200 fprintf (dump_file, " hash: %u\n", get_hash ());
201 fprintf (dump_file, " references: ");
203 for (unsigned i = 0; i < refs.length (); i++)
204 fprintf (dump_file, "%s%s ", refs[i]->node->name (),
205 i < refs.length() - 1 ? "," : "");
207 fprintf (dump_file, "\n");
211 /* Return true if target supports alias symbols. */
213 bool
214 sem_item::target_supports_symbol_aliases_p (void)
216 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
217 return false;
218 #else
219 return true;
220 #endif
223 void sem_item::set_hash (hashval_t hash)
225 m_hash = hash;
226 m_hash_set = true;
229 /* Semantic function constructor that uses STACK as bitmap memory stack. */
231 sem_function::sem_function (bitmap_obstack *stack)
232 : sem_item (FUNC, stack), m_checker (NULL), m_compared_func (NULL)
234 bb_sizes.create (0);
235 bb_sorted.create (0);
238 sem_function::sem_function (cgraph_node *node, bitmap_obstack *stack)
239 : sem_item (FUNC, node, stack), m_checker (NULL), m_compared_func (NULL)
241 bb_sizes.create (0);
242 bb_sorted.create (0);
245 sem_function::~sem_function ()
247 for (unsigned i = 0; i < bb_sorted.length (); i++)
248 delete (bb_sorted[i]);
250 bb_sizes.release ();
251 bb_sorted.release ();
254 /* Calculates hash value based on a BASIC_BLOCK. */
256 hashval_t
257 sem_function::get_bb_hash (const sem_bb *basic_block)
259 inchash::hash hstate;
261 hstate.add_int (basic_block->nondbg_stmt_count);
262 hstate.add_int (basic_block->edge_count);
264 return hstate.end ();
267 /* References independent hash function. */
269 hashval_t
270 sem_function::get_hash (void)
272 if (!m_hash_set)
274 inchash::hash hstate;
275 hstate.add_int (177454); /* Random number for function type. */
277 hstate.add_int (arg_count);
278 hstate.add_int (cfg_checksum);
279 hstate.add_int (gcode_hash);
281 for (unsigned i = 0; i < bb_sorted.length (); i++)
282 hstate.merge_hash (get_bb_hash (bb_sorted[i]));
284 for (unsigned i = 0; i < bb_sizes.length (); i++)
285 hstate.add_int (bb_sizes[i]);
287 /* Add common features of declaration itself. */
288 if (DECL_FUNCTION_SPECIFIC_TARGET (decl))
289 hstate.add_wide_int
290 (cl_target_option_hash
291 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl))));
292 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))
293 hstate.add_wide_int
294 (cl_optimization_hash
295 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))));
296 hstate.add_flag (DECL_CXX_CONSTRUCTOR_P (decl));
297 hstate.add_flag (DECL_CXX_DESTRUCTOR_P (decl));
299 set_hash (hstate.end ());
302 return m_hash;
305 /* Return ture if A1 and A2 represent equivalent function attribute lists.
306 Based on comp_type_attributes. */
308 bool
309 sem_item::compare_attributes (const_tree a1, const_tree a2)
311 const_tree a;
312 if (a1 == a2)
313 return true;
314 for (a = a1; a != NULL_TREE; a = TREE_CHAIN (a))
316 const struct attribute_spec *as;
317 const_tree attr;
319 as = lookup_attribute_spec (get_attribute_name (a));
320 /* TODO: We can introduce as->affects_decl_identity
321 and as->affects_decl_reference_identity if attribute mismatch
322 gets a common reason to give up on merging. It may not be worth
323 the effort.
324 For example returns_nonnull affects only references, while
325 optimize attribute can be ignored because it is already lowered
326 into flags representation and compared separately. */
327 if (!as)
328 continue;
330 attr = lookup_attribute (as->name, CONST_CAST_TREE (a2));
331 if (!attr || !attribute_value_equal (a, attr))
332 break;
334 if (!a)
336 for (a = a2; a != NULL_TREE; a = TREE_CHAIN (a))
338 const struct attribute_spec *as;
340 as = lookup_attribute_spec (get_attribute_name (a));
341 if (!as)
342 continue;
344 if (!lookup_attribute (as->name, CONST_CAST_TREE (a1)))
345 break;
346 /* We don't need to compare trees again, as we did this
347 already in first loop. */
349 if (!a)
350 return true;
352 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
353 return false;
356 /* Compare properties of symbols N1 and N2 that does not affect semantics of
357 symbol itself but affects semantics of its references from USED_BY (which
358 may be NULL if it is unknown). If comparsion is false, symbols
359 can still be merged but any symbols referring them can't.
361 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
363 TODO: We can also split attributes to those that determine codegen of
364 a function body/variable constructor itself and those that are used when
365 referring to it. */
367 bool
368 sem_item::compare_referenced_symbol_properties (symtab_node *used_by,
369 symtab_node *n1,
370 symtab_node *n2,
371 bool address)
373 if (is_a <cgraph_node *> (n1))
375 /* Inline properties matters: we do now want to merge uses of inline
376 function to uses of normal function because inline hint would be lost.
377 We however can merge inline function to noinline because the alias
378 will keep its DECL_DECLARED_INLINE flag.
380 Also ignore inline flag when optimizing for size or when function
381 is known to not be inlinable.
383 TODO: the optimize_size checks can also be assumed to be true if
384 unit has no !optimize_size functions. */
386 if ((!used_by || address || !is_a <cgraph_node *> (used_by)
387 || !opt_for_fn (used_by->decl, optimize_size))
388 && !opt_for_fn (n1->decl, optimize_size)
389 && n1->get_availability () > AVAIL_INTERPOSABLE
390 && (!DECL_UNINLINABLE (n1->decl) || !DECL_UNINLINABLE (n2->decl)))
392 if (DECL_DISREGARD_INLINE_LIMITS (n1->decl)
393 != DECL_DISREGARD_INLINE_LIMITS (n2->decl))
394 return return_false_with_msg
395 ("DECL_DISREGARD_INLINE_LIMITS are different");
397 if (DECL_DECLARED_INLINE_P (n1->decl)
398 != DECL_DECLARED_INLINE_P (n2->decl))
399 return return_false_with_msg ("inline attributes are different");
402 if (DECL_IS_OPERATOR_NEW (n1->decl)
403 != DECL_IS_OPERATOR_NEW (n2->decl))
404 return return_false_with_msg ("operator new flags are different");
407 /* Merging two definitions with a reference to equivalent vtables, but
408 belonging to a different type may result in ipa-polymorphic-call analysis
409 giving a wrong answer about the dynamic type of instance. */
410 if (is_a <varpool_node *> (n1))
412 if ((DECL_VIRTUAL_P (n1->decl) || DECL_VIRTUAL_P (n2->decl))
413 && (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl)
414 || !types_must_be_same_for_odr (DECL_CONTEXT (n1->decl),
415 DECL_CONTEXT (n2->decl)))
416 && (!used_by || !is_a <cgraph_node *> (used_by) || address
417 || opt_for_fn (used_by->decl, flag_devirtualize)))
418 return return_false_with_msg
419 ("references to virtual tables can not be merged");
421 if (address && DECL_ALIGN (n1->decl) != DECL_ALIGN (n2->decl))
422 return return_false_with_msg ("alignment mismatch");
424 /* For functions we compare attributes in equals_wpa, because we do
425 not know what attributes may cause codegen differences, but for
426 variables just compare attributes for references - the codegen
427 for constructors is affected only by those attributes that we lower
428 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
429 if (!compare_attributes (DECL_ATTRIBUTES (n1->decl),
430 DECL_ATTRIBUTES (n2->decl)))
431 return return_false_with_msg ("different var decl attributes");
432 if (comp_type_attributes (TREE_TYPE (n1->decl),
433 TREE_TYPE (n2->decl)) != 1)
434 return return_false_with_msg ("different var type attributes");
437 /* When matching virtual tables, be sure to also match information
438 relevant for polymorphic call analysis. */
439 if (used_by && is_a <varpool_node *> (used_by)
440 && DECL_VIRTUAL_P (used_by->decl))
442 if (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl))
443 return return_false_with_msg ("virtual flag mismatch");
444 if (DECL_VIRTUAL_P (n1->decl) && is_a <cgraph_node *> (n1)
445 && (DECL_FINAL_P (n1->decl) != DECL_FINAL_P (n2->decl)))
446 return return_false_with_msg ("final flag mismatch");
448 return true;
451 /* Hash properties that are compared by compare_referenced_symbol_properties. */
453 void
454 sem_item::hash_referenced_symbol_properties (symtab_node *ref,
455 inchash::hash &hstate,
456 bool address)
458 if (is_a <cgraph_node *> (ref))
460 if ((type != FUNC || address || !opt_for_fn (decl, optimize_size))
461 && !opt_for_fn (ref->decl, optimize_size)
462 && !DECL_UNINLINABLE (ref->decl))
464 hstate.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref->decl));
465 hstate.add_flag (DECL_DECLARED_INLINE_P (ref->decl));
467 hstate.add_flag (DECL_IS_OPERATOR_NEW (ref->decl));
469 else if (is_a <varpool_node *> (ref))
471 hstate.add_flag (DECL_VIRTUAL_P (ref->decl));
472 if (address)
473 hstate.add_int (DECL_ALIGN (ref->decl));
478 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
479 point to a same function. Comparison can be skipped if IGNORED_NODES
480 contains these nodes. ADDRESS indicate if address is taken. */
482 bool
483 sem_item::compare_symbol_references (
484 hash_map <symtab_node *, sem_item *> &ignored_nodes,
485 symtab_node *n1, symtab_node *n2, bool address)
487 enum availability avail1, avail2;
489 if (n1 == n2)
490 return true;
492 /* Never match variable and function. */
493 if (is_a <varpool_node *> (n1) != is_a <varpool_node *> (n2))
494 return false;
496 if (!compare_referenced_symbol_properties (node, n1, n2, address))
497 return false;
498 if (address && n1->equal_address_to (n2) == 1)
499 return true;
500 if (!address && n1->semantically_equivalent_p (n2))
501 return true;
503 n1 = n1->ultimate_alias_target (&avail1);
504 n2 = n2->ultimate_alias_target (&avail2);
506 if (avail1 > AVAIL_INTERPOSABLE && ignored_nodes.get (n1)
507 && avail2 > AVAIL_INTERPOSABLE && ignored_nodes.get (n2))
508 return true;
510 return return_false_with_msg ("different references");
513 /* If cgraph edges E1 and E2 are indirect calls, verify that
514 ECF flags are the same. */
516 bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
518 if (e1->indirect_info && e2->indirect_info)
520 int e1_flags = e1->indirect_info->ecf_flags;
521 int e2_flags = e2->indirect_info->ecf_flags;
523 if (e1_flags != e2_flags)
524 return return_false_with_msg ("ICF flags are different");
526 else if (e1->indirect_info || e2->indirect_info)
527 return false;
529 return true;
532 /* Return true if parameter I may be used. */
534 bool
535 sem_function::param_used_p (unsigned int i)
537 if (ipa_node_params_sum == NULL)
538 return true;
540 struct ipa_node_params *parms_info = IPA_NODE_REF (get_node ());
542 if (vec_safe_length (parms_info->descriptors) <= i)
543 return true;
545 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i);
548 /* Perform additional check needed to match types function parameters that are
549 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
550 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
552 bool
553 sem_function::compatible_parm_types_p (tree parm1, tree parm2)
555 /* Be sure that parameters are TBAA compatible. */
556 if (!func_checker::compatible_types_p (parm1, parm2))
557 return return_false_with_msg ("parameter type is not compatible");
559 if (POINTER_TYPE_P (parm1)
560 && (TYPE_RESTRICT (parm1) != TYPE_RESTRICT (parm2)))
561 return return_false_with_msg ("argument restrict flag mismatch");
563 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
564 if (POINTER_TYPE_P (parm1)
565 && TREE_CODE (parm1) != TREE_CODE (parm2)
566 && opt_for_fn (decl, flag_delete_null_pointer_checks))
567 return return_false_with_msg ("pointer wrt reference mismatch");
569 return true;
572 /* Fast equality function based on knowledge known in WPA. */
574 bool
575 sem_function::equals_wpa (sem_item *item,
576 hash_map <symtab_node *, sem_item *> &ignored_nodes)
578 gcc_assert (item->type == FUNC);
579 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
580 cgraph_node *cnode2 = dyn_cast <cgraph_node *> (item->node);
582 m_compared_func = static_cast<sem_function *> (item);
584 if (cnode->thunk.thunk_p != cnode2->thunk.thunk_p)
585 return return_false_with_msg ("thunk_p mismatch");
587 if (cnode->thunk.thunk_p)
589 if (cnode->thunk.fixed_offset != cnode2->thunk.fixed_offset)
590 return return_false_with_msg ("thunk fixed_offset mismatch");
591 if (cnode->thunk.virtual_value != cnode2->thunk.virtual_value)
592 return return_false_with_msg ("thunk virtual_value mismatch");
593 if (cnode->thunk.this_adjusting != cnode2->thunk.this_adjusting)
594 return return_false_with_msg ("thunk this_adjusting mismatch");
595 if (cnode->thunk.virtual_offset_p != cnode2->thunk.virtual_offset_p)
596 return return_false_with_msg ("thunk virtual_offset_p mismatch");
597 if (cnode->thunk.add_pointer_bounds_args
598 != cnode2->thunk.add_pointer_bounds_args)
599 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
602 /* Compare special function DECL attributes. */
603 if (DECL_FUNCTION_PERSONALITY (decl)
604 != DECL_FUNCTION_PERSONALITY (item->decl))
605 return return_false_with_msg ("function personalities are different");
607 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
608 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item->decl))
609 return return_false_with_msg ("intrument function entry exit "
610 "attributes are different");
612 if (DECL_NO_LIMIT_STACK (decl) != DECL_NO_LIMIT_STACK (item->decl))
613 return return_false_with_msg ("no stack limit attributes are different");
615 if (DECL_CXX_CONSTRUCTOR_P (decl) != DECL_CXX_CONSTRUCTOR_P (item->decl))
616 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
618 if (DECL_CXX_DESTRUCTOR_P (decl) != DECL_CXX_DESTRUCTOR_P (item->decl))
619 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
621 /* TODO: pure/const flags mostly matters only for references, except for
622 the fact that codegen takes LOOPING flag as a hint that loops are
623 finite. We may arrange the code to always pick leader that has least
624 specified flags and then this can go into comparing symbol properties. */
625 if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
626 return return_false_with_msg ("decl_or_type flags are different");
628 /* Do not match polymorphic constructors of different types. They calls
629 type memory location for ipa-polymorphic-call and we do not want
630 it to get confused by wrong type. */
631 if (DECL_CXX_CONSTRUCTOR_P (decl)
632 && TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE)
634 if (TREE_CODE (TREE_TYPE (item->decl)) != METHOD_TYPE)
635 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
636 else if (!func_checker::compatible_polymorphic_types_p
637 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
638 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
639 return return_false_with_msg ("ctor polymorphic type mismatch");
642 /* Checking function TARGET and OPTIMIZATION flags. */
643 cl_target_option *tar1 = target_opts_for_fn (decl);
644 cl_target_option *tar2 = target_opts_for_fn (item->decl);
646 if (tar1 != tar2 && !cl_target_option_eq (tar1, tar2))
648 if (dump_file && (dump_flags & TDF_DETAILS))
650 fprintf (dump_file, "target flags difference");
651 cl_target_option_print_diff (dump_file, 2, tar1, tar2);
654 return return_false_with_msg ("Target flags are different");
657 cl_optimization *opt1 = opts_for_fn (decl);
658 cl_optimization *opt2 = opts_for_fn (item->decl);
660 if (opt1 != opt2 && memcmp (opt1, opt2, sizeof(cl_optimization)))
662 if (dump_file && (dump_flags & TDF_DETAILS))
664 fprintf (dump_file, "optimization flags difference");
665 cl_optimization_print_diff (dump_file, 2, opt1, opt2);
668 return return_false_with_msg ("optimization flags are different");
671 /* Result type checking. */
672 if (!func_checker::compatible_types_p
673 (TREE_TYPE (TREE_TYPE (decl)),
674 TREE_TYPE (TREE_TYPE (m_compared_func->decl))))
675 return return_false_with_msg ("result types are different");
677 /* Checking types of arguments. */
678 tree list1 = TYPE_ARG_TYPES (TREE_TYPE (decl)),
679 list2 = TYPE_ARG_TYPES (TREE_TYPE (m_compared_func->decl));
680 for (unsigned i = 0; list1 && list2;
681 list1 = TREE_CHAIN (list1), list2 = TREE_CHAIN (list2), i++)
683 tree parm1 = TREE_VALUE (list1);
684 tree parm2 = TREE_VALUE (list2);
686 /* This guard is here for function pointer with attributes (pr59927.c). */
687 if (!parm1 || !parm2)
688 return return_false_with_msg ("NULL argument type");
690 /* Verify that types are compatible to ensure that both functions
691 have same calling conventions. */
692 if (!types_compatible_p (parm1, parm2))
693 return return_false_with_msg ("parameter types are not compatible");
695 if (!param_used_p (i))
696 continue;
698 /* Perform additional checks for used parameters. */
699 if (!compatible_parm_types_p (parm1, parm2))
700 return false;
703 if (list1 || list2)
704 return return_false_with_msg ("Mismatched number of parameters");
706 if (node->num_references () != item->node->num_references ())
707 return return_false_with_msg ("different number of references");
709 /* Checking function attributes.
710 This is quadratic in number of attributes */
711 if (comp_type_attributes (TREE_TYPE (decl),
712 TREE_TYPE (item->decl)) != 1)
713 return return_false_with_msg ("different type attributes");
714 if (!compare_attributes (DECL_ATTRIBUTES (decl),
715 DECL_ATTRIBUTES (item->decl)))
716 return return_false_with_msg ("different decl attributes");
718 /* The type of THIS pointer type memory location for
719 ipa-polymorphic-call-analysis. */
720 if (opt_for_fn (decl, flag_devirtualize)
721 && (TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE
722 || TREE_CODE (TREE_TYPE (item->decl)) == METHOD_TYPE)
723 && param_used_p (0)
724 && compare_polymorphic_p ())
726 if (TREE_CODE (TREE_TYPE (decl)) != TREE_CODE (TREE_TYPE (item->decl)))
727 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
728 if (!func_checker::compatible_polymorphic_types_p
729 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
730 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
731 return return_false_with_msg ("THIS pointer ODR type mismatch");
734 ipa_ref *ref = NULL, *ref2 = NULL;
735 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
737 item->node->iterate_reference (i, ref2);
739 if (ref->use != ref2->use)
740 return return_false_with_msg ("reference use mismatch");
742 if (!compare_symbol_references (ignored_nodes, ref->referred,
743 ref2->referred,
744 ref->address_matters_p ()))
745 return false;
748 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
749 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
751 while (e1 && e2)
753 if (!compare_symbol_references (ignored_nodes, e1->callee,
754 e2->callee, false))
755 return false;
756 if (!compare_edge_flags (e1, e2))
757 return false;
759 e1 = e1->next_callee;
760 e2 = e2->next_callee;
763 if (e1 || e2)
764 return return_false_with_msg ("different number of calls");
766 e1 = dyn_cast <cgraph_node *> (node)->indirect_calls;
767 e2 = dyn_cast <cgraph_node *> (item->node)->indirect_calls;
769 while (e1 && e2)
771 if (!compare_edge_flags (e1, e2))
772 return false;
774 e1 = e1->next_callee;
775 e2 = e2->next_callee;
778 if (e1 || e2)
779 return return_false_with_msg ("different number of indirect calls");
781 return true;
784 /* Update hash by address sensitive references. We iterate over all
785 sensitive references (address_matters_p) and we hash ultime alias
786 target of these nodes, which can improve a semantic item hash.
788 Also hash in referenced symbols properties. This can be done at any time
789 (as the properties should not change), but it is convenient to do it here
790 while we walk the references anyway. */
792 void
793 sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
794 sem_item *> &m_symtab_node_map)
796 ipa_ref* ref;
797 inchash::hash hstate (get_hash ());
799 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
801 hstate.add_int (ref->use);
802 hash_referenced_symbol_properties (ref->referred, hstate,
803 ref->use == IPA_REF_ADDR);
804 if (ref->address_matters_p () || !m_symtab_node_map.get (ref->referred))
805 hstate.add_int (ref->referred->ultimate_alias_target ()->order);
808 if (is_a <cgraph_node *> (node))
810 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
811 e = e->next_caller)
813 sem_item **result = m_symtab_node_map.get (e->callee);
814 hash_referenced_symbol_properties (e->callee, hstate, false);
815 if (!result)
816 hstate.add_int (e->callee->ultimate_alias_target ()->order);
820 set_hash (hstate.end ());
823 /* Update hash by computed local hash values taken from different
824 semantic items.
825 TODO: stronger SCC based hashing would be desirable here. */
827 void
828 sem_item::update_hash_by_local_refs (hash_map <symtab_node *,
829 sem_item *> &m_symtab_node_map)
831 ipa_ref* ref;
832 inchash::hash state (get_hash ());
834 for (unsigned j = 0; node->iterate_reference (j, ref); j++)
836 sem_item **result = m_symtab_node_map.get (ref->referring);
837 if (result)
838 state.merge_hash ((*result)->get_hash ());
841 if (type == FUNC)
843 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e;
844 e = e->next_callee)
846 sem_item **result = m_symtab_node_map.get (e->caller);
847 if (result)
848 state.merge_hash ((*result)->get_hash ());
852 global_hash = state.end ();
855 /* Returns true if the item equals to ITEM given as argument. */
857 bool
858 sem_function::equals (sem_item *item,
859 hash_map <symtab_node *, sem_item *> &)
861 gcc_assert (item->type == FUNC);
862 bool eq = equals_private (item);
864 if (m_checker != NULL)
866 delete m_checker;
867 m_checker = NULL;
870 if (dump_file && (dump_flags & TDF_DETAILS))
871 fprintf (dump_file,
872 "Equals called for: %s:%s with result: %s\n\n",
873 node->dump_name (),
874 item->node->dump_name (),
875 eq ? "true" : "false");
877 return eq;
880 /* Processes function equality comparison. */
882 bool
883 sem_function::equals_private (sem_item *item)
885 if (item->type != FUNC)
886 return false;
888 basic_block bb1, bb2;
889 edge e1, e2;
890 edge_iterator ei1, ei2;
891 bool result = true;
892 tree arg1, arg2;
894 m_compared_func = static_cast<sem_function *> (item);
896 gcc_assert (decl != item->decl);
898 if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
899 || edge_count != m_compared_func->edge_count
900 || cfg_checksum != m_compared_func->cfg_checksum)
901 return return_false ();
903 m_checker = new func_checker (decl, m_compared_func->decl,
904 compare_polymorphic_p (),
905 false,
906 &refs_set,
907 &m_compared_func->refs_set);
908 arg1 = DECL_ARGUMENTS (decl);
909 arg2 = DECL_ARGUMENTS (m_compared_func->decl);
910 for (unsigned i = 0;
911 arg1 && arg2; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2), i++)
913 if (!types_compatible_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
914 return return_false_with_msg ("argument types are not compatible");
915 if (!param_used_p (i))
916 continue;
917 /* Perform additional checks for used parameters. */
918 if (!compatible_parm_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
919 return false;
920 if (!m_checker->compare_decl (arg1, arg2))
921 return return_false ();
923 if (arg1 || arg2)
924 return return_false_with_msg ("Mismatched number of arguments");
926 if (!dyn_cast <cgraph_node *> (node)->has_gimple_body_p ())
927 return true;
929 /* Fill-up label dictionary. */
930 for (unsigned i = 0; i < bb_sorted.length (); ++i)
932 m_checker->parse_labels (bb_sorted[i]);
933 m_checker->parse_labels (m_compared_func->bb_sorted[i]);
936 /* Checking all basic blocks. */
937 for (unsigned i = 0; i < bb_sorted.length (); ++i)
938 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
939 return return_false();
941 dump_message ("All BBs are equal\n");
943 auto_vec <int> bb_dict;
945 /* Basic block edges check. */
946 for (unsigned i = 0; i < bb_sorted.length (); ++i)
948 bb1 = bb_sorted[i]->bb;
949 bb2 = m_compared_func->bb_sorted[i]->bb;
951 ei2 = ei_start (bb2->preds);
953 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
955 ei_cond (ei2, &e2);
957 if (e1->flags != e2->flags)
958 return return_false_with_msg ("flags comparison returns false");
960 if (!bb_dict_test (&bb_dict, e1->src->index, e2->src->index))
961 return return_false_with_msg ("edge comparison returns false");
963 if (!bb_dict_test (&bb_dict, e1->dest->index, e2->dest->index))
964 return return_false_with_msg ("BB comparison returns false");
966 if (!m_checker->compare_edge (e1, e2))
967 return return_false_with_msg ("edge comparison returns false");
969 ei_next (&ei2);
973 /* Basic block PHI nodes comparison. */
974 for (unsigned i = 0; i < bb_sorted.length (); i++)
975 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
976 return return_false_with_msg ("PHI node comparison returns false");
978 return result;
981 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
982 Helper for call_for_symbol_thunks_and_aliases. */
984 static bool
985 set_local (cgraph_node *node, void *data)
987 node->local.local = data != NULL;
988 return false;
991 /* TREE_ADDRESSABLE of NODE to true.
992 Helper for call_for_symbol_thunks_and_aliases. */
994 static bool
995 set_addressable (varpool_node *node, void *)
997 TREE_ADDRESSABLE (node->decl) = 1;
998 return false;
1001 /* Clear DECL_RTL of NODE.
1002 Helper for call_for_symbol_thunks_and_aliases. */
1004 static bool
1005 clear_decl_rtl (symtab_node *node, void *)
1007 SET_DECL_RTL (node->decl, NULL);
1008 return false;
1011 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1012 possible. Return number of redirections made. */
1014 static int
1015 redirect_all_callers (cgraph_node *n, cgraph_node *to)
1017 int nredirected = 0;
1018 ipa_ref *ref;
1019 cgraph_edge *e = n->callers;
1021 while (e)
1023 /* Redirecting thunks to interposable symbols or symbols in other sections
1024 may not be supported by target output code. Play safe for now and
1025 punt on redirection. */
1026 if (!e->caller->thunk.thunk_p)
1028 struct cgraph_edge *nexte = e->next_caller;
1029 e->redirect_callee (to);
1030 e = nexte;
1031 nredirected++;
1033 else
1034 e = e->next_callee;
1036 for (unsigned i = 0; n->iterate_direct_aliases (i, ref);)
1038 bool removed = false;
1039 cgraph_node *n_alias = dyn_cast <cgraph_node *> (ref->referring);
1041 if ((DECL_COMDAT_GROUP (n->decl)
1042 && (DECL_COMDAT_GROUP (n->decl)
1043 == DECL_COMDAT_GROUP (n_alias->decl)))
1044 || (n_alias->get_availability () > AVAIL_INTERPOSABLE
1045 && n->get_availability () > AVAIL_INTERPOSABLE))
1047 nredirected += redirect_all_callers (n_alias, to);
1048 if (n_alias->can_remove_if_no_direct_calls_p ()
1049 && !n_alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1050 NULL, true)
1051 && !n_alias->has_aliases_p ())
1052 n_alias->remove ();
1054 if (!removed)
1055 i++;
1057 return nredirected;
1060 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1061 be applied. */
1063 bool
1064 sem_function::merge (sem_item *alias_item)
1066 gcc_assert (alias_item->type == FUNC);
1068 sem_function *alias_func = static_cast<sem_function *> (alias_item);
1070 cgraph_node *original = get_node ();
1071 cgraph_node *local_original = NULL;
1072 cgraph_node *alias = alias_func->get_node ();
1074 bool create_wrapper = false;
1075 bool create_alias = false;
1076 bool redirect_callers = false;
1077 bool remove = false;
1079 bool original_discardable = false;
1080 bool original_discarded = false;
1082 bool original_address_matters = original->address_matters_p ();
1083 bool alias_address_matters = alias->address_matters_p ();
1085 if (DECL_EXTERNAL (alias->decl))
1087 if (dump_file)
1088 fprintf (dump_file, "Not unifying; alias is external.\n\n");
1089 return false;
1092 if (DECL_NO_INLINE_WARNING_P (original->decl)
1093 != DECL_NO_INLINE_WARNING_P (alias->decl))
1095 if (dump_file)
1096 fprintf (dump_file,
1097 "Not unifying; "
1098 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1099 return false;
1102 /* Do not attempt to mix functions from different user sections;
1103 we do not know what user intends with those. */
1104 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
1105 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
1106 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
1108 if (dump_file)
1109 fprintf (dump_file,
1110 "Not unifying; "
1111 "original and alias are in different sections.\n\n");
1112 return false;
1115 /* See if original is in a section that can be discarded if the main
1116 symbol is not used. */
1118 if (original->can_be_discarded_p ())
1119 original_discardable = true;
1120 /* Also consider case where we have resolution info and we know that
1121 original's definition is not going to be used. In this case we can not
1122 create alias to original. */
1123 if (node->resolution != LDPR_UNKNOWN
1124 && !decl_binds_to_current_def_p (node->decl))
1125 original_discardable = original_discarded = true;
1127 /* Creating a symtab alias is the optimal way to merge.
1128 It however can not be used in the following cases:
1130 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1131 2) if ORIGINAL is in a section that may be discarded by linker or if
1132 it is an external functions where we can not create an alias
1133 (ORIGINAL_DISCARDABLE)
1134 3) if target do not support symbol aliases.
1135 4) original and alias lie in different comdat groups.
1137 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1138 and/or redirect all callers from ALIAS to ORIGINAL. */
1139 if ((original_address_matters && alias_address_matters)
1140 || (original_discardable
1141 && (!DECL_COMDAT_GROUP (alias->decl)
1142 || (DECL_COMDAT_GROUP (alias->decl)
1143 != DECL_COMDAT_GROUP (original->decl))))
1144 || original_discarded
1145 || !sem_item::target_supports_symbol_aliases_p ()
1146 || DECL_COMDAT_GROUP (alias->decl) != DECL_COMDAT_GROUP (original->decl))
1148 /* First see if we can produce wrapper. */
1150 /* Symbol properties that matter for references must be preserved.
1151 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1152 with proper properties. */
1153 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1154 alias->address_taken))
1156 if (dump_file)
1157 fprintf (dump_file,
1158 "Wrapper cannot be created because referenced symbol "
1159 "properties mismatch\n");
1161 /* Do not turn function in one comdat group into wrapper to another
1162 comdat group. Other compiler producing the body of the
1163 another comdat group may make opossite decision and with unfortunate
1164 linker choices this may close a loop. */
1165 else if (DECL_COMDAT_GROUP (original->decl)
1166 && DECL_COMDAT_GROUP (alias->decl)
1167 && (DECL_COMDAT_GROUP (alias->decl)
1168 != DECL_COMDAT_GROUP (original->decl)))
1170 if (dump_file)
1171 fprintf (dump_file,
1172 "Wrapper cannot be created because of COMDAT\n");
1174 else if (DECL_STATIC_CHAIN (alias->decl)
1175 || DECL_STATIC_CHAIN (original->decl))
1177 if (dump_file)
1178 fprintf (dump_file,
1179 "Cannot create wrapper of nested function.\n");
1181 /* TODO: We can also deal with variadic functions never calling
1182 VA_START. */
1183 else if (stdarg_p (TREE_TYPE (alias->decl)))
1185 if (dump_file)
1186 fprintf (dump_file,
1187 "can not create wrapper of stdarg function.\n");
1189 else if (ipa_fn_summaries
1190 && ipa_fn_summaries->get (alias)->self_size <= 2)
1192 if (dump_file)
1193 fprintf (dump_file, "Wrapper creation is not "
1194 "profitable (function is too small).\n");
1196 /* If user paid attention to mark function noinline, assume it is
1197 somewhat special and do not try to turn it into a wrapper that can
1198 not be undone by inliner. */
1199 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
1201 if (dump_file)
1202 fprintf (dump_file, "Wrappers are not created for noinline.\n");
1204 else
1205 create_wrapper = true;
1207 /* We can redirect local calls in the case both alias and orignal
1208 are not interposable. */
1209 redirect_callers
1210 = alias->get_availability () > AVAIL_INTERPOSABLE
1211 && original->get_availability () > AVAIL_INTERPOSABLE
1212 && !alias->instrumented_version;
1213 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1214 with proper properties. */
1215 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1216 alias->address_taken))
1217 redirect_callers = false;
1219 if (!redirect_callers && !create_wrapper)
1221 if (dump_file)
1222 fprintf (dump_file, "Not unifying; can not redirect callers nor "
1223 "produce wrapper\n\n");
1224 return false;
1227 /* Work out the symbol the wrapper should call.
1228 If ORIGINAL is interposable, we need to call a local alias.
1229 Also produce local alias (if possible) as an optimization.
1231 Local aliases can not be created inside comdat groups because that
1232 prevents inlining. */
1233 if (!original_discardable && !original->get_comdat_group ())
1235 local_original
1236 = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
1237 if (!local_original
1238 && original->get_availability () > AVAIL_INTERPOSABLE)
1239 local_original = original;
1241 /* If we can not use local alias, fallback to the original
1242 when possible. */
1243 else if (original->get_availability () > AVAIL_INTERPOSABLE)
1244 local_original = original;
1246 /* If original is COMDAT local, we can not really redirect calls outside
1247 of its comdat group to it. */
1248 if (original->comdat_local_p ())
1249 redirect_callers = false;
1250 if (!local_original)
1252 if (dump_file)
1253 fprintf (dump_file, "Not unifying; "
1254 "can not produce local alias.\n\n");
1255 return false;
1258 if (!redirect_callers && !create_wrapper)
1260 if (dump_file)
1261 fprintf (dump_file, "Not unifying; "
1262 "can not redirect callers nor produce a wrapper\n\n");
1263 return false;
1265 if (!create_wrapper
1266 && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1267 NULL, true)
1268 && !alias->can_remove_if_no_direct_calls_p ())
1270 if (dump_file)
1271 fprintf (dump_file, "Not unifying; can not make wrapper and "
1272 "function has other uses than direct calls\n\n");
1273 return false;
1276 else
1277 create_alias = true;
1279 if (redirect_callers)
1281 int nredirected = redirect_all_callers (alias, local_original);
1283 if (nredirected)
1285 alias->icf_merged = true;
1286 local_original->icf_merged = true;
1288 if (dump_file && nredirected)
1289 fprintf (dump_file, "%i local calls have been "
1290 "redirected.\n", nredirected);
1293 /* If all callers was redirected, do not produce wrapper. */
1294 if (alias->can_remove_if_no_direct_calls_p ()
1295 && !DECL_VIRTUAL_P (alias->decl)
1296 && !alias->has_aliases_p ())
1298 create_wrapper = false;
1299 remove = true;
1301 gcc_assert (!create_alias);
1303 else if (create_alias)
1305 alias->icf_merged = true;
1307 /* Remove the function's body. */
1308 ipa_merge_profiles (original, alias);
1309 alias->release_body (true);
1310 alias->reset ();
1311 /* Notice global symbol possibly produced RTL. */
1312 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
1313 NULL, true);
1315 /* Create the alias. */
1316 cgraph_node::create_alias (alias_func->decl, decl);
1317 alias->resolve_alias (original);
1319 original->call_for_symbol_thunks_and_aliases
1320 (set_local, (void *)(size_t) original->local_p (), true);
1322 if (dump_file)
1323 fprintf (dump_file, "Unified; Function alias has been created.\n\n");
1325 if (create_wrapper)
1327 gcc_assert (!create_alias);
1328 alias->icf_merged = true;
1329 local_original->icf_merged = true;
1331 /* FIXME update local_original counts. */
1332 ipa_merge_profiles (original, alias, true);
1333 alias->create_wrapper (local_original);
1335 if (dump_file)
1336 fprintf (dump_file, "Unified; Wrapper has been created.\n\n");
1339 /* It's possible that redirection can hit thunks that block
1340 redirection opportunities. */
1341 gcc_assert (alias->icf_merged || remove || redirect_callers);
1342 original->icf_merged = true;
1344 /* We use merged flag to track cases where COMDAT function is known to be
1345 compatible its callers. If we merged in non-COMDAT, we need to give up
1346 on this optimization. */
1347 if (original->merged_comdat && !alias->merged_comdat)
1349 if (dump_file)
1350 fprintf (dump_file, "Dropping merged_comdat flag.\n\n");
1351 if (local_original)
1352 local_original->merged_comdat = false;
1353 original->merged_comdat = false;
1356 if (remove)
1358 ipa_merge_profiles (original, alias);
1359 alias->release_body ();
1360 alias->reset ();
1361 alias->body_removed = true;
1362 alias->icf_merged = true;
1363 if (dump_file)
1364 fprintf (dump_file, "Unified; Function body was removed.\n");
1367 return true;
1370 /* Semantic item initialization function. */
1372 void
1373 sem_function::init (void)
1375 if (in_lto_p)
1376 get_node ()->get_untransformed_body ();
1378 tree fndecl = node->decl;
1379 function *func = DECL_STRUCT_FUNCTION (fndecl);
1381 gcc_assert (func);
1382 gcc_assert (SSANAMES (func));
1384 ssa_names_size = SSANAMES (func)->length ();
1385 node = node;
1387 decl = fndecl;
1388 region_tree = func->eh->region_tree;
1390 /* iterating all function arguments. */
1391 arg_count = count_formal_params (fndecl);
1393 edge_count = n_edges_for_fn (func);
1394 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1395 if (!cnode->thunk.thunk_p)
1397 cfg_checksum = coverage_compute_cfg_checksum (func);
1399 inchash::hash hstate;
1401 basic_block bb;
1402 FOR_EACH_BB_FN (bb, func)
1404 unsigned nondbg_stmt_count = 0;
1406 edge e;
1407 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
1408 ei_next (&ei))
1409 cfg_checksum = iterative_hash_host_wide_int (e->flags,
1410 cfg_checksum);
1412 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1413 gsi_next (&gsi))
1415 gimple *stmt = gsi_stmt (gsi);
1417 if (gimple_code (stmt) != GIMPLE_DEBUG
1418 && gimple_code (stmt) != GIMPLE_PREDICT)
1420 hash_stmt (stmt, hstate);
1421 nondbg_stmt_count++;
1425 gcode_hash = hstate.end ();
1426 bb_sizes.safe_push (nondbg_stmt_count);
1428 /* Inserting basic block to hash table. */
1429 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
1430 EDGE_COUNT (bb->preds)
1431 + EDGE_COUNT (bb->succs));
1433 bb_sorted.safe_push (semantic_bb);
1436 else
1438 cfg_checksum = 0;
1439 inchash::hash hstate;
1440 hstate.add_wide_int (cnode->thunk.fixed_offset);
1441 hstate.add_wide_int (cnode->thunk.virtual_value);
1442 hstate.add_flag (cnode->thunk.this_adjusting);
1443 hstate.add_flag (cnode->thunk.virtual_offset_p);
1444 hstate.add_flag (cnode->thunk.add_pointer_bounds_args);
1445 gcode_hash = hstate.end ();
1449 /* Accumulate to HSTATE a hash of expression EXP.
1450 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1451 and DECL equality classes. */
1453 void
1454 sem_item::add_expr (const_tree exp, inchash::hash &hstate)
1456 if (exp == NULL_TREE)
1458 hstate.merge_hash (0);
1459 return;
1462 /* Handled component can be matched in a cureful way proving equivalence
1463 even if they syntactically differ. Just skip them. */
1464 STRIP_NOPS (exp);
1465 while (handled_component_p (exp))
1466 exp = TREE_OPERAND (exp, 0);
1468 enum tree_code code = TREE_CODE (exp);
1469 hstate.add_int (code);
1471 switch (code)
1473 /* Use inchash::add_expr for everything that is LTO stable. */
1474 case VOID_CST:
1475 case INTEGER_CST:
1476 case REAL_CST:
1477 case FIXED_CST:
1478 case STRING_CST:
1479 case COMPLEX_CST:
1480 case VECTOR_CST:
1481 inchash::add_expr (exp, hstate);
1482 break;
1483 case CONSTRUCTOR:
1485 unsigned HOST_WIDE_INT idx;
1486 tree value;
1488 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1490 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp), idx, value)
1491 if (value)
1492 add_expr (value, hstate);
1493 break;
1495 case ADDR_EXPR:
1496 case FDESC_EXPR:
1497 add_expr (get_base_address (TREE_OPERAND (exp, 0)), hstate);
1498 break;
1499 case SSA_NAME:
1500 case VAR_DECL:
1501 case CONST_DECL:
1502 case PARM_DECL:
1503 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1504 break;
1505 case MEM_REF:
1506 case POINTER_PLUS_EXPR:
1507 case MINUS_EXPR:
1508 case RANGE_EXPR:
1509 add_expr (TREE_OPERAND (exp, 0), hstate);
1510 add_expr (TREE_OPERAND (exp, 1), hstate);
1511 break;
1512 case PLUS_EXPR:
1514 inchash::hash one, two;
1515 add_expr (TREE_OPERAND (exp, 0), one);
1516 add_expr (TREE_OPERAND (exp, 1), two);
1517 hstate.add_commutative (one, two);
1519 break;
1520 CASE_CONVERT:
1521 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1522 return add_expr (TREE_OPERAND (exp, 0), hstate);
1523 default:
1524 break;
1528 /* Accumulate to HSTATE a hash of type t.
1529 TYpes that may end up being compatible after LTO type merging needs to have
1530 the same hash. */
1532 void
1533 sem_item::add_type (const_tree type, inchash::hash &hstate)
1535 if (type == NULL_TREE)
1537 hstate.merge_hash (0);
1538 return;
1541 type = TYPE_MAIN_VARIANT (type);
1543 hstate.add_int (TYPE_MODE (type));
1545 if (TREE_CODE (type) == COMPLEX_TYPE)
1547 hstate.add_int (COMPLEX_TYPE);
1548 sem_item::add_type (TREE_TYPE (type), hstate);
1550 else if (INTEGRAL_TYPE_P (type))
1552 hstate.add_int (INTEGER_TYPE);
1553 hstate.add_flag (TYPE_UNSIGNED (type));
1554 hstate.add_int (TYPE_PRECISION (type));
1556 else if (VECTOR_TYPE_P (type))
1558 hstate.add_int (VECTOR_TYPE);
1559 hstate.add_int (TYPE_PRECISION (type));
1560 sem_item::add_type (TREE_TYPE (type), hstate);
1562 else if (TREE_CODE (type) == ARRAY_TYPE)
1564 hstate.add_int (ARRAY_TYPE);
1565 /* Do not hash size, so complete and incomplete types can match. */
1566 sem_item::add_type (TREE_TYPE (type), hstate);
1568 else if (RECORD_OR_UNION_TYPE_P (type))
1570 gcc_checking_assert (COMPLETE_TYPE_P (type));
1571 hashval_t *val = optimizer->m_type_hash_cache.get (type);
1573 if (!val)
1575 inchash::hash hstate2;
1576 unsigned nf;
1577 tree f;
1578 hashval_t hash;
1580 hstate2.add_int (RECORD_TYPE);
1581 gcc_assert (COMPLETE_TYPE_P (type));
1583 for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
1584 if (TREE_CODE (f) == FIELD_DECL)
1586 add_type (TREE_TYPE (f), hstate2);
1587 nf++;
1590 hstate2.add_int (nf);
1591 hash = hstate2.end ();
1592 hstate.add_wide_int (hash);
1593 optimizer->m_type_hash_cache.put (type, hash);
1595 else
1596 hstate.add_wide_int (*val);
1600 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1602 void
1603 sem_function::hash_stmt (gimple *stmt, inchash::hash &hstate)
1605 enum gimple_code code = gimple_code (stmt);
1607 hstate.add_int (code);
1609 switch (code)
1611 case GIMPLE_SWITCH:
1612 add_expr (gimple_switch_index (as_a <gswitch *> (stmt)), hstate);
1613 break;
1614 case GIMPLE_ASSIGN:
1615 hstate.add_int (gimple_assign_rhs_code (stmt));
1616 if (commutative_tree_code (gimple_assign_rhs_code (stmt))
1617 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1619 inchash::hash one, two;
1621 add_expr (gimple_assign_rhs1 (stmt), one);
1622 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt)), one);
1623 add_expr (gimple_assign_rhs2 (stmt), two);
1624 hstate.add_commutative (one, two);
1625 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1627 add_expr (gimple_assign_rhs3 (stmt), hstate);
1628 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt)), hstate);
1630 add_expr (gimple_assign_lhs (stmt), hstate);
1631 add_type (TREE_TYPE (gimple_assign_lhs (stmt)), two);
1632 break;
1634 /* fall through */
1635 case GIMPLE_CALL:
1636 case GIMPLE_ASM:
1637 case GIMPLE_COND:
1638 case GIMPLE_GOTO:
1639 case GIMPLE_RETURN:
1640 /* All these statements are equivalent if their operands are. */
1641 for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1643 add_expr (gimple_op (stmt, i), hstate);
1644 if (gimple_op (stmt, i))
1645 add_type (TREE_TYPE (gimple_op (stmt, i)), hstate);
1647 default:
1648 break;
1653 /* Return true if polymorphic comparison must be processed. */
1655 bool
1656 sem_function::compare_polymorphic_p (void)
1658 struct cgraph_edge *e;
1660 if (!opt_for_fn (get_node ()->decl, flag_devirtualize))
1661 return false;
1662 if (get_node ()->indirect_calls != NULL)
1663 return true;
1664 /* TODO: We can do simple propagation determining what calls may lead to
1665 a polymorphic call. */
1666 for (e = get_node ()->callees; e; e = e->next_callee)
1667 if (e->callee->definition
1668 && opt_for_fn (e->callee->decl, flag_devirtualize))
1669 return true;
1670 return false;
1673 /* For a given call graph NODE, the function constructs new
1674 semantic function item. */
1676 sem_function *
1677 sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
1679 tree fndecl = node->decl;
1680 function *func = DECL_STRUCT_FUNCTION (fndecl);
1682 if (!func || (!node->has_gimple_body_p () && !node->thunk.thunk_p))
1683 return NULL;
1685 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
1686 return NULL;
1688 if (lookup_attribute_by_prefix ("oacc ",
1689 DECL_ATTRIBUTES (node->decl)) != NULL)
1690 return NULL;
1692 /* PR ipa/70306. */
1693 if (DECL_STATIC_CONSTRUCTOR (node->decl)
1694 || DECL_STATIC_DESTRUCTOR (node->decl))
1695 return NULL;
1697 sem_function *f = new sem_function (node, stack);
1699 f->init ();
1701 return f;
1704 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1705 return true if phi nodes are semantically equivalent in these blocks . */
1707 bool
1708 sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
1710 gphi_iterator si1, si2;
1711 gphi *phi1, *phi2;
1712 unsigned size1, size2, i;
1713 tree t1, t2;
1714 edge e1, e2;
1716 gcc_assert (bb1 != NULL);
1717 gcc_assert (bb2 != NULL);
1719 si2 = gsi_start_phis (bb2);
1720 for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
1721 gsi_next (&si1))
1723 gsi_next_nonvirtual_phi (&si1);
1724 gsi_next_nonvirtual_phi (&si2);
1726 if (gsi_end_p (si1) && gsi_end_p (si2))
1727 break;
1729 if (gsi_end_p (si1) || gsi_end_p (si2))
1730 return return_false();
1732 phi1 = si1.phi ();
1733 phi2 = si2.phi ();
1735 tree phi_result1 = gimple_phi_result (phi1);
1736 tree phi_result2 = gimple_phi_result (phi2);
1738 if (!m_checker->compare_operand (phi_result1, phi_result2))
1739 return return_false_with_msg ("PHI results are different");
1741 size1 = gimple_phi_num_args (phi1);
1742 size2 = gimple_phi_num_args (phi2);
1744 if (size1 != size2)
1745 return return_false ();
1747 for (i = 0; i < size1; ++i)
1749 t1 = gimple_phi_arg (phi1, i)->def;
1750 t2 = gimple_phi_arg (phi2, i)->def;
1752 if (!m_checker->compare_operand (t1, t2))
1753 return return_false ();
1755 e1 = gimple_phi_arg_edge (phi1, i);
1756 e2 = gimple_phi_arg_edge (phi2, i);
1758 if (!m_checker->compare_edge (e1, e2))
1759 return return_false ();
1762 gsi_next (&si2);
1765 return true;
1768 /* Returns true if tree T can be compared as a handled component. */
1770 bool
1771 sem_function::icf_handled_component_p (tree t)
1773 tree_code tc = TREE_CODE (t);
1775 return (handled_component_p (t)
1776 || tc == ADDR_EXPR || tc == MEM_REF || tc == OBJ_TYPE_REF);
1779 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1780 corresponds to TARGET. */
1782 bool
1783 sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
1785 source++;
1786 target++;
1788 if (bb_dict->length () <= (unsigned)source)
1789 bb_dict->safe_grow_cleared (source + 1);
1791 if ((*bb_dict)[source] == 0)
1793 (*bb_dict)[source] = target;
1794 return true;
1796 else
1797 return (*bb_dict)[source] == target;
1800 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
1804 sem_variable::sem_variable (varpool_node *node, bitmap_obstack *stack)
1805 : sem_item (VAR, node, stack)
1807 gcc_checking_assert (node);
1808 gcc_checking_assert (get_node ());
1811 /* Fast equality function based on knowledge known in WPA. */
1813 bool
1814 sem_variable::equals_wpa (sem_item *item,
1815 hash_map <symtab_node *, sem_item *> &ignored_nodes)
1817 gcc_assert (item->type == VAR);
1819 if (node->num_references () != item->node->num_references ())
1820 return return_false_with_msg ("different number of references");
1822 if (DECL_TLS_MODEL (decl) || DECL_TLS_MODEL (item->decl))
1823 return return_false_with_msg ("TLS model");
1825 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1826 alignment out of all aliases. */
1828 if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
1829 return return_false_with_msg ("Virtual flag mismatch");
1831 if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
1832 && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
1833 || !operand_equal_p (DECL_SIZE (decl),
1834 DECL_SIZE (item->decl), OEP_ONLY_CONST)))
1835 return return_false_with_msg ("size mismatch");
1837 /* Do not attempt to mix data from different user sections;
1838 we do not know what user intends with those. */
1839 if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
1840 || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
1841 && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
1842 return return_false_with_msg ("user section mismatch");
1844 if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
1845 return return_false_with_msg ("text section");
1847 ipa_ref *ref = NULL, *ref2 = NULL;
1848 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
1850 item->node->iterate_reference (i, ref2);
1852 if (ref->use != ref2->use)
1853 return return_false_with_msg ("reference use mismatch");
1855 if (!compare_symbol_references (ignored_nodes,
1856 ref->referred, ref2->referred,
1857 ref->address_matters_p ()))
1858 return false;
1861 return true;
1864 /* Returns true if the item equals to ITEM given as argument. */
1866 bool
1867 sem_variable::equals (sem_item *item,
1868 hash_map <symtab_node *, sem_item *> &)
1870 gcc_assert (item->type == VAR);
1871 bool ret;
1873 if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
1874 dyn_cast <varpool_node *>(node)->get_constructor ();
1875 if (DECL_INITIAL (item->decl) == error_mark_node && in_lto_p)
1876 dyn_cast <varpool_node *>(item->node)->get_constructor ();
1878 /* As seen in PR ipa/65303 we have to compare variables types. */
1879 if (!func_checker::compatible_types_p (TREE_TYPE (decl),
1880 TREE_TYPE (item->decl)))
1881 return return_false_with_msg ("variables types are different");
1883 ret = sem_variable::equals (DECL_INITIAL (decl),
1884 DECL_INITIAL (item->node->decl));
1885 if (dump_file && (dump_flags & TDF_DETAILS))
1886 fprintf (dump_file,
1887 "Equals called for vars: %s:%s with result: %s\n\n",
1888 node->dump_name (), item->node->dump_name (),
1889 ret ? "true" : "false");
1891 return ret;
1894 /* Compares trees T1 and T2 for semantic equality. */
1896 bool
1897 sem_variable::equals (tree t1, tree t2)
1899 if (!t1 || !t2)
1900 return return_with_debug (t1 == t2);
1901 if (t1 == t2)
1902 return true;
1903 tree_code tc1 = TREE_CODE (t1);
1904 tree_code tc2 = TREE_CODE (t2);
1906 if (tc1 != tc2)
1907 return return_false_with_msg ("TREE_CODE mismatch");
1909 switch (tc1)
1911 case CONSTRUCTOR:
1913 vec<constructor_elt, va_gc> *v1, *v2;
1914 unsigned HOST_WIDE_INT idx;
1916 enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
1917 if (typecode != TREE_CODE (TREE_TYPE (t2)))
1918 return return_false_with_msg ("constructor type mismatch");
1920 if (typecode == ARRAY_TYPE)
1922 HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
1923 /* For arrays, check that the sizes all match. */
1924 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
1925 || size_1 == -1
1926 || size_1 != int_size_in_bytes (TREE_TYPE (t2)))
1927 return return_false_with_msg ("constructor array size mismatch");
1929 else if (!func_checker::compatible_types_p (TREE_TYPE (t1),
1930 TREE_TYPE (t2)))
1931 return return_false_with_msg ("constructor type incompatible");
1933 v1 = CONSTRUCTOR_ELTS (t1);
1934 v2 = CONSTRUCTOR_ELTS (t2);
1935 if (vec_safe_length (v1) != vec_safe_length (v2))
1936 return return_false_with_msg ("constructor number of elts mismatch");
1938 for (idx = 0; idx < vec_safe_length (v1); ++idx)
1940 constructor_elt *c1 = &(*v1)[idx];
1941 constructor_elt *c2 = &(*v2)[idx];
1943 /* Check that each value is the same... */
1944 if (!sem_variable::equals (c1->value, c2->value))
1945 return false;
1946 /* ... and that they apply to the same fields! */
1947 if (!sem_variable::equals (c1->index, c2->index))
1948 return false;
1950 return true;
1952 case MEM_REF:
1954 tree x1 = TREE_OPERAND (t1, 0);
1955 tree x2 = TREE_OPERAND (t2, 0);
1956 tree y1 = TREE_OPERAND (t1, 1);
1957 tree y2 = TREE_OPERAND (t2, 1);
1959 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
1960 return return_false ();
1962 /* Type of the offset on MEM_REF does not matter. */
1963 return return_with_debug (sem_variable::equals (x1, x2)
1964 && wi::to_offset (y1)
1965 == wi::to_offset (y2));
1967 case ADDR_EXPR:
1968 case FDESC_EXPR:
1970 tree op1 = TREE_OPERAND (t1, 0);
1971 tree op2 = TREE_OPERAND (t2, 0);
1972 return sem_variable::equals (op1, op2);
1974 /* References to other vars/decls are compared using ipa-ref. */
1975 case FUNCTION_DECL:
1976 case VAR_DECL:
1977 if (decl_in_symtab_p (t1) && decl_in_symtab_p (t2))
1978 return true;
1979 return return_false_with_msg ("Declaration mismatch");
1980 case CONST_DECL:
1981 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1982 need to process its VAR/FUNCTION references without relying on ipa-ref
1983 compare. */
1984 case FIELD_DECL:
1985 case LABEL_DECL:
1986 return return_false_with_msg ("Declaration mismatch");
1987 case INTEGER_CST:
1988 /* Integer constants are the same only if the same width of type. */
1989 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1990 return return_false_with_msg ("INTEGER_CST precision mismatch");
1991 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1992 return return_false_with_msg ("INTEGER_CST mode mismatch");
1993 return return_with_debug (tree_int_cst_equal (t1, t2));
1994 case STRING_CST:
1995 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1996 return return_false_with_msg ("STRING_CST mode mismatch");
1997 if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
1998 return return_false_with_msg ("STRING_CST length mismatch");
1999 if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
2000 TREE_STRING_LENGTH (t1)))
2001 return return_false_with_msg ("STRING_CST mismatch");
2002 return true;
2003 case FIXED_CST:
2004 /* Fixed 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 ("FIXED_CST precision mismatch");
2008 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
2009 TREE_FIXED_CST (t2)));
2010 case COMPLEX_CST:
2011 return (sem_variable::equals (TREE_REALPART (t1), TREE_REALPART (t2))
2012 && sem_variable::equals (TREE_IMAGPART (t1), TREE_IMAGPART (t2)));
2013 case REAL_CST:
2014 /* Real constants are the same only if the same width of type. */
2015 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2016 return return_false_with_msg ("REAL_CST precision mismatch");
2017 return return_with_debug (real_identical (&TREE_REAL_CST (t1),
2018 &TREE_REAL_CST (t2)));
2019 case VECTOR_CST:
2021 unsigned i;
2023 if (VECTOR_CST_NELTS (t1) != VECTOR_CST_NELTS (t2))
2024 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2026 for (i = 0; i < VECTOR_CST_NELTS (t1); ++i)
2027 if (!sem_variable::equals (VECTOR_CST_ELT (t1, i),
2028 VECTOR_CST_ELT (t2, i)))
2029 return 0;
2031 return 1;
2033 case ARRAY_REF:
2034 case ARRAY_RANGE_REF:
2036 tree x1 = TREE_OPERAND (t1, 0);
2037 tree x2 = TREE_OPERAND (t2, 0);
2038 tree y1 = TREE_OPERAND (t1, 1);
2039 tree y2 = TREE_OPERAND (t2, 1);
2041 if (!sem_variable::equals (x1, x2) || !sem_variable::equals (y1, y2))
2042 return false;
2043 if (!sem_variable::equals (array_ref_low_bound (t1),
2044 array_ref_low_bound (t2)))
2045 return false;
2046 if (!sem_variable::equals (array_ref_element_size (t1),
2047 array_ref_element_size (t2)))
2048 return false;
2049 return true;
2052 case COMPONENT_REF:
2053 case POINTER_PLUS_EXPR:
2054 case PLUS_EXPR:
2055 case MINUS_EXPR:
2056 case RANGE_EXPR:
2058 tree x1 = TREE_OPERAND (t1, 0);
2059 tree x2 = TREE_OPERAND (t2, 0);
2060 tree y1 = TREE_OPERAND (t1, 1);
2061 tree y2 = TREE_OPERAND (t2, 1);
2063 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
2066 CASE_CONVERT:
2067 case VIEW_CONVERT_EXPR:
2068 if (!func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
2069 return return_false ();
2070 return sem_variable::equals (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
2071 case ERROR_MARK:
2072 return return_false_with_msg ("ERROR_MARK");
2073 default:
2074 return return_false_with_msg ("Unknown TREE code reached");
2078 /* Parser function that visits a varpool NODE. */
2080 sem_variable *
2081 sem_variable::parse (varpool_node *node, bitmap_obstack *stack)
2083 if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl)
2084 || node->alias)
2085 return NULL;
2087 sem_variable *v = new sem_variable (node, stack);
2089 v->init ();
2091 return v;
2094 /* References independent hash function. */
2096 hashval_t
2097 sem_variable::get_hash (void)
2099 if (m_hash_set)
2100 return m_hash;
2102 /* All WPA streamed in symbols should have their hashes computed at compile
2103 time. At this point, the constructor may not be in memory at all.
2104 DECL_INITIAL (decl) would be error_mark_node in that case. */
2105 gcc_assert (!node->lto_file_data);
2106 tree ctor = DECL_INITIAL (decl);
2107 inchash::hash hstate;
2109 hstate.add_int (456346417);
2110 if (DECL_SIZE (decl) && tree_fits_shwi_p (DECL_SIZE (decl)))
2111 hstate.add_wide_int (tree_to_shwi (DECL_SIZE (decl)));
2112 add_expr (ctor, hstate);
2113 set_hash (hstate.end ());
2115 return m_hash;
2118 /* Set all points-to UIDs of aliases pointing to node N as UID. */
2120 static void
2121 set_alias_uids (symtab_node *n, int uid)
2123 ipa_ref *ref;
2124 FOR_EACH_ALIAS (n, ref)
2126 if (dump_file)
2127 fprintf (dump_file, " Setting points-to UID of [%s] as %d\n",
2128 xstrdup_for_dump (ref->referring->asm_name ()), uid);
2130 SET_DECL_PT_UID (ref->referring->decl, uid);
2131 set_alias_uids (ref->referring, uid);
2135 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2136 be applied. */
2138 bool
2139 sem_variable::merge (sem_item *alias_item)
2141 gcc_assert (alias_item->type == VAR);
2143 if (!sem_item::target_supports_symbol_aliases_p ())
2145 if (dump_file)
2146 fprintf (dump_file, "Not unifying; "
2147 "Symbol aliases are not supported by target\n\n");
2148 return false;
2151 if (DECL_EXTERNAL (alias_item->decl))
2153 if (dump_file)
2154 fprintf (dump_file, "Not unifying; alias is external.\n\n");
2155 return false;
2158 sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
2160 varpool_node *original = get_node ();
2161 varpool_node *alias = alias_var->get_node ();
2162 bool original_discardable = false;
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 (alias_address_matters && flag_merge_constants < 2)
2208 if (dump_file)
2209 fprintf (dump_file,
2210 "Not unifying; address of original may be compared.\n\n");
2211 return false;
2214 if (DECL_ALIGN (original->decl) < DECL_ALIGN (alias->decl))
2216 if (dump_file)
2217 fprintf (dump_file, "Not unifying; "
2218 "original and alias have incompatible alignments\n\n");
2220 return false;
2223 if (DECL_COMDAT_GROUP (original->decl) != DECL_COMDAT_GROUP (alias->decl))
2225 if (dump_file)
2226 fprintf (dump_file, "Not unifying; alias cannot be created; "
2227 "across comdat group boundary\n\n");
2229 return false;
2232 if (original_discardable)
2234 if (dump_file)
2235 fprintf (dump_file, "Not unifying; alias cannot be created; "
2236 "target is discardable\n\n");
2238 return false;
2240 else
2242 gcc_assert (!original->alias);
2243 gcc_assert (!alias->alias);
2245 alias->analyzed = false;
2247 DECL_INITIAL (alias->decl) = NULL;
2248 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
2249 NULL, true);
2250 alias->need_bounds_init = false;
2251 alias->remove_all_references ();
2252 if (TREE_ADDRESSABLE (alias->decl))
2253 original->call_for_symbol_and_aliases (set_addressable, NULL, true);
2255 varpool_node::create_alias (alias_var->decl, decl);
2256 alias->resolve_alias (original);
2258 if (dump_file)
2259 fprintf (dump_file, "Unified; Variable alias has been created.\n");
2261 set_alias_uids (original, DECL_UID (original->decl));
2262 return true;
2266 /* Dump symbol to FILE. */
2268 void
2269 sem_variable::dump_to_file (FILE *file)
2271 gcc_assert (file);
2273 print_node (file, "", decl, 0);
2274 fprintf (file, "\n\n");
2277 unsigned int sem_item_optimizer::class_id = 0;
2279 sem_item_optimizer::sem_item_optimizer ()
2280 : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL),
2281 m_varpool_node_hooks (NULL)
2283 m_items.create (0);
2284 bitmap_obstack_initialize (&m_bmstack);
2287 sem_item_optimizer::~sem_item_optimizer ()
2289 for (unsigned int i = 0; i < m_items.length (); i++)
2290 delete m_items[i];
2293 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
2294 it != m_classes.end (); ++it)
2296 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2297 delete (*it)->classes[i];
2299 (*it)->classes.release ();
2300 free (*it);
2303 m_items.release ();
2305 bitmap_obstack_release (&m_bmstack);
2308 /* Write IPA ICF summary for symbols. */
2310 void
2311 sem_item_optimizer::write_summary (void)
2313 unsigned int count = 0;
2315 output_block *ob = create_output_block (LTO_section_ipa_icf);
2316 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
2317 ob->symbol = NULL;
2319 /* Calculate number of symbols to be serialized. */
2320 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2321 !lsei_end_p (lsei);
2322 lsei_next_in_partition (&lsei))
2324 symtab_node *node = lsei_node (lsei);
2326 if (m_symtab_node_map.get (node))
2327 count++;
2330 streamer_write_uhwi (ob, count);
2332 /* Process all of the symbols. */
2333 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2334 !lsei_end_p (lsei);
2335 lsei_next_in_partition (&lsei))
2337 symtab_node *node = lsei_node (lsei);
2339 sem_item **item = m_symtab_node_map.get (node);
2341 if (item && *item)
2343 int node_ref = lto_symtab_encoder_encode (encoder, node);
2344 streamer_write_uhwi_stream (ob->main_stream, node_ref);
2346 streamer_write_uhwi (ob, (*item)->get_hash ());
2350 streamer_write_char_stream (ob->main_stream, 0);
2351 produce_asm (ob, NULL);
2352 destroy_output_block (ob);
2355 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2356 contains LEN bytes. */
2358 void
2359 sem_item_optimizer::read_section (lto_file_decl_data *file_data,
2360 const char *data, size_t len)
2362 const lto_function_header *header
2363 = (const lto_function_header *) data;
2364 const int cfg_offset = sizeof (lto_function_header);
2365 const int main_offset = cfg_offset + header->cfg_size;
2366 const int string_offset = main_offset + header->main_size;
2367 data_in *data_in;
2368 unsigned int i;
2369 unsigned int count;
2371 lto_input_block ib_main ((const char *) data + main_offset, 0,
2372 header->main_size, file_data->mode_table);
2374 data_in
2375 = lto_data_in_create (file_data, (const char *) data + string_offset,
2376 header->string_size, vNULL);
2378 count = streamer_read_uhwi (&ib_main);
2380 for (i = 0; i < count; i++)
2382 unsigned int index;
2383 symtab_node *node;
2384 lto_symtab_encoder_t encoder;
2386 index = streamer_read_uhwi (&ib_main);
2387 encoder = file_data->symtab_node_encoder;
2388 node = lto_symtab_encoder_deref (encoder, index);
2390 hashval_t hash = streamer_read_uhwi (&ib_main);
2392 gcc_assert (node->definition);
2394 if (dump_file)
2395 fprintf (dump_file, "Symbol added: %s (tree: %p)\n",
2396 node->dump_asm_name (), (void *) node->decl);
2398 if (is_a<cgraph_node *> (node))
2400 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
2402 sem_function *fn = new sem_function (cnode, &m_bmstack);
2403 fn->set_hash (hash);
2404 m_items.safe_push (fn);
2406 else
2408 varpool_node *vnode = dyn_cast <varpool_node *> (node);
2410 sem_variable *var = new sem_variable (vnode, &m_bmstack);
2411 var->set_hash (hash);
2412 m_items.safe_push (var);
2416 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
2417 len);
2418 lto_data_in_delete (data_in);
2421 /* Read IPA ICF summary for symbols. */
2423 void
2424 sem_item_optimizer::read_summary (void)
2426 lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2427 lto_file_decl_data *file_data;
2428 unsigned int j = 0;
2430 while ((file_data = file_data_vec[j++]))
2432 size_t len;
2433 const char *data = lto_get_section_data (file_data,
2434 LTO_section_ipa_icf, NULL, &len);
2436 if (data)
2437 read_section (file_data, data, len);
2441 /* Register callgraph and varpool hooks. */
2443 void
2444 sem_item_optimizer::register_hooks (void)
2446 if (!m_cgraph_node_hooks)
2447 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
2448 (&sem_item_optimizer::cgraph_removal_hook, this);
2450 if (!m_varpool_node_hooks)
2451 m_varpool_node_hooks = symtab->add_varpool_removal_hook
2452 (&sem_item_optimizer::varpool_removal_hook, this);
2455 /* Unregister callgraph and varpool hooks. */
2457 void
2458 sem_item_optimizer::unregister_hooks (void)
2460 if (m_cgraph_node_hooks)
2461 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
2463 if (m_varpool_node_hooks)
2464 symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
2467 /* Adds a CLS to hashtable associated by hash value. */
2469 void
2470 sem_item_optimizer::add_class (congruence_class *cls)
2472 gcc_assert (cls->members.length ());
2474 congruence_class_group *group
2475 = get_group_by_hash (cls->members[0]->get_hash (),
2476 cls->members[0]->type);
2477 group->classes.safe_push (cls);
2480 /* Gets a congruence class group based on given HASH value and TYPE. */
2482 congruence_class_group *
2483 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
2485 congruence_class_group *item = XNEW (congruence_class_group);
2486 item->hash = hash;
2487 item->type = type;
2489 congruence_class_group **slot = m_classes.find_slot (item, INSERT);
2491 if (*slot)
2492 free (item);
2493 else
2495 item->classes.create (1);
2496 *slot = item;
2499 return *slot;
2502 /* Callgraph removal hook called for a NODE with a custom DATA. */
2504 void
2505 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
2507 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2508 optimizer->remove_symtab_node (node);
2511 /* Varpool removal hook called for a NODE with a custom DATA. */
2513 void
2514 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
2516 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2517 optimizer->remove_symtab_node (node);
2520 /* Remove symtab NODE triggered by symtab removal hooks. */
2522 void
2523 sem_item_optimizer::remove_symtab_node (symtab_node *node)
2525 gcc_assert (!m_classes.elements ());
2527 m_removed_items_set.add (node);
2530 void
2531 sem_item_optimizer::remove_item (sem_item *item)
2533 if (m_symtab_node_map.get (item->node))
2534 m_symtab_node_map.remove (item->node);
2535 delete item;
2538 /* Removes all callgraph and varpool nodes that are marked by symtab
2539 as deleted. */
2541 void
2542 sem_item_optimizer::filter_removed_items (void)
2544 auto_vec <sem_item *> filtered;
2546 for (unsigned int i = 0; i < m_items.length(); i++)
2548 sem_item *item = m_items[i];
2550 if (m_removed_items_set.contains (item->node))
2552 remove_item (item);
2553 continue;
2556 if (item->type == FUNC)
2558 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
2560 if (in_lto_p && (cnode->alias || cnode->body_removed))
2561 remove_item (item);
2562 else
2563 filtered.safe_push (item);
2565 else /* VAR. */
2567 if (!flag_ipa_icf_variables)
2568 remove_item (item);
2569 else
2571 /* Filter out non-readonly variables. */
2572 tree decl = item->decl;
2573 if (TREE_READONLY (decl))
2574 filtered.safe_push (item);
2575 else
2576 remove_item (item);
2581 /* Clean-up of released semantic items. */
2583 m_items.release ();
2584 for (unsigned int i = 0; i < filtered.length(); i++)
2585 m_items.safe_push (filtered[i]);
2588 /* Optimizer entry point which returns true in case it processes
2589 a merge operation. True is returned if there's a merge operation
2590 processed. */
2592 bool
2593 sem_item_optimizer::execute (void)
2595 filter_removed_items ();
2596 unregister_hooks ();
2598 build_graph ();
2599 update_hash_by_addr_refs ();
2600 build_hash_based_classes ();
2602 if (dump_file)
2603 fprintf (dump_file, "Dump after hash based groups\n");
2604 dump_cong_classes ();
2606 for (unsigned int i = 0; i < m_items.length(); i++)
2607 m_items[i]->init_wpa ();
2609 subdivide_classes_by_equality (true);
2611 if (dump_file)
2612 fprintf (dump_file, "Dump after WPA based types groups\n");
2614 dump_cong_classes ();
2616 process_cong_reduction ();
2617 checking_verify_classes ();
2619 if (dump_file)
2620 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
2622 dump_cong_classes ();
2624 parse_nonsingleton_classes ();
2625 subdivide_classes_by_equality ();
2627 if (dump_file)
2628 fprintf (dump_file, "Dump after full equality comparison of groups\n");
2630 dump_cong_classes ();
2632 unsigned int prev_class_count = m_classes_count;
2634 process_cong_reduction ();
2635 dump_cong_classes ();
2636 checking_verify_classes ();
2637 bool merged_p = merge_classes (prev_class_count);
2639 if (dump_file && (dump_flags & TDF_DETAILS))
2640 symtab->dump (dump_file);
2642 return merged_p;
2645 /* Function responsible for visiting all potential functions and
2646 read-only variables that can be merged. */
2648 void
2649 sem_item_optimizer::parse_funcs_and_vars (void)
2651 cgraph_node *cnode;
2653 if (flag_ipa_icf_functions)
2654 FOR_EACH_DEFINED_FUNCTION (cnode)
2656 sem_function *f = sem_function::parse (cnode, &m_bmstack);
2657 if (f)
2659 m_items.safe_push (f);
2660 m_symtab_node_map.put (cnode, f);
2662 if (dump_file)
2663 fprintf (dump_file, "Parsed function:%s\n", f->node->asm_name ());
2665 if (dump_file && (dump_flags & TDF_DETAILS))
2666 f->dump_to_file (dump_file);
2668 else if (dump_file)
2669 fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
2672 varpool_node *vnode;
2674 if (flag_ipa_icf_variables)
2675 FOR_EACH_DEFINED_VARIABLE (vnode)
2677 sem_variable *v = sem_variable::parse (vnode, &m_bmstack);
2679 if (v)
2681 m_items.safe_push (v);
2682 m_symtab_node_map.put (vnode, v);
2687 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2689 void
2690 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
2692 item->index_in_class = cls->members.length ();
2693 cls->members.safe_push (item);
2694 item->cls = cls;
2697 /* For each semantic item, append hash values of references. */
2699 void
2700 sem_item_optimizer::update_hash_by_addr_refs ()
2702 /* First, append to hash sensitive references and class type if it need to
2703 be matched for ODR. */
2704 for (unsigned i = 0; i < m_items.length (); i++)
2706 m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
2707 if (m_items[i]->type == FUNC)
2709 if (TREE_CODE (TREE_TYPE (m_items[i]->decl)) == METHOD_TYPE
2710 && contains_polymorphic_type_p
2711 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl)))
2712 && (DECL_CXX_CONSTRUCTOR_P (m_items[i]->decl)
2713 || (static_cast<sem_function *> (m_items[i])->param_used_p (0)
2714 && static_cast<sem_function *> (m_items[i])
2715 ->compare_polymorphic_p ())))
2717 tree class_type
2718 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl));
2719 inchash::hash hstate (m_items[i]->get_hash ());
2721 if (TYPE_NAME (class_type)
2722 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type)))
2723 hstate.add_wide_int
2724 (IDENTIFIER_HASH_VALUE
2725 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type))));
2727 m_items[i]->set_hash (hstate.end ());
2732 /* Once all symbols have enhanced hash value, we can append
2733 hash values of symbols that are seen by IPA ICF and are
2734 references by a semantic item. Newly computed values
2735 are saved to global_hash member variable. */
2736 for (unsigned i = 0; i < m_items.length (); i++)
2737 m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
2739 /* Global hash value replace current hash values. */
2740 for (unsigned i = 0; i < m_items.length (); i++)
2741 m_items[i]->set_hash (m_items[i]->global_hash);
2744 /* Congruence classes are built by hash value. */
2746 void
2747 sem_item_optimizer::build_hash_based_classes (void)
2749 for (unsigned i = 0; i < m_items.length (); i++)
2751 sem_item *item = m_items[i];
2753 congruence_class_group *group
2754 = get_group_by_hash (item->get_hash (), item->type);
2756 if (!group->classes.length ())
2758 m_classes_count++;
2759 group->classes.safe_push (new congruence_class (class_id++));
2762 add_item_to_class (group->classes[0], item);
2766 /* Build references according to call graph. */
2768 void
2769 sem_item_optimizer::build_graph (void)
2771 for (unsigned i = 0; i < m_items.length (); i++)
2773 sem_item *item = m_items[i];
2774 m_symtab_node_map.put (item->node, item);
2776 /* Initialize hash values if we are not in LTO mode. */
2777 if (!in_lto_p)
2778 item->get_hash ();
2781 for (unsigned i = 0; i < m_items.length (); i++)
2783 sem_item *item = m_items[i];
2785 if (item->type == FUNC)
2787 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
2789 cgraph_edge *e = cnode->callees;
2790 while (e)
2792 sem_item **slot = m_symtab_node_map.get
2793 (e->callee->ultimate_alias_target ());
2794 if (slot)
2795 item->add_reference (*slot);
2797 e = e->next_callee;
2801 ipa_ref *ref = NULL;
2802 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
2804 sem_item **slot = m_symtab_node_map.get
2805 (ref->referred->ultimate_alias_target ());
2806 if (slot)
2807 item->add_reference (*slot);
2812 /* Semantic items in classes having more than one element and initialized.
2813 In case of WPA, we load function body. */
2815 void
2816 sem_item_optimizer::parse_nonsingleton_classes (void)
2818 unsigned int init_called_count = 0;
2820 for (unsigned i = 0; i < m_items.length (); i++)
2821 if (m_items[i]->cls->members.length () > 1)
2823 m_items[i]->init ();
2824 init_called_count++;
2827 if (dump_file)
2828 fprintf (dump_file, "Init called for %u items (%.2f%%).\n",
2829 init_called_count,
2830 m_items.length () ? 100.0f * init_called_count / m_items.length ()
2831 : 0.0f);
2834 /* Equality function for semantic items is used to subdivide existing
2835 classes. If IN_WPA, fast equality function is invoked. */
2837 void
2838 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
2840 for (hash_table <congruence_class_hash>::iterator it = m_classes.begin ();
2841 it != m_classes.end (); ++it)
2843 unsigned int class_count = (*it)->classes.length ();
2845 for (unsigned i = 0; i < class_count; i++)
2847 congruence_class *c = (*it)->classes[i];
2849 if (c->members.length() > 1)
2851 auto_vec <sem_item *> new_vector;
2853 sem_item *first = c->members[0];
2854 new_vector.safe_push (first);
2856 unsigned class_split_first = (*it)->classes.length ();
2858 for (unsigned j = 1; j < c->members.length (); j++)
2860 sem_item *item = c->members[j];
2862 bool equals
2863 = in_wpa ? first->equals_wpa (item, m_symtab_node_map)
2864 : first->equals (item, m_symtab_node_map);
2866 if (equals)
2867 new_vector.safe_push (item);
2868 else
2870 bool integrated = false;
2872 for (unsigned k = class_split_first;
2873 k < (*it)->classes.length (); k++)
2875 sem_item *x = (*it)->classes[k]->members[0];
2876 bool equals
2877 = in_wpa ? x->equals_wpa (item, m_symtab_node_map)
2878 : x->equals (item, m_symtab_node_map);
2880 if (equals)
2882 integrated = true;
2883 add_item_to_class ((*it)->classes[k], item);
2885 break;
2889 if (!integrated)
2891 congruence_class *c
2892 = new congruence_class (class_id++);
2893 m_classes_count++;
2894 add_item_to_class (c, item);
2896 (*it)->classes.safe_push (c);
2901 // We replace newly created new_vector for the class we've just
2902 // splitted.
2903 c->members.release ();
2904 c->members.create (new_vector.length ());
2906 for (unsigned int j = 0; j < new_vector.length (); j++)
2907 add_item_to_class (c, new_vector[j]);
2912 checking_verify_classes ();
2915 /* Subdivide classes by address references that members of the class
2916 reference. Example can be a pair of functions that have an address
2917 taken from a function. If these addresses are different the class
2918 is split. */
2920 unsigned
2921 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2923 typedef hash_map <symbol_compare_hash, vec <sem_item *> > subdivide_hash_map;
2925 unsigned newly_created_classes = 0;
2927 for (hash_table <congruence_class_hash>::iterator it = m_classes.begin ();
2928 it != m_classes.end (); ++it)
2930 unsigned int class_count = (*it)->classes.length ();
2931 auto_vec<congruence_class *> new_classes;
2933 for (unsigned i = 0; i < class_count; i++)
2935 congruence_class *c = (*it)->classes[i];
2937 if (c->members.length() > 1)
2939 subdivide_hash_map split_map;
2941 for (unsigned j = 0; j < c->members.length (); j++)
2943 sem_item *source_node = c->members[j];
2945 symbol_compare_collection *collection
2946 = new symbol_compare_collection (source_node->node);
2948 bool existed;
2949 vec <sem_item *> *slot
2950 = &split_map.get_or_insert (collection, &existed);
2951 gcc_checking_assert (slot);
2953 slot->safe_push (source_node);
2955 if (existed)
2956 delete collection;
2959 /* If the map contains more than one key, we have to split
2960 the map appropriately. */
2961 if (split_map.elements () != 1)
2963 bool first_class = true;
2965 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2966 it2 != split_map.end (); ++it2)
2968 congruence_class *new_cls;
2969 new_cls = new congruence_class (class_id++);
2971 for (unsigned k = 0; k < (*it2).second.length (); k++)
2972 add_item_to_class (new_cls, (*it2).second[k]);
2974 worklist_push (new_cls);
2975 newly_created_classes++;
2977 if (first_class)
2979 (*it)->classes[i] = new_cls;
2980 first_class = false;
2982 else
2984 new_classes.safe_push (new_cls);
2985 m_classes_count++;
2990 /* Release memory. */
2991 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2992 it2 != split_map.end (); ++it2)
2994 delete (*it2).first;
2995 (*it2).second.release ();
3000 for (unsigned i = 0; i < new_classes.length (); i++)
3001 (*it)->classes.safe_push (new_classes[i]);
3004 return newly_created_classes;
3007 /* Verify congruence classes, if checking is enabled. */
3009 void
3010 sem_item_optimizer::checking_verify_classes (void)
3012 if (flag_checking)
3013 verify_classes ();
3016 /* Verify congruence classes. */
3018 void
3019 sem_item_optimizer::verify_classes (void)
3021 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3022 it != m_classes.end (); ++it)
3024 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3026 congruence_class *cls = (*it)->classes[i];
3028 gcc_assert (cls);
3029 gcc_assert (cls->members.length () > 0);
3031 for (unsigned int j = 0; j < cls->members.length (); j++)
3033 sem_item *item = cls->members[j];
3035 gcc_assert (item);
3036 gcc_assert (item->cls == cls);
3038 for (unsigned k = 0; k < item->usages.length (); k++)
3040 sem_usage_pair *usage = item->usages[k];
3041 gcc_assert (usage->item->index_in_class
3042 < usage->item->cls->members.length ());
3049 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3050 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3051 but unused argument. */
3053 bool
3054 sem_item_optimizer::release_split_map (congruence_class * const &,
3055 bitmap const &b, traverse_split_pair *)
3057 bitmap bmp = b;
3059 BITMAP_FREE (bmp);
3061 return true;
3064 /* Process split operation for a class given as pointer CLS_PTR,
3065 where bitmap B splits congruence class members. DATA is used
3066 as argument of split pair. */
3068 bool
3069 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
3070 bitmap const &b,
3071 traverse_split_pair *pair)
3073 sem_item_optimizer *optimizer = pair->optimizer;
3074 const congruence_class *splitter_cls = pair->cls;
3076 /* If counted bits are greater than zero and less than the number of members
3077 a group will be splitted. */
3078 unsigned popcount = bitmap_count_bits (b);
3080 if (popcount > 0 && popcount < cls->members.length ())
3082 auto_vec <congruence_class *, 2> newclasses;
3083 newclasses.quick_push (new congruence_class (class_id++));
3084 newclasses.quick_push (new congruence_class (class_id++));
3086 for (unsigned int i = 0; i < cls->members.length (); i++)
3088 int target = bitmap_bit_p (b, i);
3089 congruence_class *tc = newclasses[target];
3091 add_item_to_class (tc, cls->members[i]);
3094 if (flag_checking)
3096 for (unsigned int i = 0; i < 2; i++)
3097 gcc_assert (newclasses[i]->members.length ());
3100 if (splitter_cls == cls)
3101 optimizer->splitter_class_removed = true;
3103 /* Remove old class from worklist if presented. */
3104 bool in_worklist = cls->in_worklist;
3106 if (in_worklist)
3107 cls->in_worklist = false;
3109 congruence_class_group g;
3110 g.hash = cls->members[0]->get_hash ();
3111 g.type = cls->members[0]->type;
3113 congruence_class_group *slot = optimizer->m_classes.find (&g);
3115 for (unsigned int i = 0; i < slot->classes.length (); i++)
3116 if (slot->classes[i] == cls)
3118 slot->classes.ordered_remove (i);
3119 break;
3122 /* New class will be inserted and integrated to work list. */
3123 for (unsigned int i = 0; i < 2; i++)
3124 optimizer->add_class (newclasses[i]);
3126 /* Two classes replace one, so that increment just by one. */
3127 optimizer->m_classes_count++;
3129 /* If OLD class was presented in the worklist, we remove the class
3130 and replace it will both newly created classes. */
3131 if (in_worklist)
3132 for (unsigned int i = 0; i < 2; i++)
3133 optimizer->worklist_push (newclasses[i]);
3134 else /* Just smaller class is inserted. */
3136 unsigned int smaller_index
3137 = (newclasses[0]->members.length ()
3138 < newclasses[1]->members.length ()
3139 ? 0 : 1);
3140 optimizer->worklist_push (newclasses[smaller_index]);
3143 if (dump_file && (dump_flags & TDF_DETAILS))
3145 fprintf (dump_file, " congruence class splitted:\n");
3146 cls->dump (dump_file, 4);
3148 fprintf (dump_file, " newly created groups:\n");
3149 for (unsigned int i = 0; i < 2; i++)
3150 newclasses[i]->dump (dump_file, 4);
3153 /* Release class if not presented in work list. */
3154 if (!in_worklist)
3155 delete cls;
3159 return true;
3162 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3163 Bitmap stack BMSTACK is used for bitmap allocation. */
3165 void
3166 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
3167 unsigned int index)
3169 hash_map <congruence_class *, bitmap> split_map;
3171 for (unsigned int i = 0; i < cls->members.length (); i++)
3173 sem_item *item = cls->members[i];
3175 /* Iterate all usages that have INDEX as usage of the item. */
3176 for (unsigned int j = 0; j < item->usages.length (); j++)
3178 sem_usage_pair *usage = item->usages[j];
3180 if (usage->index != index)
3181 continue;
3183 bitmap *slot = split_map.get (usage->item->cls);
3184 bitmap b;
3186 if(!slot)
3188 b = BITMAP_ALLOC (&m_bmstack);
3189 split_map.put (usage->item->cls, b);
3191 else
3192 b = *slot;
3194 gcc_checking_assert (usage->item->cls);
3195 gcc_checking_assert (usage->item->index_in_class
3196 < usage->item->cls->members.length ());
3198 bitmap_set_bit (b, usage->item->index_in_class);
3202 traverse_split_pair pair;
3203 pair.optimizer = this;
3204 pair.cls = cls;
3206 splitter_class_removed = false;
3207 split_map.traverse <traverse_split_pair *,
3208 sem_item_optimizer::traverse_congruence_split> (&pair);
3210 /* Bitmap clean-up. */
3211 split_map.traverse <traverse_split_pair *,
3212 sem_item_optimizer::release_split_map> (NULL);
3215 /* Every usage of a congruence class CLS is a candidate that can split the
3216 collection of classes. Bitmap stack BMSTACK is used for bitmap
3217 allocation. */
3219 void
3220 sem_item_optimizer::do_congruence_step (congruence_class *cls)
3222 bitmap_iterator bi;
3223 unsigned int i;
3225 bitmap usage = BITMAP_ALLOC (&m_bmstack);
3227 for (unsigned int i = 0; i < cls->members.length (); i++)
3228 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
3230 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
3232 if (dump_file && (dump_flags & TDF_DETAILS))
3233 fprintf (dump_file, " processing congruence step for class: %u, "
3234 "index: %u\n", cls->id, i);
3236 do_congruence_step_for_index (cls, i);
3238 if (splitter_class_removed)
3239 break;
3242 BITMAP_FREE (usage);
3245 /* Adds a newly created congruence class CLS to worklist. */
3247 void
3248 sem_item_optimizer::worklist_push (congruence_class *cls)
3250 /* Return if the class CLS is already presented in work list. */
3251 if (cls->in_worklist)
3252 return;
3254 cls->in_worklist = true;
3255 worklist.push_back (cls);
3258 /* Pops a class from worklist. */
3260 congruence_class *
3261 sem_item_optimizer::worklist_pop (void)
3263 congruence_class *cls;
3265 while (!worklist.empty ())
3267 cls = worklist.front ();
3268 worklist.pop_front ();
3269 if (cls->in_worklist)
3271 cls->in_worklist = false;
3273 return cls;
3275 else
3277 /* Work list item was already intended to be removed.
3278 The only reason for doing it is to split a class.
3279 Thus, the class CLS is deleted. */
3280 delete cls;
3284 return NULL;
3287 /* Iterative congruence reduction function. */
3289 void
3290 sem_item_optimizer::process_cong_reduction (void)
3292 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3293 it != m_classes.end (); ++it)
3294 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3295 if ((*it)->classes[i]->is_class_used ())
3296 worklist_push ((*it)->classes[i]);
3298 if (dump_file)
3299 fprintf (dump_file, "Worklist has been filled with: %lu\n",
3300 (unsigned long) worklist.size ());
3302 if (dump_file && (dump_flags & TDF_DETAILS))
3303 fprintf (dump_file, "Congruence class reduction\n");
3305 congruence_class *cls;
3307 /* Process complete congruence reduction. */
3308 while ((cls = worklist_pop ()) != NULL)
3309 do_congruence_step (cls);
3311 /* Subdivide newly created classes according to references. */
3312 unsigned new_classes = subdivide_classes_by_sensitive_refs ();
3314 if (dump_file)
3315 fprintf (dump_file, "Address reference subdivision created: %u "
3316 "new classes.\n", new_classes);
3319 /* Debug function prints all informations about congruence classes. */
3321 void
3322 sem_item_optimizer::dump_cong_classes (void)
3324 if (!dump_file)
3325 return;
3327 fprintf (dump_file,
3328 "Congruence classes: %u (unique hash values: %lu), with total: "
3329 "%u items\n", m_classes_count,
3330 (unsigned long) m_classes.elements (), m_items.length ());
3332 /* Histogram calculation. */
3333 unsigned int max_index = 0;
3334 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
3336 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3337 it != m_classes.end (); ++it)
3338 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3340 unsigned int c = (*it)->classes[i]->members.length ();
3341 histogram[c]++;
3343 if (c > max_index)
3344 max_index = c;
3347 fprintf (dump_file,
3348 "Class size histogram [num of members]: number of classe number "
3349 "of classess\n");
3351 for (unsigned int i = 0; i <= max_index; i++)
3352 if (histogram[i])
3353 fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
3355 fprintf (dump_file, "\n\n");
3357 if (dump_flags & TDF_DETAILS)
3358 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3359 it != m_classes.end (); ++it)
3361 fprintf (dump_file, " group: with %u classes:\n",
3362 (*it)->classes.length ());
3364 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3366 (*it)->classes[i]->dump (dump_file, 4);
3368 if (i < (*it)->classes.length () - 1)
3369 fprintf (dump_file, " ");
3373 free (histogram);
3376 /* Sort pair of sem_items A and B by DECL_UID. */
3378 static int
3379 sort_sem_items_by_decl_uid (const void *a, const void *b)
3381 const sem_item *i1 = *(const sem_item * const *)a;
3382 const sem_item *i2 = *(const sem_item * const *)b;
3384 int uid1 = DECL_UID (i1->decl);
3385 int uid2 = DECL_UID (i2->decl);
3387 if (uid1 < uid2)
3388 return -1;
3389 else if (uid1 > uid2)
3390 return 1;
3391 else
3392 return 0;
3395 /* Sort pair of congruence_classes A and B by DECL_UID of the first member. */
3397 static int
3398 sort_congruence_classes_by_decl_uid (const void *a, const void *b)
3400 const congruence_class *c1 = *(const congruence_class * const *)a;
3401 const congruence_class *c2 = *(const congruence_class * const *)b;
3403 int uid1 = DECL_UID (c1->members[0]->decl);
3404 int uid2 = DECL_UID (c2->members[0]->decl);
3406 if (uid1 < uid2)
3407 return -1;
3408 else if (uid1 > uid2)
3409 return 1;
3410 else
3411 return 0;
3414 /* Sort pair of congruence_class_groups A and B by
3415 DECL_UID of the first member of a first group. */
3417 static int
3418 sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
3420 const congruence_class_group *g1
3421 = *(const congruence_class_group * const *)a;
3422 const congruence_class_group *g2
3423 = *(const congruence_class_group * const *)b;
3425 int uid1 = DECL_UID (g1->classes[0]->members[0]->decl);
3426 int uid2 = DECL_UID (g2->classes[0]->members[0]->decl);
3428 if (uid1 < uid2)
3429 return -1;
3430 else if (uid1 > uid2)
3431 return 1;
3432 else
3433 return 0;
3436 /* After reduction is done, we can declare all items in a group
3437 to be equal. PREV_CLASS_COUNT is start number of classes
3438 before reduction. True is returned if there's a merge operation
3439 processed. */
3441 bool
3442 sem_item_optimizer::merge_classes (unsigned int prev_class_count)
3444 unsigned int item_count = m_items.length ();
3445 unsigned int class_count = m_classes_count;
3446 unsigned int equal_items = item_count - class_count;
3448 unsigned int non_singular_classes_count = 0;
3449 unsigned int non_singular_classes_sum = 0;
3451 bool merged_p = false;
3453 /* PR lto/78211
3454 Sort functions in congruence classes by DECL_UID and do the same
3455 for the classes to not to break -fcompare-debug. */
3457 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3458 it != m_classes.end (); ++it)
3460 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3462 congruence_class *c = (*it)->classes[i];
3463 c->members.qsort (sort_sem_items_by_decl_uid);
3466 (*it)->classes.qsort (sort_congruence_classes_by_decl_uid);
3469 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3470 it != m_classes.end (); ++it)
3471 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3473 congruence_class *c = (*it)->classes[i];
3474 if (c->members.length () > 1)
3476 non_singular_classes_count++;
3477 non_singular_classes_sum += c->members.length ();
3481 auto_vec <congruence_class_group *> classes (m_classes.elements ());
3482 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3483 it != m_classes.end (); ++it)
3484 classes.quick_push (*it);
3486 classes.qsort (sort_congruence_class_groups_by_decl_uid);
3488 if (dump_file)
3490 fprintf (dump_file, "\nItem count: %u\n", item_count);
3491 fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
3492 prev_class_count, class_count);
3493 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
3494 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
3495 class_count ? 1.0f * item_count / class_count : 0.0f);
3496 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
3497 non_singular_classes_count ? 1.0f * non_singular_classes_sum /
3498 non_singular_classes_count : 0.0f,
3499 non_singular_classes_count);
3500 fprintf (dump_file, "Equal symbols: %u\n", equal_items);
3501 fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
3502 item_count ? 100.0f * equal_items / item_count : 0.0f);
3505 unsigned int l;
3506 congruence_class_group *it;
3507 FOR_EACH_VEC_ELT (classes, l, it)
3508 for (unsigned int i = 0; i < it->classes.length (); i++)
3510 congruence_class *c = it->classes[i];
3512 if (c->members.length () == 1)
3513 continue;
3515 sem_item *source = c->members[0];
3517 if (DECL_NAME (source->decl)
3518 && MAIN_NAME_P (DECL_NAME (source->decl)))
3519 /* If merge via wrappers, picking main as the target can be
3520 problematic. */
3521 source = c->members[1];
3523 for (unsigned int j = 0; j < c->members.length (); j++)
3525 sem_item *alias = c->members[j];
3527 if (alias == source)
3528 continue;
3530 if (dump_file)
3532 fprintf (dump_file, "Semantic equality hit:%s->%s\n",
3533 xstrdup_for_dump (source->node->name ()),
3534 xstrdup_for_dump (alias->node->name ()));
3535 fprintf (dump_file, "Assembler symbol names:%s->%s\n",
3536 xstrdup_for_dump (source->node->asm_name ()),
3537 xstrdup_for_dump (alias->node->asm_name ()));
3540 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl)))
3542 if (dump_file)
3543 fprintf (dump_file,
3544 "Merge operation is skipped due to no_icf "
3545 "attribute.\n\n");
3547 continue;
3550 if (dump_file && (dump_flags & TDF_DETAILS))
3552 source->dump_to_file (dump_file);
3553 alias->dump_to_file (dump_file);
3556 if (dbg_cnt (merged_ipa_icf))
3557 merged_p |= source->merge (alias);
3561 return merged_p;
3564 /* Dump function prints all class members to a FILE with an INDENT. */
3566 void
3567 congruence_class::dump (FILE *file, unsigned int indent) const
3569 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
3570 id, members[0]->get_hash (), members.length ());
3572 FPUTS_SPACES (file, indent + 2, "");
3573 for (unsigned i = 0; i < members.length (); i++)
3574 fprintf (file, "%s ", members[i]->node->dump_asm_name ());
3576 fprintf (file, "\n");
3579 /* Returns true if there's a member that is used from another group. */
3581 bool
3582 congruence_class::is_class_used (void)
3584 for (unsigned int i = 0; i < members.length (); i++)
3585 if (members[i]->usages.length ())
3586 return true;
3588 return false;
3591 /* Generate pass summary for IPA ICF pass. */
3593 static void
3594 ipa_icf_generate_summary (void)
3596 if (!optimizer)
3597 optimizer = new sem_item_optimizer ();
3599 optimizer->register_hooks ();
3600 optimizer->parse_funcs_and_vars ();
3603 /* Write pass summary for IPA ICF pass. */
3605 static void
3606 ipa_icf_write_summary (void)
3608 gcc_assert (optimizer);
3610 optimizer->write_summary ();
3613 /* Read pass summary for IPA ICF pass. */
3615 static void
3616 ipa_icf_read_summary (void)
3618 if (!optimizer)
3619 optimizer = new sem_item_optimizer ();
3621 optimizer->read_summary ();
3622 optimizer->register_hooks ();
3625 /* Semantic equality exection function. */
3627 static unsigned int
3628 ipa_icf_driver (void)
3630 gcc_assert (optimizer);
3632 bool merged_p = optimizer->execute ();
3634 delete optimizer;
3635 optimizer = NULL;
3637 return merged_p ? TODO_remove_functions : 0;
3640 const pass_data pass_data_ipa_icf =
3642 IPA_PASS, /* type */
3643 "icf", /* name */
3644 OPTGROUP_IPA, /* optinfo_flags */
3645 TV_IPA_ICF, /* tv_id */
3646 0, /* properties_required */
3647 0, /* properties_provided */
3648 0, /* properties_destroyed */
3649 0, /* todo_flags_start */
3650 0, /* todo_flags_finish */
3653 class pass_ipa_icf : public ipa_opt_pass_d
3655 public:
3656 pass_ipa_icf (gcc::context *ctxt)
3657 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
3658 ipa_icf_generate_summary, /* generate_summary */
3659 ipa_icf_write_summary, /* write_summary */
3660 ipa_icf_read_summary, /* read_summary */
3661 NULL, /*
3662 write_optimization_summary */
3663 NULL, /*
3664 read_optimization_summary */
3665 NULL, /* stmt_fixup */
3666 0, /* function_transform_todo_flags_start */
3667 NULL, /* function_transform */
3668 NULL) /* variable_transform */
3671 /* opt_pass methods: */
3672 virtual bool gate (function *)
3674 return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
3677 virtual unsigned int execute (function *)
3679 return ipa_icf_driver();
3681 }; // class pass_ipa_icf
3683 } // ipa_icf namespace
3685 ipa_opt_pass_d *
3686 make_pass_ipa_icf (gcc::context *ctxt)
3688 return new ipa_icf::pass_ipa_icf (ctxt);