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