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