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