comparison gcc/ipa-icf.c @ 16:04ced10e8804

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