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 1273246 : symbol_compare_collection::symbol_compare_collection (symtab_node *node)
107 : {
108 1273246 : m_references.create (0);
109 1273246 : m_interposables.create (0);
110 :
111 1273246 : ipa_ref *ref;
112 :
113 2278973 : if (is_a <varpool_node *> (node) && DECL_VIRTUAL_P (node->decl))
114 1273246 : return;
115 :
116 1630277 : for (unsigned i = 0; node->iterate_reference (i, ref); i++)
117 : {
118 357361 : if (ref->address_matters_p ())
119 314051 : m_references.safe_push (ref->referred);
120 :
121 357361 : if (ref->referred->get_availability () <= AVAIL_INTERPOSABLE)
122 : {
123 290905 : if (ref->address_matters_p ())
124 288280 : m_references.safe_push (ref->referred);
125 : else
126 2625 : m_interposables.safe_push (ref->referred);
127 : }
128 : }
129 :
130 1272916 : if (is_a <cgraph_node *> (node))
131 : {
132 267519 : cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
133 :
134 555216 : for (cgraph_edge *e = cnode->callees; e; e = e->next_callee)
135 287697 : if (e->callee->get_availability () <= AVAIL_INTERPOSABLE)
136 86612 : 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 31021032 : sem_usage_pair::sem_usage_pair (sem_item *_item, unsigned int _index)
143 31021032 : : item (_item), index (_index)
144 : {
145 31021032 : }
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 3314568 : sem_item::sem_item (sem_item_type _type, symtab_node *_node,
154 3314568 : bitmap_obstack *stack)
155 6629136 : : type (_type), node (_node), referenced_by_count (0), m_hash (-1),
156 3314568 : m_hash_set (false)
157 : {
158 3314568 : decl = node->decl;
159 3314568 : setup (stack);
160 3314568 : }
161 :
162 : /* Add reference to a semantic TARGET. */
163 :
164 : void
165 3945821 : sem_item::add_reference (ref_map *refs,
166 : sem_item *target)
167 : {
168 3945821 : unsigned index = reference_count++;
169 3945821 : bool existed;
170 :
171 3945821 : sem_usage_pair *pair = new sem_usage_pair (target, index);
172 3945821 : vec<sem_item *> &v = refs->get_or_insert (pair, &existed);
173 3945821 : if (existed)
174 1047610 : delete pair;
175 :
176 3945821 : v.safe_push (this);
177 3945821 : bitmap_set_bit (target->usage_index_bitmap, index);
178 3945821 : refs_set.add (target->node);
179 3945821 : ++target->referenced_by_count;
180 3945821 : }
181 :
182 : /* Initialize internal data structures. Bitmap STACK is used for
183 : bitmap memory allocation process. */
184 :
185 : void
186 3314568 : sem_item::setup (bitmap_obstack *stack)
187 : {
188 3314568 : gcc_checking_assert (node);
189 :
190 3314568 : reference_count = 0;
191 3314568 : tree_refs.create (0);
192 3314568 : usage_index_bitmap = BITMAP_ALLOC (stack);
193 3314568 : }
194 :
195 3160197 : sem_item::~sem_item ()
196 : {
197 3160197 : tree_refs.release ();
198 :
199 3160197 : BITMAP_FREE (usage_index_bitmap);
200 3160197 : }
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 431415 : 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 431415 : gcc_checking_assert (TARGET_SUPPORTS_ALIASES);
224 431415 : return true;
225 : #endif
226 : }
227 :
228 9259736 : void sem_item::set_hash (hashval_t hash)
229 : {
230 9259736 : m_hash = hash;
231 9259736 : m_hash_set = true;
232 9259736 : }
233 :
234 : hash_map<const_tree, hashval_t> sem_item::m_type_hash_cache;
235 :
236 1025110 : sem_function::sem_function (cgraph_node *node, bitmap_obstack *stack)
237 1025110 : : sem_item (FUNC, node, stack), memory_access_types (),
238 1025110 : m_alias_sets_hash (0), m_checker (NULL), m_compared_func (NULL)
239 : {
240 1025110 : bb_sizes.create (0);
241 1025110 : bb_sorted.create (0);
242 1025110 : }
243 :
244 1969078 : sem_function::~sem_function ()
245 : {
246 7385502 : for (unsigned i = 0; i < bb_sorted.length (); i++)
247 6400963 : delete (bb_sorted[i]);
248 :
249 984539 : bb_sizes.release ();
250 984539 : bb_sorted.release ();
251 1969078 : }
252 :
253 : /* Calculates hash value based on a BASIC_BLOCK. */
254 :
255 : hashval_t
256 6219148 : sem_function::get_bb_hash (const sem_bb *basic_block)
257 : {
258 6219148 : inchash::hash hstate;
259 :
260 6219148 : hstate.add_int (basic_block->nondbg_stmt_count);
261 6219148 : hstate.add_int (basic_block->edge_count);
262 :
263 6219148 : return hstate.end ();
264 : }
265 :
266 : /* References independent hash function. */
267 :
268 : hashval_t
269 10533668 : sem_function::get_hash (void)
270 : {
271 10533668 : if (!m_hash_set)
272 : {
273 948362 : inchash::hash hstate;
274 948362 : hstate.add_int (177454); /* Random number for function type. */
275 :
276 948362 : hstate.add_int (arg_count);
277 948362 : hstate.add_int (cfg_checksum);
278 948362 : hstate.add_int (gcode_hash);
279 :
280 14335020 : for (unsigned i = 0; i < bb_sorted.length (); i++)
281 6219148 : hstate.merge_hash (get_bb_hash (bb_sorted[i]));
282 :
283 7167510 : for (unsigned i = 0; i < bb_sizes.length (); i++)
284 6219148 : hstate.add_int (bb_sizes[i]);
285 :
286 : /* Add common features of declaration itself. */
287 948362 : if (DECL_FUNCTION_SPECIFIC_TARGET (decl))
288 124609 : hstate.add_hwi
289 124609 : (cl_target_option_hash
290 124609 : (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl))));
291 948362 : if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))
292 130042 : hstate.add_hwi
293 130042 : (cl_optimization_hash
294 130042 : (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl))));
295 948362 : hstate.add_flag (DECL_CXX_CONSTRUCTOR_P (decl));
296 948362 : hstate.add_flag (DECL_CXX_DESTRUCTOR_P (decl));
297 948362 : hstate.add_flag (DECL_STATIC_CHAIN (decl));
298 :
299 948362 : set_hash (hstate.end ());
300 : }
301 :
302 10533668 : 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 364852 : sem_item::compare_referenced_symbol_properties (symtab_node *used_by,
318 : symtab_node *n1,
319 : symtab_node *n2,
320 : bool address)
321 : {
322 364852 : 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 969213 : if ((!used_by || address || !is_a <cgraph_node *> (used_by)
336 245664 : || !opt_for_fn (used_by->decl, optimize_size))
337 360732 : && !opt_for_fn (n1->decl, optimize_size)
338 356853 : && n1->get_availability () > AVAIL_INTERPOSABLE
339 503882 : && (!DECL_UNINLINABLE (n1->decl) || !DECL_UNINLINABLE (n2->decl)))
340 : {
341 94768 : if (DECL_DISREGARD_INLINE_LIMITS (n1->decl)
342 47384 : != DECL_DISREGARD_INLINE_LIMITS (n2->decl))
343 0 : return return_false_with_msg
344 : ("DECL_DISREGARD_INLINE_LIMITS are different");
345 :
346 47384 : if (DECL_DECLARED_INLINE_P (n1->decl)
347 47384 : != DECL_DECLARED_INLINE_P (n2->decl))
348 335 : return return_false_with_msg ("inline attributes are different");
349 : }
350 :
351 362482 : if (DECL_IS_OPERATOR_NEW_P (n1->decl)
352 362482 : != DECL_IS_OPERATOR_NEW_P (n2->decl))
353 0 : return return_false_with_msg ("operator new flags are different");
354 :
355 362482 : if (DECL_IS_REPLACEABLE_OPERATOR (n1->decl)
356 362482 : != 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 364517 : if (is_a <varpool_node *> (n1))
364 : {
365 3826 : 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 2404 : && (!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 1791 : 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 1791 : if (!attribute_list_equal (DECL_ATTRIBUTES (n1->decl),
383 1791 : DECL_ATTRIBUTES (n2->decl)))
384 0 : return return_false_with_msg ("different var decl attributes");
385 1791 : if (comp_type_attributes (TREE_TYPE (n1->decl),
386 1791 : 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 733168 : if (used_by && is_a <varpool_node *> (used_by)
393 368316 : && DECL_VIRTUAL_P (used_by->decl))
394 : {
395 4039 : if (DECL_VIRTUAL_P (n1->decl) != DECL_VIRTUAL_P (n2->decl))
396 0 : return return_false_with_msg ("virtual flag mismatch");
397 4039 : if (DECL_VIRTUAL_P (n1->decl) && is_a <cgraph_node *> (n1)
398 6423 : && (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 5891544 : sem_item::hash_referenced_symbol_properties (symtab_node *ref,
408 : inchash::hash &hstate,
409 : bool address)
410 : {
411 5891544 : if (is_a <cgraph_node *> (ref))
412 : {
413 1618152 : if ((type != FUNC || address || !opt_for_fn (decl, optimize_size))
414 1850381 : && !opt_for_fn (ref->decl, optimize_size)
415 3737937 : && !DECL_UNINLINABLE (ref->decl))
416 : {
417 1450949 : hstate.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref->decl));
418 1450949 : hstate.add_flag (DECL_DECLARED_INLINE_P (ref->decl));
419 : }
420 1893098 : hstate.add_flag (DECL_IS_OPERATOR_NEW_P (ref->decl));
421 : }
422 3998446 : else if (is_a <varpool_node *> (ref))
423 : {
424 3998446 : hstate.add_flag (DECL_VIRTUAL_P (ref->decl));
425 3998446 : if (address)
426 2951252 : hstate.add_int (DECL_ALIGN (ref->decl));
427 : }
428 5891544 : }
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 509586 : 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 509586 : enum availability avail1, avail2;
441 :
442 509586 : if (n1 == n2)
443 : return true;
444 :
445 : /* Never match variable and function. */
446 750300 : if (is_a <varpool_node *> (n1) != is_a <varpool_node *> (n2))
447 : return false;
448 :
449 250100 : if (!compare_referenced_symbol_properties (node, n1, n2, address))
450 : return false;
451 249491 : if (address && n1->equal_address_to (n2) == 1)
452 : return true;
453 249491 : if (!address && n1->semantically_equivalent_p (n2))
454 : return true;
455 :
456 249490 : n1 = n1->ultimate_alias_target (&avail1);
457 249490 : n2 = n2->ultimate_alias_target (&avail2);
458 :
459 35943 : if (avail1 > AVAIL_INTERPOSABLE && ignored_nodes.get (n1)
460 285433 : && avail2 > AVAIL_INTERPOSABLE && ignored_nodes.get (n2))
461 : return true;
462 :
463 213652 : 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 147691 : bool sem_function::compare_edge_flags (cgraph_edge *e1, cgraph_edge *e2)
470 : {
471 147691 : 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 143214 : 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 1431775 : sem_function::param_used_p (unsigned int i)
489 : {
490 1431775 : if (ipa_node_params_sum == NULL)
491 : return true;
492 :
493 1431775 : ipa_node_params *parms_info = ipa_node_params_sum->get (get_node ());
494 :
495 1431775 : if (!parms_info || vec_safe_length (parms_info->descriptors) <= i)
496 : return true;
497 :
498 1111368 : 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 1268321 : sem_function::compatible_parm_types_p (tree parm1, tree parm2)
507 : {
508 : /* Be sure that parameters are TBAA compatible. */
509 1268321 : if (!func_checker::compatible_types_p (parm1, parm2))
510 332 : return return_false_with_msg ("parameter type is not compatible");
511 :
512 1267989 : if (POINTER_TYPE_P (parm1)
513 1267989 : && (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 1267989 : if (POINTER_TYPE_P (parm1)
518 117744 : && TREE_CODE (parm1) != TREE_CODE (parm2)
519 1267989 : && 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 1679952 : sem_function::equals_wpa (sem_item *item,
529 : hash_map <symtab_node *, sem_item *> &ignored_nodes)
530 : {
531 1679952 : gcc_assert (item->type == FUNC);
532 1679952 : cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
533 1679952 : cgraph_node *cnode2 = dyn_cast <cgraph_node *> (item->node);
534 :
535 1679952 : m_compared_func = static_cast<sem_function *> (item);
536 :
537 1679952 : if (cnode->must_remain_in_tu_name || cnode2->must_remain_in_tu_name
538 1679952 : || 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 1679949 : if (cnode->thunk != cnode2->thunk)
542 0 : return return_false_with_msg ("thunk mismatch");
543 1679949 : if (cnode->former_thunk_p () != cnode2->former_thunk_p ())
544 4 : return return_false_with_msg ("former_thunk_p mismatch");
545 :
546 1679945 : if ((cnode->thunk || cnode->former_thunk_p ())
547 1679945 : && 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 1679945 : if (DECL_FUNCTION_PERSONALITY (decl)
552 1679945 : != DECL_FUNCTION_PERSONALITY (item->decl))
553 0 : return return_false_with_msg ("function personalities are different");
554 :
555 1679945 : if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl)
556 1679945 : != 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 1679945 : 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 1679945 : if (DECL_CXX_CONSTRUCTOR_P (decl) != DECL_CXX_CONSTRUCTOR_P (item->decl))
564 344 : return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
565 :
566 1679601 : if (DECL_CXX_DESTRUCTOR_P (decl) != DECL_CXX_DESTRUCTOR_P (item->decl))
567 103 : 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 1679498 : if (flags_from_decl_or_type (decl) != flags_from_decl_or_type (item->decl))
574 114337 : 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 1565161 : if (DECL_CXX_CONSTRUCTOR_P (decl)
580 2484 : && opt_for_fn (decl, flag_devirtualize)
581 1567645 : && TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE)
582 : {
583 2451 : if (TREE_CODE (TREE_TYPE (item->decl)) != METHOD_TYPE)
584 0 : return return_false_with_msg ("DECL_CXX_CONSTRUCTOR type mismatch");
585 2451 : else if (!func_checker::compatible_polymorphic_types_p
586 2451 : (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
587 2451 : 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 1565161 : cl_target_option *tar1 = target_opts_for_fn (decl);
593 1565161 : cl_target_option *tar2 = target_opts_for_fn (item->decl);
594 :
595 1565161 : 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 1565161 : cl_optimization *opt1 = opts_for_fn (decl);
607 1565161 : cl_optimization *opt2 = opts_for_fn (item->decl);
608 :
609 1565161 : 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 1565161 : if (!func_checker::compatible_types_p
622 1565161 : (TREE_TYPE (TREE_TYPE (decl)),
623 1565161 : TREE_TYPE (TREE_TYPE (m_compared_func->decl))))
624 1032233 : return return_false_with_msg ("result types are different");
625 :
626 : /* Checking types of arguments. */
627 532928 : tree list1 = TYPE_ARG_TYPES (TREE_TYPE (decl)),
628 532928 : list2 = TYPE_ARG_TYPES (TREE_TYPE (m_compared_func->decl));
629 1685829 : for (unsigned i = 0; list1 && list2;
630 1152901 : list1 = TREE_CHAIN (list1), list2 = TREE_CHAIN (list2), i++)
631 : {
632 1360974 : tree parm1 = TREE_VALUE (list1);
633 1360974 : tree parm2 = TREE_VALUE (list2);
634 :
635 : /* This guard is here for function pointer with attributes (pr59927.c). */
636 1360974 : 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 1360974 : if (!types_compatible_p (parm1, parm2))
642 207741 : return return_false_with_msg ("parameter types are not compatible");
643 :
644 1153233 : if (!param_used_p (i))
645 48645 : continue;
646 :
647 : /* Perform additional checks for used parameters. */
648 1104588 : if (!compatible_parm_types_p (parm1, parm2))
649 : return false;
650 : }
651 :
652 324855 : if (list1 || list2)
653 5 : return return_false_with_msg ("mismatched number of parameters");
654 :
655 324850 : if (DECL_STATIC_CHAIN (decl) != DECL_STATIC_CHAIN (item->decl))
656 0 : return return_false_with_msg ("static chain mismatch");
657 :
658 355548 : 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 324850 : if (comp_type_attributes (TREE_TYPE (decl),
664 324850 : TREE_TYPE (item->decl)) != 1)
665 163 : return return_false_with_msg ("different type attributes");
666 324687 : if (!attribute_list_equal (DECL_ATTRIBUTES (decl),
667 324687 : 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 323350 : if (opt_for_fn (decl, flag_devirtualize)
673 323314 : && (TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE
674 302500 : || TREE_CODE (TREE_TYPE (item->decl)) == METHOD_TYPE)
675 20817 : && param_used_p (0)
676 338555 : && compare_polymorphic_p ())
677 : {
678 11685 : if (TREE_CODE (TREE_TYPE (decl)) != TREE_CODE (TREE_TYPE (item->decl)))
679 108 : return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
680 11577 : if (!func_checker::compatible_polymorphic_types_p
681 11577 : (TYPE_METHOD_BASETYPE (TREE_TYPE (decl)),
682 11577 : TYPE_METHOD_BASETYPE (TREE_TYPE (item->decl)), false))
683 0 : return return_false_with_msg ("THIS pointer ODR type mismatch");
684 : }
685 :
686 323242 : ipa_ref *ref = NULL, *ref2 = NULL;
687 353806 : for (unsigned i = 0; node->iterate_reference (i, ref); i++)
688 : {
689 30689 : item->node->iterate_reference (i, ref2);
690 :
691 30689 : if (ref->use != ref2->use)
692 0 : return return_false_with_msg ("reference use mismatch");
693 :
694 30689 : if (!compare_symbol_references (ignored_nodes, ref->referred,
695 : ref2->referred,
696 30689 : ref->address_matters_p ()))
697 : return false;
698 : }
699 :
700 323117 : cgraph_edge *e1 = dyn_cast <cgraph_node *> (node)->callees;
701 323117 : cgraph_edge *e2 = dyn_cast <cgraph_node *> (item->node)->callees;
702 :
703 466331 : while (e1 && e2)
704 : {
705 357164 : if (!compare_symbol_references (ignored_nodes, e1->callee,
706 357164 : e2->callee, false))
707 : return false;
708 143214 : if (!compare_edge_flags (e1, e2))
709 : return false;
710 :
711 143214 : e1 = e1->next_callee;
712 143214 : e2 = e2->next_callee;
713 : }
714 :
715 109167 : if (e1 || e2)
716 0 : return return_false_with_msg ("different number of calls");
717 :
718 109167 : e1 = dyn_cast <cgraph_node *> (node)->indirect_calls;
719 109167 : e2 = dyn_cast <cgraph_node *> (item->node)->indirect_calls;
720 :
721 113644 : 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 109167 : 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 2461730 : sem_item::update_hash_by_addr_refs (hash_map <symtab_node *,
746 : sem_item *> &m_symtab_node_map)
747 : {
748 2461730 : ipa_ref* ref;
749 2461730 : inchash::hash hstate (get_hash ());
750 :
751 6849405 : for (unsigned i = 0; node->iterate_reference (i, ref); i++)
752 : {
753 4387675 : hstate.add_int (ref->use);
754 4387675 : hash_referenced_symbol_properties (ref->referred, hstate,
755 4387675 : ref->use == IPA_REF_ADDR);
756 4387675 : if (ref->address_matters_p () || !m_symtab_node_map.get (ref->referred))
757 4234068 : hstate.add_int (ref->referred->ultimate_alias_target ()->order);
758 : }
759 :
760 2461730 : if (is_a <cgraph_node *> (node))
761 : {
762 2480853 : for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callers; e;
763 1503869 : e = e->next_caller)
764 : {
765 1503869 : sem_item **result = m_symtab_node_map.get (e->callee);
766 1503869 : hash_referenced_symbol_properties (e->callee, hstate, false);
767 1503869 : if (!result)
768 0 : hstate.add_int (e->callee->ultimate_alias_target ()->order);
769 : }
770 : }
771 :
772 2461730 : set_hash (hstate.end ());
773 2461730 : }
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 2461730 : sem_item::update_hash_by_local_refs (hash_map <symtab_node *,
781 : sem_item *> &m_symtab_node_map)
782 : {
783 2461730 : ipa_ref* ref;
784 2461730 : inchash::hash state (get_hash ());
785 :
786 6849405 : for (unsigned j = 0; node->iterate_reference (j, ref); j++)
787 : {
788 4387675 : sem_item **result = m_symtab_node_map.get (ref->referring);
789 4387675 : if (result)
790 4387675 : state.merge_hash ((*result)->get_hash ());
791 : }
792 :
793 2461730 : if (type == FUNC)
794 : {
795 4719909 : for (cgraph_edge *e = dyn_cast <cgraph_node *> (node)->callees; e;
796 3742925 : e = e->next_callee)
797 : {
798 3742925 : sem_item **result = m_symtab_node_map.get (e->caller);
799 3742925 : if (result)
800 3742925 : state.merge_hash ((*result)->get_hash ());
801 : }
802 : }
803 :
804 2461730 : global_hash = state.end ();
805 2461730 : }
806 :
807 : /* Returns true if the item equals to ITEM given as argument. */
808 :
809 : bool
810 124068 : sem_function::equals (sem_item *item,
811 : hash_map <symtab_node *, sem_item *> &)
812 : {
813 124068 : gcc_assert (item->type == FUNC);
814 124068 : bool eq = equals_private (item);
815 :
816 124068 : if (m_checker != NULL)
817 : {
818 124068 : delete m_checker;
819 124068 : m_checker = NULL;
820 : }
821 :
822 124068 : 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 124068 : return eq;
830 : }
831 :
832 : /* Processes function equality comparison. */
833 :
834 : bool
835 124068 : sem_function::equals_private (sem_item *item)
836 : {
837 124068 : if (item->type != FUNC)
838 : return false;
839 :
840 124068 : basic_block bb1, bb2;
841 124068 : edge e1, e2;
842 124068 : edge_iterator ei1, ei2;
843 124068 : bool result = true;
844 124068 : tree arg1, arg2;
845 :
846 124068 : m_compared_func = static_cast<sem_function *> (item);
847 :
848 124068 : gcc_assert (decl != item->decl);
849 :
850 248136 : if (bb_sorted.length () != m_compared_func->bb_sorted.length ()
851 124068 : || edge_count != m_compared_func->edge_count
852 248136 : || cfg_checksum != m_compared_func->cfg_checksum)
853 0 : return return_false ();
854 :
855 248136 : m_checker = new func_checker (decl, m_compared_func->decl,
856 : false,
857 248136 : opt_for_fn (m_compared_func->decl,
858 : flag_strict_aliasing),
859 : &refs_set,
860 124068 : &m_compared_func->refs_set);
861 124068 : arg1 = DECL_ARGUMENTS (decl);
862 124068 : arg2 = DECL_ARGUMENTS (m_compared_func->decl);
863 124068 : for (unsigned i = 0;
864 319638 : arg1 && arg2; arg1 = DECL_CHAIN (arg1), arg2 = DECL_CHAIN (arg2), i++)
865 : {
866 195809 : if (!types_compatible_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
867 239 : return return_false_with_msg ("argument types are not compatible");
868 195570 : if (!param_used_p (i))
869 31837 : continue;
870 : /* Perform additional checks for used parameters. */
871 163733 : if (!compatible_parm_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
872 : return false;
873 163733 : if (!m_checker->compare_decl (arg1, arg2))
874 0 : return return_false ();
875 : }
876 123829 : if (arg1 || arg2)
877 0 : return return_false_with_msg ("mismatched number of arguments");
878 :
879 123829 : if (DECL_STATIC_CHAIN (decl) != DECL_STATIC_CHAIN (m_compared_func->decl))
880 0 : return return_false_with_msg ("static chain mismatch");
881 :
882 247658 : if (!dyn_cast <cgraph_node *> (node)->has_gimple_body_p ())
883 : return true;
884 :
885 : /* Fill-up label dictionary. */
886 1405522 : for (unsigned i = 0; i < bb_sorted.length (); ++i)
887 : {
888 578932 : m_checker->parse_labels (bb_sorted[i]);
889 578932 : m_checker->parse_labels (m_compared_func->bb_sorted[i]);
890 : }
891 :
892 : /* Checking all basic blocks. */
893 518153 : for (unsigned i = 0; i < bb_sorted.length (); ++i)
894 433180 : if(!m_checker->compare_bb (bb_sorted[i], m_compared_func->bb_sorted[i]))
895 38856 : return return_false ();
896 :
897 84973 : auto_vec <int> bb_dict;
898 :
899 : /* Basic block edges check. */
900 952020 : for (unsigned i = 0; i < bb_sorted.length (); ++i)
901 : {
902 391045 : bb1 = bb_sorted[i]->bb;
903 391045 : bb2 = m_compared_func->bb_sorted[i]->bb;
904 :
905 391045 : ei2 = ei_start (bb2->preds);
906 :
907 884274 : for (ei1 = ei_start (bb1->preds); ei_cond (ei1, &e1); ei_next (&ei1))
908 : {
909 493237 : ei_cond (ei2, &e2);
910 :
911 493237 : if (e1->flags != e2->flags)
912 0 : return return_false_with_msg ("flags comparison returns false");
913 :
914 493237 : 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 493229 : 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 493229 : if (!m_checker->compare_edge (e1, e2))
921 0 : return return_false_with_msg ("edge comparison returns false");
922 :
923 493229 : ei_next (&ei2);
924 : }
925 : }
926 :
927 : /* Basic block PHI nodes comparison. */
928 475791 : for (unsigned i = 0; i < bb_sorted.length (); i++)
929 390818 : 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 84973 : }
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 51904 : set_local (cgraph_node *node, void *data)
940 : {
941 51904 : node->local = data != NULL;
942 51904 : 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 25801 : clear_decl_rtl (symtab_node *node, void *)
960 : {
961 25801 : SET_DECL_RTL (node->decl, NULL);
962 25801 : 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 16401 : redirect_all_callers (cgraph_node *n, cgraph_node *to)
970 : {
971 16401 : int nredirected = 0;
972 16401 : ipa_ref *ref;
973 16401 : cgraph_edge *e = n->callers;
974 :
975 16897 : 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 16411 : 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 16401 : return nredirected;
1012 : }
1013 :
1014 : /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1015 : be applied. */
1016 :
1017 : bool
1018 84097 : sem_function::merge (sem_item *alias_item)
1019 : {
1020 84097 : gcc_assert (alias_item->type == FUNC);
1021 :
1022 84097 : sem_function *alias_func = static_cast<sem_function *> (alias_item);
1023 :
1024 84097 : cgraph_node *original = get_node ();
1025 84097 : cgraph_node *local_original = NULL;
1026 84097 : cgraph_node *alias = alias_func->get_node ();
1027 :
1028 84097 : bool create_wrapper = false;
1029 84097 : bool create_alias = false;
1030 84097 : bool redirect_callers = false;
1031 84097 : bool remove = false;
1032 :
1033 84097 : bool original_discardable = false;
1034 84097 : bool original_discarded = false;
1035 :
1036 84097 : bool original_address_matters = original->address_matters_p ();
1037 84097 : bool alias_address_matters = alias->address_matters_p ();
1038 :
1039 84097 : AUTO_DUMP_SCOPE ("merge",
1040 : dump_user_location_t::from_function_decl (decl));
1041 :
1042 84097 : 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 83998 : if (DECL_NO_INLINE_WARNING_P (original->decl)
1051 83998 : != 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 83611 : if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
1062 83611 : || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
1063 83611 : && 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 83611 : if (!original->in_same_comdat_group_p (alias)
1073 83611 : || original->comdat_local_p ())
1074 : {
1075 12735 : 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 12735 : 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 70876 : 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 70876 : if (node->resolution != LDPR_UNKNOWN
1091 70876 : && !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 70876 : if ((original_address_matters && alias_address_matters)
1107 13500 : || (original_discardable
1108 0 : && (!DECL_COMDAT_GROUP (alias->decl)
1109 0 : || (DECL_COMDAT_GROUP (alias->decl)
1110 0 : != DECL_COMDAT_GROUP (original->decl))))
1111 13500 : || original_discarded
1112 13500 : || !sem_item::target_supports_symbol_aliases_p ()
1113 84376 : || 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 57376 : if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1121 57376 : 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 57369 : else if (DECL_COMDAT_GROUP (original->decl)
1133 0 : && DECL_COMDAT_GROUP (alias->decl)
1134 57369 : && (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 57369 : else if (DECL_STATIC_CHAIN (alias->decl)
1142 57369 : || 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 57365 : 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 56298 : else if (ipa_fn_summaries
1157 56298 : && ipa_size_summaries->get (alias) != NULL
1158 56288 : && 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 56287 : else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias->decl)))
1168 : {
1169 38044 : 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 57376 : redirect_callers
1179 57376 : = alias->get_availability () > AVAIL_INTERPOSABLE
1180 57376 : && original->get_availability () > AVAIL_INTERPOSABLE;
1181 : /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1182 : with proper properties. */
1183 57376 : if (!sem_item::compare_referenced_symbol_properties (NULL, original, alias,
1184 57376 : alias->address_taken))
1185 7 : redirect_callers = false;
1186 :
1187 57376 : 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 57354 : if (!original_discardable && !original->get_comdat_group ())
1203 : {
1204 57353 : local_original
1205 57353 : = 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 57354 : if (original->comdat_local_p ())
1218 57354 : redirect_callers = false;
1219 57354 : 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 57353 : 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 57353 : if (!create_wrapper
1236 39111 : && !alias->call_for_symbol_and_aliases (cgraph_node::has_thunk_p,
1237 : NULL, true)
1238 96464 : && !alias->can_remove_if_no_direct_calls_p ())
1239 : {
1240 39111 : 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 39111 : return false;
1245 : }
1246 : }
1247 : else
1248 : create_alias = true;
1249 :
1250 18242 : if (redirect_callers)
1251 : {
1252 16391 : int nredirected = redirect_all_callers (alias, local_original);
1253 :
1254 16391 : 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 16391 : if (alias->can_remove_if_no_direct_calls_p ()
1267 171 : && !DECL_VIRTUAL_P (alias->decl)
1268 16562 : && !alias->has_aliases_p ())
1269 : {
1270 : create_wrapper = false;
1271 : remove = true;
1272 : }
1273 : gcc_assert (!create_alias);
1274 : }
1275 15351 : else if (create_alias)
1276 : {
1277 13500 : alias->icf_merged = true;
1278 :
1279 : /* Remove the function's body. */
1280 13500 : ipa_merge_profiles (original, alias);
1281 13500 : symtab->call_cgraph_removal_hooks (alias);
1282 13500 : alias->release_body (true);
1283 13500 : alias->reset ();
1284 : /* Notice global symbol possibly produced RTL. */
1285 13500 : ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
1286 : NULL, true);
1287 :
1288 : /* Create the alias. */
1289 13500 : cgraph_node::create_alias (alias_func->decl, decl);
1290 13500 : alias->resolve_alias (original);
1291 :
1292 13500 : original->call_for_symbol_thunks_and_aliases
1293 13500 : (set_local, (void *)(size_t) original->local_p (), true);
1294 :
1295 13500 : if (dump_enabled_p ())
1296 20 : dump_printf (MSG_OPTIMIZED_LOCATIONS,
1297 : "Unified; Function alias has been created.\n");
1298 : }
1299 31742 : if (create_wrapper)
1300 : {
1301 18071 : gcc_assert (!create_alias);
1302 18071 : alias->icf_merged = true;
1303 18071 : symtab->call_cgraph_removal_hooks (alias);
1304 18071 : local_original->icf_merged = true;
1305 :
1306 : /* FIXME update local_original counts. */
1307 18071 : ipa_merge_profiles (original, alias, true);
1308 18071 : alias->create_wrapper (local_original);
1309 18071 : symtab->call_cgraph_insertion_hooks (alias);
1310 :
1311 18071 : 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 31742 : gcc_assert (alias->icf_merged || remove || redirect_callers);
1319 31742 : 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 31742 : 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 31742 : 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 1087052 : sem_function::init (ipa_icf_gimple::func_checker *checker)
1352 : {
1353 1087052 : m_checker = checker;
1354 1087052 : if (in_lto_p)
1355 65306 : get_node ()->get_untransformed_body ();
1356 :
1357 1087052 : tree fndecl = node->decl;
1358 1087052 : function *func = DECL_STRUCT_FUNCTION (fndecl);
1359 :
1360 1087052 : gcc_assert (func);
1361 1087052 : gcc_assert (SSANAMES (func));
1362 :
1363 1087052 : ssa_names_size = SSANAMES (func)->length ();
1364 :
1365 1087052 : decl = fndecl;
1366 1087052 : region_tree = func->eh->region_tree;
1367 :
1368 : /* iterating all function arguments. */
1369 1087052 : arg_count = count_formal_params (fndecl);
1370 :
1371 1087052 : edge_count = n_edges_for_fn (func);
1372 1087052 : cgraph_node *cnode = dyn_cast <cgraph_node *> (node);
1373 1087052 : if (!cnode->thunk)
1374 : {
1375 1087052 : cfg_checksum = coverage_compute_cfg_checksum (func);
1376 :
1377 1087052 : inchash::hash hstate;
1378 :
1379 1087052 : basic_block bb;
1380 7688075 : FOR_EACH_BB_FN (bb, func)
1381 : {
1382 6601023 : unsigned nondbg_stmt_count = 0;
1383 :
1384 6601023 : edge e;
1385 15379753 : for (edge_iterator ei = ei_start (bb->preds); ei_cond (ei, &e);
1386 8778730 : ei_next (&ei))
1387 8778730 : 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 6601023 : gphi_iterator si;
1394 7702440 : for (si = gsi_start_nonvirtual_phis (bb); !gsi_end_p (si);
1395 1101417 : gsi_next_nonvirtual_phi (&si))
1396 : {
1397 1101417 : hstate.add_int (GIMPLE_PHI);
1398 1101417 : gphi *phi = si.phi ();
1399 1101417 : m_checker->hash_operand (gimple_phi_result (phi), hstate, 0,
1400 : func_checker::OP_NORMAL);
1401 1101417 : hstate.add_int (gimple_phi_num_args (phi));
1402 3710027 : for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++)
1403 2608610 : m_checker->hash_operand (gimple_phi_arg_def (phi, i),
1404 : hstate, 0, func_checker::OP_NORMAL);
1405 : }
1406 :
1407 54759756 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1408 41557710 : gsi_next (&gsi))
1409 : {
1410 41557710 : gimple *stmt = gsi_stmt (gsi);
1411 :
1412 41557710 : if (gimple_code (stmt) != GIMPLE_DEBUG
1413 41557710 : && gimple_code (stmt) != GIMPLE_PREDICT)
1414 : {
1415 20750517 : hash_stmt (stmt, hstate);
1416 20750517 : nondbg_stmt_count++;
1417 : }
1418 : }
1419 :
1420 6601023 : hstate.commit_flag ();
1421 6601023 : gcode_hash = hstate.end ();
1422 6601023 : bb_sizes.safe_push (nondbg_stmt_count);
1423 :
1424 : /* Inserting basic block to hash table. */
1425 6601023 : sem_bb *semantic_bb = new sem_bb (bb, nondbg_stmt_count,
1426 6601023 : EDGE_COUNT (bb->preds)
1427 19796593 : + EDGE_COUNT (bb->succs));
1428 :
1429 6601023 : 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 1087052 : m_checker = NULL;
1439 1087052 : }
1440 :
1441 : /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1442 :
1443 : void
1444 20750517 : sem_function::hash_stmt (gimple *stmt, inchash::hash &hstate)
1445 : {
1446 20750517 : enum gimple_code code = gimple_code (stmt);
1447 :
1448 20750517 : hstate.add_int (code);
1449 :
1450 20750517 : switch (code)
1451 : {
1452 19613 : case GIMPLE_SWITCH:
1453 19613 : m_checker->hash_operand (gimple_switch_index (as_a <gswitch *> (stmt)),
1454 : hstate, 0, func_checker::OP_NORMAL);
1455 19613 : break;
1456 12786035 : case GIMPLE_ASSIGN:
1457 12786035 : hstate.add_int (gimple_assign_rhs_code (stmt));
1458 : /* fall through */
1459 20282285 : case GIMPLE_CALL:
1460 20282285 : case GIMPLE_ASM:
1461 20282285 : case GIMPLE_COND:
1462 20282285 : case GIMPLE_GOTO:
1463 20282285 : case GIMPLE_RETURN:
1464 20282285 : {
1465 20282285 : func_checker::operand_access_type_map map (5);
1466 20282285 : func_checker::classify_operands (stmt, &map);
1467 :
1468 : /* All these statements are equivalent if their operands are. */
1469 81036422 : for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1470 : {
1471 60754137 : func_checker::operand_access_type
1472 : access_type = func_checker::get_operand_access_type
1473 60754137 : (&map, gimple_op (stmt, i));
1474 60754137 : 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 60754137 : if (access_type == func_checker::OP_MEMORY
1480 7954601 : && lto_streaming_expected_p ()
1481 61072584 : && flag_strict_aliasing)
1482 : {
1483 317943 : ao_ref ref;
1484 :
1485 317943 : ao_ref_init (&ref, gimple_op (stmt, i));
1486 317943 : tree t = ao_ref_alias_ptr_type (&ref);
1487 317943 : if (!variably_modified_type_p (t, NULL_TREE))
1488 317915 : memory_access_types.safe_push (t);
1489 317943 : t = ao_ref_base_alias_ptr_type (&ref);
1490 317943 : if (!variably_modified_type_p (t, NULL_TREE))
1491 317546 : memory_access_types.safe_push (t);
1492 : }
1493 : }
1494 : /* Consider nocf_check attribute in hash as it affects code
1495 : generation. */
1496 20282285 : if (code == GIMPLE_CALL
1497 3919721 : && flag_cf_protection & CF_BRANCH)
1498 1720656 : hstate.add_flag (gimple_call_nocf_check_p (as_a <gcall *> (stmt)));
1499 20282285 : }
1500 20282285 : break;
1501 : default:
1502 : break;
1503 : }
1504 20750517 : }
1505 :
1506 :
1507 : /* Return true if polymorphic comparison must be processed. */
1508 :
1509 : bool
1510 66981 : sem_function::compare_polymorphic_p (void)
1511 : {
1512 66981 : struct cgraph_edge *e;
1513 :
1514 133962 : if (!opt_for_fn (get_node ()->decl, flag_devirtualize))
1515 : return false;
1516 133962 : 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 149227 : for (e = get_node ()->callees; e; e = e->next_callee)
1521 70808 : if (e->callee->definition
1522 70808 : && 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 1036693 : sem_function::parse (cgraph_node *node, bitmap_obstack *stack,
1532 : func_checker *checker)
1533 : {
1534 1036693 : tree fndecl = node->decl;
1535 1036693 : function *func = DECL_STRUCT_FUNCTION (fndecl);
1536 :
1537 1036693 : if (!func || (!node->has_gimple_body_p () && !node->thunk))
1538 : return NULL;
1539 :
1540 976867 : if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node->decl)) != NULL)
1541 : return NULL;
1542 :
1543 955711 : if (lookup_attribute_by_prefix ("oacc ",
1544 955711 : DECL_ATTRIBUTES (node->decl)) != NULL)
1545 : return NULL;
1546 :
1547 : /* PR ipa/70306. */
1548 955711 : if (DECL_STATIC_CONSTRUCTOR (node->decl)
1549 955711 : || DECL_STATIC_DESTRUCTOR (node->decl))
1550 : return NULL;
1551 :
1552 948367 : sem_function *f = new sem_function (node, stack);
1553 948367 : f->init (checker);
1554 :
1555 948367 : 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 390818 : sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
1563 : {
1564 390818 : gphi_iterator si1, si2;
1565 390818 : gphi *phi1, *phi2;
1566 390818 : unsigned size1, size2, i;
1567 390818 : tree t1, t2;
1568 390818 : edge e1, e2;
1569 :
1570 390818 : gcc_assert (bb1 != NULL);
1571 390818 : gcc_assert (bb2 != NULL);
1572 :
1573 390818 : si2 = gsi_start_nonvirtual_phis (bb2);
1574 413181 : for (si1 = gsi_start_nonvirtual_phis (bb1); !gsi_end_p (si1);
1575 22363 : gsi_next_nonvirtual_phi (&si1))
1576 : {
1577 22396 : if (gsi_end_p (si1) && gsi_end_p (si2))
1578 : break;
1579 :
1580 22396 : if (gsi_end_p (si1) || gsi_end_p (si2))
1581 0 : return return_false();
1582 :
1583 22396 : phi1 = si1.phi ();
1584 22396 : phi2 = si2.phi ();
1585 :
1586 22396 : tree phi_result1 = gimple_phi_result (phi1);
1587 22396 : tree phi_result2 = gimple_phi_result (phi2);
1588 :
1589 22396 : 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 22395 : size1 = gimple_phi_num_args (phi1);
1594 22395 : size2 = gimple_phi_num_args (phi2);
1595 :
1596 22395 : 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 71988 : for (i = 0; i < size1; ++i)
1602 : {
1603 49625 : t1 = gimple_phi_arg (phi1, i)->def;
1604 49625 : t2 = gimple_phi_arg (phi2, i)->def;
1605 :
1606 49625 : if (!m_checker->compare_operand (t1, t2, func_checker::OP_NORMAL))
1607 32 : return return_false ();
1608 :
1609 49593 : e1 = gimple_phi_arg_edge (phi1, i);
1610 49593 : e2 = gimple_phi_arg_edge (phi2, i);
1611 :
1612 49593 : if (!m_checker->compare_edge (e1, e2))
1613 0 : return return_false ();
1614 : }
1615 :
1616 22363 : 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 986466 : sem_function::bb_dict_test (vec<int> *bb_dict, int source, int target)
1627 : {
1628 986466 : source++;
1629 986466 : target++;
1630 :
1631 986466 : if (bb_dict->length () <= (unsigned)source)
1632 296232 : bb_dict->safe_grow_cleared (source + 1, true);
1633 :
1634 986466 : if ((*bb_dict)[source] == 0)
1635 : {
1636 313168 : (*bb_dict)[source] = target;
1637 313168 : return true;
1638 : }
1639 : else
1640 673298 : return (*bb_dict)[source] == target;
1641 : }
1642 :
1643 2289458 : sem_variable::sem_variable (varpool_node *node, bitmap_obstack *stack)
1644 2289458 : : sem_item (VAR, node, stack)
1645 : {
1646 2289458 : gcc_checking_assert (node);
1647 2289458 : gcc_checking_assert (get_node ());
1648 2289458 : }
1649 :
1650 : /* Fast equality function based on knowledge known in WPA. */
1651 :
1652 : bool
1653 438810 : sem_variable::equals_wpa (sem_item *item,
1654 : hash_map <symtab_node *, sem_item *> &ignored_nodes)
1655 : {
1656 438810 : gcc_assert (item->type == VAR);
1657 :
1658 438810 : if (node->must_remain_in_tu_name || item->node->must_remain_in_tu_name
1659 438810 : || 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 622864 : if (node->num_references () != item->node->num_references ())
1663 0 : return return_false_with_msg ("different number of references");
1664 :
1665 438810 : 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 438810 : if (DECL_VIRTUAL_P (decl) != DECL_VIRTUAL_P (item->decl))
1672 0 : return return_false_with_msg ("Virtual flag mismatch");
1673 :
1674 438810 : if (DECL_SIZE (decl) != DECL_SIZE (item->decl)
1675 438810 : && ((!DECL_SIZE (decl) || !DECL_SIZE (item->decl))
1676 14232 : || !operand_equal_p (DECL_SIZE (decl),
1677 14232 : DECL_SIZE (item->decl), OEP_ONLY_CONST)))
1678 14232 : 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 830596 : if (((DECL_SECTION_NAME (decl) && !node->implicit_section)
1683 424577 : || (DECL_SECTION_NAME (item->decl) && !item->node->implicit_section))
1684 424579 : && DECL_SECTION_NAME (decl) != DECL_SECTION_NAME (item->decl))
1685 1 : return return_false_with_msg ("user section mismatch");
1686 :
1687 424577 : if (DECL_IN_TEXT_SECTION (decl) != DECL_IN_TEXT_SECTION (item->decl))
1688 0 : return return_false_with_msg ("text section");
1689 :
1690 424577 : if (TYPE_ADDR_SPACE (TREE_TYPE (decl))
1691 424577 : != TYPE_ADDR_SPACE (TREE_TYPE (item->decl)))
1692 0 : return return_false_with_msg ("address-space");
1693 :
1694 424577 : ipa_ref *ref = NULL, *ref2 = NULL;
1695 546124 : for (unsigned i = 0; node->iterate_reference (i, ref); i++)
1696 : {
1697 121733 : item->node->iterate_reference (i, ref2);
1698 :
1699 121733 : if (ref->use != ref2->use)
1700 0 : return return_false_with_msg ("reference use mismatch");
1701 :
1702 121733 : if (!compare_symbol_references (ignored_nodes,
1703 : ref->referred, ref2->referred,
1704 121733 : 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 466541 : sem_variable::equals (sem_item *item,
1715 : hash_map <symtab_node *, sem_item *> &)
1716 : {
1717 466541 : gcc_assert (item->type == VAR);
1718 466541 : bool ret;
1719 :
1720 466541 : if (DECL_INITIAL (decl) == error_mark_node && in_lto_p)
1721 144 : dyn_cast <varpool_node *>(node)->get_constructor ();
1722 466541 : 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 466541 : if (!func_checker::compatible_types_p (TREE_TYPE (decl),
1727 466541 : TREE_TYPE (item->decl)))
1728 46090 : return return_false_with_msg ("variables types are different");
1729 :
1730 420451 : ret = sem_variable::equals (DECL_INITIAL (decl),
1731 420451 : DECL_INITIAL (item->node->decl));
1732 420451 : 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 1988463 : sem_variable::equals (tree t1, tree t2)
1745 : {
1746 2370247 : if (!t1 || !t2)
1747 2011 : return return_with_debug (t1 == t2);
1748 2368236 : if (t1 == t2)
1749 : return true;
1750 1112146 : tree_code tc1 = TREE_CODE (t1);
1751 1112146 : tree_code tc2 = TREE_CODE (t2);
1752 :
1753 1112146 : if (tc1 != tc2)
1754 0 : return return_false_with_msg ("TREE_CODE mismatch");
1755 :
1756 1112146 : switch (tc1)
1757 : {
1758 415138 : case CONSTRUCTOR:
1759 415138 : {
1760 415138 : vec<constructor_elt, va_gc> *v1, *v2;
1761 415138 : unsigned HOST_WIDE_INT idx;
1762 :
1763 415138 : enum tree_code typecode = TREE_CODE (TREE_TYPE (t1));
1764 415138 : if (typecode != TREE_CODE (TREE_TYPE (t2)))
1765 0 : return return_false_with_msg ("constructor type mismatch");
1766 :
1767 415138 : if (typecode == ARRAY_TYPE)
1768 : {
1769 166761 : HOST_WIDE_INT size_1 = int_size_in_bytes (TREE_TYPE (t1));
1770 : /* For arrays, check that the sizes all match. */
1771 166761 : if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2))
1772 166761 : || size_1 == -1
1773 333522 : || size_1 != int_size_in_bytes (TREE_TYPE (t2)))
1774 0 : return return_false_with_msg ("constructor array size mismatch");
1775 : }
1776 248377 : else if (!func_checker::compatible_types_p (TREE_TYPE (t1),
1777 248377 : TREE_TYPE (t2)))
1778 0 : return return_false_with_msg ("constructor type incompatible");
1779 :
1780 415138 : v1 = CONSTRUCTOR_ELTS (t1);
1781 415138 : v2 = CONSTRUCTOR_ELTS (t2);
1782 1122956 : if (vec_safe_length (v1) != vec_safe_length (v2))
1783 0 : return return_false_with_msg ("constructor number of elts mismatch");
1784 :
1785 1157186 : for (idx = 0; idx < vec_safe_length (v1); ++idx)
1786 : {
1787 744561 : constructor_elt *c1 = &(*v1)[idx];
1788 744561 : constructor_elt *c2 = &(*v2)[idx];
1789 :
1790 : /* Check that each value is the same... */
1791 744561 : if (!sem_variable::equals (c1->value, c2->value))
1792 : return false;
1793 : /* ... and that they apply to the same fields! */
1794 744561 : 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 381028 : case ADDR_EXPR:
1815 381028 : case FDESC_EXPR:
1816 381028 : {
1817 381028 : tree op1 = TREE_OPERAND (t1, 0);
1818 381028 : tree op2 = TREE_OPERAND (t2, 0);
1819 381028 : 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 644 : case INTEGER_CST:
1835 : /* Integer constants are the same only if the same width of type. */
1836 644 : if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1837 47 : return return_false_with_msg ("INTEGER_CST precision mismatch");
1838 597 : if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1839 0 : return return_false_with_msg ("INTEGER_CST mode mismatch");
1840 597 : return return_with_debug (tree_int_cst_equal (t1, t2));
1841 263780 : case STRING_CST:
1842 263780 : if (TYPE_MODE (TREE_TYPE (t1)) != TYPE_MODE (TREE_TYPE (t2)))
1843 0 : return return_false_with_msg ("STRING_CST mode mismatch");
1844 263780 : if (TREE_STRING_LENGTH (t1) != TREE_STRING_LENGTH (t2))
1845 0 : return return_false_with_msg ("STRING_CST length mismatch");
1846 263780 : if (memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
1847 263780 : 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 27606 : case REAL_CST:
1861 : /* Real constants are the same only if the same width of type. */
1862 27606 : if (TYPE_PRECISION (TREE_TYPE (t1)) != TYPE_PRECISION (TREE_TYPE (t2)))
1863 0 : return return_false_with_msg ("REAL_CST precision mismatch");
1864 27606 : return return_with_debug (real_identical (&TREE_REAL_CST (t1),
1865 : &TREE_REAL_CST (t2)));
1866 0 : case VECTOR_CST:
1867 0 : {
1868 0 : if (maybe_ne (VECTOR_CST_NELTS (t1), VECTOR_CST_NELTS (t2)))
1869 0 : return return_false_with_msg ("VECTOR_CST nelts mismatch");
1870 :
1871 0 : unsigned int count
1872 0 : = tree_vector_builder::binary_encoded_nelts (t1, t2);
1873 0 : for (unsigned int i = 0; i < count; ++i)
1874 0 : if (!sem_variable::equals (VECTOR_CST_ENCODED_ELT (t1, i),
1875 0 : 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 2334005 : sem_variable::parse (varpool_node *node, bitmap_obstack *stack,
1929 : func_checker *checker)
1930 : {
1931 2269756 : if (TREE_THIS_VOLATILE (node->decl) || DECL_HARD_REGISTER (node->decl)
1932 4603709 : || node->alias)
1933 : return NULL;
1934 :
1935 2269619 : sem_variable *v = new sem_variable (node, stack);
1936 2269619 : v->init (checker);
1937 :
1938 2269619 : return v;
1939 : }
1940 :
1941 : /* Semantic variable initialization function. */
1942 :
1943 : void
1944 2774461 : sem_variable::init (ipa_icf_gimple::func_checker *checker)
1945 : {
1946 2774461 : 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 2774461 : if (!m_hash_set)
1952 : {
1953 2269619 : gcc_assert (!node->lto_file_data);
1954 2269619 : inchash::hash hstate;
1955 2269619 : hstate.add_int (456346417);
1956 2269619 : checker->hash_operand (DECL_INITIAL (decl), hstate, 0);
1957 2269619 : set_hash (hstate.end ());
1958 : }
1959 2774461 : }
1960 :
1961 : /* References independent hash function. */
1962 :
1963 : hashval_t
1964 8760737 : sem_variable::get_hash (void)
1965 : {
1966 8760737 : gcc_checking_assert (m_hash_set);
1967 8760737 : 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 417915 : sem_variable::merge (sem_item *alias_item)
1975 : {
1976 417915 : gcc_assert (alias_item->type == VAR);
1977 :
1978 417915 : AUTO_DUMP_SCOPE ("merge",
1979 : dump_user_location_t::from_function_decl (decl));
1980 417915 : 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 417915 : 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 417915 : sem_variable *alias_var = static_cast<sem_variable *> (alias_item);
1997 :
1998 417915 : varpool_node *original = get_node ();
1999 417915 : varpool_node *alias = alias_var->get_node ();
2000 417915 : bool original_discardable = false;
2001 :
2002 417915 : 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 417915 : if (original->can_be_discarded_p ()
2010 417915 : || (node->resolution != LDPR_UNKNOWN
2011 416520 : && !decl_binds_to_current_def_p (node->decl)))
2012 : original_discardable = true;
2013 :
2014 417915 : 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 417915 : if (DECL_IN_CONSTANT_POOL (alias->decl)
2022 417915 : || 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 820385 : if (((DECL_SECTION_NAME (original->decl) && !original->implicit_section)
2033 417912 : || (DECL_SECTION_NAME (alias->decl) && !alias->implicit_section))
2034 417912 : && 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 417912 : if (alias_address_matters && flag_merge_constants < 2)
2045 : {
2046 405541 : if (dump_enabled_p ())
2047 1 : dump_printf (MSG_MISSED_OPTIMIZATION,
2048 : "Not unifying; address of original may be compared.\n");
2049 405541 : return false;
2050 : }
2051 :
2052 12371 : if (DECL_ALIGN (original->decl) != DECL_ALIGN (alias->decl)
2053 12371 : && (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 12357 : 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 12357 : 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 12273 : 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 12269 : gcc_assert (!original->alias);
2096 12269 : gcc_assert (!alias->alias);
2097 :
2098 12269 : alias->analyzed = false;
2099 :
2100 12269 : DECL_INITIAL (alias->decl) = NULL;
2101 12269 : ((symtab_node *)alias)->call_for_symbol_and_aliases (clear_decl_rtl,
2102 : NULL, true);
2103 12269 : alias->remove_all_references ();
2104 12269 : if (TREE_ADDRESSABLE (alias->decl))
2105 366 : original->call_for_symbol_and_aliases (set_addressable, NULL, true);
2106 :
2107 12269 : varpool_node::create_alias (alias_var->decl, decl);
2108 12269 : alias->resolve_alias (original);
2109 :
2110 12269 : if (dump_enabled_p ())
2111 17 : dump_printf (MSG_OPTIMIZED_LOCATIONS,
2112 : "Unified; Variable alias has been created.\n");
2113 :
2114 12269 : 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 136788 : sem_item_optimizer::sem_item_optimizer ()
2132 136788 : : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL),
2133 136788 : m_varpool_node_hooks (NULL), m_merged_variables (), m_references ()
2134 : {
2135 136788 : m_items.create (0);
2136 136788 : bitmap_obstack_initialize (&m_bmstack);
2137 136788 : }
2138 :
2139 127755 : sem_item_optimizer::~sem_item_optimizer ()
2140 : {
2141 2589485 : for (unsigned int i = 0; i < m_items.length (); i++)
2142 2461730 : delete m_items[i];
2143 :
2144 :
2145 1991115 : for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
2146 3854475 : it != m_classes.end (); ++it)
2147 : {
2148 3822323 : for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2149 3917926 : delete (*it)->classes[i];
2150 :
2151 1863360 : (*it)->classes.release ();
2152 1863360 : free (*it);
2153 : }
2154 :
2155 127755 : m_items.release ();
2156 :
2157 127755 : bitmap_obstack_release (&m_bmstack);
2158 127755 : m_merged_variables.release ();
2159 127755 : }
2160 :
2161 : /* Write IPA ICF summary for symbols. */
2162 :
2163 : void
2164 19770 : sem_item_optimizer::write_summary (void)
2165 : {
2166 19770 : unsigned int count = 0;
2167 :
2168 19770 : output_block *ob = create_output_block (LTO_section_ipa_icf);
2169 19770 : lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
2170 19770 : ob->symbol = NULL;
2171 :
2172 : /* Calculate number of symbols to be serialized. */
2173 19770 : for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2174 367231 : !lsei_end_p (lsei);
2175 347461 : lsei_next_in_partition (&lsei))
2176 : {
2177 347461 : symtab_node *node = dyn_cast <symtab_node *> (lsei_node (lsei));
2178 347461 : if (!node)
2179 56 : continue;
2180 :
2181 347405 : if (m_symtab_node_map.get (node))
2182 323670 : count++;
2183 : }
2184 :
2185 19770 : streamer_write_uhwi (ob, count);
2186 :
2187 : /* Process all of the symbols. */
2188 19770 : for (lto_symtab_encoder_iterator lsei = lsei_start_in_partition (encoder);
2189 367231 : !lsei_end_p (lsei);
2190 347461 : lsei_next_in_partition (&lsei))
2191 : {
2192 347461 : symtab_node *node = dyn_cast <symtab_node *> (lsei_node (lsei));
2193 347461 : if (!node)
2194 56 : continue;
2195 :
2196 347405 : sem_item **item = m_symtab_node_map.get (node);
2197 :
2198 347405 : if (item && *item)
2199 : {
2200 323670 : int node_ref = lto_symtab_encoder_encode (encoder, node);
2201 323670 : streamer_write_uhwi_stream (ob->main_stream, node_ref);
2202 :
2203 323670 : streamer_write_uhwi (ob, (*item)->get_hash ());
2204 :
2205 323670 : if ((*item)->type == FUNC)
2206 : {
2207 91668 : sem_function *fn = static_cast<sem_function *> (*item);
2208 91668 : streamer_write_uhwi (ob, fn->memory_access_types.length ());
2209 972840 : for (unsigned i = 0; i < fn->memory_access_types.length (); i++)
2210 625435 : stream_write_tree (ob, fn->memory_access_types[i], true);
2211 : }
2212 : }
2213 : }
2214 :
2215 19770 : streamer_write_char_stream (ob->main_stream, 0);
2216 19770 : produce_asm (ob);
2217 19770 : destroy_output_block (ob);
2218 19770 : }
2219 :
2220 : /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2221 : contains LEN bytes. */
2222 :
2223 : void
2224 10796 : sem_item_optimizer::read_section (lto_file_decl_data *file_data,
2225 : const char *data, size_t len)
2226 : {
2227 10796 : const lto_function_header *header
2228 : = (const lto_function_header *) data;
2229 10796 : const int cfg_offset = sizeof (lto_function_header);
2230 10796 : const int main_offset = cfg_offset + header->cfg_size;
2231 10796 : const int string_offset = main_offset + header->main_size;
2232 10796 : data_in *data_in;
2233 10796 : unsigned int i;
2234 10796 : unsigned int count;
2235 :
2236 10796 : lto_input_block ib_main ((const char *) data + main_offset, 0,
2237 10796 : header->main_size, file_data);
2238 :
2239 10796 : data_in
2240 21592 : = lto_data_in_create (file_data, (const char *) data + string_offset,
2241 10796 : header->string_size, vNULL);
2242 :
2243 10796 : count = streamer_read_uhwi (&ib_main);
2244 :
2245 107378 : for (i = 0; i < count; i++)
2246 : {
2247 96582 : unsigned int index;
2248 96582 : toplevel_node *node;
2249 96582 : lto_symtab_encoder_t encoder;
2250 :
2251 96582 : index = streamer_read_uhwi (&ib_main);
2252 96582 : encoder = file_data->symtab_node_encoder;
2253 96582 : node = lto_symtab_encoder_deref (encoder, index);
2254 :
2255 96582 : hashval_t hash = streamer_read_uhwi (&ib_main);
2256 96582 : if (symtab_node *snode = dyn_cast <symtab_node *> (node))
2257 96582 : gcc_assert (snode->definition);
2258 :
2259 96582 : if (cgraph_node *cnode = dyn_cast <cgraph_node *> (node))
2260 : {
2261 76743 : sem_function *fn = new sem_function (cnode, &m_bmstack);
2262 76743 : unsigned count = streamer_read_uhwi (&ib_main);
2263 76743 : inchash::hash hstate (0);
2264 76743 : if (flag_incremental_link == INCREMENTAL_LINK_LTO)
2265 41 : fn->memory_access_types.reserve_exact (count);
2266 609130 : for (unsigned i = 0; i < count; i++)
2267 : {
2268 532387 : tree type = stream_read_tree (&ib_main, data_in);
2269 532387 : hstate.add_int (get_deref_alias_set (type));
2270 532387 : if (flag_incremental_link == INCREMENTAL_LINK_LTO)
2271 138 : fn->memory_access_types.quick_push (type);
2272 : }
2273 76743 : fn->m_alias_sets_hash = hstate.end ();
2274 76743 : fn->set_hash (hash);
2275 76743 : m_items.safe_push (fn);
2276 : }
2277 116421 : else if (varpool_node *vnode = dyn_cast <varpool_node *> (node))
2278 : {
2279 19839 : sem_variable *var = new sem_variable (vnode, &m_bmstack);
2280 19839 : var->set_hash (hash);
2281 19839 : m_items.safe_push (var);
2282 : }
2283 : }
2284 :
2285 10796 : lto_free_section_data (file_data, LTO_section_ipa_icf, NULL, data,
2286 : len);
2287 10796 : lto_data_in_delete (data_in);
2288 10796 : }
2289 :
2290 : /* Read IPA ICF summary for symbols. */
2291 :
2292 : void
2293 12202 : sem_item_optimizer::read_summary (void)
2294 : {
2295 12202 : lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
2296 12202 : lto_file_decl_data *file_data;
2297 12202 : unsigned int j = 0;
2298 :
2299 37661 : while ((file_data = file_data_vec[j++]))
2300 : {
2301 13257 : size_t len;
2302 13257 : const char *data
2303 13257 : = lto_get_summary_section_data (file_data, LTO_section_ipa_icf, &len);
2304 13257 : if (data)
2305 10796 : read_section (file_data, data, len);
2306 : }
2307 12202 : }
2308 :
2309 : /* Register callgraph and varpool hooks. */
2310 :
2311 : void
2312 136788 : sem_item_optimizer::register_hooks (void)
2313 : {
2314 136788 : if (!m_cgraph_node_hooks)
2315 136788 : m_cgraph_node_hooks = symtab->add_cgraph_removal_hook
2316 136788 : (&sem_item_optimizer::cgraph_removal_hook, this);
2317 :
2318 136788 : if (!m_varpool_node_hooks)
2319 136788 : m_varpool_node_hooks = symtab->add_varpool_removal_hook
2320 136788 : (&sem_item_optimizer::varpool_removal_hook, this);
2321 136788 : }
2322 :
2323 : /* Unregister callgraph and varpool hooks. */
2324 :
2325 : void
2326 127755 : sem_item_optimizer::unregister_hooks (void)
2327 : {
2328 127755 : if (m_cgraph_node_hooks)
2329 127755 : symtab->remove_cgraph_removal_hook (m_cgraph_node_hooks);
2330 :
2331 127755 : if (m_varpool_node_hooks)
2332 127755 : symtab->remove_varpool_removal_hook (m_varpool_node_hooks);
2333 127755 : }
2334 :
2335 : /* Adds a CLS to hashtable associated by hash value. */
2336 :
2337 : void
2338 29572 : sem_item_optimizer::add_class (congruence_class *cls)
2339 : {
2340 29572 : gcc_assert (cls->members.length ());
2341 :
2342 29572 : congruence_class_group *group
2343 29572 : = get_group_by_hash (cls->members[0]->get_hash (),
2344 29572 : cls->members[0]->type);
2345 29572 : group->classes.safe_push (cls);
2346 29572 : }
2347 :
2348 : /* Gets a congruence class group based on given HASH value and TYPE. */
2349 :
2350 : congruence_class_group *
2351 2491302 : sem_item_optimizer::get_group_by_hash (hashval_t hash, sem_item_type type)
2352 : {
2353 2491302 : congruence_class_group *item = XNEW (congruence_class_group);
2354 2491302 : item->hash = hash;
2355 2491302 : item->type = type;
2356 :
2357 2491302 : congruence_class_group **slot = m_classes.find_slot (item, INSERT);
2358 :
2359 2491302 : if (*slot)
2360 627942 : free (item);
2361 : else
2362 : {
2363 1863360 : item->classes.create (1);
2364 1863360 : *slot = item;
2365 : }
2366 :
2367 2491302 : return *slot;
2368 : }
2369 :
2370 : /* Callgraph removal hook called for a NODE with a custom DATA. */
2371 :
2372 : void
2373 11121 : sem_item_optimizer::cgraph_removal_hook (cgraph_node *node, void *data)
2374 : {
2375 11121 : sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2376 11121 : optimizer->remove_symtab_node (node);
2377 11121 : }
2378 :
2379 : /* Varpool removal hook called for a NODE with a custom DATA. */
2380 :
2381 : void
2382 3406 : sem_item_optimizer::varpool_removal_hook (varpool_node *node, void *data)
2383 : {
2384 3406 : sem_item_optimizer *optimizer = (sem_item_optimizer *) data;
2385 3406 : optimizer->remove_symtab_node (node);
2386 3406 : }
2387 :
2388 : /* Remove symtab NODE triggered by symtab removal hooks. */
2389 :
2390 : void
2391 14527 : sem_item_optimizer::remove_symtab_node (symtab_node *node)
2392 : {
2393 14527 : gcc_assert (m_classes.is_empty ());
2394 :
2395 14527 : m_removed_items_set.add (node);
2396 14527 : }
2397 :
2398 : void
2399 698467 : sem_item_optimizer::remove_item (sem_item *item)
2400 : {
2401 698467 : if (m_symtab_node_map.get (item->node))
2402 675168 : m_symtab_node_map.remove (item->node);
2403 698467 : delete item;
2404 698467 : }
2405 :
2406 : /* Removes all callgraph and varpool nodes that are marked by symtab
2407 : as deleted. */
2408 :
2409 : void
2410 127755 : sem_item_optimizer::filter_removed_items (void)
2411 : {
2412 127755 : auto_vec <sem_item *> filtered;
2413 :
2414 3287952 : for (unsigned int i = 0; i < m_items.length(); i++)
2415 : {
2416 3160197 : sem_item *item = m_items[i];
2417 :
2418 3160197 : if (m_removed_items_set.contains (item->node))
2419 : {
2420 8851 : remove_item (item);
2421 8851 : continue;
2422 : }
2423 :
2424 3151346 : if (item->type == FUNC)
2425 : {
2426 976995 : cgraph_node *cnode = static_cast <sem_function *>(item)->get_node ();
2427 :
2428 976995 : if (in_lto_p && (cnode->alias || cnode->body_removed))
2429 11 : remove_item (item);
2430 : else
2431 976984 : filtered.safe_push (item);
2432 : }
2433 : else /* VAR. */
2434 : {
2435 2174351 : if (!flag_ipa_icf_variables)
2436 1 : remove_item (item);
2437 : else
2438 : {
2439 : /* Filter out non-readonly variables. */
2440 2174350 : tree decl = item->decl;
2441 2174350 : varpool_node *vnode = static_cast <sem_variable *>(item)->get_node ();
2442 2174350 : if (!TREE_READONLY (decl) || vnode->body_removed)
2443 689604 : remove_item (item);
2444 : else
2445 1484746 : filtered.safe_push (item);
2446 : }
2447 : }
2448 : }
2449 :
2450 : /* Clean-up of released semantic items. */
2451 :
2452 127755 : m_items.release ();
2453 2589485 : for (unsigned int i = 0; i < filtered.length(); i++)
2454 2461730 : m_items.safe_push (filtered[i]);
2455 127755 : }
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 127755 : sem_item_optimizer::execute (void)
2463 : {
2464 127755 : filter_removed_items ();
2465 127755 : unregister_hooks ();
2466 :
2467 127755 : build_graph ();
2468 127755 : update_hash_by_addr_refs ();
2469 127755 : update_hash_by_memory_access_type ();
2470 127755 : build_hash_based_classes ();
2471 :
2472 127755 : if (dump_file)
2473 182 : fprintf (dump_file, "Dump after hash based groups\n");
2474 127755 : dump_cong_classes ();
2475 :
2476 127755 : subdivide_classes_by_equality (true);
2477 :
2478 127755 : if (dump_file)
2479 182 : fprintf (dump_file, "Dump after WPA based types groups\n");
2480 :
2481 127755 : dump_cong_classes ();
2482 :
2483 127755 : process_cong_reduction ();
2484 127755 : checking_verify_classes ();
2485 :
2486 127755 : if (dump_file)
2487 182 : fprintf (dump_file, "Dump after callgraph-based congruence reduction\n");
2488 :
2489 127755 : dump_cong_classes ();
2490 :
2491 127755 : unsigned int loaded_symbols = parse_nonsingleton_classes ();
2492 127755 : subdivide_classes_by_equality ();
2493 :
2494 127755 : if (dump_file)
2495 182 : fprintf (dump_file, "Dump after full equality comparison of groups\n");
2496 :
2497 127755 : dump_cong_classes ();
2498 :
2499 127755 : unsigned int prev_class_count = m_classes_count;
2500 :
2501 127755 : process_cong_reduction ();
2502 127755 : dump_cong_classes ();
2503 127755 : checking_verify_classes ();
2504 127755 : bool merged_p = merge_classes (prev_class_count, loaded_symbols);
2505 :
2506 127755 : if (dump_file && (dump_flags & TDF_DETAILS))
2507 20 : symtab->dump (dump_file);
2508 :
2509 127755 : 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 124586 : sem_item_optimizer::parse_funcs_and_vars (void)
2517 : {
2518 124586 : cgraph_node *cnode;
2519 :
2520 : /* Create dummy func_checker for hashing purpose. */
2521 124586 : func_checker checker;
2522 :
2523 124586 : if (flag_ipa_icf_functions)
2524 1157768 : FOR_EACH_DEFINED_FUNCTION (cnode)
2525 : {
2526 1036693 : sem_function *f = sem_function::parse (cnode, &m_bmstack, &checker);
2527 1036693 : if (f)
2528 : {
2529 948367 : m_items.safe_push (f);
2530 948367 : m_symtab_node_map.put (cnode, f);
2531 : }
2532 : }
2533 :
2534 124586 : varpool_node *vnode;
2535 :
2536 124586 : if (flag_ipa_icf_variables)
2537 2458588 : FOR_EACH_DEFINED_VARIABLE (vnode)
2538 : {
2539 2334005 : sem_variable *v = sem_variable::parse (vnode, &m_bmstack, &checker);
2540 :
2541 2334005 : if (v)
2542 : {
2543 2269619 : m_items.safe_push (v);
2544 2269619 : m_symtab_node_map.put (vnode, v);
2545 : }
2546 : }
2547 124586 : }
2548 :
2549 : /* Makes pairing between a congruence class CLS and semantic ITEM. */
2550 :
2551 : void
2552 3998662 : sem_item_optimizer::add_item_to_class (congruence_class *cls, sem_item *item)
2553 : {
2554 3998662 : item->index_in_class = cls->members.length ();
2555 3998662 : cls->members.safe_push (item);
2556 3998662 : cls->referenced_by_count += item->referenced_by_count;
2557 3998662 : item->cls = cls;
2558 3998662 : }
2559 :
2560 : /* For each semantic item, append hash values of references. */
2561 :
2562 : void
2563 127755 : 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 5172035 : for (unsigned i = 0; i < m_items.length (); i++)
2568 : {
2569 2461730 : m_items[i]->update_hash_by_addr_refs (m_symtab_node_map);
2570 2461730 : if (m_items[i]->type == FUNC)
2571 : {
2572 976984 : if (TREE_CODE (TREE_TYPE (m_items[i]->decl)) == METHOD_TYPE
2573 286752 : && contains_polymorphic_type_p
2574 286752 : (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl)))
2575 1049357 : && (DECL_CXX_CONSTRUCTOR_P (m_items[i]->decl)
2576 62155 : || (static_cast<sem_function *> (m_items[i])->param_used_p (0)
2577 103552 : && static_cast<sem_function *> (m_items[i])
2578 51776 : ->compare_polymorphic_p ())))
2579 : {
2580 44729 : tree class_type
2581 44729 : = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items[i]->decl));
2582 44729 : 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 44729 : if (TYPE_NAME (class_type)
2589 44729 : && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type))
2590 45018 : && !type_in_anonymous_namespace_p
2591 289 : (class_type))
2592 285 : hstate.add_hwi
2593 285 : (IDENTIFIER_HASH_VALUE
2594 : (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type))));
2595 : else
2596 : {
2597 44444 : gcc_checking_assert
2598 : (!in_lto_p
2599 : || type_in_anonymous_namespace_p (class_type));
2600 44444 : hstate.add_hwi (TYPE_UID (TYPE_MAIN_VARIANT (class_type)));
2601 : }
2602 :
2603 44729 : 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 5172035 : for (unsigned i = 0; i < m_items.length (); i++)
2613 2461730 : m_items[i]->update_hash_by_local_refs (m_symtab_node_map);
2614 :
2615 : /* Global hash value replace current hash values. */
2616 2589485 : for (unsigned i = 0; i < m_items.length (); i++)
2617 2461730 : m_items[i]->set_hash (m_items[i]->global_hash);
2618 127755 : }
2619 :
2620 : void
2621 127755 : sem_item_optimizer::update_hash_by_memory_access_type ()
2622 : {
2623 2589485 : for (unsigned i = 0; i < m_items.length (); i++)
2624 : {
2625 2461730 : if (m_items[i]->type == FUNC)
2626 : {
2627 976984 : sem_function *fn = static_cast<sem_function *> (m_items[i]);
2628 976984 : inchash::hash hstate (fn->get_hash ());
2629 976984 : hstate.add_int (fn->m_alias_sets_hash);
2630 976984 : fn->set_hash (hstate.end ());
2631 : }
2632 : }
2633 127755 : }
2634 :
2635 : /* Congruence classes are built by hash value. */
2636 :
2637 : void
2638 127755 : sem_item_optimizer::build_hash_based_classes (void)
2639 : {
2640 2589485 : for (unsigned i = 0; i < m_items.length (); i++)
2641 : {
2642 2461730 : sem_item *item = m_items[i];
2643 :
2644 2461730 : congruence_class_group *group
2645 2461730 : = get_group_by_hash (item->get_hash (), item->type);
2646 :
2647 2461730 : if (!group->classes.length ())
2648 : {
2649 1863360 : m_classes_count++;
2650 1863360 : group->classes.safe_push (new congruence_class (class_id++));
2651 : }
2652 :
2653 2461730 : add_item_to_class (group->classes[0], item);
2654 : }
2655 127755 : }
2656 :
2657 : /* Build references according to call graph. */
2658 :
2659 : void
2660 127755 : sem_item_optimizer::build_graph (void)
2661 : {
2662 5172035 : for (unsigned i = 0; i < m_items.length (); i++)
2663 : {
2664 2461730 : sem_item *item = m_items[i];
2665 2461730 : m_symtab_node_map.put (item->node, item);
2666 :
2667 : /* Initialize hash values if we are not in LTO mode. */
2668 2461730 : if (!in_lto_p)
2669 2388554 : item->get_hash ();
2670 : }
2671 :
2672 2589485 : for (unsigned i = 0; i < m_items.length (); i++)
2673 : {
2674 2461730 : sem_item *item = m_items[i];
2675 :
2676 2461730 : if (item->type == FUNC)
2677 : {
2678 976984 : cgraph_node *cnode = dyn_cast <cgraph_node *> (item->node);
2679 :
2680 976984 : cgraph_edge *e = cnode->callees;
2681 4719909 : while (e)
2682 : {
2683 3742925 : sem_item **slot = m_symtab_node_map.get
2684 3742925 : (e->callee->ultimate_alias_target ());
2685 3742925 : if (slot)
2686 1621653 : item->add_reference (&m_references, *slot);
2687 :
2688 3742925 : e = e->next_callee;
2689 : }
2690 : }
2691 :
2692 6849405 : ipa_ref *ref = NULL;
2693 7823117 : for (unsigned i = 0; item->node->iterate_reference (i, ref); i++)
2694 : {
2695 4387675 : sem_item **slot = m_symtab_node_map.get
2696 4387675 : (ref->referred->ultimate_alias_target ());
2697 4387675 : if (slot)
2698 2324168 : item->add_reference (&m_references, *slot);
2699 : }
2700 : }
2701 127755 : }
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 127755 : sem_item_optimizer::parse_nonsingleton_classes (void)
2708 : {
2709 127755 : unsigned int counter = 0;
2710 :
2711 : /* Create dummy func_checker for hashing purpose. */
2712 127755 : func_checker checker;
2713 :
2714 2589485 : for (unsigned i = 0; i < m_items.length (); i++)
2715 3105257 : if (m_items[i]->cls->members.length () > 1)
2716 : {
2717 643527 : m_items[i]->init (&checker);
2718 643527 : ++counter;
2719 : }
2720 :
2721 127755 : 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 255510 : return counter;
2728 127755 : }
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 255510 : sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa)
2735 : {
2736 3982230 : for (hash_table <congruence_class_hash>::iterator it = m_classes.begin ();
2737 7708950 : it != m_classes.end (); ++it)
2738 : {
2739 3726720 : unsigned int class_count = (*it)->classes.length ();
2740 :
2741 7532954 : for (unsigned i = 0; i < class_count; i++)
2742 : {
2743 3806234 : congruence_class *c = (*it)->classes[i];
2744 :
2745 4069580 : if (c->members.length() > 1)
2746 : {
2747 263346 : auto_vec <sem_item *> new_vector;
2748 :
2749 263346 : sem_item *first = c->members[0];
2750 263346 : new_vector.safe_push (first);
2751 :
2752 263346 : unsigned class_split_first = (*it)->classes.length ();
2753 :
2754 1380572 : for (unsigned j = 1; j < c->members.length (); j++)
2755 : {
2756 1117226 : sem_item *item = c->members[j];
2757 :
2758 1117226 : bool equals
2759 1117226 : = in_wpa ? first->equals_wpa (item, m_symtab_node_map)
2760 1117226 : : first->equals (item, m_symtab_node_map);
2761 :
2762 1117226 : if (equals)
2763 959177 : new_vector.safe_push (item);
2764 : else
2765 : {
2766 1672962 : bool integrated = false;
2767 :
2768 1514913 : for (unsigned k = class_split_first;
2769 1672962 : k < (*it)->classes.length (); k++)
2770 : {
2771 1592145 : sem_item *x = (*it)->classes[k]->members[0];
2772 1592145 : bool equals
2773 1592145 : = in_wpa ? x->equals_wpa (item, m_symtab_node_map)
2774 1592145 : : x->equals (item, m_symtab_node_map);
2775 :
2776 1592145 : if (equals)
2777 : {
2778 77232 : integrated = true;
2779 77232 : add_item_to_class ((*it)->classes[k], item);
2780 :
2781 77232 : break;
2782 : }
2783 : }
2784 :
2785 77232 : if (!integrated)
2786 : {
2787 80817 : congruence_class *c
2788 80817 : = new congruence_class (class_id++);
2789 80817 : m_classes_count++;
2790 80817 : add_item_to_class (c, item);
2791 :
2792 80817 : (*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 263346 : c->members.release ();
2800 263346 : c->members.create (new_vector.length ());
2801 :
2802 1485869 : for (unsigned int j = 0; j < new_vector.length (); j++)
2803 1222523 : add_item_to_class (c, new_vector[j]);
2804 263346 : }
2805 : }
2806 : }
2807 :
2808 255510 : checking_verify_classes ();
2809 255510 : }
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 255510 : sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2818 : {
2819 255510 : typedef hash_map <symbol_compare_hash, vec <sem_item *> > subdivide_hash_map;
2820 :
2821 255510 : unsigned newly_created_classes = 0;
2822 :
2823 255510 : for (hash_table <congruence_class_hash>::iterator it = m_classes.begin ();
2824 7708950 : it != m_classes.end (); ++it)
2825 : {
2826 3726720 : unsigned int class_count = (*it)->classes.length ();
2827 3726720 : auto_vec<congruence_class *> new_classes;
2828 :
2829 7628557 : for (unsigned i = 0; i < class_count; i++)
2830 : {
2831 3901837 : congruence_class *c = (*it)->classes[i];
2832 :
2833 4153460 : if (c->members.length() > 1)
2834 : {
2835 251623 : subdivide_hash_map split_map;
2836 :
2837 1524869 : for (unsigned j = 0; j < c->members.length (); j++)
2838 : {
2839 1273246 : sem_item *source_node = c->members[j];
2840 :
2841 1273246 : symbol_compare_collection *collection
2842 1273246 : = new symbol_compare_collection (source_node->node);
2843 :
2844 1273246 : bool existed;
2845 1273246 : vec <sem_item *> *slot
2846 1273246 : = &split_map.get_or_insert (collection, &existed);
2847 1273246 : gcc_checking_assert (slot);
2848 :
2849 1273246 : slot->safe_push (source_node);
2850 :
2851 1273246 : if (existed)
2852 2043246 : delete collection;
2853 : }
2854 :
2855 : /* If the map contains more than one key, we have to split
2856 : the map appropriately. */
2857 251623 : 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 503246 : for (subdivide_hash_map::iterator it2 = split_map.begin ();
2888 1006492 : it2 != split_map.end (); ++it2)
2889 : {
2890 503246 : delete (*it2).first;
2891 251623 : (*it2).second.release ();
2892 : }
2893 251623 : }
2894 : }
2895 :
2896 3726720 : for (unsigned i = 0; i < new_classes.length (); i++)
2897 0 : (*it)->classes.safe_push (new_classes[i]);
2898 3726720 : }
2899 :
2900 255510 : return newly_created_classes;
2901 : }
2902 :
2903 : /* Verify congruence classes, if checking is enabled. */
2904 :
2905 : void
2906 511020 : sem_item_optimizer::checking_verify_classes (void)
2907 : {
2908 511020 : if (flag_checking)
2909 510988 : verify_classes ();
2910 511020 : }
2911 :
2912 : /* Verify congruence classes. */
2913 :
2914 : void
2915 510988 : sem_item_optimizer::verify_classes (void)
2916 : {
2917 510988 : for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
2918 15417564 : it != m_classes.end (); ++it)
2919 : {
2920 15242024 : for (unsigned int i = 0; i < (*it)->classes.length (); i++)
2921 : {
2922 7788736 : congruence_class *cls = (*it)->classes[i];
2923 :
2924 7788736 : gcc_assert (cls);
2925 7788736 : gcc_assert (cls->members.length () > 0);
2926 :
2927 17635504 : for (unsigned int j = 0; j < cls->members.length (); j++)
2928 : {
2929 9846768 : sem_item *item = cls->members[j];
2930 :
2931 9846768 : gcc_assert (item);
2932 9846768 : gcc_assert (item->cls == cls);
2933 : }
2934 : }
2935 : }
2936 510988 : }
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 152732 : sem_item_optimizer::release_split_map (congruence_class * const &,
2944 : bitmap const &b, traverse_split_pair *)
2945 : {
2946 152732 : bitmap bmp = b;
2947 :
2948 152732 : BITMAP_FREE (bmp);
2949 :
2950 152732 : 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 152732 : sem_item_optimizer::traverse_congruence_split (congruence_class * const &cls,
2959 : bitmap const &b,
2960 : traverse_split_pair *pair)
2961 : {
2962 152732 : sem_item_optimizer *optimizer = pair->optimizer;
2963 152732 : 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 152732 : unsigned popcount = bitmap_count_bits (b);
2968 :
2969 152732 : if (popcount > 0 && popcount < cls->members.length ())
2970 : {
2971 14786 : auto_vec <congruence_class *, 2> newclasses;
2972 14786 : newclasses.quick_push (new congruence_class (class_id++));
2973 14786 : newclasses.quick_push (new congruence_class (class_id++));
2974 :
2975 171146 : for (unsigned int i = 0; i < cls->members.length (); i++)
2976 : {
2977 156360 : int target = bitmap_bit_p (b, i);
2978 156360 : congruence_class *tc = newclasses[target];
2979 :
2980 156360 : add_item_to_class (tc, cls->members[i]);
2981 : }
2982 :
2983 14786 : if (flag_checking)
2984 : {
2985 44358 : for (unsigned int i = 0; i < 2; i++)
2986 29572 : gcc_assert (newclasses[i]->members.length ());
2987 : }
2988 :
2989 14786 : if (splitter_cls == cls)
2990 6 : optimizer->splitter_class_removed = true;
2991 :
2992 : /* Remove old class from worklist if presented. */
2993 14786 : bool in_worklist = cls->in_worklist;
2994 :
2995 14786 : if (in_worklist)
2996 10309 : cls->in_worklist = false;
2997 :
2998 14786 : congruence_class_group g;
2999 14786 : g.hash = cls->members[0]->get_hash ();
3000 14786 : g.type = cls->members[0]->type;
3001 :
3002 14786 : congruence_class_group *slot = optimizer->m_classes.find (&g);
3003 :
3004 134511 : for (unsigned int i = 0; i < slot->classes.length (); i++)
3005 134511 : if (slot->classes[i] == cls)
3006 : {
3007 14786 : slot->classes.ordered_remove (i);
3008 14786 : break;
3009 : }
3010 :
3011 : /* New class will be inserted and integrated to work list. */
3012 44358 : for (unsigned int i = 0; i < 2; i++)
3013 29572 : optimizer->add_class (newclasses[i]);
3014 :
3015 : /* Two classes replace one, so that increment just by one. */
3016 14786 : 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 14786 : if (in_worklist)
3021 30927 : for (unsigned int i = 0; i < 2; i++)
3022 20618 : optimizer->worklist_push (newclasses[i]);
3023 : else /* Just smaller class is inserted. */
3024 : {
3025 4477 : unsigned int smaller_index
3026 8954 : = (newclasses[0]->members.length ()
3027 4477 : < newclasses[1]->members.length ()
3028 4477 : ? 0 : 1);
3029 4477 : optimizer->worklist_push (newclasses[smaller_index]);
3030 : }
3031 :
3032 14786 : 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 14786 : if (!in_worklist)
3044 8954 : delete cls;
3045 :
3046 14786 : return true;
3047 14786 : }
3048 :
3049 : return false;
3050 : }
3051 :
3052 : /* Compare function for sorting pairs in do_congruence_step_f. */
3053 :
3054 : int
3055 1476347 : sem_item_optimizer::sort_congruence_split (const void *a_, const void *b_)
3056 : {
3057 1476347 : const std::pair<congruence_class *, bitmap> *a
3058 : = (const std::pair<congruence_class *, bitmap> *)a_;
3059 1476347 : const std::pair<congruence_class *, bitmap> *b
3060 : = (const std::pair<congruence_class *, bitmap> *)b_;
3061 1476347 : if (a->first->id < b->first->id)
3062 : return -1;
3063 696235 : else if (a->first->id > b->first->id)
3064 696235 : 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 5049680 : sem_item_optimizer::do_congruence_step_for_index (congruence_class *cls,
3073 : unsigned int index)
3074 : {
3075 5049680 : hash_map <congruence_class *, bitmap> split_map;
3076 :
3077 32124891 : for (unsigned int i = 0; i < cls->members.length (); i++)
3078 : {
3079 27075211 : sem_item *item = cls->members[i];
3080 27075211 : sem_usage_pair needle (item, index);
3081 27075211 : vec<sem_item *> *callers = m_references.get (&needle);
3082 27075211 : if (callers == NULL)
3083 21275872 : continue;
3084 :
3085 13693904 : for (unsigned int j = 0; j < callers->length (); j++)
3086 : {
3087 7894565 : sem_item *caller = (*callers)[j];
3088 7894565 : if (caller->cls->members.length () < 2)
3089 7390336 : continue;
3090 504229 : bitmap *slot = split_map.get (caller->cls);
3091 504229 : bitmap b;
3092 :
3093 504229 : if(!slot)
3094 : {
3095 152732 : b = BITMAP_ALLOC (&m_bmstack);
3096 152732 : split_map.put (caller->cls, b);
3097 : }
3098 : else
3099 351497 : b = *slot;
3100 :
3101 504229 : gcc_checking_assert (caller->cls);
3102 504229 : gcc_checking_assert (caller->index_in_class
3103 : < caller->cls->members.length ());
3104 :
3105 504229 : bitmap_set_bit (b, caller->index_in_class);
3106 : }
3107 : }
3108 :
3109 5049680 : auto_vec<std::pair<congruence_class *, bitmap> > to_split;
3110 5049680 : to_split.reserve_exact (split_map.elements ());
3111 5049680 : for (hash_map <congruence_class *, bitmap>::iterator i = split_map.begin ();
3112 5355144 : i != split_map.end (); ++i)
3113 152732 : to_split.safe_push (*i);
3114 5049680 : to_split.qsort (sort_congruence_split);
3115 :
3116 5049680 : traverse_split_pair pair;
3117 5049680 : pair.optimizer = this;
3118 5049680 : pair.cls = cls;
3119 :
3120 5049680 : splitter_class_removed = false;
3121 5049680 : bool r = false;
3122 5202412 : for (unsigned i = 0; i < to_split.length (); ++i)
3123 152732 : r |= traverse_congruence_split (to_split[i].first, to_split[i].second,
3124 : &pair);
3125 :
3126 : /* Bitmap clean-up. */
3127 5049680 : split_map.traverse <traverse_split_pair *,
3128 5202412 : sem_item_optimizer::release_split_map> (NULL);
3129 :
3130 5049680 : return r;
3131 5049680 : }
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 2938109 : sem_item_optimizer::do_congruence_step (congruence_class *cls)
3139 : {
3140 2938109 : bitmap_iterator bi;
3141 2938109 : unsigned int i;
3142 :
3143 2938109 : bitmap usage = BITMAP_ALLOC (&m_bmstack);
3144 :
3145 6827260 : for (unsigned int i = 0; i < cls->members.length (); i++)
3146 3889151 : bitmap_ior_into (usage, cls->members[i]->usage_index_bitmap);
3147 :
3148 7987783 : EXECUTE_IF_SET_IN_BITMAP (usage, 0, i, bi)
3149 : {
3150 5049680 : 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 5049680 : do_congruence_step_for_index (cls, i);
3155 :
3156 5049680 : if (splitter_class_removed)
3157 : break;
3158 : }
3159 :
3160 2938109 : BITMAP_FREE (usage);
3161 2938109 : }
3162 :
3163 : /* Adds a newly created congruence class CLS to worklist. */
3164 :
3165 : void
3166 2948418 : sem_item_optimizer::worklist_push (congruence_class *cls)
3167 : {
3168 : /* Return if the class CLS is already presented in work list. */
3169 2948418 : if (cls->in_worklist)
3170 : return;
3171 :
3172 2948418 : cls->in_worklist = true;
3173 2948418 : worklist.insert (cls->referenced_by_count, cls);
3174 : }
3175 :
3176 : /* Pops a class from worklist. */
3177 :
3178 : congruence_class *
3179 3193619 : sem_item_optimizer::worklist_pop (void)
3180 : {
3181 3193619 : congruence_class *cls;
3182 :
3183 3203928 : while (!worklist.empty ())
3184 : {
3185 2948418 : cls = worklist.extract_min ();
3186 2948418 : if (cls->in_worklist)
3187 : {
3188 2938109 : cls->in_worklist = false;
3189 :
3190 2938109 : 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 10309 : delete cls;
3198 : }
3199 : }
3200 :
3201 : return NULL;
3202 : }
3203 :
3204 : /* Iterative congruence reduction function. */
3205 :
3206 : void
3207 255510 : sem_item_optimizer::process_cong_reduction (void)
3208 : {
3209 255510 : for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3210 7708950 : it != m_classes.end (); ++it)
3211 7613771 : for (unsigned i = 0; i < (*it)->classes.length (); i++)
3212 3887051 : if ((*it)->classes[i]->is_class_used ())
3213 2923323 : worklist_push ((*it)->classes[i]);
3214 :
3215 255510 : 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 255510 : 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 3193619 : while ((cls = worklist_pop ()) != NULL)
3227 2938109 : do_congruence_step (cls);
3228 :
3229 : /* Subdivide newly created classes according to references. */
3230 255510 : unsigned new_classes = subdivide_classes_by_sensitive_refs ();
3231 :
3232 255510 : if (dump_file)
3233 364 : fprintf (dump_file, "Address reference subdivision created: %u "
3234 : "new classes.\n", new_classes);
3235 255510 : }
3236 :
3237 : /* Debug function prints all informations about congruence classes. */
3238 :
3239 : void
3240 638775 : sem_item_optimizer::dump_cong_classes (void)
3241 : {
3242 638775 : 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 11096905 : sort_sem_items_by_decl_uid (const void *a, const void *b)
3298 : {
3299 11096905 : const sem_item *i1 = *(const sem_item * const *)a;
3300 11096905 : const sem_item *i2 = *(const sem_item * const *)b;
3301 :
3302 11096905 : int uid1 = DECL_UID (i1->decl);
3303 11096905 : int uid2 = DECL_UID (i2->decl);
3304 11096905 : 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 1520501 : sort_congruence_classes_by_decl_uid (const void *a, const void *b)
3311 : {
3312 1520501 : const congruence_class *c1 = *(const congruence_class * const *)a;
3313 1520501 : const congruence_class *c2 = *(const congruence_class * const *)b;
3314 :
3315 1520501 : int uid1 = DECL_UID (c1->members[0]->decl);
3316 1520501 : int uid2 = DECL_UID (c2->members[0]->decl);
3317 1520501 : 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 71770268 : sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
3325 : {
3326 71770268 : const std::pair<congruence_class_group *, int> *g1
3327 : = (const std::pair<congruence_class_group *, int> *) a;
3328 71770268 : const std::pair<congruence_class_group *, int> *g2
3329 : = (const std::pair<congruence_class_group *, int> *) b;
3330 71770268 : 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 127755 : sem_item_optimizer::merge_classes (unsigned int prev_class_count,
3341 : unsigned int loaded_symbols)
3342 : {
3343 127755 : unsigned int item_count = m_items.length ();
3344 127755 : unsigned int class_count = m_classes_count;
3345 127755 : unsigned int equal_items = item_count - class_count;
3346 :
3347 127755 : unsigned int non_singular_classes_count = 0;
3348 127755 : unsigned int non_singular_classes_sum = 0;
3349 :
3350 127755 : 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 127755 : for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3357 3854475 : it != m_classes.end (); ++it)
3358 : {
3359 3822323 : for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3360 : {
3361 1958963 : congruence_class *c = (*it)->classes[i];
3362 3917926 : c->members.qsort (sort_sem_items_by_decl_uid);
3363 : }
3364 :
3365 3726720 : (*it)->classes.qsort (sort_congruence_classes_by_decl_uid);
3366 : }
3367 :
3368 127755 : for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3369 3854475 : it != m_classes.end (); ++it)
3370 3822323 : for (unsigned int i = 0; i < (*it)->classes.length (); i++)
3371 : {
3372 1958963 : congruence_class *c = (*it)->classes[i];
3373 2085915 : if (c->members.length () > 1)
3374 : {
3375 126952 : non_singular_classes_count++;
3376 126952 : non_singular_classes_sum += c->members.length ();
3377 : }
3378 : }
3379 :
3380 127755 : auto_vec<std::pair<congruence_class_group *, int> > classes (
3381 127755 : m_classes.elements ());
3382 127755 : for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
3383 3854475 : it != m_classes.end (); ++it)
3384 : {
3385 1863360 : int uid = DECL_UID ((*it)->classes[0]->members[0]->decl);
3386 1863360 : classes.quick_push (std::pair<congruence_class_group *, int> (*it, uid));
3387 : }
3388 :
3389 127755 : classes.qsort (sort_congruence_class_groups_by_decl_uid);
3390 :
3391 127755 : 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 3854475 : FOR_EACH_VEC_ELT (classes, l, it)
3413 3822323 : for (unsigned int i = 0; i < it->first->classes.length (); i++)
3414 : {
3415 1958963 : congruence_class *c = it->first->classes[i];
3416 :
3417 1958963 : if (c->members.length () == 1)
3418 1832011 : continue;
3419 :
3420 126952 : sem_item *source = c->members[0];
3421 126952 : bool this_merged_p = false;
3422 :
3423 126952 : if (DECL_NAME (source->decl)
3424 126952 : && 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 756671 : for (unsigned int j = 0; j < c->members.length (); j++)
3430 : {
3431 629719 : sem_item *alias = c->members[j];
3432 :
3433 629719 : if (alias == source)
3434 127703 : continue;
3435 :
3436 502767 : dump_user_location_t loc
3437 502767 : = dump_user_location_t::from_function_decl (source->decl);
3438 502767 : 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 502767 : if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias->decl))
3451 502767 : || 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 502016 : 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 502016 : if (dbg_cnt (merged_ipa_icf))
3467 : {
3468 502012 : bool merged = source->merge (alias);
3469 502012 : this_merged_p |= merged;
3470 :
3471 502012 : if (merged && alias->type == VAR)
3472 : {
3473 12269 : symtab_pair p = symtab_pair (source->node, alias->node);
3474 12269 : m_merged_variables.safe_push (p);
3475 : }
3476 : }
3477 : }
3478 :
3479 126952 : merged_p |= this_merged_p;
3480 126952 : if (this_merged_p
3481 19096 : && source->type == FUNC
3482 15266 : && (!flag_wpa || flag_checking))
3483 : {
3484 : unsigned i;
3485 : tree name;
3486 2047766 : 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 68576 : if (POINTER_TYPE_P (TREE_TYPE (name)))
3493 : {
3494 6669 : if (SSA_NAME_PTR_INFO (name))
3495 : {
3496 4285 : gcc_checking_assert (!flag_wpa);
3497 4285 : SSA_NAME_PTR_INFO (name) = NULL;
3498 : }
3499 : }
3500 61907 : 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 127755 : if (!m_merged_variables.is_empty ())
3510 1894 : fixup_points_to_sets ();
3511 :
3512 127755 : return merged_p;
3513 127755 : }
3514 :
3515 : /* Fixup points to set PT. */
3516 :
3517 : void
3518 1145772 : sem_item_optimizer::fixup_pt_set (struct pt_solution *pt)
3519 : {
3520 1145772 : if (pt->vars == NULL)
3521 1145772 : return;
3522 :
3523 : unsigned i;
3524 : symtab_pair *item;
3525 11221235 : FOR_EACH_VEC_ELT (m_merged_variables, i, item)
3526 10214922 : 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 187258 : set_alias_uids (symtab_node *n, int uid)
3534 : {
3535 187258 : ipa_ref *ref;
3536 362247 : FOR_EACH_ALIAS (n, ref)
3537 : {
3538 174989 : 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 174989 : SET_DECL_PT_UID (ref->referring->decl, uid);
3543 174989 : set_alias_uids (ref->referring, uid);
3544 : }
3545 187258 : }
3546 :
3547 : /* Fixup points to analysis info. */
3548 :
3549 : void
3550 1894 : sem_item_optimizer::fixup_points_to_sets (void)
3551 : {
3552 : /* TODO: remove in GCC 9 and trigger PTA re-creation after IPA passes. */
3553 1894 : cgraph_node *cnode;
3554 :
3555 62105 : FOR_EACH_DEFINED_FUNCTION (cnode)
3556 : {
3557 60211 : tree name;
3558 60211 : unsigned i;
3559 60211 : function *fn = DECL_STRUCT_FUNCTION (cnode->decl);
3560 60211 : if (!gimple_in_ssa_p (fn))
3561 3283 : continue;
3562 :
3563 2313000 : FOR_EACH_SSA_NAME (i, name, fn)
3564 4181741 : if (POINTER_TYPE_P (TREE_TYPE (name))
3565 2284163 : && SSA_NAME_PTR_INFO (name))
3566 341878 : fixup_pt_set (&SSA_NAME_PTR_INFO (name)->pt);
3567 56928 : fixup_pt_set (&fn->gimple_df->escaped);
3568 56928 : 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 56928 : basic_block bb;
3575 690172 : FOR_EACH_BB_FN (bb, fn)
3576 5048642 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
3577 3782154 : gsi_next (&gsi))
3578 : {
3579 4127173 : gcall *call = dyn_cast<gcall *> (gsi_stmt (gsi));
3580 345019 : if (call)
3581 : {
3582 345019 : fixup_pt_set (gimple_call_use_set (call));
3583 345019 : fixup_pt_set (gimple_call_clobber_set (call));
3584 : }
3585 : }
3586 : }
3587 :
3588 : unsigned i;
3589 : symtab_pair *item;
3590 14163 : FOR_EACH_VEC_ELT (m_merged_variables, i, item)
3591 12269 : set_alias_uids (item->first, DECL_UID (item->first->decl));
3592 1894 : }
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 3887051 : congruence_class::is_class_used (void)
3613 : {
3614 4926599 : for (unsigned int i = 0; i < members.length (); i++)
3615 3962871 : 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 124586 : ipa_icf_generate_summary (void)
3625 : {
3626 124586 : if (!optimizer)
3627 124586 : optimizer = new sem_item_optimizer ();
3628 :
3629 124586 : optimizer->register_hooks ();
3630 124586 : optimizer->parse_funcs_and_vars ();
3631 124586 : }
3632 :
3633 : /* Write pass summary for IPA ICF pass. */
3634 :
3635 : static void
3636 19770 : ipa_icf_write_summary (void)
3637 : {
3638 19770 : gcc_assert (optimizer);
3639 :
3640 19770 : optimizer->write_summary ();
3641 19770 : }
3642 :
3643 : /* Read pass summary for IPA ICF pass. */
3644 :
3645 : static void
3646 12202 : ipa_icf_read_summary (void)
3647 : {
3648 12202 : if (!optimizer)
3649 12202 : optimizer = new sem_item_optimizer ();
3650 :
3651 12202 : optimizer->read_summary ();
3652 12202 : optimizer->register_hooks ();
3653 12202 : }
3654 :
3655 : /* Semantic equality execution function. */
3656 :
3657 : static unsigned int
3658 127755 : ipa_icf_driver (void)
3659 : {
3660 127755 : gcc_assert (optimizer);
3661 :
3662 127755 : bool merged_p = optimizer->execute ();
3663 :
3664 127755 : delete optimizer;
3665 127755 : optimizer = NULL;
3666 :
3667 127755 : 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 285722 : 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 285722 : NULL) /* variable_transform */
3699 285722 : {}
3700 :
3701 : /* opt_pass methods: */
3702 586755 : bool gate (function *) final override
3703 : {
3704 586755 : return in_lto_p || flag_ipa_icf_variables || flag_ipa_icf_functions;
3705 : }
3706 :
3707 127755 : unsigned int execute (function *) final override
3708 : {
3709 127755 : return ipa_icf_driver();
3710 : }
3711 : }; // class pass_ipa_icf
3712 :
3713 : } // ipa_icf namespace
3714 :
3715 : ipa_opt_pass_d *
3716 285722 : make_pass_ipa_icf (gcc::context *ctxt)
3717 : {
3718 285722 : 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 256621 : ipa_icf_cc_finalize (void)
3726 : {
3727 256621 : ipa_icf::optimizer = NULL;
3728 256621 : }
|
