1	/* Transformations based on profile information for values.
2	Copyright (C) 2003-2023 Free Software Foundation, Inc.
3
4	This file is part of GCC.
5
6	GCC is free software; you can redistribute it and/or modify it under
7	the terms of the GNU General Public License as published by the Free
8	Software Foundation; either version 3, or (at your option) any later
9	version.
10
11	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12	WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14	for more details.
15
16	You should have received a copy of the GNU General Public License
17	along with GCC; see the file COPYING3. If not see
18	<http://www.gnu.org/licenses/>. */
19
20	#include "config.h"
21	#include "system.h"
22	#include "coretypes.h"
23	#include "backend.h"
24	#include "rtl.h"
25	#include "tree.h"
26	#include "gimple.h"
27	#include "cfghooks.h"
28	#include "ssa.h"
29	#include "cgraph.h"
30	#include "coverage.h"
31	#include "data-streamer.h"
32	#include "diagnostic.h"
33	#include "fold-const.h"
34	#include "tree-nested.h"
35	#include "calls.h"
36	#include "expr.h"
37	#include "value-prof.h"
38	#include "tree-eh.h"
39	#include "gimplify.h"
40	#include "gimple-iterator.h"
41	#include "tree-cfg.h"
42	#include "gimple-pretty-print.h"
43	#include "dumpfile.h"
44	#include "builtins.h"
45
46	/* In this file value profile based optimizations are placed. Currently the
47	following optimizations are implemented (for more detailed descriptions
48	see comments at value_profile_transformations):
49
50	1) Division/modulo specialization. Provided that we can determine that the
51	operands of the division have some special properties, we may use it to
52	produce more effective code.
53
54	2) Indirect/virtual call specialization. If we can determine most
55	common function callee in indirect/virtual call. We can use this
56	information to improve code effectiveness (especially info for
57	the inliner).
58
59	3) Speculative prefetching. If we are able to determine that the difference
60	between addresses accessed by a memory reference is usually constant, we
61	may add the prefetch instructions.
62	FIXME: This transformation was removed together with RTL based value
63	profiling.
64
65
66	Value profiling internals
67	==========================
68
69	Every value profiling transformation starts with defining what values
70	to profile. There are different histogram types (see HIST_TYPE_* in
71	value-prof.h) and each transformation can request one or more histogram
72	types per GIMPLE statement. The function gimple_find_values_to_profile()
73	collects the values to profile in a vec, and adds the number of counters
74	required for the different histogram types.
75
76	For a -fprofile-generate run, the statements for which values should be
77	recorded, are instrumented in instrument_values(). The instrumentation
78	is done by helper functions that can be found in tree-profile.cc, where
79	new types of histograms can be added if necessary.
80
81	After a -fprofile-use, the value profiling data is read back in by
82	compute_value_histograms() that translates the collected data to
83	histograms and attaches them to the profiled statements via
84	gimple_add_histogram_value(). Histograms are stored in a hash table
85	that is attached to every intrumented function, see VALUE_HISTOGRAMS
86	in function.h.
87
88	The value-profile transformations driver is the function
89	gimple_value_profile_transformations(). It traverses all statements in
90	the to-be-transformed function, and looks for statements with one or
91	more histograms attached to it. If a statement has histograms, the
92	transformation functions are called on the statement.
93
94	Limitations / FIXME / TODO:
95	* Only one histogram of each type can be associated with a statement.
96	* Some value profile transformations are done in builtins.cc (?!)
97	* Updating of histograms needs some TLC.
98	* The value profiling code could be used to record analysis results
99	from non-profiling (e.g. VRP).
100	* Adding new profilers should be simplified, starting with a cleanup
101	of what-happens-where and with making gimple_find_values_to_profile
102	and gimple_value_profile_transformations table-driven, perhaps...
103	*/
104
105	static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *);
106	static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *);
107	static bool gimple_mod_subtract_transform (gimple_stmt_iterator *);
108	static bool gimple_stringops_transform (gimple_stmt_iterator *);
109	static void dump_ic_profile (gimple_stmt_iterator *gsi);
110
111	/* Allocate histogram value. */
112
113	histogram_value
114	gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,
115	enum hist_type type, gimple *stmt, tree value)
116	{
117	histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist));
118	hist->hvalue.value = value;
119	hist->hvalue.stmt = stmt;
120	hist->type = type;
121	return hist;
122	}
123
124	/* Hash value for histogram. */
125
126	static hashval_t
127	histogram_hash (const void *x)
128	{
129	return htab_hash_pointer (((const_histogram_value)x)->hvalue.stmt);
130	}
131
132	/* Return nonzero if statement for histogram_value X is Y. */
133
134	static int
135	histogram_eq (const void *x, const void *y)
136	{
137	return ((const_histogram_value) x)->hvalue.stmt == (const gimple *) y;
138	}
139
140	/* Set histogram for STMT. */
141
142	static void
143	set_histogram_value (struct function *fun, gimple *stmt, histogram_value hist)
144	{
145	void **loc;
146	if (!hist && !VALUE_HISTOGRAMS (fun))
147	return;
148	if (!VALUE_HISTOGRAMS (fun))
149	VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash,
150	histogram_eq, NULL);
151	loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt,
152	htab_hash_pointer (stmt),
153	hist ? INSERT : NO_INSERT);
154	if (!hist)
155	{
156	if (loc)
157	htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);
158	return;
159	}
160	*loc = hist;
161	}
162
163	/* Get histogram list for STMT. */
164
165	histogram_value
166	gimple_histogram_value (struct function *fun, gimple *stmt)
167	{
168	if (!VALUE_HISTOGRAMS (fun))
169	return NULL;
170	return (histogram_value) htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,
171	htab_hash_pointer (stmt));
172	}
173
174	/* Add histogram for STMT. */
175
176	void
177	gimple_add_histogram_value (struct function *fun, gimple *stmt,
178	histogram_value hist)
179	{
180	hist->hvalue.next = gimple_histogram_value (fun, stmt);
181	set_histogram_value (fun, stmt, hist);
182	hist->fun = fun;
183	}
184
185	/* Remove histogram HIST from STMT's histogram list. */
186
187	void
188	gimple_remove_histogram_value (struct function *fun, gimple *stmt,
189	histogram_value hist)
190	{
191	histogram_value hist2 = gimple_histogram_value (fun, stmt);
192	if (hist == hist2)
193	{
194	set_histogram_value (fun, stmt, hist: hist->hvalue.next);
195	}
196	else
197	{
198	while (hist2->hvalue.next != hist)
199	hist2 = hist2->hvalue.next;
200	hist2->hvalue.next = hist->hvalue.next;
201	}
202	free (ptr: hist->hvalue.counters);
203	if (flag_checking)
204	memset (s: hist, c: 0xab, n: sizeof (*hist));
205	free (ptr: hist);
206	}
207
208	/* Lookup histogram of type TYPE in the STMT. */
209
210	histogram_value
211	gimple_histogram_value_of_type (struct function *fun, gimple *stmt,
212	enum hist_type type)
213	{
214	histogram_value hist;
215	for (hist = gimple_histogram_value (fun, stmt); hist;
216	hist = hist->hvalue.next)
217	if (hist->type == type)
218	return hist;
219	return NULL;
220	}
221
222	/* Dump information about HIST to DUMP_FILE. */
223
224	static void
225	dump_histogram_value (FILE *dump_file, histogram_value hist)
226	{
227	switch (hist->type)
228	{
229	case HIST_TYPE_INTERVAL:
230	if (hist->hvalue.counters)
231	{
232	fprintf (stream: dump_file, format: "Interval counter range [%d,%d]: [",
233	hist->hdata.intvl.int_start,
234	(hist->hdata.intvl.int_start
235	+ hist->hdata.intvl.steps - 1));
236
237	unsigned int i;
238	for (i = 0; i < hist->hdata.intvl.steps; i++)
239	{
240	fprintf (stream: dump_file, format: "%d:%" PRId64,
241	hist->hdata.intvl.int_start + i,
242	(int64_t) hist->hvalue.counters[i]);
243	if (i != hist->hdata.intvl.steps - 1)
244	fprintf (stream: dump_file, format: ", ");
245	}
246	fprintf (stream: dump_file, format: "] outside range: %" PRId64 ".\n",
247	(int64_t) hist->hvalue.counters[i]);
248	}
249	break;
250
251	case HIST_TYPE_POW2:
252	if (hist->hvalue.counters)
253	fprintf (stream: dump_file, format: "Pow2 counter pow2:%" PRId64
254	" nonpow2:%" PRId64 ".\n",
255	(int64_t) hist->hvalue.counters[1],
256	(int64_t) hist->hvalue.counters[0]);
257	break;
258
259	case HIST_TYPE_TOPN_VALUES:
260	case HIST_TYPE_INDIR_CALL:
261	if (hist->hvalue.counters)
262	{
263	fprintf (stream: dump_file,
264	format: (hist->type == HIST_TYPE_TOPN_VALUES
265	? "Top N value counter" : "Indirect call counter"));
266	if (hist->hvalue.counters)
267	{
268	unsigned count = hist->hvalue.counters[1];
269	fprintf (stream: dump_file, format: " all: %" PRId64 ", %" PRId64 " values: ",
270	(int64_t) hist->hvalue.counters[0], (int64_t) count);
271	for (unsigned i = 0; i < count; i++)
272	{
273	fprintf (stream: dump_file, format: "[%" PRId64 ":%" PRId64 "]",
274	(int64_t) hist->hvalue.counters[2 * i + 2],
275	(int64_t) hist->hvalue.counters[2 * i + 3]);
276	if (i != count - 1)
277	fprintf (stream: dump_file, format: ", ");
278	}
279	fprintf (stream: dump_file, format: ".\n");
280	}
281	}
282	break;
283
284	case HIST_TYPE_AVERAGE:
285	if (hist->hvalue.counters)
286	fprintf (stream: dump_file, format: "Average value sum:%" PRId64
287	" times:%" PRId64 ".\n",
288	(int64_t) hist->hvalue.counters[0],
289	(int64_t) hist->hvalue.counters[1]);
290	break;
291
292	case HIST_TYPE_IOR:
293	if (hist->hvalue.counters)
294	fprintf (stream: dump_file, format: "IOR value ior:%" PRId64 ".\n",
295	(int64_t) hist->hvalue.counters[0]);
296	break;
297
298	case HIST_TYPE_TIME_PROFILE:
299	if (hist->hvalue.counters)
300	fprintf (stream: dump_file, format: "Time profile time:%" PRId64 ".\n",
301	(int64_t) hist->hvalue.counters[0]);
302	break;
303	default:
304	gcc_unreachable ();
305	}
306	}
307
308	/* Dump information about HIST to DUMP_FILE. */
309
310	void
311	stream_out_histogram_value (struct output_block *ob, histogram_value hist)
312	{
313	struct bitpack_d bp;
314	unsigned int i;
315
316	bp = bitpack_create (s: ob->main_stream);
317	bp_pack_enum (&bp, hist_type, HIST_TYPE_MAX, hist->type);
318	bp_pack_value (bp: &bp, val: hist->hvalue.next != NULL, nbits: 1);
319	streamer_write_bitpack (bp: &bp);
320	switch (hist->type)
321	{
322	case HIST_TYPE_INTERVAL:
323	streamer_write_hwi (ob, hist->hdata.intvl.int_start);
324	streamer_write_uhwi (ob, hist->hdata.intvl.steps);
325	break;
326	default:
327	break;
328	}
329	for (i = 0; i < hist->n_counters; i++)
330	{
331	/* When user uses an unsigned type with a big value, constant converted
332	to gcov_type (a signed type) can be negative. */
333	gcov_type value = hist->hvalue.counters[i];
334	streamer_write_gcov_count (ob, value);
335	}
336	if (hist->hvalue.next)
337	stream_out_histogram_value (ob, hist: hist->hvalue.next);
338	}
339
340	/* Dump information about HIST to DUMP_FILE. */
341
342	void
343	stream_in_histogram_value (class lto_input_block *ib, gimple *stmt)
344	{
345	enum hist_type type;
346	unsigned int ncounters = 0;
347	struct bitpack_d bp;
348	unsigned int i;
349	histogram_value new_val;
350	bool next;
351	histogram_value *next_p = NULL;
352
353	do
354	{
355	bp = streamer_read_bitpack (ib);
356	type = bp_unpack_enum (&bp, hist_type, HIST_TYPE_MAX);
357	next = bp_unpack_value (bp: &bp, nbits: 1);
358	new_val = gimple_alloc_histogram_value (cfun, type, stmt);
359	switch (type)
360	{
361	case HIST_TYPE_INTERVAL:
362	new_val->hdata.intvl.int_start = streamer_read_hwi (ib);
363	new_val->hdata.intvl.steps = streamer_read_uhwi (ib);
364	ncounters = new_val->hdata.intvl.steps + 2;
365	break;
366
367	case HIST_TYPE_POW2:
368	case HIST_TYPE_AVERAGE:
369	ncounters = 2;
370	break;
371
372	case HIST_TYPE_TOPN_VALUES:
373	case HIST_TYPE_INDIR_CALL:
374	break;
375
376	case HIST_TYPE_IOR:
377	case HIST_TYPE_TIME_PROFILE:
378	ncounters = 1;
379	break;
380
381	default:
382	gcc_unreachable ();
383	}
384
385	/* TOP N counters have variable number of counters. */
386	if (type == HIST_TYPE_INDIR_CALL || type == HIST_TYPE_TOPN_VALUES)
387	{
388	gcov_type total = streamer_read_gcov_count (ib);
389	gcov_type ncounters = streamer_read_gcov_count (ib);
390	new_val->hvalue.counters = XNEWVAR (gcov_type,
391	sizeof (*new_val->hvalue.counters)
392	* (2 + 2 * ncounters));
393	new_val->hvalue.counters[0] = total;
394	new_val->hvalue.counters[1] = ncounters;
395	new_val->n_counters = 2 + 2 * ncounters;
396	for (i = 0; i < 2 * ncounters; i++)
397	new_val->hvalue.counters[2 + i] = streamer_read_gcov_count (ib);
398	}
399	else
400	{
401	new_val->hvalue.counters = XNEWVAR (gcov_type,
402	sizeof (*new_val->hvalue.counters)
403	* ncounters);
404	new_val->n_counters = ncounters;
405	for (i = 0; i < ncounters; i++)
406	new_val->hvalue.counters[i] = streamer_read_gcov_count (ib);
407	}
408
409	if (!next_p)
410	gimple_add_histogram_value (cfun, stmt, hist: new_val);
411	else
412	*next_p = new_val;
413	next_p = &new_val->hvalue.next;
414	}
415	while (next);
416	}
417
418	/* Dump all histograms attached to STMT to DUMP_FILE. */
419
420	void
421	dump_histograms_for_stmt (struct function *fun, FILE *dump_file, gimple *stmt)
422	{
423	histogram_value hist;
424	for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
425	dump_histogram_value (dump_file, hist);
426	}
427
428	/* Remove all histograms associated with STMT. */
429
430	void
431	gimple_remove_stmt_histograms (struct function *fun, gimple *stmt)
432	{
433	histogram_value val;
434	while ((val = gimple_histogram_value (fun, stmt)) != NULL)
435	gimple_remove_histogram_value (fun, stmt, hist: val);
436	}
437
438	/* Duplicate all histograms associates with OSTMT to STMT. */
439
440	void
441	gimple_duplicate_stmt_histograms (struct function *fun, gimple *stmt,
442	struct function *ofun, gimple *ostmt)
443	{
444	histogram_value val;
445	for (val = gimple_histogram_value (fun: ofun, stmt: ostmt); val != NULL; val = val->hvalue.next)
446	{
447	histogram_value new_val = gimple_alloc_histogram_value (fun, type: val->type);
448	memcpy (dest: new_val, src: val, n: sizeof (*val));
449	new_val->hvalue.stmt = stmt;
450	new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
451	memcpy (dest: new_val->hvalue.counters, src: val->hvalue.counters, n: sizeof (*new_val->hvalue.counters) * new_val->n_counters);
452	gimple_add_histogram_value (fun, stmt, hist: new_val);
453	}
454	}
455
456	/* Move all histograms associated with OSTMT to STMT. */
457
458	void
459	gimple_move_stmt_histograms (struct function *fun, gimple *stmt, gimple *ostmt)
460	{
461	histogram_value val = gimple_histogram_value (fun, stmt: ostmt);
462	if (val)
463	{
464	/* The following three statements can't be reordered,
465	because histogram hashtab relies on stmt field value
466	for finding the exact slot. */
467	set_histogram_value (fun, stmt: ostmt, NULL);
468	for (; val != NULL; val = val->hvalue.next)
469	val->hvalue.stmt = stmt;
470	set_histogram_value (fun, stmt, hist: val);
471	}
472	}
473
474	static bool error_found = false;
475
476	/* Helper function for verify_histograms. For each histogram reachable via htab
477	walk verify that it was reached via statement walk. */
478
479	static int
480	visit_hist (void **slot, void *data)
481	{
482	hash_set<histogram_value> *visited = (hash_set<histogram_value> *) data;
483	histogram_value hist = *(histogram_value *) slot;
484
485	if (!visited->contains (k: hist)
486	&& hist->type != HIST_TYPE_TIME_PROFILE)
487	{
488	error ("dead histogram");
489	dump_histogram_value (stderr, hist);
490	debug_gimple_stmt (hist->hvalue.stmt);
491	error_found = true;
492	}
493	return 1;
494	}
495
496	/* Verify sanity of the histograms. */
497
498	DEBUG_FUNCTION void
499	verify_histograms (void)
500	{
501	basic_block bb;
502	gimple_stmt_iterator gsi;
503	histogram_value hist;
504
505	error_found = false;
506	hash_set<histogram_value> visited_hists;
507	FOR_EACH_BB_FN (bb, cfun)
508	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
509	{
510	gimple *stmt = gsi_stmt (i: gsi);
511
512	for (hist = gimple_histogram_value (cfun, stmt); hist;
513	hist = hist->hvalue.next)
514	{
515	if (hist->hvalue.stmt != stmt)
516	{
517	error ("histogram value statement does not correspond to "
518	"the statement it is associated with");
519	debug_gimple_stmt (stmt);
520	dump_histogram_value (stderr, hist);
521	error_found = true;
522	}
523	visited_hists.add (k: hist);
524	}
525	}
526	if (VALUE_HISTOGRAMS (cfun))
527	htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, &visited_hists);
528	if (error_found)
529	internal_error ("%qs failed", __func__);
530	}
531
532	/* Helper function for verify_histograms. For each histogram reachable via htab
533	walk verify that it was reached via statement walk. */
534
535	static int
536	free_hist (void **slot, void *data ATTRIBUTE_UNUSED)
537	{
538	histogram_value hist = *(histogram_value *) slot;
539	free (ptr: hist->hvalue.counters);
540	free (ptr: hist);
541	return 1;
542	}
543
544	void
545	free_histograms (struct function *fn)
546	{
547	if (VALUE_HISTOGRAMS (fn))
548	{
549	htab_traverse (VALUE_HISTOGRAMS (fn), free_hist, NULL);
550	htab_delete (VALUE_HISTOGRAMS (fn));
551	VALUE_HISTOGRAMS (fn) = NULL;
552	}
553	}
554
555	/* The overall number of invocations of the counter should match
556	execution count of basic block. Report it as error rather than
557	internal error as it might mean that user has misused the profile
558	somehow. */
559
560	static bool
561	check_counter (gimple *stmt, const char * name,
562	gcov_type *count, gcov_type *all, profile_count bb_count_d)
563	{
564	gcov_type bb_count = bb_count_d.ipa ().to_gcov_type ();
565	if (*all != bb_count || *count > *all)
566	{
567	dump_user_location_t locus;
568	locus = ((stmt != NULL)
569	? dump_user_location_t (stmt)
570	: dump_user_location_t::from_function_decl
571	(fndecl: current_function_decl));
572	if (flag_profile_correction)
573	{
574	if (dump_enabled_p ())
575	dump_printf_loc (MSG_MISSED_OPTIMIZATION, locus,
576	"correcting inconsistent value profile: %s "
577	"profiler overall count (%d) does not match BB "
578	"count (%d)\n", name, (int)*all, (int)bb_count);
579	*all = bb_count;
580	if (*count > *all)
581	*count = *all;
582	return false;
583	}
584	else
585	{
586	error_at (locus.get_location_t (), "corrupted value profile: %s "
587	"profile counter (%d out of %d) inconsistent with "
588	"basic-block count (%d)",
589	name,
590	(int) *count,
591	(int) *all,
592	(int) bb_count);
593	return true;
594	}
595	}
596
597	return false;
598	}
599
600	/* GIMPLE based transformations. */
601
602	bool
603	gimple_value_profile_transformations (void)
604	{
605	basic_block bb;
606	gimple_stmt_iterator gsi;
607	bool changed = false;
608
609	FOR_EACH_BB_FN (bb, cfun)
610	{
611	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
612	{
613	gimple *stmt = gsi_stmt (i: gsi);
614	histogram_value th = gimple_histogram_value (cfun, stmt);
615	if (!th)
616	continue;
617
618	if (dump_file)
619	{
620	fprintf (stream: dump_file, format: "Trying transformations on stmt ");
621	print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
622	dump_histograms_for_stmt (cfun, dump_file, stmt);
623	}
624
625	/* Transformations: */
626	/* The order of things in this conditional controls which
627	transformation is used when more than one is applicable. */
628	/* It is expected that any code added by the transformations
629	will be added before the current statement, and that the
630	current statement remain valid (although possibly
631	modified) upon return. */
632	if (gimple_mod_subtract_transform (&gsi)
633	|| gimple_divmod_fixed_value_transform (&gsi)
634	|| gimple_mod_pow2_value_transform (&gsi)
635	|| gimple_stringops_transform (&gsi))
636	{
637	stmt = gsi_stmt (i: gsi);
638	changed = true;
639	/* Original statement may no longer be in the same block. */
640	if (bb != gimple_bb (g: stmt))
641	{
642	bb = gimple_bb (g: stmt);
643	gsi = gsi_for_stmt (stmt);
644	}
645	}
646
647	/* The function never thansforms a GIMPLE statement. */
648	if (dump_enabled_p ())
649	dump_ic_profile (gsi: &gsi);
650	}
651	}
652
653	return changed;
654	}
655
656	/* Generate code for transformation 1 (with parent gimple assignment
657	STMT and probability of taking the optimal path PROB, which is
658	equivalent to COUNT/ALL within roundoff error). This generates the
659	result into a temp and returns the temp; it does not replace or
660	alter the original STMT. */
661
662	static tree
663	gimple_divmod_fixed_value (gassign *stmt, tree value, profile_probability prob,
664	gcov_type count, gcov_type all)
665	{
666	gassign *stmt1, *stmt2;
667	gcond *stmt3;
668	tree tmp0, tmp1, tmp2;
669	gimple *bb1end, *bb2end, *bb3end;
670	basic_block bb, bb2, bb3, bb4;
671	tree optype, op1, op2;
672	edge e12, e13, e23, e24, e34;
673	gimple_stmt_iterator gsi;
674
675	gcc_assert (is_gimple_assign (stmt)
676	&& (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR
677	|| gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR));
678
679	optype = TREE_TYPE (gimple_assign_lhs (stmt));
680	op1 = gimple_assign_rhs1 (gs: stmt);
681	op2 = gimple_assign_rhs2 (gs: stmt);
682
683	bb = gimple_bb (g: stmt);
684	gsi = gsi_for_stmt (stmt);
685
686	tmp0 = make_temp_ssa_name (type: optype, NULL, name: "PROF");
687	tmp1 = make_temp_ssa_name (type: optype, NULL, name: "PROF");
688	stmt1 = gimple_build_assign (tmp0, fold_convert (optype, value));
689	stmt2 = gimple_build_assign (tmp1, op2);
690	stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
691	gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
692	gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
693	gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
694	bb1end = stmt3;
695
696	tmp2 = create_tmp_reg (optype, "PROF");
697	stmt1 = gimple_build_assign (tmp2, gimple_assign_rhs_code (gs: stmt), op1, tmp0);
698	gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
699	bb2end = stmt1;
700
701	stmt1 = gimple_build_assign (tmp2, gimple_assign_rhs_code (gs: stmt), op1, op2);
702	gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
703	bb3end = stmt1;
704
705	/* Fix CFG. */
706	/* Edge e23 connects bb2 to bb3, etc. */
707	e12 = split_block (bb, bb1end);
708	bb2 = e12->dest;
709	bb2->count = profile_count::from_gcov_type (v: count);
710	e23 = split_block (bb2, bb2end);
711	bb3 = e23->dest;
712	bb3->count = profile_count::from_gcov_type (v: all - count);
713	e34 = split_block (bb3, bb3end);
714	bb4 = e34->dest;
715	bb4->count = profile_count::from_gcov_type (v: all);
716
717	e12->flags &= ~EDGE_FALLTHRU;
718	e12->flags |= EDGE_FALSE_VALUE;
719	e12->probability = prob;
720
721	e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
722	e13->probability = prob.invert ();
723
724	remove_edge (e23);
725
726	e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
727	e24->probability = profile_probability::always ();
728
729	e34->probability = profile_probability::always ();
730
731	return tmp2;
732	}
733
734	/* Return the n-th value count of TOPN_VALUE histogram. If
735	there's a value, return true and set VALUE and COUNT
736	arguments.
737
738	Counters have the following meaning.
739
740	abs (counters[0]) is the number of executions
741	for i in 0 ... TOPN-1
742	counters[2 * i + 2] is target
743	counters[2 * i + 3] is corresponding hitrate counter.
744
745	Value of counters[0] negative when counter became
746	full during merging and some values are lost. */
747
748	bool
749	get_nth_most_common_value (gimple *stmt, const char *counter_type,
750	histogram_value hist, gcov_type *value,
751	gcov_type *count, gcov_type *all, unsigned n)
752	{
753	unsigned counters = hist->hvalue.counters[1];
754	if (n >= counters)
755	return false;
756
757	*count = 0;
758	*value = 0;
759
760	gcov_type read_all = abs_hwi (x: hist->hvalue.counters[0]);
761	gcov_type covered = 0;
762	for (unsigned i = 0; i < counters; ++i)
763	covered += hist->hvalue.counters[2 * i + 3];
764
765	gcov_type v = hist->hvalue.counters[2 * n + 2];
766	gcov_type c = hist->hvalue.counters[2 * n + 3];
767
768	if (hist->hvalue.counters[0] < 0
769	&& flag_profile_reproducible == PROFILE_REPRODUCIBILITY_PARALLEL_RUNS)
770	{
771	if (dump_file)
772	fprintf (stream: dump_file, format: "Histogram value dropped in '%s' mode\n",
773	"-fprofile-reproducible=parallel-runs");
774	return false;
775	}
776	else if (covered != read_all
777	&& flag_profile_reproducible == PROFILE_REPRODUCIBILITY_MULTITHREADED)
778	{
779	if (dump_file)
780	fprintf (stream: dump_file, format: "Histogram value dropped in '%s' mode\n",
781	"-fprofile-reproducible=multithreaded");
782	return false;
783	}
784
785	/* Indirect calls can't be verified. */
786	if (stmt
787	&& check_counter (stmt, name: counter_type, count: &c, all: &read_all,
788	bb_count_d: gimple_bb (g: stmt)->count))
789	return false;
790
791	*all = read_all;
792
793	*value = v;
794	*count = c;
795	return true;
796	}
797
798	/* Do transform 1) on INSN if applicable. */
799
800	static bool
801	gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
802	{
803	histogram_value histogram;
804	enum tree_code code;
805	gcov_type val, count, all;
806	tree result, value, tree_val;
807	profile_probability prob;
808	gassign *stmt;
809
810	stmt = dyn_cast <gassign *> (p: gsi_stmt (i: *si));
811	if (!stmt)
812	return false;
813
814	if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
815	return false;
816
817	code = gimple_assign_rhs_code (gs: stmt);
818
819	if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
820	return false;
821
822	histogram = gimple_histogram_value_of_type (cfun, stmt,
823	type: HIST_TYPE_TOPN_VALUES);
824	if (!histogram)
825	return false;
826
827	if (!get_nth_most_common_value (stmt, counter_type: "divmod", hist: histogram, value: &val, count: &count,
828	all: &all))
829	return false;
830
831	value = histogram->hvalue.value;
832	gimple_remove_histogram_value (cfun, stmt, hist: histogram);
833
834	/* We require that count is at least half of all. */
835	if (simple_cst_equal (gimple_assign_rhs2 (gs: stmt), value) != 1
836	|| 2 * count < all
837	|| optimize_bb_for_size_p (gimple_bb (g: stmt)))
838	return false;
839
840	/* Compute probability of taking the optimal path. */
841	if (all > 0)
842	prob = profile_probability::probability_in_gcov_type (val1: count, val2: all);
843	else
844	prob = profile_probability::never ();
845
846	if (sizeof (gcov_type) == sizeof (HOST_WIDE_INT))
847	tree_val = build_int_cst (get_gcov_type (), val);
848	else
849	{
850	HOST_WIDE_INT a[2];
851	a[0] = (unsigned HOST_WIDE_INT) val;
852	a[1] = val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1;
853
854	tree_val = wide_int_to_tree (type: get_gcov_type (), cst: wide_int::from_array (val: a, len: 2,
855	TYPE_PRECISION (get_gcov_type ()), need_canon_p: false));
856	}
857	result = gimple_divmod_fixed_value (stmt, value: tree_val, prob, count, all);
858
859	if (dump_enabled_p ())
860	dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
861	"Transformation done: div/mod by constant %T\n", tree_val);
862
863	gimple_assign_set_rhs_from_tree (si, result);
864	update_stmt (s: gsi_stmt (i: *si));
865
866	return true;
867	}
868
869	/* Generate code for transformation 2 (with parent gimple assign STMT and
870	probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
871	within roundoff error). This generates the result into a temp and returns
872	the temp; it does not replace or alter the original STMT. */
873
874	static tree
875	gimple_mod_pow2 (gassign *stmt, profile_probability prob, gcov_type count, gcov_type all)
876	{
877	gassign *stmt1, *stmt2, *stmt3;
878	gcond *stmt4;
879	tree tmp2, tmp3;
880	gimple *bb1end, *bb2end, *bb3end;
881	basic_block bb, bb2, bb3, bb4;
882	tree optype, op1, op2;
883	edge e12, e13, e23, e24, e34;
884	gimple_stmt_iterator gsi;
885	tree result;
886
887	gcc_assert (is_gimple_assign (stmt)
888	&& gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
889
890	optype = TREE_TYPE (gimple_assign_lhs (stmt));
891	op1 = gimple_assign_rhs1 (gs: stmt);
892	op2 = gimple_assign_rhs2 (gs: stmt);
893
894	bb = gimple_bb (g: stmt);
895	gsi = gsi_for_stmt (stmt);
896
897	result = create_tmp_reg (optype, "PROF");
898	tmp2 = make_temp_ssa_name (type: optype, NULL, name: "PROF");
899	tmp3 = make_temp_ssa_name (type: optype, NULL, name: "PROF");
900	stmt2 = gimple_build_assign (tmp2, PLUS_EXPR, op2,
901	build_int_cst (optype, -1));
902	stmt3 = gimple_build_assign (tmp3, BIT_AND_EXPR, tmp2, op2);
903	stmt4 = gimple_build_cond (NE_EXPR, tmp3, build_int_cst (optype, 0),
904	NULL_TREE, NULL_TREE);
905	gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
906	gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
907	gsi_insert_before (&gsi, stmt4, GSI_SAME_STMT);
908	bb1end = stmt4;
909
910	/* tmp2 == op2-1 inherited from previous block. */
911	stmt1 = gimple_build_assign (result, BIT_AND_EXPR, op1, tmp2);
912	gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
913	bb2end = stmt1;
914
915	stmt1 = gimple_build_assign (result, gimple_assign_rhs_code (gs: stmt),
916	op1, op2);
917	gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
918	bb3end = stmt1;
919
920	/* Fix CFG. */
921	/* Edge e23 connects bb2 to bb3, etc. */
922	e12 = split_block (bb, bb1end);
923	bb2 = e12->dest;
924	bb2->count = profile_count::from_gcov_type (v: count);
925	e23 = split_block (bb2, bb2end);
926	bb3 = e23->dest;
927	bb3->count = profile_count::from_gcov_type (v: all - count);
928	e34 = split_block (bb3, bb3end);
929	bb4 = e34->dest;
930	bb4->count = profile_count::from_gcov_type (v: all);
931
932	e12->flags &= ~EDGE_FALLTHRU;
933	e12->flags |= EDGE_FALSE_VALUE;
934	e12->probability = prob;
935
936	e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
937	e13->probability = prob.invert ();
938
939	remove_edge (e23);
940
941	e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
942	e24->probability = profile_probability::always ();
943
944	e34->probability = profile_probability::always ();
945
946	return result;
947	}
948
949	/* Do transform 2) on INSN if applicable. */
950
951	static bool
952	gimple_mod_pow2_value_transform (gimple_stmt_iterator *si)
953	{
954	histogram_value histogram;
955	enum tree_code code;
956	gcov_type count, wrong_values, all;
957	tree lhs_type, result, value;
958	profile_probability prob;
959	gassign *stmt;
960
961	stmt = dyn_cast <gassign *> (p: gsi_stmt (i: *si));
962	if (!stmt)
963	return false;
964
965	lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
966	if (!INTEGRAL_TYPE_P (lhs_type))
967	return false;
968
969	code = gimple_assign_rhs_code (gs: stmt);
970
971	if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
972	return false;
973
974	histogram = gimple_histogram_value_of_type (cfun, stmt, type: HIST_TYPE_POW2);
975	if (!histogram)
976	return false;
977
978	value = histogram->hvalue.value;
979	wrong_values = histogram->hvalue.counters[0];
980	count = histogram->hvalue.counters[1];
981
982	gimple_remove_histogram_value (cfun, stmt, hist: histogram);
983
984	/* We require that we hit a power of 2 at least half of all evaluations. */
985	if (simple_cst_equal (gimple_assign_rhs2 (gs: stmt), value) != 1
986	|| count < wrong_values
987	|| optimize_bb_for_size_p (gimple_bb (g: stmt)))
988	return false;
989
990	/* Compute probability of taking the optimal path. */
991	all = count + wrong_values;
992
993	if (check_counter (stmt, name: "pow2", count: &count, all: &all, bb_count_d: gimple_bb (g: stmt)->count))
994	return false;
995
996	if (dump_enabled_p ())
997	dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
998	"Transformation done: mod power of 2\n");
999
1000	if (all > 0)
1001	prob = profile_probability::probability_in_gcov_type (val1: count, val2: all);
1002	else
1003	prob = profile_probability::never ();
1004
1005	result = gimple_mod_pow2 (stmt, prob, count, all);
1006
1007	gimple_assign_set_rhs_from_tree (si, result);
1008	update_stmt (s: gsi_stmt (i: *si));
1009
1010	return true;
1011	}
1012
1013	/* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1014	NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1015	supported and this is built into this interface. The probabilities of taking
1016	the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1017	COUNT2/ALL respectively within roundoff error). This generates the
1018	result into a temp and returns the temp; it does not replace or alter
1019	the original STMT. */
1020	/* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1021
1022	static tree
1023	gimple_mod_subtract (gassign *stmt, profile_probability prob1,
1024	profile_probability prob2, int ncounts,
1025	gcov_type count1, gcov_type count2, gcov_type all)
1026	{
1027	gassign *stmt1;
1028	gimple *stmt2;
1029	gcond *stmt3;
1030	tree tmp1;
1031	gimple *bb1end, *bb2end = NULL, *bb3end;
1032	basic_block bb, bb2, bb3, bb4;
1033	tree optype, op1, op2;
1034	edge e12, e23 = 0, e24, e34, e14;
1035	gimple_stmt_iterator gsi;
1036	tree result;
1037
1038	gcc_assert (is_gimple_assign (stmt)
1039	&& gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
1040
1041	optype = TREE_TYPE (gimple_assign_lhs (stmt));
1042	op1 = gimple_assign_rhs1 (gs: stmt);
1043	op2 = gimple_assign_rhs2 (gs: stmt);
1044
1045	bb = gimple_bb (g: stmt);
1046	gsi = gsi_for_stmt (stmt);
1047
1048	result = create_tmp_reg (optype, "PROF");
1049	tmp1 = make_temp_ssa_name (type: optype, NULL, name: "PROF");
1050	stmt1 = gimple_build_assign (result, op1);
1051	stmt2 = gimple_build_assign (tmp1, op2);
1052	stmt3 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
1053	gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1054	gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
1055	gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
1056	bb1end = stmt3;
1057
1058	if (ncounts) /* Assumed to be 0 or 1 */
1059	{
1060	stmt1 = gimple_build_assign (result, MINUS_EXPR, result, tmp1);
1061	stmt2 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
1062	gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1063	gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
1064	bb2end = stmt2;
1065	}
1066
1067	/* Fallback case. */
1068	stmt1 = gimple_build_assign (result, gimple_assign_rhs_code (gs: stmt),
1069	result, tmp1);
1070	gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1071	bb3end = stmt1;
1072
1073	/* Fix CFG. */
1074	/* Edge e23 connects bb2 to bb3, etc. */
1075	/* However block 3 is optional; if it is not there, references
1076	to 3 really refer to block 2. */
1077	e12 = split_block (bb, bb1end);
1078	bb2 = e12->dest;
1079	bb2->count = profile_count::from_gcov_type (v: all - count1);
1080
1081	if (ncounts) /* Assumed to be 0 or 1. */
1082	{
1083	e23 = split_block (bb2, bb2end);
1084	bb3 = e23->dest;
1085	bb3->count = profile_count::from_gcov_type (v: all - count1 - count2);
1086	}
1087
1088	e34 = split_block (ncounts ? bb3 : bb2, bb3end);
1089	bb4 = e34->dest;
1090	bb4->count = profile_count::from_gcov_type (v: all);
1091
1092	e12->flags &= ~EDGE_FALLTHRU;
1093	e12->flags |= EDGE_FALSE_VALUE;
1094	e12->probability = prob1.invert ();
1095
1096	e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
1097	e14->probability = prob1;
1098
1099	if (ncounts) /* Assumed to be 0 or 1. */
1100	{
1101	e23->flags &= ~EDGE_FALLTHRU;
1102	e23->flags |= EDGE_FALSE_VALUE;
1103	e23->probability = prob2.invert ();
1104
1105	e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
1106	e24->probability = prob2;
1107	}
1108
1109	e34->probability = profile_probability::always ();
1110
1111	return result;
1112	}
1113
1114	/* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1115
1116	static bool
1117	gimple_mod_subtract_transform (gimple_stmt_iterator *si)
1118	{
1119	histogram_value histogram;
1120	enum tree_code code;
1121	gcov_type count, wrong_values, all;
1122	tree lhs_type, result;
1123	profile_probability prob1, prob2;
1124	unsigned int i, steps;
1125	gcov_type count1, count2;
1126	gassign *stmt;
1127	stmt = dyn_cast <gassign *> (p: gsi_stmt (i: *si));
1128	if (!stmt)
1129	return false;
1130
1131	lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
1132	if (!INTEGRAL_TYPE_P (lhs_type))
1133	return false;
1134
1135	code = gimple_assign_rhs_code (gs: stmt);
1136
1137	if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
1138	return false;
1139
1140	histogram = gimple_histogram_value_of_type (cfun, stmt, type: HIST_TYPE_INTERVAL);
1141	if (!histogram)
1142	return false;
1143
1144	all = 0;
1145	wrong_values = 0;
1146	for (i = 0; i < histogram->hdata.intvl.steps; i++)
1147	all += histogram->hvalue.counters[i];
1148
1149	wrong_values += histogram->hvalue.counters[i];
1150	wrong_values += histogram->hvalue.counters[i+1];
1151	steps = histogram->hdata.intvl.steps;
1152	all += wrong_values;
1153	count1 = histogram->hvalue.counters[0];
1154	count2 = histogram->hvalue.counters[1];
1155
1156	if (check_counter (stmt, name: "interval", count: &count1, all: &all, bb_count_d: gimple_bb (g: stmt)->count))
1157	{
1158	gimple_remove_histogram_value (cfun, stmt, hist: histogram);
1159	return false;
1160	}
1161
1162	if (flag_profile_correction && count1 + count2 > all)
1163	all = count1 + count2;
1164
1165	gcc_assert (count1 + count2 <= all);
1166
1167	/* We require that we use just subtractions in at least 50% of all
1168	evaluations. */
1169	count = 0;
1170	for (i = 0; i < histogram->hdata.intvl.steps; i++)
1171	{
1172	count += histogram->hvalue.counters[i];
1173	if (count * 2 >= all)
1174	break;
1175	}
1176	if (i == steps
1177	|| optimize_bb_for_size_p (gimple_bb (g: stmt)))
1178	return false;
1179
1180	gimple_remove_histogram_value (cfun, stmt, hist: histogram);
1181	if (dump_enabled_p ())
1182	dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
1183	"Transformation done: mod subtract\n");
1184
1185	/* Compute probability of taking the optimal path(s). */
1186	if (all > 0)
1187	{
1188	prob1 = profile_probability::probability_in_gcov_type (val1: count1, val2: all);
1189	if (all == count1)
1190	prob2 = profile_probability::even ();
1191	else
1192	prob2 = profile_probability::probability_in_gcov_type (val1: count2, val2: all
1193	- count1);
1194	}
1195	else
1196	{
1197	prob1 = prob2 = profile_probability::never ();
1198	}
1199
1200	/* In practice, "steps" is always 2. This interface reflects this,
1201	and will need to be changed if "steps" can change. */
1202	result = gimple_mod_subtract (stmt, prob1, prob2, ncounts: i, count1, count2, all);
1203
1204	gimple_assign_set_rhs_from_tree (si, result);
1205	update_stmt (s: gsi_stmt (i: *si));
1206
1207	return true;
1208	}
1209
1210	typedef int_hash <unsigned int, 0, UINT_MAX> profile_id_hash;
1211
1212	static hash_map<profile_id_hash, cgraph_node *> *cgraph_node_map = 0;
1213
1214	/* Returns true if node graph is initialized. This
1215	is used to test if profile_id has been created
1216	for cgraph_nodes. */
1217
1218	bool
1219	coverage_node_map_initialized_p (void)
1220	{
1221	return cgraph_node_map != 0;
1222	}
1223
1224	/* Initialize map from PROFILE_ID to CGRAPH_NODE.
1225	When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1226	that the PROFILE_IDs was already assigned. */
1227
1228	void
1229	init_node_map (bool local)
1230	{
1231	struct cgraph_node *n;
1232	cgraph_node_map = new hash_map<profile_id_hash, cgraph_node *>;
1233
1234	FOR_EACH_DEFINED_FUNCTION (n)
1235	if (n->has_gimple_body_p () || n->thunk)
1236	{
1237	cgraph_node **val;
1238	dump_user_location_t loc
1239	= dump_user_location_t::from_function_decl (fndecl: n->decl);
1240	if (local)
1241	{
1242	n->profile_id = coverage_compute_profile_id (n);
1243	while ((val = cgraph_node_map->get (k: n->profile_id))
1244	|| !n->profile_id)
1245	{
1246	if (dump_enabled_p ())
1247	dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1248	"Local profile-id %i conflict"
1249	" with nodes %s %s\n",
1250	n->profile_id,
1251	n->dump_name (),
1252	(*val)->dump_name ());
1253	n->profile_id = (n->profile_id + 1) & 0x7fffffff;
1254	}
1255	}
1256	else if (!n->profile_id)
1257	{
1258	if (dump_enabled_p ())
1259	dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1260	"Node %s has no profile-id"
1261	" (profile feedback missing?)\n",
1262	n->dump_name ());
1263	continue;
1264	}
1265	else if ((val = cgraph_node_map->get (k: n->profile_id)))
1266	{
1267	if (dump_enabled_p ())
1268	dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1269	"Node %s has IP profile-id %i conflict. "
1270	"Giving up.\n",
1271	n->dump_name (), n->profile_id);
1272	*val = NULL;
1273	continue;
1274	}
1275	cgraph_node_map->put (k: n->profile_id, v: n);
1276	}
1277	}
1278
1279	/* Delete the CGRAPH_NODE_MAP. */
1280
1281	void
1282	del_node_map (void)
1283	{
1284	delete cgraph_node_map;
1285	}
1286
1287	/* Return cgraph node for function with pid */
1288
1289	struct cgraph_node*
1290	find_func_by_profile_id (int profile_id)
1291	{
1292	cgraph_node **val = cgraph_node_map->get (k: profile_id);
1293	if (val)
1294	return *val;
1295	else
1296	return NULL;
1297	}
1298
1299	/* Do transformation
1300
1301	if (actual_callee_address == address_of_most_common_function/method)
1302	do direct call
1303	else
1304	old call
1305	*/
1306
1307	gcall *
1308	gimple_ic (gcall *icall_stmt, struct cgraph_node *direct_call,
1309	profile_probability prob)
1310	{
1311	gcall *dcall_stmt;
1312	gassign *load_stmt;
1313	gcond *cond_stmt;
1314	tree tmp0, tmp1, tmp;
1315	basic_block cond_bb, dcall_bb, icall_bb, join_bb = NULL;
1316	edge e_cd, e_ci, e_di, e_dj = NULL, e_ij;
1317	gimple_stmt_iterator gsi;
1318	int lp_nr, dflags;
1319	edge e_eh, e;
1320	edge_iterator ei;
1321
1322	cond_bb = gimple_bb (g: icall_stmt);
1323	gsi = gsi_for_stmt (icall_stmt);
1324
1325	tmp0 = make_temp_ssa_name (ptr_type_node, NULL, name: "PROF");
1326	tmp1 = make_temp_ssa_name (ptr_type_node, NULL, name: "PROF");
1327	tmp = unshare_expr (gimple_call_fn (gs: icall_stmt));
1328	load_stmt = gimple_build_assign (tmp0, tmp);
1329	gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1330
1331	tmp = fold_convert (ptr_type_node, build_addr (direct_call->decl));
1332	load_stmt = gimple_build_assign (tmp1, tmp);
1333	gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1334
1335	cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1336	gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1337
1338	if (TREE_CODE (gimple_vdef (icall_stmt)) == SSA_NAME)
1339	{
1340	unlink_stmt_vdef (icall_stmt);
1341	release_ssa_name (name: gimple_vdef (g: icall_stmt));
1342	}
1343	gimple_set_vdef (g: icall_stmt, NULL_TREE);
1344	gimple_set_vuse (g: icall_stmt, NULL_TREE);
1345	update_stmt (s: icall_stmt);
1346	dcall_stmt = as_a <gcall *> (p: gimple_copy (icall_stmt));
1347	gimple_call_set_fndecl (gs: dcall_stmt, decl: direct_call->decl);
1348	dflags = flags_from_decl_or_type (direct_call->decl);
1349	if ((dflags & ECF_NORETURN) != 0
1350	&& should_remove_lhs_p (lhs: gimple_call_lhs (gs: dcall_stmt)))
1351	gimple_call_set_lhs (gs: dcall_stmt, NULL_TREE);
1352	gsi_insert_before (&gsi, dcall_stmt, GSI_SAME_STMT);
1353
1354	/* Fix CFG. */
1355	/* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1356	e_cd = split_block (cond_bb, cond_stmt);
1357	dcall_bb = e_cd->dest;
1358	dcall_bb->count = cond_bb->count.apply_probability (prob);
1359
1360	e_di = split_block (dcall_bb, dcall_stmt);
1361	icall_bb = e_di->dest;
1362	icall_bb->count = cond_bb->count - dcall_bb->count;
1363
1364	/* Do not disturb existing EH edges from the indirect call. */
1365	if (!stmt_ends_bb_p (icall_stmt))
1366	e_ij = split_block (icall_bb, icall_stmt);
1367	else
1368	{
1369	e_ij = find_fallthru_edge (edges: icall_bb->succs);
1370	/* The indirect call might be noreturn. */
1371	if (e_ij != NULL)
1372	{
1373	e_ij->probability = profile_probability::always ();
1374	e_ij = single_pred_edge (bb: split_edge (e_ij));
1375	}
1376	}
1377	if (e_ij != NULL)
1378	{
1379	join_bb = e_ij->dest;
1380	join_bb->count = cond_bb->count;
1381	}
1382
1383	e_cd->flags = (e_cd->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1384	e_cd->probability = prob;
1385
1386	e_ci = make_edge (cond_bb, icall_bb, EDGE_FALSE_VALUE);
1387	e_ci->probability = prob.invert ();
1388
1389	remove_edge (e_di);
1390
1391	if (e_ij != NULL)
1392	{
1393	if ((dflags & ECF_NORETURN) == 0)
1394	{
1395	e_dj = make_edge (dcall_bb, join_bb, EDGE_FALLTHRU);
1396	e_dj->probability = profile_probability::always ();
1397	}
1398	e_ij->probability = profile_probability::always ();
1399	}
1400
1401	/* Insert PHI node for the call result if necessary. */
1402	if (gimple_call_lhs (gs: icall_stmt)
1403	&& TREE_CODE (gimple_call_lhs (icall_stmt)) == SSA_NAME
1404	&& (dflags & ECF_NORETURN) == 0)
1405	{
1406	tree result = gimple_call_lhs (gs: icall_stmt);
1407	gphi *phi = create_phi_node (result, join_bb);
1408	gimple_call_set_lhs (gs: icall_stmt,
1409	lhs: duplicate_ssa_name (var: result, stmt: icall_stmt));
1410	add_phi_arg (phi, gimple_call_lhs (gs: icall_stmt), e_ij, UNKNOWN_LOCATION);
1411	gimple_call_set_lhs (gs: dcall_stmt,
1412	lhs: duplicate_ssa_name (var: result, stmt: dcall_stmt));
1413	add_phi_arg (phi, gimple_call_lhs (gs: dcall_stmt), e_dj, UNKNOWN_LOCATION);
1414	}
1415
1416	/* Build an EH edge for the direct call if necessary. */
1417	lp_nr = lookup_stmt_eh_lp (icall_stmt);
1418	if (lp_nr > 0 && stmt_could_throw_p (cfun, dcall_stmt))
1419	{
1420	add_stmt_to_eh_lp (dcall_stmt, lp_nr);
1421	}
1422
1423	FOR_EACH_EDGE (e_eh, ei, icall_bb->succs)
1424	if (e_eh->flags & (EDGE_EH | EDGE_ABNORMAL))
1425	{
1426	e = make_edge (dcall_bb, e_eh->dest, e_eh->flags);
1427	e->probability = e_eh->probability;
1428	for (gphi_iterator psi = gsi_start_phis (e_eh->dest);
1429	!gsi_end_p (i: psi); gsi_next (i: &psi))
1430	{
1431	gphi *phi = psi.phi ();
1432	SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e),
1433	PHI_ARG_DEF_FROM_EDGE (phi, e_eh));
1434	}
1435	}
1436	if (!stmt_could_throw_p (cfun, dcall_stmt))
1437	gimple_purge_dead_eh_edges (dcall_bb);
1438	return dcall_stmt;
1439	}
1440
1441	/* Dump info about indirect call profile. */
1442
1443	static void
1444	dump_ic_profile (gimple_stmt_iterator *gsi)
1445	{
1446	gcall *stmt;
1447	histogram_value histogram;
1448	gcov_type val, count, all;
1449	struct cgraph_node *direct_call;
1450
1451	stmt = dyn_cast <gcall *> (p: gsi_stmt (i: *gsi));
1452	if (!stmt)
1453	return;
1454
1455	if (gimple_call_fndecl (gs: stmt) != NULL_TREE)
1456	return;
1457
1458	if (gimple_call_internal_p (gs: stmt))
1459	return;
1460
1461	histogram = gimple_histogram_value_of_type (cfun, stmt, type: HIST_TYPE_INDIR_CALL);
1462	if (!histogram)
1463	return;
1464
1465	count = 0;
1466	all = histogram->hvalue.counters[0];
1467
1468	for (unsigned j = 0; j < GCOV_TOPN_MAXIMUM_TRACKED_VALUES; j++)
1469	{
1470	if (!get_nth_most_common_value (NULL, counter_type: "indirect call", hist: histogram, value: &val,
1471	count: &count, all: &all, n: j))
1472	return;
1473	if (!count)
1474	continue;
1475
1476	direct_call = find_func_by_profile_id (profile_id: (int) val);
1477
1478	if (direct_call == NULL)
1479	dump_printf_loc (
1480	MSG_MISSED_OPTIMIZATION, stmt,
1481	"Indirect call -> direct call from other "
1482	"module %T=> %i (will resolve by ipa-profile only with LTO)\n",
1483	gimple_call_fn (gs: stmt), (int) val);
1484	else
1485	dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
1486	"Indirect call -> direct call "
1487	"%T => %T (will resolve by ipa-profile)\n",
1488	gimple_call_fn (gs: stmt), direct_call->decl);
1489	dump_printf_loc (MSG_NOTE, stmt,
1490	"hist->count %" PRId64 " hist->all %" PRId64 "\n",
1491	count, all);
1492	}
1493	}
1494
1495	/* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1496	set to the argument index for the size of the string operation. */
1497
1498	static bool
1499	interesting_stringop_to_profile_p (gcall *call, int *size_arg)
1500	{
1501	enum built_in_function fcode;
1502
1503	fcode = DECL_FUNCTION_CODE (decl: gimple_call_fndecl (gs: call));
1504	switch (fcode)
1505	{
1506	case BUILT_IN_MEMCPY:
1507	case BUILT_IN_MEMPCPY:
1508	case BUILT_IN_MEMMOVE:
1509	*size_arg = 2;
1510	return validate_gimple_arglist (call, POINTER_TYPE, POINTER_TYPE,
1511	INTEGER_TYPE, VOID_TYPE);
1512	case BUILT_IN_MEMSET:
1513	*size_arg = 2;
1514	return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1515	INTEGER_TYPE, VOID_TYPE);
1516	case BUILT_IN_BZERO:
1517	*size_arg = 1;
1518	return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1519	VOID_TYPE);
1520	default:
1521	return false;
1522	}
1523	}
1524
1525	/* Convert stringop (..., vcall_size)
1526	into
1527	if (vcall_size == icall_size)
1528	stringop (..., icall_size);
1529	else
1530	stringop (..., vcall_size);
1531	assuming we'll propagate a true constant into ICALL_SIZE later. */
1532
1533	static void
1534	gimple_stringop_fixed_value (gcall *vcall_stmt, tree icall_size, profile_probability prob,
1535	gcov_type count, gcov_type all)
1536	{
1537	gassign *tmp_stmt;
1538	gcond *cond_stmt;
1539	gcall *icall_stmt;
1540	tree tmp0, tmp1, vcall_size, optype;
1541	basic_block cond_bb, icall_bb, vcall_bb, join_bb;
1542	edge e_ci, e_cv, e_iv, e_ij, e_vj;
1543	gimple_stmt_iterator gsi;
1544	int size_arg;
1545
1546	if (!interesting_stringop_to_profile_p (call: vcall_stmt, size_arg: &size_arg))
1547	gcc_unreachable ();
1548
1549	cond_bb = gimple_bb (g: vcall_stmt);
1550	gsi = gsi_for_stmt (vcall_stmt);
1551
1552	vcall_size = gimple_call_arg (gs: vcall_stmt, index: size_arg);
1553	optype = TREE_TYPE (vcall_size);
1554
1555	tmp0 = make_temp_ssa_name (type: optype, NULL, name: "PROF");
1556	tmp1 = make_temp_ssa_name (type: optype, NULL, name: "PROF");
1557	tmp_stmt = gimple_build_assign (tmp0, fold_convert (optype, icall_size));
1558	gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1559
1560	tmp_stmt = gimple_build_assign (tmp1, vcall_size);
1561	gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1562
1563	cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1564	gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1565
1566	if (TREE_CODE (gimple_vdef (vcall_stmt)) == SSA_NAME)
1567	{
1568	unlink_stmt_vdef (vcall_stmt);
1569	release_ssa_name (name: gimple_vdef (g: vcall_stmt));
1570	}
1571	gimple_set_vdef (g: vcall_stmt, NULL);
1572	gimple_set_vuse (g: vcall_stmt, NULL);
1573	update_stmt (s: vcall_stmt);
1574	icall_stmt = as_a <gcall *> (p: gimple_copy (vcall_stmt));
1575	gimple_call_set_arg (gs: icall_stmt, index: size_arg,
1576	fold_convert (optype, icall_size));
1577	gsi_insert_before (&gsi, icall_stmt, GSI_SAME_STMT);
1578
1579	/* Fix CFG. */
1580	/* Edge e_ci connects cond_bb to icall_bb, etc. */
1581	e_ci = split_block (cond_bb, cond_stmt);
1582	icall_bb = e_ci->dest;
1583	icall_bb->count = profile_count::from_gcov_type (v: count);
1584
1585	e_iv = split_block (icall_bb, icall_stmt);
1586	vcall_bb = e_iv->dest;
1587	vcall_bb->count = profile_count::from_gcov_type (v: all - count);
1588
1589	e_vj = split_block (vcall_bb, vcall_stmt);
1590	join_bb = e_vj->dest;
1591	join_bb->count = profile_count::from_gcov_type (v: all);
1592
1593	e_ci->flags = (e_ci->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1594	e_ci->probability = prob;
1595
1596	e_cv = make_edge (cond_bb, vcall_bb, EDGE_FALSE_VALUE);
1597	e_cv->probability = prob.invert ();
1598
1599	remove_edge (e_iv);
1600
1601	e_ij = make_edge (icall_bb, join_bb, EDGE_FALLTHRU);
1602	e_ij->probability = profile_probability::always ();
1603
1604	e_vj->probability = profile_probability::always ();
1605
1606	/* Insert PHI node for the call result if necessary. */
1607	if (gimple_call_lhs (gs: vcall_stmt)
1608	&& TREE_CODE (gimple_call_lhs (vcall_stmt)) == SSA_NAME)
1609	{
1610	tree result = gimple_call_lhs (gs: vcall_stmt);
1611	gphi *phi = create_phi_node (result, join_bb);
1612	gimple_call_set_lhs (gs: vcall_stmt,
1613	lhs: duplicate_ssa_name (var: result, stmt: vcall_stmt));
1614	add_phi_arg (phi, gimple_call_lhs (gs: vcall_stmt), e_vj, UNKNOWN_LOCATION);
1615	gimple_call_set_lhs (gs: icall_stmt,
1616	lhs: duplicate_ssa_name (var: result, stmt: icall_stmt));
1617	add_phi_arg (phi, gimple_call_lhs (gs: icall_stmt), e_ij, UNKNOWN_LOCATION);
1618	}
1619
1620	/* Because these are all string op builtins, they're all nothrow. */
1621	gcc_assert (!stmt_could_throw_p (cfun, vcall_stmt));
1622	gcc_assert (!stmt_could_throw_p (cfun, icall_stmt));
1623	}
1624
1625	/* Find values inside STMT for that we want to measure histograms for
1626	division/modulo optimization. */
1627
1628	static bool
1629	gimple_stringops_transform (gimple_stmt_iterator *gsi)
1630	{
1631	gcall *stmt;
1632	tree blck_size;
1633	enum built_in_function fcode;
1634	histogram_value histogram;
1635	gcov_type count, all, val;
1636	tree dest, src;
1637	unsigned int dest_align, src_align;
1638	profile_probability prob;
1639	tree tree_val;
1640	int size_arg;
1641
1642	stmt = dyn_cast <gcall *> (p: gsi_stmt (i: *gsi));
1643	if (!stmt)
1644	return false;
1645
1646	if (!gimple_call_builtin_p (gsi_stmt (i: *gsi), BUILT_IN_NORMAL))
1647	return false;
1648
1649	if (!interesting_stringop_to_profile_p (call: stmt, size_arg: &size_arg))
1650	return false;
1651
1652	blck_size = gimple_call_arg (gs: stmt, index: size_arg);
1653	if (TREE_CODE (blck_size) == INTEGER_CST)
1654	return false;
1655
1656	histogram = gimple_histogram_value_of_type (cfun, stmt,
1657	type: HIST_TYPE_TOPN_VALUES);
1658	if (!histogram)
1659	return false;
1660
1661	if (!get_nth_most_common_value (stmt, counter_type: "stringops", hist: histogram, value: &val, count: &count,
1662	all: &all))
1663	return false;
1664
1665	gimple_remove_histogram_value (cfun, stmt, hist: histogram);
1666
1667	/* We require that count is at least half of all. */
1668	if (2 * count < all || optimize_bb_for_size_p (gimple_bb (g: stmt)))
1669	return false;
1670	if (check_counter (stmt, name: "value", count: &count, all: &all, bb_count_d: gimple_bb (g: stmt)->count))
1671	return false;
1672	if (all > 0)
1673	prob = profile_probability::probability_in_gcov_type (val1: count, val2: all);
1674	else
1675	prob = profile_probability::never ();
1676
1677	dest = gimple_call_arg (gs: stmt, index: 0);
1678	dest_align = get_pointer_alignment (dest);
1679	fcode = DECL_FUNCTION_CODE (decl: gimple_call_fndecl (gs: stmt));
1680	switch (fcode)
1681	{
1682	case BUILT_IN_MEMCPY:
1683	case BUILT_IN_MEMPCPY:
1684	case BUILT_IN_MEMMOVE:
1685	src = gimple_call_arg (gs: stmt, index: 1);
1686	src_align = get_pointer_alignment (src);
1687	if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1688	return false;
1689	break;
1690	case BUILT_IN_MEMSET:
1691	if (!can_store_by_pieces (val, builtin_memset_read_str,
1692	gimple_call_arg (gs: stmt, index: 1),
1693	dest_align, true))
1694	return false;
1695	break;
1696	case BUILT_IN_BZERO:
1697	if (!can_store_by_pieces (val, builtin_memset_read_str,
1698	integer_zero_node,
1699	dest_align, true))
1700	return false;
1701	break;
1702	default:
1703	gcc_unreachable ();
1704	}
1705
1706	if (sizeof (gcov_type) == sizeof (HOST_WIDE_INT))
1707	tree_val = build_int_cst (get_gcov_type (), val);
1708	else
1709	{
1710	HOST_WIDE_INT a[2];
1711	a[0] = (unsigned HOST_WIDE_INT) val;
1712	a[1] = val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1;
1713
1714	tree_val = wide_int_to_tree (type: get_gcov_type (), cst: wide_int::from_array (val: a, len: 2,
1715	TYPE_PRECISION (get_gcov_type ()), need_canon_p: false));
1716	}
1717
1718	if (dump_enabled_p ())
1719	dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
1720	"Transformation done: single value %i stringop for %s\n",
1721	(int)val, built_in_names[(int)fcode]);
1722
1723	gimple_stringop_fixed_value (vcall_stmt: stmt, icall_size: tree_val, prob, count, all);
1724
1725	return true;
1726	}
1727
1728	void
1729	stringop_block_profile (gimple *stmt, unsigned int *expected_align,
1730	HOST_WIDE_INT *expected_size)
1731	{
1732	histogram_value histogram;
1733	histogram = gimple_histogram_value_of_type (cfun, stmt, type: HIST_TYPE_AVERAGE);
1734
1735	if (!histogram)
1736	*expected_size = -1;
1737	else if (!histogram->hvalue.counters[1])
1738	{
1739	*expected_size = -1;
1740	gimple_remove_histogram_value (cfun, stmt, hist: histogram);
1741	}
1742	else
1743	{
1744	gcov_type size;
1745	size = ((histogram->hvalue.counters[0]
1746	+ histogram->hvalue.counters[1] / 2)
1747	/ histogram->hvalue.counters[1]);
1748	/* Even if we can hold bigger value in SIZE, INT_MAX
1749	is safe "infinity" for code generation strategies. */
1750	if (size > INT_MAX)
1751	size = INT_MAX;
1752	*expected_size = size;
1753	gimple_remove_histogram_value (cfun, stmt, hist: histogram);
1754	}
1755
1756	histogram = gimple_histogram_value_of_type (cfun, stmt, type: HIST_TYPE_IOR);
1757
1758	if (!histogram)
1759	*expected_align = 0;
1760	else if (!histogram->hvalue.counters[0])
1761	{
1762	gimple_remove_histogram_value (cfun, stmt, hist: histogram);
1763	*expected_align = 0;
1764	}
1765	else
1766	{
1767	gcov_type count;
1768	unsigned int alignment;
1769
1770	count = histogram->hvalue.counters[0];
1771	alignment = 1;
1772	while (!(count & alignment)
1773	&& (alignment <= UINT_MAX / 2 / BITS_PER_UNIT))
1774	alignment <<= 1;
1775	*expected_align = alignment * BITS_PER_UNIT;
1776	gimple_remove_histogram_value (cfun, stmt, hist: histogram);
1777	}
1778	}
1779
1780
1781	/* Find values inside STMT for that we want to measure histograms for
1782	division/modulo optimization. */
1783
1784	static void
1785	gimple_divmod_values_to_profile (gimple *stmt, histogram_values *values)
1786	{
1787	tree lhs, divisor, op0, type;
1788	histogram_value hist;
1789
1790	if (gimple_code (g: stmt) != GIMPLE_ASSIGN)
1791	return;
1792
1793	lhs = gimple_assign_lhs (gs: stmt);
1794	type = TREE_TYPE (lhs);
1795	if (!INTEGRAL_TYPE_P (type))
1796	return;
1797
1798	switch (gimple_assign_rhs_code (gs: stmt))
1799	{
1800	case TRUNC_DIV_EXPR:
1801	case TRUNC_MOD_EXPR:
1802	divisor = gimple_assign_rhs2 (gs: stmt);
1803	op0 = gimple_assign_rhs1 (gs: stmt);
1804
1805	if (TREE_CODE (divisor) == SSA_NAME)
1806	/* Check for the case where the divisor is the same value most
1807	of the time. */
1808	values->safe_push (obj: gimple_alloc_histogram_value (cfun,
1809	type: HIST_TYPE_TOPN_VALUES,
1810	stmt, value: divisor));
1811
1812	/* For mod, check whether it is not often a noop (or replaceable by
1813	a few subtractions). */
1814	if (gimple_assign_rhs_code (gs: stmt) == TRUNC_MOD_EXPR
1815	&& TYPE_UNSIGNED (type)
1816	&& TREE_CODE (divisor) == SSA_NAME)
1817	{
1818	tree val;
1819	/* Check for a special case where the divisor is power of 2. */
1820	values->safe_push (obj: gimple_alloc_histogram_value (cfun,
1821	type: HIST_TYPE_POW2,
1822	stmt, value: divisor));
1823	val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1824	hist = gimple_alloc_histogram_value (cfun, type: HIST_TYPE_INTERVAL,
1825	stmt, value: val);
1826	hist->hdata.intvl.int_start = 0;
1827	hist->hdata.intvl.steps = 2;
1828	values->safe_push (obj: hist);
1829	}
1830	return;
1831
1832	default:
1833	return;
1834	}
1835	}
1836
1837	/* Find calls inside STMT for that we want to measure histograms for
1838	indirect/virtual call optimization. */
1839
1840	static void
1841	gimple_indirect_call_to_profile (gimple *stmt, histogram_values *values)
1842	{
1843	tree callee;
1844
1845	if (gimple_code (g: stmt) != GIMPLE_CALL
1846	|| gimple_call_internal_p (gs: stmt)
1847	|| gimple_call_fndecl (gs: stmt) != NULL_TREE)
1848	return;
1849
1850	callee = gimple_call_fn (gs: stmt);
1851	histogram_value v = gimple_alloc_histogram_value (cfun, type: HIST_TYPE_INDIR_CALL,
1852	stmt, value: callee);
1853	values->safe_push (obj: v);
1854
1855	return;
1856	}
1857
1858	/* Find values inside STMT for that we want to measure histograms for
1859	string operations. */
1860
1861	static void
1862	gimple_stringops_values_to_profile (gimple *gs, histogram_values *values)
1863	{
1864	gcall *stmt;
1865	tree blck_size;
1866	tree dest;
1867	int size_arg;
1868
1869	stmt = dyn_cast <gcall *> (p: gs);
1870	if (!stmt)
1871	return;
1872
1873	if (!gimple_call_builtin_p (gs, BUILT_IN_NORMAL))
1874	return;
1875
1876	if (!interesting_stringop_to_profile_p (call: stmt, size_arg: &size_arg))
1877	return;
1878
1879	dest = gimple_call_arg (gs: stmt, index: 0);
1880	blck_size = gimple_call_arg (gs: stmt, index: size_arg);
1881
1882	if (TREE_CODE (blck_size) != INTEGER_CST)
1883	{
1884	values->safe_push (obj: gimple_alloc_histogram_value (cfun,
1885	type: HIST_TYPE_TOPN_VALUES,
1886	stmt, value: blck_size));
1887	values->safe_push (obj: gimple_alloc_histogram_value (cfun, type: HIST_TYPE_AVERAGE,
1888	stmt, value: blck_size));
1889	}
1890
1891	if (TREE_CODE (blck_size) != INTEGER_CST)
1892	values->safe_push (obj: gimple_alloc_histogram_value (cfun, type: HIST_TYPE_IOR,
1893	stmt, value: dest));
1894	}
1895
1896	/* Find values inside STMT for that we want to measure histograms and adds
1897	them to list VALUES. */
1898
1899	static void
1900	gimple_values_to_profile (gimple *stmt, histogram_values *values)
1901	{
1902	gimple_divmod_values_to_profile (stmt, values);
1903	gimple_stringops_values_to_profile (gs: stmt, values);
1904	gimple_indirect_call_to_profile (stmt, values);
1905	}
1906
1907	void
1908	gimple_find_values_to_profile (histogram_values *values)
1909	{
1910	basic_block bb;
1911	gimple_stmt_iterator gsi;
1912	unsigned i;
1913	histogram_value hist = NULL;
1914	values->create (nelems: 0);
1915
1916	FOR_EACH_BB_FN (bb, cfun)
1917	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
1918	gimple_values_to_profile (stmt: gsi_stmt (i: gsi), values);
1919
1920	values->safe_push (obj: gimple_alloc_histogram_value (cfun,
1921	type: HIST_TYPE_TIME_PROFILE));
1922
1923	FOR_EACH_VEC_ELT (*values, i, hist)
1924	{
1925	switch (hist->type)
1926	{
1927	case HIST_TYPE_INTERVAL:
1928	hist->n_counters = hist->hdata.intvl.steps + 2;
1929	break;
1930
1931	case HIST_TYPE_POW2:
1932	hist->n_counters = 2;
1933	break;
1934
1935	case HIST_TYPE_TOPN_VALUES:
1936	case HIST_TYPE_INDIR_CALL:
1937	hist->n_counters = GCOV_TOPN_MEM_COUNTERS;
1938	break;
1939
1940	case HIST_TYPE_TIME_PROFILE:
1941	hist->n_counters = 1;
1942	break;
1943
1944	case HIST_TYPE_AVERAGE:
1945	hist->n_counters = 2;
1946	break;
1947
1948	case HIST_TYPE_IOR:
1949	hist->n_counters = 1;
1950	break;
1951
1952	default:
1953	gcc_unreachable ();
1954	}
1955	if (dump_file && hist->hvalue.stmt != NULL)
1956	{
1957	fprintf (stream: dump_file, format: "Stmt ");
1958	print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM);
1959	dump_histogram_value (dump_file, hist);
1960	}
1961	}
1962	}
1963