1	/* Branch prediction routines for the GNU compiler.
2	Copyright (C) 2000-2024 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	/* References:
21
22	[1] "Branch Prediction for Free"
23	Ball and Larus; PLDI '93.
24	[2] "Static Branch Frequency and Program Profile Analysis"
25	Wu and Larus; MICRO-27.
26	[3] "Corpus-based Static Branch Prediction"
27	Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
28
29
30	#include "config.h"
31	#include "system.h"
32	#include "coretypes.h"
33	#include "backend.h"
34	#include "rtl.h"
35	#include "tree.h"
36	#include "gimple.h"
37	#include "cfghooks.h"
38	#include "tree-pass.h"
39	#include "ssa.h"
40	#include "memmodel.h"
41	#include "emit-rtl.h"
42	#include "cgraph.h"
43	#include "coverage.h"
44	#include "diagnostic-core.h"
45	#include "gimple-predict.h"
46	#include "fold-const.h"
47	#include "calls.h"
48	#include "cfganal.h"
49	#include "profile.h"
50	#include "sreal.h"
51	#include "cfgloop.h"
52	#include "gimple-iterator.h"
53	#include "tree-cfg.h"
54	#include "tree-ssa-loop-niter.h"
55	#include "tree-ssa-loop.h"
56	#include "tree-scalar-evolution.h"
57	#include "ipa-utils.h"
58	#include "gimple-pretty-print.h"
59	#include "selftest.h"
60	#include "cfgrtl.h"
61	#include "stringpool.h"
62	#include "attribs.h"
63
64	/* Enum with reasons why a predictor is ignored. */
65
66	enum predictor_reason
67	{
68	REASON_NONE,
69	REASON_IGNORED,
70	REASON_SINGLE_EDGE_DUPLICATE,
71	REASON_EDGE_PAIR_DUPLICATE
72	};
73
74	/* String messages for the aforementioned enum. */
75
76	static const char *reason_messages[] = {"", " (ignored)",
77	" (single edge duplicate)", " (edge pair duplicate)"};
78
79
80	static void combine_predictions_for_insn (rtx_insn *, basic_block);
81	static void dump_prediction (FILE *, enum br_predictor, int, basic_block,
82	enum predictor_reason, edge);
83	static void predict_paths_leading_to (basic_block, enum br_predictor,
84	enum prediction,
85	class loop *in_loop = NULL);
86	static void predict_paths_leading_to_edge (edge, enum br_predictor,
87	enum prediction,
88	class loop *in_loop = NULL);
89	static bool can_predict_insn_p (const rtx_insn *);
90	static HOST_WIDE_INT get_predictor_value (br_predictor, HOST_WIDE_INT);
91	static void determine_unlikely_bbs ();
92	static void estimate_bb_frequencies ();
93
94	/* Information we hold about each branch predictor.
95	Filled using information from predict.def. */
96
97	struct predictor_info
98	{
99	const char *const name; /* Name used in the debugging dumps. */
100	const int hitrate; /* Expected hitrate used by
101	predict_insn_def call. */
102	const int flags;
103	};
104
105	/* Use given predictor without Dempster-Shaffer theory if it matches
106	using first_match heuristics. */
107	#define PRED_FLAG_FIRST_MATCH 1
108
109	/* Recompute hitrate in percent to our representation. */
110
111	#define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
112
113	#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
114	static const struct predictor_info predictor_info[]= {
115	#include "predict.def"
116
117	/* Upper bound on predictors. */
118	{NULL, .hitrate: 0, .flags: 0}
119	};
120	#undef DEF_PREDICTOR
121
122	static gcov_type min_count = -1;
123
124	/* Determine the threshold for hot BB counts. */
125
126	gcov_type
127	get_hot_bb_threshold ()
128	{
129	if (min_count == -1)
130	{
131	const int hot_frac = param_hot_bb_count_fraction;
132	const gcov_type min_hot_count
133	= hot_frac
134	? profile_info->sum_max / hot_frac
135	: (gcov_type)profile_count::max_count;
136	set_hot_bb_threshold (min_hot_count);
137	if (dump_file)
138	fprintf (stream: dump_file, format: "Setting hotness threshold to %" PRId64 ".\n",
139	min_hot_count);
140	}
141	return min_count;
142	}
143
144	/* Set the threshold for hot BB counts. */
145
146	void
147	set_hot_bb_threshold (gcov_type min)
148	{
149	min_count = min;
150	}
151
152	/* Return TRUE if COUNT is considered to be hot in function FUN. */
153
154	bool
155	maybe_hot_count_p (struct function *fun, profile_count count)
156	{
157	if (!count.initialized_p ())
158	return true;
159	if (count.ipa () == profile_count::zero ())
160	return false;
161	if (!count.ipa_p ())
162	{
163	struct cgraph_node *node = cgraph_node::get (decl: fun->decl);
164	if (!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
165	{
166	if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
167	return false;
168	if (node->frequency == NODE_FREQUENCY_HOT)
169	return true;
170	}
171	if (profile_status_for_fn (fun) == PROFILE_ABSENT)
172	return true;
173	if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
174	&& count < (ENTRY_BLOCK_PTR_FOR_FN (fun)->count.apply_scale (num: 2, den: 3)))
175	return false;
176	if (count * param_hot_bb_frequency_fraction
177	< ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
178	return false;
179	return true;
180	}
181	/* Code executed at most once is not hot. */
182	if (count <= MAX (profile_info ? profile_info->runs : 1, 1))
183	return false;
184	return (count >= get_hot_bb_threshold ());
185	}
186
187	/* Return true if basic block BB of function FUN can be CPU intensive
188	and should thus be optimized for maximum performance. */
189
190	bool
191	maybe_hot_bb_p (struct function *fun, const_basic_block bb)
192	{
193	gcc_checking_assert (fun);
194	return maybe_hot_count_p (fun, count: bb->count);
195	}
196
197	/* Return true if edge E can be CPU intensive and should thus be optimized
198	for maximum performance. */
199
200	bool
201	maybe_hot_edge_p (edge e)
202	{
203	return maybe_hot_count_p (cfun, count: e->count ());
204	}
205
206	/* Return true if COUNT is considered to be never executed in function FUN
207	or if function FUN is considered so in the static profile. */
208
209	static bool
210	probably_never_executed (struct function *fun, profile_count count)
211	{
212	gcc_checking_assert (fun);
213	if (count.ipa () == profile_count::zero ())
214	return true;
215	/* Do not trust adjusted counts. This will make us to drop int cold section
216	code with low execution count as a result of inlining. These low counts
217	are not safe even with read profile and may lead us to dropping
218	code which actually gets executed into cold section of binary that is not
219	desirable. */
220	if (count.precise_p () && profile_status_for_fn (fun) == PROFILE_READ)
221	{
222	const int unlikely_frac = param_unlikely_bb_count_fraction;
223	if (count * unlikely_frac >= profile_info->runs)
224	return false;
225	return true;
226	}
227	if ((!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
228	&& (cgraph_node::get (decl: fun->decl)->frequency
229	== NODE_FREQUENCY_UNLIKELY_EXECUTED))
230	return true;
231	return false;
232	}
233
234	/* Return true if basic block BB of function FUN is probably never executed. */
235
236	bool
237	probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
238	{
239	return probably_never_executed (fun, count: bb->count);
240	}
241
242	/* Return true if edge E is unlikely executed for obvious reasons. */
243
244	static bool
245	unlikely_executed_edge_p (edge e)
246	{
247	return (e->src->count == profile_count::zero ()
248	|| e->probability == profile_probability::never ())
249	|| (e->flags & (EDGE_EH | EDGE_FAKE));
250	}
251
252	/* Return true if edge E of function FUN is probably never executed. */
253
254	bool
255	probably_never_executed_edge_p (struct function *fun, edge e)
256	{
257	if (unlikely_executed_edge_p (e))
258	return true;
259	return probably_never_executed (fun, count: e->count ());
260	}
261
262	/* Return true if function FUN should always be optimized for size. */
263
264	optimize_size_level
265	optimize_function_for_size_p (struct function *fun)
266	{
267	if (!fun || !fun->decl)
268	return optimize_size ? OPTIMIZE_SIZE_MAX : OPTIMIZE_SIZE_NO;
269	cgraph_node *n = cgraph_node::get (decl: fun->decl);
270	if (n)
271	return n->optimize_for_size_p ();
272	return OPTIMIZE_SIZE_NO;
273	}
274
275	/* Return true if function FUN should always be optimized for speed. */
276
277	bool
278	optimize_function_for_speed_p (struct function *fun)
279	{
280	return !optimize_function_for_size_p (fun);
281	}
282
283	/* Return the optimization type that should be used for function FUN. */
284
285	optimization_type
286	function_optimization_type (struct function *fun)
287	{
288	return (optimize_function_for_speed_p (fun)
289	? OPTIMIZE_FOR_SPEED
290	: OPTIMIZE_FOR_SIZE);
291	}
292
293	/* Return TRUE if basic block BB should be optimized for size. */
294
295	optimize_size_level
296	optimize_bb_for_size_p (const_basic_block bb)
297	{
298	enum optimize_size_level ret = optimize_function_for_size_p (cfun);
299
300	if (bb && ret < OPTIMIZE_SIZE_MAX && bb->count == profile_count::zero ())
301	ret = OPTIMIZE_SIZE_MAX;
302	if (bb && ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_bb_p (cfun, bb))
303	ret = OPTIMIZE_SIZE_BALANCED;
304	return ret;
305	}
306
307	/* Return TRUE if basic block BB should be optimized for speed. */
308
309	bool
310	optimize_bb_for_speed_p (const_basic_block bb)
311	{
312	return !optimize_bb_for_size_p (bb);
313	}
314
315	/* Return the optimization type that should be used for basic block BB. */
316
317	optimization_type
318	bb_optimization_type (const_basic_block bb)
319	{
320	return (optimize_bb_for_speed_p (bb)
321	? OPTIMIZE_FOR_SPEED
322	: OPTIMIZE_FOR_SIZE);
323	}
324
325	/* Return TRUE if edge E should be optimized for size. */
326
327	optimize_size_level
328	optimize_edge_for_size_p (edge e)
329	{
330	enum optimize_size_level ret = optimize_function_for_size_p (cfun);
331
332	if (ret < OPTIMIZE_SIZE_MAX && unlikely_executed_edge_p (e))
333	ret = OPTIMIZE_SIZE_MAX;
334	if (ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_edge_p (e))
335	ret = OPTIMIZE_SIZE_BALANCED;
336	return ret;
337	}
338
339	/* Return TRUE if edge E should be optimized for speed. */
340
341	bool
342	optimize_edge_for_speed_p (edge e)
343	{
344	return !optimize_edge_for_size_p (e);
345	}
346
347	/* Return TRUE if the current function is optimized for size. */
348
349	optimize_size_level
350	optimize_insn_for_size_p (void)
351	{
352	enum optimize_size_level ret = optimize_function_for_size_p (cfun);
353	if (ret < OPTIMIZE_SIZE_BALANCED && !crtl->maybe_hot_insn_p)
354	ret = OPTIMIZE_SIZE_BALANCED;
355	return ret;
356	}
357
358	/* Return TRUE if the current function is optimized for speed. */
359
360	bool
361	optimize_insn_for_speed_p (void)
362	{
363	return !optimize_insn_for_size_p ();
364	}
365
366	/* Return the optimization type that should be used for the current
367	instruction. */
368
369	optimization_type
370	insn_optimization_type ()
371	{
372	return (optimize_insn_for_speed_p ()
373	? OPTIMIZE_FOR_SPEED
374	: OPTIMIZE_FOR_SIZE);
375	}
376
377	/* Return TRUE if LOOP should be optimized for size. */
378
379	optimize_size_level
380	optimize_loop_for_size_p (class loop *loop)
381	{
382	return optimize_bb_for_size_p (bb: loop->header);
383	}
384
385	/* Return TRUE if LOOP should be optimized for speed. */
386
387	bool
388	optimize_loop_for_speed_p (class loop *loop)
389	{
390	return optimize_bb_for_speed_p (bb: loop->header);
391	}
392
393	/* Return TRUE if nest rooted at LOOP should be optimized for speed. */
394
395	bool
396	optimize_loop_nest_for_speed_p (class loop *loop)
397	{
398	class loop *l = loop;
399	if (optimize_loop_for_speed_p (loop))
400	return true;
401	l = loop->inner;
402	while (l && l != loop)
403	{
404	if (optimize_loop_for_speed_p (loop: l))
405	return true;
406	if (l->inner)
407	l = l->inner;
408	else if (l->next)
409	l = l->next;
410	else
411	{
412	while (l != loop && !l->next)
413	l = loop_outer (loop: l);
414	if (l != loop)
415	l = l->next;
416	}
417	}
418	return false;
419	}
420
421	/* Return TRUE if nest rooted at LOOP should be optimized for size. */
422
423	optimize_size_level
424	optimize_loop_nest_for_size_p (class loop *loop)
425	{
426	enum optimize_size_level ret = optimize_loop_for_size_p (loop);
427	class loop *l = loop;
428
429	l = loop->inner;
430	while (l && l != loop)
431	{
432	if (ret == OPTIMIZE_SIZE_NO)
433	break;
434	ret = MIN (optimize_loop_for_size_p (l), ret);
435	if (l->inner)
436	l = l->inner;
437	else if (l->next)
438	l = l->next;
439	else
440	{
441	while (l != loop && !l->next)
442	l = loop_outer (loop: l);
443	if (l != loop)
444	l = l->next;
445	}
446	}
447	return ret;
448	}
449
450	/* Return true if edge E is likely to be well predictable by branch
451	predictor. */
452
453	bool
454	predictable_edge_p (edge e)
455	{
456	if (!e->probability.initialized_p ())
457	return false;
458	if ((e->probability.to_reg_br_prob_base ()
459	<= param_predictable_branch_outcome * REG_BR_PROB_BASE / 100)
460	|| (REG_BR_PROB_BASE - e->probability.to_reg_br_prob_base ()
461	<= param_predictable_branch_outcome * REG_BR_PROB_BASE / 100))
462	return true;
463	return false;
464	}
465
466
467	/* Set RTL expansion for BB profile. */
468
469	void
470	rtl_profile_for_bb (basic_block bb)
471	{
472	crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
473	}
474
475	/* Set RTL expansion for edge profile. */
476
477	void
478	rtl_profile_for_edge (edge e)
479	{
480	crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
481	}
482
483	/* Set RTL expansion to default mode (i.e. when profile info is not known). */
484	void
485	default_rtl_profile (void)
486	{
487	crtl->maybe_hot_insn_p = true;
488	}
489
490	/* Return true if the one of outgoing edges is already predicted by
491	PREDICTOR. */
492
493	bool
494	rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
495	{
496	rtx note;
497	if (!INSN_P (BB_END (bb)))
498	return false;
499	for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
500	if (REG_NOTE_KIND (note) == REG_BR_PRED
501	&& INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
502	return true;
503	return false;
504	}
505
506	/* Structure representing predictions in tree level. */
507
508	struct edge_prediction {
509	struct edge_prediction *ep_next;
510	edge ep_edge;
511	enum br_predictor ep_predictor;
512	int ep_probability;
513	};
514
515	/* This map contains for a basic block the list of predictions for the
516	outgoing edges. */
517
518	static hash_map<const_basic_block, edge_prediction *> *bb_predictions;
519
520	/* Return true if the one of outgoing edges is already predicted by
521	PREDICTOR. */
522
523	bool
524	gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
525	{
526	struct edge_prediction *i;
527	edge_prediction **preds = bb_predictions->get (k: bb);
528
529	if (!preds)
530	return false;
531
532	for (i = *preds; i; i = i->ep_next)
533	if (i->ep_predictor == predictor)
534	return true;
535	return false;
536	}
537
538	/* Return true if the one of outgoing edges is already predicted by
539	PREDICTOR for edge E predicted as TAKEN. */
540
541	bool
542	edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
543	{
544	struct edge_prediction *i;
545	basic_block bb = e->src;
546	edge_prediction **preds = bb_predictions->get (k: bb);
547	if (!preds)
548	return false;
549
550	int probability = predictor_info[(int) predictor].hitrate;
551
552	if (taken != TAKEN)
553	probability = REG_BR_PROB_BASE - probability;
554
555	for (i = *preds; i; i = i->ep_next)
556	if (i->ep_predictor == predictor
557	&& i->ep_edge == e
558	&& i->ep_probability == probability)
559	return true;
560	return false;
561	}
562
563	/* Same predicate as above, working on edges. */
564	bool
565	edge_probability_reliable_p (const_edge e)
566	{
567	return e->probability.probably_reliable_p ();
568	}
569
570	/* Same predicate as edge_probability_reliable_p, working on notes. */
571	bool
572	br_prob_note_reliable_p (const_rtx note)
573	{
574	gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
575	return profile_probability::from_reg_br_prob_note
576	(XINT (note, 0)).probably_reliable_p ();
577	}
578
579	static void
580	predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
581	{
582	gcc_assert (any_condjump_p (insn));
583	if (!flag_guess_branch_prob)
584	return;
585
586	add_reg_note (insn, REG_BR_PRED,
587	gen_rtx_CONCAT (VOIDmode,
588	GEN_INT ((int) predictor),
589	GEN_INT ((int) probability)));
590	}
591
592	/* Predict insn by given predictor. */
593
594	void
595	predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
596	enum prediction taken)
597	{
598	int probability = predictor_info[(int) predictor].hitrate;
599	gcc_assert (probability != PROB_UNINITIALIZED);
600
601	if (taken != TAKEN)
602	probability = REG_BR_PROB_BASE - probability;
603
604	predict_insn (insn, predictor, probability);
605	}
606
607	/* Predict edge E with given probability if possible. */
608
609	void
610	rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
611	{
612	rtx_insn *last_insn;
613	last_insn = BB_END (e->src);
614
615	/* We can store the branch prediction information only about
616	conditional jumps. */
617	if (!any_condjump_p (last_insn))
618	return;
619
620	/* We always store probability of branching. */
621	if (e->flags & EDGE_FALLTHRU)
622	probability = REG_BR_PROB_BASE - probability;
623
624	predict_insn (insn: last_insn, predictor, probability);
625	}
626
627	/* Predict edge E with the given PROBABILITY. */
628	void
629	gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
630	{
631	if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
632	&& EDGE_COUNT (e->src->succs) > 1
633	&& flag_guess_branch_prob
634	&& optimize)
635	{
636	struct edge_prediction *i = XNEW (struct edge_prediction);
637	edge_prediction *&preds = bb_predictions->get_or_insert (k: e->src);
638
639	i->ep_next = preds;
640	preds = i;
641	i->ep_probability = probability;
642	i->ep_predictor = predictor;
643	i->ep_edge = e;
644	}
645	}
646
647	/* Filter edge predictions PREDS by a function FILTER: if FILTER return false
648	the prediction is removed.
649	DATA are passed to the filter function. */
650
651	static void
652	filter_predictions (edge_prediction **preds,
653	bool (*filter) (edge_prediction *, void *), void *data)
654	{
655	if (!bb_predictions)
656	return;
657
658	if (preds)
659	{
660	struct edge_prediction **prediction = preds;
661	struct edge_prediction *next;
662
663	while (*prediction)
664	{
665	if ((*filter) (*prediction, data))
666	prediction = &((*prediction)->ep_next);
667	else
668	{
669	next = (*prediction)->ep_next;
670	free (ptr: *prediction);
671	*prediction = next;
672	}
673	}
674	}
675	}
676
677	/* Filter function predicate that returns true for a edge predicate P
678	if its edge is equal to DATA. */
679
680	static bool
681	not_equal_edge_p (edge_prediction *p, void *data)
682	{
683	return p->ep_edge != (edge)data;
684	}
685
686	/* Remove all predictions on given basic block that are attached
687	to edge E. */
688	void
689	remove_predictions_associated_with_edge (edge e)
690	{
691	if (!bb_predictions)
692	return;
693
694	edge_prediction **preds = bb_predictions->get (k: e->src);
695	filter_predictions (preds, filter: not_equal_edge_p, data: e);
696	}
697
698	/* Clears the list of predictions stored for BB. */
699
700	static void
701	clear_bb_predictions (basic_block bb)
702	{
703	edge_prediction **preds = bb_predictions->get (k: bb);
704	struct edge_prediction *pred, *next;
705
706	if (!preds)
707	return;
708
709	for (pred = *preds; pred; pred = next)
710	{
711	next = pred->ep_next;
712	free (ptr: pred);
713	}
714	*preds = NULL;
715	}
716
717	/* Return true when we can store prediction on insn INSN.
718	At the moment we represent predictions only on conditional
719	jumps, not at computed jump or other complicated cases. */
720	static bool
721	can_predict_insn_p (const rtx_insn *insn)
722	{
723	return (JUMP_P (insn)
724	&& any_condjump_p (insn)
725	&& EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
726	}
727
728	/* Predict edge E by given predictor if possible. */
729
730	void
731	predict_edge_def (edge e, enum br_predictor predictor,
732	enum prediction taken)
733	{
734	int probability = predictor_info[(int) predictor].hitrate;
735
736	if (taken != TAKEN)
737	probability = REG_BR_PROB_BASE - probability;
738
739	predict_edge (e, predictor, probability);
740	}
741
742	/* Invert all branch predictions or probability notes in the INSN. This needs
743	to be done each time we invert the condition used by the jump. */
744
745	void
746	invert_br_probabilities (rtx insn)
747	{
748	rtx note;
749
750	for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
751	if (REG_NOTE_KIND (note) == REG_BR_PROB)
752	XINT (note, 0) = profile_probability::from_reg_br_prob_note
753	(XINT (note, 0)).invert ().to_reg_br_prob_note ();
754	else if (REG_NOTE_KIND (note) == REG_BR_PRED)
755	XEXP (XEXP (note, 0), 1)
756	= GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
757	}
758
759	/* Dump information about the branch prediction to the output file. */
760
761	static void
762	dump_prediction (FILE *file, enum br_predictor predictor, int probability,
763	basic_block bb, enum predictor_reason reason = REASON_NONE,
764	edge ep_edge = NULL)
765	{
766	edge e = ep_edge;
767	edge_iterator ei;
768
769	if (!file)
770	return;
771
772	if (e == NULL)
773	FOR_EACH_EDGE (e, ei, bb->succs)
774	if (! (e->flags & EDGE_FALLTHRU))
775	break;
776
777	char edge_info_str[128];
778	if (ep_edge)
779	sprintf (s: edge_info_str, format: " of edge %d->%d", ep_edge->src->index,
780	ep_edge->dest->index);
781	else
782	edge_info_str[0] = '\0';
783
784	fprintf (stream: file, format: " %s heuristics%s%s: %.2f%%",
785	predictor_info[predictor].name,
786	edge_info_str, reason_messages[reason],
787	probability * 100.0 / REG_BR_PROB_BASE);
788
789	if (bb->count.initialized_p ())
790	{
791	fprintf (stream: file, format: " exec ");
792	bb->count.dump (f: file);
793	if (e && e->count ().initialized_p () && bb->count.to_gcov_type ())
794	{
795	fprintf (stream: file, format: " hit ");
796	e->count ().dump (f: file);
797	fprintf (stream: file, format: " (%.1f%%)", e->count ().to_gcov_type() * 100.0
798	/ bb->count.to_gcov_type ());
799	}
800	}
801
802	fprintf (stream: file, format: "\n");
803
804	/* Print output that be easily read by analyze_brprob.py script. We are
805	interested only in counts that are read from GCDA files. */
806	if (dump_file && (dump_flags & TDF_DETAILS)
807	&& bb->count.precise_p ()
808	&& reason == REASON_NONE)
809	{
810	fprintf (stream: file, format: ";;heuristics;%s;%" PRId64 ";%" PRId64 ";%.1f;\n",
811	predictor_info[predictor].name,
812	bb->count.to_gcov_type (), e->count ().to_gcov_type (),
813	probability * 100.0 / REG_BR_PROB_BASE);
814	}
815	}
816
817	/* Return true if STMT is known to be unlikely executed. */
818
819	static bool
820	unlikely_executed_stmt_p (gimple *stmt)
821	{
822	if (!is_gimple_call (gs: stmt))
823	return false;
824	/* NORETURN attribute alone is not strong enough: exit() may be quite
825	likely executed once during program run. */
826	if (gimple_call_fntype (gs: stmt)
827	&& lookup_attribute (attr_name: "cold",
828	TYPE_ATTRIBUTES (gimple_call_fntype (stmt)))
829	&& !lookup_attribute (attr_name: "cold", DECL_ATTRIBUTES (current_function_decl)))
830	return true;
831	tree decl = gimple_call_fndecl (gs: stmt);
832	if (!decl)
833	return false;
834	if (lookup_attribute (attr_name: "cold", DECL_ATTRIBUTES (decl))
835	&& !lookup_attribute (attr_name: "cold", DECL_ATTRIBUTES (current_function_decl)))
836	return true;
837
838	cgraph_node *n = cgraph_node::get (decl);
839	if (!n)
840	return false;
841
842	availability avail;
843	n = n->ultimate_alias_target (availability: &avail);
844	if (avail < AVAIL_AVAILABLE)
845	return false;
846	if (!n->analyzed
847	|| n->decl == current_function_decl)
848	return false;
849	return n->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED;
850	}
851
852	/* Return true if BB is unlikely executed. */
853
854	static bool
855	unlikely_executed_bb_p (basic_block bb)
856	{
857	if (bb->count == profile_count::zero ())
858	return true;
859	if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
860	return false;
861	for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
862	!gsi_end_p (i: gsi); gsi_next (i: &gsi))
863	{
864	if (unlikely_executed_stmt_p (stmt: gsi_stmt (i: gsi)))
865	return true;
866	if (stmt_can_terminate_bb_p (gsi_stmt (i: gsi)))
867	return false;
868	}
869	return false;
870	}
871
872	/* We cannot predict the probabilities of outgoing edges of bb. Set them
873	evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
874	even probability for all edges not mentioned in the set. These edges
875	are given PROB_VERY_UNLIKELY probability. Similarly for LIKELY_EDGES,
876	if we have exactly one likely edge, make the other edges predicted
877	as not probable. */
878
879	static void
880	set_even_probabilities (basic_block bb,
881	hash_set<edge> *unlikely_edges = NULL,
882	hash_set<edge_prediction *> *likely_edges = NULL)
883	{
884	unsigned nedges = 0, unlikely_count = 0;
885	edge e = NULL;
886	edge_iterator ei;
887	profile_probability all = profile_probability::always ();
888
889	FOR_EACH_EDGE (e, ei, bb->succs)
890	if (e->probability.initialized_p ())
891	all -= e->probability;
892	else if (!unlikely_executed_edge_p (e))
893	{
894	nedges++;
895	if (unlikely_edges != NULL && unlikely_edges->contains (k: e))
896	{
897	all -= profile_probability::very_unlikely ();
898	unlikely_count++;
899	}
900	}
901
902	/* Make the distribution even if all edges are unlikely. */
903	unsigned likely_count = likely_edges ? likely_edges->elements () : 0;
904	if (unlikely_count == nedges)
905	{
906	unlikely_edges = NULL;
907	unlikely_count = 0;
908	}
909
910	/* If we have one likely edge, then use its probability and distribute
911	remaining probabilities as even. */
912	if (likely_count == 1)
913	{
914	FOR_EACH_EDGE (e, ei, bb->succs)
915	if (e->probability.initialized_p ())
916	;
917	else if (!unlikely_executed_edge_p (e))
918	{
919	edge_prediction *prediction = *likely_edges->begin ();
920	int p = prediction->ep_probability;
921	profile_probability prob
922	= profile_probability::from_reg_br_prob_base (v: p);
923
924	if (prediction->ep_edge == e)
925	e->probability = prob;
926	else if (unlikely_edges != NULL && unlikely_edges->contains (k: e))
927	e->probability = profile_probability::very_unlikely ();
928	else
929	{
930	profile_probability remainder = prob.invert ();
931	remainder -= (profile_probability::very_unlikely ()
932	* unlikely_count);
933	int count = nedges - unlikely_count - 1;
934	gcc_assert (count >= 0);
935
936	e->probability = remainder / count;
937	}
938	}
939	else
940	e->probability = profile_probability::never ();
941	}
942	else
943	{
944	/* Make all unlikely edges unlikely and the rest will have even
945	probability. */
946	unsigned scale = nedges - unlikely_count;
947	FOR_EACH_EDGE (e, ei, bb->succs)
948	if (e->probability.initialized_p ())
949	;
950	else if (!unlikely_executed_edge_p (e))
951	{
952	if (unlikely_edges != NULL && unlikely_edges->contains (k: e))
953	e->probability = profile_probability::very_unlikely ();
954	else
955	e->probability = all / scale;
956	}
957	else
958	e->probability = profile_probability::never ();
959	}
960	}
961
962	/* Add REG_BR_PROB note to JUMP with PROB. */
963
964	void
965	add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
966	{
967	gcc_checking_assert (JUMP_P (jump) && !find_reg_note (jump, REG_BR_PROB, 0));
968	add_int_reg_note (jump, REG_BR_PROB, prob.to_reg_br_prob_note ());
969	}
970
971	/* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
972	note if not already present. Remove now useless REG_BR_PRED notes. */
973
974	static void
975	combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
976	{
977	rtx prob_note;
978	rtx *pnote;
979	rtx note;
980	int best_probability = PROB_EVEN;
981	enum br_predictor best_predictor = END_PREDICTORS;
982	int combined_probability = REG_BR_PROB_BASE / 2;
983	int d;
984	bool first_match = false;
985	bool found = false;
986
987	if (!can_predict_insn_p (insn))
988	{
989	set_even_probabilities (bb);
990	return;
991	}
992
993	prob_note = find_reg_note (insn, REG_BR_PROB, 0);
994	pnote = &REG_NOTES (insn);
995	if (dump_file)
996	fprintf (stream: dump_file, format: "Predictions for insn %i bb %i\n", INSN_UID (insn),
997	bb->index);
998
999	/* We implement "first match" heuristics and use probability guessed
1000	by predictor with smallest index. */
1001	for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1002	if (REG_NOTE_KIND (note) == REG_BR_PRED)
1003	{
1004	enum br_predictor predictor = ((enum br_predictor)
1005	INTVAL (XEXP (XEXP (note, 0), 0)));
1006	int probability = INTVAL (XEXP (XEXP (note, 0), 1));
1007
1008	found = true;
1009	if (best_predictor > predictor
1010	&& predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1011	best_probability = probability, best_predictor = predictor;
1012
1013	d = (combined_probability * probability
1014	+ (REG_BR_PROB_BASE - combined_probability)
1015	* (REG_BR_PROB_BASE - probability));
1016
1017	/* Use FP math to avoid overflows of 32bit integers. */
1018	if (d == 0)
1019	/* If one probability is 0% and one 100%, avoid division by zero. */
1020	combined_probability = REG_BR_PROB_BASE / 2;
1021	else
1022	combined_probability = (((double) combined_probability) * probability
1023	* REG_BR_PROB_BASE / d + 0.5);
1024	}
1025
1026	/* Decide which heuristic to use. In case we didn't match anything,
1027	use no_prediction heuristic, in case we did match, use either
1028	first match or Dempster-Shaffer theory depending on the flags. */
1029
1030	if (best_predictor != END_PREDICTORS)
1031	first_match = true;
1032
1033	if (!found)
1034	dump_prediction (file: dump_file, predictor: PRED_NO_PREDICTION,
1035	probability: combined_probability, bb);
1036	else
1037	{
1038	if (!first_match)
1039	dump_prediction (file: dump_file, predictor: PRED_DS_THEORY, probability: combined_probability,
1040	bb, reason: !first_match ? REASON_NONE : REASON_IGNORED);
1041	else
1042	dump_prediction (file: dump_file, predictor: PRED_FIRST_MATCH, probability: best_probability,
1043	bb, reason: first_match ? REASON_NONE : REASON_IGNORED);
1044	}
1045
1046	if (first_match)
1047	combined_probability = best_probability;
1048	dump_prediction (file: dump_file, predictor: PRED_COMBINED, probability: combined_probability, bb);
1049
1050	while (*pnote)
1051	{
1052	if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
1053	{
1054	enum br_predictor predictor = ((enum br_predictor)
1055	INTVAL (XEXP (XEXP (*pnote, 0), 0)));
1056	int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
1057
1058	dump_prediction (file: dump_file, predictor, probability, bb,
1059	reason: (!first_match || best_predictor == predictor)
1060	? REASON_NONE : REASON_IGNORED);
1061	*pnote = XEXP (*pnote, 1);
1062	}
1063	else
1064	pnote = &XEXP (*pnote, 1);
1065	}
1066
1067	if (!prob_note)
1068	{
1069	profile_probability p
1070	= profile_probability::from_reg_br_prob_base (v: combined_probability);
1071	add_reg_br_prob_note (jump: insn, prob: p);
1072
1073	/* Save the prediction into CFG in case we are seeing non-degenerated
1074	conditional jump. */
1075	if (!single_succ_p (bb))
1076	{
1077	BRANCH_EDGE (bb)->probability = p;
1078	FALLTHRU_EDGE (bb)->probability
1079	= BRANCH_EDGE (bb)->probability.invert ();
1080	}
1081	}
1082	else if (!single_succ_p (bb))
1083	{
1084	profile_probability prob = profile_probability::from_reg_br_prob_note
1085	(XINT (prob_note, 0));
1086
1087	BRANCH_EDGE (bb)->probability = prob;
1088	FALLTHRU_EDGE (bb)->probability = prob.invert ();
1089	}
1090	else
1091	single_succ_edge (bb)->probability = profile_probability::always ();
1092	}
1093
1094	/* Edge prediction hash traits. */
1095
1096	struct predictor_hash: pointer_hash <edge_prediction>
1097	{
1098
1099	static inline hashval_t hash (const edge_prediction *);
1100	static inline bool equal (const edge_prediction *, const edge_prediction *);
1101	};
1102
1103	/* Calculate hash value of an edge prediction P based on predictor and
1104	normalized probability. */
1105
1106	inline hashval_t
1107	predictor_hash::hash (const edge_prediction *p)
1108	{
1109	inchash::hash hstate;
1110	hstate.add_int (v: p->ep_predictor);
1111
1112	int prob = p->ep_probability;
1113	if (prob > REG_BR_PROB_BASE / 2)
1114	prob = REG_BR_PROB_BASE - prob;
1115
1116	hstate.add_int (v: prob);
1117
1118	return hstate.end ();
1119	}
1120
1121	/* Return true whether edge predictions P1 and P2 use the same predictor and
1122	have equal (or opposed probability). */
1123
1124	inline bool
1125	predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
1126	{
1127	return (p1->ep_predictor == p2->ep_predictor
1128	&& (p1->ep_probability == p2->ep_probability
1129	|| p1->ep_probability == REG_BR_PROB_BASE - p2->ep_probability));
1130	}
1131
1132	struct predictor_hash_traits: predictor_hash,
1133	typed_noop_remove <edge_prediction *> {};
1134
1135	/* Return true if edge prediction P is not in DATA hash set. */
1136
1137	static bool
1138	not_removed_prediction_p (edge_prediction *p, void *data)
1139	{
1140	hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
1141	return !remove->contains (k: p);
1142	}
1143
1144	/* Prune predictions for a basic block BB. Currently we do following
1145	clean-up steps:
1146
1147	1) remove duplicate prediction that is guessed with the same probability
1148	(different than 1/2) to both edge
1149	2) remove duplicates for a prediction that belongs with the same probability
1150	to a single edge
1151
1152	*/
1153
1154	static void
1155	prune_predictions_for_bb (basic_block bb)
1156	{
1157	edge_prediction **preds = bb_predictions->get (k: bb);
1158
1159	if (preds)
1160	{
1161	hash_table <predictor_hash_traits> s (13);
1162	hash_set <edge_prediction *> remove;
1163
1164	/* Step 1: identify predictors that should be removed. */
1165	for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
1166	{
1167	edge_prediction *existing = s.find (value: pred);
1168	if (existing)
1169	{
1170	if (pred->ep_edge == existing->ep_edge
1171	&& pred->ep_probability == existing->ep_probability)
1172	{
1173	/* Remove a duplicate predictor. */
1174	dump_prediction (file: dump_file, predictor: pred->ep_predictor,
1175	probability: pred->ep_probability, bb,
1176	reason: REASON_SINGLE_EDGE_DUPLICATE, ep_edge: pred->ep_edge);
1177
1178	remove.add (k: pred);
1179	}
1180	else if (pred->ep_edge != existing->ep_edge
1181	&& pred->ep_probability == existing->ep_probability
1182	&& pred->ep_probability != REG_BR_PROB_BASE / 2)
1183	{
1184	/* Remove both predictors as they predict the same
1185	for both edges. */
1186	dump_prediction (file: dump_file, predictor: existing->ep_predictor,
1187	probability: pred->ep_probability, bb,
1188	reason: REASON_EDGE_PAIR_DUPLICATE,
1189	ep_edge: existing->ep_edge);
1190	dump_prediction (file: dump_file, predictor: pred->ep_predictor,
1191	probability: pred->ep_probability, bb,
1192	reason: REASON_EDGE_PAIR_DUPLICATE,
1193	ep_edge: pred->ep_edge);
1194
1195	remove.add (k: existing);
1196	remove.add (k: pred);
1197	}
1198	}
1199
1200	edge_prediction **slot2 = s.find_slot (value: pred, insert: INSERT);
1201	*slot2 = pred;
1202	}
1203
1204	/* Step 2: Remove predictors. */
1205	filter_predictions (preds, filter: not_removed_prediction_p, data: &remove);
1206	}
1207	}
1208
1209	/* Combine predictions into single probability and store them into CFG.
1210	Remove now useless prediction entries.
1211	If DRY_RUN is set, only produce dumps and do not modify profile. */
1212
1213	static void
1214	combine_predictions_for_bb (basic_block bb, bool dry_run)
1215	{
1216	int best_probability = PROB_EVEN;
1217	enum br_predictor best_predictor = END_PREDICTORS;
1218	int combined_probability = REG_BR_PROB_BASE / 2;
1219	int d;
1220	bool first_match = false;
1221	bool found = false;
1222	struct edge_prediction *pred;
1223	int nedges = 0;
1224	edge e, first = NULL, second = NULL;
1225	edge_iterator ei;
1226	int nzero = 0;
1227	int nunknown = 0;
1228
1229	FOR_EACH_EDGE (e, ei, bb->succs)
1230	{
1231	if (!unlikely_executed_edge_p (e))
1232	{
1233	nedges ++;
1234	if (first && !second)
1235	second = e;
1236	if (!first)
1237	first = e;
1238	}
1239	else if (!e->probability.initialized_p ())
1240	e->probability = profile_probability::never ();
1241	if (!e->probability.initialized_p ())
1242	nunknown++;
1243	else if (e->probability == profile_probability::never ())
1244	nzero++;
1245	}
1246
1247	/* When there is no successor or only one choice, prediction is easy.
1248
1249	When we have a basic block with more than 2 successors, the situation
1250	is more complicated as DS theory cannot be used literally.
1251	More precisely, let's assume we predicted edge e1 with probability p1,
1252	thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1253	need to find probability of e.g. m1({b2}), which we don't know.
1254	The only approximation is to equally distribute 1-p1 to all edges
1255	different from b1.
1256
1257	According to numbers we've got from SPEC2006 benchark, there's only
1258	one interesting reliable predictor (noreturn call), which can be
1259	handled with a bit easier approach. */
1260	if (nedges != 2)
1261	{
1262	hash_set<edge> unlikely_edges (4);
1263	hash_set<edge_prediction *> likely_edges (4);
1264
1265	/* Identify all edges that have a probability close to very unlikely.
1266	Doing the approach for very unlikely doesn't worth for doing as
1267	there's no such probability in SPEC2006 benchmark. */
1268	edge_prediction **preds = bb_predictions->get (k: bb);
1269	if (preds)
1270	for (pred = *preds; pred; pred = pred->ep_next)
1271	{
1272	if (pred->ep_probability <= PROB_VERY_UNLIKELY
1273	|| pred->ep_predictor == PRED_COLD_LABEL)
1274	unlikely_edges.add (k: pred->ep_edge);
1275	else if (pred->ep_probability >= PROB_VERY_LIKELY
1276	|| pred->ep_predictor == PRED_BUILTIN_EXPECT
1277	|| pred->ep_predictor == PRED_HOT_LABEL)
1278	likely_edges.add (k: pred);
1279	}
1280
1281	/* It can happen that an edge is both in likely_edges and unlikely_edges.
1282	Clear both sets in that situation. */
1283	for (hash_set<edge_prediction *>::iterator it = likely_edges.begin ();
1284	it != likely_edges.end (); ++it)
1285	if (unlikely_edges.contains (k: (*it)->ep_edge))
1286	{
1287	likely_edges.empty ();
1288	unlikely_edges.empty ();
1289	break;
1290	}
1291
1292	if (!dry_run)
1293	set_even_probabilities (bb, unlikely_edges: &unlikely_edges, likely_edges: &likely_edges);
1294	clear_bb_predictions (bb);
1295	if (dump_file)
1296	{
1297	fprintf (stream: dump_file, format: "Predictions for bb %i\n", bb->index);
1298	if (unlikely_edges.is_empty ())
1299	fprintf (stream: dump_file,
1300	format: "%i edges in bb %i predicted to even probabilities\n",
1301	nedges, bb->index);
1302	else
1303	{
1304	fprintf (stream: dump_file,
1305	format: "%i edges in bb %i predicted with some unlikely edges\n",
1306	nedges, bb->index);
1307	FOR_EACH_EDGE (e, ei, bb->succs)
1308	if (!unlikely_executed_edge_p (e))
1309	dump_prediction (file: dump_file, predictor: PRED_COMBINED,
1310	probability: e->probability.to_reg_br_prob_base (), bb, reason: REASON_NONE, ep_edge: e);
1311	}
1312	}
1313	return;
1314	}
1315
1316	if (dump_file)
1317	fprintf (stream: dump_file, format: "Predictions for bb %i\n", bb->index);
1318
1319	prune_predictions_for_bb (bb);
1320
1321	edge_prediction **preds = bb_predictions->get (k: bb);
1322
1323	if (preds)
1324	{
1325	/* We implement "first match" heuristics and use probability guessed
1326	by predictor with smallest index. */
1327	for (pred = *preds; pred; pred = pred->ep_next)
1328	{
1329	enum br_predictor predictor = pred->ep_predictor;
1330	int probability = pred->ep_probability;
1331
1332	if (pred->ep_edge != first)
1333	probability = REG_BR_PROB_BASE - probability;
1334
1335	found = true;
1336	/* First match heuristics would be widly confused if we predicted
1337	both directions. */
1338	if (best_predictor > predictor
1339	&& predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1340	{
1341	struct edge_prediction *pred2;
1342	int prob = probability;
1343
1344	for (pred2 = (struct edge_prediction *) *preds;
1345	pred2; pred2 = pred2->ep_next)
1346	if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
1347	{
1348	int probability2 = pred2->ep_probability;
1349
1350	if (pred2->ep_edge != first)
1351	probability2 = REG_BR_PROB_BASE - probability2;
1352
1353	if ((probability < REG_BR_PROB_BASE / 2) !=
1354	(probability2 < REG_BR_PROB_BASE / 2))
1355	break;
1356
1357	/* If the same predictor later gave better result, go for it! */
1358	if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
1359	|| (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
1360	prob = probability2;
1361	}
1362	if (!pred2)
1363	best_probability = prob, best_predictor = predictor;
1364	}
1365
1366	d = (combined_probability * probability
1367	+ (REG_BR_PROB_BASE - combined_probability)
1368	* (REG_BR_PROB_BASE - probability));
1369
1370	/* Use FP math to avoid overflows of 32bit integers. */
1371	if (d == 0)
1372	/* If one probability is 0% and one 100%, avoid division by zero. */
1373	combined_probability = REG_BR_PROB_BASE / 2;
1374	else
1375	combined_probability = (((double) combined_probability)
1376	* probability
1377	* REG_BR_PROB_BASE / d + 0.5);
1378	}
1379	}
1380
1381	/* Decide which heuristic to use. In case we didn't match anything,
1382	use no_prediction heuristic, in case we did match, use either
1383	first match or Dempster-Shaffer theory depending on the flags. */
1384
1385	if (best_predictor != END_PREDICTORS)
1386	first_match = true;
1387
1388	if (!found)
1389	dump_prediction (file: dump_file, predictor: PRED_NO_PREDICTION, probability: combined_probability, bb);
1390	else
1391	{
1392	if (!first_match)
1393	dump_prediction (file: dump_file, predictor: PRED_DS_THEORY, probability: combined_probability, bb,
1394	reason: !first_match ? REASON_NONE : REASON_IGNORED);
1395	else
1396	dump_prediction (file: dump_file, predictor: PRED_FIRST_MATCH, probability: best_probability, bb,
1397	reason: first_match ? REASON_NONE : REASON_IGNORED);
1398	}
1399
1400	if (first_match)
1401	combined_probability = best_probability;
1402	dump_prediction (file: dump_file, predictor: PRED_COMBINED, probability: combined_probability, bb);
1403
1404	if (preds)
1405	{
1406	for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
1407	{
1408	enum br_predictor predictor = pred->ep_predictor;
1409	int probability = pred->ep_probability;
1410
1411	dump_prediction (file: dump_file, predictor, probability, bb,
1412	reason: (!first_match || best_predictor == predictor)
1413	? REASON_NONE : REASON_IGNORED, ep_edge: pred->ep_edge);
1414	}
1415	}
1416	clear_bb_predictions (bb);
1417
1418
1419	/* If we have only one successor which is unknown, we can compute missing
1420	probability. */
1421	if (nunknown == 1)
1422	{
1423	profile_probability prob = profile_probability::always ();
1424	edge missing = NULL;
1425
1426	FOR_EACH_EDGE (e, ei, bb->succs)
1427	if (e->probability.initialized_p ())
1428	prob -= e->probability;
1429	else if (missing == NULL)
1430	missing = e;
1431	else
1432	gcc_unreachable ();
1433	missing->probability = prob;
1434	}
1435	/* If nothing is unknown, we have nothing to update. */
1436	else if (!nunknown && nzero != (int)EDGE_COUNT (bb->succs))
1437	;
1438	else if (!dry_run)
1439	{
1440	first->probability
1441	= profile_probability::from_reg_br_prob_base (v: combined_probability);
1442	second->probability = first->probability.invert ();
1443	}
1444	}
1445
1446	/* Check if T1 and T2 satisfy the IV_COMPARE condition.
1447	Return the SSA_NAME if the condition satisfies, NULL otherwise.
1448
1449	T1 and T2 should be one of the following cases:
1450	1. T1 is SSA_NAME, T2 is NULL
1451	2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1452	3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1453
1454	static tree
1455	strips_small_constant (tree t1, tree t2)
1456	{
1457	tree ret = NULL;
1458	int value = 0;
1459
1460	if (!t1)
1461	return NULL;
1462	else if (TREE_CODE (t1) == SSA_NAME)
1463	ret = t1;
1464	else if (tree_fits_shwi_p (t1))
1465	value = tree_to_shwi (t1);
1466	else
1467	return NULL;
1468
1469	if (!t2)
1470	return ret;
1471	else if (tree_fits_shwi_p (t2))
1472	value = tree_to_shwi (t2);
1473	else if (TREE_CODE (t2) == SSA_NAME)
1474	{
1475	if (ret)
1476	return NULL;
1477	else
1478	ret = t2;
1479	}
1480
1481	if (value <= 4 && value >= -4)
1482	return ret;
1483	else
1484	return NULL;
1485	}
1486
1487	/* Return the SSA_NAME in T or T's operands.
1488	Return NULL if SSA_NAME cannot be found. */
1489
1490	static tree
1491	get_base_value (tree t)
1492	{
1493	if (TREE_CODE (t) == SSA_NAME)
1494	return t;
1495
1496	if (!BINARY_CLASS_P (t))
1497	return NULL;
1498
1499	switch (TREE_OPERAND_LENGTH (t))
1500	{
1501	case 1:
1502	return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1503	case 2:
1504	return strips_small_constant (TREE_OPERAND (t, 0),
1505	TREE_OPERAND (t, 1));
1506	default:
1507	return NULL;
1508	}
1509	}
1510
1511	/* Check the compare STMT in LOOP. If it compares an induction
1512	variable to a loop invariant, return true, and save
1513	LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1514	Otherwise return false and set LOOP_INVAIANT to NULL. */
1515
1516	static bool
1517	is_comparison_with_loop_invariant_p (gcond *stmt, class loop *loop,
1518	tree *loop_invariant,
1519	enum tree_code *compare_code,
1520	tree *loop_step,
1521	tree *loop_iv_base)
1522	{
1523	tree op0, op1, bound, base;
1524	affine_iv iv0, iv1;
1525	enum tree_code code;
1526	tree step;
1527
1528	code = gimple_cond_code (gs: stmt);
1529	*loop_invariant = NULL;
1530
1531	switch (code)
1532	{
1533	case GT_EXPR:
1534	case GE_EXPR:
1535	case NE_EXPR:
1536	case LT_EXPR:
1537	case LE_EXPR:
1538	case EQ_EXPR:
1539	break;
1540
1541	default:
1542	return false;
1543	}
1544
1545	op0 = gimple_cond_lhs (gs: stmt);
1546	op1 = gimple_cond_rhs (gs: stmt);
1547
1548	if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST)
1549	|| (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1550	return false;
1551	if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1552	return false;
1553	if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1554	return false;
1555	if (TREE_CODE (iv0.step) != INTEGER_CST
1556	|| TREE_CODE (iv1.step) != INTEGER_CST)
1557	return false;
1558	if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1559	|| (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1560	return false;
1561
1562	if (integer_zerop (iv0.step))
1563	{
1564	if (code != NE_EXPR && code != EQ_EXPR)
1565	code = invert_tree_comparison (code, false);
1566	bound = iv0.base;
1567	base = iv1.base;
1568	if (tree_fits_shwi_p (iv1.step))
1569	step = iv1.step;
1570	else
1571	return false;
1572	}
1573	else
1574	{
1575	bound = iv1.base;
1576	base = iv0.base;
1577	if (tree_fits_shwi_p (iv0.step))
1578	step = iv0.step;
1579	else
1580	return false;
1581	}
1582
1583	if (TREE_CODE (bound) != INTEGER_CST)
1584	bound = get_base_value (t: bound);
1585	if (!bound)
1586	return false;
1587	if (TREE_CODE (base) != INTEGER_CST)
1588	base = get_base_value (t: base);
1589	if (!base)
1590	return false;
1591
1592	*loop_invariant = bound;
1593	*compare_code = code;
1594	*loop_step = step;
1595	*loop_iv_base = base;
1596	return true;
1597	}
1598
1599	/* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1600
1601	static bool
1602	expr_coherent_p (tree t1, tree t2)
1603	{
1604	gimple *stmt;
1605	tree ssa_name_1 = NULL;
1606	tree ssa_name_2 = NULL;
1607
1608	gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1609	gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1610
1611	if (t1 == t2)
1612	return true;
1613
1614	if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
1615	return true;
1616	if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
1617	return false;
1618
1619	/* Check to see if t1 is expressed/defined with t2. */
1620	stmt = SSA_NAME_DEF_STMT (t1);
1621	gcc_assert (stmt != NULL);
1622	if (is_gimple_assign (gs: stmt))
1623	{
1624	ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1625	if (ssa_name_1 && ssa_name_1 == t2)
1626	return true;
1627	}
1628
1629	/* Check to see if t2 is expressed/defined with t1. */
1630	stmt = SSA_NAME_DEF_STMT (t2);
1631	gcc_assert (stmt != NULL);
1632	if (is_gimple_assign (gs: stmt))
1633	{
1634	ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1635	if (ssa_name_2 && ssa_name_2 == t1)
1636	return true;
1637	}
1638
1639	/* Compare if t1 and t2's def_stmts are identical. */
1640	if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
1641	return true;
1642	else
1643	return false;
1644	}
1645
1646	/* Return true if E is predicted by one of loop heuristics. */
1647
1648	static bool
1649	predicted_by_loop_heuristics_p (basic_block bb)
1650	{
1651	struct edge_prediction *i;
1652	edge_prediction **preds = bb_predictions->get (k: bb);
1653
1654	if (!preds)
1655	return false;
1656
1657	for (i = *preds; i; i = i->ep_next)
1658	if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
1659	|| i->ep_predictor == PRED_LOOP_ITERATIONS_MAX
1660	|| i->ep_predictor == PRED_LOOP_ITERATIONS
1661	|| i->ep_predictor == PRED_LOOP_EXIT
1662	|| i->ep_predictor == PRED_LOOP_EXIT_WITH_RECURSION
1663	|| i->ep_predictor == PRED_LOOP_EXTRA_EXIT)
1664	return true;
1665	return false;
1666	}
1667
1668	/* Predict branch probability of BB when BB contains a branch that compares
1669	an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1670	loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1671
1672	E.g.
1673	for (int i = 0; i < bound; i++) {
1674	if (i < bound - 2)
1675	computation_1();
1676	else
1677	computation_2();
1678	}
1679
1680	In this loop, we will predict the branch inside the loop to be taken. */
1681
1682	static void
1683	predict_iv_comparison (class loop *loop, basic_block bb,
1684	tree loop_bound_var,
1685	tree loop_iv_base_var,
1686	enum tree_code loop_bound_code,
1687	int loop_bound_step)
1688	{
1689	tree compare_var, compare_base;
1690	enum tree_code compare_code;
1691	tree compare_step_var;
1692	edge then_edge;
1693	edge_iterator ei;
1694
1695	if (predicted_by_loop_heuristics_p (bb))
1696	return;
1697
1698	gcond *stmt = safe_dyn_cast <gcond *> (p: *gsi_last_bb (bb));
1699	if (!stmt)
1700	return;
1701	if (!is_comparison_with_loop_invariant_p (stmt,
1702	loop, loop_invariant: &compare_var,
1703	compare_code: &compare_code,
1704	loop_step: &compare_step_var,
1705	loop_iv_base: &compare_base))
1706	return;
1707
1708	/* Find the taken edge. */
1709	FOR_EACH_EDGE (then_edge, ei, bb->succs)
1710	if (then_edge->flags & EDGE_TRUE_VALUE)
1711	break;
1712
1713	/* When comparing an IV to a loop invariant, NE is more likely to be
1714	taken while EQ is more likely to be not-taken. */
1715	if (compare_code == NE_EXPR)
1716	{
1717	predict_edge_def (e: then_edge, predictor: PRED_LOOP_IV_COMPARE_GUESS, taken: TAKEN);
1718	return;
1719	}
1720	else if (compare_code == EQ_EXPR)
1721	{
1722	predict_edge_def (e: then_edge, predictor: PRED_LOOP_IV_COMPARE_GUESS, taken: NOT_TAKEN);
1723	return;
1724	}
1725
1726	if (!expr_coherent_p (t1: loop_iv_base_var, t2: compare_base))
1727	return;
1728
1729	/* If loop bound, base and compare bound are all constants, we can
1730	calculate the probability directly. */
1731	if (tree_fits_shwi_p (loop_bound_var)
1732	&& tree_fits_shwi_p (compare_var)
1733	&& tree_fits_shwi_p (compare_base))
1734	{
1735	int probability;
1736	wi::overflow_type overflow;
1737	bool overall_overflow = false;
1738	widest_int compare_count, tem;
1739
1740	/* (loop_bound - base) / compare_step */
1741	tem = wi::sub (x: wi::to_widest (t: loop_bound_var),
1742	y: wi::to_widest (t: compare_base), sgn: SIGNED, overflow: &overflow);
1743	overall_overflow |= overflow;
1744	widest_int loop_count = wi::div_trunc (x: tem,
1745	y: wi::to_widest (t: compare_step_var),
1746	sgn: SIGNED, overflow: &overflow);
1747	overall_overflow |= overflow;
1748
1749	if (!wi::neg_p (x: wi::to_widest (t: compare_step_var))
1750	^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1751	{
1752	/* (loop_bound - compare_bound) / compare_step */
1753	tem = wi::sub (x: wi::to_widest (t: loop_bound_var),
1754	y: wi::to_widest (t: compare_var), sgn: SIGNED, overflow: &overflow);
1755	overall_overflow |= overflow;
1756	compare_count = wi::div_trunc (x: tem, y: wi::to_widest (t: compare_step_var),
1757	sgn: SIGNED, overflow: &overflow);
1758	overall_overflow |= overflow;
1759	}
1760	else
1761	{
1762	/* (compare_bound - base) / compare_step */
1763	tem = wi::sub (x: wi::to_widest (t: compare_var),
1764	y: wi::to_widest (t: compare_base), sgn: SIGNED, overflow: &overflow);
1765	overall_overflow |= overflow;
1766	compare_count = wi::div_trunc (x: tem, y: wi::to_widest (t: compare_step_var),
1767	sgn: SIGNED, overflow: &overflow);
1768	overall_overflow |= overflow;
1769	}
1770	if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1771	++compare_count;
1772	if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1773	++loop_count;
1774	if (wi::neg_p (x: compare_count))
1775	compare_count = 0;
1776	if (wi::neg_p (x: loop_count))
1777	loop_count = 0;
1778	if (loop_count == 0)
1779	probability = 0;
1780	else if (wi::cmps (x: compare_count, y: loop_count) == 1)
1781	probability = REG_BR_PROB_BASE;
1782	else
1783	{
1784	tem = compare_count * REG_BR_PROB_BASE;
1785	tem = wi::udiv_trunc (x: tem, y: loop_count);
1786	probability = tem.to_uhwi ();
1787	}
1788
1789	/* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1790	if (!overall_overflow)
1791	predict_edge (e: then_edge, predictor: PRED_LOOP_IV_COMPARE, probability);
1792
1793	return;
1794	}
1795
1796	if (expr_coherent_p (t1: loop_bound_var, t2: compare_var))
1797	{
1798	if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
1799	&& (compare_code == LT_EXPR || compare_code == LE_EXPR))
1800	predict_edge_def (e: then_edge, predictor: PRED_LOOP_IV_COMPARE_GUESS, taken: TAKEN);
1801	else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
1802	&& (compare_code == GT_EXPR || compare_code == GE_EXPR))
1803	predict_edge_def (e: then_edge, predictor: PRED_LOOP_IV_COMPARE_GUESS, taken: TAKEN);
1804	else if (loop_bound_code == NE_EXPR)
1805	{
1806	/* If the loop backedge condition is "(i != bound)", we do
1807	the comparison based on the step of IV:
1808	* step < 0 : backedge condition is like (i > bound)
1809	* step > 0 : backedge condition is like (i < bound) */
1810	gcc_assert (loop_bound_step != 0);
1811	if (loop_bound_step > 0
1812	&& (compare_code == LT_EXPR
1813	|| compare_code == LE_EXPR))
1814	predict_edge_def (e: then_edge, predictor: PRED_LOOP_IV_COMPARE_GUESS, taken: TAKEN);
1815	else if (loop_bound_step < 0
1816	&& (compare_code == GT_EXPR
1817	|| compare_code == GE_EXPR))
1818	predict_edge_def (e: then_edge, predictor: PRED_LOOP_IV_COMPARE_GUESS, taken: TAKEN);
1819	else
1820	predict_edge_def (e: then_edge, predictor: PRED_LOOP_IV_COMPARE_GUESS, taken: NOT_TAKEN);
1821	}
1822	else
1823	/* The branch is predicted not-taken if loop_bound_code is
1824	opposite with compare_code. */
1825	predict_edge_def (e: then_edge, predictor: PRED_LOOP_IV_COMPARE_GUESS, taken: NOT_TAKEN);
1826	}
1827	else if (expr_coherent_p (t1: loop_iv_base_var, t2: compare_var))
1828	{
1829	/* For cases like:
1830	for (i = s; i < h; i++)
1831	if (i > s + 2) ....
1832	The branch should be predicted taken. */
1833	if (loop_bound_step > 0
1834	&& (compare_code == GT_EXPR || compare_code == GE_EXPR))
1835	predict_edge_def (e: then_edge, predictor: PRED_LOOP_IV_COMPARE_GUESS, taken: TAKEN);
1836	else if (loop_bound_step < 0
1837	&& (compare_code == LT_EXPR || compare_code == LE_EXPR))
1838	predict_edge_def (e: then_edge, predictor: PRED_LOOP_IV_COMPARE_GUESS, taken: TAKEN);
1839	else
1840	predict_edge_def (e: then_edge, predictor: PRED_LOOP_IV_COMPARE_GUESS, taken: NOT_TAKEN);
1841	}
1842	}
1843
1844	/* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1845	exits are resulted from short-circuit conditions that will generate an
1846	if_tmp. E.g.:
1847
1848	if (foo() || global > 10)
1849	break;
1850
1851	This will be translated into:
1852
1853	BB3:
1854	loop header...
1855	BB4:
1856	if foo() goto BB6 else goto BB5
1857	BB5:
1858	if global > 10 goto BB6 else goto BB7
1859	BB6:
1860	goto BB7
1861	BB7:
1862	iftmp = (PHI 0(BB5), 1(BB6))
1863	if iftmp == 1 goto BB8 else goto BB3
1864	BB8:
1865	outside of the loop...
1866
1867	The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1868	From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1869	exits. This function takes BB7->BB8 as input, and finds out the extra loop
1870	exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1871
1872	static void
1873	predict_extra_loop_exits (class loop *loop, edge exit_edge)
1874	{
1875	unsigned i;
1876	bool check_value_one;
1877	gimple *lhs_def_stmt;
1878	gphi *phi_stmt;
1879	tree cmp_rhs, cmp_lhs;
1880
1881	gcond *cmp_stmt = safe_dyn_cast <gcond *> (p: *gsi_last_bb (bb: exit_edge->src));
1882	if (!cmp_stmt)
1883	return;
1884
1885	cmp_rhs = gimple_cond_rhs (gs: cmp_stmt);
1886	cmp_lhs = gimple_cond_lhs (gs: cmp_stmt);
1887	if (!TREE_CONSTANT (cmp_rhs)
1888	|| !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1889	return;
1890	if (TREE_CODE (cmp_lhs) != SSA_NAME)
1891	return;
1892
1893	/* If check_value_one is true, only the phi_args with value '1' will lead
1894	to loop exit. Otherwise, only the phi_args with value '0' will lead to
1895	loop exit. */
1896	check_value_one = (((integer_onep (cmp_rhs))
1897	^ (gimple_cond_code (gs: cmp_stmt) == EQ_EXPR))
1898	^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1899
1900	lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1901	if (!lhs_def_stmt)
1902	return;
1903
1904	phi_stmt = dyn_cast <gphi *> (p: lhs_def_stmt);
1905	if (!phi_stmt)
1906	return;
1907
1908	for (i = 0; i < gimple_phi_num_args (gs: phi_stmt); i++)
1909	{
1910	edge e1;
1911	edge_iterator ei;
1912	tree val = gimple_phi_arg_def (gs: phi_stmt, index: i);
1913	edge e = gimple_phi_arg_edge (phi: phi_stmt, i);
1914
1915	if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1916	continue;
1917	if ((check_value_one ^ integer_onep (val)) == 1)
1918	continue;
1919	if (EDGE_COUNT (e->src->succs) != 1)
1920	{
1921	predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN,
1922	in_loop: loop);
1923	continue;
1924	}
1925
1926	FOR_EACH_EDGE (e1, ei, e->src->preds)
1927	predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN,
1928	in_loop: loop);
1929	}
1930	}
1931
1932
1933	/* Predict edge probabilities by exploiting loop structure. */
1934
1935	static void
1936	predict_loops (void)
1937	{
1938	basic_block bb;
1939	hash_set <class loop *> with_recursion(10);
1940
1941	FOR_EACH_BB_FN (bb, cfun)
1942	{
1943	gimple_stmt_iterator gsi;
1944	tree decl;
1945
1946	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
1947	if (is_gimple_call (gs: gsi_stmt (i: gsi))
1948	&& (decl = gimple_call_fndecl (gs: gsi_stmt (i: gsi))) != NULL
1949	&& recursive_call_p (current_function_decl, decl))
1950	{
1951	class loop *loop = bb->loop_father;
1952	while (loop && !with_recursion.add (k: loop))
1953	loop = loop_outer (loop);
1954	}
1955	}
1956
1957	/* Try to predict out blocks in a loop that are not part of a
1958	natural loop. */
1959	for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1960	{
1961	basic_block bb, *bbs;
1962	unsigned j, n_exits = 0;
1963	class tree_niter_desc niter_desc;
1964	edge ex;
1965	class nb_iter_bound *nb_iter;
1966	enum tree_code loop_bound_code = ERROR_MARK;
1967	tree loop_bound_step = NULL;
1968	tree loop_bound_var = NULL;
1969	tree loop_iv_base = NULL;
1970	gcond *stmt = NULL;
1971	bool recursion = with_recursion.contains (k: loop);
1972
1973	auto_vec<edge> exits = get_loop_exit_edges (loop);
1974	FOR_EACH_VEC_ELT (exits, j, ex)
1975	if (!unlikely_executed_edge_p (e: ex) && !(ex->flags & EDGE_ABNORMAL_CALL))
1976	n_exits ++;
1977	if (!n_exits)
1978	continue;
1979
1980	if (dump_file && (dump_flags & TDF_DETAILS))
1981	fprintf (stream: dump_file, format: "Predicting loop %i%s with %i exits.\n",
1982	loop->num, recursion ? " (with recursion)":"", n_exits);
1983	if (dump_file && (dump_flags & TDF_DETAILS)
1984	&& max_loop_iterations_int (loop) >= 0)
1985	{
1986	fprintf (stream: dump_file,
1987	format: "Loop %d iterates at most %i times.\n", loop->num,
1988	(int)max_loop_iterations_int (loop));
1989	}
1990	if (dump_file && (dump_flags & TDF_DETAILS)
1991	&& likely_max_loop_iterations_int (loop) >= 0)
1992	{
1993	fprintf (stream: dump_file, format: "Loop %d likely iterates at most %i times.\n",
1994	loop->num, (int)likely_max_loop_iterations_int (loop));
1995	}
1996
1997	FOR_EACH_VEC_ELT (exits, j, ex)
1998	{
1999	tree niter = NULL;
2000	HOST_WIDE_INT nitercst;
2001	int max = param_max_predicted_iterations;
2002	int probability;
2003	enum br_predictor predictor;
2004	widest_int nit;
2005
2006	if (unlikely_executed_edge_p (e: ex)
2007	|| (ex->flags & EDGE_ABNORMAL_CALL))
2008	continue;
2009	/* Loop heuristics do not expect exit conditional to be inside
2010	inner loop. We predict from innermost to outermost loop. */
2011	if (predicted_by_loop_heuristics_p (bb: ex->src))
2012	{
2013	if (dump_file && (dump_flags & TDF_DETAILS))
2014	fprintf (stream: dump_file, format: "Skipping exit %i->%i because "
2015	"it is already predicted.\n",
2016	ex->src->index, ex->dest->index);
2017	continue;
2018	}
2019	predict_extra_loop_exits (loop, exit_edge: ex);
2020
2021	if (number_of_iterations_exit (loop, ex, niter: &niter_desc, false, every_iteration: false))
2022	niter = niter_desc.niter;
2023	if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
2024	niter = loop_niter_by_eval (loop, ex);
2025	if (dump_file && (dump_flags & TDF_DETAILS)
2026	&& TREE_CODE (niter) == INTEGER_CST)
2027	{
2028	fprintf (stream: dump_file, format: "Exit %i->%i %d iterates ",
2029	ex->src->index, ex->dest->index,
2030	loop->num);
2031	print_generic_expr (dump_file, niter, TDF_SLIM);
2032	fprintf (stream: dump_file, format: " times.\n");
2033	}
2034
2035	if (TREE_CODE (niter) == INTEGER_CST)
2036	{
2037	if (tree_fits_uhwi_p (niter)
2038	&& max
2039	&& compare_tree_int (niter, max - 1) == -1)
2040	nitercst = tree_to_uhwi (niter) + 1;
2041	else
2042	nitercst = max;
2043	predictor = PRED_LOOP_ITERATIONS;
2044	}
2045	/* If we have just one exit and we can derive some information about
2046	the number of iterations of the loop from the statements inside
2047	the loop, use it to predict this exit. */
2048	else if (n_exits == 1
2049	&& estimated_stmt_executions (loop, &nit))
2050	{
2051	if (wi::gtu_p (x: nit, y: max))
2052	nitercst = max;
2053	else
2054	nitercst = nit.to_shwi ();
2055	predictor = PRED_LOOP_ITERATIONS_GUESSED;
2056	}
2057	/* If we have likely upper bound, trust it for very small iteration
2058	counts. Such loops would otherwise get mispredicted by standard
2059	LOOP_EXIT heuristics. */
2060	else if (n_exits == 1
2061	&& likely_max_stmt_executions (loop, &nit)
2062	&& wi::ltu_p (x: nit,
2063	RDIV (REG_BR_PROB_BASE,
2064	REG_BR_PROB_BASE
2065	- predictor_info
2066	[recursion
2067	? PRED_LOOP_EXIT_WITH_RECURSION
2068	: PRED_LOOP_EXIT].hitrate)))
2069	{
2070	nitercst = nit.to_shwi ();
2071	predictor = PRED_LOOP_ITERATIONS_MAX;
2072	}
2073	else
2074	{
2075	if (dump_file && (dump_flags & TDF_DETAILS))
2076	fprintf (stream: dump_file, format: "Nothing known about exit %i->%i.\n",
2077	ex->src->index, ex->dest->index);
2078	continue;
2079	}
2080
2081	if (dump_file && (dump_flags & TDF_DETAILS))
2082	fprintf (stream: dump_file, format: "Recording prediction to %i iterations by %s.\n",
2083	(int)nitercst, predictor_info[predictor].name);
2084	/* If the prediction for number of iterations is zero, do not
2085	predict the exit edges. */
2086	if (nitercst == 0)
2087	continue;
2088
2089	probability = RDIV (REG_BR_PROB_BASE, nitercst);
2090	predict_edge (e: ex, predictor, probability);
2091	}
2092
2093	/* Find information about loop bound variables. */
2094	for (nb_iter = loop->bounds; nb_iter;
2095	nb_iter = nb_iter->next)
2096	if (nb_iter->stmt
2097	&& gimple_code (g: nb_iter->stmt) == GIMPLE_COND)
2098	{
2099	stmt = as_a <gcond *> (p: nb_iter->stmt);
2100	break;
2101	}
2102	if (!stmt)
2103	stmt = safe_dyn_cast <gcond *> (p: *gsi_last_bb (bb: loop->header));
2104	if (stmt)
2105	is_comparison_with_loop_invariant_p (stmt, loop,
2106	loop_invariant: &loop_bound_var,
2107	compare_code: &loop_bound_code,
2108	loop_step: &loop_bound_step,
2109	loop_iv_base: &loop_iv_base);
2110
2111	bbs = get_loop_body (loop);
2112
2113	for (j = 0; j < loop->num_nodes; j++)
2114	{
2115	edge e;
2116	edge_iterator ei;
2117
2118	bb = bbs[j];
2119
2120	/* Bypass loop heuristics on continue statement. These
2121	statements construct loops via "non-loop" constructs
2122	in the source language and are better to be handled
2123	separately. */
2124	if (predicted_by_p (bb, predictor: PRED_CONTINUE))
2125	{
2126	if (dump_file && (dump_flags & TDF_DETAILS))
2127	fprintf (stream: dump_file, format: "BB %i predicted by continue.\n",
2128	bb->index);
2129	continue;
2130	}
2131
2132	/* If we already used more reliable loop exit predictors, do not
2133	bother with PRED_LOOP_EXIT. */
2134	if (!predicted_by_loop_heuristics_p (bb))
2135	{
2136	/* For loop with many exits we don't want to predict all exits
2137	with the pretty large probability, because if all exits are
2138	considered in row, the loop would be predicted to iterate
2139	almost never. The code to divide probability by number of
2140	exits is very rough. It should compute the number of exits
2141	taken in each patch through function (not the overall number
2142	of exits that might be a lot higher for loops with wide switch
2143	statements in them) and compute n-th square root.
2144
2145	We limit the minimal probability by 2% to avoid
2146	EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2147	as this was causing regression in perl benchmark containing such
2148	a wide loop. */
2149
2150	int probability = ((REG_BR_PROB_BASE
2151	- predictor_info
2152	[recursion
2153	? PRED_LOOP_EXIT_WITH_RECURSION
2154	: PRED_LOOP_EXIT].hitrate)
2155	/ n_exits);
2156	if (probability < HITRATE (2))
2157	probability = HITRATE (2);
2158	FOR_EACH_EDGE (e, ei, bb->succs)
2159	if (e->dest->index < NUM_FIXED_BLOCKS
2160	|| !flow_bb_inside_loop_p (loop, e->dest))
2161	{
2162	if (dump_file && (dump_flags & TDF_DETAILS))
2163	fprintf (stream: dump_file,
2164	format: "Predicting exit %i->%i with prob %i.\n",
2165	e->src->index, e->dest->index, probability);
2166	predict_edge (e,
2167	predictor: recursion ? PRED_LOOP_EXIT_WITH_RECURSION
2168	: PRED_LOOP_EXIT, probability);
2169	}
2170	}
2171	if (loop_bound_var)
2172	predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base_var: loop_iv_base,
2173	loop_bound_code,
2174	loop_bound_step: tree_to_shwi (loop_bound_step));
2175	}
2176
2177	/* In the following code
2178	for (loop1)
2179	if (cond)
2180	for (loop2)
2181	body;
2182	guess that cond is unlikely. */
2183	if (loop_outer (loop)->num)
2184	{
2185	basic_block bb = NULL;
2186	edge preheader_edge = loop_preheader_edge (loop);
2187
2188	if (single_pred_p (bb: preheader_edge->src)
2189	&& single_succ_p (bb: preheader_edge->src))
2190	preheader_edge = single_pred_edge (bb: preheader_edge->src);
2191
2192	/* Pattern match fortran loop preheader:
2193	_16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2194	_17 = (logical(kind=4)) _16;
2195	if (_17 != 0)
2196	goto <bb 11>;
2197	else
2198	goto <bb 13>;
2199
2200	Loop guard branch prediction says nothing about duplicated loop
2201	headers produced by fortran frontend and in this case we want
2202	to predict paths leading to this preheader. */
2203
2204	gcond *stmt
2205	= safe_dyn_cast <gcond *> (p: *gsi_last_bb (bb: preheader_edge->src));
2206	if (stmt
2207	&& gimple_cond_code (gs: stmt) == NE_EXPR
2208	&& TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
2209	&& integer_zerop (gimple_cond_rhs (gs: stmt)))
2210	{
2211	gimple *call_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
2212	if (gimple_code (g: call_stmt) == GIMPLE_ASSIGN
2213	&& CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (call_stmt))
2214	&& TREE_CODE (gimple_assign_rhs1 (call_stmt)) == SSA_NAME)
2215	call_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt));
2216	if (gimple_call_internal_p (gs: call_stmt, fn: IFN_BUILTIN_EXPECT)
2217	&& TREE_CODE (gimple_call_arg (call_stmt, 2)) == INTEGER_CST
2218	&& tree_fits_uhwi_p (gimple_call_arg (gs: call_stmt, index: 2))
2219	&& tree_to_uhwi (gimple_call_arg (gs: call_stmt, index: 2))
2220	== PRED_FORTRAN_LOOP_PREHEADER)
2221	bb = preheader_edge->src;
2222	}
2223	if (!bb)
2224	{
2225	if (!dominated_by_p (CDI_DOMINATORS,
2226	loop_outer (loop)->latch, loop->header))
2227	predict_paths_leading_to_edge (loop_preheader_edge (loop),
2228	recursion
2229	? PRED_LOOP_GUARD_WITH_RECURSION
2230	: PRED_LOOP_GUARD,
2231	NOT_TAKEN,
2232	in_loop: loop_outer (loop));
2233	}
2234	else
2235	{
2236	if (!dominated_by_p (CDI_DOMINATORS,
2237	loop_outer (loop)->latch, bb))
2238	predict_paths_leading_to (bb,
2239	recursion
2240	? PRED_LOOP_GUARD_WITH_RECURSION
2241	: PRED_LOOP_GUARD,
2242	NOT_TAKEN,
2243	in_loop: loop_outer (loop));
2244	}
2245	}
2246
2247	/* Free basic blocks from get_loop_body. */
2248	free (ptr: bbs);
2249	}
2250	}
2251
2252	/* Attempt to predict probabilities of BB outgoing edges using local
2253	properties. */
2254	static void
2255	bb_estimate_probability_locally (basic_block bb)
2256	{
2257	rtx_insn *last_insn = BB_END (bb);
2258	rtx cond;
2259
2260	if (! can_predict_insn_p (insn: last_insn))
2261	return;
2262	cond = get_condition (last_insn, NULL, false, false);
2263	if (! cond)
2264	return;
2265
2266	/* Try "pointer heuristic."
2267	A comparison ptr == 0 is predicted as false.
2268	Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2269	if (COMPARISON_P (cond)
2270	&& ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
2271	|| (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
2272	{
2273	if (GET_CODE (cond) == EQ)
2274	predict_insn_def (insn: last_insn, predictor: PRED_POINTER, taken: NOT_TAKEN);
2275	else if (GET_CODE (cond) == NE)
2276	predict_insn_def (insn: last_insn, predictor: PRED_POINTER, taken: TAKEN);
2277	}
2278	else
2279
2280	/* Try "opcode heuristic."
2281	EQ tests are usually false and NE tests are usually true. Also,
2282	most quantities are positive, so we can make the appropriate guesses
2283	about signed comparisons against zero. */
2284	switch (GET_CODE (cond))
2285	{
2286	case CONST_INT:
2287	/* Unconditional branch. */
2288	predict_insn_def (insn: last_insn, predictor: PRED_UNCONDITIONAL,
2289	taken: cond == const0_rtx ? NOT_TAKEN : TAKEN);
2290	break;
2291
2292	case EQ:
2293	case UNEQ:
2294	/* Floating point comparisons appears to behave in a very
2295	unpredictable way because of special role of = tests in
2296	FP code. */
2297	if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2298	;
2299	/* Comparisons with 0 are often used for booleans and there is
2300	nothing useful to predict about them. */
2301	else if (XEXP (cond, 1) == const0_rtx
2302	|| XEXP (cond, 0) == const0_rtx)
2303	;
2304	else
2305	predict_insn_def (insn: last_insn, predictor: PRED_OPCODE_NONEQUAL, taken: NOT_TAKEN);
2306	break;
2307
2308	case NE:
2309	case LTGT:
2310	/* Floating point comparisons appears to behave in a very
2311	unpredictable way because of special role of = tests in
2312	FP code. */
2313	if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2314	;
2315	/* Comparisons with 0 are often used for booleans and there is
2316	nothing useful to predict about them. */
2317	else if (XEXP (cond, 1) == const0_rtx
2318	|| XEXP (cond, 0) == const0_rtx)
2319	;
2320	else
2321	predict_insn_def (insn: last_insn, predictor: PRED_OPCODE_NONEQUAL, taken: TAKEN);
2322	break;
2323
2324	case ORDERED:
2325	predict_insn_def (insn: last_insn, predictor: PRED_FPOPCODE, taken: TAKEN);
2326	break;
2327
2328	case UNORDERED:
2329	predict_insn_def (insn: last_insn, predictor: PRED_FPOPCODE, taken: NOT_TAKEN);
2330	break;
2331
2332	case LE:
2333	case LT:
2334	if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2335	|| XEXP (cond, 1) == constm1_rtx)
2336	predict_insn_def (insn: last_insn, predictor: PRED_OPCODE_POSITIVE, taken: NOT_TAKEN);
2337	break;
2338
2339	case GE:
2340	case GT:
2341	if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2342	|| XEXP (cond, 1) == constm1_rtx)
2343	predict_insn_def (insn: last_insn, predictor: PRED_OPCODE_POSITIVE, taken: TAKEN);
2344	break;
2345
2346	default:
2347	break;
2348	}
2349	}
2350
2351	/* Set edge->probability for each successor edge of BB. */
2352	void
2353	guess_outgoing_edge_probabilities (basic_block bb)
2354	{
2355	bb_estimate_probability_locally (bb);
2356	combine_predictions_for_insn (BB_END (bb), bb);
2357	}
2358
2359	static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor,
2360	HOST_WIDE_INT *probability);
2361
2362	/* Helper function for expr_expected_value. */
2363
2364	static tree
2365	expr_expected_value_1 (tree type, tree op0, enum tree_code code,
2366	tree op1, bitmap visited, enum br_predictor *predictor,
2367	HOST_WIDE_INT *probability)
2368	{
2369	gimple *def;
2370
2371	/* Reset returned probability value. */
2372	*probability = -1;
2373	*predictor = PRED_UNCONDITIONAL;
2374
2375	if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2376	{
2377	if (TREE_CONSTANT (op0))
2378	return op0;
2379
2380	if (code == IMAGPART_EXPR)
2381	{
2382	if (TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
2383	{
2384	def = SSA_NAME_DEF_STMT (TREE_OPERAND (op0, 0));
2385	if (is_gimple_call (gs: def)
2386	&& gimple_call_internal_p (gs: def)
2387	&& (gimple_call_internal_fn (gs: def)
2388	== IFN_ATOMIC_COMPARE_EXCHANGE))
2389	{
2390	/* Assume that any given atomic operation has low contention,
2391	and thus the compare-and-swap operation succeeds. */
2392	*predictor = PRED_COMPARE_AND_SWAP;
2393	return build_one_cst (TREE_TYPE (op0));
2394	}
2395	}
2396	}
2397
2398	if (code != SSA_NAME)
2399	return NULL_TREE;
2400
2401	def = SSA_NAME_DEF_STMT (op0);
2402
2403	/* If we were already here, break the infinite cycle. */
2404	if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
2405	return NULL;
2406
2407	if (gphi *phi = dyn_cast <gphi *> (p: def))
2408	{
2409	/* All the arguments of the PHI node must have the same constant
2410	length. */
2411	int i, n = gimple_phi_num_args (gs: phi);
2412	tree val = NULL;
2413	bool has_nonzero_edge = false;
2414
2415	/* If we already proved that given edge is unlikely, we do not need
2416	to handle merging of the probabilities. */
2417	for (i = 0; i < n && !has_nonzero_edge; i++)
2418	{
2419	tree arg = PHI_ARG_DEF (phi, i);
2420	if (arg == PHI_RESULT (phi))
2421	continue;
2422	profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
2423	if (!cnt.initialized_p () || cnt.nonzero_p ())
2424	has_nonzero_edge = true;
2425	}
2426
2427	for (i = 0; i < n; i++)
2428	{
2429	tree arg = PHI_ARG_DEF (phi, i);
2430	enum br_predictor predictor2;
2431
2432	/* Skip self-referring parameters, since they does not change
2433	expected value. */
2434	if (arg == PHI_RESULT (phi))
2435	continue;
2436
2437	/* Skip edges which we already predicted as executing
2438	zero times. */
2439	if (has_nonzero_edge)
2440	{
2441	profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
2442	if (cnt.initialized_p () && !cnt.nonzero_p ())
2443	continue;
2444	}
2445	HOST_WIDE_INT probability2;
2446	tree new_val = expr_expected_value (arg, visited, predictor: &predictor2,
2447	probability: &probability2);
2448	/* If we know nothing about value, give up. */
2449	if (!new_val)
2450	return NULL;
2451
2452	/* If this is a first edge, trust its prediction. */
2453	if (!val)
2454	{
2455	val = new_val;
2456	*predictor = predictor2;
2457	*probability = probability2;
2458	continue;
2459	}
2460	/* If there are two different values, give up. */
2461	if (!operand_equal_p (val, new_val, flags: false))
2462	return NULL;
2463
2464	int p1 = get_predictor_value (*predictor, *probability);
2465	int p2 = get_predictor_value (predictor2, probability2);
2466	/* If both predictors agree, it does not matter from which
2467	edge we enter the basic block. */
2468	if (*predictor == predictor2 && p1 == p2)
2469	continue;
2470	/* The general case has no precise solution, since we do not
2471	know probabilities of incomming edges, yet.
2472	Still if value is predicted over all incomming edges, we
2473	can hope it will be indeed the case. Conservatively
2474	downgrade prediction quality (so first match merging is not
2475	performed) and take least successful prediction. */
2476
2477	*predictor = PRED_COMBINED_VALUE_PREDICTIONS_PHI;
2478	*probability = MIN (p1, p2);
2479	}
2480	return val;
2481	}
2482	if (is_gimple_assign (gs: def))
2483	{
2484	if (gimple_assign_lhs (gs: def) != op0)
2485	return NULL;
2486
2487	return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
2488	op0: gimple_assign_rhs1 (gs: def),
2489	code: gimple_assign_rhs_code (gs: def),
2490	op1: gimple_assign_rhs2 (gs: def),
2491	visited, predictor, probability);
2492	}
2493
2494	if (is_gimple_call (gs: def))
2495	{
2496	tree decl = gimple_call_fndecl (gs: def);
2497	if (!decl)
2498	{
2499	if (gimple_call_internal_p (gs: def)
2500	&& gimple_call_internal_fn (gs: def) == IFN_BUILTIN_EXPECT)
2501	{
2502	gcc_assert (gimple_call_num_args (def) == 3);
2503	tree val = gimple_call_arg (gs: def, index: 0);
2504	if (TREE_CONSTANT (val))
2505	return val;
2506	tree val2 = gimple_call_arg (gs: def, index: 2);
2507	gcc_assert (TREE_CODE (val2) == INTEGER_CST
2508	&& tree_fits_uhwi_p (val2)
2509	&& tree_to_uhwi (val2) < END_PREDICTORS);
2510	*predictor = (enum br_predictor) tree_to_uhwi (val2);
2511	if (*predictor == PRED_BUILTIN_EXPECT)
2512	*probability
2513	= HITRATE (param_builtin_expect_probability);
2514	return gimple_call_arg (gs: def, index: 1);
2515	}
2516	return NULL;
2517	}
2518
2519	if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW_P (decl))
2520	{
2521	if (predictor)
2522	*predictor = PRED_MALLOC_NONNULL;
2523	/* FIXME: This is wrong and we need to convert the logic
2524	to value ranges. This makes predictor to assume that
2525	malloc always returns (size_t)1 which is not the same
2526	as returning non-NULL. */
2527	return fold_convert (type, boolean_true_node);
2528	}
2529
2530	if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2531	switch (DECL_FUNCTION_CODE (decl))
2532	{
2533	case BUILT_IN_EXPECT:
2534	{
2535	tree val;
2536	if (gimple_call_num_args (gs: def) != 2)
2537	return NULL;
2538	val = gimple_call_arg (gs: def, index: 0);
2539	if (TREE_CONSTANT (val))
2540	return val;
2541	*predictor = PRED_BUILTIN_EXPECT;
2542	*probability
2543	= HITRATE (param_builtin_expect_probability);
2544	return gimple_call_arg (gs: def, index: 1);
2545	}
2546	case BUILT_IN_EXPECT_WITH_PROBABILITY:
2547	{
2548	tree val;
2549	if (gimple_call_num_args (gs: def) != 3)
2550	return NULL;
2551	val = gimple_call_arg (gs: def, index: 0);
2552	if (TREE_CONSTANT (val))
2553	return val;
2554	/* Compute final probability as:
2555	probability * REG_BR_PROB_BASE. */
2556	tree prob = gimple_call_arg (gs: def, index: 2);
2557	tree t = TREE_TYPE (prob);
2558	tree base = build_int_cst (integer_type_node,
2559	REG_BR_PROB_BASE);
2560	base = build_real_from_int_cst (t, base);
2561	tree r = fold_build2_initializer_loc (UNKNOWN_LOCATION,
2562	MULT_EXPR, t, prob, base);
2563	if (TREE_CODE (r) != REAL_CST)
2564	{
2565	error_at (gimple_location (g: def),
2566	"probability %qE must be "
2567	"constant floating-point expression", prob);
2568	return NULL;
2569	}
2570	HOST_WIDE_INT probi
2571	= real_to_integer (TREE_REAL_CST_PTR (r));
2572	if (probi >= 0 && probi <= REG_BR_PROB_BASE)
2573	{
2574	*predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
2575	*probability = probi;
2576	}
2577	else
2578	error_at (gimple_location (g: def),
2579	"probability %qE is outside "
2580	"the range [0.0, 1.0]", prob);
2581
2582	return gimple_call_arg (gs: def, index: 1);
2583	}
2584
2585	case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
2586	case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
2587	case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
2588	case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
2589	case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
2590	case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
2591	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
2592	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
2593	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
2594	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
2595	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
2596	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
2597	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
2598	/* Assume that any given atomic operation has low contention,
2599	and thus the compare-and-swap operation succeeds. */
2600	*predictor = PRED_COMPARE_AND_SWAP;
2601	return boolean_true_node;
2602	case BUILT_IN_REALLOC:
2603	case BUILT_IN_GOMP_REALLOC:
2604	if (predictor)
2605	*predictor = PRED_MALLOC_NONNULL;
2606	/* FIXME: This is wrong and we need to convert the logic
2607	to value ranges. */
2608	return fold_convert (type, boolean_true_node);
2609	default:
2610	break;
2611	}
2612	}
2613
2614	return NULL;
2615	}
2616
2617	if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2618	{
2619	tree res;
2620	tree nop0 = op0;
2621	tree nop1 = op1;
2622
2623	/* First handle situation where single op is enough to determine final
2624	value. In this case we can do better job by avoiding the prediction
2625	merging. */
2626	if (TREE_CODE (op0) != INTEGER_CST)
2627	{
2628	/* See if expected value of op0 is good enough to determine the result. */
2629	nop0 = expr_expected_value (op0, visited, predictor, probability);
2630	if (nop0
2631	&& (res = fold_build2 (code, type, nop0, op1)) != NULL
2632	&& TREE_CODE (res) == INTEGER_CST)
2633	/* We are now getting conservative probability. Consider for
2634	example:
2635	op0 * op1
2636	If op0 is 0 with probability p, then we will ignore the
2637	posibility that op0 != 0 and op1 == 0. It does not seem to be
2638	worthwhile to downgrade prediciton quality for this. */
2639	return res;
2640	if (!nop0)
2641	nop0 = op0;
2642	}
2643	enum br_predictor predictor2 = PRED_UNCONDITIONAL;
2644	HOST_WIDE_INT probability2 = -1;
2645	if (TREE_CODE (op1) != INTEGER_CST)
2646	{
2647	/* See if expected value of op1 is good enough to determine the result. */
2648	nop1 = expr_expected_value (op1, visited, predictor: &predictor2, probability: &probability2);
2649	if (nop1
2650	&& (res = fold_build2 (code, type, op0, nop1)) != NULL
2651	&& TREE_CODE (res) == INTEGER_CST)
2652	{
2653	/* Similarly as above we now get conservative probability. */
2654	*predictor = predictor2;
2655	*probability = probability2;
2656	return res;
2657	}
2658	if (!nop1)
2659	nop1 = op1;
2660	}
2661	/* We already checked if folding one of arguments to constant is good
2662	enough. Consequently failing to fold both means that we will not
2663	succeed determining the value. */
2664	if (nop0 == op0 || nop1 == op1)
2665	return NULL;
2666	/* Finally see if we have two known values. */
2667	res = fold_build2 (code, type, nop0, nop1);
2668	if (TREE_CODE (res) == INTEGER_CST)
2669	{
2670	HOST_WIDE_INT p1 = get_predictor_value (*predictor, *probability);
2671	HOST_WIDE_INT p2 = get_predictor_value (predictor2, probability2);
2672
2673	/* If one of predictions is sure, such as PRED_UNCONDITIONAL, we
2674	can ignore it. */
2675	if (p2 == PROB_ALWAYS)
2676	return res;
2677	if (p1 == PROB_ALWAYS)
2678	{
2679	*predictor = predictor2;
2680	*probability = probability2;
2681	return res;
2682	}
2683	/* Combine binary predictions.
2684	Since we do not know about independence of predictors, we
2685	can not determine value precisely. */
2686	*probability = RDIV (p1 * p2, REG_BR_PROB_BASE);
2687	/* If we no longer track useful information, give up. */
2688	if (!*probability)
2689	return NULL;
2690	/* Otherwise mark that prediction is a result of combining
2691	different heuristics, since we do not want it to participate
2692	in first match merging. It is no longer reliable since
2693	we do not know if the probabilities are indpenendet. */
2694	*predictor = PRED_COMBINED_VALUE_PREDICTIONS;
2695
2696	return res;
2697	}
2698	return NULL;
2699	}
2700	if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
2701	{
2702	tree res;
2703	op0 = expr_expected_value (op0, visited, predictor, probability);
2704	if (!op0)
2705	return NULL;
2706	res = fold_build1 (code, type, op0);
2707	if (TREE_CONSTANT (res))
2708	return res;
2709	return NULL;
2710	}
2711	return NULL;
2712	}
2713
2714	/* Return constant EXPR will likely have at execution time, NULL if unknown.
2715	The function is used by builtin_expect branch predictor so the evidence
2716	must come from this construct and additional possible constant folding.
2717
2718	We may want to implement more involved value guess (such as value range
2719	propagation based prediction), but such tricks shall go to new
2720	implementation. */
2721
2722	static tree
2723	expr_expected_value (tree expr, bitmap visited,
2724	enum br_predictor *predictor,
2725	HOST_WIDE_INT *probability)
2726	{
2727	enum tree_code code;
2728	tree op0, op1;
2729
2730	if (TREE_CONSTANT (expr))
2731	{
2732	*predictor = PRED_UNCONDITIONAL;
2733	*probability = -1;
2734	return expr;
2735	}
2736
2737	extract_ops_from_tree (expr, code: &code, op0: &op0, op1: &op1);
2738	return expr_expected_value_1 (TREE_TYPE (expr),
2739	op0, code, op1, visited, predictor,
2740	probability);
2741	}
2742
2743
2744	/* Return probability of a PREDICTOR. If the predictor has variable
2745	probability return passed PROBABILITY. */
2746
2747	static HOST_WIDE_INT
2748	get_predictor_value (br_predictor predictor, HOST_WIDE_INT probability)
2749	{
2750	switch (predictor)
2751	{
2752	case PRED_BUILTIN_EXPECT:
2753	case PRED_BUILTIN_EXPECT_WITH_PROBABILITY:
2754	case PRED_COMBINED_VALUE_PREDICTIONS_PHI:
2755	case PRED_COMBINED_VALUE_PREDICTIONS:
2756	gcc_assert (probability != -1);
2757	return probability;
2758	default:
2759	gcc_assert (probability == -1);
2760	return predictor_info[(int) predictor].hitrate;
2761	}
2762	}
2763
2764	/* Predict using opcode of the last statement in basic block. */
2765	static void
2766	tree_predict_by_opcode (basic_block bb)
2767	{
2768	edge then_edge;
2769	tree op0, op1;
2770	tree type;
2771	tree val;
2772	enum tree_code cmp;
2773	edge_iterator ei;
2774	enum br_predictor predictor;
2775	HOST_WIDE_INT probability;
2776
2777	gimple *stmt = *gsi_last_bb (bb);
2778	if (!stmt)
2779	return;
2780
2781	if (gswitch *sw = dyn_cast <gswitch *> (p: stmt))
2782	{
2783	tree index = gimple_switch_index (gs: sw);
2784	tree val = expr_expected_value (expr: index, visited: auto_bitmap (),
2785	predictor: &predictor, probability: &probability);
2786	if (val && TREE_CODE (val) == INTEGER_CST)
2787	{
2788	edge e = find_taken_edge_switch_expr (switch_stmt: sw, val);
2789	if (predictor == PRED_BUILTIN_EXPECT)
2790	{
2791	int percent = param_builtin_expect_probability;
2792	gcc_assert (percent >= 0 && percent <= 100);
2793	predict_edge (e, predictor: PRED_BUILTIN_EXPECT,
2794	HITRATE (percent));
2795	}
2796	else
2797	predict_edge_def (e, predictor, taken: TAKEN);
2798	}
2799	}
2800
2801	if (gimple_code (g: stmt) != GIMPLE_COND)
2802	return;
2803	FOR_EACH_EDGE (then_edge, ei, bb->succs)
2804	if (then_edge->flags & EDGE_TRUE_VALUE)
2805	break;
2806	op0 = gimple_cond_lhs (gs: stmt);
2807	op1 = gimple_cond_rhs (gs: stmt);
2808	cmp = gimple_cond_code (gs: stmt);
2809	type = TREE_TYPE (op0);
2810	val = expr_expected_value_1 (boolean_type_node, op0, code: cmp, op1, visited: auto_bitmap (),
2811	predictor: &predictor, probability: &probability);
2812	if (val && TREE_CODE (val) == INTEGER_CST)
2813	{
2814	HOST_WIDE_INT prob = get_predictor_value (predictor, probability);
2815	if (integer_zerop (val))
2816	prob = REG_BR_PROB_BASE - prob;
2817	predict_edge (e: then_edge, predictor, probability: prob);
2818	}
2819	/* Try "pointer heuristic."
2820	A comparison ptr == 0 is predicted as false.
2821	Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2822	if (POINTER_TYPE_P (type))
2823	{
2824	if (cmp == EQ_EXPR)
2825	predict_edge_def (e: then_edge, predictor: PRED_TREE_POINTER, taken: NOT_TAKEN);
2826	else if (cmp == NE_EXPR)
2827	predict_edge_def (e: then_edge, predictor: PRED_TREE_POINTER, taken: TAKEN);
2828	}
2829	else
2830
2831	/* Try "opcode heuristic."
2832	EQ tests are usually false and NE tests are usually true. Also,
2833	most quantities are positive, so we can make the appropriate guesses
2834	about signed comparisons against zero. */
2835	switch (cmp)
2836	{
2837	case EQ_EXPR:
2838	case UNEQ_EXPR:
2839	/* Floating point comparisons appears to behave in a very
2840	unpredictable way because of special role of = tests in
2841	FP code. */
2842	if (FLOAT_TYPE_P (type))
2843	;
2844	/* Comparisons with 0 are often used for booleans and there is
2845	nothing useful to predict about them. */
2846	else if (integer_zerop (op0) || integer_zerop (op1))
2847	;
2848	else
2849	predict_edge_def (e: then_edge, predictor: PRED_TREE_OPCODE_NONEQUAL, taken: NOT_TAKEN);
2850	break;
2851
2852	case NE_EXPR:
2853	case LTGT_EXPR:
2854	/* Floating point comparisons appears to behave in a very
2855	unpredictable way because of special role of = tests in
2856	FP code. */
2857	if (FLOAT_TYPE_P (type))
2858	;
2859	/* Comparisons with 0 are often used for booleans and there is
2860	nothing useful to predict about them. */
2861	else if (integer_zerop (op0)
2862	|| integer_zerop (op1))
2863	;
2864	else
2865	predict_edge_def (e: then_edge, predictor: PRED_TREE_OPCODE_NONEQUAL, taken: TAKEN);
2866	break;
2867
2868	case ORDERED_EXPR:
2869	predict_edge_def (e: then_edge, predictor: PRED_TREE_FPOPCODE, taken: TAKEN);
2870	break;
2871
2872	case UNORDERED_EXPR:
2873	predict_edge_def (e: then_edge, predictor: PRED_TREE_FPOPCODE, taken: NOT_TAKEN);
2874	break;
2875
2876	case LE_EXPR:
2877	case LT_EXPR:
2878	if (integer_zerop (op1)
2879	|| integer_onep (op1)
2880	|| integer_all_onesp (op1)
2881	|| real_zerop (op1)
2882	|| real_onep (op1)
2883	|| real_minus_onep (op1))
2884	predict_edge_def (e: then_edge, predictor: PRED_TREE_OPCODE_POSITIVE, taken: NOT_TAKEN);
2885	break;
2886
2887	case GE_EXPR:
2888	case GT_EXPR:
2889	if (integer_zerop (op1)
2890	|| integer_onep (op1)
2891	|| integer_all_onesp (op1)
2892	|| real_zerop (op1)
2893	|| real_onep (op1)
2894	|| real_minus_onep (op1))
2895	predict_edge_def (e: then_edge, predictor: PRED_TREE_OPCODE_POSITIVE, taken: TAKEN);
2896	break;
2897
2898	default:
2899	break;
2900	}
2901	}
2902
2903	/* Returns TRUE if the STMT is exit(0) like statement. */
2904
2905	static bool
2906	is_exit_with_zero_arg (const gimple *stmt)
2907	{
2908	/* This is not exit, _exit or _Exit. */
2909	if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
2910	&& !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
2911	&& !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
2912	return false;
2913
2914	/* Argument is an interger zero. */
2915	return integer_zerop (gimple_call_arg (gs: stmt, index: 0));
2916	}
2917
2918	/* Try to guess whether the value of return means error code. */
2919
2920	static enum br_predictor
2921	return_prediction (tree val, enum prediction *prediction)
2922	{
2923	/* VOID. */
2924	if (!val)
2925	return PRED_NO_PREDICTION;
2926	/* Different heuristics for pointers and scalars. */
2927	if (POINTER_TYPE_P (TREE_TYPE (val)))
2928	{
2929	/* NULL is usually not returned. */
2930	if (integer_zerop (val))
2931	{
2932	*prediction = NOT_TAKEN;
2933	return PRED_NULL_RETURN;
2934	}
2935	}
2936	else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
2937	{
2938	/* Negative return values are often used to indicate
2939	errors. */
2940	if (TREE_CODE (val) == INTEGER_CST
2941	&& tree_int_cst_sgn (val) < 0)
2942	{
2943	*prediction = NOT_TAKEN;
2944	return PRED_NEGATIVE_RETURN;
2945	}
2946	/* Constant return values seems to be commonly taken.
2947	Zero/one often represent booleans so exclude them from the
2948	heuristics. */
2949	if (TREE_CONSTANT (val)
2950	&& (!integer_zerop (val) && !integer_onep (val)))
2951	{
2952	*prediction = NOT_TAKEN;
2953	return PRED_CONST_RETURN;
2954	}
2955	}
2956	return PRED_NO_PREDICTION;
2957	}
2958
2959	/* Return zero if phi result could have values other than -1, 0 or 1,
2960	otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2961	values are used or likely. */
2962
2963	static int
2964	zero_one_minusone (gphi *phi, int limit)
2965	{
2966	int phi_num_args = gimple_phi_num_args (gs: phi);
2967	int ret = 0;
2968	for (int i = 0; i < phi_num_args; i++)
2969	{
2970	tree t = PHI_ARG_DEF (phi, i);
2971	if (TREE_CODE (t) != INTEGER_CST)
2972	continue;
2973	wide_int w = wi::to_wide (t);
2974	if (w == -1)
2975	ret |= 1;
2976	else if (w == 0)
2977	ret |= 2;
2978	else if (w == 1)
2979	ret |= 4;
2980	else
2981	return 0;
2982	}
2983	for (int i = 0; i < phi_num_args; i++)
2984	{
2985	tree t = PHI_ARG_DEF (phi, i);
2986	if (TREE_CODE (t) == INTEGER_CST)
2987	continue;
2988	if (TREE_CODE (t) != SSA_NAME)
2989	return 0;
2990	gimple *g = SSA_NAME_DEF_STMT (t);
2991	if (gimple_code (g) == GIMPLE_PHI && limit > 0)
2992	if (int r = zero_one_minusone (phi: as_a <gphi *> (p: g), limit: limit - 1))
2993	{
2994	ret |= r;
2995	continue;
2996	}
2997	if (!is_gimple_assign (gs: g))
2998	return 0;
2999	if (gimple_assign_cast_p (s: g))
3000	{
3001	tree rhs1 = gimple_assign_rhs1 (gs: g);
3002	if (TREE_CODE (rhs1) != SSA_NAME
3003	|| !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
3004	|| TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
3005	|| !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
3006	return 0;
3007	ret |= (2 | 4);
3008	continue;
3009	}
3010	if (TREE_CODE_CLASS (gimple_assign_rhs_code (g)) != tcc_comparison)
3011	return 0;
3012	ret |= (2 | 4);
3013	}
3014	return ret;
3015	}
3016
3017	/* Find the basic block with return expression and look up for possible
3018	return value trying to apply RETURN_PREDICTION heuristics. */
3019	static void
3020	apply_return_prediction (void)
3021	{
3022	greturn *return_stmt = NULL;
3023	tree return_val;
3024	edge e;
3025	gphi *phi;
3026	int phi_num_args, i;
3027	enum br_predictor pred;
3028	enum prediction direction;
3029	edge_iterator ei;
3030
3031	FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
3032	{
3033	if (greturn *last = safe_dyn_cast <greturn *> (p: *gsi_last_bb (bb: e->src)))
3034	{
3035	return_stmt = last;
3036	break;
3037	}
3038	}
3039	if (!e)
3040	return;
3041	return_val = gimple_return_retval (gs: return_stmt);
3042	if (!return_val)
3043	return;
3044	if (TREE_CODE (return_val) != SSA_NAME
3045	|| !SSA_NAME_DEF_STMT (return_val)
3046	|| gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
3047	return;
3048	phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
3049	phi_num_args = gimple_phi_num_args (gs: phi);
3050	pred = return_prediction (PHI_ARG_DEF (phi, 0), prediction: &direction);
3051
3052	/* Avoid the case where the function returns -1, 0 and 1 values and
3053	nothing else. Those could be qsort etc. comparison functions
3054	where the negative return isn't less probable than positive.
3055	For this require that the function returns at least -1 or 1
3056	or -1 and a boolean value or comparison result, so that functions
3057	returning just -1 and 0 are treated as if -1 represents error value. */
3058	if (INTEGRAL_TYPE_P (TREE_TYPE (return_val))
3059	&& !TYPE_UNSIGNED (TREE_TYPE (return_val))
3060	&& TYPE_PRECISION (TREE_TYPE (return_val)) > 1)
3061	if (int r = zero_one_minusone (phi, limit: 3))
3062	if ((r & (1 | 4)) == (1 | 4))
3063	return;
3064
3065	/* Avoid the degenerate case where all return values form the function
3066	belongs to same category (ie they are all positive constants)
3067	so we can hardly say something about them. */
3068	for (i = 1; i < phi_num_args; i++)
3069	if (pred != return_prediction (PHI_ARG_DEF (phi, i), prediction: &direction))
3070	break;
3071	if (i != phi_num_args)
3072	for (i = 0; i < phi_num_args; i++)
3073	{
3074	pred = return_prediction (PHI_ARG_DEF (phi, i), prediction: &direction);
3075	if (pred != PRED_NO_PREDICTION)
3076	predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
3077	direction);
3078	}
3079	}
3080
3081	/* Look for basic block that contains unlikely to happen events
3082	(such as noreturn calls) and mark all paths leading to execution
3083	of this basic blocks as unlikely. */
3084
3085	static void
3086	tree_bb_level_predictions (void)
3087	{
3088	basic_block bb;
3089	bool has_return_edges = false;
3090	edge e;
3091	edge_iterator ei;
3092
3093	FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
3094	if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
3095	{
3096	has_return_edges = true;
3097	break;
3098	}
3099
3100	apply_return_prediction ();
3101
3102	FOR_EACH_BB_FN (bb, cfun)
3103	{
3104	gimple_stmt_iterator gsi;
3105
3106	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
3107	{
3108	gimple *stmt = gsi_stmt (i: gsi);
3109	tree decl;
3110
3111	if (is_gimple_call (gs: stmt))
3112	{
3113	if (gimple_call_noreturn_p (s: stmt)
3114	&& has_return_edges
3115	&& !is_exit_with_zero_arg (stmt))
3116	predict_paths_leading_to (bb, PRED_NORETURN,
3117	NOT_TAKEN);
3118	decl = gimple_call_fndecl (gs: stmt);
3119	if (decl
3120	&& lookup_attribute (attr_name: "cold",
3121	DECL_ATTRIBUTES (decl)))
3122	predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
3123	NOT_TAKEN);
3124	if (decl && recursive_call_p (current_function_decl, decl))
3125	predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
3126	NOT_TAKEN);
3127	}
3128	else if (gimple_code (g: stmt) == GIMPLE_PREDICT)
3129	{
3130	predict_paths_leading_to (bb, gimple_predict_predictor (gs: stmt),
3131	gimple_predict_outcome (gs: stmt));
3132	/* Keep GIMPLE_PREDICT around so early inlining will propagate
3133	hints to callers. */
3134	}
3135	}
3136	}
3137	}
3138
3139	/* Callback for hash_map::traverse, asserts that the pointer map is
3140	empty. */
3141
3142	bool
3143	assert_is_empty (const_basic_block const &, edge_prediction *const &value,
3144	void *)
3145	{
3146	gcc_assert (!value);
3147	return true;
3148	}
3149
3150	/* Predict branch probabilities and estimate profile for basic block BB.
3151	When LOCAL_ONLY is set do not use any global properties of CFG. */
3152
3153	static void
3154	tree_estimate_probability_bb (basic_block bb, bool local_only)
3155	{
3156	edge e;
3157	edge_iterator ei;
3158
3159	FOR_EACH_EDGE (e, ei, bb->succs)
3160	{
3161	/* Look for block we are guarding (ie we dominate it,
3162	but it doesn't postdominate us). */
3163	if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
3164	&& !local_only
3165	&& dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
3166	&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
3167	{
3168	gimple_stmt_iterator bi;
3169
3170	/* The call heuristic claims that a guarded function call
3171	is improbable. This is because such calls are often used
3172	to signal exceptional situations such as printing error
3173	messages. */
3174	for (bi = gsi_start_bb (bb: e->dest); !gsi_end_p (i: bi);
3175	gsi_next (i: &bi))
3176	{
3177	gimple *stmt = gsi_stmt (i: bi);
3178	if (is_gimple_call (gs: stmt)
3179	&& !gimple_inexpensive_call_p (as_a <gcall *> (p: stmt))
3180	/* Constant and pure calls are hardly used to signalize
3181	something exceptional. */
3182	&& gimple_has_side_effects (stmt))
3183	{
3184	if (gimple_call_fndecl (gs: stmt))
3185	predict_edge_def (e, predictor: PRED_CALL, taken: NOT_TAKEN);
3186	else if (virtual_method_call_p (gimple_call_fn (gs: stmt)))
3187	predict_edge_def (e, predictor: PRED_POLYMORPHIC_CALL, taken: NOT_TAKEN);
3188	else
3189	predict_edge_def (e, predictor: PRED_INDIR_CALL, taken: TAKEN);
3190	break;
3191	}
3192	}
3193	}
3194	}
3195	tree_predict_by_opcode (bb);
3196	}
3197
3198	/* Predict branch probabilities and estimate profile of the tree CFG.
3199	This function can be called from the loop optimizers to recompute
3200	the profile information.
3201	If DRY_RUN is set, do not modify CFG and only produce dump files. */
3202
3203	void
3204	tree_estimate_probability (bool dry_run)
3205	{
3206	basic_block bb;
3207
3208	connect_infinite_loops_to_exit ();
3209	/* We use loop_niter_by_eval, which requires that the loops have
3210	preheaders. */
3211	create_preheaders (CP_SIMPLE_PREHEADERS);
3212	calculate_dominance_info (CDI_POST_DOMINATORS);
3213	/* Decide which edges are known to be unlikely. This improves later
3214	branch prediction. */
3215	determine_unlikely_bbs ();
3216
3217	bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3218	tree_bb_level_predictions ();
3219	record_loop_exits ();
3220
3221	if (number_of_loops (cfun) > 1)
3222	predict_loops ();
3223
3224	FOR_EACH_BB_FN (bb, cfun)
3225	tree_estimate_probability_bb (bb, local_only: false);
3226
3227	FOR_EACH_BB_FN (bb, cfun)
3228	combine_predictions_for_bb (bb, dry_run);
3229
3230	if (flag_checking)
3231	bb_predictions->traverse<void *, assert_is_empty> (NULL);
3232
3233	delete bb_predictions;
3234	bb_predictions = NULL;
3235
3236	if (!dry_run
3237	&& profile_status_for_fn (cfun) != PROFILE_READ)
3238	estimate_bb_frequencies ();
3239	free_dominance_info (CDI_POST_DOMINATORS);
3240	remove_fake_exit_edges ();
3241	}
3242
3243	/* Set edge->probability for each successor edge of BB. */
3244	void
3245	tree_guess_outgoing_edge_probabilities (basic_block bb)
3246	{
3247	bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3248	tree_estimate_probability_bb (bb, local_only: true);
3249	combine_predictions_for_bb (bb, dry_run: false);
3250	if (flag_checking)
3251	bb_predictions->traverse<void *, assert_is_empty> (NULL);
3252	delete bb_predictions;
3253	bb_predictions = NULL;
3254	}
3255
3256	/* Filter function predicate that returns true for a edge predicate P
3257	if its edge is equal to DATA. */
3258
3259	static bool
3260	not_loop_guard_equal_edge_p (edge_prediction *p, void *data)
3261	{
3262	return p->ep_edge != (edge)data || p->ep_predictor != PRED_LOOP_GUARD;
3263	}
3264
3265	/* Predict edge E with PRED unless it is already predicted by some predictor
3266	considered equivalent. */
3267
3268	static void
3269	maybe_predict_edge (edge e, enum br_predictor pred, enum prediction taken)
3270	{
3271	if (edge_predicted_by_p (e, predictor: pred, taken))
3272	return;
3273	if (pred == PRED_LOOP_GUARD
3274	&& edge_predicted_by_p (e, predictor: PRED_LOOP_GUARD_WITH_RECURSION, taken))
3275	return;
3276	/* Consider PRED_LOOP_GUARD_WITH_RECURSION superrior to LOOP_GUARD. */
3277	if (pred == PRED_LOOP_GUARD_WITH_RECURSION)
3278	{
3279	edge_prediction **preds = bb_predictions->get (k: e->src);
3280	if (preds)
3281	filter_predictions (preds, filter: not_loop_guard_equal_edge_p, data: e);
3282	}
3283	predict_edge_def (e, predictor: pred, taken);
3284	}
3285	/* Predict edges to successors of CUR whose sources are not postdominated by
3286	BB by PRED and recurse to all postdominators. */
3287
3288	static void
3289	predict_paths_for_bb (basic_block cur, basic_block bb,
3290	enum br_predictor pred,
3291	enum prediction taken,
3292	bitmap visited, class loop *in_loop = NULL)
3293	{
3294	edge e;
3295	edge_iterator ei;
3296	basic_block son;
3297
3298	/* If we exited the loop or CUR is unconditional in the loop, there is
3299	nothing to do. */
3300	if (in_loop
3301	&& (!flow_bb_inside_loop_p (in_loop, cur)
3302	|| dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
3303	return;
3304
3305	/* We are looking for all edges forming edge cut induced by
3306	set of all blocks postdominated by BB. */
3307	FOR_EACH_EDGE (e, ei, cur->preds)
3308	if (e->src->index >= NUM_FIXED_BLOCKS
3309	&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
3310	{
3311	edge e2;
3312	edge_iterator ei2;
3313	bool found = false;
3314
3315	/* Ignore fake edges and eh, we predict them as not taken anyway. */
3316	if (unlikely_executed_edge_p (e))
3317	continue;
3318	gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
3319
3320	/* See if there is an edge from e->src that is not abnormal
3321	and does not lead to BB and does not exit the loop. */
3322	FOR_EACH_EDGE (e2, ei2, e->src->succs)
3323	if (e2 != e
3324	&& !unlikely_executed_edge_p (e: e2)
3325	&& !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
3326	&& (!in_loop || !loop_exit_edge_p (in_loop, e2)))
3327	{
3328	found = true;
3329	break;
3330	}
3331
3332	/* If there is non-abnormal path leaving e->src, predict edge
3333	using predictor. Otherwise we need to look for paths
3334	leading to e->src.
3335
3336	The second may lead to infinite loop in the case we are predicitng
3337	regions that are only reachable by abnormal edges. We simply
3338	prevent visiting given BB twice. */
3339	if (found)
3340	maybe_predict_edge (e, pred, taken);
3341	else if (bitmap_set_bit (visited, e->src->index))
3342	predict_paths_for_bb (cur: e->src, bb: e->src, pred, taken, visited, in_loop);
3343	}
3344	for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
3345	son;
3346	son = next_dom_son (CDI_POST_DOMINATORS, son))
3347	predict_paths_for_bb (cur: son, bb, pred, taken, visited, in_loop);
3348	}
3349
3350	/* Sets branch probabilities according to PREDiction and
3351	FLAGS. */
3352
3353	static void
3354	predict_paths_leading_to (basic_block bb, enum br_predictor pred,
3355	enum prediction taken, class loop *in_loop)
3356	{
3357	predict_paths_for_bb (cur: bb, bb, pred, taken, visited: auto_bitmap (), in_loop);
3358	}
3359
3360	/* Like predict_paths_leading_to but take edge instead of basic block. */
3361
3362	static void
3363	predict_paths_leading_to_edge (edge e, enum br_predictor pred,
3364	enum prediction taken, class loop *in_loop)
3365	{
3366	bool has_nonloop_edge = false;
3367	edge_iterator ei;
3368	edge e2;
3369
3370	basic_block bb = e->src;
3371	FOR_EACH_EDGE (e2, ei, bb->succs)
3372	if (e2->dest != e->src && e2->dest != e->dest
3373	&& !unlikely_executed_edge_p (e: e2)
3374	&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
3375	{
3376	has_nonloop_edge = true;
3377	break;
3378	}
3379
3380	if (!has_nonloop_edge)
3381	predict_paths_for_bb (cur: bb, bb, pred, taken, visited: auto_bitmap (), in_loop);
3382	else
3383	maybe_predict_edge (e, pred, taken);
3384	}
3385
3386	/* This is used to carry information about basic blocks. It is
3387	attached to the AUX field of the standard CFG block. */
3388
3389	class block_info
3390	{
3391	public:
3392	/* Estimated frequency of execution of basic_block. */
3393	sreal frequency;
3394
3395	/* To keep queue of basic blocks to process. */
3396	basic_block next;
3397
3398	/* Number of predecessors we need to visit first. */
3399	int npredecessors;
3400	};
3401
3402	/* Similar information for edges. */
3403	class edge_prob_info
3404	{
3405	public:
3406	/* In case edge is a loopback edge, the probability edge will be reached
3407	in case header is. Estimated number of iterations of the loop can be
3408	then computed as 1 / (1 - back_edge_prob). */
3409	sreal back_edge_prob;
3410	/* True if the edge is a loopback edge in the natural loop. */
3411	unsigned int back_edge:1;
3412	};
3413
3414	#define BLOCK_INFO(B) ((block_info *) (B)->aux)
3415	#undef EDGE_INFO
3416	#define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3417
3418	/* Helper function for estimate_bb_frequencies.
3419	Propagate the frequencies in blocks marked in
3420	TOVISIT, starting in HEAD. */
3421
3422	static void
3423	propagate_freq (basic_block head, bitmap tovisit,
3424	sreal max_cyclic_prob)
3425	{
3426	basic_block bb;
3427	basic_block last;
3428	unsigned i;
3429	edge e;
3430	basic_block nextbb;
3431	bitmap_iterator bi;
3432
3433	/* For each basic block we need to visit count number of his predecessors
3434	we need to visit first. */
3435	EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
3436	{
3437	edge_iterator ei;
3438	int count = 0;
3439
3440	bb = BASIC_BLOCK_FOR_FN (cfun, i);
3441
3442	FOR_EACH_EDGE (e, ei, bb->preds)
3443	{
3444	bool visit = bitmap_bit_p (tovisit, e->src->index);
3445
3446	if (visit && !(e->flags & EDGE_DFS_BACK))
3447	count++;
3448	else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
3449	fprintf (stream: dump_file,
3450	format: "Irreducible region hit, ignoring edge to %i->%i\n",
3451	e->src->index, bb->index);
3452	}
3453	BLOCK_INFO (bb)->npredecessors = count;
3454	/* When function never returns, we will never process exit block. */
3455	if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
3456	bb->count = profile_count::zero ();
3457	}
3458
3459	BLOCK_INFO (head)->frequency = 1;
3460	last = head;
3461	for (bb = head; bb; bb = nextbb)
3462	{
3463	edge_iterator ei;
3464	sreal cyclic_probability = 0;
3465	sreal frequency = 0;
3466
3467	nextbb = BLOCK_INFO (bb)->next;
3468	BLOCK_INFO (bb)->next = NULL;
3469
3470	/* Compute frequency of basic block. */
3471	if (bb != head)
3472	{
3473	if (flag_checking)
3474	FOR_EACH_EDGE (e, ei, bb->preds)
3475	gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
3476	|| (e->flags & EDGE_DFS_BACK));
3477
3478	FOR_EACH_EDGE (e, ei, bb->preds)
3479	if (EDGE_INFO (e)->back_edge)
3480	cyclic_probability += EDGE_INFO (e)->back_edge_prob;
3481	else if (!(e->flags & EDGE_DFS_BACK))
3482	{
3483	/* FIXME: Graphite is producing edges with no profile. Once
3484	this is fixed, drop this. */
3485	sreal tmp = e->probability.initialized_p () ?
3486	e->probability.to_sreal () : 0;
3487	frequency += tmp * BLOCK_INFO (e->src)->frequency;
3488	}
3489
3490	if (cyclic_probability == 0)
3491	{
3492	BLOCK_INFO (bb)->frequency = frequency;
3493	}
3494	else
3495	{
3496	if (cyclic_probability > max_cyclic_prob)
3497	{
3498	if (dump_file)
3499	fprintf (stream: dump_file,
3500	format: "cyclic probability of bb %i is %f (capped to %f)"
3501	"; turning freq %f",
3502	bb->index, cyclic_probability.to_double (),
3503	max_cyclic_prob.to_double (),
3504	frequency.to_double ());
3505
3506	cyclic_probability = max_cyclic_prob;
3507	}
3508	else if (dump_file)
3509	fprintf (stream: dump_file,
3510	format: "cyclic probability of bb %i is %f; turning freq %f",
3511	bb->index, cyclic_probability.to_double (),
3512	frequency.to_double ());
3513
3514	BLOCK_INFO (bb)->frequency = frequency
3515	/ (sreal (1) - cyclic_probability);
3516	if (dump_file)
3517	fprintf (stream: dump_file, format: " to %f\n",
3518	BLOCK_INFO (bb)->frequency.to_double ());
3519	}
3520	}
3521
3522	bitmap_clear_bit (tovisit, bb->index);
3523
3524	e = find_edge (bb, head);
3525	if (e)
3526	{
3527	/* FIXME: Graphite is producing edges with no profile. Once
3528	this is fixed, drop this. */
3529	sreal tmp = e->probability.initialized_p () ?
3530	e->probability.to_sreal () : 0;
3531	EDGE_INFO (e)->back_edge_prob = tmp * BLOCK_INFO (bb)->frequency;
3532	}
3533
3534	/* Propagate to successor blocks. */
3535	FOR_EACH_EDGE (e, ei, bb->succs)
3536	if (!(e->flags & EDGE_DFS_BACK)
3537	&& BLOCK_INFO (e->dest)->npredecessors)
3538	{
3539	BLOCK_INFO (e->dest)->npredecessors--;
3540	if (!BLOCK_INFO (e->dest)->npredecessors)
3541	{
3542	if (!nextbb)
3543	nextbb = e->dest;
3544	else
3545	BLOCK_INFO (last)->next = e->dest;
3546
3547	last = e->dest;
3548	}
3549	}
3550	}
3551	}
3552
3553	/* Estimate frequencies in loops at same nest level. */
3554
3555	static void
3556	estimate_loops_at_level (class loop *first_loop, sreal max_cyclic_prob)
3557	{
3558	class loop *loop;
3559
3560	for (loop = first_loop; loop; loop = loop->next)
3561	{
3562	edge e;
3563	basic_block *bbs;
3564	unsigned i;
3565	auto_bitmap tovisit;
3566
3567	estimate_loops_at_level (first_loop: loop->inner, max_cyclic_prob);
3568
3569	/* Find current loop back edge and mark it. */
3570	e = loop_latch_edge (loop);
3571	EDGE_INFO (e)->back_edge = 1;
3572
3573	bbs = get_loop_body (loop);
3574	for (i = 0; i < loop->num_nodes; i++)
3575	bitmap_set_bit (tovisit, bbs[i]->index);
3576	free (ptr: bbs);
3577	propagate_freq (head: loop->header, tovisit, max_cyclic_prob);
3578	}
3579	}
3580
3581	/* Propagates frequencies through structure of loops. */
3582
3583	static void
3584	estimate_loops (void)
3585	{
3586	auto_bitmap tovisit;
3587	basic_block bb;
3588	sreal max_cyclic_prob = (sreal)1
3589	- (sreal)1 / (param_max_predicted_iterations + 1);
3590
3591	/* Start by estimating the frequencies in the loops. */
3592	if (number_of_loops (cfun) > 1)
3593	estimate_loops_at_level (current_loops->tree_root->inner, max_cyclic_prob);
3594
3595	/* Now propagate the frequencies through all the blocks. */
3596	FOR_ALL_BB_FN (bb, cfun)
3597	{
3598	bitmap_set_bit (tovisit, bb->index);
3599	}
3600	propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit, max_cyclic_prob);
3601	}
3602
3603	/* Drop the profile for NODE to guessed, and update its frequency based on
3604	whether it is expected to be hot given the CALL_COUNT. */
3605
3606	static void
3607	drop_profile (struct cgraph_node *node, profile_count call_count)
3608	{
3609	struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3610	/* In the case where this was called by another function with a
3611	dropped profile, call_count will be 0. Since there are no
3612	non-zero call counts to this function, we don't know for sure
3613	whether it is hot, and therefore it will be marked normal below. */
3614	bool hot = maybe_hot_count_p (NULL, count: call_count);
3615
3616	if (dump_file)
3617	fprintf (stream: dump_file,
3618	format: "Dropping 0 profile for %s. %s based on calls.\n",
3619	node->dump_name (),
3620	hot ? "Function is hot" : "Function is normal");
3621	/* We only expect to miss profiles for functions that are reached
3622	via non-zero call edges in cases where the function may have
3623	been linked from another module or library (COMDATs and extern
3624	templates). See the comments below for handle_missing_profiles.
3625	Also, only warn in cases where the missing counts exceed the
3626	number of training runs. In certain cases with an execv followed
3627	by a no-return call the profile for the no-return call is not
3628	dumped and there can be a mismatch. */
3629	if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
3630	&& call_count > profile_info->runs)
3631	{
3632	if (flag_profile_correction)
3633	{
3634	if (dump_file)
3635	fprintf (stream: dump_file,
3636	format: "Missing counts for called function %s\n",
3637	node->dump_name ());
3638	}
3639	else
3640	warning (0, "Missing counts for called function %s",
3641	node->dump_name ());
3642	}
3643
3644	basic_block bb;
3645	if (opt_for_fn (node->decl, flag_guess_branch_prob))
3646	{
3647	bool clear_zeros
3648	= !ENTRY_BLOCK_PTR_FOR_FN (fn)->count.nonzero_p ();
3649	FOR_ALL_BB_FN (bb, fn)
3650	if (clear_zeros || !(bb->count == profile_count::zero ()))
3651	bb->count = bb->count.guessed_local ();
3652	fn->cfg->count_max = fn->cfg->count_max.guessed_local ();
3653	}
3654	else
3655	{
3656	FOR_ALL_BB_FN (bb, fn)
3657	bb->count = profile_count::uninitialized ();
3658	fn->cfg->count_max = profile_count::uninitialized ();
3659	}
3660
3661	struct cgraph_edge *e;
3662	for (e = node->callees; e; e = e->next_callee)
3663	e->count = gimple_bb (g: e->call_stmt)->count;
3664	for (e = node->indirect_calls; e; e = e->next_callee)
3665	e->count = gimple_bb (g: e->call_stmt)->count;
3666	node->count = ENTRY_BLOCK_PTR_FOR_FN (fn)->count;
3667
3668	profile_status_for_fn (fn)
3669	= (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
3670	node->frequency
3671	= hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
3672	}
3673
3674	/* In the case of COMDAT routines, multiple object files will contain the same
3675	function and the linker will select one for the binary. In that case
3676	all the other copies from the profile instrument binary will be missing
3677	profile counts. Look for cases where this happened, due to non-zero
3678	call counts going to 0-count functions, and drop the profile to guessed
3679	so that we can use the estimated probabilities and avoid optimizing only
3680	for size.
3681
3682	The other case where the profile may be missing is when the routine
3683	is not going to be emitted to the object file, e.g. for "extern template"
3684	class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3685	all other cases of non-zero calls to 0-count functions. */
3686
3687	void
3688	handle_missing_profiles (void)
3689	{
3690	const int unlikely_frac = param_unlikely_bb_count_fraction;
3691	struct cgraph_node *node;
3692	auto_vec<struct cgraph_node *, 64> worklist;
3693
3694	/* See if 0 count function has non-0 count callers. In this case we
3695	lost some profile. Drop its function profile to PROFILE_GUESSED. */
3696	FOR_EACH_DEFINED_FUNCTION (node)
3697	{
3698	struct cgraph_edge *e;
3699	profile_count call_count = profile_count::zero ();
3700	gcov_type max_tp_first_run = 0;
3701	struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3702
3703	if (node->count.ipa ().nonzero_p ())
3704	continue;
3705	for (e = node->callers; e; e = e->next_caller)
3706	if (e->count.ipa ().initialized_p () && e->count.ipa () > 0)
3707	{
3708	call_count = call_count + e->count.ipa ();
3709
3710	if (e->caller->tp_first_run > max_tp_first_run)
3711	max_tp_first_run = e->caller->tp_first_run;
3712	}
3713
3714	/* If time profile is missing, let assign the maximum that comes from
3715	caller functions. */
3716	if (!node->tp_first_run && max_tp_first_run)
3717	node->tp_first_run = max_tp_first_run + 1;
3718
3719	if (call_count > 0
3720	&& fn && fn->cfg
3721	&& call_count * unlikely_frac >= profile_info->runs)
3722	{
3723	drop_profile (node, call_count);
3724	worklist.safe_push (obj: node);
3725	}
3726	}
3727
3728	/* Propagate the profile dropping to other 0-count COMDATs that are
3729	potentially called by COMDATs we already dropped the profile on. */
3730	while (worklist.length () > 0)
3731	{
3732	struct cgraph_edge *e;
3733
3734	node = worklist.pop ();
3735	for (e = node->callees; e; e = e->next_caller)
3736	{
3737	struct cgraph_node *callee = e->callee;
3738	struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
3739
3740	if (!(e->count.ipa () == profile_count::zero ())
3741	&& callee->count.ipa ().nonzero_p ())
3742	continue;
3743	if ((DECL_COMDAT (callee->decl) || DECL_EXTERNAL (callee->decl))
3744	&& fn && fn->cfg
3745	&& profile_status_for_fn (fn) == PROFILE_READ)
3746	{
3747	drop_profile (node, call_count: profile_count::zero ());
3748	worklist.safe_push (obj: callee);
3749	}
3750	}
3751	}
3752	}
3753
3754	/* Convert counts measured by profile driven feedback to frequencies.
3755	Return nonzero iff there was any nonzero execution count. */
3756
3757	bool
3758	update_max_bb_count (void)
3759	{
3760	profile_count true_count_max = profile_count::uninitialized ();
3761	basic_block bb;
3762
3763	FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3764	true_count_max = true_count_max.max (other: bb->count);
3765
3766	cfun->cfg->count_max = true_count_max;
3767
3768	return true_count_max.ipa ().nonzero_p ();
3769	}
3770
3771	/* Return true if function is likely to be expensive, so there is no point to
3772	optimize performance of prologue, epilogue or do inlining at the expense
3773	of code size growth. THRESHOLD is the limit of number of instructions
3774	function can execute at average to be still considered not expensive. */
3775
3776	bool
3777	expensive_function_p (int threshold)
3778	{
3779	basic_block bb;
3780
3781	/* If profile was scaled in a way entry block has count 0, then the function
3782	is deifnitly taking a lot of time. */
3783	if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.nonzero_p ())
3784	return true;
3785
3786	profile_count limit = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count * threshold;
3787	profile_count sum = profile_count::zero ();
3788	FOR_EACH_BB_FN (bb, cfun)
3789	{
3790	rtx_insn *insn;
3791
3792	if (!bb->count.initialized_p ())
3793	{
3794	if (dump_file)
3795	fprintf (stream: dump_file, format: "Function is considered expensive because"
3796	" count of bb %i is not initialized\n", bb->index);
3797	return true;
3798	}
3799
3800	FOR_BB_INSNS (bb, insn)
3801	if (active_insn_p (insn))
3802	{
3803	sum += bb->count;
3804	if (sum > limit)
3805	return true;
3806	}
3807	}
3808
3809	return false;
3810	}
3811
3812	/* All basic blocks that are reachable only from unlikely basic blocks are
3813	unlikely. */
3814
3815	void
3816	propagate_unlikely_bbs_forward (void)
3817	{
3818	auto_vec<basic_block, 64> worklist;
3819	basic_block bb;
3820	edge_iterator ei;
3821	edge e;
3822
3823	if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ()))
3824	{
3825	ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(size_t) 1;
3826	worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3827
3828	while (worklist.length () > 0)
3829	{
3830	bb = worklist.pop ();
3831	FOR_EACH_EDGE (e, ei, bb->succs)
3832	if (!(e->count () == profile_count::zero ())
3833	&& !(e->dest->count == profile_count::zero ())
3834	&& !e->dest->aux)
3835	{
3836	e->dest->aux = (void *)(size_t) 1;
3837	worklist.safe_push (obj: e->dest);
3838	}
3839	}
3840	}
3841
3842	FOR_ALL_BB_FN (bb, cfun)
3843	{
3844	if (!bb->aux)
3845	{
3846	if (!(bb->count == profile_count::zero ())
3847	&& (dump_file && (dump_flags & TDF_DETAILS)))
3848	fprintf (stream: dump_file,
3849	format: "Basic block %i is marked unlikely by forward prop\n",
3850	bb->index);
3851	bb->count = profile_count::zero ();
3852	}
3853	else
3854	bb->aux = NULL;
3855	}
3856	}
3857
3858	/* Determine basic blocks/edges that are known to be unlikely executed and set
3859	their counters to zero.
3860	This is done with first identifying obviously unlikely BBs/edges and then
3861	propagating in both directions. */
3862
3863	static void
3864	determine_unlikely_bbs ()
3865	{
3866	basic_block bb;
3867	auto_vec<basic_block, 64> worklist;
3868	edge_iterator ei;
3869	edge e;
3870
3871	FOR_EACH_BB_FN (bb, cfun)
3872	{
3873	if (!(bb->count == profile_count::zero ())
3874	&& unlikely_executed_bb_p (bb))
3875	{
3876	if (dump_file && (dump_flags & TDF_DETAILS))
3877	fprintf (stream: dump_file, format: "Basic block %i is locally unlikely\n",
3878	bb->index);
3879	bb->count = profile_count::zero ();
3880	}
3881
3882	FOR_EACH_EDGE (e, ei, bb->succs)
3883	if (!(e->probability == profile_probability::never ())
3884	&& unlikely_executed_edge_p (e))
3885	{
3886	if (dump_file && (dump_flags & TDF_DETAILS))
3887	fprintf (stream: dump_file, format: "Edge %i->%i is locally unlikely\n",
3888	bb->index, e->dest->index);
3889	e->probability = profile_probability::never ();
3890	}
3891
3892	gcc_checking_assert (!bb->aux);
3893	}
3894	propagate_unlikely_bbs_forward ();
3895
3896	auto_vec<int, 64> nsuccs;
3897	nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun), exact: true);
3898	FOR_ALL_BB_FN (bb, cfun)
3899	if (!(bb->count == profile_count::zero ())
3900	&& bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3901	{
3902	nsuccs[bb->index] = 0;
3903	FOR_EACH_EDGE (e, ei, bb->succs)
3904	if (!(e->probability == profile_probability::never ())
3905	&& !(e->dest->count == profile_count::zero ()))
3906	nsuccs[bb->index]++;
3907	if (!nsuccs[bb->index])
3908	worklist.safe_push (obj: bb);
3909	}
3910	while (worklist.length () > 0)
3911	{
3912	bb = worklist.pop ();
3913	if (bb->count == profile_count::zero ())
3914	continue;
3915	if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3916	{
3917	bool found = false;
3918	for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
3919	!gsi_end_p (i: gsi); gsi_next (i: &gsi))
3920	if (stmt_can_terminate_bb_p (gsi_stmt (i: gsi))
3921	/* stmt_can_terminate_bb_p special cases noreturns because it
3922	assumes that fake edges are created. We want to know that
3923	noreturn alone does not imply BB to be unlikely. */
3924	|| (is_gimple_call (gs: gsi_stmt (i: gsi))
3925	&& (gimple_call_flags (gsi_stmt (i: gsi)) & ECF_NORETURN)))
3926	{
3927	found = true;
3928	break;
3929	}
3930	if (found)
3931	continue;
3932	}
3933	if (dump_file && (dump_flags & TDF_DETAILS))
3934	fprintf (stream: dump_file,
3935	format: "Basic block %i is marked unlikely by backward prop\n",
3936	bb->index);
3937	bb->count = profile_count::zero ();
3938	FOR_EACH_EDGE (e, ei, bb->preds)
3939	if (!(e->probability == profile_probability::never ()))
3940	{
3941	if (!(e->src->count == profile_count::zero ()))
3942	{
3943	gcc_checking_assert (nsuccs[e->src->index] > 0);
3944	nsuccs[e->src->index]--;
3945	if (!nsuccs[e->src->index])
3946	worklist.safe_push (obj: e->src);
3947	}
3948	}
3949	}
3950	/* Finally all edges from non-0 regions to 0 are unlikely. */
3951	FOR_ALL_BB_FN (bb, cfun)
3952	{
3953	if (!(bb->count == profile_count::zero ()))
3954	FOR_EACH_EDGE (e, ei, bb->succs)
3955	if (!(e->probability == profile_probability::never ())
3956	&& e->dest->count == profile_count::zero ())
3957	{
3958	if (dump_file && (dump_flags & TDF_DETAILS))
3959	fprintf (stream: dump_file, format: "Edge %i->%i is unlikely because "
3960	"it enters unlikely block\n",
3961	bb->index, e->dest->index);
3962	e->probability = profile_probability::never ();
3963	}
3964
3965	edge other = NULL;
3966
3967	FOR_EACH_EDGE (e, ei, bb->succs)
3968	if (e->probability == profile_probability::never ())
3969	;
3970	else if (other)
3971	{
3972	other = NULL;
3973	break;
3974	}
3975	else
3976	other = e;
3977	if (other
3978	&& !(other->probability == profile_probability::always ()))
3979	{
3980	if (dump_file && (dump_flags & TDF_DETAILS))
3981	fprintf (stream: dump_file, format: "Edge %i->%i is locally likely\n",
3982	bb->index, other->dest->index);
3983	other->probability = profile_probability::always ();
3984	}
3985	}
3986	if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
3987	cgraph_node::get (decl: current_function_decl)->count = profile_count::zero ();
3988	}
3989
3990	/* Estimate and propagate basic block frequencies using the given branch
3991	probabilities. */
3992
3993	static void
3994	estimate_bb_frequencies ()
3995	{
3996	basic_block bb;
3997	sreal freq_max;
3998
3999	determine_unlikely_bbs ();
4000
4001	mark_dfs_back_edges ();
4002
4003	single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
4004	profile_probability::always ();
4005
4006	/* Set up block info for each basic block. */
4007	alloc_aux_for_blocks (sizeof (block_info));
4008	alloc_aux_for_edges (sizeof (edge_prob_info));
4009	FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4010	{
4011	edge e;
4012	edge_iterator ei;
4013
4014	FOR_EACH_EDGE (e, ei, bb->succs)
4015	{
4016	/* FIXME: Graphite is producing edges with no profile. Once
4017	this is fixed, drop this. */
4018	if (e->probability.initialized_p ())
4019	EDGE_INFO (e)->back_edge_prob
4020	= e->probability.to_sreal ();
4021	else
4022	/* back_edge_prob = 0.5 */
4023	EDGE_INFO (e)->back_edge_prob = sreal (1, -1);
4024	}
4025	}
4026
4027	/* First compute frequencies locally for each loop from innermost
4028	to outermost to examine frequencies for back edges. */
4029	estimate_loops ();
4030
4031	freq_max = 0;
4032	FOR_EACH_BB_FN (bb, cfun)
4033	if (freq_max < BLOCK_INFO (bb)->frequency)
4034	freq_max = BLOCK_INFO (bb)->frequency;
4035
4036	/* Scaling frequencies up to maximal profile count may result in
4037	frequent overflows especially when inlining loops.
4038	Small scaling results in unnecesary precision loss. Stay in
4039	the half of the (exponential) range. */
4040	freq_max = (sreal (1) << (profile_count::n_bits / 2)) / freq_max;
4041	if (freq_max < 16)
4042	freq_max = 16;
4043	profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ();
4044	cfun->cfg->count_max = profile_count::uninitialized ();
4045	FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4046	{
4047	sreal tmp = BLOCK_INFO (bb)->frequency;
4048	if (tmp >= 1)
4049	{
4050	gimple_stmt_iterator gsi;
4051	tree decl;
4052
4053	/* Self recursive calls can not have frequency greater than 1
4054	or program will never terminate. This will result in an
4055	inconsistent bb profile but it is better than greatly confusing
4056	IPA cost metrics. */
4057	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
4058	if (is_gimple_call (gs: gsi_stmt (i: gsi))
4059	&& (decl = gimple_call_fndecl (gs: gsi_stmt (i: gsi))) != NULL
4060	&& recursive_call_p (current_function_decl, decl))
4061	{
4062	if (dump_file)
4063	fprintf (stream: dump_file, format: "Dropping frequency of recursive call"
4064	" in bb %i from %f\n", bb->index,
4065	tmp.to_double ());
4066	tmp = (sreal)9 / (sreal)10;
4067	break;
4068	}
4069	}
4070	tmp = tmp * freq_max;
4071	profile_count count = profile_count::from_gcov_type (v: tmp.to_nearest_int ());
4072
4073	/* If we have profile feedback in which this function was never
4074	executed, then preserve this info. */
4075	if (!(bb->count == profile_count::zero ()))
4076	bb->count = count.guessed_local ().combine_with_ipa_count (ipa: ipa_count);
4077	cfun->cfg->count_max = cfun->cfg->count_max.max (other: bb->count);
4078	}
4079
4080	free_aux_for_blocks ();
4081	free_aux_for_edges ();
4082	compute_function_frequency ();
4083	}
4084
4085	/* Decide whether function is hot, cold or unlikely executed. */
4086	void
4087	compute_function_frequency (void)
4088	{
4089	basic_block bb;
4090	struct cgraph_node *node = cgraph_node::get (decl: current_function_decl);
4091
4092	if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4093	|| MAIN_NAME_P (DECL_NAME (current_function_decl)))
4094	node->only_called_at_startup = true;
4095	if (DECL_STATIC_DESTRUCTOR (current_function_decl))
4096	node->only_called_at_exit = true;
4097
4098	if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa_p ())
4099	{
4100	int flags = flags_from_decl_or_type (current_function_decl);
4101	if (lookup_attribute (attr_name: "cold", DECL_ATTRIBUTES (current_function_decl))
4102	!= NULL)
4103	node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4104	else if (lookup_attribute (attr_name: "hot", DECL_ATTRIBUTES (current_function_decl))
4105	!= NULL)
4106	node->frequency = NODE_FREQUENCY_HOT;
4107	else if (flags & ECF_NORETURN)
4108	node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4109	else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
4110	node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4111	else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4112	|| DECL_STATIC_DESTRUCTOR (current_function_decl))
4113	node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4114	return;
4115	}
4116
4117	node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4118	if (lookup_attribute (attr_name: "cold", DECL_ATTRIBUTES (current_function_decl))
4119	== NULL)
4120	warn_function_cold (current_function_decl);
4121	if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
4122	return;
4123	FOR_EACH_BB_FN (bb, cfun)
4124	{
4125	if (maybe_hot_bb_p (cfun, bb))
4126	{
4127	node->frequency = NODE_FREQUENCY_HOT;
4128	return;
4129	}
4130	if (!probably_never_executed_bb_p (cfun, bb))
4131	node->frequency = NODE_FREQUENCY_NORMAL;
4132	}
4133	}
4134
4135	/* Build PREDICT_EXPR. */
4136	tree
4137	build_predict_expr (enum br_predictor predictor, enum prediction taken)
4138	{
4139	tree t = build1 (PREDICT_EXPR, void_type_node,
4140	build_int_cst (integer_type_node, predictor));
4141	SET_PREDICT_EXPR_OUTCOME (t, taken);
4142	return t;
4143	}
4144
4145	const char *
4146	predictor_name (enum br_predictor predictor)
4147	{
4148	return predictor_info[predictor].name;
4149	}
4150
4151	/* Predict branch probabilities and estimate profile of the tree CFG. */
4152
4153	namespace {
4154
4155	const pass_data pass_data_profile =
4156	{
4157	.type: GIMPLE_PASS, /* type */
4158	.name: "profile_estimate", /* name */
4159	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
4160	.tv_id: TV_BRANCH_PROB, /* tv_id */
4161	PROP_cfg, /* properties_required */
4162	.properties_provided: 0, /* properties_provided */
4163	.properties_destroyed: 0, /* properties_destroyed */
4164	.todo_flags_start: 0, /* todo_flags_start */
4165	.todo_flags_finish: 0, /* todo_flags_finish */
4166	};
4167
4168	class pass_profile : public gimple_opt_pass
4169	{
4170	public:
4171	pass_profile (gcc::context *ctxt)
4172	: gimple_opt_pass (pass_data_profile, ctxt)
4173	{}
4174
4175	/* opt_pass methods: */
4176	bool gate (function *) final override { return flag_guess_branch_prob; }
4177	unsigned int execute (function *) final override;
4178
4179	}; // class pass_profile
4180
4181	unsigned int
4182	pass_profile::execute (function *fun)
4183	{
4184	unsigned nb_loops;
4185
4186	if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
4187	return 0;
4188
4189	loop_optimizer_init (LOOPS_NORMAL);
4190	if (dump_file && (dump_flags & TDF_DETAILS))
4191	flow_loops_dump (dump_file, NULL, 0);
4192
4193	nb_loops = number_of_loops (fn: fun);
4194	if (nb_loops > 1)
4195	scev_initialize ();
4196
4197	tree_estimate_probability (dry_run: false);
4198	cfun->cfg->full_profile = true;
4199
4200	if (nb_loops > 1)
4201	scev_finalize ();
4202
4203	loop_optimizer_finalize ();
4204	if (dump_file && (dump_flags & TDF_DETAILS))
4205	gimple_dump_cfg (dump_file, dump_flags);
4206	if (profile_status_for_fn (fun) == PROFILE_ABSENT)
4207	profile_status_for_fn (fun) = PROFILE_GUESSED;
4208	if (dump_file && (dump_flags & TDF_DETAILS))
4209	{
4210	sreal iterations;
4211	for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
4212	if (expected_loop_iterations_by_profile (loop, ret: &iterations))
4213	fprintf (stream: dump_file, format: "Loop got predicted %d to iterate %f times.\n",
4214	loop->num, iterations.to_double ());
4215	}
4216	return 0;
4217	}
4218
4219	} // anon namespace
4220
4221	gimple_opt_pass *
4222	make_pass_profile (gcc::context *ctxt)
4223	{
4224	return new pass_profile (ctxt);
4225	}
4226
4227	/* Return true when PRED predictor should be removed after early
4228	tree passes. Most of the predictors are beneficial to survive
4229	as early inlining can also distribute then into caller's bodies. */
4230
4231	static bool
4232	strip_predictor_early (enum br_predictor pred)
4233	{
4234	switch (pred)
4235	{
4236	case PRED_TREE_EARLY_RETURN:
4237	return true;
4238	default:
4239	return false;
4240	}
4241	}
4242
4243	/* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
4244	we no longer need. EARLY is set to true when called from early
4245	optimizations. */
4246
4247	unsigned int
4248	strip_predict_hints (function *fun, bool early)
4249	{
4250	basic_block bb;
4251	gimple *ass_stmt;
4252	tree var;
4253	bool changed = false;
4254
4255	FOR_EACH_BB_FN (bb, fun)
4256	{
4257	gimple_stmt_iterator bi;
4258	for (bi = gsi_start_bb (bb); !gsi_end_p (i: bi);)
4259	{
4260	gimple *stmt = gsi_stmt (i: bi);
4261
4262	if (gimple_code (g: stmt) == GIMPLE_PREDICT)
4263	{
4264	if (!early
4265	|| strip_predictor_early (pred: gimple_predict_predictor (gs: stmt)))
4266	{
4267	gsi_remove (&bi, true);
4268	changed = true;
4269	continue;
4270	}
4271	}
4272	else if (is_gimple_call (gs: stmt))
4273	{
4274	tree fndecl = gimple_call_fndecl (gs: stmt);
4275
4276	if (!early
4277	&& ((fndecl != NULL_TREE
4278	&& fndecl_built_in_p (node: fndecl, name1: BUILT_IN_EXPECT)
4279	&& gimple_call_num_args (gs: stmt) == 2)
4280	|| (fndecl != NULL_TREE
4281	&& fndecl_built_in_p (node: fndecl,
4282	name1: BUILT_IN_EXPECT_WITH_PROBABILITY)
4283	&& gimple_call_num_args (gs: stmt) == 3)
4284	|| (gimple_call_internal_p (gs: stmt)
4285	&& gimple_call_internal_fn (gs: stmt) == IFN_BUILTIN_EXPECT)))
4286	{
4287	var = gimple_call_lhs (gs: stmt);
4288	changed = true;
4289	if (var)
4290	{
4291	ass_stmt
4292	= gimple_build_assign (var, gimple_call_arg (gs: stmt, index: 0));
4293	gsi_replace (&bi, ass_stmt, true);
4294	}
4295	else
4296	{
4297	gsi_remove (&bi, true);
4298	continue;
4299	}
4300	}
4301	}
4302	gsi_next (i: &bi);
4303	}
4304	}
4305	return changed ? TODO_cleanup_cfg : 0;
4306	}
4307
4308	namespace {
4309
4310	const pass_data pass_data_strip_predict_hints =
4311	{
4312	.type: GIMPLE_PASS, /* type */
4313	.name: "*strip_predict_hints", /* name */
4314	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
4315	.tv_id: TV_BRANCH_PROB, /* tv_id */
4316	PROP_cfg, /* properties_required */
4317	.properties_provided: 0, /* properties_provided */
4318	.properties_destroyed: 0, /* properties_destroyed */
4319	.todo_flags_start: 0, /* todo_flags_start */
4320	.todo_flags_finish: 0, /* todo_flags_finish */
4321	};
4322
4323	class pass_strip_predict_hints : public gimple_opt_pass
4324	{
4325	public:
4326	pass_strip_predict_hints (gcc::context *ctxt)
4327	: gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
4328	{}
4329
4330	/* opt_pass methods: */
4331	opt_pass * clone () final override
4332	{
4333	return new pass_strip_predict_hints (m_ctxt);
4334	}
4335	void set_pass_param (unsigned int n, bool param) final override
4336	{
4337	gcc_assert (n == 0);
4338	early_p = param;
4339	}
4340
4341	unsigned int execute (function *) final override;
4342
4343	private:
4344	bool early_p;
4345
4346	}; // class pass_strip_predict_hints
4347
4348	unsigned int
4349	pass_strip_predict_hints::execute (function *fun)
4350	{
4351	return strip_predict_hints (fun, early: early_p);
4352	}
4353
4354	} // anon namespace
4355
4356	gimple_opt_pass *
4357	make_pass_strip_predict_hints (gcc::context *ctxt)
4358	{
4359	return new pass_strip_predict_hints (ctxt);
4360	}
4361
4362	/* Rebuild function frequencies. Passes are in general expected to
4363	maintain profile by hand, however in some cases this is not possible:
4364	for example when inlining several functions with loops freuqencies might run
4365	out of scale and thus needs to be recomputed. */
4366
4367	void
4368	rebuild_frequencies (void)
4369	{
4370	/* If we have no profile, do nothing. Note that after inlining
4371	profile_status_for_fn may not represent the actual presence/absence of
4372	profile. */
4373	if (profile_status_for_fn (cfun) == PROFILE_ABSENT
4374	&& !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.initialized_p ())
4375	return;
4376
4377
4378	/* See if everything is OK and update count_max. */
4379	basic_block bb;
4380	bool inconsistency_found = false;
4381	bool uninitialized_probablity_found = false;
4382	bool uninitialized_count_found = false;
4383
4384	cfun->cfg->count_max = profile_count::uninitialized ();
4385	FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4386	{
4387	cfun->cfg->count_max = cfun->cfg->count_max.max (other: bb->count);
4388	/* Uninitialized count may be result of inlining or an omision in an
4389	optimization pass. */
4390	if (!bb->count.initialized_p ())
4391	{
4392	uninitialized_count_found = true;
4393	if (dump_file)
4394	fprintf (stream: dump_file, format: "BB %i has uninitialized count\n",
4395	bb->index);
4396	}
4397	if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4398	&& (!uninitialized_probablity_found || !inconsistency_found))
4399	{
4400	profile_count sum = profile_count::zero ();
4401	edge e;
4402	edge_iterator ei;
4403
4404	FOR_EACH_EDGE (e, ei, bb->preds)
4405	{
4406	sum += e->count ();
4407	/* Uninitialized probability may be result of inlining or an
4408	omision in an optimization pass. */
4409	if (!e->probability.initialized_p ())
4410	{
4411	if (dump_file)
4412	fprintf (stream: dump_file,
4413	format: "Edge %i->%i has uninitialized probability\n",
4414	e->src->index, e->dest->index);
4415	}
4416	}
4417	if (sum.differs_from_p (other: bb->count))
4418	{
4419	if (dump_file)
4420	fprintf (stream: dump_file,
4421	format: "BB %i has invalid sum of incomming counts\n",
4422	bb->index);
4423	inconsistency_found = true;
4424	}
4425	}
4426	}
4427
4428	/* If everything is OK, do not re-propagate frequencies. */
4429	if (!inconsistency_found
4430	&& (!uninitialized_count_found || uninitialized_probablity_found)
4431	&& !cfun->cfg->count_max.very_large_p ())
4432	{
4433	if (dump_file)
4434	fprintf (stream: dump_file, format: "Profile is consistent\n");
4435	return;
4436	}
4437	/* Do not re-propagate if we have profile feedback. Even if the profile is
4438	inconsistent from previous transofrmations, it is probably more realistic
4439	for hot part of the program than result of repropagating.
4440
4441	Consider example where we previously has
4442
4443	if (test)
4444	then [large probability for true]
4445
4446	and we later proved that test is always 0. In this case, if profile was
4447	read correctly, we must have duplicated the conditional (for example by
4448	inlining) in to a context where test is false. From profile feedback
4449	we know that most executions if the conditionals were true, so the
4450	important copy is not the one we look on.
4451
4452	Propagating from probabilities would make profile look consistent, but
4453	because probablities after code duplication may not be representative
4454	for a given run, we would only propagate the error further. */
4455	if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ().nonzero_p ()
4456	&& !uninitialized_count_found)
4457	{
4458	if (dump_file)
4459	fprintf (stream: dump_file,
4460	format: "Profile is inconsistent but read from profile feedback;"
4461	" not rebuilding\n");
4462	return;
4463	}
4464
4465	loop_optimizer_init (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
4466	connect_infinite_loops_to_exit ();
4467	estimate_bb_frequencies ();
4468	remove_fake_exit_edges ();
4469	loop_optimizer_finalize ();
4470	if (dump_file)
4471	fprintf (stream: dump_file, format: "Rebuilt basic block counts\n");
4472
4473	return;
4474	}
4475
4476	namespace {
4477
4478	const pass_data pass_data_rebuild_frequencies =
4479	{
4480	.type: GIMPLE_PASS, /* type */
4481	.name: "rebuild_frequencies", /* name */
4482	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
4483	.tv_id: TV_REBUILD_FREQUENCIES, /* tv_id */
4484	PROP_cfg, /* properties_required */
4485	.properties_provided: 0, /* properties_provided */
4486	.properties_destroyed: 0, /* properties_destroyed */
4487	.todo_flags_start: 0, /* todo_flags_start */
4488	.todo_flags_finish: 0, /* todo_flags_finish */
4489	};
4490
4491	class pass_rebuild_frequencies : public gimple_opt_pass
4492	{
4493	public:
4494	pass_rebuild_frequencies (gcc::context *ctxt)
4495	: gimple_opt_pass (pass_data_rebuild_frequencies, ctxt)
4496	{}
4497
4498	/* opt_pass methods: */
4499	opt_pass * clone () final override
4500	{
4501	return new pass_rebuild_frequencies (m_ctxt);
4502	}
4503	void set_pass_param (unsigned int n, bool param) final override
4504	{
4505	gcc_assert (n == 0);
4506	early_p = param;
4507	}
4508
4509	unsigned int execute (function *) final override
4510	{
4511	rebuild_frequencies ();
4512	return 0;
4513	}
4514
4515	private:
4516	bool early_p;
4517
4518	}; // class pass_rebuild_frequencies
4519
4520	} // anon namespace
4521
4522	gimple_opt_pass *
4523	make_pass_rebuild_frequencies (gcc::context *ctxt)
4524	{
4525	return new pass_rebuild_frequencies (ctxt);
4526	}
4527
4528	/* Perform a dry run of the branch prediction pass and report comparsion of
4529	the predicted and real profile into the dump file. */
4530
4531	void
4532	report_predictor_hitrates (void)
4533	{
4534	unsigned nb_loops;
4535
4536	loop_optimizer_init (LOOPS_NORMAL);
4537	if (dump_file && (dump_flags & TDF_DETAILS))
4538	flow_loops_dump (dump_file, NULL, 0);
4539
4540	nb_loops = number_of_loops (cfun);
4541	if (nb_loops > 1)
4542	scev_initialize ();
4543
4544	tree_estimate_probability (dry_run: true);
4545
4546	if (nb_loops > 1)
4547	scev_finalize ();
4548
4549	loop_optimizer_finalize ();
4550	}
4551
4552	/* Force edge E to be cold.
4553	If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4554	keep low probability to represent possible error in a guess. This is used
4555	i.e. in case we predict loop to likely iterate given number of times but
4556	we are not 100% sure.
4557
4558	This function locally updates profile without attempt to keep global
4559	consistency which cannot be reached in full generality without full profile
4560	rebuild from probabilities alone. Doing so is not necessarily a good idea
4561	because frequencies and counts may be more realistic then probabilities.
4562
4563	In some cases (such as for elimination of early exits during full loop
4564	unrolling) the caller can ensure that profile will get consistent
4565	afterwards. */
4566
4567	void
4568	force_edge_cold (edge e, bool impossible)
4569	{
4570	profile_count count_sum = profile_count::zero ();
4571	profile_probability prob_sum = profile_probability::never ();
4572	edge_iterator ei;
4573	edge e2;
4574	bool uninitialized_exit = false;
4575
4576	/* When branch probability guesses are not known, then do nothing. */
4577	if (!impossible && !e->count ().initialized_p ())
4578	return;
4579
4580	profile_probability goal = (impossible ? profile_probability::never ()
4581	: profile_probability::very_unlikely ());
4582
4583	/* If edge is already improbably or cold, just return. */
4584	if (e->probability <= goal
4585	&& (!impossible || e->count () == profile_count::zero ()))
4586	return;
4587	FOR_EACH_EDGE (e2, ei, e->src->succs)
4588	if (e2 != e)
4589	{
4590	if (e->flags & EDGE_FAKE)
4591	continue;
4592	if (e2->count ().initialized_p ())
4593	count_sum += e2->count ();
4594	if (e2->probability.initialized_p ())
4595	prob_sum += e2->probability;
4596	else
4597	uninitialized_exit = true;
4598	}
4599
4600	/* If we are not guessing profiles but have some other edges out,
4601	just assume the control flow goes elsewhere. */
4602	if (uninitialized_exit)
4603	e->probability = goal;
4604	/* If there are other edges out of e->src, redistribute probabilitity
4605	there. */
4606	else if (prob_sum > profile_probability::never ())
4607	{
4608	if (dump_file && (dump_flags & TDF_DETAILS))
4609	{
4610	fprintf (stream: dump_file, format: "Making edge %i->%i %s by redistributing "
4611	"probability to other edges. Original probability: ",
4612	e->src->index, e->dest->index,
4613	impossible ? "impossible" : "cold");
4614	e->probability.dump (f: dump_file);
4615	fprintf (stream: dump_file, format: "\n");
4616	}
4617	set_edge_probability_and_rescale_others (e, goal);
4618	if (current_ir_type () != IR_GIMPLE
4619	&& e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4620	update_br_prob_note (e->src);
4621	}
4622	/* If all edges out of e->src are unlikely, the basic block itself
4623	is unlikely. */
4624	else
4625	{
4626	if (prob_sum == profile_probability::never ())
4627	e->probability = profile_probability::always ();
4628	else
4629	{
4630	if (impossible)
4631	e->probability = profile_probability::never ();
4632	/* If BB has some edges out that are not impossible, we cannot
4633	assume that BB itself is. */
4634	impossible = false;
4635	}
4636	if (current_ir_type () != IR_GIMPLE
4637	&& e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4638	update_br_prob_note (e->src);
4639	if (e->src->count == profile_count::zero ())
4640	return;
4641	if (count_sum == profile_count::zero () && impossible)
4642	{
4643	bool found = false;
4644	if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
4645	;
4646	else if (current_ir_type () == IR_GIMPLE)
4647	for (gimple_stmt_iterator gsi = gsi_start_bb (bb: e->src);
4648	!gsi_end_p (i: gsi); gsi_next (i: &gsi))
4649	{
4650	if (stmt_can_terminate_bb_p (gsi_stmt (i: gsi)))
4651	{
4652	found = true;
4653	break;
4654	}
4655	}
4656	/* FIXME: Implement RTL path. */
4657	else
4658	found = true;
4659	if (!found)
4660	{
4661	if (dump_file && (dump_flags & TDF_DETAILS))
4662	fprintf (stream: dump_file,
4663	format: "Making bb %i impossible and dropping count to 0.\n",
4664	e->src->index);
4665	e->src->count = profile_count::zero ();
4666	FOR_EACH_EDGE (e2, ei, e->src->preds)
4667	force_edge_cold (e: e2, impossible);
4668	return;
4669	}
4670	}
4671
4672	/* If we did not adjusting, the source basic block has no likely edeges
4673	leaving other direction. In that case force that bb cold, too.
4674	This in general is difficult task to do, but handle special case when
4675	BB has only one predecestor. This is common case when we are updating
4676	after loop transforms. */
4677	if (!(prob_sum > profile_probability::never ())
4678	&& count_sum == profile_count::zero ()
4679	&& single_pred_p (bb: e->src) && e->src->count.to_frequency (cfun)
4680	> (impossible ? 0 : 1))
4681	{
4682	int old_frequency = e->src->count.to_frequency (cfun);
4683	if (dump_file && (dump_flags & TDF_DETAILS))
4684	fprintf (stream: dump_file, format: "Making bb %i %s.\n", e->src->index,
4685	impossible ? "impossible" : "cold");
4686	int new_frequency = MIN (e->src->count.to_frequency (cfun),
4687	impossible ? 0 : 1);
4688	if (impossible)
4689	e->src->count = profile_count::zero ();
4690	else
4691	e->src->count = e->count ().apply_scale (num: new_frequency,
4692	den: old_frequency);
4693	force_edge_cold (e: single_pred_edge (bb: e->src), impossible);
4694	}
4695	else if (dump_file && (dump_flags & TDF_DETAILS)
4696	&& maybe_hot_bb_p (cfun, bb: e->src))
4697	fprintf (stream: dump_file, format: "Giving up on making bb %i %s.\n", e->src->index,
4698	impossible ? "impossible" : "cold");
4699	}
4700	}
4701
4702	#if CHECKING_P
4703
4704	namespace selftest {
4705
4706	/* Test that value range of predictor values defined in predict.def is
4707	within range (50, 100]. */
4708
4709	struct branch_predictor
4710	{
4711	const char *name;
4712	int probability;
4713	};
4714
4715	#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4716
4717	static void
4718	test_prediction_value_range ()
4719	{
4720	branch_predictor predictors[] = {
4721	#include "predict.def"
4722	{ NULL, PROB_UNINITIALIZED }
4723	};
4724
4725	for (unsigned i = 0; predictors[i].name != NULL; i++)
4726	{
4727	if (predictors[i].probability == PROB_UNINITIALIZED)
4728	continue;
4729
4730	unsigned p = 100 * predictors[i].probability / REG_BR_PROB_BASE;
4731	ASSERT_TRUE (p >= 50 && p <= 100);
4732	}
4733	}
4734
4735	#undef DEF_PREDICTOR
4736
4737	/* Run all of the selfests within this file. */
4738
4739	void
4740	predict_cc_tests ()
4741	{
4742	test_prediction_value_range ();
4743	}
4744
4745	} // namespace selftest
4746	#endif /* CHECKING_P. */
4747