2015-06-23 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / ipa-icf.c
blob9a8133faa2c4620acf27e54fd6c2f02951d97a56
1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2015 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural Identical Code Folding for functions and
23 read-only variables.
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
28 In case of functions,
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
32 aliases if possible.
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
45 correspond.
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
54 #include "config.h"
55 #include "system.h"
56 #include <list>
57 #include "coretypes.h"
58 #include "alias.h"
59 #include "symtab.h"
60 #include "options.h"
61 #include "tree.h"
62 #include "fold-const.h"
63 #include "predict.h"
64 #include "tm.h"
65 #include "hard-reg-set.h"
66 #include "function.h"
67 #include "dominance.h"
68 #include "cfg.h"
69 #include "basic-block.h"
70 #include "tree-ssa-alias.h"
71 #include "internal-fn.h"
72 #include "gimple-expr.h"
73 #include "gimple.h"
74 #include "rtl.h"
75 #include "flags.h"
76 #include "insn-config.h"
77 #include "expmed.h"
78 #include "dojump.h"
79 #include "explow.h"
80 #include "calls.h"
81 #include "emit-rtl.h"
82 #include "varasm.h"
83 #include "stmt.h"
84 #include "expr.h"
85 #include "gimple-iterator.h"
86 #include "gimple-ssa.h"
87 #include "tree-cfg.h"
88 #include "tree-phinodes.h"
89 #include "stringpool.h"
90 #include "tree-ssanames.h"
91 #include "tree-dfa.h"
92 #include "tree-pass.h"
93 #include "gimple-pretty-print.h"
94 #include "plugin-api.h"
95 #include "ipa-ref.h"
96 #include "cgraph.h"
97 #include "alloc-pool.h"
98 #include "symbol-summary.h"
99 #include "ipa-prop.h"
100 #include "ipa-inline.h"
101 #include "cfgloop.h"
102 #include "except.h"
103 #include "coverage.h"
104 #include "attribs.h"
105 #include "print-tree.h"
106 #include "lto-streamer.h"
107 #include "data-streamer.h"
108 #include "ipa-utils.h"
109 #include "ipa-icf-gimple.h"
110 #include "ipa-icf.h"
111 #include "stor-layout.h"
112 #include "dbgcnt.h"
114 using namespace ipa_icf_gimple;
116 namespace ipa_icf {
118 /* Initialization and computation of symtab node hash, there data
119 are propagated later on. */
121 static sem_item_optimizer *optimizer = NULL;
123 /* Constructor. */
125 symbol_compare_collection::symbol_compare_collection (symtab_node *node)
127 m_references.create (0);
128 m_interposables.create (0);
130 ipa_ref *ref;
132 if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
133 return;
135 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
137 if (ref->address_matters_p ())
138 m_references.safe_push (ref->referred);
140 if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE)
142 if (ref->address_matters_p ())
143 m_references.safe_push (ref->referred);
144 else
145 m_interposables.safe_push (ref->referred);
149 if (is_a <cgraph_node *> (node))
151 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
153 for (cgraph_edge *e = cnode->callees; e; e = e->next_callee)
154 if (e->callee->get_availability () <= AVAIL_INTERPOSABLE)
155 m_interposables.safe_push (e->callee);
159 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
161 sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index):
162 item (_item), index (_index)
166 /* Semantic item constructor for a node of _TYPE, where STACK is used
167 for bitmap memory allocation. */
169 sem_item::sem_item (sem_item_type _type,
170 bitmap_obstack *stack): type(_type), hash(0)
172 setup (stack);
175 /* Semantic item constructor for a node of _TYPE, where STACK is used
176 for bitmap memory allocation. The item is based on symtab node _NODE
177 with computed _HASH. */
179 sem_item::sem_item (sem_item_type _type, symtab_node *_node,
180 hashval_t _hash, bitmap_obstack *stack): type(_type),
181 node (_node), hash (_hash)
183 decl = node->decl;
184 setup (stack);
187 /* Add reference to a semantic TARGET. */
189 void
190 sem_item::add_reference (sem_item *target)
192 refs.safe_push (target);
193 unsigned index = refs.length ();
194 target->usages.safe_push (new sem_usage_pair(this, index));
195 bitmap_set_bit (target->usage_index_bitmap, index);
196 refs_set.add (target->node);
199 /* Initialize internal data structures. Bitmap STACK is used for
200 bitmap memory allocation process. */
202 void
203 sem_item::setup (bitmap_obstack *stack)
205 gcc_checking_assert (node);
207 refs.create (0);
208 tree_refs.create (0);
209 usages.create (0);
210 usage_index_bitmap = BITMAP_ALLOC (stack);
213 sem_item::~sem_item ()
215 for (unsigned i = 0; i < usages.length (); i++)
216 delete usages[i];
218 refs.release ();
219 tree_refs.release ();
220 usages.release ();
222 BITMAP_FREE (usage_index_bitmap);
225 /* Dump function for debugging purpose. */
227 DEBUG_FUNCTION void
228 sem_item::dump (void)
230 if (dump_file)
232 fprintf (dump_file, "[%s] %s (%u) (tree:%p)\n", type == FUNC ? "func" : "var",
233 node->name(), node->order, (void *) node->decl);
234 fprintf (dump_file, " hash: %u\n", get_hash ());
235 fprintf (dump_file, " references: ");
237 for (unsigned i = 0; i < refs.length (); i++)
238 fprintf (dump_file, "%s%s ", refs[i]->node->name (),
239 i < refs.length() - 1 ? "," : "");
241 fprintf (dump_file, "\n");
245 /* Return true if target supports alias symbols. */
247 bool
248 sem_item::target_supports_symbol_aliases_p (void)
250 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
251 return false;
252 #else
253 return true;
254 #endif
257 /* Semantic function constructor that uses STACK as bitmap memory stack. */
259 sem_function::sem_function (bitmap_obstack *stack): sem_item (FUNC, stack),
260 m_checker (NULL), m_compared_func (NULL)
262 bb_sizes.create (0);
263 bb_sorted.create (0);
266 /* Constructor based on callgraph node _NODE with computed hash _HASH.
267 Bitmap STACK is used for memory allocation. */
268 sem_function::sem_function (cgraph_node *node, hashval_t hash,
269 bitmap_obstack *stack):
270 sem_item (FUNC, node, hash, stack),
271 m_checker (NULL), m_compared_func (NULL)
273 bb_sizes.create (0);
274 bb_sorted.create (0);
277 sem_function::~sem_function ()
279 for (unsigned i = 0; i < bb_sorted.length (); i++)
280 delete (bb_sorted[i]);
282 bb_sizes.release ();
283 bb_sorted.release ();
286 /* Calculates hash value based on a BASIC_BLOCK. */
288 hashval_t
289 sem_function::get_bb_hash (const sem_bb *basic_block)
291 inchash::hash hstate;
293 hstate.add_int (basic_block->nondbg_stmt_count);
294 hstate.add_int (basic_block->edge_count);
296 return hstate.end ();
299 /* References independent hash function. */
301 hashval_t
302 sem_function::get_hash (void)
304 if(!hash)
306 inchash::hash hstate;
307 hstate.add_int (177454); /* Random number for function type. */
309 hstate.add_int (arg_count);
310 hstate.add_int (cfg_checksum);
311 hstate.add_int (gcode_hash);
313 for (unsigned i = 0; i < bb_sorted.length (); i++)
314 hstate.merge_hash (get_bb_hash (bb_sorted[i]));
316 for (unsigned i = 0; i < bb_sizes.length (); i++)
317 hstate.add_int (bb_sizes[i]);
320 /* Add common features of declaration itself. */
321 if (DECL_FUNCTION_SPECIFIC_TARGET (decl))
322 hstate.add_wide_int
323 (cl_target_option_hash
324 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl))));
325 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))
326 (cl_optimization_hash
327 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))));
328 hstate.add_flag (DECL_CXX_CONSTRUCTOR_P (decl));
329 hstate.add_flag (DECL_CXX_DESTRUCTOR_P (decl));
331 hash = hstate.end ();
334 return hash;
337 /* Return ture if A1 and A2 represent equivalent function attribute lists.
338 Based on comp_type_attributes. */
340 bool
341 sem_item::compare_attributes (const_tree a1, const_tree a2)
343 const_tree a;
344 if (a1 == a2)
345 return true;
346 for (a = a1; a != NULL_TREE; a = TREE_CHAIN (a))
348 const struct attribute_spec *as;
349 const_tree attr;
351 as = lookup_attribute_spec (get_attribute_name (a));
352 /* TODO: We can introduce as->affects_decl_identity
353 and as->affects_decl_reference_identity if attribute mismatch
354 gets a common reason to give up on merging. It may not be worth
355 the effort.
356 For example returns_nonnull affects only references, while
357 optimize attribute can be ignored because it is already lowered
358 into flags representation and compared separately. */
359 if (!as)
360 continue;
362 attr = lookup_attribute (as->name, CONST_CAST_TREE (a2));
363 if (!attr || !attribute_value_equal (a, attr))
364 break;
366 if (!a)
368 for (a = a2; a != NULL_TREE; a = TREE_CHAIN (a))
370 const struct attribute_spec *as;
372 as = lookup_attribute_spec (get_attribute_name (a));
373 if (!as)
374 continue;
376 if (!lookup_attribute (as->name, CONST_CAST_TREE (a1)))
377 break;
378 /* We don't need to compare trees again, as we did this
379 already in first loop. */
381 if (!a)
382 return true;
384 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
385 return false;
388 /* Compare properties of symbols N1 and N2 that does not affect semantics of
389 symbol itself but affects semantics of its references from USED_BY (which
390 may be NULL if it is unknown). If comparsion is false, symbols
391 can still be merged but any symbols referring them can't.
393 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
395 TODO: We can also split attributes to those that determine codegen of
396 a function body/variable constructor itself and those that are used when
397 referring to it. */
399 bool
400 sem_item::compare_referenced_symbol_properties (symtab_node *used_by,
401 symtab_node *n1,
402 symtab_node *n2,
403 bool address)
405 if (is_a <cgraph_node *> (n1))
407 /* Inline properties matters: we do now want to merge uses of inline
408 function to uses of normal function because inline hint would be lost.
409 We however can merge inline function to noinline because the alias
410 will keep its DECL_DECLARED_INLINE flag.
412 Also ignore inline flag when optimizing for size or when function
413 is known to not be inlinable.
415 TODO: the optimize_size checks can also be assumed to be true if
416 unit has no !optimize_size functions. */
418 if ((!used_by || address || !is_a <cgraph_node *> (used_by)
419 || !opt_for_fn (used_by->decl, optimize_size))
420 && !opt_for_fn (n1->decl, optimize_size)
421 && n1->get_availability () > AVAIL_INTERPOSABLE
422 && (!DECL_UNINLINABLE (n1->decl) || !DECL_UNINLINABLE (n2->decl)))
424 if (DECL_DISREGARD_INLINE_LIMITS (n1->decl)
425 != DECL_DISREGARD_INLINE_LIMITS (n2->decl))
426 return return_false_with_msg
427 ("DECL_DISREGARD_INLINE_LIMITS are different");
429 if (DECL_DECLARED_INLINE_P (n1->decl)
430 != DECL_DECLARED_INLINE_P (n2->decl))
431 return return_false_with_msg ("inline attributes are different");
434 if (DECL_IS_OPERATOR_NEW (n1->decl)
435 != DECL_IS_OPERATOR_NEW (n2->decl))
436 return return_false_with_msg ("operator new flags are different");
439 /* Merging two definitions with a reference to equivalent vtables, but
440 belonging to a different type may result in ipa-polymorphic-call analysis
441 giving a wrong answer about the dynamic type of instance. */
442 if (is_a <varpool_node *> (n1))
444 if ((DECL_VIRTUAL_P (n1->decl) || DECL_VIRTUAL_P (n2->decl))
445 && (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl)
446 || !types_must_be_same_for_odr (DECL_CONTEXT (n1->decl),
447 DECL_CONTEXT (n2->decl)))
448 && (!used_by || !is_a <cgraph_node *> (used_by) || address
449 || opt_for_fn (used_by->decl, flag_devirtualize)))
450 return return_false_with_msg
451 ("references to virtual tables can not be merged");
453 if (address && DECL_ALIGN (n1->decl) != DECL_ALIGN (n2->decl))
454 return return_false_with_msg ("alignment mismatch");
456 /* For functions we compare attributes in equals_wpa, because we do
457 not know what attributes may cause codegen differences, but for
458 variables just compare attributes for references - the codegen
459 for constructors is affected only by those attributes that we lower
460 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
461 if (!compare_attributes (DECL_ATTRIBUTES (n1->decl),
462 DECL_ATTRIBUTES (n2->decl)))
463 return return_false_with_msg ("different var decl attributes");
464 if (comp_type_attributes (TREE_TYPE (n1->decl),
465 TREE_TYPE (n2->decl)) != 1)
466 return return_false_with_msg ("different var type attributes");
469 /* When matching virtual tables, be sure to also match information
470 relevant for polymorphic call analysis. */
471 if (used_by && is_a <varpool_node *> (used_by)
472 && DECL_VIRTUAL_P (used_by->decl))
474 if (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl))
475 return return_false_with_msg ("virtual flag mismatch");
476 if (DECL_VIRTUAL_P (n1->decl) && is_a <cgraph_node *> (n1)
477 && (DECL_FINAL_P (n1->decl) != DECL_FINAL_P (n2->decl)))
478 return return_false_with_msg ("final flag mismatch");
480 return true;
483 /* Hash properties that are compared by compare_referenced_symbol_properties. */
485 void
486 sem_item::hash_referenced_symbol_properties (symtab_node *ref,
487 inchash::hash &hstate,
488 bool address)
490 if (is_a <cgraph_node *> (ref))
492 if ((type != FUNC || address || !opt_for_fn (decl, optimize_size))
493 && !opt_for_fn (ref->decl, optimize_size)
494 && !DECL_UNINLINABLE (ref->decl))
496 hstate.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref->decl));
497 hstate.add_flag (DECL_DECLARED_INLINE_P (ref->decl));
499 hstate.add_flag (DECL_IS_OPERATOR_NEW (ref->decl));
501 else if (is_a <varpool_node *> (ref))
503 hstate.add_flag (DECL_VIRTUAL_P (ref->decl));
504 if (address)
505 hstate.add_int (DECL_ALIGN (ref->decl));
510 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
511 point to a same function. Comparison can be skipped if IGNORED_NODES
512 contains these nodes. ADDRESS indicate if address is taken. */
514 bool
515 sem_item::compare_symbol_references (
516 hash_map <symtab_node *, sem_item *> &ignored_nodes,
517 symtab_node *n1, symtab_node *n2, bool address)
519 enum availability avail1, avail2;
521 if (n1 == n2)
522 return true;
524 /* Never match variable and function. */
525 if (is_a <varpool_node *> (n1) != is_a <varpool_node *> (n2))
526 return false;
528 if (!compare_referenced_symbol_properties (node, n1, n2, address))
529 return false;
530 if (address && n1->equal_address_to (n2) == 1)
531 return true;
532 if (!address && n1->semantically_equivalent_p (n2))
533 return true;
535 n1 = n1->ultimate_alias_target (&avail1);
536 n2 = n2->ultimate_alias_target (&avail2);
538 if (avail1 >= AVAIL_INTERPOSABLE && ignored_nodes.get (n1)
539 && avail2 >= AVAIL_INTERPOSABLE && ignored_nodes.get (n2))
540 return true;
542 return return_false_with_msg ("different references");
545 /* If cgraph edges E1 and E2 are indirect calls, verify that
546 ECF flags are the same. */
548 bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
550 if (e1->indirect_info && e2->indirect_info)
552 int e1_flags = e1->indirect_info->ecf_flags;
553 int e2_flags = e2->indirect_info->ecf_flags;
555 if (e1_flags != e2_flags)
556 return return_false_with_msg ("ICF flags are different");
558 else if (e1->indirect_info || e2->indirect_info)
559 return false;
561 return true;
564 /* Return true if parameter I may be used. */
566 bool
567 sem_function::param_used_p (unsigned int i)
569 if (ipa_node_params_sum == NULL)
570 return false;
572 struct ipa_node_params *parms_info = IPA_NODE_REF (get_node ());
574 if (parms_info->descriptors.is_empty ()
575 || parms_info->descriptors.length () <= i)
576 return true;
578 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i);
581 /* Perform additional check needed to match types function parameters that are
582 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
583 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
585 bool
586 sem_function::compatible_parm_types_p (tree parm1, tree parm2)
588 /* Be sure that parameters are TBAA compatible. */
589 if (!func_checker::compatible_types_p (parm1, parm2))
590 return return_false_with_msg ("parameter type is not compatible");
592 if (POINTER_TYPE_P (parm1)
593 && (TYPE_RESTRICT (parm1) != TYPE_RESTRICT (parm2)))
594 return return_false_with_msg ("argument restrict flag mismatch");
596 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
597 if (POINTER_TYPE_P (parm1)
598 && TREE_CODE (parm1) != TREE_CODE (parm2)
599 && opt_for_fn (decl, flag_delete_null_pointer_checks))
600 return return_false_with_msg ("pointer wrt reference mismatch");
602 return true;
605 /* Fast equality function based on knowledge known in WPA. */
607 bool
608 sem_function::equals_wpa (sem_item *item,
609 hash_map <symtab_node *, sem_item *> &ignored_nodes)
611 gcc_assert (item->type == FUNC);
612 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
613 cgraph_node *cnode2 = dyn_cast <cgraph_node *> (item->node);
615 m_compared_func = static_cast<sem_function *> (item);
617 if (cnode->thunk.thunk_p != cnode2->thunk.thunk_p)
618 return return_false_with_msg ("thunk_p mismatch");
620 if (cnode->thunk.thunk_p)
622 if (cnode->thunk.fixed_offset != cnode2->thunk.fixed_offset)
623 return return_false_with_msg ("thunk fixed_offset mismatch");
624 if (cnode->thunk.virtual_value != cnode2->thunk.virtual_value)
625 return return_false_with_msg ("thunk virtual_value mismatch");
626 if (cnode->thunk.this_adjusting != cnode2->thunk.this_adjusting)
627 return return_false_with_msg ("thunk this_adjusting mismatch");
628 if (cnode->thunk.virtual_offset_p != cnode2->thunk.virtual_offset_p)
629 return return_false_with_msg ("thunk virtual_offset_p mismatch");
630 if (cnode->thunk.add_pointer_bounds_args
631 != cnode2->thunk.add_pointer_bounds_args)
632 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
635 /* Compare special function DECL attributes. */
636 if (DECL_FUNCTION_PERSONALITY (decl)
637 != DECL_FUNCTION_PERSONALITY (item->decl))
638 return return_false_with_msg ("function personalities are different");
640 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
641 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item->decl))
642 return return_false_with_msg ("intrument function entry exit "
643 "attributes are different");
645 if (DECL_NO_LIMIT_STACK (decl) != DECL_NO_LIMIT_STACK (item->decl))
646 return return_false_with_msg ("no stack limit attributes are different");
648 if (DECL_CXX_CONSTRUCTOR_P (decl) != DECL_CXX_CONSTRUCTOR_P (item->decl))
649 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
651 if (DECL_CXX_DESTRUCTOR_P (decl) != DECL_CXX_DESTRUCTOR_P (item->decl))
652 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
654 /* TODO: pure/const flags mostly matters only for references, except for
655 the fact that codegen takes LOOPING flag as a hint that loops are
656 finite. We may arrange the code to always pick leader that has least
657 specified flags and then this can go into comparing symbol properties. */
658 if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
659 return return_false_with_msg ("decl_or_type flags are different");
661 /* Do not match polymorphic constructors of different types. They calls
662 type memory location for ipa-polymorphic-call and we do not want
663 it to get confused by wrong type. */
664 if (DECL_CXX_CONSTRUCTOR_P (decl)
665 && TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE)
667 if (TREE_CODE (TREE_TYPE (item->decl)) != METHOD_TYPE)
668 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
669 else if (!func_checker::compatible_polymorphic_types_p
670 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
671 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
672 return return_false_with_msg ("ctor polymorphic type mismatch");
675 /* Checking function TARGET and OPTIMIZATION flags. */
676 cl_target_option *tar1 = target_opts_for_fn (decl);
677 cl_target_option *tar2 = target_opts_for_fn (item->decl);
679 if (tar1 != tar2 && !cl_target_option_eq (tar1, tar2))
681 if (dump_file && (dump_flags & TDF_DETAILS))
683 fprintf (dump_file, "target flags difference");
684 cl_target_option_print_diff (dump_file, 2, tar1, tar2);
687 return return_false_with_msg ("Target flags are different");
690 cl_optimization *opt1 = opts_for_fn (decl);
691 cl_optimization *opt2 = opts_for_fn (item->decl);
693 if (opt1 != opt2 && memcmp (opt1, opt2, sizeof(cl_optimization)))
695 if (dump_file && (dump_flags & TDF_DETAILS))
697 fprintf (dump_file, "optimization flags difference");
698 cl_optimization_print_diff (dump_file, 2, opt1, opt2);
701 return return_false_with_msg ("optimization flags are different");
704 /* Result type checking. */
705 if (!func_checker::compatible_types_p
706 (TREE_TYPE (TREE_TYPE (decl)),
707 TREE_TYPE (TREE_TYPE (m_compared_func->decl))))
708 return return_false_with_msg ("result types are different");
710 /* Checking types of arguments. */
711 tree list1 = TYPE_ARG_TYPES (TREE_TYPE (decl)),
712 list2 = TYPE_ARG_TYPES (TREE_TYPE (m_compared_func->decl));
713 for (unsigned i = 0; list1 && list2;
714 list1 = TREE_CHAIN (list1), list2 = TREE_CHAIN (list2), i++)
716 tree parm1 = TREE_VALUE (list1);
717 tree parm2 = TREE_VALUE (list2);
719 /* This guard is here for function pointer with attributes (pr59927.c). */
720 if (!parm1 || !parm2)
721 return return_false_with_msg ("NULL argument type");
723 /* Verify that types are compatible to ensure that both functions
724 have same calling conventions. */
725 if (!types_compatible_p (parm1, parm2))
726 return return_false_with_msg ("parameter types are not compatible");
728 if (!param_used_p (i))
729 continue;
731 /* Perform additional checks for used parameters. */
732 if (!compatible_parm_types_p (parm1, parm2))
733 return false;
736 if (list1 || list2)
737 return return_false_with_msg ("Mismatched number of parameters");
739 if (node->num_references () != item->node->num_references ())
740 return return_false_with_msg ("different number of references");
742 /* Checking function attributes.
743 This is quadratic in number of attributes */
744 if (comp_type_attributes (TREE_TYPE (decl),
745 TREE_TYPE (item->decl)) != 1)
746 return return_false_with_msg ("different type attributes");
747 if (!compare_attributes (DECL_ATTRIBUTES (decl),
748 DECL_ATTRIBUTES (item->decl)))
749 return return_false_with_msg ("different decl attributes");
751 /* The type of THIS pointer type memory location for
752 ipa-polymorphic-call-analysis. */
753 if (opt_for_fn (decl, flag_devirtualize)
754 && (TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE
755 || TREE_CODE (TREE_TYPE (item->decl)) == METHOD_TYPE)
756 && param_used_p (0)
757 && compare_polymorphic_p ())
759 if (TREE_CODE (TREE_TYPE (decl)) != TREE_CODE (TREE_TYPE (item->decl)))
760 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
761 if (!func_checker::compatible_polymorphic_types_p
762 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
763 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
764 return return_false_with_msg ("THIS pointer ODR type mismatch");
767 ipa_ref *ref = NULL, *ref2 = NULL;
768 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
770 item->node->iterate_reference (i, ref2);
772 if (ref->use != ref2->use)
773 return return_false_with_msg ("reference use mismatch");
775 if (!compare_symbol_references (ignored_nodes, ref->referred,
776 ref2->referred,
777 ref->address_matters_p ()))
778 return false;
781 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
782 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
784 while (e1 && e2)
786 if (!compare_symbol_references (ignored_nodes, e1->callee,
787 e2->callee, false))
788 return false;
789 if (!compare_edge_flags (e1, e2))
790 return false;
792 e1 = e1->next_callee;
793 e2 = e2->next_callee;
796 if (e1 || e2)
797 return return_false_with_msg ("different number of calls");
799 e1 = dyn_cast <cgraph_node *> (node)->indirect_calls;
800 e2 = dyn_cast <cgraph_node *> (item->node)->indirect_calls;
802 while (e1 && e2)
804 if (!compare_edge_flags (e1, e2))
805 return false;
807 e1 = e1->next_callee;
808 e2 = e2->next_callee;
811 if (e1 || e2)
812 return return_false_with_msg ("different number of indirect calls");
814 return true;
817 /* Update hash by address sensitive references. We iterate over all
818 sensitive references (address_matters_p) and we hash ultime alias
819 target of these nodes, which can improve a semantic item hash.
821 Also hash in referenced symbols properties. This can be done at any time
822 (as the properties should not change), but it is convenient to do it here
823 while we walk the references anyway. */
825 void
826 sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
827 sem_item *> &m_symtab_node_map)
829 ipa_ref* ref;
830 inchash::hash hstate (hash);
832 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
834 hstate.add_int (ref->use);
835 hash_referenced_symbol_properties (ref->referred, hstate,
836 ref->use == IPA_REF_ADDR);
837 if (ref->address_matters_p () || !m_symtab_node_map.get (ref->referred))
838 hstate.add_int (ref->referred->ultimate_alias_target ()->order);
841 if (is_a <cgraph_node *> (node))
843 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
844 e = e->next_caller)
846 sem_item **result = m_symtab_node_map.get (e->callee);
847 hash_referenced_symbol_properties (e->callee, hstate, false);
848 if (!result)
849 hstate.add_int (e->callee->ultimate_alias_target ()->order);
853 hash = hstate.end ();
856 /* Update hash by computed local hash values taken from different
857 semantic items.
858 TODO: stronger SCC based hashing would be desirable here. */
860 void
861 sem_item::update_hash_by_local_refs (hash_map <symtab_node *,
862 sem_item *> &m_symtab_node_map)
864 ipa_ref* ref;
865 inchash::hash state (hash);
867 for (unsigned j = 0; node->iterate_reference (j, ref); j++)
869 sem_item **result = m_symtab_node_map.get (ref->referring);
870 if (result)
871 state.merge_hash ((*result)->hash);
874 if (type == FUNC)
876 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e;
877 e = e->next_callee)
879 sem_item **result = m_symtab_node_map.get (e->caller);
880 if (result)
881 state.merge_hash ((*result)->hash);
885 global_hash = state.end ();
888 /* Returns true if the item equals to ITEM given as argument. */
890 bool
891 sem_function::equals (sem_item *item,
892 hash_map <symtab_node *, sem_item *> &)
894 gcc_assert (item->type == FUNC);
895 bool eq = equals_private (item);
897 if (m_checker != NULL)
899 delete m_checker;
900 m_checker = NULL;
903 if (dump_file && (dump_flags & TDF_DETAILS))
904 fprintf (dump_file,
905 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
906 xstrdup_for_dump (node->name()),
907 xstrdup_for_dump (item->node->name ()),
908 node->order,
909 item->node->order,
910 xstrdup_for_dump (node->asm_name ()),
911 xstrdup_for_dump (item->node->asm_name ()),
912 eq ? "true" : "false");
914 return eq;
917 /* Processes function equality comparison. */
919 bool
920 sem_function::equals_private (sem_item *item)
922 if (item->type != FUNC)
923 return false;
925 basic_block bb1, bb2;
926 edge e1, e2;
927 edge_iterator ei1, ei2;
928 bool result = true;
929 tree arg1, arg2;
931 m_compared_func = static_cast<sem_function *> (item);
933 gcc_assert (decl != item->decl);
935 if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
936 || edge_count != m_compared_func->edge_count
937 || cfg_checksum != m_compared_func->cfg_checksum)
938 return return_false ();
940 m_checker = new func_checker (decl, m_compared_func->decl,
941 compare_polymorphic_p (),
942 false,
943 &refs_set,
944 &m_compared_func->refs_set);
945 arg1 = DECL_ARGUMENTS (decl);
946 arg2 = DECL_ARGUMENTS (m_compared_func->decl);
947 for (unsigned i = 0;
948 arg1 && arg2; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2), i++)
950 if (!types_compatible_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
951 return return_false_with_msg ("argument types are not compatible");
952 if (!param_used_p (i))
953 continue;
954 /* Perform additional checks for used parameters. */
955 if (!compatible_parm_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
956 return false;
957 if (!m_checker->compare_decl (arg1, arg2))
958 return return_false ();
960 if (arg1 || arg2)
961 return return_false_with_msg ("Mismatched number of arguments");
963 if (!dyn_cast <cgraph_node *> (node)->has_gimple_body_p ())
964 return true;
966 /* Fill-up label dictionary. */
967 for (unsigned i = 0; i < bb_sorted.length (); ++i)
969 m_checker->parse_labels (bb_sorted[i]);
970 m_checker->parse_labels (m_compared_func->bb_sorted[i]);
973 /* Checking all basic blocks. */
974 for (unsigned i = 0; i < bb_sorted.length (); ++i)
975 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
976 return return_false();
978 dump_message ("All BBs are equal\n");
980 auto_vec <int> bb_dict;
982 /* Basic block edges check. */
983 for (unsigned i = 0; i < bb_sorted.length (); ++i)
985 bb1 = bb_sorted[i]->bb;
986 bb2 = m_compared_func->bb_sorted[i]->bb;
988 ei2 = ei_start (bb2->preds);
990 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
992 ei_cond (ei2, &e2);
994 if (e1->flags != e2->flags)
995 return return_false_with_msg ("flags comparison returns false");
997 if (!bb_dict_test (&bb_dict, e1->src->index, e2->src->index))
998 return return_false_with_msg ("edge comparison returns false");
1000 if (!bb_dict_test (&bb_dict, e1->dest->index, e2->dest->index))
1001 return return_false_with_msg ("BB comparison returns false");
1003 if (!m_checker->compare_edge (e1, e2))
1004 return return_false_with_msg ("edge comparison returns false");
1006 ei_next (&ei2);
1010 /* Basic block PHI nodes comparison. */
1011 for (unsigned i = 0; i < bb_sorted.length (); i++)
1012 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
1013 return return_false_with_msg ("PHI node comparison returns false");
1015 return result;
1018 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
1019 Helper for call_for_symbol_thunks_and_aliases. */
1021 static bool
1022 set_local (cgraph_node *node, void *data)
1024 node->local.local = data != NULL;
1025 return false;
1028 /* TREE_ADDRESSABLE of NODE to true.
1029 Helper for call_for_symbol_thunks_and_aliases. */
1031 static bool
1032 set_addressable (varpool_node *node, void *)
1034 TREE_ADDRESSABLE (node->decl) = 1;
1035 return false;
1038 /* Clear DECL_RTL of NODE.
1039 Helper for call_for_symbol_thunks_and_aliases. */
1041 static bool
1042 clear_decl_rtl (symtab_node *node, void *)
1044 SET_DECL_RTL (node->decl, NULL);
1045 return false;
1048 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1049 possible. Return number of redirections made. */
1051 static int
1052 redirect_all_callers (cgraph_node *n, cgraph_node *to)
1054 int nredirected = 0;
1055 ipa_ref *ref;
1056 cgraph_edge *e = n->callers;
1058 while (e)
1060 /* Redirecting thunks to interposable symbols or symbols in other sections
1061 may not be supported by target output code. Play safe for now and
1062 punt on redirection. */
1063 if (!e->caller->thunk.thunk_p)
1065 struct cgraph_edge *nexte = e->next_caller;
1066 e->redirect_callee (to);
1067 e = nexte;
1068 nredirected++;
1070 else
1071 e = e->next_callee;
1073 for (unsigned i = 0; n->iterate_direct_aliases (i, ref);)
1075 bool removed = false;
1076 cgraph_node *n_alias = dyn_cast <cgraph_node *> (ref->referring);
1078 if ((DECL_COMDAT_GROUP (n->decl)
1079 && (DECL_COMDAT_GROUP (n->decl)
1080 == DECL_COMDAT_GROUP (n_alias->decl)))
1081 || (n_alias->get_availability () > AVAIL_INTERPOSABLE
1082 && n->get_availability () > AVAIL_INTERPOSABLE))
1084 nredirected += redirect_all_callers (n_alias, to);
1085 if (n_alias->can_remove_if_no_direct_calls_p ()
1086 && !n_alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1087 NULL, true)
1088 && !n_alias->has_aliases_p ())
1089 n_alias->remove ();
1091 if (!removed)
1092 i++;
1094 return nredirected;
1097 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1098 be applied. */
1100 bool
1101 sem_function::merge (sem_item *alias_item)
1103 gcc_assert (alias_item->type == FUNC);
1105 sem_function *alias_func = static_cast<sem_function *> (alias_item);
1107 cgraph_node *original = get_node ();
1108 cgraph_node *local_original = NULL;
1109 cgraph_node *alias = alias_func->get_node ();
1111 bool create_wrapper = false;
1112 bool create_alias = false;
1113 bool redirect_callers = false;
1114 bool remove = false;
1116 bool original_discardable = false;
1117 bool original_discarded = false;
1119 bool original_address_matters = original->address_matters_p ();
1120 bool alias_address_matters = alias->address_matters_p ();
1122 if (DECL_EXTERNAL (alias->decl))
1124 if (dump_file)
1125 fprintf (dump_file, "Not unifying; alias is external.\n\n");
1126 return false;
1129 if (DECL_NO_INLINE_WARNING_P (original->decl)
1130 != DECL_NO_INLINE_WARNING_P (alias->decl))
1132 if (dump_file)
1133 fprintf (dump_file,
1134 "Not unifying; "
1135 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1136 return false;
1139 /* Do not attempt to mix functions from different user sections;
1140 we do not know what user intends with those. */
1141 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
1142 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
1143 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
1145 if (dump_file)
1146 fprintf (dump_file,
1147 "Not unifying; "
1148 "original and alias are in different sections.\n\n");
1149 return false;
1152 /* See if original is in a section that can be discarded if the main
1153 symbol is not used. */
1155 if (original->can_be_discarded_p ())
1156 original_discardable = true;
1157 /* Also consider case where we have resolution info and we know that
1158 original's definition is not going to be used. In this case we can not
1159 create alias to original. */
1160 if (node->resolution != LDPR_UNKNOWN
1161 && !decl_binds_to_current_def_p (node->decl))
1162 original_discardable = original_discarded = true;
1164 /* Creating a symtab alias is the optimal way to merge.
1165 It however can not be used in the following cases:
1167 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1168 2) if ORIGINAL is in a section that may be discarded by linker or if
1169 it is an external functions where we can not create an alias
1170 (ORIGINAL_DISCARDABLE)
1171 3) if target do not support symbol aliases.
1172 4) original and alias lie in different comdat groups.
1174 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1175 and/or redirect all callers from ALIAS to ORIGINAL. */
1176 if ((original_address_matters && alias_address_matters)
1177 || (original_discardable
1178 && (!DECL_COMDAT_GROUP (alias->decl)
1179 || (DECL_COMDAT_GROUP (alias->decl)
1180 != DECL_COMDAT_GROUP (original->decl))))
1181 || original_discarded
1182 || !sem_item::target_supports_symbol_aliases_p ()
1183 || DECL_COMDAT_GROUP (alias->decl) != DECL_COMDAT_GROUP (original->decl))
1185 /* First see if we can produce wrapper. */
1187 /* Symbol properties that matter for references must be preserved.
1188 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1189 with proper properties. */
1190 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1191 alias->address_taken))
1193 if (dump_file)
1194 fprintf (dump_file,
1195 "Wrapper cannot be created because referenced symbol "
1196 "properties mismatch\n");
1198 /* Do not turn function in one comdat group into wrapper to another
1199 comdat group. Other compiler producing the body of the
1200 another comdat group may make opossite decision and with unfortunate
1201 linker choices this may close a loop. */
1202 else if (DECL_COMDAT_GROUP (original->decl)
1203 && DECL_COMDAT_GROUP (alias->decl)
1204 && (DECL_COMDAT_GROUP (alias->decl)
1205 != DECL_COMDAT_GROUP (original->decl)))
1207 if (dump_file)
1208 fprintf (dump_file,
1209 "Wrapper cannot be created because of COMDAT\n");
1211 else if (DECL_STATIC_CHAIN (alias->decl))
1213 if (dump_file)
1214 fprintf (dump_file,
1215 "Can not create wrapper of nested functions.\n");
1217 /* TODO: We can also deal with variadic functions never calling
1218 VA_START. */
1219 else if (stdarg_p (TREE_TYPE (alias->decl)))
1221 if (dump_file)
1222 fprintf (dump_file,
1223 "can not create wrapper of stdarg function.\n");
1225 else if (inline_summaries
1226 && inline_summaries->get (alias)->self_size <= 2)
1228 if (dump_file)
1229 fprintf (dump_file, "Wrapper creation is not "
1230 "profitable (function is too small).\n");
1232 /* If user paid attention to mark function noinline, assume it is
1233 somewhat special and do not try to turn it into a wrapper that can
1234 not be undone by inliner. */
1235 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
1237 if (dump_file)
1238 fprintf (dump_file, "Wrappers are not created for noinline.\n");
1240 else
1241 create_wrapper = true;
1243 /* We can redirect local calls in the case both alias and orignal
1244 are not interposable. */
1245 redirect_callers
1246 = alias->get_availability () > AVAIL_INTERPOSABLE
1247 && original->get_availability () > AVAIL_INTERPOSABLE
1248 && !alias->instrumented_version;
1249 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1250 with proper properties. */
1251 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1252 alias->address_taken))
1253 redirect_callers = false;
1255 if (!redirect_callers && !create_wrapper)
1257 if (dump_file)
1258 fprintf (dump_file, "Not unifying; can not redirect callers nor "
1259 "produce wrapper\n\n");
1260 return false;
1263 /* Work out the symbol the wrapper should call.
1264 If ORIGINAL is interposable, we need to call a local alias.
1265 Also produce local alias (if possible) as an optimization.
1267 Local aliases can not be created inside comdat groups because that
1268 prevents inlining. */
1269 if (!original_discardable && !original->get_comdat_group ())
1271 local_original
1272 = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
1273 if (!local_original
1274 && original->get_availability () > AVAIL_INTERPOSABLE)
1275 local_original = original;
1277 /* If we can not use local alias, fallback to the original
1278 when possible. */
1279 else if (original->get_availability () > AVAIL_INTERPOSABLE)
1280 local_original = original;
1282 /* If original is COMDAT local, we can not really redirect calls outside
1283 of its comdat group to it. */
1284 if (original->comdat_local_p ())
1285 redirect_callers = false;
1286 if (!local_original)
1288 if (dump_file)
1289 fprintf (dump_file, "Not unifying; "
1290 "can not produce local alias.\n\n");
1291 return false;
1294 if (!redirect_callers && !create_wrapper)
1296 if (dump_file)
1297 fprintf (dump_file, "Not unifying; "
1298 "can not redirect callers nor produce a wrapper\n\n");
1299 return false;
1301 if (!create_wrapper
1302 && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1303 NULL, true)
1304 && !alias->can_remove_if_no_direct_calls_p ())
1306 if (dump_file)
1307 fprintf (dump_file, "Not unifying; can not make wrapper and "
1308 "function has other uses than direct calls\n\n");
1309 return false;
1312 else
1313 create_alias = true;
1315 if (redirect_callers)
1317 int nredirected = redirect_all_callers (alias, local_original);
1319 if (nredirected)
1321 alias->icf_merged = true;
1322 local_original->icf_merged = true;
1324 if (dump_file && nredirected)
1325 fprintf (dump_file, "%i local calls have been "
1326 "redirected.\n", nredirected);
1329 /* If all callers was redirected, do not produce wrapper. */
1330 if (alias->can_remove_if_no_direct_calls_p ()
1331 && !alias->has_aliases_p ())
1333 create_wrapper = false;
1334 remove = true;
1336 gcc_assert (!create_alias);
1338 else if (create_alias)
1340 alias->icf_merged = true;
1342 /* Remove the function's body. */
1343 ipa_merge_profiles (original, alias);
1344 alias->release_body (true);
1345 alias->reset ();
1346 /* Notice global symbol possibly produced RTL. */
1347 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
1348 NULL, true);
1350 /* Create the alias. */
1351 cgraph_node::create_alias (alias_func->decl, decl);
1352 alias->resolve_alias (original);
1354 original->call_for_symbol_thunks_and_aliases
1355 (set_local, (void *)(size_t) original->local_p (), true);
1357 if (dump_file)
1358 fprintf (dump_file, "Unified; Function alias has been created.\n\n");
1360 if (create_wrapper)
1362 gcc_assert (!create_alias);
1363 alias->icf_merged = true;
1364 local_original->icf_merged = true;
1366 ipa_merge_profiles (local_original, alias, true);
1367 alias->create_wrapper (local_original);
1369 if (dump_file)
1370 fprintf (dump_file, "Unified; Wrapper has been created.\n\n");
1373 /* It's possible that redirection can hit thunks that block
1374 redirection opportunities. */
1375 gcc_assert (alias->icf_merged || remove || redirect_callers);
1376 original->icf_merged = true;
1378 /* Inform the inliner about cross-module merging. */
1379 if ((original->lto_file_data || alias->lto_file_data)
1380 && original->lto_file_data != alias->lto_file_data)
1381 local_original->merged = original->merged = true;
1383 if (remove)
1385 ipa_merge_profiles (original, alias);
1386 alias->release_body ();
1387 alias->reset ();
1388 alias->body_removed = true;
1389 alias->icf_merged = true;
1390 if (dump_file)
1391 fprintf (dump_file, "Unified; Function body was removed.\n");
1394 return true;
1397 /* Semantic item initialization function. */
1399 void
1400 sem_function::init (void)
1402 if (in_lto_p)
1403 get_node ()->get_untransformed_body ();
1405 tree fndecl = node->decl;
1406 function *func = DECL_STRUCT_FUNCTION (fndecl);
1408 gcc_assert (func);
1409 gcc_assert (SSANAMES (func));
1411 ssa_names_size = SSANAMES (func)->length ();
1412 node = node;
1414 decl = fndecl;
1415 region_tree = func->eh->region_tree;
1417 /* iterating all function arguments. */
1418 arg_count = count_formal_params (fndecl);
1420 edge_count = n_edges_for_fn (func);
1421 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1422 if (!cnode->thunk.thunk_p)
1424 cfg_checksum = coverage_compute_cfg_checksum (func);
1426 inchash::hash hstate;
1428 basic_block bb;
1429 FOR_EACH_BB_FN (bb, func)
1431 unsigned nondbg_stmt_count = 0;
1433 edge e;
1434 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
1435 ei_next (&ei))
1436 cfg_checksum = iterative_hash_host_wide_int (e->flags,
1437 cfg_checksum);
1439 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1440 gsi_next (&gsi))
1442 gimple stmt = gsi_stmt (gsi);
1444 if (gimple_code (stmt) != GIMPLE_DEBUG
1445 && gimple_code (stmt) != GIMPLE_PREDICT)
1447 hash_stmt (stmt, hstate);
1448 nondbg_stmt_count++;
1452 gcode_hash = hstate.end ();
1453 bb_sizes.safe_push (nondbg_stmt_count);
1455 /* Inserting basic block to hash table. */
1456 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
1457 EDGE_COUNT (bb->preds)
1458 + EDGE_COUNT (bb->succs));
1460 bb_sorted.safe_push (semantic_bb);
1463 else
1465 cfg_checksum = 0;
1466 inchash::hash hstate;
1467 hstate.add_wide_int (cnode->thunk.fixed_offset);
1468 hstate.add_wide_int (cnode->thunk.virtual_value);
1469 hstate.add_flag (cnode->thunk.this_adjusting);
1470 hstate.add_flag (cnode->thunk.virtual_offset_p);
1471 hstate.add_flag (cnode->thunk.add_pointer_bounds_args);
1472 gcode_hash = hstate.end ();
1476 /* Accumulate to HSTATE a hash of expression EXP.
1477 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1478 and DECL equality classes. */
1480 void
1481 sem_item::add_expr (const_tree exp, inchash::hash &hstate)
1483 if (exp == NULL_TREE)
1485 hstate.merge_hash (0);
1486 return;
1489 /* Handled component can be matched in a cureful way proving equivalence
1490 even if they syntactically differ. Just skip them. */
1491 STRIP_NOPS (exp);
1492 while (handled_component_p (exp))
1493 exp = TREE_OPERAND (exp, 0);
1495 enum tree_code code = TREE_CODE (exp);
1496 hstate.add_int (code);
1498 switch (code)
1500 /* Use inchash::add_expr for everything that is LTO stable. */
1501 case VOID_CST:
1502 case INTEGER_CST:
1503 case REAL_CST:
1504 case FIXED_CST:
1505 case STRING_CST:
1506 case COMPLEX_CST:
1507 case VECTOR_CST:
1508 inchash::add_expr (exp, hstate);
1509 break;
1510 case CONSTRUCTOR:
1512 unsigned HOST_WIDE_INT idx;
1513 tree value;
1515 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1517 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp), idx, value)
1518 if (value)
1519 add_expr (value, hstate);
1520 break;
1522 case ADDR_EXPR:
1523 case FDESC_EXPR:
1524 add_expr (get_base_address (TREE_OPERAND (exp, 0)), hstate);
1525 break;
1526 case SSA_NAME:
1527 case VAR_DECL:
1528 case CONST_DECL:
1529 case PARM_DECL:
1530 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1531 break;
1532 case MEM_REF:
1533 case POINTER_PLUS_EXPR:
1534 case MINUS_EXPR:
1535 case RANGE_EXPR:
1536 add_expr (TREE_OPERAND (exp, 0), hstate);
1537 add_expr (TREE_OPERAND (exp, 1), hstate);
1538 break;
1539 case PLUS_EXPR:
1541 inchash::hash one, two;
1542 add_expr (TREE_OPERAND (exp, 0), one);
1543 add_expr (TREE_OPERAND (exp, 1), two);
1544 hstate.add_commutative (one, two);
1546 break;
1547 CASE_CONVERT:
1548 hstate.add_wide_int (int_size_in_bytes (TREE_TYPE (exp)));
1549 return add_expr (TREE_OPERAND (exp, 0), hstate);
1550 default:
1551 break;
1555 /* Accumulate to HSTATE a hash of type t.
1556 TYpes that may end up being compatible after LTO type merging needs to have
1557 the same hash. */
1559 void
1560 sem_item::add_type (const_tree type, inchash::hash &hstate)
1562 if (type == NULL_TREE)
1564 hstate.merge_hash (0);
1565 return;
1568 type = TYPE_MAIN_VARIANT (type);
1569 if (TYPE_CANONICAL (type))
1570 type = TYPE_CANONICAL (type);
1572 if (!AGGREGATE_TYPE_P (type))
1573 hstate.add_int (TYPE_MODE (type));
1575 if (TREE_CODE (type) == COMPLEX_TYPE)
1577 hstate.add_int (COMPLEX_TYPE);
1578 sem_item::add_type (TREE_TYPE (type), hstate);
1580 else if (INTEGRAL_TYPE_P (type))
1582 hstate.add_int (INTEGER_TYPE);
1583 hstate.add_flag (TYPE_UNSIGNED (type));
1584 hstate.add_int (TYPE_PRECISION (type));
1586 else if (VECTOR_TYPE_P (type))
1588 hstate.add_int (VECTOR_TYPE);
1589 hstate.add_int (TYPE_PRECISION (type));
1590 sem_item::add_type (TREE_TYPE (type), hstate);
1592 else if (TREE_CODE (type) == ARRAY_TYPE)
1594 hstate.add_int (ARRAY_TYPE);
1595 /* Do not hash size, so complete and incomplete types can match. */
1596 sem_item::add_type (TREE_TYPE (type), hstate);
1598 else if (RECORD_OR_UNION_TYPE_P (type))
1600 hashval_t *val = optimizer->m_type_hash_cache.get (type);
1602 if (!val)
1604 inchash::hash hstate2;
1605 unsigned nf;
1606 tree f;
1607 hashval_t hash;
1609 hstate2.add_int (RECORD_TYPE);
1610 gcc_assert (COMPLETE_TYPE_P (type));
1612 for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
1613 if (TREE_CODE (f) == FIELD_DECL)
1615 add_type (TREE_TYPE (f), hstate2);
1616 nf++;
1619 hstate2.add_int (nf);
1620 hash = hstate2.end ();
1621 hstate.add_wide_int (hash);
1622 optimizer->m_type_hash_cache.put (type, hash);
1624 else
1625 hstate.add_wide_int (*val);
1629 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1631 void
1632 sem_function::hash_stmt (gimple stmt, inchash::hash &hstate)
1634 enum gimple_code code = gimple_code (stmt);
1636 hstate.add_int (code);
1638 switch (code)
1640 case GIMPLE_SWITCH:
1641 add_expr (gimple_switch_index (as_a <gswitch *> (stmt)), hstate);
1642 break;
1643 case GIMPLE_ASSIGN:
1644 hstate.add_int (gimple_assign_rhs_code (stmt));
1645 if (commutative_tree_code (gimple_assign_rhs_code (stmt))
1646 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1648 inchash::hash one, two;
1650 add_expr (gimple_assign_rhs1 (stmt), one);
1651 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt)), one);
1652 add_expr (gimple_assign_rhs2 (stmt), two);
1653 hstate.add_commutative (one, two);
1654 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1656 add_expr (gimple_assign_rhs3 (stmt), hstate);
1657 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt)), hstate);
1659 add_expr (gimple_assign_lhs (stmt), hstate);
1660 add_type (TREE_TYPE (gimple_assign_lhs (stmt)), two);
1661 break;
1663 /* ... fall through ... */
1664 case GIMPLE_CALL:
1665 case GIMPLE_ASM:
1666 case GIMPLE_COND:
1667 case GIMPLE_GOTO:
1668 case GIMPLE_RETURN:
1669 /* All these statements are equivalent if their operands are. */
1670 for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1672 add_expr (gimple_op (stmt, i), hstate);
1673 if (gimple_op (stmt, i))
1674 add_type (TREE_TYPE (gimple_op (stmt, i)), hstate);
1676 default:
1677 break;
1682 /* Return true if polymorphic comparison must be processed. */
1684 bool
1685 sem_function::compare_polymorphic_p (void)
1687 struct cgraph_edge *e;
1689 if (!opt_for_fn (get_node ()->decl, flag_devirtualize))
1690 return false;
1691 if (get_node ()->indirect_calls != NULL)
1692 return true;
1693 /* TODO: We can do simple propagation determining what calls may lead to
1694 a polymorphic call. */
1695 for (e = get_node ()->callees; e; e = e->next_callee)
1696 if (e->callee->definition
1697 && opt_for_fn (e->callee->decl, flag_devirtualize))
1698 return true;
1699 return false;
1702 /* For a given call graph NODE, the function constructs new
1703 semantic function item. */
1705 sem_function *
1706 sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
1708 tree fndecl = node->decl;
1709 function *func = DECL_STRUCT_FUNCTION (fndecl);
1711 if (!func || (!node->has_gimple_body_p () && !node->thunk.thunk_p))
1712 return NULL;
1714 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
1715 return NULL;
1717 sem_function *f = new sem_function (node, 0, stack);
1719 f->init ();
1721 return f;
1724 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1725 return true if phi nodes are semantically equivalent in these blocks . */
1727 bool
1728 sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
1730 gphi_iterator si1, si2;
1731 gphi *phi1, *phi2;
1732 unsigned size1, size2, i;
1733 tree t1, t2;
1734 edge e1, e2;
1736 gcc_assert (bb1 != NULL);
1737 gcc_assert (bb2 != NULL);
1739 si2 = gsi_start_phis (bb2);
1740 for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
1741 gsi_next (&si1))
1743 gsi_next_nonvirtual_phi (&si1);
1744 gsi_next_nonvirtual_phi (&si2);
1746 if (gsi_end_p (si1) && gsi_end_p (si2))
1747 break;
1749 if (gsi_end_p (si1) || gsi_end_p (si2))
1750 return return_false();
1752 phi1 = si1.phi ();
1753 phi2 = si2.phi ();
1755 tree phi_result1 = gimple_phi_result (phi1);
1756 tree phi_result2 = gimple_phi_result (phi2);
1758 if (!m_checker->compare_operand (phi_result1, phi_result2))
1759 return return_false_with_msg ("PHI results are different");
1761 size1 = gimple_phi_num_args (phi1);
1762 size2 = gimple_phi_num_args (phi2);
1764 if (size1 != size2)
1765 return return_false ();
1767 for (i = 0; i < size1; ++i)
1769 t1 = gimple_phi_arg (phi1, i)->def;
1770 t2 = gimple_phi_arg (phi2, i)->def;
1772 if (!m_checker->compare_operand (t1, t2))
1773 return return_false ();
1775 e1 = gimple_phi_arg_edge (phi1, i);
1776 e2 = gimple_phi_arg_edge (phi2, i);
1778 if (!m_checker->compare_edge (e1, e2))
1779 return return_false ();
1782 gsi_next (&si2);
1785 return true;
1788 /* Returns true if tree T can be compared as a handled component. */
1790 bool
1791 sem_function::icf_handled_component_p (tree t)
1793 tree_code tc = TREE_CODE (t);
1795 return (handled_component_p (t)
1796 || tc == ADDR_EXPR || tc == MEM_REF || tc == OBJ_TYPE_REF);
1799 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1800 corresponds to TARGET. */
1802 bool
1803 sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
1805 source++;
1806 target++;
1808 if (bb_dict->length () <= (unsigned)source)
1809 bb_dict->safe_grow_cleared (source + 1);
1811 if ((*bb_dict)[source] == 0)
1813 (*bb_dict)[source] = target;
1814 return true;
1816 else
1817 return (*bb_dict)[source] == target;
1821 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1823 sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
1827 /* Constructor based on varpool node _NODE with computed hash _HASH.
1828 Bitmap STACK is used for memory allocation. */
1830 sem_variable::sem_variable (varpool_node *node, hashval_t _hash,
1831 bitmap_obstack *stack): sem_item(VAR,
1832 node, _hash, stack)
1834 gcc_checking_assert (node);
1835 gcc_checking_assert (get_node ());
1838 /* Fast equality function based on knowledge known in WPA. */
1840 bool
1841 sem_variable::equals_wpa (sem_item *item,
1842 hash_map <symtab_node *, sem_item *> &ignored_nodes)
1844 gcc_assert (item->type == VAR);
1846 if (node->num_references () != item->node->num_references ())
1847 return return_false_with_msg ("different number of references");
1849 if (DECL_TLS_MODEL (decl) || DECL_TLS_MODEL (item->decl))
1850 return return_false_with_msg ("TLS model");
1852 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1853 alignment out of all aliases. */
1855 if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
1856 return return_false_with_msg ("Virtual flag mismatch");
1858 if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
1859 && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
1860 || !operand_equal_p (DECL_SIZE (decl),
1861 DECL_SIZE (item->decl), OEP_ONLY_CONST)))
1862 return return_false_with_msg ("size mismatch");
1864 /* Do not attempt to mix data from different user sections;
1865 we do not know what user intends with those. */
1866 if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
1867 || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
1868 && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
1869 return return_false_with_msg ("user section mismatch");
1871 if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
1872 return return_false_with_msg ("text section");
1874 ipa_ref *ref = NULL, *ref2 = NULL;
1875 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
1877 item->node->iterate_reference (i, ref2);
1879 if (ref->use != ref2->use)
1880 return return_false_with_msg ("reference use mismatch");
1882 if (!compare_symbol_references (ignored_nodes,
1883 ref->referred, ref2->referred,
1884 ref->address_matters_p ()))
1885 return false;
1888 return true;
1891 /* Returns true if the item equals to ITEM given as argument. */
1893 bool
1894 sem_variable::equals (sem_item *item,
1895 hash_map <symtab_node *, sem_item *> &)
1897 gcc_assert (item->type == VAR);
1898 bool ret;
1900 if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
1901 dyn_cast <varpool_node *>(node)->get_constructor ();
1902 if (DECL_INITIAL (item->decl) == error_mark_node && in_lto_p)
1903 dyn_cast <varpool_node *>(item->node)->get_constructor ();
1905 /* As seen in PR ipa/65303 we have to compare variables types. */
1906 if (!func_checker::compatible_types_p (TREE_TYPE (decl),
1907 TREE_TYPE (item->decl)))
1908 return return_false_with_msg ("variables types are different");
1910 ret = sem_variable::equals (DECL_INITIAL (decl),
1911 DECL_INITIAL (item->node->decl));
1912 if (dump_file && (dump_flags & TDF_DETAILS))
1913 fprintf (dump_file,
1914 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1915 xstrdup_for_dump (node->name()),
1916 xstrdup_for_dump (item->node->name ()),
1917 node->order, item->node->order,
1918 xstrdup_for_dump (node->asm_name ()),
1919 xstrdup_for_dump (item->node->asm_name ()), ret ? "true" : "false");
1921 return ret;
1924 /* Compares trees T1 and T2 for semantic equality. */
1926 bool
1927 sem_variable::equals (tree t1, tree t2)
1929 if (!t1 || !t2)
1930 return return_with_debug (t1 == t2);
1931 if (t1 == t2)
1932 return true;
1933 tree_code tc1 = TREE_CODE (t1);
1934 tree_code tc2 = TREE_CODE (t2);
1936 if (tc1 != tc2)
1937 return return_false_with_msg ("TREE_CODE mismatch");
1939 switch (tc1)
1941 case CONSTRUCTOR:
1943 vec<constructor_elt, va_gc> *v1, *v2;
1944 unsigned HOST_WIDE_INT idx;
1946 enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
1947 if (typecode != TREE_CODE (TREE_TYPE (t2)))
1948 return return_false_with_msg ("constructor type mismatch");
1950 if (typecode == ARRAY_TYPE)
1952 HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
1953 /* For arrays, check that the sizes all match. */
1954 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
1955 || size_1 == -1
1956 || size_1 != int_size_in_bytes (TREE_TYPE (t2)))
1957 return return_false_with_msg ("constructor array size mismatch");
1959 else if (!func_checker::compatible_types_p (TREE_TYPE (t1),
1960 TREE_TYPE (t2)))
1961 return return_false_with_msg ("constructor type incompatible");
1963 v1 = CONSTRUCTOR_ELTS (t1);
1964 v2 = CONSTRUCTOR_ELTS (t2);
1965 if (vec_safe_length (v1) != vec_safe_length (v2))
1966 return return_false_with_msg ("constructor number of elts mismatch");
1968 for (idx = 0; idx < vec_safe_length (v1); ++idx)
1970 constructor_elt *c1 = &(*v1)[idx];
1971 constructor_elt *c2 = &(*v2)[idx];
1973 /* Check that each value is the same... */
1974 if (!sem_variable::equals (c1->value, c2->value))
1975 return false;
1976 /* ... and that they apply to the same fields! */
1977 if (!sem_variable::equals (c1->index, c2->index))
1978 return false;
1980 return true;
1982 case MEM_REF:
1984 tree x1 = TREE_OPERAND (t1, 0);
1985 tree x2 = TREE_OPERAND (t2, 0);
1986 tree y1 = TREE_OPERAND (t1, 1);
1987 tree y2 = TREE_OPERAND (t2, 1);
1989 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
1990 return return_false ();
1992 /* Type of the offset on MEM_REF does not matter. */
1993 return return_with_debug (sem_variable::equals (x1, x2)
1994 && wi::to_offset (y1)
1995 == wi::to_offset (y2));
1997 case ADDR_EXPR:
1998 case FDESC_EXPR:
2000 tree op1 = TREE_OPERAND (t1, 0);
2001 tree op2 = TREE_OPERAND (t2, 0);
2002 return sem_variable::equals (op1, op2);
2004 /* References to other vars/decls are compared using ipa-ref. */
2005 case FUNCTION_DECL:
2006 case VAR_DECL:
2007 if (decl_in_symtab_p (t1) && decl_in_symtab_p (t2))
2008 return true;
2009 return return_false_with_msg ("Declaration mismatch");
2010 case CONST_DECL:
2011 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
2012 need to process its VAR/FUNCTION references without relying on ipa-ref
2013 compare. */
2014 case FIELD_DECL:
2015 case LABEL_DECL:
2016 return return_false_with_msg ("Declaration mismatch");
2017 case INTEGER_CST:
2018 /* Integer constants are the same only if the same width of type. */
2019 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2020 return return_false_with_msg ("INTEGER_CST precision mismatch");
2021 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
2022 return return_false_with_msg ("INTEGER_CST mode mismatch");
2023 return return_with_debug (tree_int_cst_equal (t1, t2));
2024 case STRING_CST:
2025 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
2026 return return_false_with_msg ("STRING_CST mode mismatch");
2027 if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
2028 return return_false_with_msg ("STRING_CST length mismatch");
2029 if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
2030 TREE_STRING_LENGTH (t1)))
2031 return return_false_with_msg ("STRING_CST mismatch");
2032 return true;
2033 case FIXED_CST:
2034 /* Fixed constants are the same only if the same width of type. */
2035 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2036 return return_false_with_msg ("FIXED_CST precision mismatch");
2038 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
2039 TREE_FIXED_CST (t2)));
2040 case COMPLEX_CST:
2041 return (sem_variable::equals (TREE_REALPART (t1), TREE_REALPART (t2))
2042 && sem_variable::equals (TREE_IMAGPART (t1), TREE_IMAGPART (t2)));
2043 case REAL_CST:
2044 /* Real constants are the same only if the same width of type. */
2045 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2046 return return_false_with_msg ("REAL_CST precision mismatch");
2047 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1),
2048 TREE_REAL_CST (t2)));
2049 case VECTOR_CST:
2051 unsigned i;
2053 if (VECTOR_CST_NELTS (t1) != VECTOR_CST_NELTS (t2))
2054 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2056 for (i = 0; i < VECTOR_CST_NELTS (t1); ++i)
2057 if (!sem_variable::equals (VECTOR_CST_ELT (t1, i),
2058 VECTOR_CST_ELT (t2, i)))
2059 return 0;
2061 return 1;
2063 case ARRAY_REF:
2064 case ARRAY_RANGE_REF:
2066 tree x1 = TREE_OPERAND (t1, 0);
2067 tree x2 = TREE_OPERAND (t2, 0);
2068 tree y1 = TREE_OPERAND (t1, 1);
2069 tree y2 = TREE_OPERAND (t2, 1);
2071 if (!sem_variable::equals (x1, x2) || !sem_variable::equals (y1, y2))
2072 return false;
2073 if (!sem_variable::equals (array_ref_low_bound (t1),
2074 array_ref_low_bound (t2)))
2075 return false;
2076 if (!sem_variable::equals (array_ref_element_size (t1),
2077 array_ref_element_size (t2)))
2078 return false;
2079 return true;
2082 case COMPONENT_REF:
2083 case POINTER_PLUS_EXPR:
2084 case PLUS_EXPR:
2085 case MINUS_EXPR:
2086 case RANGE_EXPR:
2088 tree x1 = TREE_OPERAND (t1, 0);
2089 tree x2 = TREE_OPERAND (t2, 0);
2090 tree y1 = TREE_OPERAND (t1, 1);
2091 tree y2 = TREE_OPERAND (t2, 1);
2093 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
2096 CASE_CONVERT:
2097 case VIEW_CONVERT_EXPR:
2098 if (!func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
2099 return return_false ();
2100 return sem_variable::equals (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
2101 case ERROR_MARK:
2102 return return_false_with_msg ("ERROR_MARK");
2103 default:
2104 return return_false_with_msg ("Unknown TREE code reached");
2108 /* Parser function that visits a varpool NODE. */
2110 sem_variable *
2111 sem_variable::parse (varpool_node *node, bitmap_obstack *stack)
2113 if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl)
2114 || node->alias)
2115 return NULL;
2117 sem_variable *v = new sem_variable (node, 0, stack);
2119 v->init ();
2121 return v;
2124 /* References independent hash function. */
2126 hashval_t
2127 sem_variable::get_hash (void)
2129 if (hash)
2130 return hash;
2132 /* All WPA streamed in symbols should have their hashes computed at compile
2133 time. At this point, the constructor may not be in memory at all.
2134 DECL_INITIAL (decl) would be error_mark_node in that case. */
2135 gcc_assert (!node->lto_file_data);
2136 tree ctor = DECL_INITIAL (decl);
2137 inchash::hash hstate;
2139 hstate.add_int (456346417);
2140 if (DECL_SIZE (decl) && tree_fits_shwi_p (DECL_SIZE (decl)))
2141 hstate.add_wide_int (tree_to_shwi (DECL_SIZE (decl)));
2142 add_expr (ctor, hstate);
2143 hash = hstate.end ();
2145 return hash;
2148 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2149 be applied. */
2151 bool
2152 sem_variable::merge (sem_item *alias_item)
2154 gcc_assert (alias_item->type == VAR);
2156 if (!sem_item::target_supports_symbol_aliases_p ())
2158 if (dump_file)
2159 fprintf (dump_file, "Not unifying; "
2160 "Symbol aliases are not supported by target\n\n");
2161 return false;
2164 if (DECL_EXTERNAL (alias_item->decl))
2166 if (dump_file)
2167 fprintf (dump_file, "Not unifying; alias is external.\n\n");
2168 return false;
2171 sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
2173 varpool_node *original = get_node ();
2174 varpool_node *alias = alias_var->get_node ();
2175 bool original_discardable = false;
2177 bool original_address_matters = original->address_matters_p ();
2178 bool alias_address_matters = alias->address_matters_p ();
2180 /* See if original is in a section that can be discarded if the main
2181 symbol is not used.
2182 Also consider case where we have resolution info and we know that
2183 original's definition is not going to be used. In this case we can not
2184 create alias to original. */
2185 if (original->can_be_discarded_p ()
2186 || (node->resolution != LDPR_UNKNOWN
2187 && !decl_binds_to_current_def_p (node->decl)))
2188 original_discardable = true;
2190 gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
2192 /* Constant pool machinery is not quite ready for aliases.
2193 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2194 For LTO merging does not happen that is an important missing feature.
2195 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2196 flag is dropped and non-local symbol name is assigned. */
2197 if (DECL_IN_CONSTANT_POOL (alias->decl)
2198 || DECL_IN_CONSTANT_POOL (original->decl))
2200 if (dump_file)
2201 fprintf (dump_file,
2202 "Not unifying; constant pool variables.\n\n");
2203 return false;
2206 /* Do not attempt to mix functions from different user sections;
2207 we do not know what user intends with those. */
2208 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
2209 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
2210 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
2212 if (dump_file)
2213 fprintf (dump_file,
2214 "Not unifying; "
2215 "original and alias are in different sections.\n\n");
2216 return false;
2219 /* We can not merge if address comparsion metters. */
2220 if (original_address_matters && alias_address_matters
2221 && flag_merge_constants < 2)
2223 if (dump_file)
2224 fprintf (dump_file,
2225 "Not unifying; "
2226 "adress of original and alias may be compared.\n\n");
2227 return false;
2229 if (DECL_COMDAT_GROUP (original->decl) != DECL_COMDAT_GROUP (alias->decl))
2231 if (dump_file)
2232 fprintf (dump_file, "Not unifying; alias cannot be created; "
2233 "across comdat group boundary\n\n");
2235 return false;
2238 if (original_discardable)
2240 if (dump_file)
2241 fprintf (dump_file, "Not unifying; alias cannot be created; "
2242 "target is discardable\n\n");
2244 return false;
2246 else
2248 gcc_assert (!original->alias);
2249 gcc_assert (!alias->alias);
2251 alias->analyzed = false;
2253 DECL_INITIAL (alias->decl) = NULL;
2254 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
2255 NULL, true);
2256 alias->need_bounds_init = false;
2257 alias->remove_all_references ();
2258 if (TREE_ADDRESSABLE (alias->decl))
2259 original->call_for_symbol_and_aliases (set_addressable, NULL, true);
2261 varpool_node::create_alias (alias_var->decl, decl);
2262 alias->resolve_alias (original);
2264 if (dump_file)
2265 fprintf (dump_file, "Unified; Variable alias has been created.\n\n");
2267 return true;
2271 /* Dump symbol to FILE. */
2273 void
2274 sem_variable::dump_to_file (FILE *file)
2276 gcc_assert (file);
2278 print_node (file, "", decl, 0);
2279 fprintf (file, "\n\n");
2282 unsigned int sem_item_optimizer::class_id = 0;
2284 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2285 m_classes_count (0), m_cgraph_node_hooks (NULL), m_varpool_node_hooks (NULL)
2287 m_items.create (0);
2288 bitmap_obstack_initialize (&m_bmstack);
2291 sem_item_optimizer::~sem_item_optimizer ()
2293 for (unsigned int i = 0; i < m_items.length (); i++)
2294 delete m_items[i];
2296 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
2297 it != m_classes.end (); ++it)
2299 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2300 delete (*it)->classes[i];
2302 (*it)->classes.release ();
2303 free (*it);
2306 m_items.release ();
2308 bitmap_obstack_release (&m_bmstack);
2311 /* Write IPA ICF summary for symbols. */
2313 void
2314 sem_item_optimizer::write_summary (void)
2316 unsigned int count = 0;
2318 output_block *ob = create_output_block (LTO_section_ipa_icf);
2319 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
2320 ob->symbol = NULL;
2322 /* Calculate number of symbols to be serialized. */
2323 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2324 !lsei_end_p (lsei);
2325 lsei_next_in_partition (&lsei))
2327 symtab_node *node = lsei_node (lsei);
2329 if (m_symtab_node_map.get (node))
2330 count++;
2333 streamer_write_uhwi (ob, count);
2335 /* Process all of the symbols. */
2336 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2337 !lsei_end_p (lsei);
2338 lsei_next_in_partition (&lsei))
2340 symtab_node *node = lsei_node (lsei);
2342 sem_item **item = m_symtab_node_map.get (node);
2344 if (item && *item)
2346 int node_ref = lto_symtab_encoder_encode (encoder, node);
2347 streamer_write_uhwi_stream (ob->main_stream, node_ref);
2349 streamer_write_uhwi (ob, (*item)->get_hash ());
2353 streamer_write_char_stream (ob->main_stream, 0);
2354 produce_asm (ob, NULL);
2355 destroy_output_block (ob);
2358 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2359 contains LEN bytes. */
2361 void
2362 sem_item_optimizer::read_section (lto_file_decl_data *file_data,
2363 const char *data, size_t len)
2365 const lto_function_header *header =
2366 (const lto_function_header *) data;
2367 const int cfg_offset = sizeof (lto_function_header);
2368 const int main_offset = cfg_offset + header->cfg_size;
2369 const int string_offset = main_offset + header->main_size;
2370 data_in *data_in;
2371 unsigned int i;
2372 unsigned int count;
2374 lto_input_block ib_main ((const char *) data + main_offset, 0,
2375 header->main_size, file_data->mode_table);
2377 data_in =
2378 lto_data_in_create (file_data, (const char *) data + string_offset,
2379 header->string_size, vNULL);
2381 count = streamer_read_uhwi (&ib_main);
2383 for (i = 0; i < count; i++)
2385 unsigned int index;
2386 symtab_node *node;
2387 lto_symtab_encoder_t encoder;
2389 index = streamer_read_uhwi (&ib_main);
2390 encoder = file_data->symtab_node_encoder;
2391 node = lto_symtab_encoder_deref (encoder, index);
2393 hashval_t hash = streamer_read_uhwi (&ib_main);
2395 gcc_assert (node->definition);
2397 if (dump_file)
2398 fprintf (dump_file, "Symbol added:%s (tree: %p, uid:%u)\n",
2399 node->asm_name (), (void *) node->decl, node->order);
2401 if (is_a<cgraph_node *> (node))
2403 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
2405 m_items.safe_push (new sem_function (cnode, hash, &m_bmstack));
2407 else
2409 varpool_node *vnode = dyn_cast <varpool_node *> (node);
2411 m_items.safe_push (new sem_variable (vnode, hash, &m_bmstack));
2415 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
2416 len);
2417 lto_data_in_delete (data_in);
2420 /* Read IPA IPA ICF summary for symbols. */
2422 void
2423 sem_item_optimizer::read_summary (void)
2425 lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2426 lto_file_decl_data *file_data;
2427 unsigned int j = 0;
2429 while ((file_data = file_data_vec[j++]))
2431 size_t len;
2432 const char *data = lto_get_section_data (file_data,
2433 LTO_section_ipa_icf, NULL, &len);
2435 if (data)
2436 read_section (file_data, data, len);
2440 /* Register callgraph and varpool hooks. */
2442 void
2443 sem_item_optimizer::register_hooks (void)
2445 if (!m_cgraph_node_hooks)
2446 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
2447 (&sem_item_optimizer::cgraph_removal_hook, this);
2449 if (!m_varpool_node_hooks)
2450 m_varpool_node_hooks = symtab->add_varpool_removal_hook
2451 (&sem_item_optimizer::varpool_removal_hook, this);
2454 /* Unregister callgraph and varpool hooks. */
2456 void
2457 sem_item_optimizer::unregister_hooks (void)
2459 if (m_cgraph_node_hooks)
2460 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
2462 if (m_varpool_node_hooks)
2463 symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
2466 /* Adds a CLS to hashtable associated by hash value. */
2468 void
2469 sem_item_optimizer::add_class (congruence_class *cls)
2471 gcc_assert (cls->members.length ());
2473 congruence_class_group *group = get_group_by_hash (
2474 cls->members[0]->get_hash (),
2475 cls->members[0]->type);
2476 group->classes.safe_push (cls);
2479 /* Gets a congruence class group based on given HASH value and TYPE. */
2481 congruence_class_group *
2482 sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
2484 congruence_class_group *item = XNEW (congruence_class_group);
2485 item->hash = hash;
2486 item->type = type;
2488 congruence_class_group **slot = m_classes.find_slot (item, INSERT);
2490 if (*slot)
2491 free (item);
2492 else
2494 item->classes.create (1);
2495 *slot = item;
2498 return *slot;
2501 /* Callgraph removal hook called for a NODE with a custom DATA. */
2503 void
2504 sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
2506 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2507 optimizer->remove_symtab_node (node);
2510 /* Varpool removal hook called for a NODE with a custom DATA. */
2512 void
2513 sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
2515 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2516 optimizer->remove_symtab_node (node);
2519 /* Remove symtab NODE triggered by symtab removal hooks. */
2521 void
2522 sem_item_optimizer::remove_symtab_node (symtab_node *node)
2524 gcc_assert (!m_classes.elements());
2526 m_removed_items_set.add (node);
2529 void
2530 sem_item_optimizer::remove_item (sem_item *item)
2532 if (m_symtab_node_map.get (item->node))
2533 m_symtab_node_map.remove (item->node);
2534 delete item;
2537 /* Removes all callgraph and varpool nodes that are marked by symtab
2538 as deleted. */
2540 void
2541 sem_item_optimizer::filter_removed_items (void)
2543 auto_vec <sem_item *> filtered;
2545 for (unsigned int i = 0; i < m_items.length(); i++)
2547 sem_item *item = m_items[i];
2549 if (m_removed_items_set.contains (item->node))
2551 remove_item (item);
2552 continue;
2555 if (item->type == FUNC)
2557 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
2559 if (in_lto_p && (cnode->alias || cnode->body_removed))
2560 remove_item (item);
2561 else
2562 filtered.safe_push (item);
2564 else /* VAR. */
2566 if (!flag_ipa_icf_variables)
2567 remove_item (item);
2568 else
2570 /* Filter out non-readonly variables. */
2571 tree decl = item->decl;
2572 if (TREE_READONLY (decl))
2573 filtered.safe_push (item);
2574 else
2575 remove_item (item);
2580 /* Clean-up of released semantic items. */
2582 m_items.release ();
2583 for (unsigned int i = 0; i < filtered.length(); i++)
2584 m_items.safe_push (filtered[i]);
2587 /* Optimizer entry point which returns true in case it processes
2588 a merge operation. True is returned if there's a merge operation
2589 processed. */
2591 bool
2592 sem_item_optimizer::execute (void)
2594 filter_removed_items ();
2595 unregister_hooks ();
2597 build_graph ();
2598 update_hash_by_addr_refs ();
2599 build_hash_based_classes ();
2601 if (dump_file)
2602 fprintf (dump_file, "Dump after hash based groups\n");
2603 dump_cong_classes ();
2605 for (unsigned int i = 0; i < m_items.length(); i++)
2606 m_items[i]->init_wpa ();
2608 subdivide_classes_by_equality (true);
2610 if (dump_file)
2611 fprintf (dump_file, "Dump after WPA based types groups\n");
2613 dump_cong_classes ();
2615 process_cong_reduction ();
2616 verify_classes ();
2618 if (dump_file)
2619 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
2621 dump_cong_classes ();
2623 parse_nonsingleton_classes ();
2624 subdivide_classes_by_equality ();
2626 if (dump_file)
2627 fprintf (dump_file, "Dump after full equality comparison of groups\n");
2629 dump_cong_classes ();
2631 unsigned int prev_class_count = m_classes_count;
2633 process_cong_reduction ();
2634 dump_cong_classes ();
2635 verify_classes ();
2636 bool merged_p = merge_classes (prev_class_count);
2638 if (dump_file && (dump_flags & TDF_DETAILS))
2639 symtab_node::dump_table (dump_file);
2641 return merged_p;
2644 /* Function responsible for visiting all potential functions and
2645 read-only variables that can be merged. */
2647 void
2648 sem_item_optimizer::parse_funcs_and_vars (void)
2650 cgraph_node *cnode;
2652 if (flag_ipa_icf_functions)
2653 FOR_EACH_DEFINED_FUNCTION (cnode)
2655 sem_function *f = sem_function::parse (cnode, &m_bmstack);
2656 if (f)
2658 m_items.safe_push (f);
2659 m_symtab_node_map.put (cnode, f);
2661 if (dump_file)
2662 fprintf (dump_file, "Parsed function:%s\n", f->node->asm_name ());
2664 if (dump_file && (dump_flags & TDF_DETAILS))
2665 f->dump_to_file (dump_file);
2667 else if (dump_file)
2668 fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
2671 varpool_node *vnode;
2673 if (flag_ipa_icf_variables)
2674 FOR_EACH_DEFINED_VARIABLE (vnode)
2676 sem_variable *v = sem_variable::parse (vnode, &m_bmstack);
2678 if (v)
2680 m_items.safe_push (v);
2681 m_symtab_node_map.put (vnode, v);
2686 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2688 void
2689 sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
2691 item->index_in_class = cls->members.length ();
2692 cls->members.safe_push (item);
2693 item->cls = cls;
2696 /* For each semantic item, append hash values of references. */
2698 void
2699 sem_item_optimizer::update_hash_by_addr_refs ()
2701 /* First, append to hash sensitive references and class type if it need to
2702 be matched for ODR. */
2703 for (unsigned i = 0; i < m_items.length (); i++)
2705 m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
2706 if (m_items[i]->type == FUNC)
2708 if (TREE_CODE (TREE_TYPE (m_items[i]->decl)) == METHOD_TYPE
2709 && contains_polymorphic_type_p
2710 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl)))
2711 && (DECL_CXX_CONSTRUCTOR_P (m_items[i]->decl)
2712 || (static_cast<sem_function *> (m_items[i])->param_used_p (0)
2713 && static_cast<sem_function *> (m_items[i])
2714 ->compare_polymorphic_p ())))
2716 tree class_type
2717 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl));
2718 inchash::hash hstate (m_items[i]->hash);
2720 if (TYPE_NAME (class_type)
2721 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type)))
2722 hstate.add_wide_int
2723 (IDENTIFIER_HASH_VALUE
2724 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type))));
2726 m_items[i]->hash = hstate.end ();
2731 /* Once all symbols have enhanced hash value, we can append
2732 hash values of symbols that are seen by IPA ICF and are
2733 references by a semantic item. Newly computed values
2734 are saved to global_hash member variable. */
2735 for (unsigned i = 0; i < m_items.length (); i++)
2736 m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
2738 /* Global hash value replace current hash values. */
2739 for (unsigned i = 0; i < m_items.length (); i++)
2740 m_items[i]->hash = m_items[i]->global_hash;
2743 /* Congruence classes are built by hash value. */
2745 void
2746 sem_item_optimizer::build_hash_based_classes (void)
2748 for (unsigned i = 0; i < m_items.length (); i++)
2750 sem_item *item = m_items[i];
2752 congruence_class_group *group = get_group_by_hash (item->hash,
2753 item->type);
2755 if (!group->classes.length ())
2757 m_classes_count++;
2758 group->classes.safe_push (new congruence_class (class_id++));
2761 add_item_to_class (group->classes[0], item);
2765 /* Build references according to call graph. */
2767 void
2768 sem_item_optimizer::build_graph (void)
2770 for (unsigned i = 0; i < m_items.length (); i++)
2772 sem_item *item = m_items[i];
2773 m_symtab_node_map.put (item->node, item);
2776 for (unsigned i = 0; i < m_items.length (); i++)
2778 sem_item *item = m_items[i];
2780 if (item->type == FUNC)
2782 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
2784 cgraph_edge *e = cnode->callees;
2785 while (e)
2787 sem_item **slot = m_symtab_node_map.get
2788 (e->callee->ultimate_alias_target ());
2789 if (slot)
2790 item->add_reference (*slot);
2792 e = e->next_callee;
2796 ipa_ref *ref = NULL;
2797 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
2799 sem_item **slot = m_symtab_node_map.get
2800 (ref->referred->ultimate_alias_target ());
2801 if (slot)
2802 item->add_reference (*slot);
2807 /* Semantic items in classes having more than one element and initialized.
2808 In case of WPA, we load function body. */
2810 void
2811 sem_item_optimizer::parse_nonsingleton_classes (void)
2813 unsigned int init_called_count = 0;
2815 for (unsigned i = 0; i < m_items.length (); i++)
2816 if (m_items[i]->cls->members.length () > 1)
2818 m_items[i]->init ();
2819 init_called_count++;
2822 if (dump_file)
2823 fprintf (dump_file, "Init called for %u items (%.2f%%).\n", init_called_count,
2824 m_items.length () ? 100.0f * init_called_count / m_items.length (): 0.0f);
2827 /* Equality function for semantic items is used to subdivide existing
2828 classes. If IN_WPA, fast equality function is invoked. */
2830 void
2831 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
2833 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2834 it != m_classes.end (); ++it)
2836 unsigned int class_count = (*it)->classes.length ();
2838 for (unsigned i = 0; i < class_count; i++)
2840 congruence_class *c = (*it)->classes [i];
2842 if (c->members.length() > 1)
2844 auto_vec <sem_item *> new_vector;
2846 sem_item *first = c->members[0];
2847 new_vector.safe_push (first);
2849 unsigned class_split_first = (*it)->classes.length ();
2851 for (unsigned j = 1; j < c->members.length (); j++)
2853 sem_item *item = c->members[j];
2855 bool equals = in_wpa ? first->equals_wpa (item,
2856 m_symtab_node_map) : first->equals (item, m_symtab_node_map);
2858 if (equals)
2859 new_vector.safe_push (item);
2860 else
2862 bool integrated = false;
2864 for (unsigned k = class_split_first; k < (*it)->classes.length (); k++)
2866 sem_item *x = (*it)->classes[k]->members[0];
2867 bool equals = in_wpa ? x->equals_wpa (item,
2868 m_symtab_node_map) : x->equals (item, m_symtab_node_map);
2870 if (equals)
2872 integrated = true;
2873 add_item_to_class ((*it)->classes[k], item);
2875 break;
2879 if (!integrated)
2881 congruence_class *c = new congruence_class (class_id++);
2882 m_classes_count++;
2883 add_item_to_class (c, item);
2885 (*it)->classes.safe_push (c);
2890 // we replace newly created new_vector for the class we've just splitted
2891 c->members.release ();
2892 c->members.create (new_vector.length ());
2894 for (unsigned int j = 0; j < new_vector.length (); j++)
2895 add_item_to_class (c, new_vector[j]);
2900 verify_classes ();
2903 /* Subdivide classes by address references that members of the class
2904 reference. Example can be a pair of functions that have an address
2905 taken from a function. If these addresses are different the class
2906 is split. */
2908 unsigned
2909 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2911 typedef hash_map <symbol_compare_collection *, vec <sem_item *>,
2912 symbol_compare_hashmap_traits> subdivide_hash_map;
2914 unsigned newly_created_classes = 0;
2916 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
2917 it != m_classes.end (); ++it)
2919 unsigned int class_count = (*it)->classes.length ();
2920 auto_vec<congruence_class *> new_classes;
2922 for (unsigned i = 0; i < class_count; i++)
2924 congruence_class *c = (*it)->classes [i];
2926 if (c->members.length() > 1)
2928 subdivide_hash_map split_map;
2930 for (unsigned j = 0; j < c->members.length (); j++)
2932 sem_item *source_node = c->members[j];
2934 symbol_compare_collection *collection = new symbol_compare_collection (source_node->node);
2936 bool existed;
2937 vec <sem_item *> *slot = &split_map.get_or_insert (collection,
2938 &existed);
2939 gcc_checking_assert (slot);
2941 slot->safe_push (source_node);
2943 if (existed)
2944 delete collection;
2947 /* If the map contains more than one key, we have to split the map
2948 appropriately. */
2949 if (split_map.elements () != 1)
2951 bool first_class = true;
2953 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2954 it2 != split_map.end (); ++it2)
2956 congruence_class *new_cls;
2957 new_cls = new congruence_class (class_id++);
2959 for (unsigned k = 0; k < (*it2).second.length (); k++)
2960 add_item_to_class (new_cls, (*it2).second[k]);
2962 worklist_push (new_cls);
2963 newly_created_classes++;
2965 if (first_class)
2967 (*it)->classes[i] = new_cls;
2968 first_class = false;
2970 else
2972 new_classes.safe_push (new_cls);
2973 m_classes_count++;
2978 /* Release memory. */
2979 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2980 it2 != split_map.end (); ++it2)
2982 delete (*it2).first;
2983 (*it2).second.release ();
2988 for (unsigned i = 0; i < new_classes.length (); i++)
2989 (*it)->classes.safe_push (new_classes[i]);
2992 return newly_created_classes;
2995 /* Verify congruence classes if checking is enabled. */
2997 void
2998 sem_item_optimizer::verify_classes (void)
3000 #if ENABLE_CHECKING
3001 for (hash_table <congruence_class_group_hash>::iterator it = m_classes.begin ();
3002 it != m_classes.end (); ++it)
3004 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3006 congruence_class *cls = (*it)->classes[i];
3008 gcc_checking_assert (cls);
3009 gcc_checking_assert (cls->members.length () > 0);
3011 for (unsigned int j = 0; j < cls->members.length (); j++)
3013 sem_item *item = cls->members[j];
3015 gcc_checking_assert (item);
3016 gcc_checking_assert (item->cls == cls);
3018 for (unsigned k = 0; k < item->usages.length (); k++)
3020 sem_usage_pair *usage = item->usages[k];
3021 gcc_checking_assert (usage->item->index_in_class <
3022 usage->item->cls->members.length ());
3027 #endif
3030 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3031 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3032 but unused argument. */
3034 bool
3035 sem_item_optimizer::release_split_map (congruence_class * const &,
3036 bitmap const &b, traverse_split_pair *)
3038 bitmap bmp = b;
3040 BITMAP_FREE (bmp);
3042 return true;
3045 /* Process split operation for a class given as pointer CLS_PTR,
3046 where bitmap B splits congruence class members. DATA is used
3047 as argument of split pair. */
3049 bool
3050 sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
3051 bitmap const &b, traverse_split_pair *pair)
3053 sem_item_optimizer *optimizer = pair->optimizer;
3054 const congruence_class *splitter_cls = pair->cls;
3056 /* If counted bits are greater than zero and less than the number of members
3057 a group will be splitted. */
3058 unsigned popcount = bitmap_count_bits (b);
3060 if (popcount > 0 && popcount < cls->members.length ())
3062 congruence_class* newclasses[2] = { new congruence_class (class_id++), new congruence_class (class_id++) };
3064 for (unsigned int i = 0; i < cls->members.length (); i++)
3066 int target = bitmap_bit_p (b, i);
3067 congruence_class *tc = newclasses[target];
3069 add_item_to_class (tc, cls->members[i]);
3072 #ifdef ENABLE_CHECKING
3073 for (unsigned int i = 0; i < 2; i++)
3074 gcc_checking_assert (newclasses[i]->members.length ());
3075 #endif
3077 if (splitter_cls == cls)
3078 optimizer->splitter_class_removed = true;
3080 /* Remove old class from worklist if presented. */
3081 bool in_worklist = cls->in_worklist;
3083 if (in_worklist)
3084 cls->in_worklist = false;
3086 congruence_class_group g;
3087 g.hash = cls->members[0]->get_hash ();
3088 g.type = cls->members[0]->type;
3090 congruence_class_group *slot = optimizer->m_classes.find(&g);
3092 for (unsigned int i = 0; i < slot->classes.length (); i++)
3093 if (slot->classes[i] == cls)
3095 slot->classes.ordered_remove (i);
3096 break;
3099 /* New class will be inserted and integrated to work list. */
3100 for (unsigned int i = 0; i < 2; i++)
3101 optimizer->add_class (newclasses[i]);
3103 /* Two classes replace one, so that increment just by one. */
3104 optimizer->m_classes_count++;
3106 /* If OLD class was presented in the worklist, we remove the class
3107 and replace it will both newly created classes. */
3108 if (in_worklist)
3109 for (unsigned int i = 0; i < 2; i++)
3110 optimizer->worklist_push (newclasses[i]);
3111 else /* Just smaller class is inserted. */
3113 unsigned int smaller_index = newclasses[0]->members.length () <
3114 newclasses[1]->members.length () ?
3115 0 : 1;
3116 optimizer->worklist_push (newclasses[smaller_index]);
3119 if (dump_file && (dump_flags & TDF_DETAILS))
3121 fprintf (dump_file, " congruence class splitted:\n");
3122 cls->dump (dump_file, 4);
3124 fprintf (dump_file, " newly created groups:\n");
3125 for (unsigned int i = 0; i < 2; i++)
3126 newclasses[i]->dump (dump_file, 4);
3129 /* Release class if not presented in work list. */
3130 if (!in_worklist)
3131 delete cls;
3135 return true;
3138 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3139 Bitmap stack BMSTACK is used for bitmap allocation. */
3141 void
3142 sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
3143 unsigned int index)
3145 hash_map <congruence_class *, bitmap> split_map;
3147 for (unsigned int i = 0; i < cls->members.length (); i++)
3149 sem_item *item = cls->members[i];
3151 /* Iterate all usages that have INDEX as usage of the item. */
3152 for (unsigned int j = 0; j < item->usages.length (); j++)
3154 sem_usage_pair *usage = item->usages[j];
3156 if (usage->index != index)
3157 continue;
3159 bitmap *slot = split_map.get (usage->item->cls);
3160 bitmap b;
3162 if(!slot)
3164 b = BITMAP_ALLOC (&m_bmstack);
3165 split_map.put (usage->item->cls, b);
3167 else
3168 b = *slot;
3170 #if ENABLE_CHECKING
3171 gcc_checking_assert (usage->item->cls);
3172 gcc_checking_assert (usage->item->index_in_class <
3173 usage->item->cls->members.length ());
3174 #endif
3176 bitmap_set_bit (b, usage->item->index_in_class);
3180 traverse_split_pair pair;
3181 pair.optimizer = this;
3182 pair.cls = cls;
3184 splitter_class_removed = false;
3185 split_map.traverse
3186 <traverse_split_pair *, sem_item_optimizer::traverse_congruence_split> (&pair);
3188 /* Bitmap clean-up. */
3189 split_map.traverse
3190 <traverse_split_pair *, sem_item_optimizer::release_split_map> (NULL);
3193 /* Every usage of a congruence class CLS is a candidate that can split the
3194 collection of classes. Bitmap stack BMSTACK is used for bitmap
3195 allocation. */
3197 void
3198 sem_item_optimizer::do_congruence_step (congruence_class *cls)
3200 bitmap_iterator bi;
3201 unsigned int i;
3203 bitmap usage = BITMAP_ALLOC (&m_bmstack);
3205 for (unsigned int i = 0; i < cls->members.length (); i++)
3206 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
3208 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
3210 if (dump_file && (dump_flags & TDF_DETAILS))
3211 fprintf (dump_file, " processing congruece step for class: %u, index: %u\n",
3212 cls->id, i);
3214 do_congruence_step_for_index (cls, i);
3216 if (splitter_class_removed)
3217 break;
3220 BITMAP_FREE (usage);
3223 /* Adds a newly created congruence class CLS to worklist. */
3225 void
3226 sem_item_optimizer::worklist_push (congruence_class *cls)
3228 /* Return if the class CLS is already presented in work list. */
3229 if (cls->in_worklist)
3230 return;
3232 cls->in_worklist = true;
3233 worklist.push_back (cls);
3236 /* Pops a class from worklist. */
3238 congruence_class *
3239 sem_item_optimizer::worklist_pop (void)
3241 congruence_class *cls;
3243 while (!worklist.empty ())
3245 cls = worklist.front ();
3246 worklist.pop_front ();
3247 if (cls->in_worklist)
3249 cls->in_worklist = false;
3251 return cls;
3253 else
3255 /* Work list item was already intended to be removed.
3256 The only reason for doing it is to split a class.
3257 Thus, the class CLS is deleted. */
3258 delete cls;
3262 return NULL;
3265 /* Iterative congruence reduction function. */
3267 void
3268 sem_item_optimizer::process_cong_reduction (void)
3270 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3271 it != m_classes.end (); ++it)
3272 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3273 if ((*it)->classes[i]->is_class_used ())
3274 worklist_push ((*it)->classes[i]);
3276 if (dump_file)
3277 fprintf (dump_file, "Worklist has been filled with: %lu\n",
3278 (unsigned long) worklist.size ());
3280 if (dump_file && (dump_flags & TDF_DETAILS))
3281 fprintf (dump_file, "Congruence class reduction\n");
3283 congruence_class *cls;
3285 /* Process complete congruence reduction. */
3286 while ((cls = worklist_pop ()) != NULL)
3287 do_congruence_step (cls);
3289 /* Subdivide newly created classes according to references. */
3290 unsigned new_classes = subdivide_classes_by_sensitive_refs ();
3292 if (dump_file)
3293 fprintf (dump_file, "Address reference subdivision created: %u "
3294 "new classes.\n", new_classes);
3297 /* Debug function prints all informations about congruence classes. */
3299 void
3300 sem_item_optimizer::dump_cong_classes (void)
3302 if (!dump_file)
3303 return;
3305 fprintf (dump_file,
3306 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3307 m_classes_count, (unsigned long) m_classes.elements(), m_items.length ());
3309 /* Histogram calculation. */
3310 unsigned int max_index = 0;
3311 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
3313 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3314 it != m_classes.end (); ++it)
3316 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3318 unsigned int c = (*it)->classes[i]->members.length ();
3319 histogram[c]++;
3321 if (c > max_index)
3322 max_index = c;
3325 fprintf (dump_file,
3326 "Class size histogram [num of members]: number of classe number of classess\n");
3328 for (unsigned int i = 0; i <= max_index; i++)
3329 if (histogram[i])
3330 fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
3332 fprintf (dump_file, "\n\n");
3335 if (dump_flags & TDF_DETAILS)
3336 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3337 it != m_classes.end (); ++it)
3339 fprintf (dump_file, " group: with %u classes:\n", (*it)->classes.length ());
3341 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3343 (*it)->classes[i]->dump (dump_file, 4);
3345 if(i < (*it)->classes.length () - 1)
3346 fprintf (dump_file, " ");
3350 free (histogram);
3353 /* After reduction is done, we can declare all items in a group
3354 to be equal. PREV_CLASS_COUNT is start number of classes
3355 before reduction. True is returned if there's a merge operation
3356 processed. */
3358 bool
3359 sem_item_optimizer::merge_classes (unsigned int prev_class_count)
3361 unsigned int item_count = m_items.length ();
3362 unsigned int class_count = m_classes_count;
3363 unsigned int equal_items = item_count - class_count;
3365 unsigned int non_singular_classes_count = 0;
3366 unsigned int non_singular_classes_sum = 0;
3368 bool merged_p = false;
3370 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3371 it != m_classes.end (); ++it)
3372 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3374 congruence_class *c = (*it)->classes[i];
3375 if (c->members.length () > 1)
3377 non_singular_classes_count++;
3378 non_singular_classes_sum += c->members.length ();
3382 if (dump_file)
3384 fprintf (dump_file, "\nItem count: %u\n", item_count);
3385 fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
3386 prev_class_count, class_count);
3387 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
3388 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
3389 class_count ? 1.0f * item_count / class_count : 0.0f);
3390 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
3391 non_singular_classes_count ? 1.0f * non_singular_classes_sum /
3392 non_singular_classes_count : 0.0f,
3393 non_singular_classes_count);
3394 fprintf (dump_file, "Equal symbols: %u\n", equal_items);
3395 fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
3396 item_count ? 100.0f * equal_items / item_count : 0.0f);
3399 for (hash_table<congruence_class_group_hash>::iterator it = m_classes.begin ();
3400 it != m_classes.end (); ++it)
3401 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3403 congruence_class *c = (*it)->classes[i];
3405 if (c->members.length () == 1)
3406 continue;
3408 gcc_assert (c->members.length ());
3410 sem_item *source = c->members[0];
3412 for (unsigned int j = 1; j < c->members.length (); j++)
3414 sem_item *alias = c->members[j];
3416 if (dump_file)
3418 fprintf (dump_file, "Semantic equality hit:%s->%s\n",
3419 xstrdup_for_dump (source->node->name ()),
3420 xstrdup_for_dump (alias->node->name ()));
3421 fprintf (dump_file, "Assembler symbol names:%s->%s\n",
3422 xstrdup_for_dump (source->node->asm_name ()),
3423 xstrdup_for_dump (alias->node->asm_name ()));
3426 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl)))
3428 if (dump_file)
3429 fprintf (dump_file,
3430 "Merge operation is skipped due to no_icf "
3431 "attribute.\n\n");
3433 continue;
3436 if (dump_file && (dump_flags & TDF_DETAILS))
3438 source->dump_to_file (dump_file);
3439 alias->dump_to_file (dump_file);
3442 if (dbg_cnt (merged_ipa_icf))
3443 merged_p |= source->merge (alias);
3447 return merged_p;
3450 /* Dump function prints all class members to a FILE with an INDENT. */
3452 void
3453 congruence_class::dump (FILE *file, unsigned int indent) const
3455 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
3456 id, members[0]->get_hash (), members.length ());
3458 FPUTS_SPACES (file, indent + 2, "");
3459 for (unsigned i = 0; i < members.length (); i++)
3460 fprintf (file, "%s(%p/%u) ", members[i]->node->asm_name (),
3461 (void *) members[i]->decl,
3462 members[i]->node->order);
3464 fprintf (file, "\n");
3467 /* Returns true if there's a member that is used from another group. */
3469 bool
3470 congruence_class::is_class_used (void)
3472 for (unsigned int i = 0; i < members.length (); i++)
3473 if (members[i]->usages.length ())
3474 return true;
3476 return false;
3479 /* Generate pass summary for IPA ICF pass. */
3481 static void
3482 ipa_icf_generate_summary (void)
3484 if (!optimizer)
3485 optimizer = new sem_item_optimizer ();
3487 optimizer->register_hooks ();
3488 optimizer->parse_funcs_and_vars ();
3491 /* Write pass summary for IPA ICF pass. */
3493 static void
3494 ipa_icf_write_summary (void)
3496 gcc_assert (optimizer);
3498 optimizer->write_summary ();
3501 /* Read pass summary for IPA ICF pass. */
3503 static void
3504 ipa_icf_read_summary (void)
3506 if (!optimizer)
3507 optimizer = new sem_item_optimizer ();
3509 optimizer->read_summary ();
3510 optimizer->register_hooks ();
3513 /* Semantic equality exection function. */
3515 static unsigned int
3516 ipa_icf_driver (void)
3518 gcc_assert (optimizer);
3520 bool merged_p = optimizer->execute ();
3522 delete optimizer;
3523 optimizer = NULL;
3525 return merged_p ? TODO_remove_functions : 0;
3528 const pass_data pass_data_ipa_icf =
3530 IPA_PASS, /* type */
3531 "icf", /* name */
3532 OPTGROUP_IPA, /* optinfo_flags */
3533 TV_IPA_ICF, /* tv_id */
3534 0, /* properties_required */
3535 0, /* properties_provided */
3536 0, /* properties_destroyed */
3537 0, /* todo_flags_start */
3538 0, /* todo_flags_finish */
3541 class pass_ipa_icf : public ipa_opt_pass_d
3543 public:
3544 pass_ipa_icf (gcc::context *ctxt)
3545 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
3546 ipa_icf_generate_summary, /* generate_summary */
3547 ipa_icf_write_summary, /* write_summary */
3548 ipa_icf_read_summary, /* read_summary */
3549 NULL, /*
3550 write_optimization_summary */
3551 NULL, /*
3552 read_optimization_summary */
3553 NULL, /* stmt_fixup */
3554 0, /* function_transform_todo_flags_start */
3555 NULL, /* function_transform */
3556 NULL) /* variable_transform */
3559 /* opt_pass methods: */
3560 virtual bool gate (function *)
3562 return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
3565 virtual unsigned int execute (function *)
3567 return ipa_icf_driver();
3569 }; // class pass_ipa_icf
3571 } // ipa_icf namespace
3573 ipa_opt_pass_d *
3574 make_pass_ipa_icf (gcc::context *ctxt)
3576 return new ipa_icf::pass_ipa_icf (ctxt);