1	/* Branch prediction routines for the GNU compiler.
2	Copyright (C) 2000-2023 Free Software Foundation, Inc.
3
4	This file is part of GCC.
5
6	GCC is free software; you can redistribute it and/or modify it under
7	the terms of the GNU General Public License as published by the Free
8	Software Foundation; either version 3, or (at your option) any later
9	version.
10
11	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12	WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14	for more details.
15
16	You should have received a copy of the GNU General Public License
17	along with GCC; see the file COPYING3. If not see
18	<http://www.gnu.org/licenses/>. */
19
20	/* 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 (gimple_code (g: def) == GIMPLE_PHI)
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: def);
2412	tree val = NULL, new_val;
2413
2414	for (i = 0; i < n; i++)
2415	{
2416	tree arg = PHI_ARG_DEF (def, i);
2417	enum br_predictor predictor2;
2418
2419	/* If this PHI has itself as an argument, we cannot
2420	determine the string length of this argument. However,
2421	if we can find an expected constant value for the other
2422	PHI args then we can still be sure that this is
2423	likely a constant. So be optimistic and just
2424	continue with the next argument. */
2425	if (arg == PHI_RESULT (def))
2426	continue;
2427
2428	HOST_WIDE_INT probability2;
2429	new_val = expr_expected_value (arg, visited, predictor: &predictor2,
2430	probability: &probability2);
2431
2432	/* It is difficult to combine value predictors. Simply assume
2433	that later predictor is weaker and take its prediction. */
2434	if (*predictor < predictor2)
2435	{
2436	*predictor = predictor2;
2437	*probability = probability2;
2438	}
2439	if (!new_val)
2440	return NULL;
2441	if (!val)
2442	val = new_val;
2443	else if (!operand_equal_p (val, new_val, flags: false))
2444	return NULL;
2445	}
2446	return val;
2447	}
2448	if (is_gimple_assign (gs: def))
2449	{
2450	if (gimple_assign_lhs (gs: def) != op0)
2451	return NULL;
2452
2453	return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
2454	op0: gimple_assign_rhs1 (gs: def),
2455	code: gimple_assign_rhs_code (gs: def),
2456	op1: gimple_assign_rhs2 (gs: def),
2457	visited, predictor, probability);
2458	}
2459
2460	if (is_gimple_call (gs: def))
2461	{
2462	tree decl = gimple_call_fndecl (gs: def);
2463	if (!decl)
2464	{
2465	if (gimple_call_internal_p (gs: def)
2466	&& gimple_call_internal_fn (gs: def) == IFN_BUILTIN_EXPECT)
2467	{
2468	gcc_assert (gimple_call_num_args (def) == 3);
2469	tree val = gimple_call_arg (gs: def, index: 0);
2470	if (TREE_CONSTANT (val))
2471	return val;
2472	tree val2 = gimple_call_arg (gs: def, index: 2);
2473	gcc_assert (TREE_CODE (val2) == INTEGER_CST
2474	&& tree_fits_uhwi_p (val2)
2475	&& tree_to_uhwi (val2) < END_PREDICTORS);
2476	*predictor = (enum br_predictor) tree_to_uhwi (val2);
2477	if (*predictor == PRED_BUILTIN_EXPECT)
2478	*probability
2479	= HITRATE (param_builtin_expect_probability);
2480	return gimple_call_arg (gs: def, index: 1);
2481	}
2482	return NULL;
2483	}
2484
2485	if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW_P (decl))
2486	{
2487	if (predictor)
2488	*predictor = PRED_MALLOC_NONNULL;
2489	/* FIXME: This is wrong and we need to convert the logic
2490	to value ranges. This makes predictor to assume that
2491	malloc always returns (size_t)1 which is not the same
2492	as returning non-NULL. */
2493	return fold_convert (type, boolean_true_node);
2494	}
2495
2496	if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2497	switch (DECL_FUNCTION_CODE (decl))
2498	{
2499	case BUILT_IN_EXPECT:
2500	{
2501	tree val;
2502	if (gimple_call_num_args (gs: def) != 2)
2503	return NULL;
2504	val = gimple_call_arg (gs: def, index: 0);
2505	if (TREE_CONSTANT (val))
2506	return val;
2507	*predictor = PRED_BUILTIN_EXPECT;
2508	*probability
2509	= HITRATE (param_builtin_expect_probability);
2510	return gimple_call_arg (gs: def, index: 1);
2511	}
2512	case BUILT_IN_EXPECT_WITH_PROBABILITY:
2513	{
2514	tree val;
2515	if (gimple_call_num_args (gs: def) != 3)
2516	return NULL;
2517	val = gimple_call_arg (gs: def, index: 0);
2518	if (TREE_CONSTANT (val))
2519	return val;
2520	/* Compute final probability as:
2521	probability * REG_BR_PROB_BASE. */
2522	tree prob = gimple_call_arg (gs: def, index: 2);
2523	tree t = TREE_TYPE (prob);
2524	tree base = build_int_cst (integer_type_node,
2525	REG_BR_PROB_BASE);
2526	base = build_real_from_int_cst (t, base);
2527	tree r = fold_build2_initializer_loc (UNKNOWN_LOCATION,
2528	MULT_EXPR, t, prob, base);
2529	if (TREE_CODE (r) != REAL_CST)
2530	{
2531	error_at (gimple_location (g: def),
2532	"probability %qE must be "
2533	"constant floating-point expression", prob);
2534	return NULL;
2535	}
2536	HOST_WIDE_INT probi
2537	= real_to_integer (TREE_REAL_CST_PTR (r));
2538	if (probi >= 0 && probi <= REG_BR_PROB_BASE)
2539	{
2540	*predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
2541	*probability = probi;
2542	}
2543	else
2544	error_at (gimple_location (g: def),
2545	"probability %qE is outside "
2546	"the range [0.0, 1.0]", prob);
2547
2548	return gimple_call_arg (gs: def, index: 1);
2549	}
2550
2551	case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
2552	case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
2553	case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
2554	case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
2555	case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
2556	case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
2557	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
2558	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
2559	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
2560	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
2561	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
2562	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
2563	case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
2564	/* Assume that any given atomic operation has low contention,
2565	and thus the compare-and-swap operation succeeds. */
2566	*predictor = PRED_COMPARE_AND_SWAP;
2567	return boolean_true_node;
2568	case BUILT_IN_REALLOC:
2569	if (predictor)
2570	*predictor = PRED_MALLOC_NONNULL;
2571	/* FIXME: This is wrong and we need to convert the logic
2572	to value ranges. */
2573	return fold_convert (type, boolean_true_node);
2574	default:
2575	break;
2576	}
2577	}
2578
2579	return NULL;
2580	}
2581
2582	if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2583	{
2584	tree res;
2585	tree nop0 = op0;
2586	tree nop1 = op1;
2587	if (TREE_CODE (op0) != INTEGER_CST)
2588	{
2589	/* See if expected value of op0 is good enough to determine the result. */
2590	nop0 = expr_expected_value (op0, visited, predictor, probability);
2591	if (nop0
2592	&& (res = fold_build2 (code, type, nop0, op1)) != NULL
2593	&& TREE_CODE (res) == INTEGER_CST)
2594	return res;
2595	if (!nop0)
2596	nop0 = op0;
2597	}
2598	enum br_predictor predictor2;
2599	HOST_WIDE_INT probability2;
2600	if (TREE_CODE (op1) != INTEGER_CST)
2601	{
2602	/* See if expected value of op1 is good enough to determine the result. */
2603	nop1 = expr_expected_value (op1, visited, predictor: &predictor2, probability: &probability2);
2604	if (nop1
2605	&& (res = fold_build2 (code, type, op0, nop1)) != NULL
2606	&& TREE_CODE (res) == INTEGER_CST)
2607	{
2608	*predictor = predictor2;
2609	*probability = probability2;
2610	return res;
2611	}
2612	if (!nop1)
2613	nop1 = op1;
2614	}
2615	if (nop0 == op0 || nop1 == op1)
2616	return NULL;
2617	/* Finally see if we have two known values. */
2618	res = fold_build2 (code, type, nop0, nop1);
2619	if (TREE_CODE (res) == INTEGER_CST
2620	&& TREE_CODE (nop0) == INTEGER_CST
2621	&& TREE_CODE (nop1) == INTEGER_CST)
2622	{
2623	/* Combine binary predictions. */
2624	if (*probability != -1 || probability2 != -1)
2625	{
2626	HOST_WIDE_INT p1 = get_predictor_value (*predictor, *probability);
2627	HOST_WIDE_INT p2 = get_predictor_value (predictor2, probability2);
2628	*probability = RDIV (p1 * p2, REG_BR_PROB_BASE);
2629	}
2630
2631	if (predictor2 < *predictor)
2632	*predictor = predictor2;
2633
2634	return res;
2635	}
2636	return NULL;
2637	}
2638	if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
2639	{
2640	tree res;
2641	op0 = expr_expected_value (op0, visited, predictor, probability);
2642	if (!op0)
2643	return NULL;
2644	res = fold_build1 (code, type, op0);
2645	if (TREE_CONSTANT (res))
2646	return res;
2647	return NULL;
2648	}
2649	return NULL;
2650	}
2651
2652	/* Return constant EXPR will likely have at execution time, NULL if unknown.
2653	The function is used by builtin_expect branch predictor so the evidence
2654	must come from this construct and additional possible constant folding.
2655
2656	We may want to implement more involved value guess (such as value range
2657	propagation based prediction), but such tricks shall go to new
2658	implementation. */
2659
2660	static tree
2661	expr_expected_value (tree expr, bitmap visited,
2662	enum br_predictor *predictor,
2663	HOST_WIDE_INT *probability)
2664	{
2665	enum tree_code code;
2666	tree op0, op1;
2667
2668	if (TREE_CONSTANT (expr))
2669	{
2670	*predictor = PRED_UNCONDITIONAL;
2671	*probability = -1;
2672	return expr;
2673	}
2674
2675	extract_ops_from_tree (expr, code: &code, op0: &op0, op1: &op1);
2676	return expr_expected_value_1 (TREE_TYPE (expr),
2677	op0, code, op1, visited, predictor,
2678	probability);
2679	}
2680
2681
2682	/* Return probability of a PREDICTOR. If the predictor has variable
2683	probability return passed PROBABILITY. */
2684
2685	static HOST_WIDE_INT
2686	get_predictor_value (br_predictor predictor, HOST_WIDE_INT probability)
2687	{
2688	switch (predictor)
2689	{
2690	case PRED_BUILTIN_EXPECT:
2691	case PRED_BUILTIN_EXPECT_WITH_PROBABILITY:
2692	gcc_assert (probability != -1);
2693	return probability;
2694	default:
2695	gcc_assert (probability == -1);
2696	return predictor_info[(int) predictor].hitrate;
2697	}
2698	}
2699
2700	/* Predict using opcode of the last statement in basic block. */
2701	static void
2702	tree_predict_by_opcode (basic_block bb)
2703	{
2704	edge then_edge;
2705	tree op0, op1;
2706	tree type;
2707	tree val;
2708	enum tree_code cmp;
2709	edge_iterator ei;
2710	enum br_predictor predictor;
2711	HOST_WIDE_INT probability;
2712
2713	gimple *stmt = *gsi_last_bb (bb);
2714	if (!stmt)
2715	return;
2716
2717	if (gswitch *sw = dyn_cast <gswitch *> (p: stmt))
2718	{
2719	tree index = gimple_switch_index (gs: sw);
2720	tree val = expr_expected_value (expr: index, visited: auto_bitmap (),
2721	predictor: &predictor, probability: &probability);
2722	if (val && TREE_CODE (val) == INTEGER_CST)
2723	{
2724	edge e = find_taken_edge_switch_expr (switch_stmt: sw, val);
2725	if (predictor == PRED_BUILTIN_EXPECT)
2726	{
2727	int percent = param_builtin_expect_probability;
2728	gcc_assert (percent >= 0 && percent <= 100);
2729	predict_edge (e, predictor: PRED_BUILTIN_EXPECT,
2730	HITRATE (percent));
2731	}
2732	else
2733	predict_edge_def (e, predictor, taken: TAKEN);
2734	}
2735	}
2736
2737	if (gimple_code (g: stmt) != GIMPLE_COND)
2738	return;
2739	FOR_EACH_EDGE (then_edge, ei, bb->succs)
2740	if (then_edge->flags & EDGE_TRUE_VALUE)
2741	break;
2742	op0 = gimple_cond_lhs (gs: stmt);
2743	op1 = gimple_cond_rhs (gs: stmt);
2744	cmp = gimple_cond_code (gs: stmt);
2745	type = TREE_TYPE (op0);
2746	val = expr_expected_value_1 (boolean_type_node, op0, code: cmp, op1, visited: auto_bitmap (),
2747	predictor: &predictor, probability: &probability);
2748	if (val && TREE_CODE (val) == INTEGER_CST)
2749	{
2750	HOST_WIDE_INT prob = get_predictor_value (predictor, probability);
2751	if (integer_zerop (val))
2752	prob = REG_BR_PROB_BASE - prob;
2753	predict_edge (e: then_edge, predictor, probability: prob);
2754	}
2755	/* Try "pointer heuristic."
2756	A comparison ptr == 0 is predicted as false.
2757	Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2758	if (POINTER_TYPE_P (type))
2759	{
2760	if (cmp == EQ_EXPR)
2761	predict_edge_def (e: then_edge, predictor: PRED_TREE_POINTER, taken: NOT_TAKEN);
2762	else if (cmp == NE_EXPR)
2763	predict_edge_def (e: then_edge, predictor: PRED_TREE_POINTER, taken: TAKEN);
2764	}
2765	else
2766
2767	/* Try "opcode heuristic."
2768	EQ tests are usually false and NE tests are usually true. Also,
2769	most quantities are positive, so we can make the appropriate guesses
2770	about signed comparisons against zero. */
2771	switch (cmp)
2772	{
2773	case EQ_EXPR:
2774	case UNEQ_EXPR:
2775	/* Floating point comparisons appears to behave in a very
2776	unpredictable way because of special role of = tests in
2777	FP code. */
2778	if (FLOAT_TYPE_P (type))
2779	;
2780	/* Comparisons with 0 are often used for booleans and there is
2781	nothing useful to predict about them. */
2782	else if (integer_zerop (op0) || integer_zerop (op1))
2783	;
2784	else
2785	predict_edge_def (e: then_edge, predictor: PRED_TREE_OPCODE_NONEQUAL, taken: NOT_TAKEN);
2786	break;
2787
2788	case NE_EXPR:
2789	case LTGT_EXPR:
2790	/* Floating point comparisons appears to behave in a very
2791	unpredictable way because of special role of = tests in
2792	FP code. */
2793	if (FLOAT_TYPE_P (type))
2794	;
2795	/* Comparisons with 0 are often used for booleans and there is
2796	nothing useful to predict about them. */
2797	else if (integer_zerop (op0)
2798	|| integer_zerop (op1))
2799	;
2800	else
2801	predict_edge_def (e: then_edge, predictor: PRED_TREE_OPCODE_NONEQUAL, taken: TAKEN);
2802	break;
2803
2804	case ORDERED_EXPR:
2805	predict_edge_def (e: then_edge, predictor: PRED_TREE_FPOPCODE, taken: TAKEN);
2806	break;
2807
2808	case UNORDERED_EXPR:
2809	predict_edge_def (e: then_edge, predictor: PRED_TREE_FPOPCODE, taken: NOT_TAKEN);
2810	break;
2811
2812	case LE_EXPR:
2813	case LT_EXPR:
2814	if (integer_zerop (op1)
2815	|| integer_onep (op1)
2816	|| integer_all_onesp (op1)
2817	|| real_zerop (op1)
2818	|| real_onep (op1)
2819	|| real_minus_onep (op1))
2820	predict_edge_def (e: then_edge, predictor: PRED_TREE_OPCODE_POSITIVE, taken: NOT_TAKEN);
2821	break;
2822
2823	case GE_EXPR:
2824	case GT_EXPR:
2825	if (integer_zerop (op1)
2826	|| integer_onep (op1)
2827	|| integer_all_onesp (op1)
2828	|| real_zerop (op1)
2829	|| real_onep (op1)
2830	|| real_minus_onep (op1))
2831	predict_edge_def (e: then_edge, predictor: PRED_TREE_OPCODE_POSITIVE, taken: TAKEN);
2832	break;
2833
2834	default:
2835	break;
2836	}
2837	}
2838
2839	/* Returns TRUE if the STMT is exit(0) like statement. */
2840
2841	static bool
2842	is_exit_with_zero_arg (const gimple *stmt)
2843	{
2844	/* This is not exit, _exit or _Exit. */
2845	if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
2846	&& !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
2847	&& !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
2848	return false;
2849
2850	/* Argument is an interger zero. */
2851	return integer_zerop (gimple_call_arg (gs: stmt, index: 0));
2852	}
2853
2854	/* Try to guess whether the value of return means error code. */
2855
2856	static enum br_predictor
2857	return_prediction (tree val, enum prediction *prediction)
2858	{
2859	/* VOID. */
2860	if (!val)
2861	return PRED_NO_PREDICTION;
2862	/* Different heuristics for pointers and scalars. */
2863	if (POINTER_TYPE_P (TREE_TYPE (val)))
2864	{
2865	/* NULL is usually not returned. */
2866	if (integer_zerop (val))
2867	{
2868	*prediction = NOT_TAKEN;
2869	return PRED_NULL_RETURN;
2870	}
2871	}
2872	else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
2873	{
2874	/* Negative return values are often used to indicate
2875	errors. */
2876	if (TREE_CODE (val) == INTEGER_CST
2877	&& tree_int_cst_sgn (val) < 0)
2878	{
2879	*prediction = NOT_TAKEN;
2880	return PRED_NEGATIVE_RETURN;
2881	}
2882	/* Constant return values seems to be commonly taken.
2883	Zero/one often represent booleans so exclude them from the
2884	heuristics. */
2885	if (TREE_CONSTANT (val)
2886	&& (!integer_zerop (val) && !integer_onep (val)))
2887	{
2888	*prediction = NOT_TAKEN;
2889	return PRED_CONST_RETURN;
2890	}
2891	}
2892	return PRED_NO_PREDICTION;
2893	}
2894
2895	/* Return zero if phi result could have values other than -1, 0 or 1,
2896	otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2897	values are used or likely. */
2898
2899	static int
2900	zero_one_minusone (gphi *phi, int limit)
2901	{
2902	int phi_num_args = gimple_phi_num_args (gs: phi);
2903	int ret = 0;
2904	for (int i = 0; i < phi_num_args; i++)
2905	{
2906	tree t = PHI_ARG_DEF (phi, i);
2907	if (TREE_CODE (t) != INTEGER_CST)
2908	continue;
2909	wide_int w = wi::to_wide (t);
2910	if (w == -1)
2911	ret |= 1;
2912	else if (w == 0)
2913	ret |= 2;
2914	else if (w == 1)
2915	ret |= 4;
2916	else
2917	return 0;
2918	}
2919	for (int i = 0; i < phi_num_args; i++)
2920	{
2921	tree t = PHI_ARG_DEF (phi, i);
2922	if (TREE_CODE (t) == INTEGER_CST)
2923	continue;
2924	if (TREE_CODE (t) != SSA_NAME)
2925	return 0;
2926	gimple *g = SSA_NAME_DEF_STMT (t);
2927	if (gimple_code (g) == GIMPLE_PHI && limit > 0)
2928	if (int r = zero_one_minusone (phi: as_a <gphi *> (p: g), limit: limit - 1))
2929	{
2930	ret |= r;
2931	continue;
2932	}
2933	if (!is_gimple_assign (gs: g))
2934	return 0;
2935	if (gimple_assign_cast_p (s: g))
2936	{
2937	tree rhs1 = gimple_assign_rhs1 (gs: g);
2938	if (TREE_CODE (rhs1) != SSA_NAME
2939	|| !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2940	|| TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
2941	|| !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
2942	return 0;
2943	ret |= (2 | 4);
2944	continue;
2945	}
2946	if (TREE_CODE_CLASS (gimple_assign_rhs_code (g)) != tcc_comparison)
2947	return 0;
2948	ret |= (2 | 4);
2949	}
2950	return ret;
2951	}
2952
2953	/* Find the basic block with return expression and look up for possible
2954	return value trying to apply RETURN_PREDICTION heuristics. */
2955	static void
2956	apply_return_prediction (void)
2957	{
2958	greturn *return_stmt = NULL;
2959	tree return_val;
2960	edge e;
2961	gphi *phi;
2962	int phi_num_args, i;
2963	enum br_predictor pred;
2964	enum prediction direction;
2965	edge_iterator ei;
2966
2967	FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2968	{
2969	if (greturn *last = safe_dyn_cast <greturn *> (p: *gsi_last_bb (bb: e->src)))
2970	{
2971	return_stmt = last;
2972	break;
2973	}
2974	}
2975	if (!e)
2976	return;
2977	return_val = gimple_return_retval (gs: return_stmt);
2978	if (!return_val)
2979	return;
2980	if (TREE_CODE (return_val) != SSA_NAME
2981	|| !SSA_NAME_DEF_STMT (return_val)
2982	|| gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
2983	return;
2984	phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
2985	phi_num_args = gimple_phi_num_args (gs: phi);
2986	pred = return_prediction (PHI_ARG_DEF (phi, 0), prediction: &direction);
2987
2988	/* Avoid the case where the function returns -1, 0 and 1 values and
2989	nothing else. Those could be qsort etc. comparison functions
2990	where the negative return isn't less probable than positive.
2991	For this require that the function returns at least -1 or 1
2992	or -1 and a boolean value or comparison result, so that functions
2993	returning just -1 and 0 are treated as if -1 represents error value. */
2994	if (INTEGRAL_TYPE_P (TREE_TYPE (return_val))
2995	&& !TYPE_UNSIGNED (TREE_TYPE (return_val))
2996	&& TYPE_PRECISION (TREE_TYPE (return_val)) > 1)
2997	if (int r = zero_one_minusone (phi, limit: 3))
2998	if ((r & (1 | 4)) == (1 | 4))
2999	return;
3000
3001	/* Avoid the degenerate case where all return values form the function
3002	belongs to same category (ie they are all positive constants)
3003	so we can hardly say something about them. */
3004	for (i = 1; i < phi_num_args; i++)
3005	if (pred != return_prediction (PHI_ARG_DEF (phi, i), prediction: &direction))
3006	break;
3007	if (i != phi_num_args)
3008	for (i = 0; i < phi_num_args; i++)
3009	{
3010	pred = return_prediction (PHI_ARG_DEF (phi, i), prediction: &direction);
3011	if (pred != PRED_NO_PREDICTION)
3012	predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
3013	direction);
3014	}
3015	}
3016
3017	/* Look for basic block that contains unlikely to happen events
3018	(such as noreturn calls) and mark all paths leading to execution
3019	of this basic blocks as unlikely. */
3020
3021	static void
3022	tree_bb_level_predictions (void)
3023	{
3024	basic_block bb;
3025	bool has_return_edges = false;
3026	edge e;
3027	edge_iterator ei;
3028
3029	FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
3030	if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
3031	{
3032	has_return_edges = true;
3033	break;
3034	}
3035
3036	apply_return_prediction ();
3037
3038	FOR_EACH_BB_FN (bb, cfun)
3039	{
3040	gimple_stmt_iterator gsi;
3041
3042	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
3043	{
3044	gimple *stmt = gsi_stmt (i: gsi);
3045	tree decl;
3046
3047	if (is_gimple_call (gs: stmt))
3048	{
3049	if (gimple_call_noreturn_p (s: stmt)
3050	&& has_return_edges
3051	&& !is_exit_with_zero_arg (stmt))
3052	predict_paths_leading_to (bb, PRED_NORETURN,
3053	NOT_TAKEN);
3054	decl = gimple_call_fndecl (gs: stmt);
3055	if (decl
3056	&& lookup_attribute (attr_name: "cold",
3057	DECL_ATTRIBUTES (decl)))
3058	predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
3059	NOT_TAKEN);
3060	if (decl && recursive_call_p (current_function_decl, decl))
3061	predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
3062	NOT_TAKEN);
3063	}
3064	else if (gimple_code (g: stmt) == GIMPLE_PREDICT)
3065	{
3066	predict_paths_leading_to (bb, gimple_predict_predictor (gs: stmt),
3067	gimple_predict_outcome (gs: stmt));
3068	/* Keep GIMPLE_PREDICT around so early inlining will propagate
3069	hints to callers. */
3070	}
3071	}
3072	}
3073	}
3074
3075	/* Callback for hash_map::traverse, asserts that the pointer map is
3076	empty. */
3077
3078	bool
3079	assert_is_empty (const_basic_block const &, edge_prediction *const &value,
3080	void *)
3081	{
3082	gcc_assert (!value);
3083	return true;
3084	}
3085
3086	/* Predict branch probabilities and estimate profile for basic block BB.
3087	When LOCAL_ONLY is set do not use any global properties of CFG. */
3088
3089	static void
3090	tree_estimate_probability_bb (basic_block bb, bool local_only)
3091	{
3092	edge e;
3093	edge_iterator ei;
3094
3095	FOR_EACH_EDGE (e, ei, bb->succs)
3096	{
3097	/* Look for block we are guarding (ie we dominate it,
3098	but it doesn't postdominate us). */
3099	if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
3100	&& !local_only
3101	&& dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
3102	&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
3103	{
3104	gimple_stmt_iterator bi;
3105
3106	/* The call heuristic claims that a guarded function call
3107	is improbable. This is because such calls are often used
3108	to signal exceptional situations such as printing error
3109	messages. */
3110	for (bi = gsi_start_bb (bb: e->dest); !gsi_end_p (i: bi);
3111	gsi_next (i: &bi))
3112	{
3113	gimple *stmt = gsi_stmt (i: bi);
3114	if (is_gimple_call (gs: stmt)
3115	&& !gimple_inexpensive_call_p (as_a <gcall *> (p: stmt))
3116	/* Constant and pure calls are hardly used to signalize
3117	something exceptional. */
3118	&& gimple_has_side_effects (stmt))
3119	{
3120	if (gimple_call_fndecl (gs: stmt))
3121	predict_edge_def (e, predictor: PRED_CALL, taken: NOT_TAKEN);
3122	else if (virtual_method_call_p (gimple_call_fn (gs: stmt)))
3123	predict_edge_def (e, predictor: PRED_POLYMORPHIC_CALL, taken: NOT_TAKEN);
3124	else
3125	predict_edge_def (e, predictor: PRED_INDIR_CALL, taken: TAKEN);
3126	break;
3127	}
3128	}
3129	}
3130	}
3131	tree_predict_by_opcode (bb);
3132	}
3133
3134	/* Predict branch probabilities and estimate profile of the tree CFG.
3135	This function can be called from the loop optimizers to recompute
3136	the profile information.
3137	If DRY_RUN is set, do not modify CFG and only produce dump files. */
3138
3139	void
3140	tree_estimate_probability (bool dry_run)
3141	{
3142	basic_block bb;
3143
3144	connect_infinite_loops_to_exit ();
3145	/* We use loop_niter_by_eval, which requires that the loops have
3146	preheaders. */
3147	create_preheaders (CP_SIMPLE_PREHEADERS);
3148	calculate_dominance_info (CDI_POST_DOMINATORS);
3149	/* Decide which edges are known to be unlikely. This improves later
3150	branch prediction. */
3151	determine_unlikely_bbs ();
3152
3153	bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3154	tree_bb_level_predictions ();
3155	record_loop_exits ();
3156
3157	if (number_of_loops (cfun) > 1)
3158	predict_loops ();
3159
3160	FOR_EACH_BB_FN (bb, cfun)
3161	tree_estimate_probability_bb (bb, local_only: false);
3162
3163	FOR_EACH_BB_FN (bb, cfun)
3164	combine_predictions_for_bb (bb, dry_run);
3165
3166	if (flag_checking)
3167	bb_predictions->traverse<void *, assert_is_empty> (NULL);
3168
3169	delete bb_predictions;
3170	bb_predictions = NULL;
3171
3172	if (!dry_run
3173	&& profile_status_for_fn (cfun) != PROFILE_READ)
3174	estimate_bb_frequencies ();
3175	free_dominance_info (CDI_POST_DOMINATORS);
3176	remove_fake_exit_edges ();
3177	}
3178
3179	/* Set edge->probability for each successor edge of BB. */
3180	void
3181	tree_guess_outgoing_edge_probabilities (basic_block bb)
3182	{
3183	bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3184	tree_estimate_probability_bb (bb, local_only: true);
3185	combine_predictions_for_bb (bb, dry_run: false);
3186	if (flag_checking)
3187	bb_predictions->traverse<void *, assert_is_empty> (NULL);
3188	delete bb_predictions;
3189	bb_predictions = NULL;
3190	}
3191
3192	/* Filter function predicate that returns true for a edge predicate P
3193	if its edge is equal to DATA. */
3194
3195	static bool
3196	not_loop_guard_equal_edge_p (edge_prediction *p, void *data)
3197	{
3198	return p->ep_edge != (edge)data || p->ep_predictor != PRED_LOOP_GUARD;
3199	}
3200
3201	/* Predict edge E with PRED unless it is already predicted by some predictor
3202	considered equivalent. */
3203
3204	static void
3205	maybe_predict_edge (edge e, enum br_predictor pred, enum prediction taken)
3206	{
3207	if (edge_predicted_by_p (e, predictor: pred, taken))
3208	return;
3209	if (pred == PRED_LOOP_GUARD
3210	&& edge_predicted_by_p (e, predictor: PRED_LOOP_GUARD_WITH_RECURSION, taken))
3211	return;
3212	/* Consider PRED_LOOP_GUARD_WITH_RECURSION superrior to LOOP_GUARD. */
3213	if (pred == PRED_LOOP_GUARD_WITH_RECURSION)
3214	{
3215	edge_prediction **preds = bb_predictions->get (k: e->src);
3216	if (preds)
3217	filter_predictions (preds, filter: not_loop_guard_equal_edge_p, data: e);
3218	}
3219	predict_edge_def (e, predictor: pred, taken);
3220	}
3221	/* Predict edges to successors of CUR whose sources are not postdominated by
3222	BB by PRED and recurse to all postdominators. */
3223
3224	static void
3225	predict_paths_for_bb (basic_block cur, basic_block bb,
3226	enum br_predictor pred,
3227	enum prediction taken,
3228	bitmap visited, class loop *in_loop = NULL)
3229	{
3230	edge e;
3231	edge_iterator ei;
3232	basic_block son;
3233
3234	/* If we exited the loop or CUR is unconditional in the loop, there is
3235	nothing to do. */
3236	if (in_loop
3237	&& (!flow_bb_inside_loop_p (in_loop, cur)
3238	|| dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
3239	return;
3240
3241	/* We are looking for all edges forming edge cut induced by
3242	set of all blocks postdominated by BB. */
3243	FOR_EACH_EDGE (e, ei, cur->preds)
3244	if (e->src->index >= NUM_FIXED_BLOCKS
3245	&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
3246	{
3247	edge e2;
3248	edge_iterator ei2;
3249	bool found = false;
3250
3251	/* Ignore fake edges and eh, we predict them as not taken anyway. */
3252	if (unlikely_executed_edge_p (e))
3253	continue;
3254	gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
3255
3256	/* See if there is an edge from e->src that is not abnormal
3257	and does not lead to BB and does not exit the loop. */
3258	FOR_EACH_EDGE (e2, ei2, e->src->succs)
3259	if (e2 != e
3260	&& !unlikely_executed_edge_p (e: e2)
3261	&& !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
3262	&& (!in_loop || !loop_exit_edge_p (in_loop, e2)))
3263	{
3264	found = true;
3265	break;
3266	}
3267
3268	/* If there is non-abnormal path leaving e->src, predict edge
3269	using predictor. Otherwise we need to look for paths
3270	leading to e->src.
3271
3272	The second may lead to infinite loop in the case we are predicitng
3273	regions that are only reachable by abnormal edges. We simply
3274	prevent visiting given BB twice. */
3275	if (found)
3276	maybe_predict_edge (e, pred, taken);
3277	else if (bitmap_set_bit (visited, e->src->index))
3278	predict_paths_for_bb (cur: e->src, bb: e->src, pred, taken, visited, in_loop);
3279	}
3280	for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
3281	son;
3282	son = next_dom_son (CDI_POST_DOMINATORS, son))
3283	predict_paths_for_bb (cur: son, bb, pred, taken, visited, in_loop);
3284	}
3285
3286	/* Sets branch probabilities according to PREDiction and
3287	FLAGS. */
3288
3289	static void
3290	predict_paths_leading_to (basic_block bb, enum br_predictor pred,
3291	enum prediction taken, class loop *in_loop)
3292	{
3293	predict_paths_for_bb (cur: bb, bb, pred, taken, visited: auto_bitmap (), in_loop);
3294	}
3295
3296	/* Like predict_paths_leading_to but take edge instead of basic block. */
3297
3298	static void
3299	predict_paths_leading_to_edge (edge e, enum br_predictor pred,
3300	enum prediction taken, class loop *in_loop)
3301	{
3302	bool has_nonloop_edge = false;
3303	edge_iterator ei;
3304	edge e2;
3305
3306	basic_block bb = e->src;
3307	FOR_EACH_EDGE (e2, ei, bb->succs)
3308	if (e2->dest != e->src && e2->dest != e->dest
3309	&& !unlikely_executed_edge_p (e: e2)
3310	&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
3311	{
3312	has_nonloop_edge = true;
3313	break;
3314	}
3315
3316	if (!has_nonloop_edge)
3317	predict_paths_for_bb (cur: bb, bb, pred, taken, visited: auto_bitmap (), in_loop);
3318	else
3319	maybe_predict_edge (e, pred, taken);
3320	}
3321
3322	/* This is used to carry information about basic blocks. It is
3323	attached to the AUX field of the standard CFG block. */
3324
3325	class block_info
3326	{
3327	public:
3328	/* Estimated frequency of execution of basic_block. */
3329	sreal frequency;
3330
3331	/* To keep queue of basic blocks to process. */
3332	basic_block next;
3333
3334	/* Number of predecessors we need to visit first. */
3335	int npredecessors;
3336	};
3337
3338	/* Similar information for edges. */
3339	class edge_prob_info
3340	{
3341	public:
3342	/* In case edge is a loopback edge, the probability edge will be reached
3343	in case header is. Estimated number of iterations of the loop can be
3344	then computed as 1 / (1 - back_edge_prob). */
3345	sreal back_edge_prob;
3346	/* True if the edge is a loopback edge in the natural loop. */
3347	unsigned int back_edge:1;
3348	};
3349
3350	#define BLOCK_INFO(B) ((block_info *) (B)->aux)
3351	#undef EDGE_INFO
3352	#define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3353
3354	/* Helper function for estimate_bb_frequencies.
3355	Propagate the frequencies in blocks marked in
3356	TOVISIT, starting in HEAD. */
3357
3358	static void
3359	propagate_freq (basic_block head, bitmap tovisit,
3360	sreal max_cyclic_prob)
3361	{
3362	basic_block bb;
3363	basic_block last;
3364	unsigned i;
3365	edge e;
3366	basic_block nextbb;
3367	bitmap_iterator bi;
3368
3369	/* For each basic block we need to visit count number of his predecessors
3370	we need to visit first. */
3371	EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
3372	{
3373	edge_iterator ei;
3374	int count = 0;
3375
3376	bb = BASIC_BLOCK_FOR_FN (cfun, i);
3377
3378	FOR_EACH_EDGE (e, ei, bb->preds)
3379	{
3380	bool visit = bitmap_bit_p (tovisit, e->src->index);
3381
3382	if (visit && !(e->flags & EDGE_DFS_BACK))
3383	count++;
3384	else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
3385	fprintf (stream: dump_file,
3386	format: "Irreducible region hit, ignoring edge to %i->%i\n",
3387	e->src->index, bb->index);
3388	}
3389	BLOCK_INFO (bb)->npredecessors = count;
3390	/* When function never returns, we will never process exit block. */
3391	if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
3392	bb->count = profile_count::zero ();
3393	}
3394
3395	BLOCK_INFO (head)->frequency = 1;
3396	last = head;
3397	for (bb = head; bb; bb = nextbb)
3398	{
3399	edge_iterator ei;
3400	sreal cyclic_probability = 0;
3401	sreal frequency = 0;
3402
3403	nextbb = BLOCK_INFO (bb)->next;
3404	BLOCK_INFO (bb)->next = NULL;
3405
3406	/* Compute frequency of basic block. */
3407	if (bb != head)
3408	{
3409	if (flag_checking)
3410	FOR_EACH_EDGE (e, ei, bb->preds)
3411	gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
3412	|| (e->flags & EDGE_DFS_BACK));
3413
3414	FOR_EACH_EDGE (e, ei, bb->preds)
3415	if (EDGE_INFO (e)->back_edge)
3416	cyclic_probability += EDGE_INFO (e)->back_edge_prob;
3417	else if (!(e->flags & EDGE_DFS_BACK))
3418	{
3419	/* FIXME: Graphite is producing edges with no profile. Once
3420	this is fixed, drop this. */
3421	sreal tmp = e->probability.initialized_p () ?
3422	e->probability.to_sreal () : 0;
3423	frequency += tmp * BLOCK_INFO (e->src)->frequency;
3424	}
3425
3426	if (cyclic_probability == 0)
3427	{
3428	BLOCK_INFO (bb)->frequency = frequency;
3429	}
3430	else
3431	{
3432	if (cyclic_probability > max_cyclic_prob)
3433	{
3434	if (dump_file)
3435	fprintf (stream: dump_file,
3436	format: "cyclic probability of bb %i is %f (capped to %f)"
3437	"; turning freq %f",
3438	bb->index, cyclic_probability.to_double (),
3439	max_cyclic_prob.to_double (),
3440	frequency.to_double ());
3441
3442	cyclic_probability = max_cyclic_prob;
3443	}
3444	else if (dump_file)
3445	fprintf (stream: dump_file,
3446	format: "cyclic probability of bb %i is %f; turning freq %f",
3447	bb->index, cyclic_probability.to_double (),
3448	frequency.to_double ());
3449
3450	BLOCK_INFO (bb)->frequency = frequency
3451	/ (sreal (1) - cyclic_probability);
3452	if (dump_file)
3453	fprintf (stream: dump_file, format: " to %f\n",
3454	BLOCK_INFO (bb)->frequency.to_double ());
3455	}
3456	}
3457
3458	bitmap_clear_bit (tovisit, bb->index);
3459
3460	e = find_edge (bb, head);
3461	if (e)
3462	{
3463	/* FIXME: Graphite is producing edges with no profile. Once
3464	this is fixed, drop this. */
3465	sreal tmp = e->probability.initialized_p () ?
3466	e->probability.to_sreal () : 0;
3467	EDGE_INFO (e)->back_edge_prob = tmp * BLOCK_INFO (bb)->frequency;
3468	}
3469
3470	/* Propagate to successor blocks. */
3471	FOR_EACH_EDGE (e, ei, bb->succs)
3472	if (!(e->flags & EDGE_DFS_BACK)
3473	&& BLOCK_INFO (e->dest)->npredecessors)
3474	{
3475	BLOCK_INFO (e->dest)->npredecessors--;
3476	if (!BLOCK_INFO (e->dest)->npredecessors)
3477	{
3478	if (!nextbb)
3479	nextbb = e->dest;
3480	else
3481	BLOCK_INFO (last)->next = e->dest;
3482
3483	last = e->dest;
3484	}
3485	}
3486	}
3487	}
3488
3489	/* Estimate frequencies in loops at same nest level. */
3490
3491	static void
3492	estimate_loops_at_level (class loop *first_loop, sreal max_cyclic_prob)
3493	{
3494	class loop *loop;
3495
3496	for (loop = first_loop; loop; loop = loop->next)
3497	{
3498	edge e;
3499	basic_block *bbs;
3500	unsigned i;
3501	auto_bitmap tovisit;
3502
3503	estimate_loops_at_level (first_loop: loop->inner, max_cyclic_prob);
3504
3505	/* Find current loop back edge and mark it. */
3506	e = loop_latch_edge (loop);
3507	EDGE_INFO (e)->back_edge = 1;
3508
3509	bbs = get_loop_body (loop);
3510	for (i = 0; i < loop->num_nodes; i++)
3511	bitmap_set_bit (tovisit, bbs[i]->index);
3512	free (ptr: bbs);
3513	propagate_freq (head: loop->header, tovisit, max_cyclic_prob);
3514	}
3515	}
3516
3517	/* Propagates frequencies through structure of loops. */
3518
3519	static void
3520	estimate_loops (void)
3521	{
3522	auto_bitmap tovisit;
3523	basic_block bb;
3524	sreal max_cyclic_prob = (sreal)1
3525	- (sreal)1 / (param_max_predicted_iterations + 1);
3526
3527	/* Start by estimating the frequencies in the loops. */
3528	if (number_of_loops (cfun) > 1)
3529	estimate_loops_at_level (current_loops->tree_root->inner, max_cyclic_prob);
3530
3531	/* Now propagate the frequencies through all the blocks. */
3532	FOR_ALL_BB_FN (bb, cfun)
3533	{
3534	bitmap_set_bit (tovisit, bb->index);
3535	}
3536	propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit, max_cyclic_prob);
3537	}
3538
3539	/* Drop the profile for NODE to guessed, and update its frequency based on
3540	whether it is expected to be hot given the CALL_COUNT. */
3541
3542	static void
3543	drop_profile (struct cgraph_node *node, profile_count call_count)
3544	{
3545	struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3546	/* In the case where this was called by another function with a
3547	dropped profile, call_count will be 0. Since there are no
3548	non-zero call counts to this function, we don't know for sure
3549	whether it is hot, and therefore it will be marked normal below. */
3550	bool hot = maybe_hot_count_p (NULL, count: call_count);
3551
3552	if (dump_file)
3553	fprintf (stream: dump_file,
3554	format: "Dropping 0 profile for %s. %s based on calls.\n",
3555	node->dump_name (),
3556	hot ? "Function is hot" : "Function is normal");
3557	/* We only expect to miss profiles for functions that are reached
3558	via non-zero call edges in cases where the function may have
3559	been linked from another module or library (COMDATs and extern
3560	templates). See the comments below for handle_missing_profiles.
3561	Also, only warn in cases where the missing counts exceed the
3562	number of training runs. In certain cases with an execv followed
3563	by a no-return call the profile for the no-return call is not
3564	dumped and there can be a mismatch. */
3565	if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
3566	&& call_count > profile_info->runs)
3567	{
3568	if (flag_profile_correction)
3569	{
3570	if (dump_file)
3571	fprintf (stream: dump_file,
3572	format: "Missing counts for called function %s\n",
3573	node->dump_name ());
3574	}
3575	else
3576	warning (0, "Missing counts for called function %s",
3577	node->dump_name ());
3578	}
3579
3580	basic_block bb;
3581	if (opt_for_fn (node->decl, flag_guess_branch_prob))
3582	{
3583	bool clear_zeros
3584	= !ENTRY_BLOCK_PTR_FOR_FN (fn)->count.nonzero_p ();
3585	FOR_ALL_BB_FN (bb, fn)
3586	if (clear_zeros || !(bb->count == profile_count::zero ()))
3587	bb->count = bb->count.guessed_local ();
3588	fn->cfg->count_max = fn->cfg->count_max.guessed_local ();
3589	}
3590	else
3591	{
3592	FOR_ALL_BB_FN (bb, fn)
3593	bb->count = profile_count::uninitialized ();
3594	fn->cfg->count_max = profile_count::uninitialized ();
3595	}
3596
3597	struct cgraph_edge *e;
3598	for (e = node->callees; e; e = e->next_callee)
3599	e->count = gimple_bb (g: e->call_stmt)->count;
3600	for (e = node->indirect_calls; e; e = e->next_callee)
3601	e->count = gimple_bb (g: e->call_stmt)->count;
3602	node->count = ENTRY_BLOCK_PTR_FOR_FN (fn)->count;
3603
3604	profile_status_for_fn (fn)
3605	= (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
3606	node->frequency
3607	= hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
3608	}
3609
3610	/* In the case of COMDAT routines, multiple object files will contain the same
3611	function and the linker will select one for the binary. In that case
3612	all the other copies from the profile instrument binary will be missing
3613	profile counts. Look for cases where this happened, due to non-zero
3614	call counts going to 0-count functions, and drop the profile to guessed
3615	so that we can use the estimated probabilities and avoid optimizing only
3616	for size.
3617
3618	The other case where the profile may be missing is when the routine
3619	is not going to be emitted to the object file, e.g. for "extern template"
3620	class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3621	all other cases of non-zero calls to 0-count functions. */
3622
3623	void
3624	handle_missing_profiles (void)
3625	{
3626	const int unlikely_frac = param_unlikely_bb_count_fraction;
3627	struct cgraph_node *node;
3628	auto_vec<struct cgraph_node *, 64> worklist;
3629
3630	/* See if 0 count function has non-0 count callers. In this case we
3631	lost some profile. Drop its function profile to PROFILE_GUESSED. */
3632	FOR_EACH_DEFINED_FUNCTION (node)
3633	{
3634	struct cgraph_edge *e;
3635	profile_count call_count = profile_count::zero ();
3636	gcov_type max_tp_first_run = 0;
3637	struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3638
3639	if (node->count.ipa ().nonzero_p ())
3640	continue;
3641	for (e = node->callers; e; e = e->next_caller)
3642	if (e->count.ipa ().initialized_p () && e->count.ipa () > 0)
3643	{
3644	call_count = call_count + e->count.ipa ();
3645
3646	if (e->caller->tp_first_run > max_tp_first_run)
3647	max_tp_first_run = e->caller->tp_first_run;
3648	}
3649
3650	/* If time profile is missing, let assign the maximum that comes from
3651	caller functions. */
3652	if (!node->tp_first_run && max_tp_first_run)
3653	node->tp_first_run = max_tp_first_run + 1;
3654
3655	if (call_count > 0
3656	&& fn && fn->cfg
3657	&& call_count * unlikely_frac >= profile_info->runs)
3658	{
3659	drop_profile (node, call_count);
3660	worklist.safe_push (obj: node);
3661	}
3662	}
3663
3664	/* Propagate the profile dropping to other 0-count COMDATs that are
3665	potentially called by COMDATs we already dropped the profile on. */
3666	while (worklist.length () > 0)
3667	{
3668	struct cgraph_edge *e;
3669
3670	node = worklist.pop ();
3671	for (e = node->callees; e; e = e->next_caller)
3672	{
3673	struct cgraph_node *callee = e->callee;
3674	struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
3675
3676	if (!(e->count.ipa () == profile_count::zero ())
3677	&& callee->count.ipa ().nonzero_p ())
3678	continue;
3679	if ((DECL_COMDAT (callee->decl) || DECL_EXTERNAL (callee->decl))
3680	&& fn && fn->cfg
3681	&& profile_status_for_fn (fn) == PROFILE_READ)
3682	{
3683	drop_profile (node, call_count: profile_count::zero ());
3684	worklist.safe_push (obj: callee);
3685	}
3686	}
3687	}
3688	}
3689
3690	/* Convert counts measured by profile driven feedback to frequencies.
3691	Return nonzero iff there was any nonzero execution count. */
3692
3693	bool
3694	update_max_bb_count (void)
3695	{
3696	profile_count true_count_max = profile_count::uninitialized ();
3697	basic_block bb;
3698
3699	FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3700	true_count_max = true_count_max.max (other: bb->count);
3701
3702	cfun->cfg->count_max = true_count_max;
3703
3704	return true_count_max.ipa ().nonzero_p ();
3705	}
3706
3707	/* Return true if function is likely to be expensive, so there is no point to
3708	optimize performance of prologue, epilogue or do inlining at the expense
3709	of code size growth. THRESHOLD is the limit of number of instructions
3710	function can execute at average to be still considered not expensive. */
3711
3712	bool
3713	expensive_function_p (int threshold)
3714	{
3715	basic_block bb;
3716
3717	/* If profile was scaled in a way entry block has count 0, then the function
3718	is deifnitly taking a lot of time. */
3719	if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.nonzero_p ())
3720	return true;
3721
3722	profile_count limit = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count * threshold;
3723	profile_count sum = profile_count::zero ();
3724	FOR_EACH_BB_FN (bb, cfun)
3725	{
3726	rtx_insn *insn;
3727
3728	if (!bb->count.initialized_p ())
3729	{
3730	if (dump_file)
3731	fprintf (stream: dump_file, format: "Function is considered expensive because"
3732	" count of bb %i is not initialized\n", bb->index);
3733	return true;
3734	}
3735
3736	FOR_BB_INSNS (bb, insn)
3737	if (active_insn_p (insn))
3738	{
3739	sum += bb->count;
3740	if (sum > limit)
3741	return true;
3742	}
3743	}
3744
3745	return false;
3746	}
3747
3748	/* All basic blocks that are reachable only from unlikely basic blocks are
3749	unlikely. */
3750
3751	void
3752	propagate_unlikely_bbs_forward (void)
3753	{
3754	auto_vec<basic_block, 64> worklist;
3755	basic_block bb;
3756	edge_iterator ei;
3757	edge e;
3758
3759	if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ()))
3760	{
3761	ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(size_t) 1;
3762	worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3763
3764	while (worklist.length () > 0)
3765	{
3766	bb = worklist.pop ();
3767	FOR_EACH_EDGE (e, ei, bb->succs)
3768	if (!(e->count () == profile_count::zero ())
3769	&& !(e->dest->count == profile_count::zero ())
3770	&& !e->dest->aux)
3771	{
3772	e->dest->aux = (void *)(size_t) 1;
3773	worklist.safe_push (obj: e->dest);
3774	}
3775	}
3776	}
3777
3778	FOR_ALL_BB_FN (bb, cfun)
3779	{
3780	if (!bb->aux)
3781	{
3782	if (!(bb->count == profile_count::zero ())
3783	&& (dump_file && (dump_flags & TDF_DETAILS)))
3784	fprintf (stream: dump_file,
3785	format: "Basic block %i is marked unlikely by forward prop\n",
3786	bb->index);
3787	bb->count = profile_count::zero ();
3788	}
3789	else
3790	bb->aux = NULL;
3791	}
3792	}
3793
3794	/* Determine basic blocks/edges that are known to be unlikely executed and set
3795	their counters to zero.
3796	This is done with first identifying obviously unlikely BBs/edges and then
3797	propagating in both directions. */
3798
3799	static void
3800	determine_unlikely_bbs ()
3801	{
3802	basic_block bb;
3803	auto_vec<basic_block, 64> worklist;
3804	edge_iterator ei;
3805	edge e;
3806
3807	FOR_EACH_BB_FN (bb, cfun)
3808	{
3809	if (!(bb->count == profile_count::zero ())
3810	&& unlikely_executed_bb_p (bb))
3811	{
3812	if (dump_file && (dump_flags & TDF_DETAILS))
3813	fprintf (stream: dump_file, format: "Basic block %i is locally unlikely\n",
3814	bb->index);
3815	bb->count = profile_count::zero ();
3816	}
3817
3818	FOR_EACH_EDGE (e, ei, bb->succs)
3819	if (!(e->probability == profile_probability::never ())
3820	&& unlikely_executed_edge_p (e))
3821	{
3822	if (dump_file && (dump_flags & TDF_DETAILS))
3823	fprintf (stream: dump_file, format: "Edge %i->%i is locally unlikely\n",
3824	bb->index, e->dest->index);
3825	e->probability = profile_probability::never ();
3826	}
3827
3828	gcc_checking_assert (!bb->aux);
3829	}
3830	propagate_unlikely_bbs_forward ();
3831
3832	auto_vec<int, 64> nsuccs;
3833	nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun), exact: true);
3834	FOR_ALL_BB_FN (bb, cfun)
3835	if (!(bb->count == profile_count::zero ())
3836	&& bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3837	{
3838	nsuccs[bb->index] = 0;
3839	FOR_EACH_EDGE (e, ei, bb->succs)
3840	if (!(e->probability == profile_probability::never ())
3841	&& !(e->dest->count == profile_count::zero ()))
3842	nsuccs[bb->index]++;
3843	if (!nsuccs[bb->index])
3844	worklist.safe_push (obj: bb);
3845	}
3846	while (worklist.length () > 0)
3847	{
3848	bb = worklist.pop ();
3849	if (bb->count == profile_count::zero ())
3850	continue;
3851	if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3852	{
3853	bool found = false;
3854	for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
3855	!gsi_end_p (i: gsi); gsi_next (i: &gsi))
3856	if (stmt_can_terminate_bb_p (gsi_stmt (i: gsi))
3857	/* stmt_can_terminate_bb_p special cases noreturns because it
3858	assumes that fake edges are created. We want to know that
3859	noreturn alone does not imply BB to be unlikely. */
3860	|| (is_gimple_call (gs: gsi_stmt (i: gsi))
3861	&& (gimple_call_flags (gsi_stmt (i: gsi)) & ECF_NORETURN)))
3862	{
3863	found = true;
3864	break;
3865	}
3866	if (found)
3867	continue;
3868	}
3869	if (dump_file && (dump_flags & TDF_DETAILS))
3870	fprintf (stream: dump_file,
3871	format: "Basic block %i is marked unlikely by backward prop\n",
3872	bb->index);
3873	bb->count = profile_count::zero ();
3874	FOR_EACH_EDGE (e, ei, bb->preds)
3875	if (!(e->probability == profile_probability::never ()))
3876	{
3877	if (!(e->src->count == profile_count::zero ()))
3878	{
3879	gcc_checking_assert (nsuccs[e->src->index] > 0);
3880	nsuccs[e->src->index]--;
3881	if (!nsuccs[e->src->index])
3882	worklist.safe_push (obj: e->src);
3883	}
3884	}
3885	}
3886	/* Finally all edges from non-0 regions to 0 are unlikely. */
3887	FOR_ALL_BB_FN (bb, cfun)
3888	{
3889	if (!(bb->count == profile_count::zero ()))
3890	FOR_EACH_EDGE (e, ei, bb->succs)
3891	if (!(e->probability == profile_probability::never ())
3892	&& e->dest->count == profile_count::zero ())
3893	{
3894	if (dump_file && (dump_flags & TDF_DETAILS))
3895	fprintf (stream: dump_file, format: "Edge %i->%i is unlikely because "
3896	"it enters unlikely block\n",
3897	bb->index, e->dest->index);
3898	e->probability = profile_probability::never ();
3899	}
3900
3901	edge other = NULL;
3902
3903	FOR_EACH_EDGE (e, ei, bb->succs)
3904	if (e->probability == profile_probability::never ())
3905	;
3906	else if (other)
3907	{
3908	other = NULL;
3909	break;
3910	}
3911	else
3912	other = e;
3913	if (other
3914	&& !(other->probability == profile_probability::always ()))
3915	{
3916	if (dump_file && (dump_flags & TDF_DETAILS))
3917	fprintf (stream: dump_file, format: "Edge %i->%i is locally likely\n",
3918	bb->index, other->dest->index);
3919	other->probability = profile_probability::always ();
3920	}
3921	}
3922	if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
3923	cgraph_node::get (decl: current_function_decl)->count = profile_count::zero ();
3924	}
3925
3926	/* Estimate and propagate basic block frequencies using the given branch
3927	probabilities. */
3928
3929	static void
3930	estimate_bb_frequencies ()
3931	{
3932	basic_block bb;
3933	sreal freq_max;
3934
3935	determine_unlikely_bbs ();
3936
3937	mark_dfs_back_edges ();
3938
3939	single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
3940	profile_probability::always ();
3941
3942	/* Set up block info for each basic block. */
3943	alloc_aux_for_blocks (sizeof (block_info));
3944	alloc_aux_for_edges (sizeof (edge_prob_info));
3945	FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3946	{
3947	edge e;
3948	edge_iterator ei;
3949
3950	FOR_EACH_EDGE (e, ei, bb->succs)
3951	{
3952	/* FIXME: Graphite is producing edges with no profile. Once
3953	this is fixed, drop this. */
3954	if (e->probability.initialized_p ())
3955	EDGE_INFO (e)->back_edge_prob
3956	= e->probability.to_sreal ();
3957	else
3958	/* back_edge_prob = 0.5 */
3959	EDGE_INFO (e)->back_edge_prob = sreal (1, -1);
3960	}
3961	}
3962
3963	/* First compute frequencies locally for each loop from innermost
3964	to outermost to examine frequencies for back edges. */
3965	estimate_loops ();
3966
3967	freq_max = 0;
3968	FOR_EACH_BB_FN (bb, cfun)
3969	if (freq_max < BLOCK_INFO (bb)->frequency)
3970	freq_max = BLOCK_INFO (bb)->frequency;
3971
3972	/* Scaling frequencies up to maximal profile count may result in
3973	frequent overflows especially when inlining loops.
3974	Small scalling results in unnecesary precision loss. Stay in
3975	the half of the (exponential) range. */
3976	freq_max = (sreal (1) << (profile_count::n_bits / 2)) / freq_max;
3977	if (freq_max < 16)
3978	freq_max = 16;
3979	profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ();
3980	cfun->cfg->count_max = profile_count::uninitialized ();
3981	FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3982	{
3983	sreal tmp = BLOCK_INFO (bb)->frequency;
3984	if (tmp >= 1)
3985	{
3986	gimple_stmt_iterator gsi;
3987	tree decl;
3988
3989	/* Self recursive calls can not have frequency greater than 1
3990	or program will never terminate. This will result in an
3991	inconsistent bb profile but it is better than greatly confusing
3992	IPA cost metrics. */
3993	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
3994	if (is_gimple_call (gs: gsi_stmt (i: gsi))
3995	&& (decl = gimple_call_fndecl (gs: gsi_stmt (i: gsi))) != NULL
3996	&& recursive_call_p (current_function_decl, decl))
3997	{
3998	if (dump_file)
3999	fprintf (stream: dump_file, format: "Dropping frequency of recursive call"
4000	" in bb %i from %f\n", bb->index,
4001	tmp.to_double ());
4002	tmp = (sreal)9 / (sreal)10;
4003	break;
4004	}
4005	}
4006	tmp = tmp * freq_max;
4007	profile_count count = profile_count::from_gcov_type (v: tmp.to_nearest_int ());
4008
4009	/* If we have profile feedback in which this function was never
4010	executed, then preserve this info. */
4011	if (!(bb->count == profile_count::zero ()))
4012	bb->count = count.guessed_local ().combine_with_ipa_count (ipa: ipa_count);
4013	cfun->cfg->count_max = cfun->cfg->count_max.max (other: bb->count);
4014	}
4015
4016	free_aux_for_blocks ();
4017	free_aux_for_edges ();
4018	compute_function_frequency ();
4019	}
4020
4021	/* Decide whether function is hot, cold or unlikely executed. */
4022	void
4023	compute_function_frequency (void)
4024	{
4025	basic_block bb;
4026	struct cgraph_node *node = cgraph_node::get (decl: current_function_decl);
4027
4028	if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4029	|| MAIN_NAME_P (DECL_NAME (current_function_decl)))
4030	node->only_called_at_startup = true;
4031	if (DECL_STATIC_DESTRUCTOR (current_function_decl))
4032	node->only_called_at_exit = true;
4033
4034	if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa_p ())
4035	{
4036	int flags = flags_from_decl_or_type (current_function_decl);
4037	if (lookup_attribute (attr_name: "cold", DECL_ATTRIBUTES (current_function_decl))
4038	!= NULL)
4039	node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4040	else if (lookup_attribute (attr_name: "hot", DECL_ATTRIBUTES (current_function_decl))
4041	!= NULL)
4042	node->frequency = NODE_FREQUENCY_HOT;
4043	else if (flags & ECF_NORETURN)
4044	node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4045	else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
4046	node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4047	else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4048	|| DECL_STATIC_DESTRUCTOR (current_function_decl))
4049	node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4050	return;
4051	}
4052
4053	node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4054	if (lookup_attribute (attr_name: "cold", DECL_ATTRIBUTES (current_function_decl))
4055	== NULL)
4056	warn_function_cold (current_function_decl);
4057	if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
4058	return;
4059	FOR_EACH_BB_FN (bb, cfun)
4060	{
4061	if (maybe_hot_bb_p (cfun, bb))
4062	{
4063	node->frequency = NODE_FREQUENCY_HOT;
4064	return;
4065	}
4066	if (!probably_never_executed_bb_p (cfun, bb))
4067	node->frequency = NODE_FREQUENCY_NORMAL;
4068	}
4069	}
4070
4071	/* Build PREDICT_EXPR. */
4072	tree
4073	build_predict_expr (enum br_predictor predictor, enum prediction taken)
4074	{
4075	tree t = build1 (PREDICT_EXPR, void_type_node,
4076	build_int_cst (integer_type_node, predictor));
4077	SET_PREDICT_EXPR_OUTCOME (t, taken);
4078	return t;
4079	}
4080
4081	const char *
4082	predictor_name (enum br_predictor predictor)
4083	{
4084	return predictor_info[predictor].name;
4085	}
4086
4087	/* Predict branch probabilities and estimate profile of the tree CFG. */
4088
4089	namespace {
4090
4091	const pass_data pass_data_profile =
4092	{
4093	.type: GIMPLE_PASS, /* type */
4094	.name: "profile_estimate", /* name */
4095	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
4096	.tv_id: TV_BRANCH_PROB, /* tv_id */
4097	PROP_cfg, /* properties_required */
4098	.properties_provided: 0, /* properties_provided */
4099	.properties_destroyed: 0, /* properties_destroyed */
4100	.todo_flags_start: 0, /* todo_flags_start */
4101	.todo_flags_finish: 0, /* todo_flags_finish */
4102	};
4103
4104	class pass_profile : public gimple_opt_pass
4105	{
4106	public:
4107	pass_profile (gcc::context *ctxt)
4108	: gimple_opt_pass (pass_data_profile, ctxt)
4109	{}
4110
4111	/* opt_pass methods: */
4112	bool gate (function *) final override { return flag_guess_branch_prob; }
4113	unsigned int execute (function *) final override;
4114
4115	}; // class pass_profile
4116
4117	unsigned int
4118	pass_profile::execute (function *fun)
4119	{
4120	unsigned nb_loops;
4121
4122	if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
4123	return 0;
4124
4125	loop_optimizer_init (LOOPS_NORMAL);
4126	if (dump_file && (dump_flags & TDF_DETAILS))
4127	flow_loops_dump (dump_file, NULL, 0);
4128
4129	nb_loops = number_of_loops (fn: fun);
4130	if (nb_loops > 1)
4131	scev_initialize ();
4132
4133	tree_estimate_probability (dry_run: false);
4134	cfun->cfg->full_profile = true;
4135
4136	if (nb_loops > 1)
4137	scev_finalize ();
4138
4139	loop_optimizer_finalize ();
4140	if (dump_file && (dump_flags & TDF_DETAILS))
4141	gimple_dump_cfg (dump_file, dump_flags);
4142	if (profile_status_for_fn (fun) == PROFILE_ABSENT)
4143	profile_status_for_fn (fun) = PROFILE_GUESSED;
4144	if (dump_file && (dump_flags & TDF_DETAILS))
4145	{
4146	sreal iterations;
4147	for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
4148	if (expected_loop_iterations_by_profile (loop, ret: &iterations))
4149	fprintf (stream: dump_file, format: "Loop got predicted %d to iterate %f times.\n",
4150	loop->num, iterations.to_double ());
4151	}
4152	return 0;
4153	}
4154
4155	} // anon namespace
4156
4157	gimple_opt_pass *
4158	make_pass_profile (gcc::context *ctxt)
4159	{
4160	return new pass_profile (ctxt);
4161	}
4162
4163	/* Return true when PRED predictor should be removed after early
4164	tree passes. Most of the predictors are beneficial to survive
4165	as early inlining can also distribute then into caller's bodies. */
4166
4167	static bool
4168	strip_predictor_early (enum br_predictor pred)
4169	{
4170	switch (pred)
4171	{
4172	case PRED_TREE_EARLY_RETURN:
4173	return true;
4174	default:
4175	return false;
4176	}
4177	}
4178
4179	/* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
4180	we no longer need. EARLY is set to true when called from early
4181	optimizations. */
4182
4183	unsigned int
4184	strip_predict_hints (function *fun, bool early)
4185	{
4186	basic_block bb;
4187	gimple *ass_stmt;
4188	tree var;
4189	bool changed = false;
4190
4191	FOR_EACH_BB_FN (bb, fun)
4192	{
4193	gimple_stmt_iterator bi;
4194	for (bi = gsi_start_bb (bb); !gsi_end_p (i: bi);)
4195	{
4196	gimple *stmt = gsi_stmt (i: bi);
4197
4198	if (gimple_code (g: stmt) == GIMPLE_PREDICT)
4199	{
4200	if (!early
4201	|| strip_predictor_early (pred: gimple_predict_predictor (gs: stmt)))
4202	{
4203	gsi_remove (&bi, true);
4204	changed = true;
4205	continue;
4206	}
4207	}
4208	else if (is_gimple_call (gs: stmt))
4209	{
4210	tree fndecl = gimple_call_fndecl (gs: stmt);
4211
4212	if (!early
4213	&& ((fndecl != NULL_TREE
4214	&& fndecl_built_in_p (node: fndecl, name1: BUILT_IN_EXPECT)
4215	&& gimple_call_num_args (gs: stmt) == 2)
4216	|| (fndecl != NULL_TREE
4217	&& fndecl_built_in_p (node: fndecl,
4218	name1: BUILT_IN_EXPECT_WITH_PROBABILITY)
4219	&& gimple_call_num_args (gs: stmt) == 3)
4220	|| (gimple_call_internal_p (gs: stmt)
4221	&& gimple_call_internal_fn (gs: stmt) == IFN_BUILTIN_EXPECT)))
4222	{
4223	var = gimple_call_lhs (gs: stmt);
4224	changed = true;
4225	if (var)
4226	{
4227	ass_stmt
4228	= gimple_build_assign (var, gimple_call_arg (gs: stmt, index: 0));
4229	gsi_replace (&bi, ass_stmt, true);
4230	}
4231	else
4232	{
4233	gsi_remove (&bi, true);
4234	continue;
4235	}
4236	}
4237	}
4238	gsi_next (i: &bi);
4239	}
4240	}
4241	return changed ? TODO_cleanup_cfg : 0;
4242	}
4243
4244	namespace {
4245
4246	const pass_data pass_data_strip_predict_hints =
4247	{
4248	.type: GIMPLE_PASS, /* type */
4249	.name: "*strip_predict_hints", /* name */
4250	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
4251	.tv_id: TV_BRANCH_PROB, /* tv_id */
4252	PROP_cfg, /* properties_required */
4253	.properties_provided: 0, /* properties_provided */
4254	.properties_destroyed: 0, /* properties_destroyed */
4255	.todo_flags_start: 0, /* todo_flags_start */
4256	.todo_flags_finish: 0, /* todo_flags_finish */
4257	};
4258
4259	class pass_strip_predict_hints : public gimple_opt_pass
4260	{
4261	public:
4262	pass_strip_predict_hints (gcc::context *ctxt)
4263	: gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
4264	{}
4265
4266	/* opt_pass methods: */
4267	opt_pass * clone () final override
4268	{
4269	return new pass_strip_predict_hints (m_ctxt);
4270	}
4271	void set_pass_param (unsigned int n, bool param) final override
4272	{
4273	gcc_assert (n == 0);
4274	early_p = param;
4275	}
4276
4277	unsigned int execute (function *) final override;
4278
4279	private:
4280	bool early_p;
4281
4282	}; // class pass_strip_predict_hints
4283
4284	unsigned int
4285	pass_strip_predict_hints::execute (function *fun)
4286	{
4287	return strip_predict_hints (fun, early: early_p);
4288	}
4289
4290	} // anon namespace
4291
4292	gimple_opt_pass *
4293	make_pass_strip_predict_hints (gcc::context *ctxt)
4294	{
4295	return new pass_strip_predict_hints (ctxt);
4296	}
4297
4298	/* Rebuild function frequencies. Passes are in general expected to
4299	maintain profile by hand, however in some cases this is not possible:
4300	for example when inlining several functions with loops freuqencies might run
4301	out of scale and thus needs to be recomputed. */
4302
4303	void
4304	rebuild_frequencies (void)
4305	{
4306	/* If we have no profile, do nothing. Note that after inlining
4307	profile_status_for_fn may not represent the actual presence/absence of
4308	profile. */
4309	if (profile_status_for_fn (cfun) == PROFILE_ABSENT
4310	&& !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.initialized_p ())
4311	return;
4312
4313
4314	/* See if everything is OK and update count_max. */
4315	basic_block bb;
4316	bool inconsistency_found = false;
4317	bool uninitialized_probablity_found = false;
4318	bool uninitialized_count_found = false;
4319
4320	cfun->cfg->count_max = profile_count::uninitialized ();
4321	FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4322	{
4323	cfun->cfg->count_max = cfun->cfg->count_max.max (other: bb->count);
4324	/* Uninitialized count may be result of inlining or an omision in an
4325	optimization pass. */
4326	if (!bb->count.initialized_p ())
4327	{
4328	uninitialized_count_found = true;
4329	if (dump_file)
4330	fprintf (stream: dump_file, format: "BB %i has uninitialized count\n",
4331	bb->index);
4332	}
4333	if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4334	&& (!uninitialized_probablity_found || !inconsistency_found))
4335	{
4336	profile_count sum = profile_count::zero ();
4337	edge e;
4338	edge_iterator ei;
4339
4340	FOR_EACH_EDGE (e, ei, bb->preds)
4341	{
4342	sum += e->count ();
4343	/* Uninitialized probability may be result of inlining or an
4344	omision in an optimization pass. */
4345	if (!e->probability.initialized_p ())
4346	{
4347	if (dump_file)
4348	fprintf (stream: dump_file,
4349	format: "Edge %i->%i has uninitialized probability\n",
4350	e->src->index, e->dest->index);
4351	}
4352	}
4353	if (sum.differs_from_p (other: bb->count))
4354	{
4355	if (dump_file)
4356	fprintf (stream: dump_file,
4357	format: "BB %i has invalid sum of incomming counts\n",
4358	bb->index);
4359	inconsistency_found = true;
4360	}
4361	}
4362	}
4363
4364	/* If everything is OK, do not re-propagate frequencies. */
4365	if (!inconsistency_found
4366	&& (!uninitialized_count_found || uninitialized_probablity_found)
4367	&& !cfun->cfg->count_max.very_large_p ())
4368	{
4369	if (dump_file)
4370	fprintf (stream: dump_file, format: "Profile is consistent\n");
4371	return;
4372	}
4373	/* Do not re-propagate if we have profile feedback. Even if the profile is
4374	inconsistent from previous transofrmations, it is probably more realistic
4375	for hot part of the program than result of repropagating.
4376
4377	Consider example where we previously has
4378
4379	if (test)
4380	then [large probability for true]
4381
4382	and we later proved that test is always 0. In this case, if profile was
4383	read correctly, we must have duplicated the conditional (for example by
4384	inlining) in to a context where test is false. From profile feedback
4385	we know that most executions if the conditionals were true, so the
4386	important copy is not the one we look on.
4387
4388	Propagating from probabilities would make profile look consistent, but
4389	because probablities after code duplication may not be representative
4390	for a given run, we would only propagate the error further. */
4391	if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ().nonzero_p ()
4392	&& !uninitialized_count_found)
4393	{
4394	if (dump_file)
4395	fprintf (stream: dump_file,
4396	format: "Profile is inconsistent but read from profile feedback;"
4397	" not rebuilding\n");
4398	return;
4399	}
4400
4401	loop_optimizer_init (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
4402	connect_infinite_loops_to_exit ();
4403	estimate_bb_frequencies ();
4404	remove_fake_exit_edges ();
4405	loop_optimizer_finalize ();
4406	if (dump_file)
4407	fprintf (stream: dump_file, format: "Rebuilt basic block counts\n");
4408
4409	return;
4410	}
4411
4412	namespace {
4413
4414	const pass_data pass_data_rebuild_frequencies =
4415	{
4416	.type: GIMPLE_PASS, /* type */
4417	.name: "rebuild_frequencies", /* name */
4418	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
4419	.tv_id: TV_REBUILD_FREQUENCIES, /* tv_id */
4420	PROP_cfg, /* properties_required */
4421	.properties_provided: 0, /* properties_provided */
4422	.properties_destroyed: 0, /* properties_destroyed */
4423	.todo_flags_start: 0, /* todo_flags_start */
4424	.todo_flags_finish: 0, /* todo_flags_finish */
4425	};
4426
4427	class pass_rebuild_frequencies : public gimple_opt_pass
4428	{
4429	public:
4430	pass_rebuild_frequencies (gcc::context *ctxt)
4431	: gimple_opt_pass (pass_data_rebuild_frequencies, ctxt)
4432	{}
4433
4434	/* opt_pass methods: */
4435	opt_pass * clone () final override
4436	{
4437	return new pass_rebuild_frequencies (m_ctxt);
4438	}
4439	void set_pass_param (unsigned int n, bool param) final override
4440	{
4441	gcc_assert (n == 0);
4442	early_p = param;
4443	}
4444
4445	unsigned int execute (function *) final override
4446	{
4447	rebuild_frequencies ();
4448	return 0;
4449	}
4450
4451	private:
4452	bool early_p;
4453
4454	}; // class pass_rebuild_frequencies
4455
4456	} // anon namespace
4457
4458	gimple_opt_pass *
4459	make_pass_rebuild_frequencies (gcc::context *ctxt)
4460	{
4461	return new pass_rebuild_frequencies (ctxt);
4462	}
4463
4464	/* Perform a dry run of the branch prediction pass and report comparsion of
4465	the predicted and real profile into the dump file. */
4466
4467	void
4468	report_predictor_hitrates (void)
4469	{
4470	unsigned nb_loops;
4471
4472	loop_optimizer_init (LOOPS_NORMAL);
4473	if (dump_file && (dump_flags & TDF_DETAILS))
4474	flow_loops_dump (dump_file, NULL, 0);
4475
4476	nb_loops = number_of_loops (cfun);
4477	if (nb_loops > 1)
4478	scev_initialize ();
4479
4480	tree_estimate_probability (dry_run: true);
4481
4482	if (nb_loops > 1)
4483	scev_finalize ();
4484
4485	loop_optimizer_finalize ();
4486	}
4487
4488	/* Force edge E to be cold.
4489	If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4490	keep low probability to represent possible error in a guess. This is used
4491	i.e. in case we predict loop to likely iterate given number of times but
4492	we are not 100% sure.
4493
4494	This function locally updates profile without attempt to keep global
4495	consistency which cannot be reached in full generality without full profile
4496	rebuild from probabilities alone. Doing so is not necessarily a good idea
4497	because frequencies and counts may be more realistic then probabilities.
4498
4499	In some cases (such as for elimination of early exits during full loop
4500	unrolling) the caller can ensure that profile will get consistent
4501	afterwards. */
4502
4503	void
4504	force_edge_cold (edge e, bool impossible)
4505	{
4506	profile_count count_sum = profile_count::zero ();
4507	profile_probability prob_sum = profile_probability::never ();
4508	edge_iterator ei;
4509	edge e2;
4510	bool uninitialized_exit = false;
4511
4512	/* When branch probability guesses are not known, then do nothing. */
4513	if (!impossible && !e->count ().initialized_p ())
4514	return;
4515
4516	profile_probability goal = (impossible ? profile_probability::never ()
4517	: profile_probability::very_unlikely ());
4518
4519	/* If edge is already improbably or cold, just return. */
4520	if (e->probability <= goal
4521	&& (!impossible || e->count () == profile_count::zero ()))
4522	return;
4523	FOR_EACH_EDGE (e2, ei, e->src->succs)
4524	if (e2 != e)
4525	{
4526	if (e->flags & EDGE_FAKE)
4527	continue;
4528	if (e2->count ().initialized_p ())
4529	count_sum += e2->count ();
4530	if (e2->probability.initialized_p ())
4531	prob_sum += e2->probability;
4532	else
4533	uninitialized_exit = true;
4534	}
4535
4536	/* If we are not guessing profiles but have some other edges out,
4537	just assume the control flow goes elsewhere. */
4538	if (uninitialized_exit)
4539	e->probability = goal;
4540	/* If there are other edges out of e->src, redistribute probabilitity
4541	there. */
4542	else if (prob_sum > profile_probability::never ())
4543	{
4544	if (dump_file && (dump_flags & TDF_DETAILS))
4545	{
4546	fprintf (stream: dump_file, format: "Making edge %i->%i %s by redistributing "
4547	"probability to other edges. Original probability: ",
4548	e->src->index, e->dest->index,
4549	impossible ? "impossible" : "cold");
4550	e->probability.dump (f: dump_file);
4551	fprintf (stream: dump_file, format: "\n");
4552	}
4553	set_edge_probability_and_rescale_others (e, goal);
4554	if (current_ir_type () != IR_GIMPLE
4555	&& e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4556	update_br_prob_note (e->src);
4557	}
4558	/* If all edges out of e->src are unlikely, the basic block itself
4559	is unlikely. */
4560	else
4561	{
4562	if (prob_sum == profile_probability::never ())
4563	e->probability = profile_probability::always ();
4564	else
4565	{
4566	if (impossible)
4567	e->probability = profile_probability::never ();
4568	/* If BB has some edges out that are not impossible, we cannot
4569	assume that BB itself is. */
4570	impossible = false;
4571	}
4572	if (current_ir_type () != IR_GIMPLE
4573	&& e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4574	update_br_prob_note (e->src);
4575	if (e->src->count == profile_count::zero ())
4576	return;
4577	if (count_sum == profile_count::zero () && impossible)
4578	{
4579	bool found = false;
4580	if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
4581	;
4582	else if (current_ir_type () == IR_GIMPLE)
4583	for (gimple_stmt_iterator gsi = gsi_start_bb (bb: e->src);
4584	!gsi_end_p (i: gsi); gsi_next (i: &gsi))
4585	{
4586	if (stmt_can_terminate_bb_p (gsi_stmt (i: gsi)))
4587	{
4588	found = true;
4589	break;
4590	}
4591	}
4592	/* FIXME: Implement RTL path. */
4593	else
4594	found = true;
4595	if (!found)
4596	{
4597	if (dump_file && (dump_flags & TDF_DETAILS))
4598	fprintf (stream: dump_file,
4599	format: "Making bb %i impossible and dropping count to 0.\n",
4600	e->src->index);
4601	e->src->count = profile_count::zero ();
4602	FOR_EACH_EDGE (e2, ei, e->src->preds)
4603	force_edge_cold (e: e2, impossible);
4604	return;
4605	}
4606	}
4607
4608	/* If we did not adjusting, the source basic block has no likely edeges
4609	leaving other direction. In that case force that bb cold, too.
4610	This in general is difficult task to do, but handle special case when
4611	BB has only one predecestor. This is common case when we are updating
4612	after loop transforms. */
4613	if (!(prob_sum > profile_probability::never ())
4614	&& count_sum == profile_count::zero ()
4615	&& single_pred_p (bb: e->src) && e->src->count.to_frequency (cfun)
4616	> (impossible ? 0 : 1))
4617	{
4618	int old_frequency = e->src->count.to_frequency (cfun);
4619	if (dump_file && (dump_flags & TDF_DETAILS))
4620	fprintf (stream: dump_file, format: "Making bb %i %s.\n", e->src->index,
4621	impossible ? "impossible" : "cold");
4622	int new_frequency = MIN (e->src->count.to_frequency (cfun),
4623	impossible ? 0 : 1);
4624	if (impossible)
4625	e->src->count = profile_count::zero ();
4626	else
4627	e->src->count = e->count ().apply_scale (num: new_frequency,
4628	den: old_frequency);
4629	force_edge_cold (e: single_pred_edge (bb: e->src), impossible);
4630	}
4631	else if (dump_file && (dump_flags & TDF_DETAILS)
4632	&& maybe_hot_bb_p (cfun, bb: e->src))
4633	fprintf (stream: dump_file, format: "Giving up on making bb %i %s.\n", e->src->index,
4634	impossible ? "impossible" : "cold");
4635	}
4636	}
4637
4638	#if CHECKING_P
4639
4640	namespace selftest {
4641
4642	/* Test that value range of predictor values defined in predict.def is
4643	within range (50, 100]. */
4644
4645	struct branch_predictor
4646	{
4647	const char *name;
4648	int probability;
4649	};
4650
4651	#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4652
4653	static void
4654	test_prediction_value_range ()
4655	{
4656	branch_predictor predictors[] = {
4657	#include "predict.def"
4658	{ NULL, PROB_UNINITIALIZED }
4659	};
4660
4661	for (unsigned i = 0; predictors[i].name != NULL; i++)
4662	{
4663	if (predictors[i].probability == PROB_UNINITIALIZED)
4664	continue;
4665
4666	unsigned p = 100 * predictors[i].probability / REG_BR_PROB_BASE;
4667	ASSERT_TRUE (p >= 50 && p <= 100);
4668	}
4669	}
4670
4671	#undef DEF_PREDICTOR
4672
4673	/* Run all of the selfests within this file. */
4674
4675	void
4676	predict_cc_tests ()
4677	{
4678	test_prediction_value_range ();
4679	}
4680
4681	} // namespace selftest
4682	#endif /* CHECKING_P. */
4683