Daily bump.
[official-gcc.git] / gcc / ipa-icf.c
blob4c1f25d08348e24bbc2fc6ce5f29b287ee045d5b
1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2021 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural Identical Code Folding for functions and
23 read-only variables.
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
28 In case of functions,
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
32 aliases if possible.
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
45 correspond.
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
54 #include "config.h"
55 #include "system.h"
56 #include "coretypes.h"
57 #include "backend.h"
58 #include "target.h"
59 #include "rtl.h"
60 #include "tree.h"
61 #include "gimple.h"
62 #include "alloc-pool.h"
63 #include "tree-pass.h"
64 #include "ssa.h"
65 #include "cgraph.h"
66 #include "coverage.h"
67 #include "gimple-pretty-print.h"
68 #include "data-streamer.h"
69 #include "tree-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 "tree-ssa-alias-compare.h"
83 #include "ipa-icf-gimple.h"
84 #include "fibonacci_heap.h"
85 #include "ipa-icf.h"
86 #include "stor-layout.h"
87 #include "dbgcnt.h"
88 #include "tree-vector-builder.h"
89 #include "symtab-thunks.h"
90 #include "alias.h"
91 #include "asan.h"
93 using namespace ipa_icf_gimple;
95 namespace ipa_icf {
97 /* Initialization and computation of symtab node hash, there data
98 are propagated later on. */
100 static sem_item_optimizer *optimizer = NULL;
102 /* Constructor. */
104 symbol_compare_collection::symbol_compare_collection (symtab_node *node)
106 m_references.create (0);
107 m_interposables.create (0);
109 ipa_ref *ref;
111 if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
112 return;
114 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
116 if (ref->address_matters_p ())
117 m_references.safe_push (ref->referred);
119 if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE)
121 if (ref->address_matters_p ())
122 m_references.safe_push (ref->referred);
123 else
124 m_interposables.safe_push (ref->referred);
128 if (is_a <cgraph_node *> (node))
130 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
132 for (cgraph_edge *e = cnode->callees; e; e = e->next_callee)
133 if (e->callee->get_availability () <= AVAIL_INTERPOSABLE)
134 m_interposables.safe_push (e->callee);
138 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
140 sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index)
141 : item (_item), index (_index)
145 sem_item::sem_item (sem_item_type _type, bitmap_obstack *stack)
146 : type (_type), referenced_by_count (0), m_hash (-1), m_hash_set (false)
148 setup (stack);
151 sem_item::sem_item (sem_item_type _type, symtab_node *_node,
152 bitmap_obstack *stack)
153 : type (_type), node (_node), referenced_by_count (0), m_hash (-1),
154 m_hash_set (false)
156 decl = node->decl;
157 setup (stack);
160 /* Add reference to a semantic TARGET. */
162 void
163 sem_item::add_reference (ref_map *refs,
164 sem_item *target)
166 unsigned index = reference_count++;
167 bool existed;
169 sem_usage_pair *pair = new sem_usage_pair (target, index);
170 vec<sem_item *> &v = refs->get_or_insert (pair, &existed);
171 if (existed)
172 delete pair;
174 v.safe_push (this);
175 bitmap_set_bit (target->usage_index_bitmap, index);
176 refs_set.add (target->node);
177 ++target->referenced_by_count;
180 /* Initialize internal data structures. Bitmap STACK is used for
181 bitmap memory allocation process. */
183 void
184 sem_item::setup (bitmap_obstack *stack)
186 gcc_checking_assert (node);
188 reference_count = 0;
189 tree_refs.create (0);
190 usage_index_bitmap = BITMAP_ALLOC (stack);
193 sem_item::~sem_item ()
195 tree_refs.release ();
197 BITMAP_FREE (usage_index_bitmap);
200 /* Dump function for debugging purpose. */
202 DEBUG_FUNCTION void
203 sem_item::dump (void)
205 if (dump_file)
207 fprintf (dump_file, "[%s] %s (tree:%p)\n", type == FUNC ? "func" : "var",
208 node->dump_name (), (void *) node->decl);
209 fprintf (dump_file, " hash: %u\n", get_hash ());
213 /* Return true if target supports alias symbols. */
215 bool
216 sem_item::target_supports_symbol_aliases_p (void)
218 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
219 return false;
220 #else
221 return true;
222 #endif
225 void sem_item::set_hash (hashval_t hash)
227 m_hash = hash;
228 m_hash_set = true;
231 hash_map<const_tree, hashval_t> sem_item::m_type_hash_cache;
233 /* Semantic function constructor that uses STACK as bitmap memory stack. */
235 sem_function::sem_function (bitmap_obstack *stack)
236 : sem_item (FUNC, stack), memory_access_types (), m_alias_sets_hash (0),
237 m_checker (NULL), m_compared_func (NULL)
239 bb_sizes.create (0);
240 bb_sorted.create (0);
243 sem_function::sem_function (cgraph_node *node, bitmap_obstack *stack)
244 : sem_item (FUNC, node, stack), memory_access_types (),
245 m_alias_sets_hash (0), m_checker (NULL), m_compared_func (NULL)
247 bb_sizes.create (0);
248 bb_sorted.create (0);
251 sem_function::~sem_function ()
253 for (unsigned i = 0; i < bb_sorted.length (); i++)
254 delete (bb_sorted[i]);
256 bb_sizes.release ();
257 bb_sorted.release ();
260 /* Calculates hash value based on a BASIC_BLOCK. */
262 hashval_t
263 sem_function::get_bb_hash (const sem_bb *basic_block)
265 inchash::hash hstate;
267 hstate.add_int (basic_block->nondbg_stmt_count);
268 hstate.add_int (basic_block->edge_count);
270 return hstate.end ();
273 /* References independent hash function. */
275 hashval_t
276 sem_function::get_hash (void)
278 if (!m_hash_set)
280 inchash::hash hstate;
281 hstate.add_int (177454); /* Random number for function type. */
283 hstate.add_int (arg_count);
284 hstate.add_int (cfg_checksum);
285 hstate.add_int (gcode_hash);
287 for (unsigned i = 0; i < bb_sorted.length (); i++)
288 hstate.merge_hash (get_bb_hash (bb_sorted[i]));
290 for (unsigned i = 0; i < bb_sizes.length (); i++)
291 hstate.add_int (bb_sizes[i]);
293 /* Add common features of declaration itself. */
294 if (DECL_FUNCTION_SPECIFIC_TARGET (decl))
295 hstate.add_hwi
296 (cl_target_option_hash
297 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl))));
298 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))
299 hstate.add_hwi
300 (cl_optimization_hash
301 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))));
302 hstate.add_flag (DECL_CXX_CONSTRUCTOR_P (decl));
303 hstate.add_flag (DECL_CXX_DESTRUCTOR_P (decl));
305 set_hash (hstate.end ());
308 return m_hash;
311 /* Compare properties of symbols N1 and N2 that does not affect semantics of
312 symbol itself but affects semantics of its references from USED_BY (which
313 may be NULL if it is unknown). If comparison is false, symbols
314 can still be merged but any symbols referring them can't.
316 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
318 TODO: We can also split attributes to those that determine codegen of
319 a function body/variable constructor itself and those that are used when
320 referring to it. */
322 bool
323 sem_item::compare_referenced_symbol_properties (symtab_node *used_by,
324 symtab_node *n1,
325 symtab_node *n2,
326 bool address)
328 if (is_a <cgraph_node *> (n1))
330 /* Inline properties matters: we do now want to merge uses of inline
331 function to uses of normal function because inline hint would be lost.
332 We however can merge inline function to noinline because the alias
333 will keep its DECL_DECLARED_INLINE flag.
335 Also ignore inline flag when optimizing for size or when function
336 is known to not be inlinable.
338 TODO: the optimize_size checks can also be assumed to be true if
339 unit has no !optimize_size functions. */
341 if ((!used_by || address || !is_a <cgraph_node *> (used_by)
342 || !opt_for_fn (used_by->decl, optimize_size))
343 && !opt_for_fn (n1->decl, optimize_size)
344 && n1->get_availability () > AVAIL_INTERPOSABLE
345 && (!DECL_UNINLINABLE (n1->decl) || !DECL_UNINLINABLE (n2->decl)))
347 if (DECL_DISREGARD_INLINE_LIMITS (n1->decl)
348 != DECL_DISREGARD_INLINE_LIMITS (n2->decl))
349 return return_false_with_msg
350 ("DECL_DISREGARD_INLINE_LIMITS are different");
352 if (DECL_DECLARED_INLINE_P (n1->decl)
353 != DECL_DECLARED_INLINE_P (n2->decl))
354 return return_false_with_msg ("inline attributes are different");
357 if (DECL_IS_OPERATOR_NEW_P (n1->decl)
358 != DECL_IS_OPERATOR_NEW_P (n2->decl))
359 return return_false_with_msg ("operator new flags are different");
361 if (DECL_IS_REPLACEABLE_OPERATOR (n1->decl)
362 != DECL_IS_REPLACEABLE_OPERATOR (n2->decl))
363 return return_false_with_msg ("replaceable operator flags are different");
366 /* Merging two definitions with a reference to equivalent vtables, but
367 belonging to a different type may result in ipa-polymorphic-call analysis
368 giving a wrong answer about the dynamic type of instance. */
369 if (is_a <varpool_node *> (n1))
371 if ((DECL_VIRTUAL_P (n1->decl) || DECL_VIRTUAL_P (n2->decl))
372 && (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl)
373 || !types_must_be_same_for_odr (DECL_CONTEXT (n1->decl),
374 DECL_CONTEXT (n2->decl)))
375 && (!used_by || !is_a <cgraph_node *> (used_by) || address
376 || opt_for_fn (used_by->decl, flag_devirtualize)))
377 return return_false_with_msg
378 ("references to virtual tables cannot be merged");
380 if (address && DECL_ALIGN (n1->decl) != DECL_ALIGN (n2->decl))
381 return return_false_with_msg ("alignment mismatch");
383 /* For functions we compare attributes in equals_wpa, because we do
384 not know what attributes may cause codegen differences, but for
385 variables just compare attributes for references - the codegen
386 for constructors is affected only by those attributes that we lower
387 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
388 if (!attribute_list_equal (DECL_ATTRIBUTES (n1->decl),
389 DECL_ATTRIBUTES (n2->decl)))
390 return return_false_with_msg ("different var decl attributes");
391 if (comp_type_attributes (TREE_TYPE (n1->decl),
392 TREE_TYPE (n2->decl)) != 1)
393 return return_false_with_msg ("different var type attributes");
396 /* When matching virtual tables, be sure to also match information
397 relevant for polymorphic call analysis. */
398 if (used_by && is_a <varpool_node *> (used_by)
399 && DECL_VIRTUAL_P (used_by->decl))
401 if (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl))
402 return return_false_with_msg ("virtual flag mismatch");
403 if (DECL_VIRTUAL_P (n1->decl) && is_a <cgraph_node *> (n1)
404 && (DECL_FINAL_P (n1->decl) != DECL_FINAL_P (n2->decl)))
405 return return_false_with_msg ("final flag mismatch");
407 return true;
410 /* Hash properties that are compared by compare_referenced_symbol_properties. */
412 void
413 sem_item::hash_referenced_symbol_properties (symtab_node *ref,
414 inchash::hash &hstate,
415 bool address)
417 if (is_a <cgraph_node *> (ref))
419 if ((type != FUNC || address || !opt_for_fn (decl, optimize_size))
420 && !opt_for_fn (ref->decl, optimize_size)
421 && !DECL_UNINLINABLE (ref->decl))
423 hstate.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref->decl));
424 hstate.add_flag (DECL_DECLARED_INLINE_P (ref->decl));
426 hstate.add_flag (DECL_IS_OPERATOR_NEW_P (ref->decl));
428 else if (is_a <varpool_node *> (ref))
430 hstate.add_flag (DECL_VIRTUAL_P (ref->decl));
431 if (address)
432 hstate.add_int (DECL_ALIGN (ref->decl));
437 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
438 point to a same function. Comparison can be skipped if IGNORED_NODES
439 contains these nodes. ADDRESS indicate if address is taken. */
441 bool
442 sem_item::compare_symbol_references (
443 hash_map <symtab_node *, sem_item *> &ignored_nodes,
444 symtab_node *n1, symtab_node *n2, bool address)
446 enum availability avail1, avail2;
448 if (n1 == n2)
449 return true;
451 /* Never match variable and function. */
452 if (is_a <varpool_node *> (n1) != is_a <varpool_node *> (n2))
453 return false;
455 if (!compare_referenced_symbol_properties (node, n1, n2, address))
456 return false;
457 if (address && n1->equal_address_to (n2) == 1)
458 return true;
459 if (!address && n1->semantically_equivalent_p (n2))
460 return true;
462 n1 = n1->ultimate_alias_target (&avail1);
463 n2 = n2->ultimate_alias_target (&avail2);
465 if (avail1 > AVAIL_INTERPOSABLE && ignored_nodes.get (n1)
466 && avail2 > AVAIL_INTERPOSABLE && ignored_nodes.get (n2))
467 return true;
469 return return_false_with_msg ("different references");
472 /* If cgraph edges E1 and E2 are indirect calls, verify that
473 ECF flags are the same. */
475 bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
477 if (e1->indirect_info && e2->indirect_info)
479 int e1_flags = e1->indirect_info->ecf_flags;
480 int e2_flags = e2->indirect_info->ecf_flags;
482 if (e1_flags != e2_flags)
483 return return_false_with_msg ("ICF flags are different");
485 else if (e1->indirect_info || e2->indirect_info)
486 return false;
488 return true;
491 /* Return true if parameter I may be used. */
493 bool
494 sem_function::param_used_p (unsigned int i)
496 if (ipa_node_params_sum == NULL)
497 return true;
499 ipa_node_params *parms_info = ipa_node_params_sum->get (get_node ());
501 if (!parms_info || vec_safe_length (parms_info->descriptors) <= i)
502 return true;
504 return ipa_is_param_used (parms_info, i);
507 /* Perform additional check needed to match types function parameters that are
508 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
509 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
511 bool
512 sem_function::compatible_parm_types_p (tree parm1, tree parm2)
514 /* Be sure that parameters are TBAA compatible. */
515 if (!func_checker::compatible_types_p (parm1, parm2))
516 return return_false_with_msg ("parameter type is not compatible");
518 if (POINTER_TYPE_P (parm1)
519 && (TYPE_RESTRICT (parm1) != TYPE_RESTRICT (parm2)))
520 return return_false_with_msg ("argument restrict flag mismatch");
522 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
523 if (POINTER_TYPE_P (parm1)
524 && TREE_CODE (parm1) != TREE_CODE (parm2)
525 && opt_for_fn (decl, flag_delete_null_pointer_checks))
526 return return_false_with_msg ("pointer wrt reference mismatch");
528 return true;
531 /* Fast equality function based on knowledge known in WPA. */
533 bool
534 sem_function::equals_wpa (sem_item *item,
535 hash_map <symtab_node *, sem_item *> &ignored_nodes)
537 gcc_assert (item->type == FUNC);
538 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
539 cgraph_node *cnode2 = dyn_cast <cgraph_node *> (item->node);
541 m_compared_func = static_cast<sem_function *> (item);
543 if (cnode->thunk != cnode2->thunk)
544 return return_false_with_msg ("thunk mismatch");
545 if (cnode->former_thunk_p () != cnode2->former_thunk_p ())
546 return return_false_with_msg ("former_thunk_p mismatch");
548 if ((cnode->thunk || cnode->former_thunk_p ())
549 && thunk_info::get (cnode) != thunk_info::get (cnode2))
550 return return_false_with_msg ("thunk_info mismatch");
552 /* Compare special function DECL attributes. */
553 if (DECL_FUNCTION_PERSONALITY (decl)
554 != DECL_FUNCTION_PERSONALITY (item->decl))
555 return return_false_with_msg ("function personalities are different");
557 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
558 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item->decl))
559 return return_false_with_msg ("instrument function entry exit "
560 "attributes are different");
562 if (DECL_NO_LIMIT_STACK (decl) != DECL_NO_LIMIT_STACK (item->decl))
563 return return_false_with_msg ("no stack limit attributes are different");
565 if (DECL_CXX_CONSTRUCTOR_P (decl) != DECL_CXX_CONSTRUCTOR_P (item->decl))
566 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
568 if (DECL_CXX_DESTRUCTOR_P (decl) != DECL_CXX_DESTRUCTOR_P (item->decl))
569 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
571 /* TODO: pure/const flags mostly matters only for references, except for
572 the fact that codegen takes LOOPING flag as a hint that loops are
573 finite. We may arrange the code to always pick leader that has least
574 specified flags and then this can go into comparing symbol properties. */
575 if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
576 return return_false_with_msg ("decl_or_type flags are different");
578 /* Do not match polymorphic constructors of different types. They calls
579 type memory location for ipa-polymorphic-call and we do not want
580 it to get confused by wrong type. */
581 if (DECL_CXX_CONSTRUCTOR_P (decl)
582 && opt_for_fn (decl, flag_devirtualize)
583 && TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE)
585 if (TREE_CODE (TREE_TYPE (item->decl)) != METHOD_TYPE)
586 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR type mismatch");
587 else if (!func_checker::compatible_polymorphic_types_p
588 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
589 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
590 return return_false_with_msg ("ctor polymorphic type mismatch");
593 /* Checking function TARGET and OPTIMIZATION flags. */
594 cl_target_option *tar1 = target_opts_for_fn (decl);
595 cl_target_option *tar2 = target_opts_for_fn (item->decl);
597 if (tar1 != tar2 && !cl_target_option_eq (tar1, tar2))
599 if (dump_file && (dump_flags & TDF_DETAILS))
601 fprintf (dump_file, "target flags difference");
602 cl_target_option_print_diff (dump_file, 2, tar1, tar2);
605 return return_false_with_msg ("Target flags are different");
608 cl_optimization *opt1 = opts_for_fn (decl);
609 cl_optimization *opt2 = opts_for_fn (item->decl);
611 if (opt1 != opt2 && !cl_optimization_option_eq (opt1, opt2))
613 if (dump_file && (dump_flags & TDF_DETAILS))
615 fprintf (dump_file, "optimization flags difference");
616 cl_optimization_print_diff (dump_file, 2, opt1, opt2);
619 return return_false_with_msg ("optimization flags are different");
622 /* Result type checking. */
623 if (!func_checker::compatible_types_p
624 (TREE_TYPE (TREE_TYPE (decl)),
625 TREE_TYPE (TREE_TYPE (m_compared_func->decl))))
626 return return_false_with_msg ("result types are different");
628 /* Checking types of arguments. */
629 tree list1 = TYPE_ARG_TYPES (TREE_TYPE (decl)),
630 list2 = TYPE_ARG_TYPES (TREE_TYPE (m_compared_func->decl));
631 for (unsigned i = 0; list1 && list2;
632 list1 = TREE_CHAIN (list1), list2 = TREE_CHAIN (list2), i++)
634 tree parm1 = TREE_VALUE (list1);
635 tree parm2 = TREE_VALUE (list2);
637 /* This guard is here for function pointer with attributes (pr59927.c). */
638 if (!parm1 || !parm2)
639 return return_false_with_msg ("NULL argument type");
641 /* Verify that types are compatible to ensure that both functions
642 have same calling conventions. */
643 if (!types_compatible_p (parm1, parm2))
644 return return_false_with_msg ("parameter types are not compatible");
646 if (!param_used_p (i))
647 continue;
649 /* Perform additional checks for used parameters. */
650 if (!compatible_parm_types_p (parm1, parm2))
651 return false;
654 if (list1 || list2)
655 return return_false_with_msg ("Mismatched number of parameters");
657 if (node->num_references () != item->node->num_references ())
658 return return_false_with_msg ("different number of references");
660 /* Checking function attributes.
661 This is quadratic in number of attributes */
662 if (comp_type_attributes (TREE_TYPE (decl),
663 TREE_TYPE (item->decl)) != 1)
664 return return_false_with_msg ("different type attributes");
665 if (!attribute_list_equal (DECL_ATTRIBUTES (decl),
666 DECL_ATTRIBUTES (item->decl)))
667 return return_false_with_msg ("different decl attributes");
669 /* The type of THIS pointer type memory location for
670 ipa-polymorphic-call-analysis. */
671 if (opt_for_fn (decl, flag_devirtualize)
672 && (TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE
673 || TREE_CODE (TREE_TYPE (item->decl)) == METHOD_TYPE)
674 && param_used_p (0)
675 && compare_polymorphic_p ())
677 if (TREE_CODE (TREE_TYPE (decl)) != TREE_CODE (TREE_TYPE (item->decl)))
678 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
679 if (!func_checker::compatible_polymorphic_types_p
680 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
681 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
682 return return_false_with_msg ("THIS pointer ODR type mismatch");
685 ipa_ref *ref = NULL, *ref2 = NULL;
686 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
688 item->node->iterate_reference (i, ref2);
690 if (ref->use != ref2->use)
691 return return_false_with_msg ("reference use mismatch");
693 if (!compare_symbol_references (ignored_nodes, ref->referred,
694 ref2->referred,
695 ref->address_matters_p ()))
696 return false;
699 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
700 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
702 while (e1 && e2)
704 if (!compare_symbol_references (ignored_nodes, e1->callee,
705 e2->callee, false))
706 return false;
707 if (!compare_edge_flags (e1, e2))
708 return false;
710 e1 = e1->next_callee;
711 e2 = e2->next_callee;
714 if (e1 || e2)
715 return return_false_with_msg ("different number of calls");
717 e1 = dyn_cast <cgraph_node *> (node)->indirect_calls;
718 e2 = dyn_cast <cgraph_node *> (item->node)->indirect_calls;
720 while (e1 && e2)
722 if (!compare_edge_flags (e1, e2))
723 return false;
725 e1 = e1->next_callee;
726 e2 = e2->next_callee;
729 if (e1 || e2)
730 return return_false_with_msg ("different number of indirect calls");
732 return true;
735 /* Update hash by address sensitive references. We iterate over all
736 sensitive references (address_matters_p) and we hash ultimate alias
737 target of these nodes, which can improve a semantic item hash.
739 Also hash in referenced symbols properties. This can be done at any time
740 (as the properties should not change), but it is convenient to do it here
741 while we walk the references anyway. */
743 void
744 sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
745 sem_item *> &m_symtab_node_map)
747 ipa_ref* ref;
748 inchash::hash hstate (get_hash ());
750 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
752 hstate.add_int (ref->use);
753 hash_referenced_symbol_properties (ref->referred, hstate,
754 ref->use == IPA_REF_ADDR);
755 if (ref->address_matters_p () || !m_symtab_node_map.get (ref->referred))
756 hstate.add_int (ref->referred->ultimate_alias_target ()->order);
759 if (is_a <cgraph_node *> (node))
761 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
762 e = e->next_caller)
764 sem_item **result = m_symtab_node_map.get (e->callee);
765 hash_referenced_symbol_properties (e->callee, hstate, false);
766 if (!result)
767 hstate.add_int (e->callee->ultimate_alias_target ()->order);
771 set_hash (hstate.end ());
774 /* Update hash by computed local hash values taken from different
775 semantic items.
776 TODO: stronger SCC based hashing would be desirable here. */
778 void
779 sem_item::update_hash_by_local_refs (hash_map <symtab_node *,
780 sem_item *> &m_symtab_node_map)
782 ipa_ref* ref;
783 inchash::hash state (get_hash ());
785 for (unsigned j = 0; node->iterate_reference (j, ref); j++)
787 sem_item **result = m_symtab_node_map.get (ref->referring);
788 if (result)
789 state.merge_hash ((*result)->get_hash ());
792 if (type == FUNC)
794 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e;
795 e = e->next_callee)
797 sem_item **result = m_symtab_node_map.get (e->caller);
798 if (result)
799 state.merge_hash ((*result)->get_hash ());
803 global_hash = state.end ();
806 /* Returns true if the item equals to ITEM given as argument. */
808 bool
809 sem_function::equals (sem_item *item,
810 hash_map <symtab_node *, sem_item *> &)
812 gcc_assert (item->type == FUNC);
813 bool eq = equals_private (item);
815 if (m_checker != NULL)
817 delete m_checker;
818 m_checker = NULL;
821 if (dump_file && (dump_flags & TDF_DETAILS))
822 fprintf (dump_file,
823 "Equals called for: %s:%s with result: %s\n\n",
824 node->dump_name (),
825 item->node->dump_name (),
826 eq ? "true" : "false");
828 return eq;
831 /* Processes function equality comparison. */
833 bool
834 sem_function::equals_private (sem_item *item)
836 if (item->type != FUNC)
837 return false;
839 basic_block bb1, bb2;
840 edge e1, e2;
841 edge_iterator ei1, ei2;
842 bool result = true;
843 tree arg1, arg2;
845 m_compared_func = static_cast<sem_function *> (item);
847 gcc_assert (decl != item->decl);
849 if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
850 || edge_count != m_compared_func->edge_count
851 || cfg_checksum != m_compared_func->cfg_checksum)
852 return return_false ();
854 m_checker = new func_checker (decl, m_compared_func->decl,
855 false,
856 opt_for_fn (m_compared_func->decl,
857 flag_strict_aliasing),
858 &refs_set,
859 &m_compared_func->refs_set);
860 arg1 = DECL_ARGUMENTS (decl);
861 arg2 = DECL_ARGUMENTS (m_compared_func->decl);
862 for (unsigned i = 0;
863 arg1 && arg2; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2), i++)
865 if (!types_compatible_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
866 return return_false_with_msg ("argument types are not compatible");
867 if (!param_used_p (i))
868 continue;
869 /* Perform additional checks for used parameters. */
870 if (!compatible_parm_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
871 return false;
872 if (!m_checker->compare_decl (arg1, arg2))
873 return return_false ();
875 if (arg1 || arg2)
876 return return_false_with_msg ("Mismatched number of arguments");
878 if (!dyn_cast <cgraph_node *> (node)->has_gimple_body_p ())
879 return true;
881 /* Fill-up label dictionary. */
882 for (unsigned i = 0; i < bb_sorted.length (); ++i)
884 m_checker->parse_labels (bb_sorted[i]);
885 m_checker->parse_labels (m_compared_func->bb_sorted[i]);
888 /* Checking all basic blocks. */
889 for (unsigned i = 0; i < bb_sorted.length (); ++i)
890 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
891 return return_false ();
893 auto_vec <int> bb_dict;
895 /* Basic block edges check. */
896 for (unsigned i = 0; i < bb_sorted.length (); ++i)
898 bb1 = bb_sorted[i]->bb;
899 bb2 = m_compared_func->bb_sorted[i]->bb;
901 ei2 = ei_start (bb2->preds);
903 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
905 ei_cond (ei2, &e2);
907 if (e1->flags != e2->flags)
908 return return_false_with_msg ("flags comparison returns false");
910 if (!bb_dict_test (&bb_dict, e1->src->index, e2->src->index))
911 return return_false_with_msg ("edge comparison returns false");
913 if (!bb_dict_test (&bb_dict, e1->dest->index, e2->dest->index))
914 return return_false_with_msg ("BB comparison returns false");
916 if (!m_checker->compare_edge (e1, e2))
917 return return_false_with_msg ("edge comparison returns false");
919 ei_next (&ei2);
923 /* Basic block PHI nodes comparison. */
924 for (unsigned i = 0; i < bb_sorted.length (); i++)
925 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
926 return return_false_with_msg ("PHI node comparison returns false");
928 return result;
931 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
932 Helper for call_for_symbol_thunks_and_aliases. */
934 static bool
935 set_local (cgraph_node *node, void *data)
937 node->local = data != NULL;
938 return false;
941 /* TREE_ADDRESSABLE of NODE to true.
942 Helper for call_for_symbol_thunks_and_aliases. */
944 static bool
945 set_addressable (varpool_node *node, void *)
947 TREE_ADDRESSABLE (node->decl) = 1;
948 return false;
951 /* Clear DECL_RTL of NODE.
952 Helper for call_for_symbol_thunks_and_aliases. */
954 static bool
955 clear_decl_rtl (symtab_node *node, void *)
957 SET_DECL_RTL (node->decl, NULL);
958 return false;
961 /* Redirect all callers of N and its aliases to TO. Remove aliases if
962 possible. Return number of redirections made. */
964 static int
965 redirect_all_callers (cgraph_node *n, cgraph_node *to)
967 int nredirected = 0;
968 ipa_ref *ref;
969 cgraph_edge *e = n->callers;
971 while (e)
973 /* Redirecting thunks to interposable symbols or symbols in other sections
974 may not be supported by target output code. Play safe for now and
975 punt on redirection. */
976 if (!e->caller->thunk)
978 struct cgraph_edge *nexte = e->next_caller;
979 e->redirect_callee (to);
980 e = nexte;
981 nredirected++;
983 else
984 e = e->next_callee;
986 for (unsigned i = 0; n->iterate_direct_aliases (i, ref);)
988 bool removed = false;
989 cgraph_node *n_alias = dyn_cast <cgraph_node *> (ref->referring);
991 if ((DECL_COMDAT_GROUP (n->decl)
992 && (DECL_COMDAT_GROUP (n->decl)
993 == DECL_COMDAT_GROUP (n_alias->decl)))
994 || (n_alias->get_availability () > AVAIL_INTERPOSABLE
995 && n->get_availability () > AVAIL_INTERPOSABLE))
997 nredirected += redirect_all_callers (n_alias, to);
998 if (n_alias->can_remove_if_no_direct_calls_p ()
999 && !n_alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1000 NULL, true)
1001 && !n_alias->has_aliases_p ())
1002 n_alias->remove ();
1004 if (!removed)
1005 i++;
1007 return nredirected;
1010 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1011 be applied. */
1013 bool
1014 sem_function::merge (sem_item *alias_item)
1016 gcc_assert (alias_item->type == FUNC);
1018 sem_function *alias_func = static_cast<sem_function *> (alias_item);
1020 cgraph_node *original = get_node ();
1021 cgraph_node *local_original = NULL;
1022 cgraph_node *alias = alias_func->get_node ();
1024 bool create_wrapper = false;
1025 bool create_alias = false;
1026 bool redirect_callers = false;
1027 bool remove = false;
1029 bool original_discardable = false;
1030 bool original_discarded = false;
1032 bool original_address_matters = original->address_matters_p ();
1033 bool alias_address_matters = alias->address_matters_p ();
1035 AUTO_DUMP_SCOPE ("merge",
1036 dump_user_location_t::from_function_decl (decl));
1038 if (DECL_EXTERNAL (alias->decl))
1040 if (dump_enabled_p ())
1041 dump_printf (MSG_MISSED_OPTIMIZATION,
1042 "Not unifying; alias is external.\n");
1043 return false;
1046 if (DECL_NO_INLINE_WARNING_P (original->decl)
1047 != DECL_NO_INLINE_WARNING_P (alias->decl))
1049 if (dump_enabled_p ())
1050 dump_printf (MSG_MISSED_OPTIMIZATION,
1051 "Not unifying; DECL_NO_INLINE_WARNING mismatch.\n");
1052 return false;
1055 /* Do not attempt to mix functions from different user sections;
1056 we do not know what user intends with those. */
1057 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
1058 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
1059 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
1061 if (dump_enabled_p ())
1062 dump_printf (MSG_MISSED_OPTIMIZATION,
1063 "Not unifying; "
1064 "original and alias are in different sections.\n");
1065 return false;
1068 if (!original->in_same_comdat_group_p (alias)
1069 || original->comdat_local_p ())
1071 if (dump_enabled_p ())
1072 dump_printf (MSG_MISSED_OPTIMIZATION,
1073 "Not unifying; alias nor wrapper cannot be created; "
1074 "across comdat group boundary\n");
1075 return false;
1078 /* See if original is in a section that can be discarded if the main
1079 symbol is not used. */
1081 if (original->can_be_discarded_p ())
1082 original_discardable = true;
1083 /* Also consider case where we have resolution info and we know that
1084 original's definition is not going to be used. In this case we cannot
1085 create alias to original. */
1086 if (node->resolution != LDPR_UNKNOWN
1087 && !decl_binds_to_current_def_p (node->decl))
1088 original_discardable = original_discarded = true;
1090 /* Creating a symtab alias is the optimal way to merge.
1091 It however cannot be used in the following cases:
1093 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1094 2) if ORIGINAL is in a section that may be discarded by linker or if
1095 it is an external functions where we cannot create an alias
1096 (ORIGINAL_DISCARDABLE)
1097 3) if target do not support symbol aliases.
1098 4) original and alias lie in different comdat groups.
1100 If we cannot produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1101 and/or redirect all callers from ALIAS to ORIGINAL. */
1102 if ((original_address_matters && alias_address_matters)
1103 || (original_discardable
1104 && (!DECL_COMDAT_GROUP (alias->decl)
1105 || (DECL_COMDAT_GROUP (alias->decl)
1106 != DECL_COMDAT_GROUP (original->decl))))
1107 || original_discarded
1108 || !sem_item::target_supports_symbol_aliases_p ()
1109 || DECL_COMDAT_GROUP (alias->decl) != DECL_COMDAT_GROUP (original->decl))
1111 /* First see if we can produce wrapper. */
1113 /* Symbol properties that matter for references must be preserved.
1114 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1115 with proper properties. */
1116 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1117 alias->address_taken))
1119 if (dump_enabled_p ())
1120 dump_printf (MSG_MISSED_OPTIMIZATION,
1121 "Wrapper cannot be created because referenced symbol "
1122 "properties mismatch\n");
1124 /* Do not turn function in one comdat group into wrapper to another
1125 comdat group. Other compiler producing the body of the
1126 another comdat group may make opposite decision and with unfortunate
1127 linker choices this may close a loop. */
1128 else if (DECL_COMDAT_GROUP (original->decl)
1129 && DECL_COMDAT_GROUP (alias->decl)
1130 && (DECL_COMDAT_GROUP (alias->decl)
1131 != DECL_COMDAT_GROUP (original->decl)))
1133 if (dump_enabled_p ())
1134 dump_printf (MSG_MISSED_OPTIMIZATION,
1135 "Wrapper cannot be created because of COMDAT\n");
1137 else if (DECL_STATIC_CHAIN (alias->decl)
1138 || DECL_STATIC_CHAIN (original->decl))
1140 if (dump_enabled_p ())
1141 dump_printf (MSG_MISSED_OPTIMIZATION,
1142 "Cannot create wrapper of nested function.\n");
1144 /* TODO: We can also deal with variadic functions never calling
1145 VA_START. */
1146 else if (stdarg_p (TREE_TYPE (alias->decl)))
1148 if (dump_enabled_p ())
1149 dump_printf (MSG_MISSED_OPTIMIZATION,
1150 "cannot create wrapper of stdarg function.\n");
1152 else if (ipa_fn_summaries
1153 && ipa_size_summaries->get (alias) != NULL
1154 && ipa_size_summaries->get (alias)->self_size <= 2)
1156 if (dump_enabled_p ())
1157 dump_printf (MSG_MISSED_OPTIMIZATION, "Wrapper creation is not "
1158 "profitable (function is too small).\n");
1160 /* If user paid attention to mark function noinline, assume it is
1161 somewhat special and do not try to turn it into a wrapper that
1162 cannot be undone by inliner. */
1163 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
1165 if (dump_enabled_p ())
1166 dump_printf (MSG_MISSED_OPTIMIZATION,
1167 "Wrappers are not created for noinline.\n");
1169 else
1170 create_wrapper = true;
1172 /* We can redirect local calls in the case both alias and original
1173 are not interposable. */
1174 redirect_callers
1175 = alias->get_availability () > AVAIL_INTERPOSABLE
1176 && original->get_availability () > AVAIL_INTERPOSABLE;
1177 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1178 with proper properties. */
1179 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1180 alias->address_taken))
1181 redirect_callers = false;
1183 if (!redirect_callers && !create_wrapper)
1185 if (dump_enabled_p ())
1186 dump_printf (MSG_MISSED_OPTIMIZATION,
1187 "Not unifying; cannot redirect callers nor "
1188 "produce wrapper\n");
1189 return false;
1192 /* Work out the symbol the wrapper should call.
1193 If ORIGINAL is interposable, we need to call a local alias.
1194 Also produce local alias (if possible) as an optimization.
1196 Local aliases cannot be created inside comdat groups because that
1197 prevents inlining. */
1198 if (!original_discardable && !original->get_comdat_group ())
1200 local_original
1201 = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
1202 if (!local_original
1203 && original->get_availability () > AVAIL_INTERPOSABLE)
1204 local_original = original;
1206 /* If we cannot use local alias, fallback to the original
1207 when possible. */
1208 else if (original->get_availability () > AVAIL_INTERPOSABLE)
1209 local_original = original;
1211 /* If original is COMDAT local, we cannot really redirect calls outside
1212 of its comdat group to it. */
1213 if (original->comdat_local_p ())
1214 redirect_callers = false;
1215 if (!local_original)
1217 if (dump_enabled_p ())
1218 dump_printf (MSG_MISSED_OPTIMIZATION,
1219 "Not unifying; cannot produce local alias.\n");
1220 return false;
1223 if (!redirect_callers && !create_wrapper)
1225 if (dump_enabled_p ())
1226 dump_printf (MSG_MISSED_OPTIMIZATION,
1227 "Not unifying; "
1228 "cannot redirect callers nor produce a wrapper\n");
1229 return false;
1231 if (!create_wrapper
1232 && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1233 NULL, true)
1234 && !alias->can_remove_if_no_direct_calls_p ())
1236 if (dump_enabled_p ())
1237 dump_printf (MSG_MISSED_OPTIMIZATION,
1238 "Not unifying; cannot make wrapper and "
1239 "function has other uses than direct calls\n");
1240 return false;
1243 else
1244 create_alias = true;
1246 if (redirect_callers)
1248 int nredirected = redirect_all_callers (alias, local_original);
1250 if (nredirected)
1252 alias->icf_merged = true;
1253 local_original->icf_merged = true;
1255 if (dump_enabled_p ())
1256 dump_printf (MSG_NOTE,
1257 "%i local calls have been "
1258 "redirected.\n", nredirected);
1261 /* If all callers was redirected, do not produce wrapper. */
1262 if (alias->can_remove_if_no_direct_calls_p ()
1263 && !DECL_VIRTUAL_P (alias->decl)
1264 && !alias->has_aliases_p ())
1266 create_wrapper = false;
1267 remove = true;
1269 gcc_assert (!create_alias);
1271 else if (create_alias)
1273 alias->icf_merged = true;
1275 /* Remove the function's body. */
1276 ipa_merge_profiles (original, alias);
1277 symtab->call_cgraph_removal_hooks (alias);
1278 alias->release_body (true);
1279 alias->reset ();
1280 /* Notice global symbol possibly produced RTL. */
1281 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
1282 NULL, true);
1284 /* Create the alias. */
1285 cgraph_node::create_alias (alias_func->decl, decl);
1286 alias->resolve_alias (original);
1288 original->call_for_symbol_thunks_and_aliases
1289 (set_local, (void *)(size_t) original->local_p (), true);
1291 if (dump_enabled_p ())
1292 dump_printf (MSG_OPTIMIZED_LOCATIONS,
1293 "Unified; Function alias has been created.\n");
1295 if (create_wrapper)
1297 gcc_assert (!create_alias);
1298 alias->icf_merged = true;
1299 symtab->call_cgraph_removal_hooks (alias);
1300 local_original->icf_merged = true;
1302 /* FIXME update local_original counts. */
1303 ipa_merge_profiles (original, alias, true);
1304 alias->create_wrapper (local_original);
1305 symtab->call_cgraph_insertion_hooks (alias);
1307 if (dump_enabled_p ())
1308 dump_printf (MSG_OPTIMIZED_LOCATIONS,
1309 "Unified; Wrapper has been created.\n");
1312 /* It's possible that redirection can hit thunks that block
1313 redirection opportunities. */
1314 gcc_assert (alias->icf_merged || remove || redirect_callers);
1315 original->icf_merged = true;
1317 /* We use merged flag to track cases where COMDAT function is known to be
1318 compatible its callers. If we merged in non-COMDAT, we need to give up
1319 on this optimization. */
1320 if (original->merged_comdat && !alias->merged_comdat)
1322 if (dump_enabled_p ())
1323 dump_printf (MSG_NOTE, "Dropping merged_comdat flag.\n");
1324 if (local_original)
1325 local_original->merged_comdat = false;
1326 original->merged_comdat = false;
1329 if (remove)
1331 ipa_merge_profiles (original, alias);
1332 alias->release_body ();
1333 alias->reset ();
1334 alias->body_removed = true;
1335 alias->icf_merged = true;
1336 if (dump_enabled_p ())
1337 dump_printf (MSG_OPTIMIZED_LOCATIONS,
1338 "Unified; Function body was removed.\n");
1341 return true;
1344 /* Semantic item initialization function. */
1346 void
1347 sem_function::init (ipa_icf_gimple::func_checker *checker)
1349 m_checker = checker;
1350 if (in_lto_p)
1351 get_node ()->get_untransformed_body ();
1353 tree fndecl = node->decl;
1354 function *func = DECL_STRUCT_FUNCTION (fndecl);
1356 gcc_assert (func);
1357 gcc_assert (SSANAMES (func));
1359 ssa_names_size = SSANAMES (func)->length ();
1360 node = node;
1362 decl = fndecl;
1363 region_tree = func->eh->region_tree;
1365 /* iterating all function arguments. */
1366 arg_count = count_formal_params (fndecl);
1368 edge_count = n_edges_for_fn (func);
1369 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1370 if (!cnode->thunk)
1372 cfg_checksum = coverage_compute_cfg_checksum (func);
1374 inchash::hash hstate;
1376 basic_block bb;
1377 FOR_EACH_BB_FN (bb, func)
1379 unsigned nondbg_stmt_count = 0;
1381 edge e;
1382 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
1383 ei_next (&ei))
1384 cfg_checksum = iterative_hash_host_wide_int (e->flags,
1385 cfg_checksum);
1387 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1388 gsi_next (&gsi))
1390 gimple *stmt = gsi_stmt (gsi);
1392 if (gimple_code (stmt) != GIMPLE_DEBUG
1393 && gimple_code (stmt) != GIMPLE_PREDICT)
1395 hash_stmt (stmt, hstate);
1396 nondbg_stmt_count++;
1400 hstate.commit_flag ();
1401 gcode_hash = hstate.end ();
1402 bb_sizes.safe_push (nondbg_stmt_count);
1404 /* Inserting basic block to hash table. */
1405 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
1406 EDGE_COUNT (bb->preds)
1407 + EDGE_COUNT (bb->succs));
1409 bb_sorted.safe_push (semantic_bb);
1412 else
1414 cfg_checksum = 0;
1415 gcode_hash = thunk_info::get (cnode)->hash ();
1418 m_checker = NULL;
1421 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1423 void
1424 sem_function::hash_stmt (gimple *stmt, inchash::hash &hstate)
1426 enum gimple_code code = gimple_code (stmt);
1428 hstate.add_int (code);
1430 switch (code)
1432 case GIMPLE_SWITCH:
1433 m_checker->hash_operand (gimple_switch_index (as_a <gswitch *> (stmt)),
1434 hstate, 0, func_checker::OP_NORMAL);
1435 break;
1436 case GIMPLE_ASSIGN:
1437 hstate.add_int (gimple_assign_rhs_code (stmt));
1438 /* fall through */
1439 case GIMPLE_CALL:
1440 case GIMPLE_ASM:
1441 case GIMPLE_COND:
1442 case GIMPLE_GOTO:
1443 case GIMPLE_RETURN:
1445 func_checker::operand_access_type_map map (5);
1446 func_checker::classify_operands (stmt, &map);
1448 /* All these statements are equivalent if their operands are. */
1449 for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1451 func_checker::operand_access_type
1452 access_type = func_checker::get_operand_access_type
1453 (&map, gimple_op (stmt, i));
1454 m_checker->hash_operand (gimple_op (stmt, i), hstate, 0,
1455 access_type);
1456 /* For memory accesses when hasing for LTO stremaing record
1457 base and ref alias ptr types so we can compare them at WPA
1458 time without having to read actual function body. */
1459 if (access_type == func_checker::OP_MEMORY
1460 && lto_streaming_expected_p ()
1461 && flag_strict_aliasing)
1463 ao_ref ref;
1465 ao_ref_init (&ref, gimple_op (stmt, i));
1466 tree t = ao_ref_alias_ptr_type (&ref);
1467 if (!variably_modified_type_p (t, NULL_TREE))
1468 memory_access_types.safe_push (t);
1469 t = ao_ref_base_alias_ptr_type (&ref);
1470 if (!variably_modified_type_p (t, NULL_TREE))
1471 memory_access_types.safe_push (t);
1474 /* Consider nocf_check attribute in hash as it affects code
1475 generation. */
1476 if (code == GIMPLE_CALL
1477 && flag_cf_protection & CF_BRANCH)
1478 hstate.add_flag (gimple_call_nocf_check_p (as_a <gcall *> (stmt)));
1480 break;
1481 default:
1482 break;
1487 /* Return true if polymorphic comparison must be processed. */
1489 bool
1490 sem_function::compare_polymorphic_p (void)
1492 struct cgraph_edge *e;
1494 if (!opt_for_fn (get_node ()->decl, flag_devirtualize))
1495 return false;
1496 if (get_node ()->indirect_calls != NULL)
1497 return true;
1498 /* TODO: We can do simple propagation determining what calls may lead to
1499 a polymorphic call. */
1500 for (e = get_node ()->callees; e; e = e->next_callee)
1501 if (e->callee->definition
1502 && opt_for_fn (e->callee->decl, flag_devirtualize))
1503 return true;
1504 return false;
1507 /* For a given call graph NODE, the function constructs new
1508 semantic function item. */
1510 sem_function *
1511 sem_function::parse (cgraph_node *node, bitmap_obstack *stack,
1512 func_checker *checker)
1514 tree fndecl = node->decl;
1515 function *func = DECL_STRUCT_FUNCTION (fndecl);
1517 if (!func || (!node->has_gimple_body_p () && !node->thunk))
1518 return NULL;
1520 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
1521 return NULL;
1523 if (lookup_attribute_by_prefix ("oacc ",
1524 DECL_ATTRIBUTES (node->decl)) != NULL)
1525 return NULL;
1527 /* PR ipa/70306. */
1528 if (DECL_STATIC_CONSTRUCTOR (node->decl)
1529 || DECL_STATIC_DESTRUCTOR (node->decl))
1530 return NULL;
1532 sem_function *f = new sem_function (node, stack);
1533 f->init (checker);
1535 return f;
1538 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1539 return true if phi nodes are semantically equivalent in these blocks . */
1541 bool
1542 sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
1544 gphi_iterator si1, si2;
1545 gphi *phi1, *phi2;
1546 unsigned size1, size2, i;
1547 tree t1, t2;
1548 edge e1, e2;
1550 gcc_assert (bb1 != NULL);
1551 gcc_assert (bb2 != NULL);
1553 si2 = gsi_start_nonvirtual_phis (bb2);
1554 for (si1 = gsi_start_nonvirtual_phis (bb1); !gsi_end_p (si1);
1555 gsi_next_nonvirtual_phi (&si1))
1557 if (gsi_end_p (si1) && gsi_end_p (si2))
1558 break;
1560 if (gsi_end_p (si1) || gsi_end_p (si2))
1561 return return_false();
1563 phi1 = si1.phi ();
1564 phi2 = si2.phi ();
1566 tree phi_result1 = gimple_phi_result (phi1);
1567 tree phi_result2 = gimple_phi_result (phi2);
1569 if (!m_checker->compare_operand (phi_result1, phi_result2,
1570 func_checker::OP_NORMAL))
1571 return return_false_with_msg ("PHI results are different");
1573 size1 = gimple_phi_num_args (phi1);
1574 size2 = gimple_phi_num_args (phi2);
1576 if (size1 != size2)
1577 return return_false ();
1579 for (i = 0; i < size1; ++i)
1581 t1 = gimple_phi_arg (phi1, i)->def;
1582 t2 = gimple_phi_arg (phi2, i)->def;
1584 if (!m_checker->compare_operand (t1, t2, func_checker::OP_NORMAL))
1585 return return_false ();
1587 e1 = gimple_phi_arg_edge (phi1, i);
1588 e2 = gimple_phi_arg_edge (phi2, i);
1590 if (!m_checker->compare_edge (e1, e2))
1591 return return_false ();
1594 gsi_next_nonvirtual_phi (&si2);
1597 return true;
1600 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1601 corresponds to TARGET. */
1603 bool
1604 sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
1606 source++;
1607 target++;
1609 if (bb_dict->length () <= (unsigned)source)
1610 bb_dict->safe_grow_cleared (source + 1, true);
1612 if ((*bb_dict)[source] == 0)
1614 (*bb_dict)[source] = target;
1615 return true;
1617 else
1618 return (*bb_dict)[source] == target;
1621 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
1625 sem_variable::sem_variable (varpool_node *node, bitmap_obstack *stack)
1626 : sem_item (VAR, node, stack)
1628 gcc_checking_assert (node);
1629 gcc_checking_assert (get_node ());
1632 /* Fast equality function based on knowledge known in WPA. */
1634 bool
1635 sem_variable::equals_wpa (sem_item *item,
1636 hash_map <symtab_node *, sem_item *> &ignored_nodes)
1638 gcc_assert (item->type == VAR);
1640 if (node->num_references () != item->node->num_references ())
1641 return return_false_with_msg ("different number of references");
1643 if (DECL_TLS_MODEL (decl) || DECL_TLS_MODEL (item->decl))
1644 return return_false_with_msg ("TLS model");
1646 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1647 alignment out of all aliases. */
1649 if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
1650 return return_false_with_msg ("Virtual flag mismatch");
1652 if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
1653 && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
1654 || !operand_equal_p (DECL_SIZE (decl),
1655 DECL_SIZE (item->decl), OEP_ONLY_CONST)))
1656 return return_false_with_msg ("size mismatch");
1658 /* Do not attempt to mix data from different user sections;
1659 we do not know what user intends with those. */
1660 if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
1661 || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
1662 && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
1663 return return_false_with_msg ("user section mismatch");
1665 if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
1666 return return_false_with_msg ("text section");
1668 ipa_ref *ref = NULL, *ref2 = NULL;
1669 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
1671 item->node->iterate_reference (i, ref2);
1673 if (ref->use != ref2->use)
1674 return return_false_with_msg ("reference use mismatch");
1676 if (!compare_symbol_references (ignored_nodes,
1677 ref->referred, ref2->referred,
1678 ref->address_matters_p ()))
1679 return false;
1682 return true;
1685 /* Returns true if the item equals to ITEM given as argument. */
1687 bool
1688 sem_variable::equals (sem_item *item,
1689 hash_map <symtab_node *, sem_item *> &)
1691 gcc_assert (item->type == VAR);
1692 bool ret;
1694 if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
1695 dyn_cast <varpool_node *>(node)->get_constructor ();
1696 if (DECL_INITIAL (item->decl) == error_mark_node && in_lto_p)
1697 dyn_cast <varpool_node *>(item->node)->get_constructor ();
1699 /* As seen in PR ipa/65303 we have to compare variables types. */
1700 if (!func_checker::compatible_types_p (TREE_TYPE (decl),
1701 TREE_TYPE (item->decl)))
1702 return return_false_with_msg ("variables types are different");
1704 ret = sem_variable::equals (DECL_INITIAL (decl),
1705 DECL_INITIAL (item->node->decl));
1706 if (dump_file && (dump_flags & TDF_DETAILS))
1707 fprintf (dump_file,
1708 "Equals called for vars: %s:%s with result: %s\n\n",
1709 node->dump_name (), item->node->dump_name (),
1710 ret ? "true" : "false");
1712 return ret;
1715 /* Compares trees T1 and T2 for semantic equality. */
1717 bool
1718 sem_variable::equals (tree t1, tree t2)
1720 if (!t1 || !t2)
1721 return return_with_debug (t1 == t2);
1722 if (t1 == t2)
1723 return true;
1724 tree_code tc1 = TREE_CODE (t1);
1725 tree_code tc2 = TREE_CODE (t2);
1727 if (tc1 != tc2)
1728 return return_false_with_msg ("TREE_CODE mismatch");
1730 switch (tc1)
1732 case CONSTRUCTOR:
1734 vec<constructor_elt, va_gc> *v1, *v2;
1735 unsigned HOST_WIDE_INT idx;
1737 enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
1738 if (typecode != TREE_CODE (TREE_TYPE (t2)))
1739 return return_false_with_msg ("constructor type mismatch");
1741 if (typecode == ARRAY_TYPE)
1743 HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
1744 /* For arrays, check that the sizes all match. */
1745 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
1746 || size_1 == -1
1747 || size_1 != int_size_in_bytes (TREE_TYPE (t2)))
1748 return return_false_with_msg ("constructor array size mismatch");
1750 else if (!func_checker::compatible_types_p (TREE_TYPE (t1),
1751 TREE_TYPE (t2)))
1752 return return_false_with_msg ("constructor type incompatible");
1754 v1 = CONSTRUCTOR_ELTS (t1);
1755 v2 = CONSTRUCTOR_ELTS (t2);
1756 if (vec_safe_length (v1) != vec_safe_length (v2))
1757 return return_false_with_msg ("constructor number of elts mismatch");
1759 for (idx = 0; idx < vec_safe_length (v1); ++idx)
1761 constructor_elt *c1 = &(*v1)[idx];
1762 constructor_elt *c2 = &(*v2)[idx];
1764 /* Check that each value is the same... */
1765 if (!sem_variable::equals (c1->value, c2->value))
1766 return false;
1767 /* ... and that they apply to the same fields! */
1768 if (!sem_variable::equals (c1->index, c2->index))
1769 return false;
1771 return true;
1773 case MEM_REF:
1775 tree x1 = TREE_OPERAND (t1, 0);
1776 tree x2 = TREE_OPERAND (t2, 0);
1777 tree y1 = TREE_OPERAND (t1, 1);
1778 tree y2 = TREE_OPERAND (t2, 1);
1780 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
1781 return return_false ();
1783 /* Type of the offset on MEM_REF does not matter. */
1784 return return_with_debug (sem_variable::equals (x1, x2)
1785 && known_eq (wi::to_poly_offset (y1),
1786 wi::to_poly_offset (y2)));
1788 case ADDR_EXPR:
1789 case FDESC_EXPR:
1791 tree op1 = TREE_OPERAND (t1, 0);
1792 tree op2 = TREE_OPERAND (t2, 0);
1793 return sem_variable::equals (op1, op2);
1795 /* References to other vars/decls are compared using ipa-ref. */
1796 case FUNCTION_DECL:
1797 case VAR_DECL:
1798 if (decl_in_symtab_p (t1) && decl_in_symtab_p (t2))
1799 return true;
1800 return return_false_with_msg ("Declaration mismatch");
1801 case CONST_DECL:
1802 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1803 need to process its VAR/FUNCTION references without relying on ipa-ref
1804 compare. */
1805 case FIELD_DECL:
1806 case LABEL_DECL:
1807 return return_false_with_msg ("Declaration mismatch");
1808 case INTEGER_CST:
1809 /* Integer constants are the same only if the same width of type. */
1810 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1811 return return_false_with_msg ("INTEGER_CST precision mismatch");
1812 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1813 return return_false_with_msg ("INTEGER_CST mode mismatch");
1814 return return_with_debug (tree_int_cst_equal (t1, t2));
1815 case STRING_CST:
1816 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1817 return return_false_with_msg ("STRING_CST mode mismatch");
1818 if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
1819 return return_false_with_msg ("STRING_CST length mismatch");
1820 if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
1821 TREE_STRING_LENGTH (t1)))
1822 return return_false_with_msg ("STRING_CST mismatch");
1823 return true;
1824 case FIXED_CST:
1825 /* Fixed constants are the same only if the same width of type. */
1826 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1827 return return_false_with_msg ("FIXED_CST precision mismatch");
1829 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
1830 TREE_FIXED_CST (t2)));
1831 case COMPLEX_CST:
1832 return (sem_variable::equals (TREE_REALPART (t1), TREE_REALPART (t2))
1833 && sem_variable::equals (TREE_IMAGPART (t1), TREE_IMAGPART (t2)));
1834 case REAL_CST:
1835 /* Real constants are the same only if the same width of type. */
1836 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1837 return return_false_with_msg ("REAL_CST precision mismatch");
1838 return return_with_debug (real_identical (&TREE_REAL_CST (t1),
1839 &TREE_REAL_CST (t2)));
1840 case VECTOR_CST:
1842 if (maybe_ne (VECTOR_CST_NELTS (t1), VECTOR_CST_NELTS (t2)))
1843 return return_false_with_msg ("VECTOR_CST nelts mismatch");
1845 unsigned int count
1846 = tree_vector_builder::binary_encoded_nelts (t1, t2);
1847 for (unsigned int i = 0; i < count; ++i)
1848 if (!sem_variable::equals (VECTOR_CST_ENCODED_ELT (t1, i),
1849 VECTOR_CST_ENCODED_ELT (t2, i)))
1850 return false;
1852 return true;
1854 case ARRAY_REF:
1855 case ARRAY_RANGE_REF:
1857 tree x1 = TREE_OPERAND (t1, 0);
1858 tree x2 = TREE_OPERAND (t2, 0);
1859 tree y1 = TREE_OPERAND (t1, 1);
1860 tree y2 = TREE_OPERAND (t2, 1);
1862 if (!sem_variable::equals (x1, x2) || !sem_variable::equals (y1, y2))
1863 return false;
1864 if (!sem_variable::equals (array_ref_low_bound (t1),
1865 array_ref_low_bound (t2)))
1866 return false;
1867 if (!sem_variable::equals (array_ref_element_size (t1),
1868 array_ref_element_size (t2)))
1869 return false;
1870 return true;
1873 case COMPONENT_REF:
1874 case POINTER_PLUS_EXPR:
1875 case PLUS_EXPR:
1876 case MINUS_EXPR:
1877 case RANGE_EXPR:
1879 tree x1 = TREE_OPERAND (t1, 0);
1880 tree x2 = TREE_OPERAND (t2, 0);
1881 tree y1 = TREE_OPERAND (t1, 1);
1882 tree y2 = TREE_OPERAND (t2, 1);
1884 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
1887 CASE_CONVERT:
1888 case VIEW_CONVERT_EXPR:
1889 if (!func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
1890 return return_false ();
1891 return sem_variable::equals (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1892 case ERROR_MARK:
1893 return return_false_with_msg ("ERROR_MARK");
1894 default:
1895 return return_false_with_msg ("Unknown TREE code reached");
1899 /* Parser function that visits a varpool NODE. */
1901 sem_variable *
1902 sem_variable::parse (varpool_node *node, bitmap_obstack *stack,
1903 func_checker *checker)
1905 if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl)
1906 || node->alias)
1907 return NULL;
1909 sem_variable *v = new sem_variable (node, stack);
1910 v->init (checker);
1912 return v;
1915 /* Semantic variable initialization function. */
1917 void
1918 sem_variable::init (ipa_icf_gimple::func_checker *checker)
1920 decl = get_node ()->decl;
1922 /* All WPA streamed in symbols should have their hashes computed at compile
1923 time. At this point, the constructor may not be in memory at all.
1924 DECL_INITIAL (decl) would be error_mark_node in that case. */
1925 if (!m_hash_set)
1927 gcc_assert (!node->lto_file_data);
1928 inchash::hash hstate;
1929 hstate.add_int (456346417);
1930 checker->hash_operand (DECL_INITIAL (decl), hstate, 0);
1931 set_hash (hstate.end ());
1935 /* References independent hash function. */
1937 hashval_t
1938 sem_variable::get_hash (void)
1940 gcc_checking_assert (m_hash_set);
1941 return m_hash;
1944 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1945 be applied. */
1947 bool
1948 sem_variable::merge (sem_item *alias_item)
1950 gcc_assert (alias_item->type == VAR);
1952 AUTO_DUMP_SCOPE ("merge",
1953 dump_user_location_t::from_function_decl (decl));
1954 if (!sem_item::target_supports_symbol_aliases_p ())
1956 if (dump_enabled_p ())
1957 dump_printf (MSG_MISSED_OPTIMIZATION, "Not unifying; "
1958 "Symbol aliases are not supported by target\n");
1959 return false;
1962 if (DECL_EXTERNAL (alias_item->decl))
1964 if (dump_enabled_p ())
1965 dump_printf (MSG_MISSED_OPTIMIZATION,
1966 "Not unifying; alias is external.\n");
1967 return false;
1970 sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
1972 varpool_node *original = get_node ();
1973 varpool_node *alias = alias_var->get_node ();
1974 bool original_discardable = false;
1976 bool alias_address_matters = alias->address_matters_p ();
1978 /* See if original is in a section that can be discarded if the main
1979 symbol is not used.
1980 Also consider case where we have resolution info and we know that
1981 original's definition is not going to be used. In this case we cannot
1982 create alias to original. */
1983 if (original->can_be_discarded_p ()
1984 || (node->resolution != LDPR_UNKNOWN
1985 && !decl_binds_to_current_def_p (node->decl)))
1986 original_discardable = true;
1988 gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
1990 /* Constant pool machinery is not quite ready for aliases.
1991 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
1992 For LTO merging does not happen that is an important missing feature.
1993 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
1994 flag is dropped and non-local symbol name is assigned. */
1995 if (DECL_IN_CONSTANT_POOL (alias->decl)
1996 || DECL_IN_CONSTANT_POOL (original->decl))
1998 if (dump_enabled_p ())
1999 dump_printf (MSG_MISSED_OPTIMIZATION,
2000 "Not unifying; constant pool variables.\n");
2001 return false;
2004 /* Do not attempt to mix functions from different user sections;
2005 we do not know what user intends with those. */
2006 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
2007 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
2008 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
2010 if (dump_enabled_p ())
2011 dump_printf (MSG_MISSED_OPTIMIZATION,
2012 "Not unifying; "
2013 "original and alias are in different sections.\n");
2014 return false;
2017 /* We cannot merge if address comparison matters. */
2018 if (alias_address_matters && flag_merge_constants < 2)
2020 if (dump_enabled_p ())
2021 dump_printf (MSG_MISSED_OPTIMIZATION,
2022 "Not unifying; address of original may be compared.\n");
2023 return false;
2026 if (DECL_ALIGN (original->decl) != DECL_ALIGN (alias->decl)
2027 && (sanitize_flags_p (SANITIZE_ADDRESS, original->decl)
2028 || sanitize_flags_p (SANITIZE_ADDRESS, alias->decl)))
2030 if (dump_enabled_p ())
2031 dump_printf (MSG_MISSED_OPTIMIZATION,
2032 "Not unifying; "
2033 "ASAN requires equal alignments for original and alias\n");
2035 return false;
2038 if (DECL_ALIGN (original->decl) < DECL_ALIGN (alias->decl))
2040 if (dump_enabled_p ())
2041 dump_printf (MSG_MISSED_OPTIMIZATION,
2042 "Not unifying; "
2043 "original and alias have incompatible alignments\n");
2045 return false;
2048 if (DECL_COMDAT_GROUP (original->decl) != DECL_COMDAT_GROUP (alias->decl))
2050 if (dump_enabled_p ())
2051 dump_printf (MSG_MISSED_OPTIMIZATION,
2052 "Not unifying; alias cannot be created; "
2053 "across comdat group boundary\n");
2055 return false;
2058 if (original_discardable)
2060 if (dump_enabled_p ())
2061 dump_printf (MSG_MISSED_OPTIMIZATION,
2062 "Not unifying; alias cannot be created; "
2063 "target is discardable\n");
2065 return false;
2067 else
2069 gcc_assert (!original->alias);
2070 gcc_assert (!alias->alias);
2072 alias->analyzed = false;
2074 DECL_INITIAL (alias->decl) = NULL;
2075 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
2076 NULL, true);
2077 alias->remove_all_references ();
2078 if (TREE_ADDRESSABLE (alias->decl))
2079 original->call_for_symbol_and_aliases (set_addressable, NULL, true);
2081 varpool_node::create_alias (alias_var->decl, decl);
2082 alias->resolve_alias (original);
2084 if (dump_enabled_p ())
2085 dump_printf (MSG_OPTIMIZED_LOCATIONS,
2086 "Unified; Variable alias has been created.\n");
2088 return true;
2092 /* Dump symbol to FILE. */
2094 void
2095 sem_variable::dump_to_file (FILE *file)
2097 gcc_assert (file);
2099 print_node (file, "", decl, 0);
2100 fprintf (file, "\n\n");
2103 unsigned int sem_item_optimizer::class_id = 0;
2105 sem_item_optimizer::sem_item_optimizer ()
2106 : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL),
2107 m_varpool_node_hooks (NULL), m_merged_variables (), m_references ()
2109 m_items.create (0);
2110 bitmap_obstack_initialize (&m_bmstack);
2113 sem_item_optimizer::~sem_item_optimizer ()
2115 for (unsigned int i = 0; i < m_items.length (); i++)
2116 delete m_items[i];
2119 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
2120 it != m_classes.end (); ++it)
2122 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2123 delete (*it)->classes[i];
2125 (*it)->classes.release ();
2126 free (*it);
2129 m_items.release ();
2131 bitmap_obstack_release (&m_bmstack);
2132 m_merged_variables.release ();
2135 /* Write IPA ICF summary for symbols. */
2137 void
2138 sem_item_optimizer::write_summary (void)
2140 unsigned int count = 0;
2142 output_block *ob = create_output_block (LTO_section_ipa_icf);
2143 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
2144 ob->symbol = NULL;
2146 /* Calculate number of symbols to be serialized. */
2147 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2148 !lsei_end_p (lsei);
2149 lsei_next_in_partition (&lsei))
2151 symtab_node *node = lsei_node (lsei);
2153 if (m_symtab_node_map.get (node))
2154 count++;
2157 streamer_write_uhwi (ob, count);
2159 /* Process all of the symbols. */
2160 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2161 !lsei_end_p (lsei);
2162 lsei_next_in_partition (&lsei))
2164 symtab_node *node = lsei_node (lsei);
2166 sem_item **item = m_symtab_node_map.get (node);
2168 if (item && *item)
2170 int node_ref = lto_symtab_encoder_encode (encoder, node);
2171 streamer_write_uhwi_stream (ob->main_stream, node_ref);
2173 streamer_write_uhwi (ob, (*item)->get_hash ());
2175 if ((*item)->type == FUNC)
2177 sem_function *fn = static_cast<sem_function *> (*item);
2178 streamer_write_uhwi (ob, fn->memory_access_types.length ());
2179 for (unsigned i = 0; i < fn->memory_access_types.length (); i++)
2180 stream_write_tree (ob, fn->memory_access_types[i], true);
2185 streamer_write_char_stream (ob->main_stream, 0);
2186 produce_asm (ob, NULL);
2187 destroy_output_block (ob);
2190 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2191 contains LEN bytes. */
2193 void
2194 sem_item_optimizer::read_section (lto_file_decl_data *file_data,
2195 const char *data, size_t len)
2197 const lto_function_header *header
2198 = (const lto_function_header *) data;
2199 const int cfg_offset = sizeof (lto_function_header);
2200 const int main_offset = cfg_offset + header->cfg_size;
2201 const int string_offset = main_offset + header->main_size;
2202 data_in *data_in;
2203 unsigned int i;
2204 unsigned int count;
2206 lto_input_block ib_main ((const char *) data + main_offset, 0,
2207 header->main_size, file_data->mode_table);
2209 data_in
2210 = lto_data_in_create (file_data, (const char *) data + string_offset,
2211 header->string_size, vNULL);
2213 count = streamer_read_uhwi (&ib_main);
2215 for (i = 0; i < count; i++)
2217 unsigned int index;
2218 symtab_node *node;
2219 lto_symtab_encoder_t encoder;
2221 index = streamer_read_uhwi (&ib_main);
2222 encoder = file_data->symtab_node_encoder;
2223 node = lto_symtab_encoder_deref (encoder, index);
2225 hashval_t hash = streamer_read_uhwi (&ib_main);
2226 gcc_assert (node->definition);
2228 if (is_a<cgraph_node *> (node))
2230 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
2232 sem_function *fn = new sem_function (cnode, &m_bmstack);
2233 unsigned count = streamer_read_uhwi (&ib_main);
2234 inchash::hash hstate (0);
2235 if (flag_incremental_link == INCREMENTAL_LINK_LTO)
2236 fn->memory_access_types.reserve_exact (count);
2237 for (unsigned i = 0; i < count; i++)
2239 tree type = stream_read_tree (&ib_main, data_in);
2240 hstate.add_int (get_deref_alias_set (type));
2241 if (flag_incremental_link == INCREMENTAL_LINK_LTO)
2242 fn->memory_access_types.quick_push (type);
2244 fn->m_alias_sets_hash = hstate.end ();
2245 fn->set_hash (hash);
2246 m_items.safe_push (fn);
2248 else
2250 varpool_node *vnode = dyn_cast <varpool_node *> (node);
2252 sem_variable *var = new sem_variable (vnode, &m_bmstack);
2253 var->set_hash (hash);
2254 m_items.safe_push (var);
2258 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
2259 len);
2260 lto_data_in_delete (data_in);
2263 /* Read IPA ICF summary for symbols. */
2265 void
2266 sem_item_optimizer::read_summary (void)
2268 lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2269 lto_file_decl_data *file_data;
2270 unsigned int j = 0;
2272 while ((file_data = file_data_vec[j++]))
2274 size_t len;
2275 const char *data
2276 = lto_get_summary_section_data (file_data, LTO_section_ipa_icf, &len);
2277 if (data)
2278 read_section (file_data, data, len);
2282 /* Register callgraph and varpool hooks. */
2284 void
2285 sem_item_optimizer::register_hooks (void)
2287 if (!m_cgraph_node_hooks)
2288 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
2289 (&sem_item_optimizer::cgraph_removal_hook, this);
2291 if (!m_varpool_node_hooks)
2292 m_varpool_node_hooks = symtab->add_varpool_removal_hook
2293 (&sem_item_optimizer::varpool_removal_hook, this);
2296 /* Unregister callgraph and varpool hooks. */
2298 void
2299 sem_item_optimizer::unregister_hooks (void)
2301 if (m_cgraph_node_hooks)
2302 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
2304 if (m_varpool_node_hooks)
2305 symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
2308 /* Adds a CLS to hashtable associated by hash value. */
2310 void
2311 sem_item_optimizer::add_class (congruence_class *cls)
2313 gcc_assert (cls->members.length ());
2315 congruence_class_group *group
2316 = get_group_by_hash (cls->members[0]->get_hash (),
2317 cls->members[0]->type);
2318 group->classes.safe_push (cls);
2321 /* Gets a congruence class group based on given HASH value and TYPE. */
2323 congruence_class_group *
2324 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
2326 congruence_class_group *item = XNEW (congruence_class_group);
2327 item->hash = hash;
2328 item->type = type;
2330 congruence_class_group **slot = m_classes.find_slot (item, INSERT);
2332 if (*slot)
2333 free (item);
2334 else
2336 item->classes.create (1);
2337 *slot = item;
2340 return *slot;
2343 /* Callgraph removal hook called for a NODE with a custom DATA. */
2345 void
2346 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
2348 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2349 optimizer->remove_symtab_node (node);
2352 /* Varpool removal hook called for a NODE with a custom DATA. */
2354 void
2355 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
2357 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2358 optimizer->remove_symtab_node (node);
2361 /* Remove symtab NODE triggered by symtab removal hooks. */
2363 void
2364 sem_item_optimizer::remove_symtab_node (symtab_node *node)
2366 gcc_assert (m_classes.is_empty ());
2368 m_removed_items_set.add (node);
2371 void
2372 sem_item_optimizer::remove_item (sem_item *item)
2374 if (m_symtab_node_map.get (item->node))
2375 m_symtab_node_map.remove (item->node);
2376 delete item;
2379 /* Removes all callgraph and varpool nodes that are marked by symtab
2380 as deleted. */
2382 void
2383 sem_item_optimizer::filter_removed_items (void)
2385 auto_vec <sem_item *> filtered;
2387 for (unsigned int i = 0; i < m_items.length(); i++)
2389 sem_item *item = m_items[i];
2391 if (m_removed_items_set.contains (item->node))
2393 remove_item (item);
2394 continue;
2397 if (item->type == FUNC)
2399 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
2401 if (in_lto_p && (cnode->alias || cnode->body_removed))
2402 remove_item (item);
2403 else
2404 filtered.safe_push (item);
2406 else /* VAR. */
2408 if (!flag_ipa_icf_variables)
2409 remove_item (item);
2410 else
2412 /* Filter out non-readonly variables. */
2413 tree decl = item->decl;
2414 if (TREE_READONLY (decl))
2415 filtered.safe_push (item);
2416 else
2417 remove_item (item);
2422 /* Clean-up of released semantic items. */
2424 m_items.release ();
2425 for (unsigned int i = 0; i < filtered.length(); i++)
2426 m_items.safe_push (filtered[i]);
2429 /* Optimizer entry point which returns true in case it processes
2430 a merge operation. True is returned if there's a merge operation
2431 processed. */
2433 bool
2434 sem_item_optimizer::execute (void)
2436 filter_removed_items ();
2437 unregister_hooks ();
2439 build_graph ();
2440 update_hash_by_addr_refs ();
2441 update_hash_by_memory_access_type ();
2442 build_hash_based_classes ();
2444 if (dump_file)
2445 fprintf (dump_file, "Dump after hash based groups\n");
2446 dump_cong_classes ();
2448 subdivide_classes_by_equality (true);
2450 if (dump_file)
2451 fprintf (dump_file, "Dump after WPA based types groups\n");
2453 dump_cong_classes ();
2455 process_cong_reduction ();
2456 checking_verify_classes ();
2458 if (dump_file)
2459 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
2461 dump_cong_classes ();
2463 unsigned int loaded_symbols = parse_nonsingleton_classes ();
2464 subdivide_classes_by_equality ();
2466 if (dump_file)
2467 fprintf (dump_file, "Dump after full equality comparison of groups\n");
2469 dump_cong_classes ();
2471 unsigned int prev_class_count = m_classes_count;
2473 process_cong_reduction ();
2474 dump_cong_classes ();
2475 checking_verify_classes ();
2476 bool merged_p = merge_classes (prev_class_count, loaded_symbols);
2478 if (dump_file && (dump_flags & TDF_DETAILS))
2479 symtab->dump (dump_file);
2481 return merged_p;
2484 /* Function responsible for visiting all potential functions and
2485 read-only variables that can be merged. */
2487 void
2488 sem_item_optimizer::parse_funcs_and_vars (void)
2490 cgraph_node *cnode;
2492 /* Create dummy func_checker for hashing purpose. */
2493 func_checker checker;
2495 if (flag_ipa_icf_functions)
2496 FOR_EACH_DEFINED_FUNCTION (cnode)
2498 sem_function *f = sem_function::parse (cnode, &m_bmstack, &checker);
2499 if (f)
2501 m_items.safe_push (f);
2502 m_symtab_node_map.put (cnode, f);
2506 varpool_node *vnode;
2508 if (flag_ipa_icf_variables)
2509 FOR_EACH_DEFINED_VARIABLE (vnode)
2511 sem_variable *v = sem_variable::parse (vnode, &m_bmstack, &checker);
2513 if (v)
2515 m_items.safe_push (v);
2516 m_symtab_node_map.put (vnode, v);
2521 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2523 void
2524 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
2526 item->index_in_class = cls->members.length ();
2527 cls->members.safe_push (item);
2528 cls->referenced_by_count += item->referenced_by_count;
2529 item->cls = cls;
2532 /* For each semantic item, append hash values of references. */
2534 void
2535 sem_item_optimizer::update_hash_by_addr_refs ()
2537 /* First, append to hash sensitive references and class type if it need to
2538 be matched for ODR. */
2539 for (unsigned i = 0; i < m_items.length (); i++)
2541 m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
2542 if (m_items[i]->type == FUNC)
2544 if (TREE_CODE (TREE_TYPE (m_items[i]->decl)) == METHOD_TYPE
2545 && contains_polymorphic_type_p
2546 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl)))
2547 && (DECL_CXX_CONSTRUCTOR_P (m_items[i]->decl)
2548 || (static_cast<sem_function *> (m_items[i])->param_used_p (0)
2549 && static_cast<sem_function *> (m_items[i])
2550 ->compare_polymorphic_p ())))
2552 tree class_type
2553 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl));
2554 inchash::hash hstate (m_items[i]->get_hash ());
2556 /* Hash ODR types by mangled name if it is defined.
2557 If not we know that type is anonymous of free_lang_data
2558 was not run and in that case type main variants are
2559 unique. */
2560 if (TYPE_NAME (class_type)
2561 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type))
2562 && !type_in_anonymous_namespace_p
2563 (class_type))
2564 hstate.add_hwi
2565 (IDENTIFIER_HASH_VALUE
2566 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type))));
2567 else
2569 gcc_checking_assert
2570 (!in_lto_p
2571 || type_in_anonymous_namespace_p (class_type));
2572 hstate.add_hwi (TYPE_UID (TYPE_MAIN_VARIANT (class_type)));
2575 m_items[i]->set_hash (hstate.end ());
2580 /* Once all symbols have enhanced hash value, we can append
2581 hash values of symbols that are seen by IPA ICF and are
2582 references by a semantic item. Newly computed values
2583 are saved to global_hash member variable. */
2584 for (unsigned i = 0; i < m_items.length (); i++)
2585 m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
2587 /* Global hash value replace current hash values. */
2588 for (unsigned i = 0; i < m_items.length (); i++)
2589 m_items[i]->set_hash (m_items[i]->global_hash);
2592 void
2593 sem_item_optimizer::update_hash_by_memory_access_type ()
2595 for (unsigned i = 0; i < m_items.length (); i++)
2597 if (m_items[i]->type == FUNC)
2599 sem_function *fn = static_cast<sem_function *> (m_items[i]);
2600 inchash::hash hstate (fn->get_hash ());
2601 hstate.add_int (fn->m_alias_sets_hash);
2602 fn->set_hash (hstate.end ());
2607 /* Congruence classes are built by hash value. */
2609 void
2610 sem_item_optimizer::build_hash_based_classes (void)
2612 for (unsigned i = 0; i < m_items.length (); i++)
2614 sem_item *item = m_items[i];
2616 congruence_class_group *group
2617 = get_group_by_hash (item->get_hash (), item->type);
2619 if (!group->classes.length ())
2621 m_classes_count++;
2622 group->classes.safe_push (new congruence_class (class_id++));
2625 add_item_to_class (group->classes[0], item);
2629 /* Build references according to call graph. */
2631 void
2632 sem_item_optimizer::build_graph (void)
2634 for (unsigned i = 0; i < m_items.length (); i++)
2636 sem_item *item = m_items[i];
2637 m_symtab_node_map.put (item->node, item);
2639 /* Initialize hash values if we are not in LTO mode. */
2640 if (!in_lto_p)
2641 item->get_hash ();
2644 for (unsigned i = 0; i < m_items.length (); i++)
2646 sem_item *item = m_items[i];
2648 if (item->type == FUNC)
2650 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
2652 cgraph_edge *e = cnode->callees;
2653 while (e)
2655 sem_item **slot = m_symtab_node_map.get
2656 (e->callee->ultimate_alias_target ());
2657 if (slot)
2658 item->add_reference (&m_references, *slot);
2660 e = e->next_callee;
2664 ipa_ref *ref = NULL;
2665 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
2667 sem_item **slot = m_symtab_node_map.get
2668 (ref->referred->ultimate_alias_target ());
2669 if (slot)
2670 item->add_reference (&m_references, *slot);
2675 /* Semantic items in classes having more than one element and initialized.
2676 In case of WPA, we load function body. */
2678 unsigned int
2679 sem_item_optimizer::parse_nonsingleton_classes (void)
2681 unsigned int counter = 0;
2683 /* Create dummy func_checker for hashing purpose. */
2684 func_checker checker;
2686 for (unsigned i = 0; i < m_items.length (); i++)
2687 if (m_items[i]->cls->members.length () > 1)
2689 m_items[i]->init (&checker);
2690 ++counter;
2693 if (dump_file)
2695 float f = m_items.length () ? 100.0f * counter / m_items.length () : 0.0f;
2696 fprintf (dump_file, "Init called for %u items (%.2f%%).\n", counter, f);
2699 return counter;
2702 /* Equality function for semantic items is used to subdivide existing
2703 classes. If IN_WPA, fast equality function is invoked. */
2705 void
2706 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
2708 for (hash_table <congruence_class_hash>::iterator it = m_classes.begin ();
2709 it != m_classes.end (); ++it)
2711 unsigned int class_count = (*it)->classes.length ();
2713 for (unsigned i = 0; i < class_count; i++)
2715 congruence_class *c = (*it)->classes[i];
2717 if (c->members.length() > 1)
2719 auto_vec <sem_item *> new_vector;
2721 sem_item *first = c->members[0];
2722 new_vector.safe_push (first);
2724 unsigned class_split_first = (*it)->classes.length ();
2726 for (unsigned j = 1; j < c->members.length (); j++)
2728 sem_item *item = c->members[j];
2730 bool equals
2731 = in_wpa ? first->equals_wpa (item, m_symtab_node_map)
2732 : first->equals (item, m_symtab_node_map);
2734 if (equals)
2735 new_vector.safe_push (item);
2736 else
2738 bool integrated = false;
2740 for (unsigned k = class_split_first;
2741 k < (*it)->classes.length (); k++)
2743 sem_item *x = (*it)->classes[k]->members[0];
2744 bool equals
2745 = in_wpa ? x->equals_wpa (item, m_symtab_node_map)
2746 : x->equals (item, m_symtab_node_map);
2748 if (equals)
2750 integrated = true;
2751 add_item_to_class ((*it)->classes[k], item);
2753 break;
2757 if (!integrated)
2759 congruence_class *c
2760 = new congruence_class (class_id++);
2761 m_classes_count++;
2762 add_item_to_class (c, item);
2764 (*it)->classes.safe_push (c);
2769 // We replace newly created new_vector for the class we've just
2770 // splitted.
2771 c->members.release ();
2772 c->members.create (new_vector.length ());
2774 for (unsigned int j = 0; j < new_vector.length (); j++)
2775 add_item_to_class (c, new_vector[j]);
2780 checking_verify_classes ();
2783 /* Subdivide classes by address references that members of the class
2784 reference. Example can be a pair of functions that have an address
2785 taken from a function. If these addresses are different the class
2786 is split. */
2788 unsigned
2789 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2791 typedef hash_map <symbol_compare_hash, vec <sem_item *> > subdivide_hash_map;
2793 unsigned newly_created_classes = 0;
2795 for (hash_table <congruence_class_hash>::iterator it = m_classes.begin ();
2796 it != m_classes.end (); ++it)
2798 unsigned int class_count = (*it)->classes.length ();
2799 auto_vec<congruence_class *> new_classes;
2801 for (unsigned i = 0; i < class_count; i++)
2803 congruence_class *c = (*it)->classes[i];
2805 if (c->members.length() > 1)
2807 subdivide_hash_map split_map;
2809 for (unsigned j = 0; j < c->members.length (); j++)
2811 sem_item *source_node = c->members[j];
2813 symbol_compare_collection *collection
2814 = new symbol_compare_collection (source_node->node);
2816 bool existed;
2817 vec <sem_item *> *slot
2818 = &split_map.get_or_insert (collection, &existed);
2819 gcc_checking_assert (slot);
2821 slot->safe_push (source_node);
2823 if (existed)
2824 delete collection;
2827 /* If the map contains more than one key, we have to split
2828 the map appropriately. */
2829 if (split_map.elements () != 1)
2831 bool first_class = true;
2833 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2834 it2 != split_map.end (); ++it2)
2836 congruence_class *new_cls;
2837 new_cls = new congruence_class (class_id++);
2839 for (unsigned k = 0; k < (*it2).second.length (); k++)
2840 add_item_to_class (new_cls, (*it2).second[k]);
2842 worklist_push (new_cls);
2843 newly_created_classes++;
2845 if (first_class)
2847 (*it)->classes[i] = new_cls;
2848 first_class = false;
2850 else
2852 new_classes.safe_push (new_cls);
2853 m_classes_count++;
2858 /* Release memory. */
2859 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2860 it2 != split_map.end (); ++it2)
2862 delete (*it2).first;
2863 (*it2).second.release ();
2868 for (unsigned i = 0; i < new_classes.length (); i++)
2869 (*it)->classes.safe_push (new_classes[i]);
2872 return newly_created_classes;
2875 /* Verify congruence classes, if checking is enabled. */
2877 void
2878 sem_item_optimizer::checking_verify_classes (void)
2880 if (flag_checking)
2881 verify_classes ();
2884 /* Verify congruence classes. */
2886 void
2887 sem_item_optimizer::verify_classes (void)
2889 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
2890 it != m_classes.end (); ++it)
2892 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2894 congruence_class *cls = (*it)->classes[i];
2896 gcc_assert (cls);
2897 gcc_assert (cls->members.length () > 0);
2899 for (unsigned int j = 0; j < cls->members.length (); j++)
2901 sem_item *item = cls->members[j];
2903 gcc_assert (item);
2904 gcc_assert (item->cls == cls);
2910 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2911 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2912 but unused argument. */
2914 bool
2915 sem_item_optimizer::release_split_map (congruence_class * const &,
2916 bitmap const &b, traverse_split_pair *)
2918 bitmap bmp = b;
2920 BITMAP_FREE (bmp);
2922 return true;
2925 /* Process split operation for a class given as pointer CLS_PTR,
2926 where bitmap B splits congruence class members. DATA is used
2927 as argument of split pair. */
2929 bool
2930 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
2931 bitmap const &b,
2932 traverse_split_pair *pair)
2934 sem_item_optimizer *optimizer = pair->optimizer;
2935 const congruence_class *splitter_cls = pair->cls;
2937 /* If counted bits are greater than zero and less than the number of members
2938 a group will be splitted. */
2939 unsigned popcount = bitmap_count_bits (b);
2941 if (popcount > 0 && popcount < cls->members.length ())
2943 auto_vec <congruence_class *, 2> newclasses;
2944 newclasses.quick_push (new congruence_class (class_id++));
2945 newclasses.quick_push (new congruence_class (class_id++));
2947 for (unsigned int i = 0; i < cls->members.length (); i++)
2949 int target = bitmap_bit_p (b, i);
2950 congruence_class *tc = newclasses[target];
2952 add_item_to_class (tc, cls->members[i]);
2955 if (flag_checking)
2957 for (unsigned int i = 0; i < 2; i++)
2958 gcc_assert (newclasses[i]->members.length ());
2961 if (splitter_cls == cls)
2962 optimizer->splitter_class_removed = true;
2964 /* Remove old class from worklist if presented. */
2965 bool in_worklist = cls->in_worklist;
2967 if (in_worklist)
2968 cls->in_worklist = false;
2970 congruence_class_group g;
2971 g.hash = cls->members[0]->get_hash ();
2972 g.type = cls->members[0]->type;
2974 congruence_class_group *slot = optimizer->m_classes.find (&g);
2976 for (unsigned int i = 0; i < slot->classes.length (); i++)
2977 if (slot->classes[i] == cls)
2979 slot->classes.ordered_remove (i);
2980 break;
2983 /* New class will be inserted and integrated to work list. */
2984 for (unsigned int i = 0; i < 2; i++)
2985 optimizer->add_class (newclasses[i]);
2987 /* Two classes replace one, so that increment just by one. */
2988 optimizer->m_classes_count++;
2990 /* If OLD class was presented in the worklist, we remove the class
2991 and replace it will both newly created classes. */
2992 if (in_worklist)
2993 for (unsigned int i = 0; i < 2; i++)
2994 optimizer->worklist_push (newclasses[i]);
2995 else /* Just smaller class is inserted. */
2997 unsigned int smaller_index
2998 = (newclasses[0]->members.length ()
2999 < newclasses[1]->members.length ()
3000 ? 0 : 1);
3001 optimizer->worklist_push (newclasses[smaller_index]);
3004 if (dump_file && (dump_flags & TDF_DETAILS))
3006 fprintf (dump_file, " congruence class splitted:\n");
3007 cls->dump (dump_file, 4);
3009 fprintf (dump_file, " newly created groups:\n");
3010 for (unsigned int i = 0; i < 2; i++)
3011 newclasses[i]->dump (dump_file, 4);
3014 /* Release class if not presented in work list. */
3015 if (!in_worklist)
3016 delete cls;
3018 return true;
3021 return false;
3024 /* Compare function for sorting pairs in do_congruence_step_f. */
3027 sem_item_optimizer::sort_congruence_split (const void *a_, const void *b_)
3029 const std::pair<congruence_class *, bitmap> *a
3030 = (const std::pair<congruence_class *, bitmap> *)a_;
3031 const std::pair<congruence_class *, bitmap> *b
3032 = (const std::pair<congruence_class *, bitmap> *)b_;
3033 if (a->first->id < b->first->id)
3034 return -1;
3035 else if (a->first->id > b->first->id)
3036 return 1;
3037 return 0;
3040 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3041 Bitmap stack BMSTACK is used for bitmap allocation. */
3043 bool
3044 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
3045 unsigned int index)
3047 hash_map <congruence_class *, bitmap> split_map;
3049 for (unsigned int i = 0; i < cls->members.length (); i++)
3051 sem_item *item = cls->members[i];
3052 sem_usage_pair needle (item, index);
3053 vec<sem_item *> *callers = m_references.get (&needle);
3054 if (callers == NULL)
3055 continue;
3057 for (unsigned int j = 0; j < callers->length (); j++)
3059 sem_item *caller = (*callers)[j];
3060 if (caller->cls->members.length () < 2)
3061 continue;
3062 bitmap *slot = split_map.get (caller->cls);
3063 bitmap b;
3065 if(!slot)
3067 b = BITMAP_ALLOC (&m_bmstack);
3068 split_map.put (caller->cls, b);
3070 else
3071 b = *slot;
3073 gcc_checking_assert (caller->cls);
3074 gcc_checking_assert (caller->index_in_class
3075 < caller->cls->members.length ());
3077 bitmap_set_bit (b, caller->index_in_class);
3081 auto_vec<std::pair<congruence_class *, bitmap> > to_split;
3082 to_split.reserve_exact (split_map.elements ());
3083 for (hash_map <congruence_class *, bitmap>::iterator i = split_map.begin ();
3084 i != split_map.end (); ++i)
3085 to_split.safe_push (*i);
3086 to_split.qsort (sort_congruence_split);
3088 traverse_split_pair pair;
3089 pair.optimizer = this;
3090 pair.cls = cls;
3092 splitter_class_removed = false;
3093 bool r = false;
3094 for (unsigned i = 0; i < to_split.length (); ++i)
3095 r |= traverse_congruence_split (to_split[i].first, to_split[i].second,
3096 &pair);
3098 /* Bitmap clean-up. */
3099 split_map.traverse <traverse_split_pair *,
3100 sem_item_optimizer::release_split_map> (NULL);
3102 return r;
3105 /* Every usage of a congruence class CLS is a candidate that can split the
3106 collection of classes. Bitmap stack BMSTACK is used for bitmap
3107 allocation. */
3109 void
3110 sem_item_optimizer::do_congruence_step (congruence_class *cls)
3112 bitmap_iterator bi;
3113 unsigned int i;
3115 bitmap usage = BITMAP_ALLOC (&m_bmstack);
3117 for (unsigned int i = 0; i < cls->members.length (); i++)
3118 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
3120 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
3122 if (dump_file && (dump_flags & TDF_DETAILS))
3123 fprintf (dump_file, " processing congruence step for class: %u "
3124 "(%u items, %u references), index: %u\n", cls->id,
3125 cls->referenced_by_count, cls->members.length (), i);
3126 do_congruence_step_for_index (cls, i);
3128 if (splitter_class_removed)
3129 break;
3132 BITMAP_FREE (usage);
3135 /* Adds a newly created congruence class CLS to worklist. */
3137 void
3138 sem_item_optimizer::worklist_push (congruence_class *cls)
3140 /* Return if the class CLS is already presented in work list. */
3141 if (cls->in_worklist)
3142 return;
3144 cls->in_worklist = true;
3145 worklist.insert (cls->referenced_by_count, cls);
3148 /* Pops a class from worklist. */
3150 congruence_class *
3151 sem_item_optimizer::worklist_pop (void)
3153 congruence_class *cls;
3155 while (!worklist.empty ())
3157 cls = worklist.extract_min ();
3158 if (cls->in_worklist)
3160 cls->in_worklist = false;
3162 return cls;
3164 else
3166 /* Work list item was already intended to be removed.
3167 The only reason for doing it is to split a class.
3168 Thus, the class CLS is deleted. */
3169 delete cls;
3173 return NULL;
3176 /* Iterative congruence reduction function. */
3178 void
3179 sem_item_optimizer::process_cong_reduction (void)
3181 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3182 it != m_classes.end (); ++it)
3183 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3184 if ((*it)->classes[i]->is_class_used ())
3185 worklist_push ((*it)->classes[i]);
3187 if (dump_file)
3188 fprintf (dump_file, "Worklist has been filled with: %lu\n",
3189 (unsigned long) worklist.nodes ());
3191 if (dump_file && (dump_flags & TDF_DETAILS))
3192 fprintf (dump_file, "Congruence class reduction\n");
3194 congruence_class *cls;
3196 /* Process complete congruence reduction. */
3197 while ((cls = worklist_pop ()) != NULL)
3198 do_congruence_step (cls);
3200 /* Subdivide newly created classes according to references. */
3201 unsigned new_classes = subdivide_classes_by_sensitive_refs ();
3203 if (dump_file)
3204 fprintf (dump_file, "Address reference subdivision created: %u "
3205 "new classes.\n", new_classes);
3208 /* Debug function prints all informations about congruence classes. */
3210 void
3211 sem_item_optimizer::dump_cong_classes (void)
3213 if (!dump_file)
3214 return;
3216 /* Histogram calculation. */
3217 unsigned int max_index = 0;
3218 unsigned int single_element_classes = 0;
3219 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
3221 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3222 it != m_classes.end (); ++it)
3223 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3225 unsigned int c = (*it)->classes[i]->members.length ();
3226 histogram[c]++;
3228 if (c > max_index)
3229 max_index = c;
3231 if (c == 1)
3232 ++single_element_classes;
3235 fprintf (dump_file,
3236 "Congruence classes: %lu with total: %u items (in a non-singular "
3237 "class: %u)\n", (unsigned long) m_classes.elements (),
3238 m_items.length (), m_items.length () - single_element_classes);
3239 fprintf (dump_file,
3240 "Class size histogram [number of members]: number of classes\n");
3241 for (unsigned int i = 0; i <= max_index; i++)
3242 if (histogram[i])
3243 fprintf (dump_file, "%6u: %6u\n", i, histogram[i]);
3245 if (dump_flags & TDF_DETAILS)
3246 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3247 it != m_classes.end (); ++it)
3249 fprintf (dump_file, " group: with %u classes:\n",
3250 (*it)->classes.length ());
3252 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3254 (*it)->classes[i]->dump (dump_file, 4);
3256 if (i < (*it)->classes.length () - 1)
3257 fprintf (dump_file, " ");
3261 free (histogram);
3264 /* Sort pair of sem_items A and B by DECL_UID. */
3266 static int
3267 sort_sem_items_by_decl_uid (const void *a, const void *b)
3269 const sem_item *i1 = *(const sem_item * const *)a;
3270 const sem_item *i2 = *(const sem_item * const *)b;
3272 int uid1 = DECL_UID (i1->decl);
3273 int uid2 = DECL_UID (i2->decl);
3274 return uid1 - uid2;
3277 /* Sort pair of congruence_classes A and B by DECL_UID of the first member. */
3279 static int
3280 sort_congruence_classes_by_decl_uid (const void *a, const void *b)
3282 const congruence_class *c1 = *(const congruence_class * const *)a;
3283 const congruence_class *c2 = *(const congruence_class * const *)b;
3285 int uid1 = DECL_UID (c1->members[0]->decl);
3286 int uid2 = DECL_UID (c2->members[0]->decl);
3287 return uid1 - uid2;
3290 /* Sort pair of congruence_class_groups A and B by
3291 DECL_UID of the first member of a first group. */
3293 static int
3294 sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
3296 const std::pair<congruence_class_group *, int> *g1
3297 = (const std::pair<congruence_class_group *, int> *) a;
3298 const std::pair<congruence_class_group *, int> *g2
3299 = (const std::pair<congruence_class_group *, int> *) b;
3300 return g1->second - g2->second;
3303 /* After reduction is done, we can declare all items in a group
3304 to be equal. PREV_CLASS_COUNT is start number of classes
3305 before reduction. True is returned if there's a merge operation
3306 processed. LOADED_SYMBOLS is number of symbols that were loaded
3307 in WPA. */
3309 bool
3310 sem_item_optimizer::merge_classes (unsigned int prev_class_count,
3311 unsigned int loaded_symbols)
3313 unsigned int item_count = m_items.length ();
3314 unsigned int class_count = m_classes_count;
3315 unsigned int equal_items = item_count - class_count;
3317 unsigned int non_singular_classes_count = 0;
3318 unsigned int non_singular_classes_sum = 0;
3320 bool merged_p = false;
3322 /* PR lto/78211
3323 Sort functions in congruence classes by DECL_UID and do the same
3324 for the classes to not to break -fcompare-debug. */
3326 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3327 it != m_classes.end (); ++it)
3329 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3331 congruence_class *c = (*it)->classes[i];
3332 c->members.qsort (sort_sem_items_by_decl_uid);
3335 (*it)->classes.qsort (sort_congruence_classes_by_decl_uid);
3338 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3339 it != m_classes.end (); ++it)
3340 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3342 congruence_class *c = (*it)->classes[i];
3343 if (c->members.length () > 1)
3345 non_singular_classes_count++;
3346 non_singular_classes_sum += c->members.length ();
3350 auto_vec<std::pair<congruence_class_group *, int> > classes (
3351 m_classes.elements ());
3352 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3353 it != m_classes.end (); ++it)
3355 int uid = DECL_UID ((*it)->classes[0]->members[0]->decl);
3356 classes.quick_push (std::pair<congruence_class_group *, int> (*it, uid));
3359 classes.qsort (sort_congruence_class_groups_by_decl_uid);
3361 if (dump_file)
3363 fprintf (dump_file, "\nItem count: %u\n", item_count);
3364 fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
3365 prev_class_count, class_count);
3366 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
3367 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
3368 class_count ? 1.0f * item_count / class_count : 0.0f);
3369 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
3370 non_singular_classes_count ? 1.0f * non_singular_classes_sum /
3371 non_singular_classes_count : 0.0f,
3372 non_singular_classes_count);
3373 fprintf (dump_file, "Equal symbols: %u\n", equal_items);
3374 unsigned total = equal_items + non_singular_classes_count;
3375 fprintf (dump_file, "Totally needed symbols: %u"
3376 ", fraction of loaded symbols: %.2f%%\n\n", total,
3377 loaded_symbols ? 100.0f * total / loaded_symbols: 0.0f);
3380 unsigned int l;
3381 std::pair<congruence_class_group *, int> *it;
3382 FOR_EACH_VEC_ELT (classes, l, it)
3383 for (unsigned int i = 0; i < it->first->classes.length (); i++)
3385 congruence_class *c = it->first->classes[i];
3387 if (c->members.length () == 1)
3388 continue;
3390 sem_item *source = c->members[0];
3392 if (DECL_NAME (source->decl)
3393 && MAIN_NAME_P (DECL_NAME (source->decl)))
3394 /* If merge via wrappers, picking main as the target can be
3395 problematic. */
3396 source = c->members[1];
3398 for (unsigned int j = 0; j < c->members.length (); j++)
3400 sem_item *alias = c->members[j];
3402 if (alias == source)
3403 continue;
3405 dump_user_location_t loc
3406 = dump_user_location_t::from_function_decl (source->decl);
3407 if (dump_enabled_p ())
3409 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
3410 "Semantic equality hit:%s->%s\n",
3411 source->node->dump_name (),
3412 alias->node->dump_name ());
3413 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
3414 "Assembler symbol names:%s->%s\n",
3415 source->node->dump_asm_name (),
3416 alias->node->dump_asm_name ());
3419 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl)))
3421 if (dump_enabled_p ())
3422 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
3423 "Merge operation is skipped due to no_icf "
3424 "attribute.\n");
3425 continue;
3428 if (dump_file && (dump_flags & TDF_DETAILS))
3430 source->dump_to_file (dump_file);
3431 alias->dump_to_file (dump_file);
3434 if (dbg_cnt (merged_ipa_icf))
3436 bool merged = source->merge (alias);
3437 merged_p |= merged;
3439 if (merged && alias->type == VAR)
3441 symtab_pair p = symtab_pair (source->node, alias->node);
3442 m_merged_variables.safe_push (p);
3448 if (!m_merged_variables.is_empty ())
3449 fixup_points_to_sets ();
3451 return merged_p;
3454 /* Fixup points to set PT. */
3456 void
3457 sem_item_optimizer::fixup_pt_set (struct pt_solution *pt)
3459 if (pt->vars == NULL)
3460 return;
3462 unsigned i;
3463 symtab_pair *item;
3464 FOR_EACH_VEC_ELT (m_merged_variables, i, item)
3465 if (bitmap_bit_p (pt->vars, DECL_UID (item->second->decl)))
3466 bitmap_set_bit (pt->vars, DECL_UID (item->first->decl));
3469 /* Set all points-to UIDs of aliases pointing to node N as UID. */
3471 static void
3472 set_alias_uids (symtab_node *n, int uid)
3474 ipa_ref *ref;
3475 FOR_EACH_ALIAS (n, ref)
3477 if (dump_file)
3478 fprintf (dump_file, " Setting points-to UID of [%s] as %d\n",
3479 ref->referring->dump_asm_name (), uid);
3481 SET_DECL_PT_UID (ref->referring->decl, uid);
3482 set_alias_uids (ref->referring, uid);
3486 /* Fixup points to analysis info. */
3488 void
3489 sem_item_optimizer::fixup_points_to_sets (void)
3491 /* TODO: remove in GCC 9 and trigger PTA re-creation after IPA passes. */
3492 cgraph_node *cnode;
3494 FOR_EACH_DEFINED_FUNCTION (cnode)
3496 tree name;
3497 unsigned i;
3498 function *fn = DECL_STRUCT_FUNCTION (cnode->decl);
3499 if (!gimple_in_ssa_p (fn))
3500 continue;
3502 FOR_EACH_SSA_NAME (i, name, fn)
3503 if (POINTER_TYPE_P (TREE_TYPE (name))
3504 && SSA_NAME_PTR_INFO (name))
3505 fixup_pt_set (&SSA_NAME_PTR_INFO (name)->pt);
3506 fixup_pt_set (&fn->gimple_df->escaped);
3508 /* The above gets us to 99% I guess, at least catching the
3509 address compares. Below also gets us aliasing correct
3510 but as said we're giving leeway to the situation with
3511 readonly vars anyway, so ... */
3512 basic_block bb;
3513 FOR_EACH_BB_FN (bb, fn)
3514 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
3515 gsi_next (&gsi))
3517 gcall *call = dyn_cast<gcall *> (gsi_stmt (gsi));
3518 if (call)
3520 fixup_pt_set (gimple_call_use_set (call));
3521 fixup_pt_set (gimple_call_clobber_set (call));
3526 unsigned i;
3527 symtab_pair *item;
3528 FOR_EACH_VEC_ELT (m_merged_variables, i, item)
3529 set_alias_uids (item->first, DECL_UID (item->first->decl));
3532 /* Dump function prints all class members to a FILE with an INDENT. */
3534 void
3535 congruence_class::dump (FILE *file, unsigned int indent) const
3537 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
3538 id, members[0]->get_hash (), members.length ());
3540 FPUTS_SPACES (file, indent + 2, "");
3541 for (unsigned i = 0; i < members.length (); i++)
3542 fprintf (file, "%s ", members[i]->node->dump_asm_name ());
3544 fprintf (file, "\n");
3547 /* Returns true if there's a member that is used from another group. */
3549 bool
3550 congruence_class::is_class_used (void)
3552 for (unsigned int i = 0; i < members.length (); i++)
3553 if (members[i]->referenced_by_count)
3554 return true;
3556 return false;
3559 /* Generate pass summary for IPA ICF pass. */
3561 static void
3562 ipa_icf_generate_summary (void)
3564 if (!optimizer)
3565 optimizer = new sem_item_optimizer ();
3567 optimizer->register_hooks ();
3568 optimizer->parse_funcs_and_vars ();
3571 /* Write pass summary for IPA ICF pass. */
3573 static void
3574 ipa_icf_write_summary (void)
3576 gcc_assert (optimizer);
3578 optimizer->write_summary ();
3581 /* Read pass summary for IPA ICF pass. */
3583 static void
3584 ipa_icf_read_summary (void)
3586 if (!optimizer)
3587 optimizer = new sem_item_optimizer ();
3589 optimizer->read_summary ();
3590 optimizer->register_hooks ();
3593 /* Semantic equality execution function. */
3595 static unsigned int
3596 ipa_icf_driver (void)
3598 gcc_assert (optimizer);
3600 bool merged_p = optimizer->execute ();
3602 delete optimizer;
3603 optimizer = NULL;
3605 return merged_p ? TODO_remove_functions : 0;
3608 const pass_data pass_data_ipa_icf =
3610 IPA_PASS, /* type */
3611 "icf", /* name */
3612 OPTGROUP_IPA, /* optinfo_flags */
3613 TV_IPA_ICF, /* tv_id */
3614 0, /* properties_required */
3615 0, /* properties_provided */
3616 0, /* properties_destroyed */
3617 0, /* todo_flags_start */
3618 0, /* todo_flags_finish */
3621 class pass_ipa_icf : public ipa_opt_pass_d
3623 public:
3624 pass_ipa_icf (gcc::context *ctxt)
3625 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
3626 ipa_icf_generate_summary, /* generate_summary */
3627 ipa_icf_write_summary, /* write_summary */
3628 ipa_icf_read_summary, /* read_summary */
3629 NULL, /*
3630 write_optimization_summary */
3631 NULL, /*
3632 read_optimization_summary */
3633 NULL, /* stmt_fixup */
3634 0, /* function_transform_todo_flags_start */
3635 NULL, /* function_transform */
3636 NULL) /* variable_transform */
3639 /* opt_pass methods: */
3640 virtual bool gate (function *)
3642 return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
3645 virtual unsigned int execute (function *)
3647 return ipa_icf_driver();
3649 }; // class pass_ipa_icf
3651 } // ipa_icf namespace
3653 ipa_opt_pass_d *
3654 make_pass_ipa_icf (gcc::context *ctxt)
3656 return new ipa_icf::pass_ipa_icf (ctxt);