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