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