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