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