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