1/* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2017 Free Software Foundation, Inc.
3
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
22/* Interprocedural Identical Code Folding for functions and
23 read-only variables.
24
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
27
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.
33
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.
51
52*/
53
54#include "config.h"
55#define INCLUDE_LIST
56#include "system.h"
57#include "coretypes.h"
58#include "backend.h"
59#include "target.h"
60#include "rtl.h"
61#include "tree.h"
62#include "gimple.h"
63#include "alloc-pool.h"
64#include "tree-pass.h"
65#include "ssa.h"
66#include "cgraph.h"
67#include "coverage.h"
68#include "gimple-pretty-print.h"
69#include "data-streamer.h"
70#include "fold-const.h"
71#include "calls.h"
72#include "varasm.h"
73#include "gimple-iterator.h"
74#include "tree-cfg.h"
75#include "symbol-summary.h"
76#include "ipa-prop.h"
77#include "ipa-fnsummary.h"
78#include "except.h"
79#include "attribs.h"
80#include "print-tree.h"
81#include "ipa-utils.h"
82#include "ipa-icf-gimple.h"
83#include "ipa-icf.h"
84#include "stor-layout.h"
85#include "dbgcnt.h"
86#include "tree-vector-builder.h"
87
88using namespace ipa_icf_gimple;
89
90namespace ipa_icf {
91
92/* Initialization and computation of symtab node hash, there data
93 are propagated later on. */
94
95static sem_item_optimizer *optimizer = NULL;
96
97/* Constructor. */
98
99symbol_compare_collection::symbol_compare_collection (symtab_node *node)
100{
101 m_references.create (0);
102 m_interposables.create (0);
103
104 ipa_ref *ref;
105
106 if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
107 return;
108
109 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
110 {
111 if (ref->address_matters_p ())
112 m_references.safe_push (ref->referred);
113
114 if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE)
115 {
116 if (ref->address_matters_p ())
117 m_references.safe_push (ref->referred);
118 else
119 m_interposables.safe_push (ref->referred);
120 }
121 }
122
123 if (is_a <cgraph_node *> (node))
124 {
125 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
126
127 for (cgraph_edge *e = cnode->callees; e; e = e->next_callee)
128 if (e->callee->get_availability () <= AVAIL_INTERPOSABLE)
129 m_interposables.safe_push (e->callee);
130 }
131}
132
133/* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
134
135sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index)
136: item (_item), index (_index)
137{
138}
139
140sem_item::sem_item (sem_item_type _type, bitmap_obstack *stack)
141: type (_type), m_hash (-1), m_hash_set (false)
142{
143 setup (stack);
144}
145
146sem_item::sem_item (sem_item_type _type, symtab_node *_node,
147 bitmap_obstack *stack)
148: type (_type), node (_node), m_hash (-1), m_hash_set (false)
149{
150 decl = node->decl;
151 setup (stack);
152}
153
154/* Add reference to a semantic TARGET. */
155
156void
157sem_item::add_reference (sem_item *target)
158{
159 refs.safe_push (target);
160 unsigned index = refs.length ();
161 target->usages.safe_push (new sem_usage_pair(this, index));
162 bitmap_set_bit (target->usage_index_bitmap, index);
163 refs_set.add (target->node);
164}
165
166/* Initialize internal data structures. Bitmap STACK is used for
167 bitmap memory allocation process. */
168
169void
170sem_item::setup (bitmap_obstack *stack)
171{
172 gcc_checking_assert (node);
173
174 refs.create (0);
175 tree_refs.create (0);
176 usages.create (0);
177 usage_index_bitmap = BITMAP_ALLOC (stack);
178}
179
180sem_item::~sem_item ()
181{
182 for (unsigned i = 0; i < usages.length (); i++)
183 delete usages[i];
184
185 refs.release ();
186 tree_refs.release ();
187 usages.release ();
188
189 BITMAP_FREE (usage_index_bitmap);
190}
191
192/* Dump function for debugging purpose. */
193
194DEBUG_FUNCTION void
195sem_item::dump (void)
196{
197 if (dump_file)
198 {
199 fprintf (dump_file, "[%s] %s (tree:%p)\n", type == FUNC ? "func" : "var",
200 node->dump_name (), (void *) node->decl);
201 fprintf (dump_file, " hash: %u\n", get_hash ());
202 fprintf (dump_file, " references: ");
203
204 for (unsigned i = 0; i < refs.length (); i++)
205 fprintf (dump_file, "%s%s ", refs[i]->node->name (),
206 i < refs.length() - 1 ? "," : "");
207
208 fprintf (dump_file, "\n");
209 }
210}
211
212/* Return true if target supports alias symbols. */
213
214bool
215sem_item::target_supports_symbol_aliases_p (void)
216{
217#if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
218 return false;
219#else
220 return true;
221#endif
222}
223
224void sem_item::set_hash (hashval_t hash)
225{
226 m_hash = hash;
227 m_hash_set = true;
228}
229
230/* Semantic function constructor that uses STACK as bitmap memory stack. */
231
232sem_function::sem_function (bitmap_obstack *stack)
233: sem_item (FUNC, stack), m_checker (NULL), m_compared_func (NULL)
234{
235 bb_sizes.create (0);
236 bb_sorted.create (0);
237}
238
239sem_function::sem_function (cgraph_node *node, bitmap_obstack *stack)
240: sem_item (FUNC, node, stack), m_checker (NULL), m_compared_func (NULL)
241{
242 bb_sizes.create (0);
243 bb_sorted.create (0);
244}
245
246sem_function::~sem_function ()
247{
248 for (unsigned i = 0; i < bb_sorted.length (); i++)
249 delete (bb_sorted[i]);
250
251 bb_sizes.release ();
252 bb_sorted.release ();
253}
254
255/* Calculates hash value based on a BASIC_BLOCK. */
256
257hashval_t
258sem_function::get_bb_hash (const sem_bb *basic_block)
259{
260 inchash::hash hstate;
261
262 hstate.add_int (basic_block->nondbg_stmt_count);
263 hstate.add_int (basic_block->edge_count);
264
265 return hstate.end ();
266}
267
268/* References independent hash function. */
269
270hashval_t
271sem_function::get_hash (void)
272{
273 if (!m_hash_set)
274 {
275 inchash::hash hstate;
276 hstate.add_int (177454); /* Random number for function type. */
277
278 hstate.add_int (arg_count);
279 hstate.add_int (cfg_checksum);
280 hstate.add_int (gcode_hash);
281
282 for (unsigned i = 0; i < bb_sorted.length (); i++)
283 hstate.merge_hash (get_bb_hash (bb_sorted[i]));
284
285 for (unsigned i = 0; i < bb_sizes.length (); i++)
286 hstate.add_int (bb_sizes[i]);
287
288 /* Add common features of declaration itself. */
289 if (DECL_FUNCTION_SPECIFIC_TARGET (decl))
290 hstate.add_hwi
291 (cl_target_option_hash
292 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl))));
293 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))
294 hstate.add_hwi
295 (cl_optimization_hash
296 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))));
297 hstate.add_flag (DECL_CXX_CONSTRUCTOR_P (decl));
298 hstate.add_flag (DECL_CXX_DESTRUCTOR_P (decl));
299
300 set_hash (hstate.end ());
301 }
302
303 return m_hash;
304}
305
306/* Return ture if A1 and A2 represent equivalent function attribute lists.
307 Based on comp_type_attributes. */
308
309bool
310sem_item::compare_attributes (const_tree a1, const_tree a2)
311{
312 const_tree a;
313 if (a1 == a2)
314 return true;
315 for (a = a1; a != NULL_TREE; a = TREE_CHAIN (a))
316 {
317 const struct attribute_spec *as;
318 const_tree attr;
319
320 as = lookup_attribute_spec (get_attribute_name (a));
321 /* TODO: We can introduce as->affects_decl_identity
322 and as->affects_decl_reference_identity if attribute mismatch
323 gets a common reason to give up on merging. It may not be worth
324 the effort.
325 For example returns_nonnull affects only references, while
326 optimize attribute can be ignored because it is already lowered
327 into flags representation and compared separately. */
328 if (!as)
329 continue;
330
331 attr = lookup_attribute (as->name, CONST_CAST_TREE (a2));
332 if (!attr || !attribute_value_equal (a, attr))
333 break;
334 }
335 if (!a)
336 {
337 for (a = a2; a != NULL_TREE; a = TREE_CHAIN (a))
338 {
339 const struct attribute_spec *as;
340
341 as = lookup_attribute_spec (get_attribute_name (a));
342 if (!as)
343 continue;
344
345 if (!lookup_attribute (as->name, CONST_CAST_TREE (a1)))
346 break;
347 /* We don't need to compare trees again, as we did this
348 already in first loop. */
349 }
350 if (!a)
351 return true;
352 }
353 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
354 return false;
355}
356
357/* Compare properties of symbols N1 and N2 that does not affect semantics of
358 symbol itself but affects semantics of its references from USED_BY (which
359 may be NULL if it is unknown). If comparsion is false, symbols
360 can still be merged but any symbols referring them can't.
361
362 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
363
364 TODO: We can also split attributes to those that determine codegen of
365 a function body/variable constructor itself and those that are used when
366 referring to it. */
367
368bool
369sem_item::compare_referenced_symbol_properties (symtab_node *used_by,
370 symtab_node *n1,
371 symtab_node *n2,
372 bool address)
373{
374 if (is_a <cgraph_node *> (n1))
375 {
376 /* Inline properties matters: we do now want to merge uses of inline
377 function to uses of normal function because inline hint would be lost.
378 We however can merge inline function to noinline because the alias
379 will keep its DECL_DECLARED_INLINE flag.
380
381 Also ignore inline flag when optimizing for size or when function
382 is known to not be inlinable.
383
384 TODO: the optimize_size checks can also be assumed to be true if
385 unit has no !optimize_size functions. */
386
387 if ((!used_by || address || !is_a <cgraph_node *> (used_by)
388 || !opt_for_fn (used_by->decl, optimize_size))
389 && !opt_for_fn (n1->decl, optimize_size)
390 && n1->get_availability () > AVAIL_INTERPOSABLE
391 && (!DECL_UNINLINABLE (n1->decl) || !DECL_UNINLINABLE (n2->decl)))
392 {
393 if (DECL_DISREGARD_INLINE_LIMITS (n1->decl)
394 != DECL_DISREGARD_INLINE_LIMITS (n2->decl))
395 return return_false_with_msg
396 ("DECL_DISREGARD_INLINE_LIMITS are different");
397
398 if (DECL_DECLARED_INLINE_P (n1->decl)
399 != DECL_DECLARED_INLINE_P (n2->decl))
400 return return_false_with_msg ("inline attributes are different");
401 }
402
403 if (DECL_IS_OPERATOR_NEW (n1->decl)
404 != DECL_IS_OPERATOR_NEW (n2->decl))
405 return return_false_with_msg ("operator new flags are different");
406 }
407
408 /* Merging two definitions with a reference to equivalent vtables, but
409 belonging to a different type may result in ipa-polymorphic-call analysis
410 giving a wrong answer about the dynamic type of instance. */
411 if (is_a <varpool_node *> (n1))
412 {
413 if ((DECL_VIRTUAL_P (n1->decl) || DECL_VIRTUAL_P (n2->decl))
414 && (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl)
415 || !types_must_be_same_for_odr (DECL_CONTEXT (n1->decl),
416 DECL_CONTEXT (n2->decl)))
417 && (!used_by || !is_a <cgraph_node *> (used_by) || address
418 || opt_for_fn (used_by->decl, flag_devirtualize)))
419 return return_false_with_msg
420 ("references to virtual tables can not be merged");
421
422 if (address && DECL_ALIGN (n1->decl) != DECL_ALIGN (n2->decl))
423 return return_false_with_msg ("alignment mismatch");
424
425 /* For functions we compare attributes in equals_wpa, because we do
426 not know what attributes may cause codegen differences, but for
427 variables just compare attributes for references - the codegen
428 for constructors is affected only by those attributes that we lower
429 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
430 if (!compare_attributes (DECL_ATTRIBUTES (n1->decl),
431 DECL_ATTRIBUTES (n2->decl)))
432 return return_false_with_msg ("different var decl attributes");
433 if (comp_type_attributes (TREE_TYPE (n1->decl),
434 TREE_TYPE (n2->decl)) != 1)
435 return return_false_with_msg ("different var type attributes");
436 }
437
438 /* When matching virtual tables, be sure to also match information
439 relevant for polymorphic call analysis. */
440 if (used_by && is_a <varpool_node *> (used_by)
441 && DECL_VIRTUAL_P (used_by->decl))
442 {
443 if (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl))
444 return return_false_with_msg ("virtual flag mismatch");
445 if (DECL_VIRTUAL_P (n1->decl) && is_a <cgraph_node *> (n1)
446 && (DECL_FINAL_P (n1->decl) != DECL_FINAL_P (n2->decl)))
447 return return_false_with_msg ("final flag mismatch");
448 }
449 return true;
450}
451
452/* Hash properties that are compared by compare_referenced_symbol_properties. */
453
454void
455sem_item::hash_referenced_symbol_properties (symtab_node *ref,
456 inchash::hash &hstate,
457 bool address)
458{
459 if (is_a <cgraph_node *> (ref))
460 {
461 if ((type != FUNC || address || !opt_for_fn (decl, optimize_size))
462 && !opt_for_fn (ref->decl, optimize_size)
463 && !DECL_UNINLINABLE (ref->decl))
464 {
465 hstate.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref->decl));
466 hstate.add_flag (DECL_DECLARED_INLINE_P (ref->decl));
467 }
468 hstate.add_flag (DECL_IS_OPERATOR_NEW (ref->decl));
469 }
470 else if (is_a <varpool_node *> (ref))
471 {
472 hstate.add_flag (DECL_VIRTUAL_P (ref->decl));
473 if (address)
474 hstate.add_int (DECL_ALIGN (ref->decl));
475 }
476}
477
478
479/* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
480 point to a same function. Comparison can be skipped if IGNORED_NODES
481 contains these nodes. ADDRESS indicate if address is taken. */
482
483bool
484sem_item::compare_symbol_references (
485 hash_map <symtab_node *, sem_item *> &ignored_nodes,
486 symtab_node *n1, symtab_node *n2, bool address)
487{
488 enum availability avail1, avail2;
489
490 if (n1 == n2)
491 return true;
492
493 /* Never match variable and function. */
494 if (is_a <varpool_node *> (n1) != is_a <varpool_node *> (n2))
495 return false;
496
497 if (!compare_referenced_symbol_properties (node, n1, n2, address))
498 return false;
499 if (address && n1->equal_address_to (n2) == 1)
500 return true;
501 if (!address && n1->semantically_equivalent_p (n2))
502 return true;
503
504 n1 = n1->ultimate_alias_target (&avail1);
505 n2 = n2->ultimate_alias_target (&avail2);
506
507 if (avail1 > AVAIL_INTERPOSABLE && ignored_nodes.get (n1)
508 && avail2 > AVAIL_INTERPOSABLE && ignored_nodes.get (n2))
509 return true;
510
511 return return_false_with_msg ("different references");
512}
513
514/* If cgraph edges E1 and E2 are indirect calls, verify that
515 ECF flags are the same. */
516
517bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
518{
519 if (e1->indirect_info && e2->indirect_info)
520 {
521 int e1_flags = e1->indirect_info->ecf_flags;
522 int e2_flags = e2->indirect_info->ecf_flags;
523
524 if (e1_flags != e2_flags)
525 return return_false_with_msg ("ICF flags are different");
526 }
527 else if (e1->indirect_info || e2->indirect_info)
528 return false;
529
530 return true;
531}
532
533/* Return true if parameter I may be used. */
534
535bool
536sem_function::param_used_p (unsigned int i)
537{
538 if (ipa_node_params_sum == NULL)
539 return true;
540
541 struct ipa_node_params *parms_info = IPA_NODE_REF (get_node ());
542
543 if (vec_safe_length (parms_info->descriptors) <= i)
544 return true;
545
546 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i);
547}
548
549/* Perform additional check needed to match types function parameters that are
550 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
551 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
552
553bool
554sem_function::compatible_parm_types_p (tree parm1, tree parm2)
555{
556 /* Be sure that parameters are TBAA compatible. */
557 if (!func_checker::compatible_types_p (parm1, parm2))
558 return return_false_with_msg ("parameter type is not compatible");
559
560 if (POINTER_TYPE_P (parm1)
561 && (TYPE_RESTRICT (parm1) != TYPE_RESTRICT (parm2)))
562 return return_false_with_msg ("argument restrict flag mismatch");
563
564 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
565 if (POINTER_TYPE_P (parm1)
566 && TREE_CODE (parm1) != TREE_CODE (parm2)
567 && opt_for_fn (decl, flag_delete_null_pointer_checks))
568 return return_false_with_msg ("pointer wrt reference mismatch");
569
570 return true;
571}
572
573/* Fast equality function based on knowledge known in WPA. */
574
575bool
576sem_function::equals_wpa (sem_item *item,
577 hash_map <symtab_node *, sem_item *> &ignored_nodes)
578{
579 gcc_assert (item->type == FUNC);
580 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
581 cgraph_node *cnode2 = dyn_cast <cgraph_node *> (item->node);
582
583 m_compared_func = static_cast<sem_function *> (item);
584
585 if (cnode->thunk.thunk_p != cnode2->thunk.thunk_p)
586 return return_false_with_msg ("thunk_p mismatch");
587
588 if (cnode->thunk.thunk_p)
589 {
590 if (cnode->thunk.fixed_offset != cnode2->thunk.fixed_offset)
591 return return_false_with_msg ("thunk fixed_offset mismatch");
592 if (cnode->thunk.virtual_value != cnode2->thunk.virtual_value)
593 return return_false_with_msg ("thunk virtual_value mismatch");
594 if (cnode->thunk.this_adjusting != cnode2->thunk.this_adjusting)
595 return return_false_with_msg ("thunk this_adjusting mismatch");
596 if (cnode->thunk.virtual_offset_p != cnode2->thunk.virtual_offset_p)
597 return return_false_with_msg ("thunk virtual_offset_p mismatch");
598 if (cnode->thunk.add_pointer_bounds_args
599 != cnode2->thunk.add_pointer_bounds_args)
600 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
601 }
602
603 /* Compare special function DECL attributes. */
604 if (DECL_FUNCTION_PERSONALITY (decl)
605 != DECL_FUNCTION_PERSONALITY (item->decl))
606 return return_false_with_msg ("function personalities are different");
607
608 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
609 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item->decl))
610 return return_false_with_msg ("intrument function entry exit "
611 "attributes are different");
612
613 if (DECL_NO_LIMIT_STACK (decl) != DECL_NO_LIMIT_STACK (item->decl))
614 return return_false_with_msg ("no stack limit attributes are different");
615
616 if (DECL_CXX_CONSTRUCTOR_P (decl) != DECL_CXX_CONSTRUCTOR_P (item->decl))
617 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
618
619 if (DECL_CXX_DESTRUCTOR_P (decl) != DECL_CXX_DESTRUCTOR_P (item->decl))
620 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
621
622 /* TODO: pure/const flags mostly matters only for references, except for
623 the fact that codegen takes LOOPING flag as a hint that loops are
624 finite. We may arrange the code to always pick leader that has least
625 specified flags and then this can go into comparing symbol properties. */
626 if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
627 return return_false_with_msg ("decl_or_type flags are different");
628
629 /* Do not match polymorphic constructors of different types. They calls
630 type memory location for ipa-polymorphic-call and we do not want
631 it to get confused by wrong type. */
632 if (DECL_CXX_CONSTRUCTOR_P (decl)
633 && TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE)
634 {
635 if (TREE_CODE (TREE_TYPE (item->decl)) != METHOD_TYPE)
636 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
637 else if (!func_checker::compatible_polymorphic_types_p
638 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
639 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
640 return return_false_with_msg ("ctor polymorphic type mismatch");
641 }
642
643 /* Checking function TARGET and OPTIMIZATION flags. */
644 cl_target_option *tar1 = target_opts_for_fn (decl);
645 cl_target_option *tar2 = target_opts_for_fn (item->decl);
646
647 if (tar1 != tar2 && !cl_target_option_eq (tar1, tar2))
648 {
649 if (dump_file && (dump_flags & TDF_DETAILS))
650 {
651 fprintf (dump_file, "target flags difference");
652 cl_target_option_print_diff (dump_file, 2, tar1, tar2);
653 }
654
655 return return_false_with_msg ("Target flags are different");
656 }
657
658 cl_optimization *opt1 = opts_for_fn (decl);
659 cl_optimization *opt2 = opts_for_fn (item->decl);
660
661 if (opt1 != opt2 && memcmp (opt1, opt2, sizeof(cl_optimization)))
662 {
663 if (dump_file && (dump_flags & TDF_DETAILS))
664 {
665 fprintf (dump_file, "optimization flags difference");
666 cl_optimization_print_diff (dump_file, 2, opt1, opt2);
667 }
668
669 return return_false_with_msg ("optimization flags are different");
670 }
671
672 /* Result type checking. */
673 if (!func_checker::compatible_types_p
674 (TREE_TYPE (TREE_TYPE (decl)),
675 TREE_TYPE (TREE_TYPE (m_compared_func->decl))))
676 return return_false_with_msg ("result types are different");
677
678 /* Checking types of arguments. */
679 tree list1 = TYPE_ARG_TYPES (TREE_TYPE (decl)),
680 list2 = TYPE_ARG_TYPES (TREE_TYPE (m_compared_func->decl));
681 for (unsigned i = 0; list1 && list2;
682 list1 = TREE_CHAIN (list1), list2 = TREE_CHAIN (list2), i++)
683 {
684 tree parm1 = TREE_VALUE (list1);
685 tree parm2 = TREE_VALUE (list2);
686
687 /* This guard is here for function pointer with attributes (pr59927.c). */
688 if (!parm1 || !parm2)
689 return return_false_with_msg ("NULL argument type");
690
691 /* Verify that types are compatible to ensure that both functions
692 have same calling conventions. */
693 if (!types_compatible_p (parm1, parm2))
694 return return_false_with_msg ("parameter types are not compatible");
695
696 if (!param_used_p (i))
697 continue;
698
699 /* Perform additional checks for used parameters. */
700 if (!compatible_parm_types_p (parm1, parm2))
701 return false;
702 }
703
704 if (list1 || list2)
705 return return_false_with_msg ("Mismatched number of parameters");
706
707 if (node->num_references () != item->node->num_references ())
708 return return_false_with_msg ("different number of references");
709
710 /* Checking function attributes.
711 This is quadratic in number of attributes */
712 if (comp_type_attributes (TREE_TYPE (decl),
713 TREE_TYPE (item->decl)) != 1)
714 return return_false_with_msg ("different type attributes");
715 if (!compare_attributes (DECL_ATTRIBUTES (decl),
716 DECL_ATTRIBUTES (item->decl)))
717 return return_false_with_msg ("different decl attributes");
718
719 /* The type of THIS pointer type memory location for
720 ipa-polymorphic-call-analysis. */
721 if (opt_for_fn (decl, flag_devirtualize)
722 && (TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE
723 || TREE_CODE (TREE_TYPE (item->decl)) == METHOD_TYPE)
724 && param_used_p (0)
725 && compare_polymorphic_p ())
726 {
727 if (TREE_CODE (TREE_TYPE (decl)) != TREE_CODE (TREE_TYPE (item->decl)))
728 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
729 if (!func_checker::compatible_polymorphic_types_p
730 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
731 TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
732 return return_false_with_msg ("THIS pointer ODR type mismatch");
733 }
734
735 ipa_ref *ref = NULL, *ref2 = NULL;
736 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
737 {
738 item->node->iterate_reference (i, ref2);
739
740 if (ref->use != ref2->use)
741 return return_false_with_msg ("reference use mismatch");
742
743 if (!compare_symbol_references (ignored_nodes, ref->referred,
744 ref2->referred,
745 ref->address_matters_p ()))
746 return false;
747 }
748
749 cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
750 cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
751
752 while (e1 && e2)
753 {
754 if (!compare_symbol_references (ignored_nodes, e1->callee,
755 e2->callee, false))
756 return false;
757 if (!compare_edge_flags (e1, e2))
758 return false;
759
760 e1 = e1->next_callee;
761 e2 = e2->next_callee;
762 }
763
764 if (e1 || e2)
765 return return_false_with_msg ("different number of calls");
766
767 e1 = dyn_cast <cgraph_node *> (node)->indirect_calls;
768 e2 = dyn_cast <cgraph_node *> (item->node)->indirect_calls;
769
770 while (e1 && e2)
771 {
772 if (!compare_edge_flags (e1, e2))
773 return false;
774
775 e1 = e1->next_callee;
776 e2 = e2->next_callee;
777 }
778
779 if (e1 || e2)
780 return return_false_with_msg ("different number of indirect calls");
781
782 return true;
783}
784
785/* Update hash by address sensitive references. We iterate over all
786 sensitive references (address_matters_p) and we hash ultime alias
787 target of these nodes, which can improve a semantic item hash.
788
789 Also hash in referenced symbols properties. This can be done at any time
790 (as the properties should not change), but it is convenient to do it here
791 while we walk the references anyway. */
792
793void
794sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
795 sem_item *> &m_symtab_node_map)
796{
797 ipa_ref* ref;
798 inchash::hash hstate (get_hash ());
799
800 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
801 {
802 hstate.add_int (ref->use);
803 hash_referenced_symbol_properties (ref->referred, hstate,
804 ref->use == IPA_REF_ADDR);
805 if (ref->address_matters_p () || !m_symtab_node_map.get (ref->referred))
806 hstate.add_int (ref->referred->ultimate_alias_target ()->order);
807 }
808
809 if (is_a <cgraph_node *> (node))
810 {
811 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
812 e = e->next_caller)
813 {
814 sem_item **result = m_symtab_node_map.get (e->callee);
815 hash_referenced_symbol_properties (e->callee, hstate, false);
816 if (!result)
817 hstate.add_int (e->callee->ultimate_alias_target ()->order);
818 }
819 }
820
821 set_hash (hstate.end ());
822}
823
824/* Update hash by computed local hash values taken from different
825 semantic items.
826 TODO: stronger SCC based hashing would be desirable here. */
827
828void
829sem_item::update_hash_by_local_refs (hash_map <symtab_node *,
830 sem_item *> &m_symtab_node_map)
831{
832 ipa_ref* ref;
833 inchash::hash state (get_hash ());
834
835 for (unsigned j = 0; node->iterate_reference (j, ref); j++)
836 {
837 sem_item **result = m_symtab_node_map.get (ref->referring);
838 if (result)
839 state.merge_hash ((*result)->get_hash ());
840 }
841
842 if (type == FUNC)
843 {
844 for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e;
845 e = e->next_callee)
846 {
847 sem_item **result = m_symtab_node_map.get (e->caller);
848 if (result)
849 state.merge_hash ((*result)->get_hash ());
850 }
851 }
852
853 global_hash = state.end ();
854}
855
856/* Returns true if the item equals to ITEM given as argument. */
857
858bool
859sem_function::equals (sem_item *item,
860 hash_map <symtab_node *, sem_item *> &)
861{
862 gcc_assert (item->type == FUNC);
863 bool eq = equals_private (item);
864
865 if (m_checker != NULL)
866 {
867 delete m_checker;
868 m_checker = NULL;
869 }
870
871 if (dump_file && (dump_flags & TDF_DETAILS))
872 fprintf (dump_file,
873 "Equals called for: %s:%s with result: %s\n\n",
874 node->dump_name (),
875 item->node->dump_name (),
876 eq ? "true" : "false");
877
878 return eq;
879}
880
881/* Processes function equality comparison. */
882
883bool
884sem_function::equals_private (sem_item *item)
885{
886 if (item->type != FUNC)
887 return false;
888
889 basic_block bb1, bb2;
890 edge e1, e2;
891 edge_iterator ei1, ei2;
892 bool result = true;
893 tree arg1, arg2;
894
895 m_compared_func = static_cast<sem_function *> (item);
896
897 gcc_assert (decl != item->decl);
898
899 if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
900 || edge_count != m_compared_func->edge_count
901 || cfg_checksum != m_compared_func->cfg_checksum)
902 return return_false ();
903
904 m_checker = new func_checker (decl, m_compared_func->decl,
905 compare_polymorphic_p (),
906 false,
907 &refs_set,
908 &m_compared_func->refs_set);
909 arg1 = DECL_ARGUMENTS (decl);
910 arg2 = DECL_ARGUMENTS (m_compared_func->decl);
911 for (unsigned i = 0;
912 arg1 && arg2; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2), i++)
913 {
914 if (!types_compatible_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
915 return return_false_with_msg ("argument types are not compatible");
916 if (!param_used_p (i))
917 continue;
918 /* Perform additional checks for used parameters. */
919 if (!compatible_parm_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
920 return false;
921 if (!m_checker->compare_decl (arg1, arg2))
922 return return_false ();
923 }
924 if (arg1 || arg2)
925 return return_false_with_msg ("Mismatched number of arguments");
926
927 if (!dyn_cast <cgraph_node *> (node)->has_gimple_body_p ())
928 return true;
929
930 /* Fill-up label dictionary. */
931 for (unsigned i = 0; i < bb_sorted.length (); ++i)
932 {
933 m_checker->parse_labels (bb_sorted[i]);
934 m_checker->parse_labels (m_compared_func->bb_sorted[i]);
935 }
936
937 /* Checking all basic blocks. */
938 for (unsigned i = 0; i < bb_sorted.length (); ++i)
939 if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
940 return return_false();
941
942 dump_message ("All BBs are equal\n");
943
944 auto_vec <int> bb_dict;
945
946 /* Basic block edges check. */
947 for (unsigned i = 0; i < bb_sorted.length (); ++i)
948 {
949 bb1 = bb_sorted[i]->bb;
950 bb2 = m_compared_func->bb_sorted[i]->bb;
951
952 ei2 = ei_start (bb2->preds);
953
954 for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
955 {
956 ei_cond (ei2, &e2);
957
958 if (e1->flags != e2->flags)
959 return return_false_with_msg ("flags comparison returns false");
960
961 if (!bb_dict_test (&bb_dict, e1->src->index, e2->src->index))
962 return return_false_with_msg ("edge comparison returns false");
963
964 if (!bb_dict_test (&bb_dict, e1->dest->index, e2->dest->index))
965 return return_false_with_msg ("BB comparison returns false");
966
967 if (!m_checker->compare_edge (e1, e2))
968 return return_false_with_msg ("edge comparison returns false");
969
970 ei_next (&ei2);
971 }
972 }
973
974 /* Basic block PHI nodes comparison. */
975 for (unsigned i = 0; i < bb_sorted.length (); i++)
976 if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
977 return return_false_with_msg ("PHI node comparison returns false");
978
979 return result;
980}
981
982/* Set LOCAL_P of NODE to true if DATA is non-NULL.
983 Helper for call_for_symbol_thunks_and_aliases. */
984
985static bool
986set_local (cgraph_node *node, void *data)
987{
988 node->local.local = data != NULL;
989 return false;
990}
991
992/* TREE_ADDRESSABLE of NODE to true.
993 Helper for call_for_symbol_thunks_and_aliases. */
994
995static bool
996set_addressable (varpool_node *node, void *)
997{
998 TREE_ADDRESSABLE (node->decl) = 1;
999 return false;
1000}
1001
1002/* Clear DECL_RTL of NODE.
1003 Helper for call_for_symbol_thunks_and_aliases. */
1004
1005static bool
1006clear_decl_rtl (symtab_node *node, void *)
1007{
1008 SET_DECL_RTL (node->decl, NULL);
1009 return false;
1010}
1011
1012/* Redirect all callers of N and its aliases to TO. Remove aliases if
1013 possible. Return number of redirections made. */
1014
1015static int
1016redirect_all_callers (cgraph_node *n, cgraph_node *to)
1017{
1018 int nredirected = 0;
1019 ipa_ref *ref;
1020 cgraph_edge *e = n->callers;
1021
1022 while (e)
1023 {
1024 /* Redirecting thunks to interposable symbols or symbols in other sections
1025 may not be supported by target output code. Play safe for now and
1026 punt on redirection. */
1027 if (!e->caller->thunk.thunk_p)
1028 {
1029 struct cgraph_edge *nexte = e->next_caller;
1030 e->redirect_callee (to);
1031 e = nexte;
1032 nredirected++;
1033 }
1034 else
1035 e = e->next_callee;
1036 }
1037 for (unsigned i = 0; n->iterate_direct_aliases (i, ref);)
1038 {
1039 bool removed = false;
1040 cgraph_node *n_alias = dyn_cast <cgraph_node *> (ref->referring);
1041
1042 if ((DECL_COMDAT_GROUP (n->decl)
1043 && (DECL_COMDAT_GROUP (n->decl)
1044 == DECL_COMDAT_GROUP (n_alias->decl)))
1045 || (n_alias->get_availability () > AVAIL_INTERPOSABLE
1046 && n->get_availability () > AVAIL_INTERPOSABLE))
1047 {
1048 nredirected += redirect_all_callers (n_alias, to);
1049 if (n_alias->can_remove_if_no_direct_calls_p ()
1050 && !n_alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1051 NULL, true)
1052 && !n_alias->has_aliases_p ())
1053 n_alias->remove ();
1054 }
1055 if (!removed)
1056 i++;
1057 }
1058 return nredirected;
1059}
1060
1061/* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1062 be applied. */
1063
1064bool
1065sem_function::merge (sem_item *alias_item)
1066{
1067 gcc_assert (alias_item->type == FUNC);
1068
1069 sem_function *alias_func = static_cast<sem_function *> (alias_item);
1070
1071 cgraph_node *original = get_node ();
1072 cgraph_node *local_original = NULL;
1073 cgraph_node *alias = alias_func->get_node ();
1074
1075 bool create_wrapper = false;
1076 bool create_alias = false;
1077 bool redirect_callers = false;
1078 bool remove = false;
1079
1080 bool original_discardable = false;
1081 bool original_discarded = false;
1082
1083 bool original_address_matters = original->address_matters_p ();
1084 bool alias_address_matters = alias->address_matters_p ();
1085
1086 if (DECL_EXTERNAL (alias->decl))
1087 {
1088 if (dump_file)
1089 fprintf (dump_file, "Not unifying; alias is external.\n\n");
1090 return false;
1091 }
1092
1093 if (DECL_NO_INLINE_WARNING_P (original->decl)
1094 != DECL_NO_INLINE_WARNING_P (alias->decl))
1095 {
1096 if (dump_file)
1097 fprintf (dump_file,
1098 "Not unifying; "
1099 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1100 return false;
1101 }
1102
1103 /* Do not attempt to mix functions from different user sections;
1104 we do not know what user intends with those. */
1105 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
1106 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
1107 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
1108 {
1109 if (dump_file)
1110 fprintf (dump_file,
1111 "Not unifying; "
1112 "original and alias are in different sections.\n\n");
1113 return false;
1114 }
1115
1116 /* See if original is in a section that can be discarded if the main
1117 symbol is not used. */
1118
1119 if (original->can_be_discarded_p ())
1120 original_discardable = true;
1121 /* Also consider case where we have resolution info and we know that
1122 original's definition is not going to be used. In this case we can not
1123 create alias to original. */
1124 if (node->resolution != LDPR_UNKNOWN
1125 && !decl_binds_to_current_def_p (node->decl))
1126 original_discardable = original_discarded = true;
1127
1128 /* Creating a symtab alias is the optimal way to merge.
1129 It however can not be used in the following cases:
1130
1131 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1132 2) if ORIGINAL is in a section that may be discarded by linker or if
1133 it is an external functions where we can not create an alias
1134 (ORIGINAL_DISCARDABLE)
1135 3) if target do not support symbol aliases.
1136 4) original and alias lie in different comdat groups.
1137
1138 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1139 and/or redirect all callers from ALIAS to ORIGINAL. */
1140 if ((original_address_matters && alias_address_matters)
1141 || (original_discardable
1142 && (!DECL_COMDAT_GROUP (alias->decl)
1143 || (DECL_COMDAT_GROUP (alias->decl)
1144 != DECL_COMDAT_GROUP (original->decl))))
1145 || original_discarded
1146 || !sem_item::target_supports_symbol_aliases_p ()
1147 || DECL_COMDAT_GROUP (alias->decl) != DECL_COMDAT_GROUP (original->decl))
1148 {
1149 /* First see if we can produce wrapper. */
1150
1151 /* Symbol properties that matter for references must be preserved.
1152 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1153 with proper properties. */
1154 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1155 alias->address_taken))
1156 {
1157 if (dump_file)
1158 fprintf (dump_file,
1159 "Wrapper cannot be created because referenced symbol "
1160 "properties mismatch\n");
1161 }
1162 /* Do not turn function in one comdat group into wrapper to another
1163 comdat group. Other compiler producing the body of the
1164 another comdat group may make opossite decision and with unfortunate
1165 linker choices this may close a loop. */
1166 else if (DECL_COMDAT_GROUP (original->decl)
1167 && DECL_COMDAT_GROUP (alias->decl)
1168 && (DECL_COMDAT_GROUP (alias->decl)
1169 != DECL_COMDAT_GROUP (original->decl)))
1170 {
1171 if (dump_file)
1172 fprintf (dump_file,
1173 "Wrapper cannot be created because of COMDAT\n");
1174 }
1175 else if (DECL_STATIC_CHAIN (alias->decl)
1176 || DECL_STATIC_CHAIN (original->decl))
1177 {
1178 if (dump_file)
1179 fprintf (dump_file,
1180 "Cannot create wrapper of nested function.\n");
1181 }
1182 /* TODO: We can also deal with variadic functions never calling
1183 VA_START. */
1184 else if (stdarg_p (TREE_TYPE (alias->decl)))
1185 {
1186 if (dump_file)
1187 fprintf (dump_file,
1188 "can not create wrapper of stdarg function.\n");
1189 }
1190 else if (ipa_fn_summaries
1191 && ipa_fn_summaries->get (alias)->self_size <= 2)
1192 {
1193 if (dump_file)
1194 fprintf (dump_file, "Wrapper creation is not "
1195 "profitable (function is too small).\n");
1196 }
1197 /* If user paid attention to mark function noinline, assume it is
1198 somewhat special and do not try to turn it into a wrapper that can
1199 not be undone by inliner. */
1200 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
1201 {
1202 if (dump_file)
1203 fprintf (dump_file, "Wrappers are not created for noinline.\n");
1204 }
1205 else
1206 create_wrapper = true;
1207
1208 /* We can redirect local calls in the case both alias and orignal
1209 are not interposable. */
1210 redirect_callers
1211 = alias->get_availability () > AVAIL_INTERPOSABLE
1212 && original->get_availability () > AVAIL_INTERPOSABLE
1213 && !alias->instrumented_version;
1214 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1215 with proper properties. */
1216 if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1217 alias->address_taken))
1218 redirect_callers = false;
1219
1220 if (!redirect_callers && !create_wrapper)
1221 {
1222 if (dump_file)
1223 fprintf (dump_file, "Not unifying; can not redirect callers nor "
1224 "produce wrapper\n\n");
1225 return false;
1226 }
1227
1228 /* Work out the symbol the wrapper should call.
1229 If ORIGINAL is interposable, we need to call a local alias.
1230 Also produce local alias (if possible) as an optimization.
1231
1232 Local aliases can not be created inside comdat groups because that
1233 prevents inlining. */
1234 if (!original_discardable && !original->get_comdat_group ())
1235 {
1236 local_original
1237 = dyn_cast <cgraph_node *> (original->noninterposable_alias ());
1238 if (!local_original
1239 && original->get_availability () > AVAIL_INTERPOSABLE)
1240 local_original = original;
1241 }
1242 /* If we can not use local alias, fallback to the original
1243 when possible. */
1244 else if (original->get_availability () > AVAIL_INTERPOSABLE)
1245 local_original = original;
1246
1247 /* If original is COMDAT local, we can not really redirect calls outside
1248 of its comdat group to it. */
1249 if (original->comdat_local_p ())
1250 redirect_callers = false;
1251 if (!local_original)
1252 {
1253 if (dump_file)
1254 fprintf (dump_file, "Not unifying; "
1255 "can not produce local alias.\n\n");
1256 return false;
1257 }
1258
1259 if (!redirect_callers && !create_wrapper)
1260 {
1261 if (dump_file)
1262 fprintf (dump_file, "Not unifying; "
1263 "can not redirect callers nor produce a wrapper\n\n");
1264 return false;
1265 }
1266 if (!create_wrapper
1267 && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1268 NULL, true)
1269 && !alias->can_remove_if_no_direct_calls_p ())
1270 {
1271 if (dump_file)
1272 fprintf (dump_file, "Not unifying; can not make wrapper and "
1273 "function has other uses than direct calls\n\n");
1274 return false;
1275 }
1276 }
1277 else
1278 create_alias = true;
1279
1280 if (redirect_callers)
1281 {
1282 int nredirected = redirect_all_callers (alias, local_original);
1283
1284 if (nredirected)
1285 {
1286 alias->icf_merged = true;
1287 local_original->icf_merged = true;
1288
1289 if (dump_file && nredirected)
1290 fprintf (dump_file, "%i local calls have been "
1291 "redirected.\n", nredirected);
1292 }
1293
1294 /* If all callers was redirected, do not produce wrapper. */
1295 if (alias->can_remove_if_no_direct_calls_p ()
1296 && !DECL_VIRTUAL_P (alias->decl)
1297 && !alias->has_aliases_p ())
1298 {
1299 create_wrapper = false;
1300 remove = true;
1301 }
1302 gcc_assert (!create_alias);
1303 }
1304 else if (create_alias)
1305 {
1306 alias->icf_merged = true;
1307
1308 /* Remove the function's body. */
1309 ipa_merge_profiles (original, alias);
1310 alias->release_body (true);
1311 alias->reset ();
1312 /* Notice global symbol possibly produced RTL. */
1313 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
1314 NULL, true);
1315
1316 /* Create the alias. */
1317 cgraph_node::create_alias (alias_func->decl, decl);
1318 alias->resolve_alias (original);
1319
1320 original->call_for_symbol_thunks_and_aliases
1321 (set_local, (void *)(size_t) original->local_p (), true);
1322
1323 if (dump_file)
1324 fprintf (dump_file, "Unified; Function alias has been created.\n\n");
1325 }
1326 if (create_wrapper)
1327 {
1328 gcc_assert (!create_alias);
1329 alias->icf_merged = true;
1330 local_original->icf_merged = true;
1331
1332 /* FIXME update local_original counts. */
1333 ipa_merge_profiles (original, alias, true);
1334 alias->create_wrapper (local_original);
1335
1336 if (dump_file)
1337 fprintf (dump_file, "Unified; Wrapper has been created.\n\n");
1338 }
1339
1340 /* It's possible that redirection can hit thunks that block
1341 redirection opportunities. */
1342 gcc_assert (alias->icf_merged || remove || redirect_callers);
1343 original->icf_merged = true;
1344
1345 /* We use merged flag to track cases where COMDAT function is known to be
1346 compatible its callers. If we merged in non-COMDAT, we need to give up
1347 on this optimization. */
1348 if (original->merged_comdat && !alias->merged_comdat)
1349 {
1350 if (dump_file)
1351 fprintf (dump_file, "Dropping merged_comdat flag.\n\n");
1352 if (local_original)
1353 local_original->merged_comdat = false;
1354 original->merged_comdat = false;
1355 }
1356
1357 if (remove)
1358 {
1359 ipa_merge_profiles (original, alias);
1360 alias->release_body ();
1361 alias->reset ();
1362 alias->body_removed = true;
1363 alias->icf_merged = true;
1364 if (dump_file)
1365 fprintf (dump_file, "Unified; Function body was removed.\n");
1366 }
1367
1368 return true;
1369}
1370
1371/* Semantic item initialization function. */
1372
1373void
1374sem_function::init (void)
1375{
1376 if (in_lto_p)
1377 get_node ()->get_untransformed_body ();
1378
1379 tree fndecl = node->decl;
1380 function *func = DECL_STRUCT_FUNCTION (fndecl);
1381
1382 gcc_assert (func);
1383 gcc_assert (SSANAMES (func));
1384
1385 ssa_names_size = SSANAMES (func)->length ();
1386 node = node;
1387
1388 decl = fndecl;
1389 region_tree = func->eh->region_tree;
1390
1391 /* iterating all function arguments. */
1392 arg_count = count_formal_params (fndecl);
1393
1394 edge_count = n_edges_for_fn (func);
1395 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1396 if (!cnode->thunk.thunk_p)
1397 {
1398 cfg_checksum = coverage_compute_cfg_checksum (func);
1399
1400 inchash::hash hstate;
1401
1402 basic_block bb;
1403 FOR_EACH_BB_FN (bb, func)
1404 {
1405 unsigned nondbg_stmt_count = 0;
1406
1407 edge e;
1408 for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
1409 ei_next (&ei))
1410 cfg_checksum = iterative_hash_host_wide_int (e->flags,
1411 cfg_checksum);
1412
1413 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1414 gsi_next (&gsi))
1415 {
1416 gimple *stmt = gsi_stmt (gsi);
1417
1418 if (gimple_code (stmt) != GIMPLE_DEBUG
1419 && gimple_code (stmt) != GIMPLE_PREDICT)
1420 {
1421 hash_stmt (stmt, hstate);
1422 nondbg_stmt_count++;
1423 }
1424 }
1425
1426 hstate.commit_flag ();
1427 gcode_hash = hstate.end ();
1428 bb_sizes.safe_push (nondbg_stmt_count);
1429
1430 /* Inserting basic block to hash table. */
1431 sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
1432 EDGE_COUNT (bb->preds)
1433 + EDGE_COUNT (bb->succs));
1434
1435 bb_sorted.safe_push (semantic_bb);
1436 }
1437 }
1438 else
1439 {
1440 cfg_checksum = 0;
1441 inchash::hash hstate;
1442 hstate.add_hwi (cnode->thunk.fixed_offset);
1443 hstate.add_hwi (cnode->thunk.virtual_value);
1444 hstate.add_flag (cnode->thunk.this_adjusting);
1445 hstate.add_flag (cnode->thunk.virtual_offset_p);
1446 hstate.add_flag (cnode->thunk.add_pointer_bounds_args);
1447 gcode_hash = hstate.end ();
1448 }
1449}
1450
1451/* Accumulate to HSTATE a hash of expression EXP.
1452 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1453 and DECL equality classes. */
1454
1455void
1456sem_item::add_expr (const_tree exp, inchash::hash &hstate)
1457{
1458 if (exp == NULL_TREE)
1459 {
1460 hstate.merge_hash (0);
1461 return;
1462 }
1463
1464 /* Handled component can be matched in a cureful way proving equivalence
1465 even if they syntactically differ. Just skip them. */
1466 STRIP_NOPS (exp);
1467 while (handled_component_p (exp))
1468 exp = TREE_OPERAND (exp, 0);
1469
1470 enum tree_code code = TREE_CODE (exp);
1471 hstate.add_int (code);
1472
1473 switch (code)
1474 {
1475 /* Use inchash::add_expr for everything that is LTO stable. */
1476 case VOID_CST:
1477 case INTEGER_CST:
1478 case REAL_CST:
1479 case FIXED_CST:
1480 case STRING_CST:
1481 case COMPLEX_CST:
1482 case VECTOR_CST:
1483 inchash::add_expr (exp, hstate);
1484 break;
1485 case CONSTRUCTOR:
1486 {
1487 unsigned HOST_WIDE_INT idx;
1488 tree value;
1489
1490 hstate.add_hwi (int_size_in_bytes (TREE_TYPE (exp)));
1491
1492 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp), idx, value)
1493 if (value)
1494 add_expr (value, hstate);
1495 break;
1496 }
1497 case ADDR_EXPR:
1498 case FDESC_EXPR:
1499 add_expr (get_base_address (TREE_OPERAND (exp, 0)), hstate);
1500 break;
1501 case SSA_NAME:
1502 case VAR_DECL:
1503 case CONST_DECL:
1504 case PARM_DECL:
1505 hstate.add_hwi (int_size_in_bytes (TREE_TYPE (exp)));
1506 break;
1507 case MEM_REF:
1508 case POINTER_PLUS_EXPR:
1509 case MINUS_EXPR:
1510 case RANGE_EXPR:
1511 add_expr (TREE_OPERAND (exp, 0), hstate);
1512 add_expr (TREE_OPERAND (exp, 1), hstate);
1513 break;
1514 case PLUS_EXPR:
1515 {
1516 inchash::hash one, two;
1517 add_expr (TREE_OPERAND (exp, 0), one);
1518 add_expr (TREE_OPERAND (exp, 1), two);
1519 hstate.add_commutative (one, two);
1520 }
1521 break;
1522 CASE_CONVERT:
1523 hstate.add_hwi (int_size_in_bytes (TREE_TYPE (exp)));
1524 return add_expr (TREE_OPERAND (exp, 0), hstate);
1525 default:
1526 break;
1527 }
1528}
1529
1530/* Accumulate to HSTATE a hash of type t.
1531 TYpes that may end up being compatible after LTO type merging needs to have
1532 the same hash. */
1533
1534void
1535sem_item::add_type (const_tree type, inchash::hash &hstate)
1536{
1537 if (type == NULL_TREE)
1538 {
1539 hstate.merge_hash (0);
1540 return;
1541 }
1542
1543 type = TYPE_MAIN_VARIANT (type);
1544
1545 hstate.add_int (TYPE_MODE (type));
1546
1547 if (TREE_CODE (type) == COMPLEX_TYPE)
1548 {
1549 hstate.add_int (COMPLEX_TYPE);
1550 sem_item::add_type (TREE_TYPE (type), hstate);
1551 }
1552 else if (INTEGRAL_TYPE_P (type))
1553 {
1554 hstate.add_int (INTEGER_TYPE);
1555 hstate.add_flag (TYPE_UNSIGNED (type));
1556 hstate.add_int (TYPE_PRECISION (type));
1557 }
1558 else if (VECTOR_TYPE_P (type))
1559 {
1560 hstate.add_int (VECTOR_TYPE);
1561 hstate.add_int (TYPE_PRECISION (type));
1562 sem_item::add_type (TREE_TYPE (type), hstate);
1563 }
1564 else if (TREE_CODE (type) == ARRAY_TYPE)
1565 {
1566 hstate.add_int (ARRAY_TYPE);
1567 /* Do not hash size, so complete and incomplete types can match. */
1568 sem_item::add_type (TREE_TYPE (type), hstate);
1569 }
1570 else if (RECORD_OR_UNION_TYPE_P (type))
1571 {
1572 gcc_checking_assert (COMPLETE_TYPE_P (type));
1573 hashval_t *val = optimizer->m_type_hash_cache.get (type);
1574
1575 if (!val)
1576 {
1577 inchash::hash hstate2;
1578 unsigned nf;
1579 tree f;
1580 hashval_t hash;
1581
1582 hstate2.add_int (RECORD_TYPE);
1583 gcc_assert (COMPLETE_TYPE_P (type));
1584
1585 for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
1586 if (TREE_CODE (f) == FIELD_DECL)
1587 {
1588 add_type (TREE_TYPE (f), hstate2);
1589 nf++;
1590 }
1591
1592 hstate2.add_int (nf);
1593 hash = hstate2.end ();
1594 hstate.add_hwi (hash);
1595 optimizer->m_type_hash_cache.put (type, hash);
1596 }
1597 else
1598 hstate.add_hwi (*val);
1599 }
1600}
1601
1602/* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1603
1604void
1605sem_function::hash_stmt (gimple *stmt, inchash::hash &hstate)
1606{
1607 enum gimple_code code = gimple_code (stmt);
1608
1609 hstate.add_int (code);
1610
1611 switch (code)
1612 {
1613 case GIMPLE_SWITCH:
1614 add_expr (gimple_switch_index (as_a <gswitch *> (stmt)), hstate);
1615 break;
1616 case GIMPLE_ASSIGN:
1617 hstate.add_int (gimple_assign_rhs_code (stmt));
1618 if (commutative_tree_code (gimple_assign_rhs_code (stmt))
1619 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1620 {
1621 inchash::hash one, two;
1622
1623 add_expr (gimple_assign_rhs1 (stmt), one);
1624 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt)), one);
1625 add_expr (gimple_assign_rhs2 (stmt), two);
1626 hstate.add_commutative (one, two);
1627 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt)))
1628 {
1629 add_expr (gimple_assign_rhs3 (stmt), hstate);
1630 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt)), hstate);
1631 }
1632 add_expr (gimple_assign_lhs (stmt), hstate);
1633 add_type (TREE_TYPE (gimple_assign_lhs (stmt)), two);
1634 break;
1635 }
1636 /* fall through */
1637 case GIMPLE_CALL:
1638 case GIMPLE_ASM:
1639 case GIMPLE_COND:
1640 case GIMPLE_GOTO:
1641 case GIMPLE_RETURN:
1642 /* All these statements are equivalent if their operands are. */
1643 for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1644 {
1645 add_expr (gimple_op (stmt, i), hstate);
1646 if (gimple_op (stmt, i))
1647 add_type (TREE_TYPE (gimple_op (stmt, i)), hstate);
1648 }
1649 /* Consider nocf_check attribute in hash as it affects code
1650 generation. */
1651 if (code == GIMPLE_CALL
1652 && flag_cf_protection & CF_BRANCH)
1653 hstate.add_flag (gimple_call_nocf_check_p (as_a <gcall *> (stmt)));
1654 default:
1655 break;
1656 }
1657}
1658
1659
1660/* Return true if polymorphic comparison must be processed. */
1661
1662bool
1663sem_function::compare_polymorphic_p (void)
1664{
1665 struct cgraph_edge *e;
1666
1667 if (!opt_for_fn (get_node ()->decl, flag_devirtualize))
1668 return false;
1669 if (get_node ()->indirect_calls != NULL)
1670 return true;
1671 /* TODO: We can do simple propagation determining what calls may lead to
1672 a polymorphic call. */
1673 for (e = get_node ()->callees; e; e = e->next_callee)
1674 if (e->callee->definition
1675 && opt_for_fn (e->callee->decl, flag_devirtualize))
1676 return true;
1677 return false;
1678}
1679
1680/* For a given call graph NODE, the function constructs new
1681 semantic function item. */
1682
1683sem_function *
1684sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
1685{
1686 tree fndecl = node->decl;
1687 function *func = DECL_STRUCT_FUNCTION (fndecl);
1688
1689 if (!func || (!node->has_gimple_body_p () && !node->thunk.thunk_p))
1690 return NULL;
1691
1692 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
1693 return NULL;
1694
1695 if (lookup_attribute_by_prefix ("oacc ",
1696 DECL_ATTRIBUTES (node->decl)) != NULL)
1697 return NULL;
1698
1699 /* PR ipa/70306. */
1700 if (DECL_STATIC_CONSTRUCTOR (node->decl)
1701 || DECL_STATIC_DESTRUCTOR (node->decl))
1702 return NULL;
1703
1704 sem_function *f = new sem_function (node, stack);
1705
1706 f->init ();
1707
1708 return f;
1709}
1710
1711/* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1712 return true if phi nodes are semantically equivalent in these blocks . */
1713
1714bool
1715sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
1716{
1717 gphi_iterator si1, si2;
1718 gphi *phi1, *phi2;
1719 unsigned size1, size2, i;
1720 tree t1, t2;
1721 edge e1, e2;
1722
1723 gcc_assert (bb1 != NULL);
1724 gcc_assert (bb2 != NULL);
1725
1726 si2 = gsi_start_phis (bb2);
1727 for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
1728 gsi_next (&si1))
1729 {
1730 gsi_next_nonvirtual_phi (&si1);
1731 gsi_next_nonvirtual_phi (&si2);
1732
1733 if (gsi_end_p (si1) && gsi_end_p (si2))
1734 break;
1735
1736 if (gsi_end_p (si1) || gsi_end_p (si2))
1737 return return_false();
1738
1739 phi1 = si1.phi ();
1740 phi2 = si2.phi ();
1741
1742 tree phi_result1 = gimple_phi_result (phi1);
1743 tree phi_result2 = gimple_phi_result (phi2);
1744
1745 if (!m_checker->compare_operand (phi_result1, phi_result2))
1746 return return_false_with_msg ("PHI results are different");
1747
1748 size1 = gimple_phi_num_args (phi1);
1749 size2 = gimple_phi_num_args (phi2);
1750
1751 if (size1 != size2)
1752 return return_false ();
1753
1754 for (i = 0; i < size1; ++i)
1755 {
1756 t1 = gimple_phi_arg (phi1, i)->def;
1757 t2 = gimple_phi_arg (phi2, i)->def;
1758
1759 if (!m_checker->compare_operand (t1, t2))
1760 return return_false ();
1761
1762 e1 = gimple_phi_arg_edge (phi1, i);
1763 e2 = gimple_phi_arg_edge (phi2, i);
1764
1765 if (!m_checker->compare_edge (e1, e2))
1766 return return_false ();
1767 }
1768
1769 gsi_next (&si2);
1770 }
1771
1772 return true;
1773}
1774
1775/* Returns true if tree T can be compared as a handled component. */
1776
1777bool
1778sem_function::icf_handled_component_p (tree t)
1779{
1780 tree_code tc = TREE_CODE (t);
1781
1782 return (handled_component_p (t)
1783 || tc == ADDR_EXPR || tc == MEM_REF || tc == OBJ_TYPE_REF);
1784}
1785
1786/* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1787 corresponds to TARGET. */
1788
1789bool
1790sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
1791{
1792 source++;
1793 target++;
1794
1795 if (bb_dict->length () <= (unsigned)source)
1796 bb_dict->safe_grow_cleared (source + 1);
1797
1798 if ((*bb_dict)[source] == 0)
1799 {
1800 (*bb_dict)[source] = target;
1801 return true;
1802 }
1803 else
1804 return (*bb_dict)[source] == target;
1805}
1806
1807sem_variable::sem_variable (bitmap_obstack *stack): sem_item (VAR, stack)
1808{
1809}
1810
1811sem_variable::sem_variable (varpool_node *node, bitmap_obstack *stack)
1812: sem_item (VAR, node, stack)
1813{
1814 gcc_checking_assert (node);
1815 gcc_checking_assert (get_node ());
1816}
1817
1818/* Fast equality function based on knowledge known in WPA. */
1819
1820bool
1821sem_variable::equals_wpa (sem_item *item,
1822 hash_map <symtab_node *, sem_item *> &ignored_nodes)
1823{
1824 gcc_assert (item->type == VAR);
1825
1826 if (node->num_references () != item->node->num_references ())
1827 return return_false_with_msg ("different number of references");
1828
1829 if (DECL_TLS_MODEL (decl) || DECL_TLS_MODEL (item->decl))
1830 return return_false_with_msg ("TLS model");
1831
1832 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1833 alignment out of all aliases. */
1834
1835 if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
1836 return return_false_with_msg ("Virtual flag mismatch");
1837
1838 if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
1839 && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
1840 || !operand_equal_p (DECL_SIZE (decl),
1841 DECL_SIZE (item->decl), OEP_ONLY_CONST)))
1842 return return_false_with_msg ("size mismatch");
1843
1844 /* Do not attempt to mix data from different user sections;
1845 we do not know what user intends with those. */
1846 if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
1847 || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
1848 && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
1849 return return_false_with_msg ("user section mismatch");
1850
1851 if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
1852 return return_false_with_msg ("text section");
1853
1854 ipa_ref *ref = NULL, *ref2 = NULL;
1855 for (unsigned i = 0; node->iterate_reference (i, ref); i++)
1856 {
1857 item->node->iterate_reference (i, ref2);
1858
1859 if (ref->use != ref2->use)
1860 return return_false_with_msg ("reference use mismatch");
1861
1862 if (!compare_symbol_references (ignored_nodes,
1863 ref->referred, ref2->referred,
1864 ref->address_matters_p ()))
1865 return false;
1866 }
1867
1868 return true;
1869}
1870
1871/* Returns true if the item equals to ITEM given as argument. */
1872
1873bool
1874sem_variable::equals (sem_item *item,
1875 hash_map <symtab_node *, sem_item *> &)
1876{
1877 gcc_assert (item->type == VAR);
1878 bool ret;
1879
1880 if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
1881 dyn_cast <varpool_node *>(node)->get_constructor ();
1882 if (DECL_INITIAL (item->decl) == error_mark_node && in_lto_p)
1883 dyn_cast <varpool_node *>(item->node)->get_constructor ();
1884
1885 /* As seen in PR ipa/65303 we have to compare variables types. */
1886 if (!func_checker::compatible_types_p (TREE_TYPE (decl),
1887 TREE_TYPE (item->decl)))
1888 return return_false_with_msg ("variables types are different");
1889
1890 ret = sem_variable::equals (DECL_INITIAL (decl),
1891 DECL_INITIAL (item->node->decl));
1892 if (dump_file && (dump_flags & TDF_DETAILS))
1893 fprintf (dump_file,
1894 "Equals called for vars: %s:%s with result: %s\n\n",
1895 node->dump_name (), item->node->dump_name (),
1896 ret ? "true" : "false");
1897
1898 return ret;
1899}
1900
1901/* Compares trees T1 and T2 for semantic equality. */
1902
1903bool
1904sem_variable::equals (tree t1, tree t2)
1905{
1906 if (!t1 || !t2)
1907 return return_with_debug (t1 == t2);
1908 if (t1 == t2)
1909 return true;
1910 tree_code tc1 = TREE_CODE (t1);
1911 tree_code tc2 = TREE_CODE (t2);
1912
1913 if (tc1 != tc2)
1914 return return_false_with_msg ("TREE_CODE mismatch");
1915
1916 switch (tc1)
1917 {
1918 case CONSTRUCTOR:
1919 {
1920 vec<constructor_elt, va_gc> *v1, *v2;
1921 unsigned HOST_WIDE_INT idx;
1922
1923 enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
1924 if (typecode != TREE_CODE (TREE_TYPE (t2)))
1925 return return_false_with_msg ("constructor type mismatch");
1926
1927 if (typecode == ARRAY_TYPE)
1928 {
1929 HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
1930 /* For arrays, check that the sizes all match. */
1931 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
1932 || size_1 == -1
1933 || size_1 != int_size_in_bytes (TREE_TYPE (t2)))
1934 return return_false_with_msg ("constructor array size mismatch");
1935 }
1936 else if (!func_checker::compatible_types_p (TREE_TYPE (t1),
1937 TREE_TYPE (t2)))
1938 return return_false_with_msg ("constructor type incompatible");
1939
1940 v1 = CONSTRUCTOR_ELTS (t1);
1941 v2 = CONSTRUCTOR_ELTS (t2);
1942 if (vec_safe_length (v1) != vec_safe_length (v2))
1943 return return_false_with_msg ("constructor number of elts mismatch");
1944
1945 for (idx = 0; idx < vec_safe_length (v1); ++idx)
1946 {
1947 constructor_elt *c1 = &(*v1)[idx];
1948 constructor_elt *c2 = &(*v2)[idx];
1949
1950 /* Check that each value is the same... */
1951 if (!sem_variable::equals (c1->value, c2->value))
1952 return false;
1953 /* ... and that they apply to the same fields! */
1954 if (!sem_variable::equals (c1->index, c2->index))
1955 return false;
1956 }
1957 return true;
1958 }
1959 case MEM_REF:
1960 {
1961 tree x1 = TREE_OPERAND (t1, 0);
1962 tree x2 = TREE_OPERAND (t2, 0);
1963 tree y1 = TREE_OPERAND (t1, 1);
1964 tree y2 = TREE_OPERAND (t2, 1);
1965
1966 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
1967 return return_false ();
1968
1969 /* Type of the offset on MEM_REF does not matter. */
1970 return return_with_debug (sem_variable::equals (x1, x2)
1971 && wi::to_offset (y1)
1972 == wi::to_offset (y2));
1973 }
1974 case ADDR_EXPR:
1975 case FDESC_EXPR:
1976 {
1977 tree op1 = TREE_OPERAND (t1, 0);
1978 tree op2 = TREE_OPERAND (t2, 0);
1979 return sem_variable::equals (op1, op2);
1980 }
1981 /* References to other vars/decls are compared using ipa-ref. */
1982 case FUNCTION_DECL:
1983 case VAR_DECL:
1984 if (decl_in_symtab_p (t1) && decl_in_symtab_p (t2))
1985 return true;
1986 return return_false_with_msg ("Declaration mismatch");
1987 case CONST_DECL:
1988 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1989 need to process its VAR/FUNCTION references without relying on ipa-ref
1990 compare. */
1991 case FIELD_DECL:
1992 case LABEL_DECL:
1993 return return_false_with_msg ("Declaration mismatch");
1994 case INTEGER_CST:
1995 /* Integer constants are the same only if the same width of type. */
1996 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1997 return return_false_with_msg ("INTEGER_CST precision mismatch");
1998 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1999 return return_false_with_msg ("INTEGER_CST mode mismatch");
2000 return return_with_debug (tree_int_cst_equal (t1, t2));
2001 case STRING_CST:
2002 if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
2003 return return_false_with_msg ("STRING_CST mode mismatch");
2004 if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
2005 return return_false_with_msg ("STRING_CST length mismatch");
2006 if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
2007 TREE_STRING_LENGTH (t1)))
2008 return return_false_with_msg ("STRING_CST mismatch");
2009 return true;
2010 case FIXED_CST:
2011 /* Fixed constants are the same only if the same width of type. */
2012 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2013 return return_false_with_msg ("FIXED_CST precision mismatch");
2014
2015 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
2016 TREE_FIXED_CST (t2)));
2017 case COMPLEX_CST:
2018 return (sem_variable::equals (TREE_REALPART (t1), TREE_REALPART (t2))
2019 && sem_variable::equals (TREE_IMAGPART (t1), TREE_IMAGPART (t2)));
2020 case REAL_CST:
2021 /* Real constants are the same only if the same width of type. */
2022 if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
2023 return return_false_with_msg ("REAL_CST precision mismatch");
2024 return return_with_debug (real_identical (&TREE_REAL_CST (t1),
2025 &TREE_REAL_CST (t2)));
2026 case VECTOR_CST:
2027 {
2028 if (VECTOR_CST_NELTS (t1) != VECTOR_CST_NELTS (t2))
2029 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2030
2031 unsigned int count
2032 = tree_vector_builder::binary_encoded_nelts (t1, t2);
2033 for (unsigned int i = 0; i < count; ++i)
2034 if (!sem_variable::equals (VECTOR_CST_ENCODED_ELT (t1, i),
2035 VECTOR_CST_ENCODED_ELT (t2, i)))
2036 return false;
2037
2038 return true;
2039 }
2040 case ARRAY_REF:
2041 case ARRAY_RANGE_REF:
2042 {
2043 tree x1 = TREE_OPERAND (t1, 0);
2044 tree x2 = TREE_OPERAND (t2, 0);
2045 tree y1 = TREE_OPERAND (t1, 1);
2046 tree y2 = TREE_OPERAND (t2, 1);
2047
2048 if (!sem_variable::equals (x1, x2) || !sem_variable::equals (y1, y2))
2049 return false;
2050 if (!sem_variable::equals (array_ref_low_bound (t1),
2051 array_ref_low_bound (t2)))
2052 return false;
2053 if (!sem_variable::equals (array_ref_element_size (t1),
2054 array_ref_element_size (t2)))
2055 return false;
2056 return true;
2057 }
2058
2059 case COMPONENT_REF:
2060 case POINTER_PLUS_EXPR:
2061 case PLUS_EXPR:
2062 case MINUS_EXPR:
2063 case RANGE_EXPR:
2064 {
2065 tree x1 = TREE_OPERAND (t1, 0);
2066 tree x2 = TREE_OPERAND (t2, 0);
2067 tree y1 = TREE_OPERAND (t1, 1);
2068 tree y2 = TREE_OPERAND (t2, 1);
2069
2070 return sem_variable::equals (x1, x2) && sem_variable::equals (y1, y2);
2071 }
2072
2073 CASE_CONVERT:
2074 case VIEW_CONVERT_EXPR:
2075 if (!func_checker::compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
2076 return return_false ();
2077 return sem_variable::equals (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
2078 case ERROR_MARK:
2079 return return_false_with_msg ("ERROR_MARK");
2080 default:
2081 return return_false_with_msg ("Unknown TREE code reached");
2082 }
2083}
2084
2085/* Parser function that visits a varpool NODE. */
2086
2087sem_variable *
2088sem_variable::parse (varpool_node *node, bitmap_obstack *stack)
2089{
2090 if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl)
2091 || node->alias)
2092 return NULL;
2093
2094 sem_variable *v = new sem_variable (node, stack);
2095
2096 v->init ();
2097
2098 return v;
2099}
2100
2101/* References independent hash function. */
2102
2103hashval_t
2104sem_variable::get_hash (void)
2105{
2106 if (m_hash_set)
2107 return m_hash;
2108
2109 /* All WPA streamed in symbols should have their hashes computed at compile
2110 time. At this point, the constructor may not be in memory at all.
2111 DECL_INITIAL (decl) would be error_mark_node in that case. */
2112 gcc_assert (!node->lto_file_data);
2113 tree ctor = DECL_INITIAL (decl);
2114 inchash::hash hstate;
2115
2116 hstate.add_int (456346417);
2117 if (DECL_SIZE (decl) && tree_fits_shwi_p (DECL_SIZE (decl)))
2118 hstate.add_hwi (tree_to_shwi (DECL_SIZE (decl)));
2119 add_expr (ctor, hstate);
2120 set_hash (hstate.end ());
2121
2122 return m_hash;
2123}
2124
2125/* Set all points-to UIDs of aliases pointing to node N as UID. */
2126
2127static void
2128set_alias_uids (symtab_node *n, int uid)
2129{
2130 ipa_ref *ref;
2131 FOR_EACH_ALIAS (n, ref)
2132 {
2133 if (dump_file)
2134 fprintf (dump_file, " Setting points-to UID of [%s] as %d\n",
2135 xstrdup_for_dump (ref->referring->asm_name ()), uid);
2136
2137 SET_DECL_PT_UID (ref->referring->decl, uid);
2138 set_alias_uids (ref->referring, uid);
2139 }
2140}
2141
2142/* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2143 be applied. */
2144
2145bool
2146sem_variable::merge (sem_item *alias_item)
2147{
2148 gcc_assert (alias_item->type == VAR);
2149
2150 if (!sem_item::target_supports_symbol_aliases_p ())
2151 {
2152 if (dump_file)
2153 fprintf (dump_file, "Not unifying; "
2154 "Symbol aliases are not supported by target\n\n");
2155 return false;
2156 }
2157
2158 if (DECL_EXTERNAL (alias_item->decl))
2159 {
2160 if (dump_file)
2161 fprintf (dump_file, "Not unifying; alias is external.\n\n");
2162 return false;
2163 }
2164
2165 sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
2166
2167 varpool_node *original = get_node ();
2168 varpool_node *alias = alias_var->get_node ();
2169 bool original_discardable = false;
2170
2171 bool alias_address_matters = alias->address_matters_p ();
2172
2173 /* See if original is in a section that can be discarded if the main
2174 symbol is not used.
2175 Also consider case where we have resolution info and we know that
2176 original's definition is not going to be used. In this case we can not
2177 create alias to original. */
2178 if (original->can_be_discarded_p ()
2179 || (node->resolution != LDPR_UNKNOWN
2180 && !decl_binds_to_current_def_p (node->decl)))
2181 original_discardable = true;
2182
2183 gcc_assert (!TREE_ASM_WRITTEN (alias->decl));
2184
2185 /* Constant pool machinery is not quite ready for aliases.
2186 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2187 For LTO merging does not happen that is an important missing feature.
2188 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2189 flag is dropped and non-local symbol name is assigned. */
2190 if (DECL_IN_CONSTANT_POOL (alias->decl)
2191 || DECL_IN_CONSTANT_POOL (original->decl))
2192 {
2193 if (dump_file)
2194 fprintf (dump_file,
2195 "Not unifying; constant pool variables.\n\n");
2196 return false;
2197 }
2198
2199 /* Do not attempt to mix functions from different user sections;
2200 we do not know what user intends with those. */
2201 if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
2202 || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
2203 && DECL_SECTION_NAME (original->decl) != DECL_SECTION_NAME (alias->decl))
2204 {
2205 if (dump_file)
2206 fprintf (dump_file,
2207 "Not unifying; "
2208 "original and alias are in different sections.\n\n");
2209 return false;
2210 }
2211
2212 /* We can not merge if address comparsion metters. */
2213 if (alias_address_matters && flag_merge_constants < 2)
2214 {
2215 if (dump_file)
2216 fprintf (dump_file,
2217 "Not unifying; address of original may be compared.\n\n");
2218 return false;
2219 }
2220
2221 if (DECL_ALIGN (original->decl) < DECL_ALIGN (alias->decl))
2222 {
2223 if (dump_file)
2224 fprintf (dump_file, "Not unifying; "
2225 "original and alias have incompatible alignments\n\n");
2226
2227 return false;
2228 }
2229
2230 if (DECL_COMDAT_GROUP (original->decl) != DECL_COMDAT_GROUP (alias->decl))
2231 {
2232 if (dump_file)
2233 fprintf (dump_file, "Not unifying; alias cannot be created; "
2234 "across comdat group boundary\n\n");
2235
2236 return false;
2237 }
2238
2239 if (original_discardable)
2240 {
2241 if (dump_file)
2242 fprintf (dump_file, "Not unifying; alias cannot be created; "
2243 "target is discardable\n\n");
2244
2245 return false;
2246 }
2247 else
2248 {
2249 gcc_assert (!original->alias);
2250 gcc_assert (!alias->alias);
2251
2252 alias->analyzed = false;
2253
2254 DECL_INITIAL (alias->decl) = NULL;
2255 ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
2256 NULL, true);
2257 alias->need_bounds_init = false;
2258 alias->remove_all_references ();
2259 if (TREE_ADDRESSABLE (alias->decl))
2260 original->call_for_symbol_and_aliases (set_addressable, NULL, true);
2261
2262 varpool_node::create_alias (alias_var->decl, decl);
2263 alias->resolve_alias (original);
2264
2265 if (dump_file)
2266 fprintf (dump_file, "Unified; Variable alias has been created.\n");
2267
2268 set_alias_uids (original, DECL_UID (original->decl));
2269 return true;
2270 }
2271}
2272
2273/* Dump symbol to FILE. */
2274
2275void
2276sem_variable::dump_to_file (FILE *file)
2277{
2278 gcc_assert (file);
2279
2280 print_node (file, "", decl, 0);
2281 fprintf (file, "\n\n");
2282}
2283
2284unsigned int sem_item_optimizer::class_id = 0;
2285
2286sem_item_optimizer::sem_item_optimizer ()
2287: worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL),
2288 m_varpool_node_hooks (NULL)
2289{
2290 m_items.create (0);
2291 bitmap_obstack_initialize (&m_bmstack);
2292}
2293
2294sem_item_optimizer::~sem_item_optimizer ()
2295{
2296 for (unsigned int i = 0; i < m_items.length (); i++)
2297 delete m_items[i];
2298
2299
2300 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
2301 it != m_classes.end (); ++it)
2302 {
2303 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2304 delete (*it)->classes[i];
2305
2306 (*it)->classes.release ();
2307 free (*it);
2308 }
2309
2310 m_items.release ();
2311
2312 bitmap_obstack_release (&m_bmstack);
2313}
2314
2315/* Write IPA ICF summary for symbols. */
2316
2317void
2318sem_item_optimizer::write_summary (void)
2319{
2320 unsigned int count = 0;
2321
2322 output_block *ob = create_output_block (LTO_section_ipa_icf);
2323 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
2324 ob->symbol = NULL;
2325
2326 /* Calculate number of symbols to be serialized. */
2327 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2328 !lsei_end_p (lsei);
2329 lsei_next_in_partition (&lsei))
2330 {
2331 symtab_node *node = lsei_node (lsei);
2332
2333 if (m_symtab_node_map.get (node))
2334 count++;
2335 }
2336
2337 streamer_write_uhwi (ob, count);
2338
2339 /* Process all of the symbols. */
2340 for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2341 !lsei_end_p (lsei);
2342 lsei_next_in_partition (&lsei))
2343 {
2344 symtab_node *node = lsei_node (lsei);
2345
2346 sem_item **item = m_symtab_node_map.get (node);
2347
2348 if (item && *item)
2349 {
2350 int node_ref = lto_symtab_encoder_encode (encoder, node);
2351 streamer_write_uhwi_stream (ob->main_stream, node_ref);
2352
2353 streamer_write_uhwi (ob, (*item)->get_hash ());
2354 }
2355 }
2356
2357 streamer_write_char_stream (ob->main_stream, 0);
2358 produce_asm (ob, NULL);
2359 destroy_output_block (ob);
2360}
2361
2362/* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2363 contains LEN bytes. */
2364
2365void
2366sem_item_optimizer::read_section (lto_file_decl_data *file_data,
2367 const char *data, size_t len)
2368{
2369 const lto_function_header *header
2370 = (const lto_function_header *) data;
2371 const int cfg_offset = sizeof (lto_function_header);
2372 const int main_offset = cfg_offset + header->cfg_size;
2373 const int string_offset = main_offset + header->main_size;
2374 data_in *data_in;
2375 unsigned int i;
2376 unsigned int count;
2377
2378 lto_input_block ib_main ((const char *) data + main_offset, 0,
2379 header->main_size, file_data->mode_table);
2380
2381 data_in
2382 = lto_data_in_create (file_data, (const char *) data + string_offset,
2383 header->string_size, vNULL);
2384
2385 count = streamer_read_uhwi (&ib_main);
2386
2387 for (i = 0; i < count; i++)
2388 {
2389 unsigned int index;
2390 symtab_node *node;
2391 lto_symtab_encoder_t encoder;
2392
2393 index = streamer_read_uhwi (&ib_main);
2394 encoder = file_data->symtab_node_encoder;
2395 node = lto_symtab_encoder_deref (encoder, index);
2396
2397 hashval_t hash = streamer_read_uhwi (&ib_main);
2398
2399 gcc_assert (node->definition);
2400
2401 if (dump_file)
2402 fprintf (dump_file, "Symbol added: %s (tree: %p)\n",
2403 node->dump_asm_name (), (void *) node->decl);
2404
2405 if (is_a<cgraph_node *> (node))
2406 {
2407 cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
2408
2409 sem_function *fn = new sem_function (cnode, &m_bmstack);
2410 fn->set_hash (hash);
2411 m_items.safe_push (fn);
2412 }
2413 else
2414 {
2415 varpool_node *vnode = dyn_cast <varpool_node *> (node);
2416
2417 sem_variable *var = new sem_variable (vnode, &m_bmstack);
2418 var->set_hash (hash);
2419 m_items.safe_push (var);
2420 }
2421 }
2422
2423 lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
2424 len);
2425 lto_data_in_delete (data_in);
2426}
2427
2428/* Read IPA ICF summary for symbols. */
2429
2430void
2431sem_item_optimizer::read_summary (void)
2432{
2433 lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2434 lto_file_decl_data *file_data;
2435 unsigned int j = 0;
2436
2437 while ((file_data = file_data_vec[j++]))
2438 {
2439 size_t len;
2440 const char *data = lto_get_section_data (file_data,
2441 LTO_section_ipa_icf, NULL, &len);
2442
2443 if (data)
2444 read_section (file_data, data, len);
2445 }
2446}
2447
2448/* Register callgraph and varpool hooks. */
2449
2450void
2451sem_item_optimizer::register_hooks (void)
2452{
2453 if (!m_cgraph_node_hooks)
2454 m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
2455 (&sem_item_optimizer::cgraph_removal_hook, this);
2456
2457 if (!m_varpool_node_hooks)
2458 m_varpool_node_hooks = symtab->add_varpool_removal_hook
2459 (&sem_item_optimizer::varpool_removal_hook, this);
2460}
2461
2462/* Unregister callgraph and varpool hooks. */
2463
2464void
2465sem_item_optimizer::unregister_hooks (void)
2466{
2467 if (m_cgraph_node_hooks)
2468 symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
2469
2470 if (m_varpool_node_hooks)
2471 symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
2472}
2473
2474/* Adds a CLS to hashtable associated by hash value. */
2475
2476void
2477sem_item_optimizer::add_class (congruence_class *cls)
2478{
2479 gcc_assert (cls->members.length ());
2480
2481 congruence_class_group *group
2482 = get_group_by_hash (cls->members[0]->get_hash (),
2483 cls->members[0]->type);
2484 group->classes.safe_push (cls);
2485}
2486
2487/* Gets a congruence class group based on given HASH value and TYPE. */
2488
2489congruence_class_group *
2490sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
2491{
2492 congruence_class_group *item = XNEW (congruence_class_group);
2493 item->hash = hash;
2494 item->type = type;
2495
2496 congruence_class_group **slot = m_classes.find_slot (item, INSERT);
2497
2498 if (*slot)
2499 free (item);
2500 else
2501 {
2502 item->classes.create (1);
2503 *slot = item;
2504 }
2505
2506 return *slot;
2507}
2508
2509/* Callgraph removal hook called for a NODE with a custom DATA. */
2510
2511void
2512sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
2513{
2514 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2515 optimizer->remove_symtab_node (node);
2516}
2517
2518/* Varpool removal hook called for a NODE with a custom DATA. */
2519
2520void
2521sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
2522{
2523 sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2524 optimizer->remove_symtab_node (node);
2525}
2526
2527/* Remove symtab NODE triggered by symtab removal hooks. */
2528
2529void
2530sem_item_optimizer::remove_symtab_node (symtab_node *node)
2531{
2532 gcc_assert (!m_classes.elements ());
2533
2534 m_removed_items_set.add (node);
2535}
2536
2537void
2538sem_item_optimizer::remove_item (sem_item *item)
2539{
2540 if (m_symtab_node_map.get (item->node))
2541 m_symtab_node_map.remove (item->node);
2542 delete item;
2543}
2544
2545/* Removes all callgraph and varpool nodes that are marked by symtab
2546 as deleted. */
2547
2548void
2549sem_item_optimizer::filter_removed_items (void)
2550{
2551 auto_vec <sem_item *> filtered;
2552
2553 for (unsigned int i = 0; i < m_items.length(); i++)
2554 {
2555 sem_item *item = m_items[i];
2556
2557 if (m_removed_items_set.contains (item->node))
2558 {
2559 remove_item (item);
2560 continue;
2561 }
2562
2563 if (item->type == FUNC)
2564 {
2565 cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
2566
2567 if (in_lto_p && (cnode->alias || cnode->body_removed))
2568 remove_item (item);
2569 else
2570 filtered.safe_push (item);
2571 }
2572 else /* VAR. */
2573 {
2574 if (!flag_ipa_icf_variables)
2575 remove_item (item);
2576 else
2577 {
2578 /* Filter out non-readonly variables. */
2579 tree decl = item->decl;
2580 if (TREE_READONLY (decl))
2581 filtered.safe_push (item);
2582 else
2583 remove_item (item);
2584 }
2585 }
2586 }
2587
2588 /* Clean-up of released semantic items. */
2589
2590 m_items.release ();
2591 for (unsigned int i = 0; i < filtered.length(); i++)
2592 m_items.safe_push (filtered[i]);
2593}
2594
2595/* Optimizer entry point which returns true in case it processes
2596 a merge operation. True is returned if there's a merge operation
2597 processed. */
2598
2599bool
2600sem_item_optimizer::execute (void)
2601{
2602 filter_removed_items ();
2603 unregister_hooks ();
2604
2605 build_graph ();
2606 update_hash_by_addr_refs ();
2607 build_hash_based_classes ();
2608
2609 if (dump_file)
2610 fprintf (dump_file, "Dump after hash based groups\n");
2611 dump_cong_classes ();
2612
2613 for (unsigned int i = 0; i < m_items.length(); i++)
2614 m_items[i]->init_wpa ();
2615
2616 subdivide_classes_by_equality (true);
2617
2618 if (dump_file)
2619 fprintf (dump_file, "Dump after WPA based types groups\n");
2620
2621 dump_cong_classes ();
2622
2623 process_cong_reduction ();
2624 checking_verify_classes ();
2625
2626 if (dump_file)
2627 fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
2628
2629 dump_cong_classes ();
2630
2631 parse_nonsingleton_classes ();
2632 subdivide_classes_by_equality ();
2633
2634 if (dump_file)
2635 fprintf (dump_file, "Dump after full equality comparison of groups\n");
2636
2637 dump_cong_classes ();
2638
2639 unsigned int prev_class_count = m_classes_count;
2640
2641 process_cong_reduction ();
2642 dump_cong_classes ();
2643 checking_verify_classes ();
2644 bool merged_p = merge_classes (prev_class_count);
2645
2646 if (dump_file && (dump_flags & TDF_DETAILS))
2647 symtab->dump (dump_file);
2648
2649 return merged_p;
2650}
2651
2652/* Function responsible for visiting all potential functions and
2653 read-only variables that can be merged. */
2654
2655void
2656sem_item_optimizer::parse_funcs_and_vars (void)
2657{
2658 cgraph_node *cnode;
2659
2660 if (flag_ipa_icf_functions)
2661 FOR_EACH_DEFINED_FUNCTION (cnode)
2662 {
2663 sem_function *f = sem_function::parse (cnode, &m_bmstack);
2664 if (f)
2665 {
2666 m_items.safe_push (f);
2667 m_symtab_node_map.put (cnode, f);
2668
2669 if (dump_file)
2670 fprintf (dump_file, "Parsed function:%s\n", f->node->asm_name ());
2671
2672 if (dump_file && (dump_flags & TDF_DETAILS))
2673 f->dump_to_file (dump_file);
2674 }
2675 else if (dump_file)
2676 fprintf (dump_file, "Not parsed function:%s\n", cnode->asm_name ());
2677 }
2678
2679 varpool_node *vnode;
2680
2681 if (flag_ipa_icf_variables)
2682 FOR_EACH_DEFINED_VARIABLE (vnode)
2683 {
2684 sem_variable *v = sem_variable::parse (vnode, &m_bmstack);
2685
2686 if (v)
2687 {
2688 m_items.safe_push (v);
2689 m_symtab_node_map.put (vnode, v);
2690 }
2691 }
2692}
2693
2694/* Makes pairing between a congruence class CLS and semantic ITEM. */
2695
2696void
2697sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
2698{
2699 item->index_in_class = cls->members.length ();
2700 cls->members.safe_push (item);
2701 item->cls = cls;
2702}
2703
2704/* For each semantic item, append hash values of references. */
2705
2706void
2707sem_item_optimizer::update_hash_by_addr_refs ()
2708{
2709 /* First, append to hash sensitive references and class type if it need to
2710 be matched for ODR. */
2711 for (unsigned i = 0; i < m_items.length (); i++)
2712 {
2713 m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
2714 if (m_items[i]->type == FUNC)
2715 {
2716 if (TREE_CODE (TREE_TYPE (m_items[i]->decl)) == METHOD_TYPE
2717 && contains_polymorphic_type_p
2718 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl)))
2719 && (DECL_CXX_CONSTRUCTOR_P (m_items[i]->decl)
2720 || (static_cast<sem_function *> (m_items[i])->param_used_p (0)
2721 && static_cast<sem_function *> (m_items[i])
2722 ->compare_polymorphic_p ())))
2723 {
2724 tree class_type
2725 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl));
2726 inchash::hash hstate (m_items[i]->get_hash ());
2727
2728 if (TYPE_NAME (class_type)
2729 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type)))
2730 hstate.add_hwi
2731 (IDENTIFIER_HASH_VALUE
2732 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type))));
2733
2734 m_items[i]->set_hash (hstate.end ());
2735 }
2736 }
2737 }
2738
2739 /* Once all symbols have enhanced hash value, we can append
2740 hash values of symbols that are seen by IPA ICF and are
2741 references by a semantic item. Newly computed values
2742 are saved to global_hash member variable. */
2743 for (unsigned i = 0; i < m_items.length (); i++)
2744 m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
2745
2746 /* Global hash value replace current hash values. */
2747 for (unsigned i = 0; i < m_items.length (); i++)
2748 m_items[i]->set_hash (m_items[i]->global_hash);
2749}
2750
2751/* Congruence classes are built by hash value. */
2752
2753void
2754sem_item_optimizer::build_hash_based_classes (void)
2755{
2756 for (unsigned i = 0; i < m_items.length (); i++)
2757 {
2758 sem_item *item = m_items[i];
2759
2760 congruence_class_group *group
2761 = get_group_by_hash (item->get_hash (), item->type);
2762
2763 if (!group->classes.length ())
2764 {
2765 m_classes_count++;
2766 group->classes.safe_push (new congruence_class (class_id++));
2767 }
2768
2769 add_item_to_class (group->classes[0], item);
2770 }
2771}
2772
2773/* Build references according to call graph. */
2774
2775void
2776sem_item_optimizer::build_graph (void)
2777{
2778 for (unsigned i = 0; i < m_items.length (); i++)
2779 {
2780 sem_item *item = m_items[i];
2781 m_symtab_node_map.put (item->node, item);
2782
2783 /* Initialize hash values if we are not in LTO mode. */
2784 if (!in_lto_p)
2785 item->get_hash ();
2786 }
2787
2788 for (unsigned i = 0; i < m_items.length (); i++)
2789 {
2790 sem_item *item = m_items[i];
2791
2792 if (item->type == FUNC)
2793 {
2794 cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
2795
2796 cgraph_edge *e = cnode->callees;
2797 while (e)
2798 {
2799 sem_item **slot = m_symtab_node_map.get
2800 (e->callee->ultimate_alias_target ());
2801 if (slot)
2802 item->add_reference (*slot);
2803
2804 e = e->next_callee;
2805 }
2806 }
2807
2808 ipa_ref *ref = NULL;
2809 for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
2810 {
2811 sem_item **slot = m_symtab_node_map.get
2812 (ref->referred->ultimate_alias_target ());
2813 if (slot)
2814 item->add_reference (*slot);
2815 }
2816 }
2817}
2818
2819/* Semantic items in classes having more than one element and initialized.
2820 In case of WPA, we load function body. */
2821
2822void
2823sem_item_optimizer::parse_nonsingleton_classes (void)
2824{
2825 unsigned int init_called_count = 0;
2826
2827 for (unsigned i = 0; i < m_items.length (); i++)
2828 if (m_items[i]->cls->members.length () > 1)
2829 {
2830 m_items[i]->init ();
2831 init_called_count++;
2832 }
2833
2834 if (dump_file)
2835 fprintf (dump_file, "Init called for %u items (%.2f%%).\n",
2836 init_called_count,
2837 m_items.length () ? 100.0f * init_called_count / m_items.length ()
2838 : 0.0f);
2839}
2840
2841/* Equality function for semantic items is used to subdivide existing
2842 classes. If IN_WPA, fast equality function is invoked. */
2843
2844void
2845sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
2846{
2847 for (hash_table <congruence_class_hash>::iterator it = m_classes.begin ();
2848 it != m_classes.end (); ++it)
2849 {
2850 unsigned int class_count = (*it)->classes.length ();
2851
2852 for (unsigned i = 0; i < class_count; i++)
2853 {
2854 congruence_class *c = (*it)->classes[i];
2855
2856 if (c->members.length() > 1)
2857 {
2858 auto_vec <sem_item *> new_vector;
2859
2860 sem_item *first = c->members[0];
2861 new_vector.safe_push (first);
2862
2863 unsigned class_split_first = (*it)->classes.length ();
2864
2865 for (unsigned j = 1; j < c->members.length (); j++)
2866 {
2867 sem_item *item = c->members[j];
2868
2869 bool equals
2870 = in_wpa ? first->equals_wpa (item, m_symtab_node_map)
2871 : first->equals (item, m_symtab_node_map);
2872
2873 if (equals)
2874 new_vector.safe_push (item);
2875 else
2876 {
2877 bool integrated = false;
2878
2879 for (unsigned k = class_split_first;
2880 k < (*it)->classes.length (); k++)
2881 {
2882 sem_item *x = (*it)->classes[k]->members[0];
2883 bool equals
2884 = in_wpa ? x->equals_wpa (item, m_symtab_node_map)
2885 : x->equals (item, m_symtab_node_map);
2886
2887 if (equals)
2888 {
2889 integrated = true;
2890 add_item_to_class ((*it)->classes[k], item);
2891
2892 break;
2893 }
2894 }
2895
2896 if (!integrated)
2897 {
2898 congruence_class *c
2899 = new congruence_class (class_id++);
2900 m_classes_count++;
2901 add_item_to_class (c, item);
2902
2903 (*it)->classes.safe_push (c);
2904 }
2905 }
2906 }
2907
2908 // We replace newly created new_vector for the class we've just
2909 // splitted.
2910 c->members.release ();
2911 c->members.create (new_vector.length ());
2912
2913 for (unsigned int j = 0; j < new_vector.length (); j++)
2914 add_item_to_class (c, new_vector[j]);
2915 }
2916 }
2917 }
2918
2919 checking_verify_classes ();
2920}
2921
2922/* Subdivide classes by address references that members of the class
2923 reference. Example can be a pair of functions that have an address
2924 taken from a function. If these addresses are different the class
2925 is split. */
2926
2927unsigned
2928sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2929{
2930 typedef hash_map <symbol_compare_hash, vec <sem_item *> > subdivide_hash_map;
2931
2932 unsigned newly_created_classes = 0;
2933
2934 for (hash_table <congruence_class_hash>::iterator it = m_classes.begin ();
2935 it != m_classes.end (); ++it)
2936 {
2937 unsigned int class_count = (*it)->classes.length ();
2938 auto_vec<congruence_class *> new_classes;
2939
2940 for (unsigned i = 0; i < class_count; i++)
2941 {
2942 congruence_class *c = (*it)->classes[i];
2943
2944 if (c->members.length() > 1)
2945 {
2946 subdivide_hash_map split_map;
2947
2948 for (unsigned j = 0; j < c->members.length (); j++)
2949 {
2950 sem_item *source_node = c->members[j];
2951
2952 symbol_compare_collection *collection
2953 = new symbol_compare_collection (source_node->node);
2954
2955 bool existed;
2956 vec <sem_item *> *slot
2957 = &split_map.get_or_insert (collection, &existed);
2958 gcc_checking_assert (slot);
2959
2960 slot->safe_push (source_node);
2961
2962 if (existed)
2963 delete collection;
2964 }
2965
2966 /* If the map contains more than one key, we have to split
2967 the map appropriately. */
2968 if (split_map.elements () != 1)
2969 {
2970 bool first_class = true;
2971
2972 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2973 it2 != split_map.end (); ++it2)
2974 {
2975 congruence_class *new_cls;
2976 new_cls = new congruence_class (class_id++);
2977
2978 for (unsigned k = 0; k < (*it2).second.length (); k++)
2979 add_item_to_class (new_cls, (*it2).second[k]);
2980
2981 worklist_push (new_cls);
2982 newly_created_classes++;
2983
2984 if (first_class)
2985 {
2986 (*it)->classes[i] = new_cls;
2987 first_class = false;
2988 }
2989 else
2990 {
2991 new_classes.safe_push (new_cls);
2992 m_classes_count++;
2993 }
2994 }
2995 }
2996
2997 /* Release memory. */
2998 for (subdivide_hash_map::iterator it2 = split_map.begin ();
2999 it2 != split_map.end (); ++it2)
3000 {
3001 delete (*it2).first;
3002 (*it2).second.release ();
3003 }
3004 }
3005 }
3006
3007 for (unsigned i = 0; i < new_classes.length (); i++)
3008 (*it)->classes.safe_push (new_classes[i]);
3009 }
3010
3011 return newly_created_classes;
3012}
3013
3014/* Verify congruence classes, if checking is enabled. */
3015
3016void
3017sem_item_optimizer::checking_verify_classes (void)
3018{
3019 if (flag_checking)
3020 verify_classes ();
3021}
3022
3023/* Verify congruence classes. */
3024
3025void
3026sem_item_optimizer::verify_classes (void)
3027{
3028 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3029 it != m_classes.end (); ++it)
3030 {
3031 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3032 {
3033 congruence_class *cls = (*it)->classes[i];
3034
3035 gcc_assert (cls);
3036 gcc_assert (cls->members.length () > 0);
3037
3038 for (unsigned int j = 0; j < cls->members.length (); j++)
3039 {
3040 sem_item *item = cls->members[j];
3041
3042 gcc_assert (item);
3043 gcc_assert (item->cls == cls);
3044
3045 for (unsigned k = 0; k < item->usages.length (); k++)
3046 {
3047 sem_usage_pair *usage = item->usages[k];
3048 gcc_assert (usage->item->index_in_class
3049 < usage->item->cls->members.length ());
3050 }
3051 }
3052 }
3053 }
3054}
3055
3056/* Disposes split map traverse function. CLS_PTR is pointer to congruence
3057 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3058 but unused argument. */
3059
3060bool
3061sem_item_optimizer::release_split_map (congruence_class * const &,
3062 bitmap const &b, traverse_split_pair *)
3063{
3064 bitmap bmp = b;
3065
3066 BITMAP_FREE (bmp);
3067
3068 return true;
3069}
3070
3071/* Process split operation for a class given as pointer CLS_PTR,
3072 where bitmap B splits congruence class members. DATA is used
3073 as argument of split pair. */
3074
3075bool
3076sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
3077 bitmap const &b,
3078 traverse_split_pair *pair)
3079{
3080 sem_item_optimizer *optimizer = pair->optimizer;
3081 const congruence_class *splitter_cls = pair->cls;
3082
3083 /* If counted bits are greater than zero and less than the number of members
3084 a group will be splitted. */
3085 unsigned popcount = bitmap_count_bits (b);
3086
3087 if (popcount > 0 && popcount < cls->members.length ())
3088 {
3089 auto_vec <congruence_class *, 2> newclasses;
3090 newclasses.quick_push (new congruence_class (class_id++));
3091 newclasses.quick_push (new congruence_class (class_id++));
3092
3093 for (unsigned int i = 0; i < cls->members.length (); i++)
3094 {
3095 int target = bitmap_bit_p (b, i);
3096 congruence_class *tc = newclasses[target];
3097
3098 add_item_to_class (tc, cls->members[i]);
3099 }
3100
3101 if (flag_checking)
3102 {
3103 for (unsigned int i = 0; i < 2; i++)
3104 gcc_assert (newclasses[i]->members.length ());
3105 }
3106
3107 if (splitter_cls == cls)
3108 optimizer->splitter_class_removed = true;
3109
3110 /* Remove old class from worklist if presented. */
3111 bool in_worklist = cls->in_worklist;
3112
3113 if (in_worklist)
3114 cls->in_worklist = false;
3115
3116 congruence_class_group g;
3117 g.hash = cls->members[0]->get_hash ();
3118 g.type = cls->members[0]->type;
3119
3120 congruence_class_group *slot = optimizer->m_classes.find (&g);
3121
3122 for (unsigned int i = 0; i < slot->classes.length (); i++)
3123 if (slot->classes[i] == cls)
3124 {
3125 slot->classes.ordered_remove (i);
3126 break;
3127 }
3128
3129 /* New class will be inserted and integrated to work list. */
3130 for (unsigned int i = 0; i < 2; i++)
3131 optimizer->add_class (newclasses[i]);
3132
3133 /* Two classes replace one, so that increment just by one. */
3134 optimizer->m_classes_count++;
3135
3136 /* If OLD class was presented in the worklist, we remove the class
3137 and replace it will both newly created classes. */
3138 if (in_worklist)
3139 for (unsigned int i = 0; i < 2; i++)
3140 optimizer->worklist_push (newclasses[i]);
3141 else /* Just smaller class is inserted. */
3142 {
3143 unsigned int smaller_index
3144 = (newclasses[0]->members.length ()
3145 < newclasses[1]->members.length ()
3146 ? 0 : 1);
3147 optimizer->worklist_push (newclasses[smaller_index]);
3148 }
3149
3150 if (dump_file && (dump_flags & TDF_DETAILS))
3151 {
3152 fprintf (dump_file, " congruence class splitted:\n");
3153 cls->dump (dump_file, 4);
3154
3155 fprintf (dump_file, " newly created groups:\n");
3156 for (unsigned int i = 0; i < 2; i++)
3157 newclasses[i]->dump (dump_file, 4);
3158 }
3159
3160 /* Release class if not presented in work list. */
3161 if (!in_worklist)
3162 delete cls;
3163 }
3164
3165
3166 return true;
3167}
3168
3169/* Tests if a class CLS used as INDEXth splits any congruence classes.
3170 Bitmap stack BMSTACK is used for bitmap allocation. */
3171
3172void
3173sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
3174 unsigned int index)
3175{
3176 hash_map <congruence_class *, bitmap> split_map;
3177
3178 for (unsigned int i = 0; i < cls->members.length (); i++)
3179 {
3180 sem_item *item = cls->members[i];
3181
3182 /* Iterate all usages that have INDEX as usage of the item. */
3183 for (unsigned int j = 0; j < item->usages.length (); j++)
3184 {
3185 sem_usage_pair *usage = item->usages[j];
3186
3187 if (usage->index != index)
3188 continue;
3189
3190 bitmap *slot = split_map.get (usage->item->cls);
3191 bitmap b;
3192
3193 if(!slot)
3194 {
3195 b = BITMAP_ALLOC (&m_bmstack);
3196 split_map.put (usage->item->cls, b);
3197 }
3198 else
3199 b = *slot;
3200
3201 gcc_checking_assert (usage->item->cls);
3202 gcc_checking_assert (usage->item->index_in_class
3203 < usage->item->cls->members.length ());
3204
3205 bitmap_set_bit (b, usage->item->index_in_class);
3206 }
3207 }
3208
3209 traverse_split_pair pair;
3210 pair.optimizer = this;
3211 pair.cls = cls;
3212
3213 splitter_class_removed = false;
3214 split_map.traverse <traverse_split_pair *,
3215 sem_item_optimizer::traverse_congruence_split> (&pair);
3216
3217 /* Bitmap clean-up. */
3218 split_map.traverse <traverse_split_pair *,
3219 sem_item_optimizer::release_split_map> (NULL);
3220}
3221
3222/* Every usage of a congruence class CLS is a candidate that can split the
3223 collection of classes. Bitmap stack BMSTACK is used for bitmap
3224 allocation. */
3225
3226void
3227sem_item_optimizer::do_congruence_step (congruence_class *cls)
3228{
3229 bitmap_iterator bi;
3230 unsigned int i;
3231
3232 bitmap usage = BITMAP_ALLOC (&m_bmstack);
3233
3234 for (unsigned int i = 0; i < cls->members.length (); i++)
3235 bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
3236
3237 EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
3238 {
3239 if (dump_file && (dump_flags & TDF_DETAILS))
3240 fprintf (dump_file, " processing congruence step for class: %u, "
3241 "index: %u\n", cls->id, i);
3242
3243 do_congruence_step_for_index (cls, i);
3244
3245 if (splitter_class_removed)
3246 break;
3247 }
3248
3249 BITMAP_FREE (usage);
3250}
3251
3252/* Adds a newly created congruence class CLS to worklist. */
3253
3254void
3255sem_item_optimizer::worklist_push (congruence_class *cls)
3256{
3257 /* Return if the class CLS is already presented in work list. */
3258 if (cls->in_worklist)
3259 return;
3260
3261 cls->in_worklist = true;
3262 worklist.push_back (cls);
3263}
3264
3265/* Pops a class from worklist. */
3266
3267congruence_class *
3268sem_item_optimizer::worklist_pop (void)
3269{
3270 congruence_class *cls;
3271
3272 while (!worklist.empty ())
3273 {
3274 cls = worklist.front ();
3275 worklist.pop_front ();
3276 if (cls->in_worklist)
3277 {
3278 cls->in_worklist = false;
3279
3280 return cls;
3281 }
3282 else
3283 {
3284 /* Work list item was already intended to be removed.
3285 The only reason for doing it is to split a class.
3286 Thus, the class CLS is deleted. */
3287 delete cls;
3288 }
3289 }
3290
3291 return NULL;
3292}
3293
3294/* Iterative congruence reduction function. */
3295
3296void
3297sem_item_optimizer::process_cong_reduction (void)
3298{
3299 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3300 it != m_classes.end (); ++it)
3301 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3302 if ((*it)->classes[i]->is_class_used ())
3303 worklist_push ((*it)->classes[i]);
3304
3305 if (dump_file)
3306 fprintf (dump_file, "Worklist has been filled with: %lu\n",
3307 (unsigned long) worklist.size ());
3308
3309 if (dump_file && (dump_flags & TDF_DETAILS))
3310 fprintf (dump_file, "Congruence class reduction\n");
3311
3312 congruence_class *cls;
3313
3314 /* Process complete congruence reduction. */
3315 while ((cls = worklist_pop ()) != NULL)
3316 do_congruence_step (cls);
3317
3318 /* Subdivide newly created classes according to references. */
3319 unsigned new_classes = subdivide_classes_by_sensitive_refs ();
3320
3321 if (dump_file)
3322 fprintf (dump_file, "Address reference subdivision created: %u "
3323 "new classes.\n", new_classes);
3324}
3325
3326/* Debug function prints all informations about congruence classes. */
3327
3328void
3329sem_item_optimizer::dump_cong_classes (void)
3330{
3331 if (!dump_file)
3332 return;
3333
3334 fprintf (dump_file,
3335 "Congruence classes: %u (unique hash values: %lu), with total: "
3336 "%u items\n", m_classes_count,
3337 (unsigned long) m_classes.elements (), m_items.length ());
3338
3339 /* Histogram calculation. */
3340 unsigned int max_index = 0;
3341 unsigned int* histogram = XCNEWVEC (unsigned int, m_items.length () + 1);
3342
3343 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3344 it != m_classes.end (); ++it)
3345 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3346 {
3347 unsigned int c = (*it)->classes[i]->members.length ();
3348 histogram[c]++;
3349
3350 if (c > max_index)
3351 max_index = c;
3352 }
3353
3354 fprintf (dump_file,
3355 "Class size histogram [num of members]: number of classe number "
3356 "of classess\n");
3357
3358 for (unsigned int i = 0; i <= max_index; i++)
3359 if (histogram[i])
3360 fprintf (dump_file, "[%u]: %u classes\n", i, histogram[i]);
3361
3362 fprintf (dump_file, "\n\n");
3363
3364 if (dump_flags & TDF_DETAILS)
3365 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3366 it != m_classes.end (); ++it)
3367 {
3368 fprintf (dump_file, " group: with %u classes:\n",
3369 (*it)->classes.length ());
3370
3371 for (unsigned i = 0; i < (*it)->classes.length (); i++)
3372 {
3373 (*it)->classes[i]->dump (dump_file, 4);
3374
3375 if (i < (*it)->classes.length () - 1)
3376 fprintf (dump_file, " ");
3377 }
3378 }
3379
3380 free (histogram);
3381}
3382
3383/* Sort pair of sem_items A and B by DECL_UID. */
3384
3385static int
3386sort_sem_items_by_decl_uid (const void *a, const void *b)
3387{
3388 const sem_item *i1 = *(const sem_item * const *)a;
3389 const sem_item *i2 = *(const sem_item * const *)b;
3390
3391 int uid1 = DECL_UID (i1->decl);
3392 int uid2 = DECL_UID (i2->decl);
3393
3394 if (uid1 < uid2)
3395 return -1;
3396 else if (uid1 > uid2)
3397 return 1;
3398 else
3399 return 0;
3400}
3401
3402/* Sort pair of congruence_classes A and B by DECL_UID of the first member. */
3403
3404static int
3405sort_congruence_classes_by_decl_uid (const void *a, const void *b)
3406{
3407 const congruence_class *c1 = *(const congruence_class * const *)a;
3408 const congruence_class *c2 = *(const congruence_class * const *)b;
3409
3410 int uid1 = DECL_UID (c1->members[0]->decl);
3411 int uid2 = DECL_UID (c2->members[0]->decl);
3412
3413 if (uid1 < uid2)
3414 return -1;
3415 else if (uid1 > uid2)
3416 return 1;
3417 else
3418 return 0;
3419}
3420
3421/* Sort pair of congruence_class_groups A and B by
3422 DECL_UID of the first member of a first group. */
3423
3424static int
3425sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
3426{
3427 const congruence_class_group *g1
3428 = *(const congruence_class_group * const *)a;
3429 const congruence_class_group *g2
3430 = *(const congruence_class_group * const *)b;
3431
3432 int uid1 = DECL_UID (g1->classes[0]->members[0]->decl);
3433 int uid2 = DECL_UID (g2->classes[0]->members[0]->decl);
3434
3435 if (uid1 < uid2)
3436 return -1;
3437 else if (uid1 > uid2)
3438 return 1;
3439 else
3440 return 0;
3441}
3442
3443/* After reduction is done, we can declare all items in a group
3444 to be equal. PREV_CLASS_COUNT is start number of classes
3445 before reduction. True is returned if there's a merge operation
3446 processed. */
3447
3448bool
3449sem_item_optimizer::merge_classes (unsigned int prev_class_count)
3450{
3451 unsigned int item_count = m_items.length ();
3452 unsigned int class_count = m_classes_count;
3453 unsigned int equal_items = item_count - class_count;
3454
3455 unsigned int non_singular_classes_count = 0;
3456 unsigned int non_singular_classes_sum = 0;
3457
3458 bool merged_p = false;
3459
3460 /* PR lto/78211
3461 Sort functions in congruence classes by DECL_UID and do the same
3462 for the classes to not to break -fcompare-debug. */
3463
3464 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3465 it != m_classes.end (); ++it)
3466 {
3467 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3468 {
3469 congruence_class *c = (*it)->classes[i];
3470 c->members.qsort (sort_sem_items_by_decl_uid);
3471 }
3472
3473 (*it)->classes.qsort (sort_congruence_classes_by_decl_uid);
3474 }
3475
3476 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3477 it != m_classes.end (); ++it)
3478 for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3479 {
3480 congruence_class *c = (*it)->classes[i];
3481 if (c->members.length () > 1)
3482 {
3483 non_singular_classes_count++;
3484 non_singular_classes_sum += c->members.length ();
3485 }
3486 }
3487
3488 auto_vec <congruence_class_group *> classes (m_classes.elements ());
3489 for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3490 it != m_classes.end (); ++it)
3491 classes.quick_push (*it);
3492
3493 classes.qsort (sort_congruence_class_groups_by_decl_uid);
3494
3495 if (dump_file)
3496 {
3497 fprintf (dump_file, "\nItem count: %u\n", item_count);
3498 fprintf (dump_file, "Congruent classes before: %u, after: %u\n",
3499 prev_class_count, class_count);
3500 fprintf (dump_file, "Average class size before: %.2f, after: %.2f\n",
3501 prev_class_count ? 1.0f * item_count / prev_class_count : 0.0f,
3502 class_count ? 1.0f * item_count / class_count : 0.0f);
3503 fprintf (dump_file, "Average non-singular class size: %.2f, count: %u\n",
3504 non_singular_classes_count ? 1.0f * non_singular_classes_sum /
3505 non_singular_classes_count : 0.0f,
3506 non_singular_classes_count);
3507 fprintf (dump_file, "Equal symbols: %u\n", equal_items);
3508 fprintf (dump_file, "Fraction of visited symbols: %.2f%%\n\n",
3509 item_count ? 100.0f * equal_items / item_count : 0.0f);
3510 }
3511
3512 unsigned int l;
3513 congruence_class_group *it;
3514 FOR_EACH_VEC_ELT (classes, l, it)
3515 for (unsigned int i = 0; i < it->classes.length (); i++)
3516 {
3517 congruence_class *c = it->classes[i];
3518
3519 if (c->members.length () == 1)
3520 continue;
3521
3522 sem_item *source = c->members[0];
3523
3524 if (DECL_NAME (source->decl)
3525 && MAIN_NAME_P (DECL_NAME (source->decl)))
3526 /* If merge via wrappers, picking main as the target can be
3527 problematic. */
3528 source = c->members[1];
3529
3530 for (unsigned int j = 0; j < c->members.length (); j++)
3531 {
3532 sem_item *alias = c->members[j];
3533
3534 if (alias == source)
3535 continue;
3536
3537 if (dump_file)
3538 {
3539 fprintf (dump_file, "Semantic equality hit:%s->%s\n",
3540 xstrdup_for_dump (source->node->name ()),
3541 xstrdup_for_dump (alias->node->name ()));
3542 fprintf (dump_file, "Assembler symbol names:%s->%s\n",
3543 xstrdup_for_dump (source->node->asm_name ()),
3544 xstrdup_for_dump (alias->node->asm_name ()));
3545 }
3546
3547 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl)))
3548 {
3549 if (dump_file)
3550 fprintf (dump_file,
3551 "Merge operation is skipped due to no_icf "
3552 "attribute.\n\n");
3553
3554 continue;
3555 }
3556
3557 if (dump_file && (dump_flags & TDF_DETAILS))
3558 {
3559 source->dump_to_file (dump_file);
3560 alias->dump_to_file (dump_file);
3561 }
3562
3563 if (dbg_cnt (merged_ipa_icf))
3564 merged_p |= source->merge (alias);
3565 }
3566 }
3567
3568 return merged_p;
3569}
3570
3571/* Dump function prints all class members to a FILE with an INDENT. */
3572
3573void
3574congruence_class::dump (FILE *file, unsigned int indent) const
3575{
3576 FPRINTF_SPACES (file, indent, "class with id: %u, hash: %u, items: %u\n",
3577 id, members[0]->get_hash (), members.length ());
3578
3579 FPUTS_SPACES (file, indent + 2, "");
3580 for (unsigned i = 0; i < members.length (); i++)
3581 fprintf (file, "%s ", members[i]->node->dump_asm_name ());
3582
3583 fprintf (file, "\n");
3584}
3585
3586/* Returns true if there's a member that is used from another group. */
3587
3588bool
3589congruence_class::is_class_used (void)
3590{
3591 for (unsigned int i = 0; i < members.length (); i++)
3592 if (members[i]->usages.length ())
3593 return true;
3594
3595 return false;
3596}
3597
3598/* Generate pass summary for IPA ICF pass. */
3599
3600static void
3601ipa_icf_generate_summary (void)
3602{
3603 if (!optimizer)
3604 optimizer = new sem_item_optimizer ();
3605
3606 optimizer->register_hooks ();
3607 optimizer->parse_funcs_and_vars ();
3608}
3609
3610/* Write pass summary for IPA ICF pass. */
3611
3612static void
3613ipa_icf_write_summary (void)
3614{
3615 gcc_assert (optimizer);
3616
3617 optimizer->write_summary ();
3618}
3619
3620/* Read pass summary for IPA ICF pass. */
3621
3622static void
3623ipa_icf_read_summary (void)
3624{
3625 if (!optimizer)
3626 optimizer = new sem_item_optimizer ();
3627
3628 optimizer->read_summary ();
3629 optimizer->register_hooks ();
3630}
3631
3632/* Semantic equality exection function. */
3633
3634static unsigned int
3635ipa_icf_driver (void)
3636{
3637 gcc_assert (optimizer);
3638
3639 bool merged_p = optimizer->execute ();
3640
3641 delete optimizer;
3642 optimizer = NULL;
3643
3644 return merged_p ? TODO_remove_functions : 0;
3645}
3646
3647const pass_data pass_data_ipa_icf =
3648{
3649 IPA_PASS, /* type */
3650 "icf", /* name */
3651 OPTGROUP_IPA, /* optinfo_flags */
3652 TV_IPA_ICF, /* tv_id */
3653 0, /* properties_required */
3654 0, /* properties_provided */
3655 0, /* properties_destroyed */
3656 0, /* todo_flags_start */
3657 0, /* todo_flags_finish */
3658};
3659
3660class pass_ipa_icf : public ipa_opt_pass_d
3661{
3662public:
3663 pass_ipa_icf (gcc::context *ctxt)
3664 : ipa_opt_pass_d (pass_data_ipa_icf, ctxt,
3665 ipa_icf_generate_summary, /* generate_summary */
3666 ipa_icf_write_summary, /* write_summary */
3667 ipa_icf_read_summary, /* read_summary */
3668 NULL, /*
3669 write_optimization_summary */
3670 NULL, /*
3671 read_optimization_summary */
3672 NULL, /* stmt_fixup */
3673 0, /* function_transform_todo_flags_start */
3674 NULL, /* function_transform */
3675 NULL) /* variable_transform */
3676 {}
3677
3678 /* opt_pass methods: */
3679 virtual bool gate (function *)
3680 {
3681 return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
3682 }
3683
3684 virtual unsigned int execute (function *)
3685 {
3686 return ipa_icf_driver();
3687 }
3688}; // class pass_ipa_icf
3689
3690} // ipa_icf namespace
3691
3692ipa_opt_pass_d *
3693make_pass_ipa_icf (gcc::context *ctxt)
3694{
3695 return new ipa_icf::pass_ipa_icf (ctxt);
3696}
3697