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 1271810 : symbol_compare_collection::symbol_compare_collection (symtab_node *node)
107 : {
108 1271810 : m_references.create (0);
109 1271810 : m_interposables.create (0);
110 :
111 1271810 : ipa_ref *ref;
112 :
113 2277789 : if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
114 1271810 : return;
115 :
116 1628969 : for (unsigned i = 0; node->iterate_reference (i, ref); i++)
117 : {
118 357489 : if (ref->address_matters_p ())
119 314099 : m_references.safe_push (ref->referred);
120 :
121 357489 : if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE)
122 : {
123 290925 : if (ref->address_matters_p ())
124 288300 : m_references.safe_push (ref->referred);
125 : else
126 2625 : m_interposables.safe_push (ref->referred);
127 : }
128 : }
129 :
130 1271480 : if (is_a <cgraph_node *> (node))
131 : {
132 265831 : cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
133 :
134 557110 : for (cgraph_edge *e = cnode->callees; e; e = e->next_callee)
135 291279 : if (e->callee->get_availability () <= AVAIL_INTERPOSABLE)
136 88166 : 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 30989922 : sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index)
143 30989922 : : item (_item), index (_index)
144 : {
145 30989922 : }
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 3310799 : sem_item::sem_item (sem_item_type _type, symtab_node *_node,
154 3310799 : bitmap_obstack *stack)
155 6621598 : : type (_type), node (_node), referenced_by_count (0), m_hash (-1),
156 3310799 : m_hash_set (false)
157 : {
158 3310799 : decl = node->decl;
159 3310799 : setup (stack);
160 3310799 : }
161 :
162 : /* Add reference to a semantic TARGET. */
163 :
164 : void
165 3938406 : sem_item::add_reference (ref_map *refs,
166 : sem_item *target)
167 : {
168 3938406 : unsigned index = reference_count++;
169 3938406 : bool existed;
170 :
171 3938406 : sem_usage_pair *pair = new sem_usage_pair (target, index);
172 3938406 : vec<sem_item *> &v = refs->get_or_insert (pair, &existed);
173 3938406 : if (existed)
174 1053069 : delete pair;
175 :
176 3938406 : v.safe_push (this);
177 3938406 : bitmap_set_bit (target->usage_index_bitmap, index);
178 3938406 : refs_set.add (target->node);
179 3938406 : ++target->referenced_by_count;
180 3938406 : }
181 :
182 : /* Initialize internal data structures. Bitmap STACK is used for
183 : bitmap memory allocation process. */
184 :
185 : void
186 3310799 : sem_item::setup (bitmap_obstack *stack)
187 : {
188 3310799 : gcc_checking_assert (node);
189 :
190 3310799 : reference_count = 0;
191 3310799 : tree_refs.create (0);
192 3310799 : usage_index_bitmap = BITMAP_ALLOC (stack);
193 3310799 : }
194 :
195 3156317 : sem_item::~sem_item ()
196 : {
197 3156317 : tree_refs.release ();
198 :
199 3156317 : BITMAP_FREE (usage_index_bitmap);
200 3156317 : }
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 431436 : 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 431436 : gcc_checking_assert (TARGET_SUPPORTS_ALIASES);
224 431436 : return true;
225 : #endif
226 : }
227 :
228 9237435 : void sem_item::set_hash (hashval_t hash)
229 : {
230 9237435 : m_hash = hash;
231 9237435 : m_hash_set = true;
232 9237435 : }
233 :
234 : hash_map<const_tree, hashval_t> sem_item::m_type_hash_cache;
235 :
236 1019358 : sem_function::sem_function (cgraph_node *node, bitmap_obstack *stack)
237 1019358 : : sem_item (FUNC, node, stack), memory_access_types (),
238 1019358 : m_alias_sets_hash (0), m_checker (NULL), m_compared_func (NULL)
239 : {
240 1019358 : bb_sizes.create (0);
241 1019358 : bb_sorted.create (0);
242 1019358 : }
243 :
244 1957426 : sem_function::~sem_function ()
245 : {
246 7396004 : for (unsigned i = 0; i < bb_sorted.length (); i++)
247 6417291 : delete (bb_sorted[i]);
248 :
249 978713 : bb_sizes.release ();
250 978713 : bb_sorted.release ();
251 1957426 : }
252 :
253 : /* Calculates hash value based on a BASIC_BLOCK. */
254 :
255 : hashval_t
256 6229378 : sem_function::get_bb_hash (const sem_bb *basic_block)
257 : {
258 6229378 : inchash::hash hstate;
259 :
260 6229378 : hstate.add_int (basic_block->nondbg_stmt_count);
261 6229378 : hstate.add_int (basic_block->edge_count);
262 :
263 6229378 : return hstate.end ();
264 : }
265 :
266 : /* References independent hash function. */
267 :
268 : hashval_t
269 10517142 : sem_function::get_hash (void)
270 : {
271 10517142 : if (!m_hash_set)
272 : {
273 942460 : inchash::hash hstate;
274 942460 : hstate.add_int (177454); /* Random number for function type. */
275 :
276 942460 : hstate.add_int (arg_count);
277 942460 : hstate.add_int (cfg_checksum);
278 942460 : hstate.add_int (gcode_hash);
279 :
280 14343676 : for (unsigned i = 0; i < bb_sorted.length (); i++)
281 6229378 : hstate.merge_hash (get_bb_hash (bb_sorted[i]));
282 :
283 7171838 : for (unsigned i = 0; i < bb_sizes.length (); i++)
284 6229378 : hstate.add_int (bb_sizes[i]);
285 :
286 : /* Add common features of declaration itself. */
287 942460 : if (DECL_FUNCTION_SPECIFIC_TARGET (decl))
288 124768 : hstate.add_hwi
289 124768 : (cl_target_option_hash
290 124768 : (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl))));
291 942460 : if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))
292 130205 : hstate.add_hwi
293 130205 : (cl_optimization_hash
294 130205 : (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))));
295 942460 : hstate.add_flag (DECL_CXX_CONSTRUCTOR_P (decl));
296 942460 : hstate.add_flag (DECL_CXX_DESTRUCTOR_P (decl));
297 942460 : hstate.add_flag (DECL_STATIC_CHAIN (decl));
298 :
299 942460 : set_hash (hstate.end ());
300 : }
301 :
302 10517142 : 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 365641 : sem_item::compare_referenced_symbol_properties (symtab_node *used_by,
318 : symtab_node *n1,
319 : symtab_node *n2,
320 : bool address)
321 : {
322 365641 : 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 971567 : if ((!used_by || address || !is_a <cgraph_node *> (used_by)
336 246442 : || !opt_for_fn (used_by->decl, optimize_size))
337 361520 : && !opt_for_fn (n1->decl, optimize_size)
338 357641 : && n1->get_availability () > AVAIL_INTERPOSABLE
339 505466 : && (!DECL_UNINLINABLE (n1->decl) || !DECL_UNINLINABLE (n2->decl)))
340 : {
341 97240 : if (DECL_DISREGARD_INLINE_LIMITS (n1->decl)
342 48620 : != DECL_DISREGARD_INLINE_LIMITS (n2->decl))
343 0 : return return_false_with_msg
344 : ("DECL_DISREGARD_INLINE_LIMITS are different");
345 :
346 48620 : if (DECL_DECLARED_INLINE_P (n1->decl)
347 48620 : != DECL_DECLARED_INLINE_P (n2->decl))
348 300 : return return_false_with_msg ("inline attributes are different");
349 : }
350 :
351 363305 : if (DECL_IS_OPERATOR_NEW_P (n1->decl)
352 363305 : != DECL_IS_OPERATOR_NEW_P (n2->decl))
353 0 : return return_false_with_msg ("operator new flags are different");
354 :
355 363305 : if (DECL_IS_REPLACEABLE_OPERATOR (n1->decl)
356 363305 : != 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 365341 : if (is_a <varpool_node *> (n1))
364 : {
365 3828 : 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 2405 : && (!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 1792 : 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 1792 : if (!attribute_list_equal (DECL_ATTRIBUTES (n1->decl),
383 1792 : DECL_ATTRIBUTES (n2->decl)))
384 0 : return return_false_with_msg ("different var decl attributes");
385 1792 : if (comp_type_attributes (TREE_TYPE (n1->decl),
386 1792 : 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 734784 : if (used_by && is_a <varpool_node *> (used_by)
393 369143 : && DECL_VIRTUAL_P (used_by->decl))
394 : {
395 4042 : if (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl))
396 0 : return return_false_with_msg ("virtual flag mismatch");
397 4042 : if (DECL_VIRTUAL_P (n1->decl) && is_a <cgraph_node *> (n1)
398 6428 : && (DECL_FINAL_P (n1->decl) != DECL_FINAL_P (n2->decl)))
399 44 : 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 5895951 : sem_item::hash_referenced_symbol_properties (symtab_node *ref,
408 : inchash::hash &hstate,
409 : bool address)
410 : {
411 5895951 : if (is_a <cgraph_node *> (ref))
412 : {
413 1612997 : if ((type != FUNC || address || !opt_for_fn (decl, optimize_size))
414 1844850 : && !opt_for_fn (ref->decl, optimize_size)
415 3726950 : && !DECL_UNINLINABLE (ref->decl))
416 : {
417 1448899 : hstate.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref->decl));
418 1448899 : hstate.add_flag (DECL_DECLARED_INLINE_P (ref->decl));
419 : }
420 1887657 : hstate.add_flag (DECL_IS_OPERATOR_NEW_P (ref->decl));
421 : }
422 4008294 : else if (is_a <varpool_node *> (ref))
423 : {
424 4008294 : hstate.add_flag (DECL_VIRTUAL_P (ref->decl));
425 4008294 : if (address)
426 2953273 : hstate.add_int (DECL_ALIGN (ref->decl));
427 : }
428 5895951 : }
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 514640 : 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 514640 : enum availability avail1, avail2;
441 :
442 514640 : if (n1 == n2)
443 : return true;
444 :
445 : /* Never match variable and function. */
446 752643 : if (is_a <varpool_node *> (n1) != is_a <varpool_node *> (n2))
447 : return false;
448 :
449 250881 : if (!compare_referenced_symbol_properties (node, n1, n2, address))
450 : return false;
451 250307 : if (address && n1->equal_address_to (n2) == 1)
452 : return true;
453 250307 : if (!address && n1->semantically_equivalent_p (n2))
454 : return true;
455 :
456 250306 : n1 = n1->ultimate_alias_target (&avail1);
457 250306 : n2 = n2->ultimate_alias_target (&avail2);
458 :
459 36767 : if (avail1 > AVAIL_INTERPOSABLE && ignored_nodes.get (n1)
460 287073 : && avail2 > AVAIL_INTERPOSABLE && ignored_nodes.get (n2))
461 : return true;
462 :
463 213644 : 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 151124 : bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
470 : {
471 151124 : if (e1->indirect_info && e2->indirect_info)
472 : {
473 4477 : int e1_flags = e1->indirect_info->ecf_flags;
474 4477 : int e2_flags = e2->indirect_info->ecf_flags;
475 :
476 4477 : if (e1_flags != e2_flags)
477 0 : return return_false_with_msg ("ICF flags are different");
478 : }
479 146647 : 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 1429315 : sem_function::param_used_p (unsigned int i)
489 : {
490 1429315 : if (ipa_node_params_sum == NULL)
491 : return true;
492 :
493 1429315 : ipa_node_params *parms_info = ipa_node_params_sum->get (get_node ());
494 :
495 1429315 : if (!parms_info || vec_safe_length (parms_info->descriptors) <= i)
496 : return true;
497 :
498 1108969 : 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 1268296 : sem_function::compatible_parm_types_p (tree parm1, tree parm2)
507 : {
508 : /* Be sure that parameters are TBAA compatible. */
509 1268296 : if (!func_checker::compatible_types_p (parm1, parm2))
510 333 : return return_false_with_msg ("parameter type is not compatible");
511 :
512 1267963 : if (POINTER_TYPE_P (parm1)
513 1267963 : && (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 1267963 : if (POINTER_TYPE_P (parm1)
518 117538 : && TREE_CODE (parm1) != TREE_CODE (parm2)
519 1267963 : && 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 1679890 : sem_function::equals_wpa (sem_item *item,
529 : hash_map <symtab_node *, sem_item *> &ignored_nodes)
530 : {
531 1679890 : gcc_assert (item->type == FUNC);
532 1679890 : cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
533 1679890 : cgraph_node *cnode2 = dyn_cast <cgraph_node *> (item->node);
534 :
535 1679890 : m_compared_func = static_cast<sem_function *> (item);
536 :
537 1679890 : if (cnode->must_remain_in_tu_name || cnode2->must_remain_in_tu_name
538 1679890 : || 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 1679887 : if (cnode->thunk != cnode2->thunk)
542 0 : return return_false_with_msg ("thunk mismatch");
543 1679887 : if (cnode->former_thunk_p () != cnode2->former_thunk_p ())
544 4 : return return_false_with_msg ("former_thunk_p mismatch");
545 :
546 1679883 : if ((cnode->thunk || cnode->former_thunk_p ())
547 1679883 : && 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 1679883 : if (DECL_FUNCTION_PERSONALITY (decl)
552 1679883 : != DECL_FUNCTION_PERSONALITY (item->decl))
553 0 : return return_false_with_msg ("function personalities are different");
554 :
555 1679883 : if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
556 1679883 : != 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 1679883 : 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 1679883 : if (DECL_CXX_CONSTRUCTOR_P (decl) != DECL_CXX_CONSTRUCTOR_P (item->decl))
564 318 : return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
565 :
566 1679565 : 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 1679461 : if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
574 114311 : 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 1565150 : if (DECL_CXX_CONSTRUCTOR_P (decl)
580 2465 : && opt_for_fn (decl, flag_devirtualize)
581 1567615 : && TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE)
582 : {
583 2432 : if (TREE_CODE (TREE_TYPE (item->decl)) != METHOD_TYPE)
584 0 : return return_false_with_msg ("DECL_CXX_CONSTRUCTOR type mismatch");
585 2432 : else if (!func_checker::compatible_polymorphic_types_p
586 2432 : (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
587 2432 : 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 1565150 : cl_target_option *tar1 = target_opts_for_fn (decl);
593 1565150 : cl_target_option *tar2 = target_opts_for_fn (item->decl);
594 :
595 1565150 : 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 1565150 : cl_optimization *opt1 = opts_for_fn (decl);
607 1565150 : cl_optimization *opt2 = opts_for_fn (item->decl);
608 :
609 1565150 : 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 1565150 : if (!func_checker::compatible_types_p
622 1565150 : (TREE_TYPE (TREE_TYPE (decl)),
623 1565150 : TREE_TYPE (TREE_TYPE (m_compared_func->decl))))
624 1032279 : return return_false_with_msg ("result types are different");
625 :
626 : /* Checking types of arguments. */
627 532871 : tree list1 = TYPE_ARG_TYPES (TREE_TYPE (decl)),
628 532871 : list2 = TYPE_ARG_TYPES (TREE_TYPE (m_compared_func->decl));
629 1685854 : for (unsigned i = 0; list1 && list2;
630 1152983 : list1 = TREE_CHAIN (list1), list2 = TREE_CHAIN (list2), i++)
631 : {
632 1361060 : tree parm1 = TREE_VALUE (list1);
633 1361060 : tree parm2 = TREE_VALUE (list2);
634 :
635 : /* This guard is here for function pointer with attributes (pr59927.c). */
636 1361060 : 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 1361060 : if (!types_compatible_p (parm1, parm2))
642 207744 : return return_false_with_msg ("parameter types are not compatible");
643 :
644 1153316 : if (!param_used_p (i))
645 48330 : continue;
646 :
647 : /* Perform additional checks for used parameters. */
648 1104986 : if (!compatible_parm_types_p (parm1, parm2))
649 : return false;
650 : }
651 :
652 324794 : if (list1 || list2)
653 5 : return return_false_with_msg ("mismatched number of parameters");
654 :
655 324789 : if (DECL_STATIC_CHAIN (decl) != DECL_STATIC_CHAIN (item->decl))
656 0 : return return_false_with_msg ("static chain mismatch");
657 :
658 356069 : 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 324789 : if (comp_type_attributes (TREE_TYPE (decl),
664 324789 : TREE_TYPE (item->decl)) != 1)
665 163 : return return_false_with_msg ("different type attributes");
666 324626 : if (!attribute_list_equal (DECL_ATTRIBUTES (decl),
667 324626 : DECL_ATTRIBUTES (item->decl)))
668 1337 : 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 323289 : if (opt_for_fn (decl, flag_devirtualize)
673 323253 : && (TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE
674 302904 : || TREE_CODE (TREE_TYPE (item->decl)) == METHOD_TYPE)
675 20352 : && param_used_p (0)
676 338252 : && compare_polymorphic_p ())
677 : {
678 11583 : if (TREE_CODE (TREE_TYPE (decl)) != TREE_CODE (TREE_TYPE (item->decl)))
679 82 : return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
680 11501 : if (!func_checker::compatible_polymorphic_types_p
681 11501 : (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
682 11501 : TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
683 0 : return return_false_with_msg ("THIS pointer ODR type mismatch");
684 : }
685 :
686 323207 : ipa_ref *ref = NULL, *ref2 = NULL;
687 355430 : for (unsigned i = 0; node->iterate_reference (i, ref); i++)
688 : {
689 32348 : item->node->iterate_reference (i, ref2);
690 :
691 32348 : if (ref->use != ref2->use)
692 0 : return return_false_with_msg ("reference use mismatch");
693 :
694 32348 : if (!compare_symbol_references (ignored_nodes, ref->referred,
695 : ref2->referred,
696 32348 : ref->address_matters_p ()))
697 : return false;
698 : }
699 :
700 323082 : cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
701 323082 : cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
702 :
703 469729 : while (e1 && e2)
704 : {
705 360554 : if (!compare_symbol_references (ignored_nodes, e1->callee,
706 360554 : e2->callee, false))
707 : return false;
708 146647 : if (!compare_edge_flags (e1, e2))
709 : return false;
710 :
711 146647 : e1 = e1->next_callee;
712 146647 : e2 = e2->next_callee;
713 : }
714 :
715 109175 : if (e1 || e2)
716 0 : return return_false_with_msg ("different number of calls");
717 :
718 109175 : e1 = dyn_cast <cgraph_node *> (node)->indirect_calls;
719 109175 : e2 = dyn_cast <cgraph_node *> (item->node)->indirect_calls;
720 :
721 113652 : while (e1 && e2)
722 : {
723 4477 : if (!compare_edge_flags (e1, e2))
724 : return false;
725 :
726 4477 : e1 = e1->next_callee;
727 4477 : e2 = e2->next_callee;
728 : }
729 :
730 109175 : 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 2455792 : sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
746 : sem_item *> &m_symtab_node_map)
747 : {
748 2455792 : ipa_ref* ref;
749 2455792 : inchash::hash hstate (get_hash ());
750 :
751 6853209 : for (unsigned i = 0; node->iterate_reference (i, ref); i++)
752 : {
753 4397417 : hstate.add_int (ref->use);
754 4397417 : hash_referenced_symbol_properties (ref->referred, hstate,
755 4397417 : ref->use == IPA_REF_ADDR);
756 4397417 : if (ref->address_matters_p () || !m_symtab_node_map.get (ref->referred))
757 4244222 : hstate.add_int (ref->referred->ultimate_alias_target ()->order);
758 : }
759 :
760 2455792 : if (is_a <cgraph_node *> (node))
761 : {
762 2469688 : for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
763 1498534 : e = e->next_caller)
764 : {
765 1498534 : sem_item **result = m_symtab_node_map.get (e->callee);
766 1498534 : hash_referenced_symbol_properties (e->callee, hstate, false);
767 1498534 : if (!result)
768 0 : hstate.add_int (e->callee->ultimate_alias_target ()->order);
769 : }
770 : }
771 :
772 2455792 : set_hash (hstate.end ());
773 2455792 : }
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 2455792 : sem_item::update_hash_by_local_refs (hash_map <symtab_node *,
781 : sem_item *> &m_symtab_node_map)
782 : {
783 2455792 : ipa_ref* ref;
784 2455792 : inchash::hash state (get_hash ());
785 :
786 6853209 : for (unsigned j = 0; node->iterate_reference (j, ref); j++)
787 : {
788 4397417 : sem_item **result = m_symtab_node_map.get (ref->referring);
789 4397417 : if (result)
790 4397417 : state.merge_hash ((*result)->get_hash ());
791 : }
792 :
793 2455792 : if (type == FUNC)
794 : {
795 4715497 : for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e;
796 3744343 : e = e->next_callee)
797 : {
798 3744343 : sem_item **result = m_symtab_node_map.get (e->caller);
799 3744343 : if (result)
800 3744343 : state.merge_hash ((*result)->get_hash ());
801 : }
802 : }
803 :
804 2455792 : global_hash = state.end ();
805 2455792 : }
806 :
807 : /* Returns true if the item equals to ITEM given as argument. */
808 :
809 : bool
810 123508 : sem_function::equals (sem_item *item,
811 : hash_map <symtab_node *, sem_item *> &)
812 : {
813 123508 : gcc_assert (item->type == FUNC);
814 123508 : bool eq = equals_private (item);
815 :
816 123508 : if (m_checker != NULL)
817 : {
818 123508 : delete m_checker;
819 123508 : m_checker = NULL;
820 : }
821 :
822 123508 : 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 123508 : return eq;
830 : }
831 :
832 : /* Processes function equality comparison. */
833 :
834 : bool
835 123508 : sem_function::equals_private (sem_item *item)
836 : {
837 123508 : if (item->type != FUNC)
838 : return false;
839 :
840 123508 : basic_block bb1, bb2;
841 123508 : edge e1, e2;
842 123508 : edge_iterator ei1, ei2;
843 123508 : bool result = true;
844 123508 : tree arg1, arg2;
845 :
846 123508 : m_compared_func = static_cast<sem_function *> (item);
847 :
848 123508 : gcc_assert (decl != item->decl);
849 :
850 247016 : if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
851 123508 : || edge_count != m_compared_func->edge_count
852 247016 : || cfg_checksum != m_compared_func->cfg_checksum)
853 0 : return return_false ();
854 :
855 247016 : m_checker = new func_checker (decl, m_compared_func->decl,
856 : false,
857 247016 : opt_for_fn (m_compared_func->decl,
858 : flag_strict_aliasing),
859 : &refs_set,
860 123508 : &m_compared_func->refs_set);
861 123508 : arg1 = DECL_ARGUMENTS (decl);
862 123508 : arg2 = DECL_ARGUMENTS (m_compared_func->decl);
863 123508 : for (unsigned i = 0;
864 318317 : arg1 && arg2; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2), i++)
865 : {
866 195048 : if (!types_compatible_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
867 239 : return return_false_with_msg ("argument types are not compatible");
868 194809 : if (!param_used_p (i))
869 31499 : continue;
870 : /* Perform additional checks for used parameters. */
871 163310 : if (!compatible_parm_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
872 : return false;
873 163310 : if (!m_checker->compare_decl (arg1, arg2))
874 0 : return return_false ();
875 : }
876 123269 : if (arg1 || arg2)
877 0 : return return_false_with_msg ("mismatched number of arguments");
878 :
879 123269 : if (DECL_STATIC_CHAIN (decl) != DECL_STATIC_CHAIN (m_compared_func->decl))
880 0 : return return_false_with_msg ("static chain mismatch");
881 :
882 246538 : if (!dyn_cast <cgraph_node *> (node)->has_gimple_body_p ())
883 : return true;
884 :
885 : /* Fill-up label dictionary. */
886 1416838 : for (unsigned i = 0; i < bb_sorted.length (); ++i)
887 : {
888 585150 : m_checker->parse_labels (bb_sorted[i]);
889 585150 : m_checker->parse_labels (m_compared_func->bb_sorted[i]);
890 : }
891 :
892 : /* Checking all basic blocks. */
893 524186 : for (unsigned i = 0; i < bb_sorted.length (); ++i)
894 439618 : if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
895 38701 : return return_false ();
896 :
897 84568 : auto_vec <int> bb_dict;
898 :
899 : /* Basic block edges check. */
900 964370 : for (unsigned i = 0; i < bb_sorted.length (); ++i)
901 : {
902 397625 : bb1 = bb_sorted[i]->bb;
903 397625 : bb2 = m_compared_func->bb_sorted[i]->bb;
904 :
905 397625 : ei2 = ei_start (bb2->preds);
906 :
907 900958 : for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
908 : {
909 503341 : ei_cond (ei2, &e2);
910 :
911 503341 : if (e1->flags != e2->flags)
912 0 : return return_false_with_msg ("flags comparison returns false");
913 :
914 503341 : 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 503333 : 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 503333 : if (!m_checker->compare_edge (e1, e2))
921 0 : return return_false_with_msg ("edge comparison returns false");
922 :
923 503333 : ei_next (&ei2);
924 : }
925 : }
926 :
927 : /* Basic block PHI nodes comparison. */
928 481966 : for (unsigned i = 0; i < bb_sorted.length (); i++)
929 397398 : 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 84568 : }
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 51818 : set_local (cgraph_node *node, void *data)
940 : {
941 51818 : node->local = data != NULL;
942 51818 : 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 25751 : clear_decl_rtl (symtab_node *node, void *)
960 : {
961 25751 : SET_DECL_RTL (node->decl, NULL);
962 25751 : 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 16404 : redirect_all_callers (cgraph_node *n, cgraph_node *to)
970 : {
971 16404 : int nredirected = 0;
972 16404 : ipa_ref *ref;
973 16404 : cgraph_edge *e = n->callers;
974 :
975 16900 : 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 496 : if (!e->caller->thunk)
981 : {
982 496 : struct cgraph_edge *nexte = e->next_caller;
983 496 : e->redirect_callee (to);
984 496 : e = nexte;
985 496 : nredirected++;
986 : }
987 : else
988 0 : e = e->next_callee;
989 : }
990 16414 : 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 16404 : return nredirected;
1012 : }
1013 :
1014 : /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1015 : be applied. */
1016 :
1017 : bool
1018 83692 : sem_function::merge (sem_item *alias_item)
1019 : {
1020 83692 : gcc_assert (alias_item->type == FUNC);
1021 :
1022 83692 : sem_function *alias_func = static_cast<sem_function *> (alias_item);
1023 :
1024 83692 : cgraph_node *original = get_node ();
1025 83692 : cgraph_node *local_original = NULL;
1026 83692 : cgraph_node *alias = alias_func->get_node ();
1027 :
1028 83692 : bool create_wrapper = false;
1029 83692 : bool create_alias = false;
1030 83692 : bool redirect_callers = false;
1031 83692 : bool remove = false;
1032 :
1033 83692 : bool original_discardable = false;
1034 83692 : bool original_discarded = false;
1035 :
1036 83692 : bool original_address_matters = original->address_matters_p ();
1037 83692 : bool alias_address_matters = alias->address_matters_p ();
1038 :
1039 83692 : AUTO_DUMP_SCOPE ("merge",
1040 : dump_user_location_t::from_function_decl (decl));
1041 :
1042 83692 : if (DECL_EXTERNAL (alias->decl))
1043 : {
1044 99 : if (dump_enabled_p ())
1045 0 : dump_printf (MSG_MISSED_OPTIMIZATION,
1046 : "Not unifying; alias is external.\n");
1047 99 : return false;
1048 : }
1049 :
1050 83593 : if (DECL_NO_INLINE_WARNING_P (original->decl)
1051 83593 : != DECL_NO_INLINE_WARNING_P (alias->decl))
1052 : {
1053 387 : if (dump_enabled_p ())
1054 0 : dump_printf (MSG_MISSED_OPTIMIZATION,
1055 : "Not unifying; DECL_NO_INLINE_WARNING mismatch.\n");
1056 387 : 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 83206 : if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
1062 83206 : || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
1063 83206 : && 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 83206 : if (!original->in_same_comdat_group_p (alias)
1073 83206 : || original->comdat_local_p ())
1074 : {
1075 12388 : 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 12388 : 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 70818 : 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 70818 : if (node->resolution != LDPR_UNKNOWN
1091 70818 : && !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 70818 : if ((original_address_matters && alias_address_matters)
1107 13438 : || (original_discardable
1108 0 : && (!DECL_COMDAT_GROUP (alias->decl)
1109 0 : || (DECL_COMDAT_GROUP (alias->decl)
1110 0 : != DECL_COMDAT_GROUP (original->decl))))
1111 13438 : || original_discarded
1112 13438 : || !sem_item::target_supports_symbol_aliases_p ()
1113 84256 : || 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 57380 : if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1121 57380 : 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 57373 : else if (DECL_COMDAT_GROUP (original->decl)
1133 0 : && DECL_COMDAT_GROUP (alias->decl)
1134 57373 : && (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 57373 : else if (DECL_STATIC_CHAIN (alias->decl)
1142 57373 : || 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 57369 : 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 56302 : else if (ipa_fn_summaries
1157 56302 : && ipa_size_summaries->get (alias) != NULL
1158 56292 : && 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 56291 : else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
1168 : {
1169 38045 : 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 57380 : redirect_callers
1179 57380 : = alias->get_availability () > AVAIL_INTERPOSABLE
1180 57380 : && original->get_availability () > AVAIL_INTERPOSABLE;
1181 : /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1182 : with proper properties. */
1183 57380 : if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1184 57380 : alias->address_taken))
1185 7 : redirect_callers = false;
1186 :
1187 57380 : 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 57358 : if (!original_discardable && !original->get_comdat_group ())
1203 : {
1204 57357 : local_original
1205 57357 : = 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 1 : else if (original->get_availability () > AVAIL_INTERPOSABLE)
1213 0 : local_original = original;
1214 :
1215 : /* If original is COMDAT local, we cannot really redirect calls outside
1216 : of its comdat group to it. */
1217 57358 : if (original->comdat_local_p ())
1218 57358 : redirect_callers = false;
1219 57358 : 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 57357 : 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 57357 : if (!create_wrapper
1236 39112 : && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1237 : NULL, true)
1238 96469 : && !alias->can_remove_if_no_direct_calls_p ())
1239 : {
1240 39112 : 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 39112 : return false;
1245 : }
1246 : }
1247 : else
1248 : create_alias = true;
1249 :
1250 18245 : if (redirect_callers)
1251 : {
1252 16394 : int nredirected = redirect_all_callers (alias, local_original);
1253 :
1254 16394 : 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 16394 : if (alias->can_remove_if_no_direct_calls_p ()
1267 171 : && !DECL_VIRTUAL_P (alias->decl)
1268 16565 : && !alias->has_aliases_p ())
1269 : {
1270 : create_wrapper = false;
1271 : remove = true;
1272 : }
1273 : gcc_assert (!create_alias);
1274 : }
1275 15289 : else if (create_alias)
1276 : {
1277 13438 : alias->icf_merged = true;
1278 :
1279 : /* Remove the function's body. */
1280 13438 : ipa_merge_profiles (original, alias);
1281 13438 : symtab->call_cgraph_removal_hooks (alias);
1282 13438 : alias->release_body (true);
1283 13438 : alias->reset ();
1284 : /* Notice global symbol possibly produced RTL. */
1285 13438 : ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
1286 : NULL, true);
1287 :
1288 : /* Create the alias. */
1289 13438 : cgraph_node::create_alias (alias_func->decl, decl);
1290 13438 : alias->resolve_alias (original);
1291 :
1292 13438 : original->call_for_symbol_thunks_and_aliases
1293 13438 : (set_local, (void *)(size_t) original->local_p (), true);
1294 :
1295 13438 : if (dump_enabled_p ())
1296 20 : dump_printf (MSG_OPTIMIZED_LOCATIONS,
1297 : "Unified; Function alias has been created.\n");
1298 : }
1299 31683 : if (create_wrapper)
1300 : {
1301 18074 : gcc_assert (!create_alias);
1302 18074 : alias->icf_merged = true;
1303 18074 : symtab->call_cgraph_removal_hooks (alias);
1304 18074 : local_original->icf_merged = true;
1305 :
1306 : /* FIXME update local_original counts. */
1307 18074 : ipa_merge_profiles (original, alias, true);
1308 18074 : alias->create_wrapper (local_original);
1309 18074 : symtab->call_cgraph_insertion_hooks (alias);
1310 :
1311 18074 : 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 31683 : gcc_assert (alias->icf_merged || remove || redirect_callers);
1319 31683 : 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 31683 : 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 31683 : if (remove)
1334 : {
1335 171 : ipa_merge_profiles (original, alias);
1336 171 : alias->release_body ();
1337 171 : alias->reset ();
1338 171 : alias->body_removed = true;
1339 171 : alias->icf_merged = true;
1340 171 : 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 1080151 : sem_function::init (ipa_icf_gimple::func_checker *checker)
1352 : {
1353 1080151 : m_checker = checker;
1354 1080151 : if (in_lto_p)
1355 65306 : get_node ()->get_untransformed_body ();
1356 :
1357 1080151 : tree fndecl = node->decl;
1358 1080151 : function *func = DECL_STRUCT_FUNCTION (fndecl);
1359 :
1360 1080151 : gcc_assert (func);
1361 1080151 : gcc_assert (SSANAMES (func));
1362 :
1363 1080151 : ssa_names_size = SSANAMES (func)->length ();
1364 :
1365 1080151 : decl = fndecl;
1366 1080151 : region_tree = func->eh->region_tree;
1367 :
1368 : /* iterating all function arguments. */
1369 1080151 : arg_count = count_formal_params (fndecl);
1370 :
1371 1080151 : edge_count = n_edges_for_fn (func);
1372 1080151 : cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1373 1080151 : if (!cnode->thunk)
1374 : {
1375 1080151 : cfg_checksum = coverage_compute_cfg_checksum (func);
1376 :
1377 1080151 : inchash::hash hstate;
1378 :
1379 1080151 : basic_block bb;
1380 7697745 : FOR_EACH_BB_FN (bb, func)
1381 : {
1382 6617594 : unsigned nondbg_stmt_count = 0;
1383 :
1384 6617594 : edge e;
1385 15433193 : for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
1386 8815599 : ei_next (&ei))
1387 8815599 : 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 6617594 : gphi_iterator si;
1394 7724713 : for (si = gsi_start_nonvirtual_phis (bb); !gsi_end_p (si);
1395 1107119 : gsi_next_nonvirtual_phi (&si))
1396 : {
1397 1107119 : hstate.add_int (GIMPLE_PHI);
1398 1107119 : gphi *phi = si.phi ();
1399 1107119 : m_checker->hash_operand (gimple_phi_result (phi), hstate, 0,
1400 : func_checker::OP_NORMAL);
1401 1107119 : hstate.add_int (gimple_phi_num_args (phi));
1402 3732490 : for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++)
1403 2625371 : m_checker->hash_operand (gimple_phi_arg_def (phi, i),
1404 : hstate, 0, func_checker::OP_NORMAL);
1405 : }
1406 :
1407 55127464 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1408 41892276 : gsi_next (&gsi))
1409 : {
1410 41892276 : gimple *stmt = gsi_stmt (gsi);
1411 :
1412 41892276 : if (gimple_code (stmt) != GIMPLE_DEBUG
1413 41892276 : && gimple_code (stmt) != GIMPLE_PREDICT)
1414 : {
1415 20839900 : hash_stmt (stmt, hstate);
1416 20839900 : nondbg_stmt_count++;
1417 : }
1418 : }
1419 :
1420 6617594 : hstate.commit_flag ();
1421 6617594 : gcode_hash = hstate.end ();
1422 6617594 : bb_sizes.safe_push (nondbg_stmt_count);
1423 :
1424 : /* Inserting basic block to hash table. */
1425 6617594 : sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
1426 6617594 : EDGE_COUNT (bb->preds)
1427 19846290 : + EDGE_COUNT (bb->succs));
1428 :
1429 6617594 : 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 1080151 : m_checker = NULL;
1439 1080151 : }
1440 :
1441 : /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1442 :
1443 : void
1444 20839900 : sem_function::hash_stmt (gimple *stmt, inchash::hash &hstate)
1445 : {
1446 20839900 : enum gimple_code code = gimple_code (stmt);
1447 :
1448 20839900 : hstate.add_int (code);
1449 :
1450 20839900 : switch (code)
1451 : {
1452 19906 : case GIMPLE_SWITCH:
1453 19906 : m_checker->hash_operand (gimple_switch_index (as_a <gswitch *> (stmt)),
1454 : hstate, 0, func_checker::OP_NORMAL);
1455 19906 : break;
1456 12859241 : case GIMPLE_ASSIGN:
1457 12859241 : hstate.add_int (gimple_assign_rhs_code (stmt));
1458 : /* fall through */
1459 20374315 : case GIMPLE_CALL:
1460 20374315 : case GIMPLE_ASM:
1461 20374315 : case GIMPLE_COND:
1462 20374315 : case GIMPLE_GOTO:
1463 20374315 : case GIMPLE_RETURN:
1464 20374315 : {
1465 20374315 : func_checker::operand_access_type_map map (5);
1466 20374315 : func_checker::classify_operands (stmt, &map);
1467 :
1468 : /* All these statements are equivalent if their operands are. */
1469 81404414 : for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1470 : {
1471 61030099 : func_checker::operand_access_type
1472 : access_type = func_checker::get_operand_access_type
1473 61030099 : (&map, gimple_op (stmt, i));
1474 61030099 : 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 61030099 : if (access_type == func_checker::OP_MEMORY
1480 7998003 : && lto_streaming_expected_p ()
1481 61349511 : && flag_strict_aliasing)
1482 : {
1483 318894 : ao_ref ref;
1484 :
1485 318894 : ao_ref_init (&ref, gimple_op (stmt, i));
1486 318894 : tree t = ao_ref_alias_ptr_type (&ref);
1487 318894 : if (!variably_modified_type_p (t, NULL_TREE))
1488 318866 : memory_access_types.safe_push (t);
1489 318894 : t = ao_ref_base_alias_ptr_type (&ref);
1490 318894 : if (!variably_modified_type_p (t, NULL_TREE))
1491 318493 : memory_access_types.safe_push (t);
1492 : }
1493 : }
1494 : /* Consider nocf_check attribute in hash as it affects code
1495 : generation. */
1496 20374315 : if (code == GIMPLE_CALL
1497 3924449 : && flag_cf_protection & CF_BRANCH)
1498 1723393 : hstate.add_flag (gimple_call_nocf_check_p (as_a <gcall *> (stmt)));
1499 20374315 : }
1500 20374315 : break;
1501 : default:
1502 : break;
1503 : }
1504 20839900 : }
1505 :
1506 :
1507 : /* Return true if polymorphic comparison must be processed. */
1508 :
1509 : bool
1510 65877 : sem_function::compare_polymorphic_p (void)
1511 : {
1512 65877 : struct cgraph_edge *e;
1513 :
1514 131754 : if (!opt_for_fn (get_node ()->decl, flag_devirtualize))
1515 : return false;
1516 131754 : 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 146539 : for (e = get_node ()->callees; e; e = e->next_callee)
1521 69448 : if (e->callee->definition
1522 69448 : && 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 1029852 : sem_function::parse (cgraph_node *node, bitmap_obstack *stack,
1532 : func_checker *checker)
1533 : {
1534 1029852 : tree fndecl = node->decl;
1535 1029852 : function *func = DECL_STRUCT_FUNCTION (fndecl);
1536 :
1537 1029852 : if (!func || (!node->has_gimple_body_p () && !node->thunk))
1538 : return NULL;
1539 :
1540 970981 : if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
1541 : return NULL;
1542 :
1543 949826 : if (lookup_attribute_by_prefix ("oacc ",
1544 949826 : DECL_ATTRIBUTES (node->decl)) != NULL)
1545 : return NULL;
1546 :
1547 : /* PR ipa/70306. */
1548 949826 : if (DECL_STATIC_CONSTRUCTOR (node->decl)
1549 949826 : || DECL_STATIC_DESTRUCTOR (node->decl))
1550 : return NULL;
1551 :
1552 942465 : sem_function *f = new sem_function (node, stack);
1553 942465 : f->init (checker);
1554 :
1555 942465 : 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 397398 : sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
1563 : {
1564 397398 : gphi_iterator si1, si2;
1565 397398 : gphi *phi1, *phi2;
1566 397398 : unsigned size1, size2, i;
1567 397398 : tree t1, t2;
1568 397398 : edge e1, e2;
1569 :
1570 397398 : gcc_assert (bb1 != NULL);
1571 397398 : gcc_assert (bb2 != NULL);
1572 :
1573 397398 : si2 = gsi_start_nonvirtual_phis (bb2);
1574 422507 : for (si1 = gsi_start_nonvirtual_phis (bb1); !gsi_end_p (si1);
1575 25109 : gsi_next_nonvirtual_phi (&si1))
1576 : {
1577 25142 : if (gsi_end_p (si1) && gsi_end_p (si2))
1578 : break;
1579 :
1580 25142 : if (gsi_end_p (si1) || gsi_end_p (si2))
1581 0 : return return_false();
1582 :
1583 25142 : phi1 = si1.phi ();
1584 25142 : phi2 = si2.phi ();
1585 :
1586 25142 : tree phi_result1 = gimple_phi_result (phi1);
1587 25142 : tree phi_result2 = gimple_phi_result (phi2);
1588 :
1589 25142 : 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 25141 : size1 = gimple_phi_num_args (phi1);
1594 25141 : size2 = gimple_phi_num_args (phi2);
1595 :
1596 25141 : 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 83130 : for (i = 0; i < size1; ++i)
1602 : {
1603 58021 : t1 = gimple_phi_arg (phi1, i)->def;
1604 58021 : t2 = gimple_phi_arg (phi2, i)->def;
1605 :
1606 58021 : if (!m_checker->compare_operand (t1, t2, func_checker::OP_NORMAL))
1607 32 : return return_false ();
1608 :
1609 57989 : e1 = gimple_phi_arg_edge (phi1, i);
1610 57989 : e2 = gimple_phi_arg_edge (phi2, i);
1611 :
1612 57989 : if (!m_checker->compare_edge (e1, e2))
1613 0 : return return_false ();
1614 : }
1615 :
1616 25109 : 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 1006674 : sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
1627 : {
1628 1006674 : source++;
1629 1006674 : target++;
1630 :
1631 1006674 : if (bb_dict->length () <= (unsigned)source)
1632 297385 : bb_dict->safe_grow_cleared (source + 1, true);
1633 :
1634 1006674 : if ((*bb_dict)[source] == 0)
1635 : {
1636 316053 : (*bb_dict)[source] = target;
1637 316053 : return true;
1638 : }
1639 : else
1640 690621 : return (*bb_dict)[source] == target;
1641 : }
1642 :
1643 2291441 : sem_variable::sem_variable (varpool_node *node, bitmap_obstack *stack)
1644 2291441 : : sem_item (VAR, node, stack)
1645 : {
1646 2291441 : gcc_checking_assert (node);
1647 2291441 : gcc_checking_assert (get_node ());
1648 2291441 : }
1649 :
1650 : /* Fast equality function based on knowledge known in WPA. */
1651 :
1652 : bool
1653 438926 : sem_variable::equals_wpa (sem_item *item,
1654 : hash_map <symtab_node *, sem_item *> &ignored_nodes)
1655 : {
1656 438926 : gcc_assert (item->type == VAR);
1657 :
1658 438926 : if (node->must_remain_in_tu_name || item->node->must_remain_in_tu_name
1659 438926 : || 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 622982 : if (node->num_references () != item->node->num_references ())
1663 0 : return return_false_with_msg ("different number of references");
1664 :
1665 438926 : 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 438926 : if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
1672 0 : return return_false_with_msg ("Virtual flag mismatch");
1673 :
1674 438926 : if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
1675 438926 : && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
1676 14241 : || !operand_equal_p (DECL_SIZE (decl),
1677 14241 : DECL_SIZE (item->decl), OEP_ONLY_CONST)))
1678 14241 : 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 830729 : if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
1683 424684 : || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
1684 424686 : && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
1685 1 : return return_false_with_msg ("user section mismatch");
1686 :
1687 424684 : if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
1688 0 : return return_false_with_msg ("text section");
1689 :
1690 424684 : if (TYPE_ADDR_SPACE (TREE_TYPE (decl))
1691 424684 : != TYPE_ADDR_SPACE (TREE_TYPE (item->decl)))
1692 0 : return return_false_with_msg ("address-space");
1693 :
1694 424684 : ipa_ref *ref = NULL, *ref2 = NULL;
1695 546236 : for (unsigned i = 0; node->iterate_reference (i, ref); i++)
1696 : {
1697 121738 : item->node->iterate_reference (i, ref2);
1698 :
1699 121738 : if (ref->use != ref2->use)
1700 0 : return return_false_with_msg ("reference use mismatch");
1701 :
1702 121738 : if (!compare_symbol_references (ignored_nodes,
1703 : ref->referred, ref2->referred,
1704 121738 : 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 466646 : sem_variable::equals (sem_item *item,
1715 : hash_map <symtab_node *, sem_item *> &)
1716 : {
1717 466646 : gcc_assert (item->type == VAR);
1718 466646 : bool ret;
1719 :
1720 466646 : if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
1721 144 : dyn_cast <varpool_node *>(node)->get_constructor ();
1722 466646 : 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 466646 : if (!func_checker::compatible_types_p (TREE_TYPE (decl),
1727 466646 : TREE_TYPE (item->decl)))
1728 46112 : return return_false_with_msg ("variables types are different");
1729 :
1730 420534 : ret = sem_variable::equals (DECL_INITIAL (decl),
1731 420534 : DECL_INITIAL (item->node->decl));
1732 420534 : 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 1988708 : sem_variable::equals (tree t1, tree t2)
1745 : {
1746 2370505 : if (!t1 || !t2)
1747 2011 : return return_with_debug (t1 == t2);
1748 2368494 : if (t1 == t2)
1749 : return true;
1750 1112286 : tree_code tc1 = TREE_CODE (t1);
1751 1112286 : tree_code tc2 = TREE_CODE (t2);
1752 :
1753 1112286 : if (tc1 != tc2)
1754 0 : return return_false_with_msg ("TREE_CODE mismatch");
1755 :
1756 1112286 : switch (tc1)
1757 : {
1758 415193 : case CONSTRUCTOR:
1759 415193 : {
1760 415193 : vec<constructor_elt, va_gc> *v1, *v2;
1761 415193 : unsigned HOST_WIDE_INT idx;
1762 :
1763 415193 : enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
1764 415193 : if (typecode != TREE_CODE (TREE_TYPE (t2)))
1765 0 : return return_false_with_msg ("constructor type mismatch");
1766 :
1767 415193 : if (typecode == ARRAY_TYPE)
1768 : {
1769 166782 : HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
1770 : /* For arrays, check that the sizes all match. */
1771 166782 : if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
1772 166782 : || size_1 == -1
1773 333564 : || 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 415193 : v1 = CONSTRUCTOR_ELTS (t1);
1781 415193 : v2 = CONSTRUCTOR_ELTS (t2);
1782 1123095 : if (vec_safe_length (v1) != vec_safe_length (v2))
1783 0 : return return_false_with_msg ("constructor number of elts mismatch");
1784 :
1785 1157304 : for (idx = 0; idx < vec_safe_length (v1); ++idx)
1786 : {
1787 744624 : constructor_elt *c1 = &(*v1)[idx];
1788 744624 : constructor_elt *c2 = &(*v2)[idx];
1789 :
1790 : /* Check that each value is the same... */
1791 744624 : if (!sem_variable::equals (c1->value, c2->value))
1792 : return false;
1793 : /* ... and that they apply to the same fields! */
1794 744624 : 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 381041 : case ADDR_EXPR:
1815 381041 : case FDESC_EXPR:
1816 381041 : {
1817 381041 : tree op1 = TREE_OPERAND (t1, 0);
1818 381041 : tree op2 = TREE_OPERAND (t2, 0);
1819 381041 : 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 658 : case INTEGER_CST:
1835 : /* Integer constants are the same only if the same width of type. */
1836 658 : if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1837 47 : 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 263793 : case STRING_CST:
1842 263793 : if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1843 0 : return return_false_with_msg ("STRING_CST mode mismatch");
1844 263793 : if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
1845 0 : return return_false_with_msg ("STRING_CST length mismatch");
1846 263793 : if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
1847 263793 : 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 18523 : case ARRAY_REF:
1881 18523 : case ARRAY_RANGE_REF:
1882 18523 : {
1883 18523 : tree x1 = TREE_OPERAND (t1, 0);
1884 18523 : tree x2 = TREE_OPERAND (t2, 0);
1885 18523 : tree y1 = TREE_OPERAND (t1, 1);
1886 18523 : tree y2 = TREE_OPERAND (t2, 1);
1887 :
1888 18523 : if (!sem_variable::equals (x1, x2) || !sem_variable::equals (y1, y2))
1889 0 : return false;
1890 18523 : if (!sem_variable::equals (array_ref_low_bound (t1),
1891 : array_ref_low_bound (t2)))
1892 : return false;
1893 18523 : 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 0 : default:
1921 0 : 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 2335933 : sem_variable::parse (varpool_node *node, bitmap_obstack *stack,
1929 : func_checker *checker)
1930 : {
1931 2271679 : if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl)
1932 4607560 : || node->alias)
1933 : return NULL;
1934 :
1935 2271542 : sem_variable *v = new sem_variable (node, stack);
1936 2271542 : v->init (checker);
1937 :
1938 2271542 : return v;
1939 : }
1940 :
1941 : /* Semantic variable initialization function. */
1942 :
1943 : void
1944 2776524 : sem_variable::init (ipa_icf_gimple::func_checker *checker)
1945 : {
1946 2776524 : 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 2776524 : if (!m_hash_set)
1952 : {
1953 2271542 : gcc_assert (!node->lto_file_data);
1954 2271542 : inchash::hash hstate;
1955 2271542 : hstate.add_int (456346417);
1956 2271542 : checker->hash_operand (DECL_INITIAL (decl), hstate, 0);
1957 2271542 : set_hash (hstate.end ());
1958 : }
1959 2776524 : }
1960 :
1961 : /* References independent hash function. */
1962 :
1963 : hashval_t
1964 8759774 : sem_variable::get_hash (void)
1965 : {
1966 8759774 : gcc_checking_assert (m_hash_set);
1967 8759774 : 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 417998 : sem_variable::merge (sem_item *alias_item)
1975 : {
1976 417998 : gcc_assert (alias_item->type == VAR);
1977 :
1978 417998 : AUTO_DUMP_SCOPE ("merge",
1979 : dump_user_location_t::from_function_decl (decl));
1980 417998 : 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 417998 : 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 417998 : sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
1997 :
1998 417998 : varpool_node *original = get_node ();
1999 417998 : varpool_node *alias = alias_var->get_node ();
2000 417998 : bool original_discardable = false;
2001 :
2002 417998 : 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 417998 : if (original->can_be_discarded_p ()
2010 417998 : || (node->resolution != LDPR_UNKNOWN
2011 416554 : && !decl_binds_to_current_def_p (node->decl)))
2012 : original_discardable = true;
2013 :
2014 417998 : 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 417998 : if (DECL_IN_CONSTANT_POOL (alias->decl)
2022 417998 : || 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 820494 : if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
2033 417995 : || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
2034 417995 : && 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 417995 : if (alias_address_matters && flag_merge_constants < 2)
2045 : {
2046 405616 : if (dump_enabled_p ())
2047 1 : dump_printf (MSG_MISSED_OPTIMIZATION,
2048 : "Not unifying; address of original may be compared.\n");
2049 405616 : return false;
2050 : }
2051 :
2052 12379 : if (DECL_ALIGN (original->decl) != DECL_ALIGN (alias->decl)
2053 12379 : && (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 12365 : 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 12365 : 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 12281 : 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 12277 : gcc_assert (!original->alias);
2096 12277 : gcc_assert (!alias->alias);
2097 :
2098 12277 : alias->analyzed = false;
2099 :
2100 12277 : DECL_INITIAL (alias->decl) = NULL;
2101 12277 : ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
2102 : NULL, true);
2103 12277 : alias->remove_all_references ();
2104 12277 : if (TREE_ADDRESSABLE (alias->decl))
2105 366 : original->call_for_symbol_and_aliases (set_addressable, NULL, true);
2106 :
2107 12277 : varpool_node::create_alias (alias_var->decl, decl);
2108 12277 : alias->resolve_alias (original);
2109 :
2110 12277 : if (dump_enabled_p ())
2111 17 : dump_printf (MSG_OPTIMIZED_LOCATIONS,
2112 : "Unified; Variable alias has been created.\n");
2113 :
2114 12277 : 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 136561 : sem_item_optimizer::sem_item_optimizer ()
2132 136561 : : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL),
2133 136561 : m_varpool_node_hooks (NULL), m_merged_variables (), m_references ()
2134 : {
2135 136561 : m_items.create (0);
2136 136561 : bitmap_obstack_initialize (&m_bmstack);
2137 136561 : }
2138 :
2139 127522 : sem_item_optimizer::~sem_item_optimizer ()
2140 : {
2141 2583314 : for (unsigned int i = 0; i < m_items.length (); i++)
2142 2455792 : delete m_items[i];
2143 :
2144 :
2145 1984956 : for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
2146 3842390 : it != m_classes.end (); ++it)
2147 : {
2148 3810781 : for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2149 3906694 : delete (*it)->classes[i];
2150 :
2151 1857434 : (*it)->classes.release ();
2152 1857434 : free (*it);
2153 : }
2154 :
2155 127522 : m_items.release ();
2156 :
2157 127522 : bitmap_obstack_release (&m_bmstack);
2158 127522 : m_merged_variables.release ();
2159 127522 : }
2160 :
2161 : /* Write IPA ICF summary for symbols. */
2162 :
2163 : void
2164 19795 : sem_item_optimizer::write_summary (void)
2165 : {
2166 19795 : unsigned int count = 0;
2167 :
2168 19795 : output_block *ob = create_output_block (LTO_section_ipa_icf);
2169 19795 : lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
2170 19795 : ob->symbol = NULL;
2171 :
2172 : /* Calculate number of symbols to be serialized. */
2173 19795 : for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2174 367511 : !lsei_end_p (lsei);
2175 347716 : lsei_next_in_partition (&lsei))
2176 : {
2177 347716 : symtab_node *node = dyn_cast <symtab_node *> (lsei_node (lsei));
2178 347716 : if (!node)
2179 56 : continue;
2180 :
2181 347660 : if (m_symtab_node_map.get (node))
2182 323902 : count++;
2183 : }
2184 :
2185 19795 : streamer_write_uhwi (ob, count);
2186 :
2187 : /* Process all of the symbols. */
2188 19795 : for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2189 367511 : !lsei_end_p (lsei);
2190 347716 : lsei_next_in_partition (&lsei))
2191 : {
2192 347716 : symtab_node *node = dyn_cast <symtab_node *> (lsei_node (lsei));
2193 347716 : if (!node)
2194 56 : continue;
2195 :
2196 347660 : sem_item **item = m_symtab_node_map.get (node);
2197 :
2198 347660 : if (item && *item)
2199 : {
2200 323902 : int node_ref = lto_symtab_encoder_encode (encoder, node);
2201 323902 : streamer_write_uhwi_stream (ob->main_stream, node_ref);
2202 :
2203 323902 : streamer_write_uhwi (ob, (*item)->get_hash ());
2204 :
2205 323902 : if ((*item)->type == FUNC)
2206 : {
2207 91826 : sem_function *fn = static_cast<sem_function *> (*item);
2208 91826 : streamer_write_uhwi (ob, fn->memory_access_types.length ());
2209 974993 : for (unsigned i = 0; i < fn->memory_access_types.length (); i++)
2210 627333 : stream_write_tree (ob, fn->memory_access_types[i], true);
2211 : }
2212 : }
2213 : }
2214 :
2215 19795 : streamer_write_char_stream (ob->main_stream, 0);
2216 19795 : produce_asm (ob);
2217 19795 : destroy_output_block (ob);
2218 19795 : }
2219 :
2220 : /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2221 : contains LEN bytes. */
2222 :
2223 : void
2224 10824 : sem_item_optimizer::read_section (lto_file_decl_data *file_data,
2225 : const char *data, size_t len)
2226 : {
2227 10824 : const lto_function_header *header
2228 : = (const lto_function_header *) data;
2229 10824 : const int cfg_offset = sizeof (lto_function_header);
2230 10824 : const int main_offset = cfg_offset + header->cfg_size;
2231 10824 : const int string_offset = main_offset + header->main_size;
2232 10824 : data_in *data_in;
2233 10824 : unsigned int i;
2234 10824 : unsigned int count;
2235 :
2236 10824 : lto_input_block ib_main ((const char *) data + main_offset, 0,
2237 10824 : header->main_size, file_data);
2238 :
2239 10824 : data_in
2240 21648 : = lto_data_in_create (file_data, (const char *) data + string_offset,
2241 10824 : header->string_size, vNULL);
2242 :
2243 10824 : count = streamer_read_uhwi (&ib_main);
2244 :
2245 107616 : for (i = 0; i < count; i++)
2246 : {
2247 96792 : unsigned int index;
2248 96792 : toplevel_node *node;
2249 96792 : lto_symtab_encoder_t encoder;
2250 :
2251 96792 : index = streamer_read_uhwi (&ib_main);
2252 96792 : encoder = file_data->symtab_node_encoder;
2253 96792 : node = lto_symtab_encoder_deref (encoder, index);
2254 :
2255 96792 : hashval_t hash = streamer_read_uhwi (&ib_main);
2256 96792 : if (symtab_node *snode = dyn_cast <symtab_node *> (node))
2257 96792 : gcc_assert (snode->definition);
2258 :
2259 96792 : if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
2260 : {
2261 76893 : sem_function *fn = new sem_function (cnode, &m_bmstack);
2262 76893 : unsigned count = streamer_read_uhwi (&ib_main);
2263 76893 : inchash::hash hstate (0);
2264 76893 : if (flag_incremental_link == INCREMENTAL_LINK_LTO)
2265 41 : fn->memory_access_types.reserve_exact (count);
2266 611060 : for (unsigned i = 0; i < count; i++)
2267 : {
2268 534167 : tree type = stream_read_tree (&ib_main, data_in);
2269 534167 : hstate.add_int (get_deref_alias_set (type));
2270 534167 : if (flag_incremental_link == INCREMENTAL_LINK_LTO)
2271 138 : fn->memory_access_types.quick_push (type);
2272 : }
2273 76893 : fn->m_alias_sets_hash = hstate.end ();
2274 76893 : fn->set_hash (hash);
2275 76893 : m_items.safe_push (fn);
2276 : }
2277 116691 : else if (varpool_node *vnode = dyn_cast <varpool_node *> (node))
2278 : {
2279 19899 : sem_variable *var = new sem_variable (vnode, &m_bmstack);
2280 19899 : var->set_hash (hash);
2281 19899 : m_items.safe_push (var);
2282 : }
2283 : }
2284 :
2285 10824 : lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
2286 : len);
2287 10824 : lto_data_in_delete (data_in);
2288 10824 : }
2289 :
2290 : /* Read IPA ICF summary for symbols. */
2291 :
2292 : void
2293 12211 : sem_item_optimizer::read_summary (void)
2294 : {
2295 12211 : lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2296 12211 : lto_file_decl_data *file_data;
2297 12211 : unsigned int j = 0;
2298 :
2299 37688 : while ((file_data = file_data_vec[j++]))
2300 : {
2301 13266 : size_t len;
2302 13266 : const char *data
2303 13266 : = lto_get_summary_section_data (file_data, LTO_section_ipa_icf, &len);
2304 13266 : if (data)
2305 10824 : read_section (file_data, data, len);
2306 : }
2307 12211 : }
2308 :
2309 : /* Register callgraph and varpool hooks. */
2310 :
2311 : void
2312 136561 : sem_item_optimizer::register_hooks (void)
2313 : {
2314 136561 : if (!m_cgraph_node_hooks)
2315 136561 : m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
2316 136561 : (&sem_item_optimizer::cgraph_removal_hook, this);
2317 :
2318 136561 : if (!m_varpool_node_hooks)
2319 136561 : m_varpool_node_hooks = symtab->add_varpool_removal_hook
2320 136561 : (&sem_item_optimizer::varpool_removal_hook, this);
2321 136561 : }
2322 :
2323 : /* Unregister callgraph and varpool hooks. */
2324 :
2325 : void
2326 127522 : sem_item_optimizer::unregister_hooks (void)
2327 : {
2328 127522 : if (m_cgraph_node_hooks)
2329 127522 : symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
2330 :
2331 127522 : if (m_varpool_node_hooks)
2332 127522 : symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
2333 127522 : }
2334 :
2335 : /* Adds a CLS to hashtable associated by hash value. */
2336 :
2337 : void
2338 30710 : sem_item_optimizer::add_class (congruence_class *cls)
2339 : {
2340 30710 : gcc_assert (cls->members.length ());
2341 :
2342 30710 : congruence_class_group *group
2343 30710 : = get_group_by_hash (cls->members[0]->get_hash (),
2344 30710 : cls->members[0]->type);
2345 30710 : group->classes.safe_push (cls);
2346 30710 : }
2347 :
2348 : /* Gets a congruence class group based on given HASH value and TYPE. */
2349 :
2350 : congruence_class_group *
2351 2486502 : sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
2352 : {
2353 2486502 : congruence_class_group *item = XNEW (congruence_class_group);
2354 2486502 : item->hash = hash;
2355 2486502 : item->type = type;
2356 :
2357 2486502 : congruence_class_group **slot = m_classes.find_slot (item, INSERT);
2358 :
2359 2486502 : if (*slot)
2360 629068 : free (item);
2361 : else
2362 : {
2363 1857434 : item->classes.create (1);
2364 1857434 : *slot = item;
2365 : }
2366 :
2367 2486502 : return *slot;
2368 : }
2369 :
2370 : /* Callgraph removal hook called for a NODE with a custom DATA. */
2371 :
2372 : void
2373 11138 : sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
2374 : {
2375 11138 : sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2376 11138 : optimizer->remove_symtab_node (node);
2377 11138 : }
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 14552 : sem_item_optimizer::remove_symtab_node (symtab_node *node)
2392 : {
2393 14552 : gcc_assert (m_classes.is_empty ());
2394 :
2395 14552 : m_removed_items_set.add (node);
2396 14552 : }
2397 :
2398 : void
2399 700525 : sem_item_optimizer::remove_item (sem_item *item)
2400 : {
2401 700525 : if (m_symtab_node_map.get (item->node))
2402 677196 : m_symtab_node_map.remove (item->node);
2403 700525 : delete item;
2404 700525 : }
2405 :
2406 : /* Removes all callgraph and varpool nodes that are marked by symtab
2407 : as deleted. */
2408 :
2409 : void
2410 127522 : sem_item_optimizer::filter_removed_items (void)
2411 : {
2412 127522 : auto_vec <sem_item *> filtered;
2413 :
2414 3283839 : for (unsigned int i = 0; i < m_items.length(); i++)
2415 : {
2416 3156317 : sem_item *item = m_items[i];
2417 :
2418 3156317 : if (m_removed_items_set.contains (item->node))
2419 : {
2420 8855 : remove_item (item);
2421 8855 : continue;
2422 : }
2423 :
2424 3147462 : if (item->type == FUNC)
2425 : {
2426 971165 : cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
2427 :
2428 971165 : if (in_lto_p && (cnode->alias || cnode->body_removed))
2429 11 : remove_item (item);
2430 : else
2431 971154 : filtered.safe_push (item);
2432 : }
2433 : else /* VAR. */
2434 : {
2435 2176297 : if (!flag_ipa_icf_variables)
2436 1 : remove_item (item);
2437 : else
2438 : {
2439 : /* Filter out non-readonly variables. */
2440 2176296 : tree decl = item->decl;
2441 2176296 : varpool_node *vnode = static_cast <sem_variable *>(item)->get_node ();
2442 2176296 : if (!TREE_READONLY (decl) || vnode->body_removed)
2443 691658 : remove_item (item);
2444 : else
2445 1484638 : filtered.safe_push (item);
2446 : }
2447 : }
2448 : }
2449 :
2450 : /* Clean-up of released semantic items. */
2451 :
2452 127522 : m_items.release ();
2453 2583314 : for (unsigned int i = 0; i < filtered.length(); i++)
2454 2455792 : m_items.safe_push (filtered[i]);
2455 127522 : }
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 127522 : sem_item_optimizer::execute (void)
2463 : {
2464 127522 : filter_removed_items ();
2465 127522 : unregister_hooks ();
2466 :
2467 127522 : build_graph ();
2468 127522 : update_hash_by_addr_refs ();
2469 127522 : update_hash_by_memory_access_type ();
2470 127522 : build_hash_based_classes ();
2471 :
2472 127522 : if (dump_file)
2473 182 : fprintf (dump_file, "Dump after hash based groups\n");
2474 127522 : dump_cong_classes ();
2475 :
2476 127522 : subdivide_classes_by_equality (true);
2477 :
2478 127522 : if (dump_file)
2479 182 : fprintf (dump_file, "Dump after WPA based types groups\n");
2480 :
2481 127522 : dump_cong_classes ();
2482 :
2483 127522 : process_cong_reduction ();
2484 127522 : checking_verify_classes ();
2485 :
2486 127522 : if (dump_file)
2487 182 : fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
2488 :
2489 127522 : dump_cong_classes ();
2490 :
2491 127522 : unsigned int loaded_symbols = parse_nonsingleton_classes ();
2492 127522 : subdivide_classes_by_equality ();
2493 :
2494 127522 : if (dump_file)
2495 182 : fprintf (dump_file, "Dump after full equality comparison of groups\n");
2496 :
2497 127522 : dump_cong_classes ();
2498 :
2499 127522 : unsigned int prev_class_count = m_classes_count;
2500 :
2501 127522 : process_cong_reduction ();
2502 127522 : dump_cong_classes ();
2503 127522 : checking_verify_classes ();
2504 127522 : bool merged_p = merge_classes (prev_class_count, loaded_symbols);
2505 :
2506 127522 : if (dump_file && (dump_flags & TDF_DETAILS))
2507 20 : symtab->dump (dump_file);
2508 :
2509 127522 : 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 124350 : sem_item_optimizer::parse_funcs_and_vars (void)
2517 : {
2518 124350 : cgraph_node *cnode;
2519 :
2520 : /* Create dummy func_checker for hashing purpose. */
2521 124350 : func_checker checker;
2522 :
2523 124350 : if (flag_ipa_icf_functions)
2524 1150693 : FOR_EACH_DEFINED_FUNCTION (cnode)
2525 : {
2526 1029852 : sem_function *f = sem_function::parse (cnode, &m_bmstack, &checker);
2527 1029852 : if (f)
2528 : {
2529 942465 : m_items.safe_push (f);
2530 942465 : m_symtab_node_map.put (cnode, f);
2531 : }
2532 : }
2533 :
2534 124350 : varpool_node *vnode;
2535 :
2536 124350 : if (flag_ipa_icf_variables)
2537 2460280 : FOR_EACH_DEFINED_VARIABLE (vnode)
2538 : {
2539 2335933 : sem_variable *v = sem_variable::parse (vnode, &m_bmstack, &checker);
2540 :
2541 2335933 : if (v)
2542 : {
2543 2271542 : m_items.safe_push (v);
2544 2271542 : m_symtab_node_map.put (vnode, v);
2545 : }
2546 : }
2547 124350 : }
2548 :
2549 : /* Makes pairing between a congruence class CLS and semantic ITEM. */
2550 :
2551 : void
2552 3995098 : sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
2553 : {
2554 3995098 : item->index_in_class = cls->members.length ();
2555 3995098 : cls->members.safe_push (item);
2556 3995098 : cls->referenced_by_count += item->referenced_by_count;
2557 3995098 : item->cls = cls;
2558 3995098 : }
2559 :
2560 : /* For each semantic item, append hash values of references. */
2561 :
2562 : void
2563 127522 : 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 5159709 : for (unsigned i = 0; i < m_items.length (); i++)
2568 : {
2569 2455792 : m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
2570 2455792 : if (m_items[i]->type == FUNC)
2571 : {
2572 971154 : if (TREE_CODE (TREE_TYPE (m_items[i]->decl)) == METHOD_TYPE
2573 281702 : && contains_polymorphic_type_p
2574 281702 : (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl)))
2575 1042040 : && (DECL_CXX_CONSTRUCTOR_P (m_items[i]->decl)
2576 60838 : || (static_cast<sem_function *> (m_items[i])->param_used_p (0)
2577 101828 : && static_cast<sem_function *> (m_items[i])
2578 50914 : ->compare_polymorphic_p ())))
2579 : {
2580 43903 : tree class_type
2581 43903 : = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl));
2582 43903 : 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 43903 : if (TYPE_NAME (class_type)
2589 43903 : && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type))
2590 44217 : && !type_in_anonymous_namespace_p
2591 314 : (class_type))
2592 310 : hstate.add_hwi
2593 310 : (IDENTIFIER_HASH_VALUE
2594 : (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type))));
2595 : else
2596 : {
2597 43593 : gcc_checking_assert
2598 : (!in_lto_p
2599 : || type_in_anonymous_namespace_p (class_type));
2600 43593 : hstate.add_hwi (TYPE_UID (TYPE_MAIN_VARIANT (class_type)));
2601 : }
2602 :
2603 43903 : 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 5159709 : for (unsigned i = 0; i < m_items.length (); i++)
2613 2455792 : m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
2614 :
2615 : /* Global hash value replace current hash values. */
2616 2583314 : for (unsigned i = 0; i < m_items.length (); i++)
2617 2455792 : m_items[i]->set_hash (m_items[i]->global_hash);
2618 127522 : }
2619 :
2620 : void
2621 127522 : sem_item_optimizer::update_hash_by_memory_access_type ()
2622 : {
2623 2583314 : for (unsigned i = 0; i < m_items.length (); i++)
2624 : {
2625 2455792 : if (m_items[i]->type == FUNC)
2626 : {
2627 971154 : sem_function *fn = static_cast<sem_function *> (m_items[i]);
2628 971154 : inchash::hash hstate (fn->get_hash ());
2629 971154 : hstate.add_int (fn->m_alias_sets_hash);
2630 971154 : fn->set_hash (hstate.end ());
2631 : }
2632 : }
2633 127522 : }
2634 :
2635 : /* Congruence classes are built by hash value. */
2636 :
2637 : void
2638 127522 : sem_item_optimizer::build_hash_based_classes (void)
2639 : {
2640 2583314 : for (unsigned i = 0; i < m_items.length (); i++)
2641 : {
2642 2455792 : sem_item *item = m_items[i];
2643 :
2644 2455792 : congruence_class_group *group
2645 2455792 : = get_group_by_hash (item->get_hash (), item->type);
2646 :
2647 2455792 : if (!group->classes.length ())
2648 : {
2649 1857434 : m_classes_count++;
2650 1857434 : group->classes.safe_push (new congruence_class (class_id++));
2651 : }
2652 :
2653 2455792 : add_item_to_class (group->classes[0], item);
2654 : }
2655 127522 : }
2656 :
2657 : /* Build references according to call graph. */
2658 :
2659 : void
2660 127522 : sem_item_optimizer::build_graph (void)
2661 : {
2662 5159709 : for (unsigned i = 0; i < m_items.length (); i++)
2663 : {
2664 2455792 : sem_item *item = m_items[i];
2665 2455792 : m_symtab_node_map.put (item->node, item);
2666 :
2667 : /* Initialize hash values if we are not in LTO mode. */
2668 2455792 : if (!in_lto_p)
2669 2382436 : item->get_hash ();
2670 : }
2671 :
2672 2583314 : for (unsigned i = 0; i < m_items.length (); i++)
2673 : {
2674 2455792 : sem_item *item = m_items[i];
2675 :
2676 2455792 : if (item->type == FUNC)
2677 : {
2678 971154 : cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
2679 :
2680 971154 : cgraph_edge *e = cnode->callees;
2681 4715497 : while (e)
2682 : {
2683 3744343 : sem_item **slot = m_symtab_node_map.get
2684 3744343 : (e->callee->ultimate_alias_target ());
2685 3744343 : if (slot)
2686 1612760 : item->add_reference (&m_references, *slot);
2687 :
2688 3744343 : e = e->next_callee;
2689 : }
2690 : }
2691 :
2692 6853209 : ipa_ref *ref = NULL;
2693 7827057 : for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
2694 : {
2695 4397417 : sem_item **slot = m_symtab_node_map.get
2696 4397417 : (ref->referred->ultimate_alias_target ());
2697 4397417 : if (slot)
2698 2325646 : item->add_reference (&m_references, *slot);
2699 : }
2700 : }
2701 127522 : }
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 127522 : sem_item_optimizer::parse_nonsingleton_classes (void)
2708 : {
2709 127522 : unsigned int counter = 0;
2710 :
2711 : /* Create dummy func_checker for hashing purpose. */
2712 127522 : func_checker checker;
2713 :
2714 2583314 : for (unsigned i = 0; i < m_items.length (); i++)
2715 3098460 : if (m_items[i]->cls->members.length () > 1)
2716 : {
2717 642668 : m_items[i]->init (&checker);
2718 642668 : ++counter;
2719 : }
2720 :
2721 127522 : 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 255044 : return counter;
2728 127522 : }
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 255044 : sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
2735 : {
2736 3969912 : for (hash_table <congruence_class_hash>::iterator it = m_classes.begin ();
2737 7684780 : it != m_classes.end (); ++it)
2738 : {
2739 3714868 : unsigned int class_count = (*it)->classes.length ();
2740 :
2741 7509692 : for (unsigned i = 0; i < class_count; i++)
2742 : {
2743 3794824 : congruence_class *c = (*it)->classes[i];
2744 :
2745 4057280 : if (c->members.length() > 1)
2746 : {
2747 262456 : auto_vec <sem_item *> new_vector;
2748 :
2749 262456 : sem_item *first = c->members[0];
2750 262456 : new_vector.safe_push (first);
2751 :
2752 262456 : unsigned class_split_first = (*it)->classes.length ();
2753 :
2754 1379216 : for (unsigned j = 1; j < c->members.length (); j++)
2755 : {
2756 1116760 : sem_item *item = c->members[j];
2757 :
2758 1116760 : bool equals
2759 1116760 : = in_wpa ? first->equals_wpa (item, m_symtab_node_map)
2760 1116760 : : first->equals (item, m_symtab_node_map);
2761 :
2762 1116760 : if (equals)
2763 958962 : new_vector.safe_push (item);
2764 : else
2765 : {
2766 1672768 : bool integrated = false;
2767 :
2768 1514970 : for (unsigned k = class_split_first;
2769 1672768 : k < (*it)->classes.length (); k++)
2770 : {
2771 1592210 : sem_item *x = (*it)->classes[k]->members[0];
2772 1592210 : bool equals
2773 1592210 : = in_wpa ? x->equals_wpa (item, m_symtab_node_map)
2774 1592210 : : x->equals (item, m_symtab_node_map);
2775 :
2776 1592210 : if (equals)
2777 : {
2778 77240 : integrated = true;
2779 77240 : add_item_to_class ((*it)->classes[k], item);
2780 :
2781 77240 : break;
2782 : }
2783 : }
2784 :
2785 77240 : if (!integrated)
2786 : {
2787 80558 : congruence_class *c
2788 80558 : = new congruence_class (class_id++);
2789 80558 : m_classes_count++;
2790 80558 : add_item_to_class (c, item);
2791 :
2792 80558 : (*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 262456 : c->members.release ();
2800 262456 : c->members.create (new_vector.length ());
2801 :
2802 1483874 : for (unsigned int j = 0; j < new_vector.length (); j++)
2803 1221418 : add_item_to_class (c, new_vector[j]);
2804 262456 : }
2805 : }
2806 : }
2807 :
2808 255044 : checking_verify_classes ();
2809 255044 : }
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 255044 : sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2818 : {
2819 255044 : typedef hash_map <symbol_compare_hash, vec <sem_item *> > subdivide_hash_map;
2820 :
2821 255044 : unsigned newly_created_classes = 0;
2822 :
2823 255044 : for (hash_table <congruence_class_hash>::iterator it = m_classes.begin ();
2824 7684780 : it != m_classes.end (); ++it)
2825 : {
2826 3714868 : unsigned int class_count = (*it)->classes.length ();
2827 3714868 : auto_vec<congruence_class *> new_classes;
2828 :
2829 7605605 : for (unsigned i = 0; i < class_count; i++)
2830 : {
2831 3890737 : congruence_class *c = (*it)->classes[i];
2832 :
2833 4141700 : if (c->members.length() > 1)
2834 : {
2835 250963 : subdivide_hash_map split_map;
2836 :
2837 1522773 : for (unsigned j = 0; j < c->members.length (); j++)
2838 : {
2839 1271810 : sem_item *source_node = c->members[j];
2840 :
2841 1271810 : symbol_compare_collection *collection
2842 1271810 : = new symbol_compare_collection (source_node->node);
2843 :
2844 1271810 : bool existed;
2845 1271810 : vec <sem_item *> *slot
2846 1271810 : = &split_map.get_or_insert (collection, &existed);
2847 1271810 : gcc_checking_assert (slot);
2848 :
2849 1271810 : slot->safe_push (source_node);
2850 :
2851 1271810 : if (existed)
2852 2041694 : delete collection;
2853 : }
2854 :
2855 : /* If the map contains more than one key, we have to split
2856 : the map appropriately. */
2857 250963 : 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 501926 : for (subdivide_hash_map::iterator it2 = split_map.begin ();
2888 1003852 : it2 != split_map.end (); ++it2)
2889 : {
2890 501926 : delete (*it2).first;
2891 250963 : (*it2).second.release ();
2892 : }
2893 250963 : }
2894 : }
2895 :
2896 3714868 : for (unsigned i = 0; i < new_classes.length (); i++)
2897 0 : (*it)->classes.safe_push (new_classes[i]);
2898 3714868 : }
2899 :
2900 255044 : return newly_created_classes;
2901 : }
2902 :
2903 : /* Verify congruence classes, if checking is enabled. */
2904 :
2905 : void
2906 510088 : sem_item_optimizer::checking_verify_classes (void)
2907 : {
2908 510088 : if (flag_checking)
2909 510056 : verify_classes ();
2910 510088 : }
2911 :
2912 : /* Verify congruence classes. */
2913 :
2914 : void
2915 510056 : sem_item_optimizer::verify_classes (void)
2916 : {
2917 510056 : for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
2918 15369224 : it != m_classes.end (); ++it)
2919 : {
2920 15195551 : for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2921 : {
2922 7765967 : congruence_class *cls = (*it)->classes[i];
2923 :
2924 7765967 : gcc_assert (cls);
2925 7765967 : gcc_assert (cls->members.length () > 0);
2926 :
2927 17588983 : for (unsigned int j = 0; j < cls->members.length (); j++)
2928 : {
2929 9823016 : sem_item *item = cls->members[j];
2930 :
2931 9823016 : gcc_assert (item);
2932 9823016 : gcc_assert (item->cls == cls);
2933 : }
2934 : }
2935 : }
2936 510056 : }
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 154325 : sem_item_optimizer::release_split_map (congruence_class * const &,
2944 : bitmap const &b, traverse_split_pair *)
2945 : {
2946 154325 : bitmap bmp = b;
2947 :
2948 154325 : BITMAP_FREE (bmp);
2949 :
2950 154325 : 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 154325 : sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
2959 : bitmap const &b,
2960 : traverse_split_pair *pair)
2961 : {
2962 154325 : sem_item_optimizer *optimizer = pair->optimizer;
2963 154325 : 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 154325 : unsigned popcount = bitmap_count_bits (b);
2968 :
2969 154325 : if (popcount > 0 && popcount < cls->members.length ())
2970 : {
2971 15355 : auto_vec <congruence_class *, 2> newclasses;
2972 15355 : newclasses.quick_push (new congruence_class (class_id++));
2973 15355 : newclasses.quick_push (new congruence_class (class_id++));
2974 :
2975 175445 : for (unsigned int i = 0; i < cls->members.length (); i++)
2976 : {
2977 160090 : int target = bitmap_bit_p (b, i);
2978 160090 : congruence_class *tc = newclasses[target];
2979 :
2980 160090 : add_item_to_class (tc, cls->members[i]);
2981 : }
2982 :
2983 15355 : if (flag_checking)
2984 : {
2985 46065 : for (unsigned int i = 0; i < 2; i++)
2986 30710 : gcc_assert (newclasses[i]->members.length ());
2987 : }
2988 :
2989 15355 : if (splitter_cls == cls)
2990 6 : optimizer->splitter_class_removed = true;
2991 :
2992 : /* Remove old class from worklist if presented. */
2993 15355 : bool in_worklist = cls->in_worklist;
2994 :
2995 15355 : if (in_worklist)
2996 10889 : cls->in_worklist = false;
2997 :
2998 15355 : congruence_class_group g;
2999 15355 : g.hash = cls->members[0]->get_hash ();
3000 15355 : g.type = cls->members[0]->type;
3001 :
3002 15355 : congruence_class_group *slot = optimizer->m_classes.find (&g);
3003 :
3004 137184 : for (unsigned int i = 0; i < slot->classes.length (); i++)
3005 137184 : if (slot->classes[i] == cls)
3006 : {
3007 15355 : slot->classes.ordered_remove (i);
3008 15355 : break;
3009 : }
3010 :
3011 : /* New class will be inserted and integrated to work list. */
3012 46065 : for (unsigned int i = 0; i < 2; i++)
3013 30710 : optimizer->add_class (newclasses[i]);
3014 :
3015 : /* Two classes replace one, so that increment just by one. */
3016 15355 : 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 15355 : if (in_worklist)
3021 32667 : for (unsigned int i = 0; i < 2; i++)
3022 21778 : optimizer->worklist_push (newclasses[i]);
3023 : else /* Just smaller class is inserted. */
3024 : {
3025 4466 : unsigned int smaller_index
3026 8932 : = (newclasses[0]->members.length ()
3027 4466 : < newclasses[1]->members.length ()
3028 4466 : ? 0 : 1);
3029 4466 : optimizer->worklist_push (newclasses[smaller_index]);
3030 : }
3031 :
3032 15355 : 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 15355 : if (!in_worklist)
3044 8932 : delete cls;
3045 :
3046 15355 : return true;
3047 15355 : }
3048 :
3049 : return false;
3050 : }
3051 :
3052 : /* Compare function for sorting pairs in do_congruence_step_f. */
3053 :
3054 : int
3055 1478752 : sem_item_optimizer::sort_congruence_split (const void *a_, const void *b_)
3056 : {
3057 1478752 : const std::pair<congruence_class *, bitmap> *a
3058 : = (const std::pair<congruence_class *, bitmap> *)a_;
3059 1478752 : const std::pair<congruence_class *, bitmap> *b
3060 : = (const std::pair<congruence_class *, bitmap> *)b_;
3061 1478752 : if (a->first->id < b->first->id)
3062 : return -1;
3063 697740 : else if (a->first->id > b->first->id)
3064 697740 : 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 5023541 : sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
3073 : unsigned int index)
3074 : {
3075 5023541 : hash_map <congruence_class *, bitmap> split_map;
3076 :
3077 32075057 : for (unsigned int i = 0; i < cls->members.length (); i++)
3078 : {
3079 27051516 : sem_item *item = cls->members[i];
3080 27051516 : sem_usage_pair needle (item, index);
3081 27051516 : vec<sem_item *> *callers = m_references.get (&needle);
3082 27051516 : if (callers == NULL)
3083 21277935 : continue;
3084 :
3085 13653306 : for (unsigned int j = 0; j < callers->length (); j++)
3086 : {
3087 7879725 : sem_item *caller = (*callers)[j];
3088 7879725 : if (caller->cls->members.length () < 2)
3089 7372850 : continue;
3090 506875 : bitmap *slot = split_map.get (caller->cls);
3091 506875 : bitmap b;
3092 :
3093 506875 : if(!slot)
3094 : {
3095 154325 : b = BITMAP_ALLOC (&m_bmstack);
3096 154325 : split_map.put (caller->cls, b);
3097 : }
3098 : else
3099 352550 : b = *slot;
3100 :
3101 506875 : gcc_checking_assert (caller->cls);
3102 506875 : gcc_checking_assert (caller->index_in_class
3103 : < caller->cls->members.length ());
3104 :
3105 506875 : bitmap_set_bit (b, caller->index_in_class);
3106 : }
3107 : }
3108 :
3109 5023541 : auto_vec<std::pair<congruence_class *, bitmap> > to_split;
3110 5023541 : to_split.reserve_exact (split_map.elements ());
3111 5023541 : for (hash_map <congruence_class *, bitmap>::iterator i = split_map.begin ();
3112 5332191 : i != split_map.end (); ++i)
3113 154325 : to_split.safe_push (*i);
3114 5023541 : to_split.qsort (sort_congruence_split);
3115 :
3116 5023541 : traverse_split_pair pair;
3117 5023541 : pair.optimizer = this;
3118 5023541 : pair.cls = cls;
3119 :
3120 5023541 : splitter_class_removed = false;
3121 5023541 : bool r = false;
3122 5177866 : for (unsigned i = 0; i < to_split.length (); ++i)
3123 154325 : r |= traverse_congruence_split (to_split[i].first, to_split[i].second,
3124 : &pair);
3125 :
3126 : /* Bitmap clean-up. */
3127 5023541 : split_map.traverse <traverse_split_pair *,
3128 5177866 : sem_item_optimizer::release_split_map> (NULL);
3129 :
3130 5023541 : return r;
3131 5023541 : }
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 2929407 : sem_item_optimizer::do_congruence_step (congruence_class *cls)
3139 : {
3140 2929407 : bitmap_iterator bi;
3141 2929407 : unsigned int i;
3142 :
3143 2929407 : bitmap usage = BITMAP_ALLOC (&m_bmstack);
3144 :
3145 6809237 : for (unsigned int i = 0; i < cls->members.length (); i++)
3146 3879830 : bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
3147 :
3148 7952942 : EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
3149 : {
3150 5023541 : 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 5023541 : do_congruence_step_for_index (cls, i);
3155 :
3156 5023541 : if (splitter_class_removed)
3157 : break;
3158 : }
3159 :
3160 2929407 : BITMAP_FREE (usage);
3161 2929407 : }
3162 :
3163 : /* Adds a newly created congruence class CLS to worklist. */
3164 :
3165 : void
3166 2940296 : sem_item_optimizer::worklist_push (congruence_class *cls)
3167 : {
3168 : /* Return if the class CLS is already presented in work list. */
3169 2940296 : if (cls->in_worklist)
3170 : return;
3171 :
3172 2940296 : cls->in_worklist = true;
3173 2940296 : worklist.insert (cls->referenced_by_count, cls);
3174 : }
3175 :
3176 : /* Pops a class from worklist. */
3177 :
3178 : congruence_class *
3179 3184451 : sem_item_optimizer::worklist_pop (void)
3180 : {
3181 3184451 : congruence_class *cls;
3182 :
3183 3195340 : while (!worklist.empty ())
3184 : {
3185 2940296 : cls = worklist.extract_min ();
3186 2940296 : if (cls->in_worklist)
3187 : {
3188 2929407 : cls->in_worklist = false;
3189 :
3190 2929407 : 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 10889 : delete cls;
3198 : }
3199 : }
3200 :
3201 : return NULL;
3202 : }
3203 :
3204 : /* Iterative congruence reduction function. */
3205 :
3206 : void
3207 255044 : sem_item_optimizer::process_cong_reduction (void)
3208 : {
3209 255044 : for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3210 7684780 : it != m_classes.end (); ++it)
3211 7590250 : for (unsigned i = 0; i < (*it)->classes.length (); i++)
3212 3875382 : if ((*it)->classes[i]->is_class_used ())
3213 2914052 : worklist_push ((*it)->classes[i]);
3214 :
3215 255044 : 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 255044 : 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 3184451 : while ((cls = worklist_pop ()) != NULL)
3227 2929407 : do_congruence_step (cls);
3228 :
3229 : /* Subdivide newly created classes according to references. */
3230 255044 : unsigned new_classes = subdivide_classes_by_sensitive_refs ();
3231 :
3232 255044 : if (dump_file)
3233 364 : fprintf (dump_file, "Address reference subdivision created: %u "
3234 : "new classes.\n", new_classes);
3235 255044 : }
3236 :
3237 : /* Debug function prints all informations about congruence classes. */
3238 :
3239 : void
3240 637610 : sem_item_optimizer::dump_cong_classes (void)
3241 : {
3242 637610 : 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 11096591 : sort_sem_items_by_decl_uid (const void *a, const void *b)
3298 : {
3299 11096591 : const sem_item *i1 = *(const sem_item * const *)a;
3300 11096591 : const sem_item *i2 = *(const sem_item * const *)b;
3301 :
3302 11096591 : int uid1 = DECL_UID (i1->decl);
3303 11096591 : int uid2 = DECL_UID (i2->decl);
3304 11096591 : 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 1527637 : sort_congruence_classes_by_decl_uid (const void *a, const void *b)
3311 : {
3312 1527637 : const congruence_class *c1 = *(const congruence_class * const *)a;
3313 1527637 : const congruence_class *c2 = *(const congruence_class * const *)b;
3314 :
3315 1527637 : int uid1 = DECL_UID (c1->members[0]->decl);
3316 1527637 : int uid2 = DECL_UID (c2->members[0]->decl);
3317 1527637 : 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 71562477 : sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
3325 : {
3326 71562477 : const std::pair<congruence_class_group *, int> *g1
3327 : = (const std::pair<congruence_class_group *, int> *) a;
3328 71562477 : const std::pair<congruence_class_group *, int> *g2
3329 : = (const std::pair<congruence_class_group *, int> *) b;
3330 71562477 : 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 127522 : sem_item_optimizer::merge_classes (unsigned int prev_class_count,
3341 : unsigned int loaded_symbols)
3342 : {
3343 127522 : unsigned int item_count = m_items.length ();
3344 127522 : unsigned int class_count = m_classes_count;
3345 127522 : unsigned int equal_items = item_count - class_count;
3346 :
3347 127522 : unsigned int non_singular_classes_count = 0;
3348 127522 : unsigned int non_singular_classes_sum = 0;
3349 :
3350 127522 : 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 127522 : for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3357 3842390 : it != m_classes.end (); ++it)
3358 : {
3359 3810781 : for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3360 : {
3361 1953347 : congruence_class *c = (*it)->classes[i];
3362 3906694 : c->members.qsort (sort_sem_items_by_decl_uid);
3363 : }
3364 :
3365 3714868 : (*it)->classes.qsort (sort_congruence_classes_by_decl_uid);
3366 : }
3367 :
3368 127522 : for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3369 3842390 : it != m_classes.end (); ++it)
3370 3810781 : for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3371 : {
3372 1953347 : congruence_class *c = (*it)->classes[i];
3373 2080044 : if (c->members.length () > 1)
3374 : {
3375 126697 : non_singular_classes_count++;
3376 126697 : non_singular_classes_sum += c->members.length ();
3377 : }
3378 : }
3379 :
3380 127522 : auto_vec<std::pair<congruence_class_group *, int> > classes (
3381 127522 : m_classes.elements ());
3382 127522 : for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3383 3842390 : it != m_classes.end (); ++it)
3384 : {
3385 1857434 : int uid = DECL_UID ((*it)->classes[0]->members[0]->decl);
3386 1857434 : classes.quick_push (std::pair<congruence_class_group *, int> (*it, uid));
3387 : }
3388 :
3389 127522 : classes.qsort (sort_congruence_class_groups_by_decl_uid);
3390 :
3391 127522 : 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 3842390 : FOR_EACH_VEC_ELT (classes, l, it)
3413 3810781 : for (unsigned int i = 0; i < it->first->classes.length (); i++)
3414 : {
3415 1953347 : congruence_class *c = it->first->classes[i];
3416 :
3417 1953347 : if (c->members.length () == 1)
3418 1826650 : continue;
3419 :
3420 126697 : sem_item *source = c->members[0];
3421 126697 : bool this_merged_p = false;
3422 :
3423 126697 : if (DECL_NAME (source->decl)
3424 126697 : && 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 755839 : for (unsigned int j = 0; j < c->members.length (); j++)
3430 : {
3431 629142 : sem_item *alias = c->members[j];
3432 :
3433 629142 : if (alias == source)
3434 127448 : continue;
3435 :
3436 502445 : dump_user_location_t loc
3437 502445 : = dump_user_location_t::from_function_decl (source->decl);
3438 502445 : 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 502445 : if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl))
3451 502445 : || lookup_attribute ("no_icf", DECL_ATTRIBUTES (source->decl)))
3452 : {
3453 751 : 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 751 : continue;
3458 : }
3459 :
3460 501694 : 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 501694 : if (dbg_cnt (merged_ipa_icf))
3467 : {
3468 501690 : bool merged = source->merge (alias);
3469 501690 : this_merged_p |= merged;
3470 :
3471 501690 : if (merged && alias->type == VAR)
3472 : {
3473 12277 : symtab_pair p = symtab_pair (source->node, alias->node);
3474 12277 : m_merged_variables.safe_push (p);
3475 : }
3476 : }
3477 : }
3478 :
3479 126697 : merged_p |= this_merged_p;
3480 126697 : if (this_merged_p
3481 19030 : && source->type == FUNC
3482 15196 : && (!flag_wpa || flag_checking))
3483 : {
3484 : unsigned i;
3485 : tree name;
3486 2041992 : 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 68488 : if (POINTER_TYPE_P (TREE_TYPE (name)))
3493 : {
3494 6643 : if (SSA_NAME_PTR_INFO (name))
3495 : {
3496 4253 : gcc_checking_assert (!flag_wpa);
3497 4253 : SSA_NAME_PTR_INFO (name) = NULL;
3498 : }
3499 : }
3500 61845 : else if (SSA_NAME_RANGE_INFO (name))
3501 : {
3502 4932 : gcc_checking_assert (!flag_wpa);
3503 4932 : SSA_NAME_RANGE_INFO (name) = NULL;
3504 : }
3505 : }
3506 : }
3507 : }
3508 :
3509 127522 : if (!m_merged_variables.is_empty ())
3510 1898 : fixup_points_to_sets ();
3511 :
3512 127522 : return merged_p;
3513 127522 : }
3514 :
3515 : /* Fixup points to set PT. */
3516 :
3517 : void
3518 1145311 : sem_item_optimizer::fixup_pt_set (struct pt_solution *pt)
3519 : {
3520 1145311 : if (pt->vars == NULL)
3521 1145311 : return;
3522 :
3523 : unsigned i;
3524 : symtab_pair *item;
3525 11218052 : FOR_EACH_VEC_ELT (m_merged_variables, i, item)
3526 10212420 : 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 187282 : set_alias_uids (symtab_node *n, int uid)
3534 : {
3535 187282 : ipa_ref *ref;
3536 362287 : FOR_EACH_ALIAS (n, ref)
3537 : {
3538 175005 : 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 175005 : SET_DECL_PT_UID (ref->referring->decl, uid);
3543 175005 : set_alias_uids (ref->referring, uid);
3544 : }
3545 187282 : }
3546 :
3547 : /* Fixup points to analysis info. */
3548 :
3549 : void
3550 1898 : sem_item_optimizer::fixup_points_to_sets (void)
3551 : {
3552 : /* TODO: remove in GCC 9 and trigger PTA re-creation after IPA passes. */
3553 1898 : cgraph_node *cnode;
3554 :
3555 62047 : FOR_EACH_DEFINED_FUNCTION (cnode)
3556 : {
3557 60149 : tree name;
3558 60149 : unsigned i;
3559 60149 : function *fn = DECL_STRUCT_FUNCTION (cnode->decl);
3560 60149 : if (!gimple_in_ssa_p (fn))
3561 3283 : continue;
3562 :
3563 2319317 : FOR_EACH_SSA_NAME (i, name, fn)
3564 4194454 : if (POINTER_TYPE_P (TREE_TYPE (name))
3565 2290419 : && SSA_NAME_PTR_INFO (name))
3566 341343 : fixup_pt_set (&SSA_NAME_PTR_INFO (name)->pt);
3567 56866 : fixup_pt_set (&fn->gimple_df->escaped);
3568 56866 : 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 56866 : basic_block bb;
3575 690347 : FOR_EACH_BB_FN (bb, fn)
3576 5052989 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
3577 3786027 : gsi_next (&gsi))
3578 : {
3579 4131145 : gcall *call = dyn_cast<gcall *> (gsi_stmt (gsi));
3580 345118 : if (call)
3581 : {
3582 345118 : fixup_pt_set (gimple_call_use_set (call));
3583 345118 : fixup_pt_set (gimple_call_clobber_set (call));
3584 : }
3585 : }
3586 : }
3587 :
3588 : unsigned i;
3589 : symtab_pair *item;
3590 14175 : FOR_EACH_VEC_ELT (m_merged_variables, i, item)
3591 12277 : set_alias_uids (item->first, DECL_UID (item->first->decl));
3592 1898 : }
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 3875382 : congruence_class::is_class_used (void)
3613 : {
3614 4912186 : for (unsigned int i = 0; i < members.length (); i++)
3615 3950856 : 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 124350 : ipa_icf_generate_summary (void)
3625 : {
3626 124350 : if (!optimizer)
3627 124350 : optimizer = new sem_item_optimizer ();
3628 :
3629 124350 : optimizer->register_hooks ();
3630 124350 : optimizer->parse_funcs_and_vars ();
3631 124350 : }
3632 :
3633 : /* Write pass summary for IPA ICF pass. */
3634 :
3635 : static void
3636 19795 : ipa_icf_write_summary (void)
3637 : {
3638 19795 : gcc_assert (optimizer);
3639 :
3640 19795 : optimizer->write_summary ();
3641 19795 : }
3642 :
3643 : /* Read pass summary for IPA ICF pass. */
3644 :
3645 : static void
3646 12211 : ipa_icf_read_summary (void)
3647 : {
3648 12211 : if (!optimizer)
3649 12211 : optimizer = new sem_item_optimizer ();
3650 :
3651 12211 : optimizer->read_summary ();
3652 12211 : optimizer->register_hooks ();
3653 12211 : }
3654 :
3655 : /* Semantic equality execution function. */
3656 :
3657 : static unsigned int
3658 127522 : ipa_icf_driver (void)
3659 : {
3660 127522 : gcc_assert (optimizer);
3661 :
3662 127522 : bool merged_p = optimizer->execute ();
3663 :
3664 127522 : delete optimizer;
3665 127522 : optimizer = NULL;
3666 :
3667 127522 : 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 287872 : 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 287872 : NULL) /* variable_transform */
3699 287872 : {}
3700 :
3701 : /* opt_pass methods: */
3702 591225 : bool gate (function *) final override
3703 : {
3704 591225 : return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
3705 : }
3706 :
3707 127522 : unsigned int execute (function *) final override
3708 : {
3709 127522 : return ipa_icf_driver();
3710 : }
3711 : }; // class pass_ipa_icf
3712 :
3713 : } // ipa_icf namespace
3714 :
3715 : ipa_opt_pass_d *
3716 287872 : make_pass_ipa_icf (gcc::context *ctxt)
3717 : {
3718 287872 : 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 258766 : ipa_icf_cc_finalize (void)
3726 : {
3727 258766 : ipa_icf::optimizer = NULL;
3728 258766 : }
|
