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