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