xref: /dflybsd-src/contrib/gcc-4.7/gcc/predict.c (revision 0a8dc9fc45f4d0b236341a473fac4a486375f60c)
1e4b17023SJohn Marino /* Branch prediction routines for the GNU compiler.
2e4b17023SJohn Marino    Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
3e4b17023SJohn Marino    Free Software Foundation, Inc.
4e4b17023SJohn Marino 
5e4b17023SJohn Marino This file is part of GCC.
6e4b17023SJohn Marino 
7e4b17023SJohn Marino GCC is free software; you can redistribute it and/or modify it under
8e4b17023SJohn Marino the terms of the GNU General Public License as published by the Free
9e4b17023SJohn Marino Software Foundation; either version 3, or (at your option) any later
10e4b17023SJohn Marino version.
11e4b17023SJohn Marino 
12e4b17023SJohn Marino GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13e4b17023SJohn Marino WARRANTY; without even the implied warranty of MERCHANTABILITY or
14e4b17023SJohn Marino FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15e4b17023SJohn Marino for more details.
16e4b17023SJohn Marino 
17e4b17023SJohn Marino You should have received a copy of the GNU General Public License
18e4b17023SJohn Marino along with GCC; see the file COPYING3.  If not see
19e4b17023SJohn Marino <http://www.gnu.org/licenses/>.  */
20e4b17023SJohn Marino 
21e4b17023SJohn Marino /* References:
22e4b17023SJohn Marino 
23e4b17023SJohn Marino    [1] "Branch Prediction for Free"
24e4b17023SJohn Marino        Ball and Larus; PLDI '93.
25e4b17023SJohn Marino    [2] "Static Branch Frequency and Program Profile Analysis"
26e4b17023SJohn Marino        Wu and Larus; MICRO-27.
27e4b17023SJohn Marino    [3] "Corpus-based Static Branch Prediction"
28e4b17023SJohn Marino        Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95.  */
29e4b17023SJohn Marino 
30e4b17023SJohn Marino 
31e4b17023SJohn Marino #include "config.h"
32e4b17023SJohn Marino #include "system.h"
33e4b17023SJohn Marino #include "coretypes.h"
34e4b17023SJohn Marino #include "tm.h"
35e4b17023SJohn Marino #include "tree.h"
36e4b17023SJohn Marino #include "rtl.h"
37e4b17023SJohn Marino #include "tm_p.h"
38e4b17023SJohn Marino #include "hard-reg-set.h"
39e4b17023SJohn Marino #include "basic-block.h"
40e4b17023SJohn Marino #include "insn-config.h"
41e4b17023SJohn Marino #include "regs.h"
42e4b17023SJohn Marino #include "flags.h"
43e4b17023SJohn Marino #include "output.h"
44e4b17023SJohn Marino #include "function.h"
45e4b17023SJohn Marino #include "except.h"
46e4b17023SJohn Marino #include "diagnostic-core.h"
47e4b17023SJohn Marino #include "recog.h"
48e4b17023SJohn Marino #include "expr.h"
49e4b17023SJohn Marino #include "predict.h"
50e4b17023SJohn Marino #include "coverage.h"
51e4b17023SJohn Marino #include "sreal.h"
52e4b17023SJohn Marino #include "params.h"
53e4b17023SJohn Marino #include "target.h"
54e4b17023SJohn Marino #include "cfgloop.h"
55e4b17023SJohn Marino #include "tree-flow.h"
56e4b17023SJohn Marino #include "ggc.h"
57e4b17023SJohn Marino #include "tree-dump.h"
58e4b17023SJohn Marino #include "tree-pass.h"
59e4b17023SJohn Marino #include "timevar.h"
60e4b17023SJohn Marino #include "tree-scalar-evolution.h"
61e4b17023SJohn Marino #include "cfgloop.h"
62e4b17023SJohn Marino #include "pointer-set.h"
63e4b17023SJohn Marino 
64e4b17023SJohn Marino /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
65e4b17023SJohn Marino 		   1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX.  */
66e4b17023SJohn Marino static sreal real_zero, real_one, real_almost_one, real_br_prob_base,
67e4b17023SJohn Marino 	     real_inv_br_prob_base, real_one_half, real_bb_freq_max;
68e4b17023SJohn Marino 
69e4b17023SJohn Marino /* Random guesstimation given names.
70e4b17023SJohn Marino    PROV_VERY_UNLIKELY should be small enough so basic block predicted
71e4b17023SJohn Marino    by it gets bellow HOT_BB_FREQUENCY_FRANCTION.  */
72e4b17023SJohn Marino #define PROB_VERY_UNLIKELY	(REG_BR_PROB_BASE / 2000 - 1)
73e4b17023SJohn Marino #define PROB_EVEN		(REG_BR_PROB_BASE / 2)
74e4b17023SJohn Marino #define PROB_VERY_LIKELY	(REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
75e4b17023SJohn Marino #define PROB_ALWAYS		(REG_BR_PROB_BASE)
76e4b17023SJohn Marino 
77e4b17023SJohn Marino static void combine_predictions_for_insn (rtx, basic_block);
78e4b17023SJohn Marino static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
79e4b17023SJohn Marino static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction);
80e4b17023SJohn Marino static void predict_paths_leading_to_edge (edge, enum br_predictor, enum prediction);
81e4b17023SJohn Marino static bool can_predict_insn_p (const_rtx);
82e4b17023SJohn Marino 
83e4b17023SJohn Marino /* Information we hold about each branch predictor.
84e4b17023SJohn Marino    Filled using information from predict.def.  */
85e4b17023SJohn Marino 
86e4b17023SJohn Marino struct predictor_info
87e4b17023SJohn Marino {
88e4b17023SJohn Marino   const char *const name;	/* Name used in the debugging dumps.  */
89e4b17023SJohn Marino   const int hitrate;		/* Expected hitrate used by
90e4b17023SJohn Marino 				   predict_insn_def call.  */
91e4b17023SJohn Marino   const int flags;
92e4b17023SJohn Marino };
93e4b17023SJohn Marino 
94e4b17023SJohn Marino /* Use given predictor without Dempster-Shaffer theory if it matches
95e4b17023SJohn Marino    using first_match heuristics.  */
96e4b17023SJohn Marino #define PRED_FLAG_FIRST_MATCH 1
97e4b17023SJohn Marino 
98e4b17023SJohn Marino /* Recompute hitrate in percent to our representation.  */
99e4b17023SJohn Marino 
100e4b17023SJohn Marino #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
101e4b17023SJohn Marino 
102e4b17023SJohn Marino #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
103e4b17023SJohn Marino static const struct predictor_info predictor_info[]= {
104e4b17023SJohn Marino #include "predict.def"
105e4b17023SJohn Marino 
106e4b17023SJohn Marino   /* Upper bound on predictors.  */
107e4b17023SJohn Marino   {NULL, 0, 0}
108e4b17023SJohn Marino };
109e4b17023SJohn Marino #undef DEF_PREDICTOR
110e4b17023SJohn Marino 
111e4b17023SJohn Marino /* Return TRUE if frequency FREQ is considered to be hot.  */
112e4b17023SJohn Marino 
113e4b17023SJohn Marino static inline bool
maybe_hot_frequency_p(int freq)114e4b17023SJohn Marino maybe_hot_frequency_p (int freq)
115e4b17023SJohn Marino {
116e4b17023SJohn Marino   struct cgraph_node *node = cgraph_get_node (current_function_decl);
117e4b17023SJohn Marino   if (!profile_info || !flag_branch_probabilities)
118e4b17023SJohn Marino     {
119e4b17023SJohn Marino       if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
120e4b17023SJohn Marino         return false;
121e4b17023SJohn Marino       if (node->frequency == NODE_FREQUENCY_HOT)
122e4b17023SJohn Marino         return true;
123e4b17023SJohn Marino     }
124e4b17023SJohn Marino   if (profile_status == PROFILE_ABSENT)
125e4b17023SJohn Marino     return true;
126e4b17023SJohn Marino   if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
127e4b17023SJohn Marino       && freq < (ENTRY_BLOCK_PTR->frequency * 2 / 3))
128e4b17023SJohn Marino     return false;
129e4b17023SJohn Marino   if (freq < ENTRY_BLOCK_PTR->frequency / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
130e4b17023SJohn Marino     return false;
131e4b17023SJohn Marino   return true;
132e4b17023SJohn Marino }
133e4b17023SJohn Marino 
134e4b17023SJohn Marino /* Return TRUE if frequency FREQ is considered to be hot.  */
135e4b17023SJohn Marino 
136e4b17023SJohn Marino static inline bool
maybe_hot_count_p(gcov_type count)137e4b17023SJohn Marino maybe_hot_count_p (gcov_type count)
138e4b17023SJohn Marino {
139e4b17023SJohn Marino   if (profile_status != PROFILE_READ)
140e4b17023SJohn Marino     return true;
141e4b17023SJohn Marino   /* Code executed at most once is not hot.  */
142e4b17023SJohn Marino   if (profile_info->runs >= count)
143e4b17023SJohn Marino     return false;
144e4b17023SJohn Marino   return (count
145e4b17023SJohn Marino 	  > profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION));
146e4b17023SJohn Marino }
147e4b17023SJohn Marino 
148e4b17023SJohn Marino /* Return true in case BB can be CPU intensive and should be optimized
149e4b17023SJohn Marino    for maximal performance.  */
150e4b17023SJohn Marino 
151e4b17023SJohn Marino bool
maybe_hot_bb_p(const_basic_block bb)152e4b17023SJohn Marino maybe_hot_bb_p (const_basic_block bb)
153e4b17023SJohn Marino {
154e4b17023SJohn Marino   if (profile_status == PROFILE_READ)
155e4b17023SJohn Marino     return maybe_hot_count_p (bb->count);
156e4b17023SJohn Marino   return maybe_hot_frequency_p (bb->frequency);
157e4b17023SJohn Marino }
158e4b17023SJohn Marino 
159e4b17023SJohn Marino /* Return true if the call can be hot.  */
160e4b17023SJohn Marino 
161e4b17023SJohn Marino bool
cgraph_maybe_hot_edge_p(struct cgraph_edge * edge)162e4b17023SJohn Marino cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
163e4b17023SJohn Marino {
164e4b17023SJohn Marino   if (profile_info && flag_branch_probabilities
165e4b17023SJohn Marino       && (edge->count
166e4b17023SJohn Marino 	  <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
167e4b17023SJohn Marino     return false;
168e4b17023SJohn Marino   if (edge->caller->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED
169e4b17023SJohn Marino       || edge->callee->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
170e4b17023SJohn Marino     return false;
171e4b17023SJohn Marino   if (edge->caller->frequency > NODE_FREQUENCY_UNLIKELY_EXECUTED
172e4b17023SJohn Marino       && edge->callee->frequency <= NODE_FREQUENCY_EXECUTED_ONCE)
173e4b17023SJohn Marino     return false;
174e4b17023SJohn Marino   if (optimize_size)
175e4b17023SJohn Marino     return false;
176e4b17023SJohn Marino   if (edge->caller->frequency == NODE_FREQUENCY_HOT)
177e4b17023SJohn Marino     return true;
178e4b17023SJohn Marino   if (edge->caller->frequency == NODE_FREQUENCY_EXECUTED_ONCE
179e4b17023SJohn Marino       && edge->frequency < CGRAPH_FREQ_BASE * 3 / 2)
180e4b17023SJohn Marino     return false;
181e4b17023SJohn Marino   if (flag_guess_branch_prob
182e4b17023SJohn Marino       && edge->frequency <= (CGRAPH_FREQ_BASE
183e4b17023SJohn Marino       			     / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
184e4b17023SJohn Marino     return false;
185e4b17023SJohn Marino   return true;
186e4b17023SJohn Marino }
187e4b17023SJohn Marino 
188e4b17023SJohn Marino /* Return true in case BB can be CPU intensive and should be optimized
189e4b17023SJohn Marino    for maximal performance.  */
190e4b17023SJohn Marino 
191e4b17023SJohn Marino bool
maybe_hot_edge_p(edge e)192e4b17023SJohn Marino maybe_hot_edge_p (edge e)
193e4b17023SJohn Marino {
194e4b17023SJohn Marino   if (profile_status == PROFILE_READ)
195e4b17023SJohn Marino     return maybe_hot_count_p (e->count);
196e4b17023SJohn Marino   return maybe_hot_frequency_p (EDGE_FREQUENCY (e));
197e4b17023SJohn Marino }
198e4b17023SJohn Marino 
199e4b17023SJohn Marino 
200e4b17023SJohn Marino /* Return true in case BB is probably never executed.  */
201e4b17023SJohn Marino 
202e4b17023SJohn Marino bool
probably_never_executed_bb_p(const_basic_block bb)203e4b17023SJohn Marino probably_never_executed_bb_p (const_basic_block bb)
204e4b17023SJohn Marino {
205e4b17023SJohn Marino   if (profile_info && flag_branch_probabilities)
206e4b17023SJohn Marino     return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
207e4b17023SJohn Marino   if ((!profile_info || !flag_branch_probabilities)
208e4b17023SJohn Marino       && (cgraph_get_node (current_function_decl)->frequency
209e4b17023SJohn Marino 	  == NODE_FREQUENCY_UNLIKELY_EXECUTED))
210e4b17023SJohn Marino     return true;
211e4b17023SJohn Marino   return false;
212e4b17023SJohn Marino }
213e4b17023SJohn Marino 
214e4b17023SJohn Marino /* Return true if NODE should be optimized for size.  */
215e4b17023SJohn Marino 
216e4b17023SJohn Marino bool
cgraph_optimize_for_size_p(struct cgraph_node * node)217e4b17023SJohn Marino cgraph_optimize_for_size_p (struct cgraph_node *node)
218e4b17023SJohn Marino {
219e4b17023SJohn Marino   if (optimize_size)
220e4b17023SJohn Marino     return true;
221e4b17023SJohn Marino   if (node && (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED))
222e4b17023SJohn Marino     return true;
223e4b17023SJohn Marino   else
224e4b17023SJohn Marino     return false;
225e4b17023SJohn Marino }
226e4b17023SJohn Marino 
227e4b17023SJohn Marino /* Return true when current function should always be optimized for size.  */
228e4b17023SJohn Marino 
229e4b17023SJohn Marino bool
optimize_function_for_size_p(struct function * fun)230e4b17023SJohn Marino optimize_function_for_size_p (struct function *fun)
231e4b17023SJohn Marino {
232e4b17023SJohn Marino   if (optimize_size)
233e4b17023SJohn Marino     return true;
234e4b17023SJohn Marino   if (!fun || !fun->decl)
235e4b17023SJohn Marino     return false;
236e4b17023SJohn Marino   return cgraph_optimize_for_size_p (cgraph_get_node (fun->decl));
237e4b17023SJohn Marino }
238e4b17023SJohn Marino 
239e4b17023SJohn Marino /* Return true when current function should always be optimized for speed.  */
240e4b17023SJohn Marino 
241e4b17023SJohn Marino bool
optimize_function_for_speed_p(struct function * fun)242e4b17023SJohn Marino optimize_function_for_speed_p (struct function *fun)
243e4b17023SJohn Marino {
244e4b17023SJohn Marino   return !optimize_function_for_size_p (fun);
245e4b17023SJohn Marino }
246e4b17023SJohn Marino 
247e4b17023SJohn Marino /* Return TRUE when BB should be optimized for size.  */
248e4b17023SJohn Marino 
249e4b17023SJohn Marino bool
optimize_bb_for_size_p(const_basic_block bb)250e4b17023SJohn Marino optimize_bb_for_size_p (const_basic_block bb)
251e4b17023SJohn Marino {
252e4b17023SJohn Marino   return optimize_function_for_size_p (cfun) || !maybe_hot_bb_p (bb);
253e4b17023SJohn Marino }
254e4b17023SJohn Marino 
255e4b17023SJohn Marino /* Return TRUE when BB should be optimized for speed.  */
256e4b17023SJohn Marino 
257e4b17023SJohn Marino bool
optimize_bb_for_speed_p(const_basic_block bb)258e4b17023SJohn Marino optimize_bb_for_speed_p (const_basic_block bb)
259e4b17023SJohn Marino {
260e4b17023SJohn Marino   return !optimize_bb_for_size_p (bb);
261e4b17023SJohn Marino }
262e4b17023SJohn Marino 
263e4b17023SJohn Marino /* Return TRUE when BB should be optimized for size.  */
264e4b17023SJohn Marino 
265e4b17023SJohn Marino bool
optimize_edge_for_size_p(edge e)266e4b17023SJohn Marino optimize_edge_for_size_p (edge e)
267e4b17023SJohn Marino {
268e4b17023SJohn Marino   return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
269e4b17023SJohn Marino }
270e4b17023SJohn Marino 
271e4b17023SJohn Marino /* Return TRUE when BB should be optimized for speed.  */
272e4b17023SJohn Marino 
273e4b17023SJohn Marino bool
optimize_edge_for_speed_p(edge e)274e4b17023SJohn Marino optimize_edge_for_speed_p (edge e)
275e4b17023SJohn Marino {
276e4b17023SJohn Marino   return !optimize_edge_for_size_p (e);
277e4b17023SJohn Marino }
278e4b17023SJohn Marino 
279e4b17023SJohn Marino /* Return TRUE when BB should be optimized for size.  */
280e4b17023SJohn Marino 
281e4b17023SJohn Marino bool
optimize_insn_for_size_p(void)282e4b17023SJohn Marino optimize_insn_for_size_p (void)
283e4b17023SJohn Marino {
284e4b17023SJohn Marino   return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
285e4b17023SJohn Marino }
286e4b17023SJohn Marino 
287e4b17023SJohn Marino /* Return TRUE when BB should be optimized for speed.  */
288e4b17023SJohn Marino 
289e4b17023SJohn Marino bool
optimize_insn_for_speed_p(void)290e4b17023SJohn Marino optimize_insn_for_speed_p (void)
291e4b17023SJohn Marino {
292e4b17023SJohn Marino   return !optimize_insn_for_size_p ();
293e4b17023SJohn Marino }
294e4b17023SJohn Marino 
295e4b17023SJohn Marino /* Return TRUE when LOOP should be optimized for size.  */
296e4b17023SJohn Marino 
297e4b17023SJohn Marino bool
optimize_loop_for_size_p(struct loop * loop)298e4b17023SJohn Marino optimize_loop_for_size_p (struct loop *loop)
299e4b17023SJohn Marino {
300e4b17023SJohn Marino   return optimize_bb_for_size_p (loop->header);
301e4b17023SJohn Marino }
302e4b17023SJohn Marino 
303e4b17023SJohn Marino /* Return TRUE when LOOP should be optimized for speed.  */
304e4b17023SJohn Marino 
305e4b17023SJohn Marino bool
optimize_loop_for_speed_p(struct loop * loop)306e4b17023SJohn Marino optimize_loop_for_speed_p (struct loop *loop)
307e4b17023SJohn Marino {
308e4b17023SJohn Marino   return optimize_bb_for_speed_p (loop->header);
309e4b17023SJohn Marino }
310e4b17023SJohn Marino 
311e4b17023SJohn Marino /* Return TRUE when LOOP nest should be optimized for speed.  */
312e4b17023SJohn Marino 
313e4b17023SJohn Marino bool
optimize_loop_nest_for_speed_p(struct loop * loop)314e4b17023SJohn Marino optimize_loop_nest_for_speed_p (struct loop *loop)
315e4b17023SJohn Marino {
316e4b17023SJohn Marino   struct loop *l = loop;
317e4b17023SJohn Marino   if (optimize_loop_for_speed_p (loop))
318e4b17023SJohn Marino     return true;
319e4b17023SJohn Marino   l = loop->inner;
320e4b17023SJohn Marino   while (l && l != loop)
321e4b17023SJohn Marino     {
322e4b17023SJohn Marino       if (optimize_loop_for_speed_p (l))
323e4b17023SJohn Marino         return true;
324e4b17023SJohn Marino       if (l->inner)
325e4b17023SJohn Marino         l = l->inner;
326e4b17023SJohn Marino       else if (l->next)
327e4b17023SJohn Marino         l = l->next;
328e4b17023SJohn Marino       else
329e4b17023SJohn Marino         {
330e4b17023SJohn Marino 	  while (l != loop && !l->next)
331e4b17023SJohn Marino 	    l = loop_outer (l);
332e4b17023SJohn Marino 	  if (l != loop)
333e4b17023SJohn Marino 	    l = l->next;
334e4b17023SJohn Marino 	}
335e4b17023SJohn Marino     }
336e4b17023SJohn Marino   return false;
337e4b17023SJohn Marino }
338e4b17023SJohn Marino 
339e4b17023SJohn Marino /* Return TRUE when LOOP nest should be optimized for size.  */
340e4b17023SJohn Marino 
341e4b17023SJohn Marino bool
optimize_loop_nest_for_size_p(struct loop * loop)342e4b17023SJohn Marino optimize_loop_nest_for_size_p (struct loop *loop)
343e4b17023SJohn Marino {
344e4b17023SJohn Marino   return !optimize_loop_nest_for_speed_p (loop);
345e4b17023SJohn Marino }
346e4b17023SJohn Marino 
347e4b17023SJohn Marino /* Return true when edge E is likely to be well predictable by branch
348e4b17023SJohn Marino    predictor.  */
349e4b17023SJohn Marino 
350e4b17023SJohn Marino bool
predictable_edge_p(edge e)351e4b17023SJohn Marino predictable_edge_p (edge e)
352e4b17023SJohn Marino {
353e4b17023SJohn Marino   if (profile_status == PROFILE_ABSENT)
354e4b17023SJohn Marino     return false;
355e4b17023SJohn Marino   if ((e->probability
356e4b17023SJohn Marino        <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
357e4b17023SJohn Marino       || (REG_BR_PROB_BASE - e->probability
358e4b17023SJohn Marino           <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
359e4b17023SJohn Marino     return true;
360e4b17023SJohn Marino   return false;
361e4b17023SJohn Marino }
362e4b17023SJohn Marino 
363e4b17023SJohn Marino 
364e4b17023SJohn Marino /* Set RTL expansion for BB profile.  */
365e4b17023SJohn Marino 
366e4b17023SJohn Marino void
rtl_profile_for_bb(basic_block bb)367e4b17023SJohn Marino rtl_profile_for_bb (basic_block bb)
368e4b17023SJohn Marino {
369e4b17023SJohn Marino   crtl->maybe_hot_insn_p = maybe_hot_bb_p (bb);
370e4b17023SJohn Marino }
371e4b17023SJohn Marino 
372e4b17023SJohn Marino /* Set RTL expansion for edge profile.  */
373e4b17023SJohn Marino 
374e4b17023SJohn Marino void
rtl_profile_for_edge(edge e)375e4b17023SJohn Marino rtl_profile_for_edge (edge e)
376e4b17023SJohn Marino {
377e4b17023SJohn Marino   crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
378e4b17023SJohn Marino }
379e4b17023SJohn Marino 
380e4b17023SJohn Marino /* Set RTL expansion to default mode (i.e. when profile info is not known).  */
381e4b17023SJohn Marino void
default_rtl_profile(void)382e4b17023SJohn Marino default_rtl_profile (void)
383e4b17023SJohn Marino {
384e4b17023SJohn Marino   crtl->maybe_hot_insn_p = true;
385e4b17023SJohn Marino }
386e4b17023SJohn Marino 
387e4b17023SJohn Marino /* Return true if the one of outgoing edges is already predicted by
388e4b17023SJohn Marino    PREDICTOR.  */
389e4b17023SJohn Marino 
390e4b17023SJohn Marino bool
rtl_predicted_by_p(const_basic_block bb,enum br_predictor predictor)391e4b17023SJohn Marino rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
392e4b17023SJohn Marino {
393e4b17023SJohn Marino   rtx note;
394e4b17023SJohn Marino   if (!INSN_P (BB_END (bb)))
395e4b17023SJohn Marino     return false;
396e4b17023SJohn Marino   for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
397e4b17023SJohn Marino     if (REG_NOTE_KIND (note) == REG_BR_PRED
398e4b17023SJohn Marino 	&& INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
399e4b17023SJohn Marino       return true;
400e4b17023SJohn Marino   return false;
401e4b17023SJohn Marino }
402e4b17023SJohn Marino 
403e4b17023SJohn Marino /* This map contains for a basic block the list of predictions for the
404e4b17023SJohn Marino    outgoing edges.  */
405e4b17023SJohn Marino 
406e4b17023SJohn Marino static struct pointer_map_t *bb_predictions;
407e4b17023SJohn Marino 
408e4b17023SJohn Marino /*  Structure representing predictions in tree level. */
409e4b17023SJohn Marino 
410e4b17023SJohn Marino struct edge_prediction {
411e4b17023SJohn Marino     struct edge_prediction *ep_next;
412e4b17023SJohn Marino     edge ep_edge;
413e4b17023SJohn Marino     enum br_predictor ep_predictor;
414e4b17023SJohn Marino     int ep_probability;
415e4b17023SJohn Marino };
416e4b17023SJohn Marino 
417e4b17023SJohn Marino /* Return true if the one of outgoing edges is already predicted by
418e4b17023SJohn Marino    PREDICTOR.  */
419e4b17023SJohn Marino 
420e4b17023SJohn Marino bool
gimple_predicted_by_p(const_basic_block bb,enum br_predictor predictor)421e4b17023SJohn Marino gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
422e4b17023SJohn Marino {
423e4b17023SJohn Marino   struct edge_prediction *i;
424e4b17023SJohn Marino   void **preds = pointer_map_contains (bb_predictions, bb);
425e4b17023SJohn Marino 
426e4b17023SJohn Marino   if (!preds)
427e4b17023SJohn Marino     return false;
428e4b17023SJohn Marino 
429e4b17023SJohn Marino   for (i = (struct edge_prediction *) *preds; i; i = i->ep_next)
430e4b17023SJohn Marino     if (i->ep_predictor == predictor)
431e4b17023SJohn Marino       return true;
432e4b17023SJohn Marino   return false;
433e4b17023SJohn Marino }
434e4b17023SJohn Marino 
435e4b17023SJohn Marino /* Return true when the probability of edge is reliable.
436e4b17023SJohn Marino 
437e4b17023SJohn Marino    The profile guessing code is good at predicting branch outcome (ie.
438e4b17023SJohn Marino    taken/not taken), that is predicted right slightly over 75% of time.
439e4b17023SJohn Marino    It is however notoriously poor on predicting the probability itself.
440e4b17023SJohn Marino    In general the profile appear a lot flatter (with probabilities closer
441e4b17023SJohn Marino    to 50%) than the reality so it is bad idea to use it to drive optimization
442e4b17023SJohn Marino    such as those disabling dynamic branch prediction for well predictable
443e4b17023SJohn Marino    branches.
444e4b17023SJohn Marino 
445e4b17023SJohn Marino    There are two exceptions - edges leading to noreturn edges and edges
446e4b17023SJohn Marino    predicted by number of iterations heuristics are predicted well.  This macro
447e4b17023SJohn Marino    should be able to distinguish those, but at the moment it simply check for
448e4b17023SJohn Marino    noreturn heuristic that is only one giving probability over 99% or bellow
449e4b17023SJohn Marino    1%.  In future we might want to propagate reliability information across the
450e4b17023SJohn Marino    CFG if we find this information useful on multiple places.   */
451e4b17023SJohn Marino static bool
probability_reliable_p(int prob)452e4b17023SJohn Marino probability_reliable_p (int prob)
453e4b17023SJohn Marino {
454e4b17023SJohn Marino   return (profile_status == PROFILE_READ
455e4b17023SJohn Marino 	  || (profile_status == PROFILE_GUESSED
456e4b17023SJohn Marino 	      && (prob <= HITRATE (1) || prob >= HITRATE (99))));
457e4b17023SJohn Marino }
458e4b17023SJohn Marino 
459e4b17023SJohn Marino /* Same predicate as above, working on edges.  */
460e4b17023SJohn Marino bool
edge_probability_reliable_p(const_edge e)461e4b17023SJohn Marino edge_probability_reliable_p (const_edge e)
462e4b17023SJohn Marino {
463e4b17023SJohn Marino   return probability_reliable_p (e->probability);
464e4b17023SJohn Marino }
465e4b17023SJohn Marino 
466e4b17023SJohn Marino /* Same predicate as edge_probability_reliable_p, working on notes.  */
467e4b17023SJohn Marino bool
br_prob_note_reliable_p(const_rtx note)468e4b17023SJohn Marino br_prob_note_reliable_p (const_rtx note)
469e4b17023SJohn Marino {
470e4b17023SJohn Marino   gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
471e4b17023SJohn Marino   return probability_reliable_p (INTVAL (XEXP (note, 0)));
472e4b17023SJohn Marino }
473e4b17023SJohn Marino 
474e4b17023SJohn Marino static void
predict_insn(rtx insn,enum br_predictor predictor,int probability)475e4b17023SJohn Marino predict_insn (rtx insn, enum br_predictor predictor, int probability)
476e4b17023SJohn Marino {
477e4b17023SJohn Marino   gcc_assert (any_condjump_p (insn));
478e4b17023SJohn Marino   if (!flag_guess_branch_prob)
479e4b17023SJohn Marino     return;
480e4b17023SJohn Marino 
481e4b17023SJohn Marino   add_reg_note (insn, REG_BR_PRED,
482e4b17023SJohn Marino 		gen_rtx_CONCAT (VOIDmode,
483e4b17023SJohn Marino 				GEN_INT ((int) predictor),
484e4b17023SJohn Marino 				GEN_INT ((int) probability)));
485e4b17023SJohn Marino }
486e4b17023SJohn Marino 
487e4b17023SJohn Marino /* Predict insn by given predictor.  */
488e4b17023SJohn Marino 
489e4b17023SJohn Marino void
predict_insn_def(rtx insn,enum br_predictor predictor,enum prediction taken)490e4b17023SJohn Marino predict_insn_def (rtx insn, enum br_predictor predictor,
491e4b17023SJohn Marino 		  enum prediction taken)
492e4b17023SJohn Marino {
493e4b17023SJohn Marino    int probability = predictor_info[(int) predictor].hitrate;
494e4b17023SJohn Marino 
495e4b17023SJohn Marino    if (taken != TAKEN)
496e4b17023SJohn Marino      probability = REG_BR_PROB_BASE - probability;
497e4b17023SJohn Marino 
498e4b17023SJohn Marino    predict_insn (insn, predictor, probability);
499e4b17023SJohn Marino }
500e4b17023SJohn Marino 
501e4b17023SJohn Marino /* Predict edge E with given probability if possible.  */
502e4b17023SJohn Marino 
503e4b17023SJohn Marino void
rtl_predict_edge(edge e,enum br_predictor predictor,int probability)504e4b17023SJohn Marino rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
505e4b17023SJohn Marino {
506e4b17023SJohn Marino   rtx last_insn;
507e4b17023SJohn Marino   last_insn = BB_END (e->src);
508e4b17023SJohn Marino 
509e4b17023SJohn Marino   /* We can store the branch prediction information only about
510e4b17023SJohn Marino      conditional jumps.  */
511e4b17023SJohn Marino   if (!any_condjump_p (last_insn))
512e4b17023SJohn Marino     return;
513e4b17023SJohn Marino 
514e4b17023SJohn Marino   /* We always store probability of branching.  */
515e4b17023SJohn Marino   if (e->flags & EDGE_FALLTHRU)
516e4b17023SJohn Marino     probability = REG_BR_PROB_BASE - probability;
517e4b17023SJohn Marino 
518e4b17023SJohn Marino   predict_insn (last_insn, predictor, probability);
519e4b17023SJohn Marino }
520e4b17023SJohn Marino 
521e4b17023SJohn Marino /* Predict edge E with the given PROBABILITY.  */
522e4b17023SJohn Marino void
gimple_predict_edge(edge e,enum br_predictor predictor,int probability)523e4b17023SJohn Marino gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
524e4b17023SJohn Marino {
525e4b17023SJohn Marino   gcc_assert (profile_status != PROFILE_GUESSED);
526e4b17023SJohn Marino   if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
527e4b17023SJohn Marino       && flag_guess_branch_prob && optimize)
528e4b17023SJohn Marino     {
529e4b17023SJohn Marino       struct edge_prediction *i = XNEW (struct edge_prediction);
530e4b17023SJohn Marino       void **preds = pointer_map_insert (bb_predictions, e->src);
531e4b17023SJohn Marino 
532e4b17023SJohn Marino       i->ep_next = (struct edge_prediction *) *preds;
533e4b17023SJohn Marino       *preds = i;
534e4b17023SJohn Marino       i->ep_probability = probability;
535e4b17023SJohn Marino       i->ep_predictor = predictor;
536e4b17023SJohn Marino       i->ep_edge = e;
537e4b17023SJohn Marino     }
538e4b17023SJohn Marino }
539e4b17023SJohn Marino 
540e4b17023SJohn Marino /* Remove all predictions on given basic block that are attached
541e4b17023SJohn Marino    to edge E.  */
542e4b17023SJohn Marino void
remove_predictions_associated_with_edge(edge e)543e4b17023SJohn Marino remove_predictions_associated_with_edge (edge e)
544e4b17023SJohn Marino {
545e4b17023SJohn Marino   void **preds;
546e4b17023SJohn Marino 
547e4b17023SJohn Marino   if (!bb_predictions)
548e4b17023SJohn Marino     return;
549e4b17023SJohn Marino 
550e4b17023SJohn Marino   preds = pointer_map_contains (bb_predictions, e->src);
551e4b17023SJohn Marino 
552e4b17023SJohn Marino   if (preds)
553e4b17023SJohn Marino     {
554e4b17023SJohn Marino       struct edge_prediction **prediction = (struct edge_prediction **) preds;
555e4b17023SJohn Marino       struct edge_prediction *next;
556e4b17023SJohn Marino 
557e4b17023SJohn Marino       while (*prediction)
558e4b17023SJohn Marino 	{
559e4b17023SJohn Marino 	  if ((*prediction)->ep_edge == e)
560e4b17023SJohn Marino 	    {
561e4b17023SJohn Marino 	      next = (*prediction)->ep_next;
562e4b17023SJohn Marino 	      free (*prediction);
563e4b17023SJohn Marino 	      *prediction = next;
564e4b17023SJohn Marino 	    }
565e4b17023SJohn Marino 	  else
566e4b17023SJohn Marino 	    prediction = &((*prediction)->ep_next);
567e4b17023SJohn Marino 	}
568e4b17023SJohn Marino     }
569e4b17023SJohn Marino }
570e4b17023SJohn Marino 
571e4b17023SJohn Marino /* Clears the list of predictions stored for BB.  */
572e4b17023SJohn Marino 
573e4b17023SJohn Marino static void
clear_bb_predictions(basic_block bb)574e4b17023SJohn Marino clear_bb_predictions (basic_block bb)
575e4b17023SJohn Marino {
576e4b17023SJohn Marino   void **preds = pointer_map_contains (bb_predictions, bb);
577e4b17023SJohn Marino   struct edge_prediction *pred, *next;
578e4b17023SJohn Marino 
579e4b17023SJohn Marino   if (!preds)
580e4b17023SJohn Marino     return;
581e4b17023SJohn Marino 
582e4b17023SJohn Marino   for (pred = (struct edge_prediction *) *preds; pred; pred = next)
583e4b17023SJohn Marino     {
584e4b17023SJohn Marino       next = pred->ep_next;
585e4b17023SJohn Marino       free (pred);
586e4b17023SJohn Marino     }
587e4b17023SJohn Marino   *preds = NULL;
588e4b17023SJohn Marino }
589e4b17023SJohn Marino 
590e4b17023SJohn Marino /* Return true when we can store prediction on insn INSN.
591e4b17023SJohn Marino    At the moment we represent predictions only on conditional
592e4b17023SJohn Marino    jumps, not at computed jump or other complicated cases.  */
593e4b17023SJohn Marino static bool
can_predict_insn_p(const_rtx insn)594e4b17023SJohn Marino can_predict_insn_p (const_rtx insn)
595e4b17023SJohn Marino {
596e4b17023SJohn Marino   return (JUMP_P (insn)
597e4b17023SJohn Marino 	  && any_condjump_p (insn)
598e4b17023SJohn Marino 	  && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
599e4b17023SJohn Marino }
600e4b17023SJohn Marino 
601e4b17023SJohn Marino /* Predict edge E by given predictor if possible.  */
602e4b17023SJohn Marino 
603e4b17023SJohn Marino void
predict_edge_def(edge e,enum br_predictor predictor,enum prediction taken)604e4b17023SJohn Marino predict_edge_def (edge e, enum br_predictor predictor,
605e4b17023SJohn Marino 		  enum prediction taken)
606e4b17023SJohn Marino {
607e4b17023SJohn Marino    int probability = predictor_info[(int) predictor].hitrate;
608e4b17023SJohn Marino 
609e4b17023SJohn Marino    if (taken != TAKEN)
610e4b17023SJohn Marino      probability = REG_BR_PROB_BASE - probability;
611e4b17023SJohn Marino 
612e4b17023SJohn Marino    predict_edge (e, predictor, probability);
613e4b17023SJohn Marino }
614e4b17023SJohn Marino 
615e4b17023SJohn Marino /* Invert all branch predictions or probability notes in the INSN.  This needs
616e4b17023SJohn Marino    to be done each time we invert the condition used by the jump.  */
617e4b17023SJohn Marino 
618e4b17023SJohn Marino void
invert_br_probabilities(rtx insn)619e4b17023SJohn Marino invert_br_probabilities (rtx insn)
620e4b17023SJohn Marino {
621e4b17023SJohn Marino   rtx note;
622e4b17023SJohn Marino 
623e4b17023SJohn Marino   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
624e4b17023SJohn Marino     if (REG_NOTE_KIND (note) == REG_BR_PROB)
625e4b17023SJohn Marino       XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
626e4b17023SJohn Marino     else if (REG_NOTE_KIND (note) == REG_BR_PRED)
627e4b17023SJohn Marino       XEXP (XEXP (note, 0), 1)
628e4b17023SJohn Marino 	= GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
629e4b17023SJohn Marino }
630e4b17023SJohn Marino 
631e4b17023SJohn Marino /* Dump information about the branch prediction to the output file.  */
632e4b17023SJohn Marino 
633e4b17023SJohn Marino static void
dump_prediction(FILE * file,enum br_predictor predictor,int probability,basic_block bb,int used)634e4b17023SJohn Marino dump_prediction (FILE *file, enum br_predictor predictor, int probability,
635e4b17023SJohn Marino 		 basic_block bb, int used)
636e4b17023SJohn Marino {
637e4b17023SJohn Marino   edge e;
638e4b17023SJohn Marino   edge_iterator ei;
639e4b17023SJohn Marino 
640e4b17023SJohn Marino   if (!file)
641e4b17023SJohn Marino     return;
642e4b17023SJohn Marino 
643e4b17023SJohn Marino   FOR_EACH_EDGE (e, ei, bb->succs)
644e4b17023SJohn Marino     if (! (e->flags & EDGE_FALLTHRU))
645e4b17023SJohn Marino       break;
646e4b17023SJohn Marino 
647e4b17023SJohn Marino   fprintf (file, "  %s heuristics%s: %.1f%%",
648e4b17023SJohn Marino 	   predictor_info[predictor].name,
649e4b17023SJohn Marino 	   used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
650e4b17023SJohn Marino 
651e4b17023SJohn Marino   if (bb->count)
652e4b17023SJohn Marino     {
653e4b17023SJohn Marino       fprintf (file, "  exec ");
654e4b17023SJohn Marino       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
655e4b17023SJohn Marino       if (e)
656e4b17023SJohn Marino 	{
657e4b17023SJohn Marino 	  fprintf (file, " hit ");
658e4b17023SJohn Marino 	  fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
659e4b17023SJohn Marino 	  fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
660e4b17023SJohn Marino 	}
661e4b17023SJohn Marino     }
662e4b17023SJohn Marino 
663e4b17023SJohn Marino   fprintf (file, "\n");
664e4b17023SJohn Marino }
665e4b17023SJohn Marino 
666e4b17023SJohn Marino /* We can not predict the probabilities of outgoing edges of bb.  Set them
667e4b17023SJohn Marino    evenly and hope for the best.  */
668e4b17023SJohn Marino static void
set_even_probabilities(basic_block bb)669e4b17023SJohn Marino set_even_probabilities (basic_block bb)
670e4b17023SJohn Marino {
671e4b17023SJohn Marino   int nedges = 0;
672e4b17023SJohn Marino   edge e;
673e4b17023SJohn Marino   edge_iterator ei;
674e4b17023SJohn Marino 
675e4b17023SJohn Marino   FOR_EACH_EDGE (e, ei, bb->succs)
676e4b17023SJohn Marino     if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
677e4b17023SJohn Marino       nedges ++;
678e4b17023SJohn Marino   FOR_EACH_EDGE (e, ei, bb->succs)
679e4b17023SJohn Marino     if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
680e4b17023SJohn Marino       e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
681e4b17023SJohn Marino     else
682e4b17023SJohn Marino       e->probability = 0;
683e4b17023SJohn Marino }
684e4b17023SJohn Marino 
685e4b17023SJohn Marino /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
686e4b17023SJohn Marino    note if not already present.  Remove now useless REG_BR_PRED notes.  */
687e4b17023SJohn Marino 
688e4b17023SJohn Marino static void
combine_predictions_for_insn(rtx insn,basic_block bb)689e4b17023SJohn Marino combine_predictions_for_insn (rtx insn, basic_block bb)
690e4b17023SJohn Marino {
691e4b17023SJohn Marino   rtx prob_note;
692e4b17023SJohn Marino   rtx *pnote;
693e4b17023SJohn Marino   rtx note;
694e4b17023SJohn Marino   int best_probability = PROB_EVEN;
695e4b17023SJohn Marino   enum br_predictor best_predictor = END_PREDICTORS;
696e4b17023SJohn Marino   int combined_probability = REG_BR_PROB_BASE / 2;
697e4b17023SJohn Marino   int d;
698e4b17023SJohn Marino   bool first_match = false;
699e4b17023SJohn Marino   bool found = false;
700e4b17023SJohn Marino 
701e4b17023SJohn Marino   if (!can_predict_insn_p (insn))
702e4b17023SJohn Marino     {
703e4b17023SJohn Marino       set_even_probabilities (bb);
704e4b17023SJohn Marino       return;
705e4b17023SJohn Marino     }
706e4b17023SJohn Marino 
707e4b17023SJohn Marino   prob_note = find_reg_note (insn, REG_BR_PROB, 0);
708e4b17023SJohn Marino   pnote = &REG_NOTES (insn);
709e4b17023SJohn Marino   if (dump_file)
710e4b17023SJohn Marino     fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
711e4b17023SJohn Marino 	     bb->index);
712e4b17023SJohn Marino 
713e4b17023SJohn Marino   /* We implement "first match" heuristics and use probability guessed
714e4b17023SJohn Marino      by predictor with smallest index.  */
715e4b17023SJohn Marino   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
716e4b17023SJohn Marino     if (REG_NOTE_KIND (note) == REG_BR_PRED)
717e4b17023SJohn Marino       {
718e4b17023SJohn Marino 	enum br_predictor predictor = ((enum br_predictor)
719e4b17023SJohn Marino 				       INTVAL (XEXP (XEXP (note, 0), 0)));
720e4b17023SJohn Marino 	int probability = INTVAL (XEXP (XEXP (note, 0), 1));
721e4b17023SJohn Marino 
722e4b17023SJohn Marino 	found = true;
723e4b17023SJohn Marino 	if (best_predictor > predictor)
724e4b17023SJohn Marino 	  best_probability = probability, best_predictor = predictor;
725e4b17023SJohn Marino 
726e4b17023SJohn Marino 	d = (combined_probability * probability
727e4b17023SJohn Marino 	     + (REG_BR_PROB_BASE - combined_probability)
728e4b17023SJohn Marino 	     * (REG_BR_PROB_BASE - probability));
729e4b17023SJohn Marino 
730e4b17023SJohn Marino 	/* Use FP math to avoid overflows of 32bit integers.  */
731e4b17023SJohn Marino 	if (d == 0)
732e4b17023SJohn Marino 	  /* If one probability is 0% and one 100%, avoid division by zero.  */
733e4b17023SJohn Marino 	  combined_probability = REG_BR_PROB_BASE / 2;
734e4b17023SJohn Marino 	else
735e4b17023SJohn Marino 	  combined_probability = (((double) combined_probability) * probability
736e4b17023SJohn Marino 				  * REG_BR_PROB_BASE / d + 0.5);
737e4b17023SJohn Marino       }
738e4b17023SJohn Marino 
739e4b17023SJohn Marino   /* Decide which heuristic to use.  In case we didn't match anything,
740e4b17023SJohn Marino      use no_prediction heuristic, in case we did match, use either
741e4b17023SJohn Marino      first match or Dempster-Shaffer theory depending on the flags.  */
742e4b17023SJohn Marino 
743e4b17023SJohn Marino   if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
744e4b17023SJohn Marino     first_match = true;
745e4b17023SJohn Marino 
746e4b17023SJohn Marino   if (!found)
747e4b17023SJohn Marino     dump_prediction (dump_file, PRED_NO_PREDICTION,
748e4b17023SJohn Marino 		     combined_probability, bb, true);
749e4b17023SJohn Marino   else
750e4b17023SJohn Marino     {
751e4b17023SJohn Marino       dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
752e4b17023SJohn Marino 		       bb, !first_match);
753e4b17023SJohn Marino       dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
754e4b17023SJohn Marino 		       bb, first_match);
755e4b17023SJohn Marino     }
756e4b17023SJohn Marino 
757e4b17023SJohn Marino   if (first_match)
758e4b17023SJohn Marino     combined_probability = best_probability;
759e4b17023SJohn Marino   dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
760e4b17023SJohn Marino 
761e4b17023SJohn Marino   while (*pnote)
762e4b17023SJohn Marino     {
763e4b17023SJohn Marino       if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
764e4b17023SJohn Marino 	{
765e4b17023SJohn Marino 	  enum br_predictor predictor = ((enum br_predictor)
766e4b17023SJohn Marino 					 INTVAL (XEXP (XEXP (*pnote, 0), 0)));
767e4b17023SJohn Marino 	  int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
768e4b17023SJohn Marino 
769e4b17023SJohn Marino 	  dump_prediction (dump_file, predictor, probability, bb,
770e4b17023SJohn Marino 			   !first_match || best_predictor == predictor);
771e4b17023SJohn Marino 	  *pnote = XEXP (*pnote, 1);
772e4b17023SJohn Marino 	}
773e4b17023SJohn Marino       else
774e4b17023SJohn Marino 	pnote = &XEXP (*pnote, 1);
775e4b17023SJohn Marino     }
776e4b17023SJohn Marino 
777e4b17023SJohn Marino   if (!prob_note)
778e4b17023SJohn Marino     {
779e4b17023SJohn Marino       add_reg_note (insn, REG_BR_PROB, GEN_INT (combined_probability));
780e4b17023SJohn Marino 
781e4b17023SJohn Marino       /* Save the prediction into CFG in case we are seeing non-degenerated
782e4b17023SJohn Marino 	 conditional jump.  */
783e4b17023SJohn Marino       if (!single_succ_p (bb))
784e4b17023SJohn Marino 	{
785e4b17023SJohn Marino 	  BRANCH_EDGE (bb)->probability = combined_probability;
786e4b17023SJohn Marino 	  FALLTHRU_EDGE (bb)->probability
787e4b17023SJohn Marino 	    = REG_BR_PROB_BASE - combined_probability;
788e4b17023SJohn Marino 	}
789e4b17023SJohn Marino     }
790e4b17023SJohn Marino   else if (!single_succ_p (bb))
791e4b17023SJohn Marino     {
792e4b17023SJohn Marino       int prob = INTVAL (XEXP (prob_note, 0));
793e4b17023SJohn Marino 
794e4b17023SJohn Marino       BRANCH_EDGE (bb)->probability = prob;
795e4b17023SJohn Marino       FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
796e4b17023SJohn Marino     }
797e4b17023SJohn Marino   else
798e4b17023SJohn Marino     single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
799e4b17023SJohn Marino }
800e4b17023SJohn Marino 
801e4b17023SJohn Marino /* Combine predictions into single probability and store them into CFG.
802e4b17023SJohn Marino    Remove now useless prediction entries.  */
803e4b17023SJohn Marino 
804e4b17023SJohn Marino static void
combine_predictions_for_bb(basic_block bb)805e4b17023SJohn Marino combine_predictions_for_bb (basic_block bb)
806e4b17023SJohn Marino {
807e4b17023SJohn Marino   int best_probability = PROB_EVEN;
808e4b17023SJohn Marino   enum br_predictor best_predictor = END_PREDICTORS;
809e4b17023SJohn Marino   int combined_probability = REG_BR_PROB_BASE / 2;
810e4b17023SJohn Marino   int d;
811e4b17023SJohn Marino   bool first_match = false;
812e4b17023SJohn Marino   bool found = false;
813e4b17023SJohn Marino   struct edge_prediction *pred;
814e4b17023SJohn Marino   int nedges = 0;
815e4b17023SJohn Marino   edge e, first = NULL, second = NULL;
816e4b17023SJohn Marino   edge_iterator ei;
817e4b17023SJohn Marino   void **preds;
818e4b17023SJohn Marino 
819e4b17023SJohn Marino   FOR_EACH_EDGE (e, ei, bb->succs)
820e4b17023SJohn Marino     if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
821e4b17023SJohn Marino       {
822e4b17023SJohn Marino 	nedges ++;
823e4b17023SJohn Marino 	if (first && !second)
824e4b17023SJohn Marino 	  second = e;
825e4b17023SJohn Marino 	if (!first)
826e4b17023SJohn Marino 	  first = e;
827e4b17023SJohn Marino       }
828e4b17023SJohn Marino 
829e4b17023SJohn Marino   /* When there is no successor or only one choice, prediction is easy.
830e4b17023SJohn Marino 
831e4b17023SJohn Marino      We are lazy for now and predict only basic blocks with two outgoing
832e4b17023SJohn Marino      edges.  It is possible to predict generic case too, but we have to
833e4b17023SJohn Marino      ignore first match heuristics and do more involved combining.  Implement
834e4b17023SJohn Marino      this later.  */
835e4b17023SJohn Marino   if (nedges != 2)
836e4b17023SJohn Marino     {
837e4b17023SJohn Marino       if (!bb->count)
838e4b17023SJohn Marino 	set_even_probabilities (bb);
839e4b17023SJohn Marino       clear_bb_predictions (bb);
840e4b17023SJohn Marino       if (dump_file)
841e4b17023SJohn Marino 	fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
842e4b17023SJohn Marino 		 nedges, bb->index);
843e4b17023SJohn Marino       return;
844e4b17023SJohn Marino     }
845e4b17023SJohn Marino 
846e4b17023SJohn Marino   if (dump_file)
847e4b17023SJohn Marino     fprintf (dump_file, "Predictions for bb %i\n", bb->index);
848e4b17023SJohn Marino 
849e4b17023SJohn Marino   preds = pointer_map_contains (bb_predictions, bb);
850e4b17023SJohn Marino   if (preds)
851e4b17023SJohn Marino     {
852e4b17023SJohn Marino       /* We implement "first match" heuristics and use probability guessed
853e4b17023SJohn Marino 	 by predictor with smallest index.  */
854e4b17023SJohn Marino       for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
855e4b17023SJohn Marino 	{
856e4b17023SJohn Marino 	  enum br_predictor predictor = pred->ep_predictor;
857e4b17023SJohn Marino 	  int probability = pred->ep_probability;
858e4b17023SJohn Marino 
859e4b17023SJohn Marino 	  if (pred->ep_edge != first)
860e4b17023SJohn Marino 	    probability = REG_BR_PROB_BASE - probability;
861e4b17023SJohn Marino 
862e4b17023SJohn Marino 	  found = true;
863e4b17023SJohn Marino 	  /* First match heuristics would be widly confused if we predicted
864e4b17023SJohn Marino 	     both directions.  */
865e4b17023SJohn Marino 	  if (best_predictor > predictor)
866e4b17023SJohn Marino 	    {
867e4b17023SJohn Marino               struct edge_prediction *pred2;
868e4b17023SJohn Marino 	      int prob = probability;
869e4b17023SJohn Marino 
870e4b17023SJohn Marino               for (pred2 = (struct edge_prediction *) *preds; pred2; pred2 = pred2->ep_next)
871e4b17023SJohn Marino 	       if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
872e4b17023SJohn Marino 	         {
873e4b17023SJohn Marino 	           int probability2 = pred->ep_probability;
874e4b17023SJohn Marino 
875e4b17023SJohn Marino 		   if (pred2->ep_edge != first)
876e4b17023SJohn Marino 		     probability2 = REG_BR_PROB_BASE - probability2;
877e4b17023SJohn Marino 
878e4b17023SJohn Marino 		   if ((probability < REG_BR_PROB_BASE / 2) !=
879e4b17023SJohn Marino 		       (probability2 < REG_BR_PROB_BASE / 2))
880e4b17023SJohn Marino 		     break;
881e4b17023SJohn Marino 
882e4b17023SJohn Marino 		   /* If the same predictor later gave better result, go for it! */
883e4b17023SJohn Marino 		   if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
884e4b17023SJohn Marino 		       || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
885e4b17023SJohn Marino 		     prob = probability2;
886e4b17023SJohn Marino 		 }
887e4b17023SJohn Marino 	      if (!pred2)
888e4b17023SJohn Marino 	        best_probability = prob, best_predictor = predictor;
889e4b17023SJohn Marino 	    }
890e4b17023SJohn Marino 
891e4b17023SJohn Marino 	  d = (combined_probability * probability
892e4b17023SJohn Marino 	       + (REG_BR_PROB_BASE - combined_probability)
893e4b17023SJohn Marino 	       * (REG_BR_PROB_BASE - probability));
894e4b17023SJohn Marino 
895e4b17023SJohn Marino 	  /* Use FP math to avoid overflows of 32bit integers.  */
896e4b17023SJohn Marino 	  if (d == 0)
897e4b17023SJohn Marino 	    /* If one probability is 0% and one 100%, avoid division by zero.  */
898e4b17023SJohn Marino 	    combined_probability = REG_BR_PROB_BASE / 2;
899e4b17023SJohn Marino 	  else
900e4b17023SJohn Marino 	    combined_probability = (((double) combined_probability)
901e4b17023SJohn Marino 				    * probability
902e4b17023SJohn Marino 		    		    * REG_BR_PROB_BASE / d + 0.5);
903e4b17023SJohn Marino 	}
904e4b17023SJohn Marino     }
905e4b17023SJohn Marino 
906e4b17023SJohn Marino   /* Decide which heuristic to use.  In case we didn't match anything,
907e4b17023SJohn Marino      use no_prediction heuristic, in case we did match, use either
908e4b17023SJohn Marino      first match or Dempster-Shaffer theory depending on the flags.  */
909e4b17023SJohn Marino 
910e4b17023SJohn Marino   if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
911e4b17023SJohn Marino     first_match = true;
912e4b17023SJohn Marino 
913e4b17023SJohn Marino   if (!found)
914e4b17023SJohn Marino     dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true);
915e4b17023SJohn Marino   else
916e4b17023SJohn Marino     {
917e4b17023SJohn Marino       dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
918e4b17023SJohn Marino 		       !first_match);
919e4b17023SJohn Marino       dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
920e4b17023SJohn Marino 		       first_match);
921e4b17023SJohn Marino     }
922e4b17023SJohn Marino 
923e4b17023SJohn Marino   if (first_match)
924e4b17023SJohn Marino     combined_probability = best_probability;
925e4b17023SJohn Marino   dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
926e4b17023SJohn Marino 
927e4b17023SJohn Marino   if (preds)
928e4b17023SJohn Marino     {
929e4b17023SJohn Marino       for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
930e4b17023SJohn Marino 	{
931e4b17023SJohn Marino 	  enum br_predictor predictor = pred->ep_predictor;
932e4b17023SJohn Marino 	  int probability = pred->ep_probability;
933e4b17023SJohn Marino 
934e4b17023SJohn Marino 	  if (pred->ep_edge != EDGE_SUCC (bb, 0))
935e4b17023SJohn Marino 	    probability = REG_BR_PROB_BASE - probability;
936e4b17023SJohn Marino 	  dump_prediction (dump_file, predictor, probability, bb,
937e4b17023SJohn Marino 			   !first_match || best_predictor == predictor);
938e4b17023SJohn Marino 	}
939e4b17023SJohn Marino     }
940e4b17023SJohn Marino   clear_bb_predictions (bb);
941e4b17023SJohn Marino 
942e4b17023SJohn Marino   if (!bb->count)
943e4b17023SJohn Marino     {
944e4b17023SJohn Marino       first->probability = combined_probability;
945e4b17023SJohn Marino       second->probability = REG_BR_PROB_BASE - combined_probability;
946e4b17023SJohn Marino     }
947e4b17023SJohn Marino }
948e4b17023SJohn Marino 
949e4b17023SJohn Marino /* Predict edge probabilities by exploiting loop structure.  */
950e4b17023SJohn Marino 
951e4b17023SJohn Marino static void
predict_loops(void)952e4b17023SJohn Marino predict_loops (void)
953e4b17023SJohn Marino {
954e4b17023SJohn Marino   loop_iterator li;
955e4b17023SJohn Marino   struct loop *loop;
956e4b17023SJohn Marino 
957e4b17023SJohn Marino   /* Try to predict out blocks in a loop that are not part of a
958e4b17023SJohn Marino      natural loop.  */
959e4b17023SJohn Marino   FOR_EACH_LOOP (li, loop, 0)
960e4b17023SJohn Marino     {
961e4b17023SJohn Marino       basic_block bb, *bbs;
962e4b17023SJohn Marino       unsigned j, n_exits;
963e4b17023SJohn Marino       VEC (edge, heap) *exits;
964e4b17023SJohn Marino       struct tree_niter_desc niter_desc;
965e4b17023SJohn Marino       edge ex;
966e4b17023SJohn Marino 
967e4b17023SJohn Marino       exits = get_loop_exit_edges (loop);
968e4b17023SJohn Marino       n_exits = VEC_length (edge, exits);
969e4b17023SJohn Marino 
970e4b17023SJohn Marino       FOR_EACH_VEC_ELT (edge, exits, j, ex)
971e4b17023SJohn Marino 	{
972e4b17023SJohn Marino 	  tree niter = NULL;
973e4b17023SJohn Marino 	  HOST_WIDE_INT nitercst;
974e4b17023SJohn Marino 	  int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
975e4b17023SJohn Marino 	  int probability;
976e4b17023SJohn Marino 	  enum br_predictor predictor;
977e4b17023SJohn Marino 
978e4b17023SJohn Marino 	  if (number_of_iterations_exit (loop, ex, &niter_desc, false))
979e4b17023SJohn Marino 	    niter = niter_desc.niter;
980e4b17023SJohn Marino 	  if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
981e4b17023SJohn Marino 	    niter = loop_niter_by_eval (loop, ex);
982e4b17023SJohn Marino 
983e4b17023SJohn Marino 	  if (TREE_CODE (niter) == INTEGER_CST)
984e4b17023SJohn Marino 	    {
985e4b17023SJohn Marino 	      if (host_integerp (niter, 1)
986*95d28233SJohn Marino 		  && max
987e4b17023SJohn Marino 		  && compare_tree_int (niter, max - 1) == -1)
988e4b17023SJohn Marino 		nitercst = tree_low_cst (niter, 1) + 1;
989e4b17023SJohn Marino 	      else
990e4b17023SJohn Marino 		nitercst = max;
991e4b17023SJohn Marino 	      predictor = PRED_LOOP_ITERATIONS;
992e4b17023SJohn Marino 	    }
993e4b17023SJohn Marino 	  /* If we have just one exit and we can derive some information about
994e4b17023SJohn Marino 	     the number of iterations of the loop from the statements inside
995e4b17023SJohn Marino 	     the loop, use it to predict this exit.  */
996e4b17023SJohn Marino 	  else if (n_exits == 1)
997e4b17023SJohn Marino 	    {
998e4b17023SJohn Marino 	      nitercst = max_stmt_executions_int (loop, false);
999e4b17023SJohn Marino 	      if (nitercst < 0)
1000e4b17023SJohn Marino 		continue;
1001e4b17023SJohn Marino 	      if (nitercst > max)
1002e4b17023SJohn Marino 		nitercst = max;
1003e4b17023SJohn Marino 
1004e4b17023SJohn Marino 	      predictor = PRED_LOOP_ITERATIONS_GUESSED;
1005e4b17023SJohn Marino 	    }
1006e4b17023SJohn Marino 	  else
1007e4b17023SJohn Marino 	    continue;
1008e4b17023SJohn Marino 
1009*95d28233SJohn Marino 	  /* If the prediction for number of iterations is zero, do not
1010*95d28233SJohn Marino 	     predict the exit edges.  */
1011*95d28233SJohn Marino 	  if (nitercst == 0)
1012*95d28233SJohn Marino 	    continue;
1013*95d28233SJohn Marino 
1014e4b17023SJohn Marino 	  probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
1015e4b17023SJohn Marino 	  predict_edge (ex, predictor, probability);
1016e4b17023SJohn Marino 	}
1017e4b17023SJohn Marino       VEC_free (edge, heap, exits);
1018e4b17023SJohn Marino 
1019e4b17023SJohn Marino       bbs = get_loop_body (loop);
1020e4b17023SJohn Marino 
1021e4b17023SJohn Marino       for (j = 0; j < loop->num_nodes; j++)
1022e4b17023SJohn Marino 	{
1023e4b17023SJohn Marino 	  int header_found = 0;
1024e4b17023SJohn Marino 	  edge e;
1025e4b17023SJohn Marino 	  edge_iterator ei;
1026e4b17023SJohn Marino 
1027e4b17023SJohn Marino 	  bb = bbs[j];
1028e4b17023SJohn Marino 
1029e4b17023SJohn Marino 	  /* Bypass loop heuristics on continue statement.  These
1030e4b17023SJohn Marino 	     statements construct loops via "non-loop" constructs
1031e4b17023SJohn Marino 	     in the source language and are better to be handled
1032e4b17023SJohn Marino 	     separately.  */
1033e4b17023SJohn Marino 	  if (predicted_by_p (bb, PRED_CONTINUE))
1034e4b17023SJohn Marino 	    continue;
1035e4b17023SJohn Marino 
1036e4b17023SJohn Marino 	  /* Loop branch heuristics - predict an edge back to a
1037e4b17023SJohn Marino 	     loop's head as taken.  */
1038e4b17023SJohn Marino 	  if (bb == loop->latch)
1039e4b17023SJohn Marino 	    {
1040e4b17023SJohn Marino 	      e = find_edge (loop->latch, loop->header);
1041e4b17023SJohn Marino 	      if (e)
1042e4b17023SJohn Marino 		{
1043e4b17023SJohn Marino 		  header_found = 1;
1044e4b17023SJohn Marino 		  predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
1045e4b17023SJohn Marino 		}
1046e4b17023SJohn Marino 	    }
1047e4b17023SJohn Marino 
1048e4b17023SJohn Marino 	  /* Loop exit heuristics - predict an edge exiting the loop if the
1049e4b17023SJohn Marino 	     conditional has no loop header successors as not taken.  */
1050e4b17023SJohn Marino 	  if (!header_found
1051e4b17023SJohn Marino 	      /* If we already used more reliable loop exit predictors, do not
1052e4b17023SJohn Marino 		 bother with PRED_LOOP_EXIT.  */
1053e4b17023SJohn Marino 	      && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
1054e4b17023SJohn Marino 	      && !predicted_by_p (bb, PRED_LOOP_ITERATIONS))
1055e4b17023SJohn Marino 	    {
1056e4b17023SJohn Marino 	      /* For loop with many exits we don't want to predict all exits
1057e4b17023SJohn Marino 	         with the pretty large probability, because if all exits are
1058e4b17023SJohn Marino 		 considered in row, the loop would be predicted to iterate
1059e4b17023SJohn Marino 		 almost never.  The code to divide probability by number of
1060e4b17023SJohn Marino 		 exits is very rough.  It should compute the number of exits
1061e4b17023SJohn Marino 		 taken in each patch through function (not the overall number
1062e4b17023SJohn Marino 		 of exits that might be a lot higher for loops with wide switch
1063e4b17023SJohn Marino 		 statements in them) and compute n-th square root.
1064e4b17023SJohn Marino 
1065e4b17023SJohn Marino 		 We limit the minimal probability by 2% to avoid
1066e4b17023SJohn Marino 		 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1067e4b17023SJohn Marino 		 as this was causing regression in perl benchmark containing such
1068e4b17023SJohn Marino 		 a wide loop.  */
1069e4b17023SJohn Marino 
1070e4b17023SJohn Marino 	      int probability = ((REG_BR_PROB_BASE
1071e4b17023SJohn Marino 		                  - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
1072e4b17023SJohn Marino 				 / n_exits);
1073e4b17023SJohn Marino 	      if (probability < HITRATE (2))
1074e4b17023SJohn Marino 		probability = HITRATE (2);
1075e4b17023SJohn Marino 	      FOR_EACH_EDGE (e, ei, bb->succs)
1076e4b17023SJohn Marino 		if (e->dest->index < NUM_FIXED_BLOCKS
1077e4b17023SJohn Marino 		    || !flow_bb_inside_loop_p (loop, e->dest))
1078e4b17023SJohn Marino 		  predict_edge (e, PRED_LOOP_EXIT, probability);
1079e4b17023SJohn Marino 	    }
1080e4b17023SJohn Marino 	}
1081e4b17023SJohn Marino 
1082e4b17023SJohn Marino       /* Free basic blocks from get_loop_body.  */
1083e4b17023SJohn Marino       free (bbs);
1084e4b17023SJohn Marino     }
1085e4b17023SJohn Marino }
1086e4b17023SJohn Marino 
1087e4b17023SJohn Marino /* Attempt to predict probabilities of BB outgoing edges using local
1088e4b17023SJohn Marino    properties.  */
1089e4b17023SJohn Marino static void
bb_estimate_probability_locally(basic_block bb)1090e4b17023SJohn Marino bb_estimate_probability_locally (basic_block bb)
1091e4b17023SJohn Marino {
1092e4b17023SJohn Marino   rtx last_insn = BB_END (bb);
1093e4b17023SJohn Marino   rtx cond;
1094e4b17023SJohn Marino 
1095e4b17023SJohn Marino   if (! can_predict_insn_p (last_insn))
1096e4b17023SJohn Marino     return;
1097e4b17023SJohn Marino   cond = get_condition (last_insn, NULL, false, false);
1098e4b17023SJohn Marino   if (! cond)
1099e4b17023SJohn Marino     return;
1100e4b17023SJohn Marino 
1101e4b17023SJohn Marino   /* Try "pointer heuristic."
1102e4b17023SJohn Marino      A comparison ptr == 0 is predicted as false.
1103e4b17023SJohn Marino      Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
1104e4b17023SJohn Marino   if (COMPARISON_P (cond)
1105e4b17023SJohn Marino       && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
1106e4b17023SJohn Marino 	  || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
1107e4b17023SJohn Marino     {
1108e4b17023SJohn Marino       if (GET_CODE (cond) == EQ)
1109e4b17023SJohn Marino 	predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
1110e4b17023SJohn Marino       else if (GET_CODE (cond) == NE)
1111e4b17023SJohn Marino 	predict_insn_def (last_insn, PRED_POINTER, TAKEN);
1112e4b17023SJohn Marino     }
1113e4b17023SJohn Marino   else
1114e4b17023SJohn Marino 
1115e4b17023SJohn Marino   /* Try "opcode heuristic."
1116e4b17023SJohn Marino      EQ tests are usually false and NE tests are usually true. Also,
1117e4b17023SJohn Marino      most quantities are positive, so we can make the appropriate guesses
1118e4b17023SJohn Marino      about signed comparisons against zero.  */
1119e4b17023SJohn Marino     switch (GET_CODE (cond))
1120e4b17023SJohn Marino       {
1121e4b17023SJohn Marino       case CONST_INT:
1122e4b17023SJohn Marino 	/* Unconditional branch.  */
1123e4b17023SJohn Marino 	predict_insn_def (last_insn, PRED_UNCONDITIONAL,
1124e4b17023SJohn Marino 			  cond == const0_rtx ? NOT_TAKEN : TAKEN);
1125e4b17023SJohn Marino 	break;
1126e4b17023SJohn Marino 
1127e4b17023SJohn Marino       case EQ:
1128e4b17023SJohn Marino       case UNEQ:
1129e4b17023SJohn Marino 	/* Floating point comparisons appears to behave in a very
1130e4b17023SJohn Marino 	   unpredictable way because of special role of = tests in
1131e4b17023SJohn Marino 	   FP code.  */
1132e4b17023SJohn Marino 	if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1133e4b17023SJohn Marino 	  ;
1134e4b17023SJohn Marino 	/* Comparisons with 0 are often used for booleans and there is
1135e4b17023SJohn Marino 	   nothing useful to predict about them.  */
1136e4b17023SJohn Marino 	else if (XEXP (cond, 1) == const0_rtx
1137e4b17023SJohn Marino 		 || XEXP (cond, 0) == const0_rtx)
1138e4b17023SJohn Marino 	  ;
1139e4b17023SJohn Marino 	else
1140e4b17023SJohn Marino 	  predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
1141e4b17023SJohn Marino 	break;
1142e4b17023SJohn Marino 
1143e4b17023SJohn Marino       case NE:
1144e4b17023SJohn Marino       case LTGT:
1145e4b17023SJohn Marino 	/* Floating point comparisons appears to behave in a very
1146e4b17023SJohn Marino 	   unpredictable way because of special role of = tests in
1147e4b17023SJohn Marino 	   FP code.  */
1148e4b17023SJohn Marino 	if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1149e4b17023SJohn Marino 	  ;
1150e4b17023SJohn Marino 	/* Comparisons with 0 are often used for booleans and there is
1151e4b17023SJohn Marino 	   nothing useful to predict about them.  */
1152e4b17023SJohn Marino 	else if (XEXP (cond, 1) == const0_rtx
1153e4b17023SJohn Marino 		 || XEXP (cond, 0) == const0_rtx)
1154e4b17023SJohn Marino 	  ;
1155e4b17023SJohn Marino 	else
1156e4b17023SJohn Marino 	  predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
1157e4b17023SJohn Marino 	break;
1158e4b17023SJohn Marino 
1159e4b17023SJohn Marino       case ORDERED:
1160e4b17023SJohn Marino 	predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
1161e4b17023SJohn Marino 	break;
1162e4b17023SJohn Marino 
1163e4b17023SJohn Marino       case UNORDERED:
1164e4b17023SJohn Marino 	predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
1165e4b17023SJohn Marino 	break;
1166e4b17023SJohn Marino 
1167e4b17023SJohn Marino       case LE:
1168e4b17023SJohn Marino       case LT:
1169e4b17023SJohn Marino 	if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1170e4b17023SJohn Marino 	    || XEXP (cond, 1) == constm1_rtx)
1171e4b17023SJohn Marino 	  predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
1172e4b17023SJohn Marino 	break;
1173e4b17023SJohn Marino 
1174e4b17023SJohn Marino       case GE:
1175e4b17023SJohn Marino       case GT:
1176e4b17023SJohn Marino 	if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1177e4b17023SJohn Marino 	    || XEXP (cond, 1) == constm1_rtx)
1178e4b17023SJohn Marino 	  predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
1179e4b17023SJohn Marino 	break;
1180e4b17023SJohn Marino 
1181e4b17023SJohn Marino       default:
1182e4b17023SJohn Marino 	break;
1183e4b17023SJohn Marino       }
1184e4b17023SJohn Marino }
1185e4b17023SJohn Marino 
1186e4b17023SJohn Marino /* Set edge->probability for each successor edge of BB.  */
1187e4b17023SJohn Marino void
guess_outgoing_edge_probabilities(basic_block bb)1188e4b17023SJohn Marino guess_outgoing_edge_probabilities (basic_block bb)
1189e4b17023SJohn Marino {
1190e4b17023SJohn Marino   bb_estimate_probability_locally (bb);
1191e4b17023SJohn Marino   combine_predictions_for_insn (BB_END (bb), bb);
1192e4b17023SJohn Marino }
1193e4b17023SJohn Marino 
1194e4b17023SJohn Marino static tree expr_expected_value (tree, bitmap);
1195e4b17023SJohn Marino 
1196e4b17023SJohn Marino /* Helper function for expr_expected_value.  */
1197e4b17023SJohn Marino 
1198e4b17023SJohn Marino static tree
expr_expected_value_1(tree type,tree op0,enum tree_code code,tree op1,bitmap visited)1199e4b17023SJohn Marino expr_expected_value_1 (tree type, tree op0, enum tree_code code,
1200e4b17023SJohn Marino 		       tree op1, bitmap visited)
1201e4b17023SJohn Marino {
1202e4b17023SJohn Marino   gimple def;
1203e4b17023SJohn Marino 
1204e4b17023SJohn Marino   if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1205e4b17023SJohn Marino     {
1206e4b17023SJohn Marino       if (TREE_CONSTANT (op0))
1207e4b17023SJohn Marino 	return op0;
1208e4b17023SJohn Marino 
1209e4b17023SJohn Marino       if (code != SSA_NAME)
1210e4b17023SJohn Marino 	return NULL_TREE;
1211e4b17023SJohn Marino 
1212e4b17023SJohn Marino       def = SSA_NAME_DEF_STMT (op0);
1213e4b17023SJohn Marino 
1214e4b17023SJohn Marino       /* If we were already here, break the infinite cycle.  */
1215e4b17023SJohn Marino       if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
1216e4b17023SJohn Marino 	return NULL;
1217e4b17023SJohn Marino 
1218e4b17023SJohn Marino       if (gimple_code (def) == GIMPLE_PHI)
1219e4b17023SJohn Marino 	{
1220e4b17023SJohn Marino 	  /* All the arguments of the PHI node must have the same constant
1221e4b17023SJohn Marino 	     length.  */
1222e4b17023SJohn Marino 	  int i, n = gimple_phi_num_args (def);
1223e4b17023SJohn Marino 	  tree val = NULL, new_val;
1224e4b17023SJohn Marino 
1225e4b17023SJohn Marino 	  for (i = 0; i < n; i++)
1226e4b17023SJohn Marino 	    {
1227e4b17023SJohn Marino 	      tree arg = PHI_ARG_DEF (def, i);
1228e4b17023SJohn Marino 
1229e4b17023SJohn Marino 	      /* If this PHI has itself as an argument, we cannot
1230e4b17023SJohn Marino 		 determine the string length of this argument.  However,
1231e4b17023SJohn Marino 		 if we can find an expected constant value for the other
1232e4b17023SJohn Marino 		 PHI args then we can still be sure that this is
1233e4b17023SJohn Marino 		 likely a constant.  So be optimistic and just
1234e4b17023SJohn Marino 		 continue with the next argument.  */
1235e4b17023SJohn Marino 	      if (arg == PHI_RESULT (def))
1236e4b17023SJohn Marino 		continue;
1237e4b17023SJohn Marino 
1238e4b17023SJohn Marino 	      new_val = expr_expected_value (arg, visited);
1239e4b17023SJohn Marino 	      if (!new_val)
1240e4b17023SJohn Marino 		return NULL;
1241e4b17023SJohn Marino 	      if (!val)
1242e4b17023SJohn Marino 		val = new_val;
1243e4b17023SJohn Marino 	      else if (!operand_equal_p (val, new_val, false))
1244e4b17023SJohn Marino 		return NULL;
1245e4b17023SJohn Marino 	    }
1246e4b17023SJohn Marino 	  return val;
1247e4b17023SJohn Marino 	}
1248e4b17023SJohn Marino       if (is_gimple_assign (def))
1249e4b17023SJohn Marino 	{
1250e4b17023SJohn Marino 	  if (gimple_assign_lhs (def) != op0)
1251e4b17023SJohn Marino 	    return NULL;
1252e4b17023SJohn Marino 
1253e4b17023SJohn Marino 	  return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
1254e4b17023SJohn Marino 					gimple_assign_rhs1 (def),
1255e4b17023SJohn Marino 					gimple_assign_rhs_code (def),
1256e4b17023SJohn Marino 					gimple_assign_rhs2 (def),
1257e4b17023SJohn Marino 					visited);
1258e4b17023SJohn Marino 	}
1259e4b17023SJohn Marino 
1260e4b17023SJohn Marino       if (is_gimple_call (def))
1261e4b17023SJohn Marino 	{
1262e4b17023SJohn Marino 	  tree decl = gimple_call_fndecl (def);
1263e4b17023SJohn Marino 	  if (!decl)
1264e4b17023SJohn Marino 	    return NULL;
1265e4b17023SJohn Marino 	  if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
1266e4b17023SJohn Marino 	    switch (DECL_FUNCTION_CODE (decl))
1267e4b17023SJohn Marino 	      {
1268e4b17023SJohn Marino 	      case BUILT_IN_EXPECT:
1269e4b17023SJohn Marino 		{
1270e4b17023SJohn Marino 		  tree val;
1271e4b17023SJohn Marino 		  if (gimple_call_num_args (def) != 2)
1272e4b17023SJohn Marino 		    return NULL;
1273e4b17023SJohn Marino 		  val = gimple_call_arg (def, 0);
1274e4b17023SJohn Marino 		  if (TREE_CONSTANT (val))
1275e4b17023SJohn Marino 		    return val;
1276e4b17023SJohn Marino 		  return gimple_call_arg (def, 1);
1277e4b17023SJohn Marino 		}
1278e4b17023SJohn Marino 
1279e4b17023SJohn Marino 	      case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
1280e4b17023SJohn Marino 	      case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
1281e4b17023SJohn Marino 	      case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
1282e4b17023SJohn Marino 	      case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
1283e4b17023SJohn Marino 	      case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
1284e4b17023SJohn Marino 	      case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
1285e4b17023SJohn Marino 	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
1286e4b17023SJohn Marino 	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
1287e4b17023SJohn Marino 	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
1288e4b17023SJohn Marino 	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
1289e4b17023SJohn Marino 	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
1290e4b17023SJohn Marino 	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
1291e4b17023SJohn Marino 	      case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
1292e4b17023SJohn Marino 		/* Assume that any given atomic operation has low contention,
1293e4b17023SJohn Marino 		   and thus the compare-and-swap operation succeeds.  */
1294e4b17023SJohn Marino 		return boolean_true_node;
1295e4b17023SJohn Marino 	    }
1296e4b17023SJohn Marino 	}
1297e4b17023SJohn Marino 
1298e4b17023SJohn Marino       return NULL;
1299e4b17023SJohn Marino     }
1300e4b17023SJohn Marino 
1301e4b17023SJohn Marino   if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
1302e4b17023SJohn Marino     {
1303e4b17023SJohn Marino       tree res;
1304e4b17023SJohn Marino       op0 = expr_expected_value (op0, visited);
1305e4b17023SJohn Marino       if (!op0)
1306e4b17023SJohn Marino 	return NULL;
1307e4b17023SJohn Marino       op1 = expr_expected_value (op1, visited);
1308e4b17023SJohn Marino       if (!op1)
1309e4b17023SJohn Marino 	return NULL;
1310e4b17023SJohn Marino       res = fold_build2 (code, type, op0, op1);
1311e4b17023SJohn Marino       if (TREE_CONSTANT (res))
1312e4b17023SJohn Marino 	return res;
1313e4b17023SJohn Marino       return NULL;
1314e4b17023SJohn Marino     }
1315e4b17023SJohn Marino   if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
1316e4b17023SJohn Marino     {
1317e4b17023SJohn Marino       tree res;
1318e4b17023SJohn Marino       op0 = expr_expected_value (op0, visited);
1319e4b17023SJohn Marino       if (!op0)
1320e4b17023SJohn Marino 	return NULL;
1321e4b17023SJohn Marino       res = fold_build1 (code, type, op0);
1322e4b17023SJohn Marino       if (TREE_CONSTANT (res))
1323e4b17023SJohn Marino 	return res;
1324e4b17023SJohn Marino       return NULL;
1325e4b17023SJohn Marino     }
1326e4b17023SJohn Marino   return NULL;
1327e4b17023SJohn Marino }
1328e4b17023SJohn Marino 
1329e4b17023SJohn Marino /* Return constant EXPR will likely have at execution time, NULL if unknown.
1330e4b17023SJohn Marino    The function is used by builtin_expect branch predictor so the evidence
1331e4b17023SJohn Marino    must come from this construct and additional possible constant folding.
1332e4b17023SJohn Marino 
1333e4b17023SJohn Marino    We may want to implement more involved value guess (such as value range
1334e4b17023SJohn Marino    propagation based prediction), but such tricks shall go to new
1335e4b17023SJohn Marino    implementation.  */
1336e4b17023SJohn Marino 
1337e4b17023SJohn Marino static tree
expr_expected_value(tree expr,bitmap visited)1338e4b17023SJohn Marino expr_expected_value (tree expr, bitmap visited)
1339e4b17023SJohn Marino {
1340e4b17023SJohn Marino   enum tree_code code;
1341e4b17023SJohn Marino   tree op0, op1;
1342e4b17023SJohn Marino 
1343e4b17023SJohn Marino   if (TREE_CONSTANT (expr))
1344e4b17023SJohn Marino     return expr;
1345e4b17023SJohn Marino 
1346e4b17023SJohn Marino   extract_ops_from_tree (expr, &code, &op0, &op1);
1347e4b17023SJohn Marino   return expr_expected_value_1 (TREE_TYPE (expr),
1348e4b17023SJohn Marino 				op0, code, op1, visited);
1349e4b17023SJohn Marino }
1350e4b17023SJohn Marino 
1351e4b17023SJohn Marino 
1352e4b17023SJohn Marino /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
1353e4b17023SJohn Marino    we no longer need.  */
1354e4b17023SJohn Marino static unsigned int
strip_predict_hints(void)1355e4b17023SJohn Marino strip_predict_hints (void)
1356e4b17023SJohn Marino {
1357e4b17023SJohn Marino   basic_block bb;
1358e4b17023SJohn Marino   gimple ass_stmt;
1359e4b17023SJohn Marino   tree var;
1360e4b17023SJohn Marino 
1361e4b17023SJohn Marino   FOR_EACH_BB (bb)
1362e4b17023SJohn Marino     {
1363e4b17023SJohn Marino       gimple_stmt_iterator bi;
1364e4b17023SJohn Marino       for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
1365e4b17023SJohn Marino 	{
1366e4b17023SJohn Marino 	  gimple stmt = gsi_stmt (bi);
1367e4b17023SJohn Marino 
1368e4b17023SJohn Marino 	  if (gimple_code (stmt) == GIMPLE_PREDICT)
1369e4b17023SJohn Marino 	    {
1370e4b17023SJohn Marino 	      gsi_remove (&bi, true);
1371e4b17023SJohn Marino 	      continue;
1372e4b17023SJohn Marino 	    }
1373e4b17023SJohn Marino 	  else if (gimple_code (stmt) == GIMPLE_CALL)
1374e4b17023SJohn Marino 	    {
1375e4b17023SJohn Marino 	      tree fndecl = gimple_call_fndecl (stmt);
1376e4b17023SJohn Marino 
1377e4b17023SJohn Marino 	      if (fndecl
1378e4b17023SJohn Marino 		  && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
1379e4b17023SJohn Marino 		  && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
1380e4b17023SJohn Marino 		  && gimple_call_num_args (stmt) == 2)
1381e4b17023SJohn Marino 		{
1382e4b17023SJohn Marino 		  var = gimple_call_lhs (stmt);
1383e4b17023SJohn Marino 		  if (var)
1384e4b17023SJohn Marino 		    {
1385e4b17023SJohn Marino 		      ass_stmt
1386e4b17023SJohn Marino 			= gimple_build_assign (var, gimple_call_arg (stmt, 0));
1387e4b17023SJohn Marino 		      gsi_replace (&bi, ass_stmt, true);
1388e4b17023SJohn Marino 		    }
1389e4b17023SJohn Marino 		  else
1390e4b17023SJohn Marino 		    {
1391e4b17023SJohn Marino 		      gsi_remove (&bi, true);
1392e4b17023SJohn Marino 		      continue;
1393e4b17023SJohn Marino 		    }
1394e4b17023SJohn Marino 		}
1395e4b17023SJohn Marino 	    }
1396e4b17023SJohn Marino 	  gsi_next (&bi);
1397e4b17023SJohn Marino 	}
1398e4b17023SJohn Marino     }
1399e4b17023SJohn Marino   return 0;
1400e4b17023SJohn Marino }
1401e4b17023SJohn Marino 
1402e4b17023SJohn Marino /* Predict using opcode of the last statement in basic block.  */
1403e4b17023SJohn Marino static void
tree_predict_by_opcode(basic_block bb)1404e4b17023SJohn Marino tree_predict_by_opcode (basic_block bb)
1405e4b17023SJohn Marino {
1406e4b17023SJohn Marino   gimple stmt = last_stmt (bb);
1407e4b17023SJohn Marino   edge then_edge;
1408e4b17023SJohn Marino   tree op0, op1;
1409e4b17023SJohn Marino   tree type;
1410e4b17023SJohn Marino   tree val;
1411e4b17023SJohn Marino   enum tree_code cmp;
1412e4b17023SJohn Marino   bitmap visited;
1413e4b17023SJohn Marino   edge_iterator ei;
1414e4b17023SJohn Marino 
1415e4b17023SJohn Marino   if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1416e4b17023SJohn Marino     return;
1417e4b17023SJohn Marino   FOR_EACH_EDGE (then_edge, ei, bb->succs)
1418e4b17023SJohn Marino     if (then_edge->flags & EDGE_TRUE_VALUE)
1419e4b17023SJohn Marino       break;
1420e4b17023SJohn Marino   op0 = gimple_cond_lhs (stmt);
1421e4b17023SJohn Marino   op1 = gimple_cond_rhs (stmt);
1422e4b17023SJohn Marino   cmp = gimple_cond_code (stmt);
1423e4b17023SJohn Marino   type = TREE_TYPE (op0);
1424e4b17023SJohn Marino   visited = BITMAP_ALLOC (NULL);
1425e4b17023SJohn Marino   val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited);
1426e4b17023SJohn Marino   BITMAP_FREE (visited);
1427e4b17023SJohn Marino   if (val)
1428e4b17023SJohn Marino     {
1429e4b17023SJohn Marino       if (integer_zerop (val))
1430e4b17023SJohn Marino 	predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
1431e4b17023SJohn Marino       else
1432e4b17023SJohn Marino 	predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN);
1433e4b17023SJohn Marino       return;
1434e4b17023SJohn Marino     }
1435e4b17023SJohn Marino   /* Try "pointer heuristic."
1436e4b17023SJohn Marino      A comparison ptr == 0 is predicted as false.
1437e4b17023SJohn Marino      Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
1438e4b17023SJohn Marino   if (POINTER_TYPE_P (type))
1439e4b17023SJohn Marino     {
1440e4b17023SJohn Marino       if (cmp == EQ_EXPR)
1441e4b17023SJohn Marino 	predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
1442e4b17023SJohn Marino       else if (cmp == NE_EXPR)
1443e4b17023SJohn Marino 	predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
1444e4b17023SJohn Marino     }
1445e4b17023SJohn Marino   else
1446e4b17023SJohn Marino 
1447e4b17023SJohn Marino   /* Try "opcode heuristic."
1448e4b17023SJohn Marino      EQ tests are usually false and NE tests are usually true. Also,
1449e4b17023SJohn Marino      most quantities are positive, so we can make the appropriate guesses
1450e4b17023SJohn Marino      about signed comparisons against zero.  */
1451e4b17023SJohn Marino     switch (cmp)
1452e4b17023SJohn Marino       {
1453e4b17023SJohn Marino       case EQ_EXPR:
1454e4b17023SJohn Marino       case UNEQ_EXPR:
1455e4b17023SJohn Marino 	/* Floating point comparisons appears to behave in a very
1456e4b17023SJohn Marino 	   unpredictable way because of special role of = tests in
1457e4b17023SJohn Marino 	   FP code.  */
1458e4b17023SJohn Marino 	if (FLOAT_TYPE_P (type))
1459e4b17023SJohn Marino 	  ;
1460e4b17023SJohn Marino 	/* Comparisons with 0 are often used for booleans and there is
1461e4b17023SJohn Marino 	   nothing useful to predict about them.  */
1462e4b17023SJohn Marino 	else if (integer_zerop (op0) || integer_zerop (op1))
1463e4b17023SJohn Marino 	  ;
1464e4b17023SJohn Marino 	else
1465e4b17023SJohn Marino 	  predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
1466e4b17023SJohn Marino 	break;
1467e4b17023SJohn Marino 
1468e4b17023SJohn Marino       case NE_EXPR:
1469e4b17023SJohn Marino       case LTGT_EXPR:
1470e4b17023SJohn Marino 	/* Floating point comparisons appears to behave in a very
1471e4b17023SJohn Marino 	   unpredictable way because of special role of = tests in
1472e4b17023SJohn Marino 	   FP code.  */
1473e4b17023SJohn Marino 	if (FLOAT_TYPE_P (type))
1474e4b17023SJohn Marino 	  ;
1475e4b17023SJohn Marino 	/* Comparisons with 0 are often used for booleans and there is
1476e4b17023SJohn Marino 	   nothing useful to predict about them.  */
1477e4b17023SJohn Marino 	else if (integer_zerop (op0)
1478e4b17023SJohn Marino 		 || integer_zerop (op1))
1479e4b17023SJohn Marino 	  ;
1480e4b17023SJohn Marino 	else
1481e4b17023SJohn Marino 	  predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
1482e4b17023SJohn Marino 	break;
1483e4b17023SJohn Marino 
1484e4b17023SJohn Marino       case ORDERED_EXPR:
1485e4b17023SJohn Marino 	predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
1486e4b17023SJohn Marino 	break;
1487e4b17023SJohn Marino 
1488e4b17023SJohn Marino       case UNORDERED_EXPR:
1489e4b17023SJohn Marino 	predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
1490e4b17023SJohn Marino 	break;
1491e4b17023SJohn Marino 
1492e4b17023SJohn Marino       case LE_EXPR:
1493e4b17023SJohn Marino       case LT_EXPR:
1494e4b17023SJohn Marino 	if (integer_zerop (op1)
1495e4b17023SJohn Marino 	    || integer_onep (op1)
1496e4b17023SJohn Marino 	    || integer_all_onesp (op1)
1497e4b17023SJohn Marino 	    || real_zerop (op1)
1498e4b17023SJohn Marino 	    || real_onep (op1)
1499e4b17023SJohn Marino 	    || real_minus_onep (op1))
1500e4b17023SJohn Marino 	  predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
1501e4b17023SJohn Marino 	break;
1502e4b17023SJohn Marino 
1503e4b17023SJohn Marino       case GE_EXPR:
1504e4b17023SJohn Marino       case GT_EXPR:
1505e4b17023SJohn Marino 	if (integer_zerop (op1)
1506e4b17023SJohn Marino 	    || integer_onep (op1)
1507e4b17023SJohn Marino 	    || integer_all_onesp (op1)
1508e4b17023SJohn Marino 	    || real_zerop (op1)
1509e4b17023SJohn Marino 	    || real_onep (op1)
1510e4b17023SJohn Marino 	    || real_minus_onep (op1))
1511e4b17023SJohn Marino 	  predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
1512e4b17023SJohn Marino 	break;
1513e4b17023SJohn Marino 
1514e4b17023SJohn Marino       default:
1515e4b17023SJohn Marino 	break;
1516e4b17023SJohn Marino       }
1517e4b17023SJohn Marino }
1518e4b17023SJohn Marino 
1519e4b17023SJohn Marino /* Try to guess whether the value of return means error code.  */
1520e4b17023SJohn Marino 
1521e4b17023SJohn Marino static enum br_predictor
return_prediction(tree val,enum prediction * prediction)1522e4b17023SJohn Marino return_prediction (tree val, enum prediction *prediction)
1523e4b17023SJohn Marino {
1524e4b17023SJohn Marino   /* VOID.  */
1525e4b17023SJohn Marino   if (!val)
1526e4b17023SJohn Marino     return PRED_NO_PREDICTION;
1527e4b17023SJohn Marino   /* Different heuristics for pointers and scalars.  */
1528e4b17023SJohn Marino   if (POINTER_TYPE_P (TREE_TYPE (val)))
1529e4b17023SJohn Marino     {
1530e4b17023SJohn Marino       /* NULL is usually not returned.  */
1531e4b17023SJohn Marino       if (integer_zerop (val))
1532e4b17023SJohn Marino 	{
1533e4b17023SJohn Marino 	  *prediction = NOT_TAKEN;
1534e4b17023SJohn Marino 	  return PRED_NULL_RETURN;
1535e4b17023SJohn Marino 	}
1536e4b17023SJohn Marino     }
1537e4b17023SJohn Marino   else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
1538e4b17023SJohn Marino     {
1539e4b17023SJohn Marino       /* Negative return values are often used to indicate
1540e4b17023SJohn Marino          errors.  */
1541e4b17023SJohn Marino       if (TREE_CODE (val) == INTEGER_CST
1542e4b17023SJohn Marino 	  && tree_int_cst_sgn (val) < 0)
1543e4b17023SJohn Marino 	{
1544e4b17023SJohn Marino 	  *prediction = NOT_TAKEN;
1545e4b17023SJohn Marino 	  return PRED_NEGATIVE_RETURN;
1546e4b17023SJohn Marino 	}
1547e4b17023SJohn Marino       /* Constant return values seems to be commonly taken.
1548e4b17023SJohn Marino          Zero/one often represent booleans so exclude them from the
1549e4b17023SJohn Marino 	 heuristics.  */
1550e4b17023SJohn Marino       if (TREE_CONSTANT (val)
1551e4b17023SJohn Marino 	  && (!integer_zerop (val) && !integer_onep (val)))
1552e4b17023SJohn Marino 	{
1553e4b17023SJohn Marino 	  *prediction = TAKEN;
1554e4b17023SJohn Marino 	  return PRED_CONST_RETURN;
1555e4b17023SJohn Marino 	}
1556e4b17023SJohn Marino     }
1557e4b17023SJohn Marino   return PRED_NO_PREDICTION;
1558e4b17023SJohn Marino }
1559e4b17023SJohn Marino 
1560e4b17023SJohn Marino /* Find the basic block with return expression and look up for possible
1561e4b17023SJohn Marino    return value trying to apply RETURN_PREDICTION heuristics.  */
1562e4b17023SJohn Marino static void
apply_return_prediction(void)1563e4b17023SJohn Marino apply_return_prediction (void)
1564e4b17023SJohn Marino {
1565e4b17023SJohn Marino   gimple return_stmt = NULL;
1566e4b17023SJohn Marino   tree return_val;
1567e4b17023SJohn Marino   edge e;
1568e4b17023SJohn Marino   gimple phi;
1569e4b17023SJohn Marino   int phi_num_args, i;
1570e4b17023SJohn Marino   enum br_predictor pred;
1571e4b17023SJohn Marino   enum prediction direction;
1572e4b17023SJohn Marino   edge_iterator ei;
1573e4b17023SJohn Marino 
1574e4b17023SJohn Marino   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1575e4b17023SJohn Marino     {
1576e4b17023SJohn Marino       return_stmt = last_stmt (e->src);
1577e4b17023SJohn Marino       if (return_stmt
1578e4b17023SJohn Marino 	  && gimple_code (return_stmt) == GIMPLE_RETURN)
1579e4b17023SJohn Marino 	break;
1580e4b17023SJohn Marino     }
1581e4b17023SJohn Marino   if (!e)
1582e4b17023SJohn Marino     return;
1583e4b17023SJohn Marino   return_val = gimple_return_retval (return_stmt);
1584e4b17023SJohn Marino   if (!return_val)
1585e4b17023SJohn Marino     return;
1586e4b17023SJohn Marino   if (TREE_CODE (return_val) != SSA_NAME
1587e4b17023SJohn Marino       || !SSA_NAME_DEF_STMT (return_val)
1588e4b17023SJohn Marino       || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
1589e4b17023SJohn Marino     return;
1590e4b17023SJohn Marino   phi = SSA_NAME_DEF_STMT (return_val);
1591e4b17023SJohn Marino   phi_num_args = gimple_phi_num_args (phi);
1592e4b17023SJohn Marino   pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
1593e4b17023SJohn Marino 
1594e4b17023SJohn Marino   /* Avoid the degenerate case where all return values form the function
1595e4b17023SJohn Marino      belongs to same category (ie they are all positive constants)
1596e4b17023SJohn Marino      so we can hardly say something about them.  */
1597e4b17023SJohn Marino   for (i = 1; i < phi_num_args; i++)
1598e4b17023SJohn Marino     if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
1599e4b17023SJohn Marino       break;
1600e4b17023SJohn Marino   if (i != phi_num_args)
1601e4b17023SJohn Marino     for (i = 0; i < phi_num_args; i++)
1602e4b17023SJohn Marino       {
1603e4b17023SJohn Marino 	pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
1604e4b17023SJohn Marino 	if (pred != PRED_NO_PREDICTION)
1605e4b17023SJohn Marino 	  predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
1606e4b17023SJohn Marino 				         direction);
1607e4b17023SJohn Marino       }
1608e4b17023SJohn Marino }
1609e4b17023SJohn Marino 
1610e4b17023SJohn Marino /* Look for basic block that contains unlikely to happen events
1611e4b17023SJohn Marino    (such as noreturn calls) and mark all paths leading to execution
1612e4b17023SJohn Marino    of this basic blocks as unlikely.  */
1613e4b17023SJohn Marino 
1614e4b17023SJohn Marino static void
tree_bb_level_predictions(void)1615e4b17023SJohn Marino tree_bb_level_predictions (void)
1616e4b17023SJohn Marino {
1617e4b17023SJohn Marino   basic_block bb;
1618e4b17023SJohn Marino   bool has_return_edges = false;
1619e4b17023SJohn Marino   edge e;
1620e4b17023SJohn Marino   edge_iterator ei;
1621e4b17023SJohn Marino 
1622e4b17023SJohn Marino   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1623e4b17023SJohn Marino     if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
1624e4b17023SJohn Marino       {
1625e4b17023SJohn Marino         has_return_edges = true;
1626e4b17023SJohn Marino 	break;
1627e4b17023SJohn Marino       }
1628e4b17023SJohn Marino 
1629e4b17023SJohn Marino   apply_return_prediction ();
1630e4b17023SJohn Marino 
1631e4b17023SJohn Marino   FOR_EACH_BB (bb)
1632e4b17023SJohn Marino     {
1633e4b17023SJohn Marino       gimple_stmt_iterator gsi;
1634e4b17023SJohn Marino 
1635e4b17023SJohn Marino       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1636e4b17023SJohn Marino 	{
1637e4b17023SJohn Marino 	  gimple stmt = gsi_stmt (gsi);
1638e4b17023SJohn Marino 	  tree decl;
1639e4b17023SJohn Marino 
1640e4b17023SJohn Marino 	  if (is_gimple_call (stmt))
1641e4b17023SJohn Marino 	    {
1642e4b17023SJohn Marino 	      if ((gimple_call_flags (stmt) & ECF_NORETURN)
1643e4b17023SJohn Marino 	          && has_return_edges)
1644e4b17023SJohn Marino 		predict_paths_leading_to (bb, PRED_NORETURN,
1645e4b17023SJohn Marino 					  NOT_TAKEN);
1646e4b17023SJohn Marino 	      decl = gimple_call_fndecl (stmt);
1647e4b17023SJohn Marino 	      if (decl
1648e4b17023SJohn Marino 		  && lookup_attribute ("cold",
1649e4b17023SJohn Marino 				       DECL_ATTRIBUTES (decl)))
1650e4b17023SJohn Marino 		predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
1651e4b17023SJohn Marino 					  NOT_TAKEN);
1652e4b17023SJohn Marino 	    }
1653e4b17023SJohn Marino 	  else if (gimple_code (stmt) == GIMPLE_PREDICT)
1654e4b17023SJohn Marino 	    {
1655e4b17023SJohn Marino 	      predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
1656e4b17023SJohn Marino 					gimple_predict_outcome (stmt));
1657e4b17023SJohn Marino 	      /* Keep GIMPLE_PREDICT around so early inlining will propagate
1658e4b17023SJohn Marino 	         hints to callers.  */
1659e4b17023SJohn Marino 	    }
1660e4b17023SJohn Marino 	}
1661e4b17023SJohn Marino     }
1662e4b17023SJohn Marino }
1663e4b17023SJohn Marino 
1664e4b17023SJohn Marino #ifdef ENABLE_CHECKING
1665e4b17023SJohn Marino 
1666e4b17023SJohn Marino /* Callback for pointer_map_traverse, asserts that the pointer map is
1667e4b17023SJohn Marino    empty.  */
1668e4b17023SJohn Marino 
1669e4b17023SJohn Marino static bool
assert_is_empty(const void * key ATTRIBUTE_UNUSED,void ** value,void * data ATTRIBUTE_UNUSED)1670e4b17023SJohn Marino assert_is_empty (const void *key ATTRIBUTE_UNUSED, void **value,
1671e4b17023SJohn Marino 		 void *data ATTRIBUTE_UNUSED)
1672e4b17023SJohn Marino {
1673e4b17023SJohn Marino   gcc_assert (!*value);
1674e4b17023SJohn Marino   return false;
1675e4b17023SJohn Marino }
1676e4b17023SJohn Marino #endif
1677e4b17023SJohn Marino 
1678e4b17023SJohn Marino /* Predict branch probabilities and estimate profile for basic block BB.  */
1679e4b17023SJohn Marino 
1680e4b17023SJohn Marino static void
tree_estimate_probability_bb(basic_block bb)1681e4b17023SJohn Marino tree_estimate_probability_bb (basic_block bb)
1682e4b17023SJohn Marino {
1683e4b17023SJohn Marino   edge e;
1684e4b17023SJohn Marino   edge_iterator ei;
1685e4b17023SJohn Marino   gimple last;
1686e4b17023SJohn Marino 
1687e4b17023SJohn Marino   FOR_EACH_EDGE (e, ei, bb->succs)
1688e4b17023SJohn Marino     {
1689e4b17023SJohn Marino       /* Predict early returns to be probable, as we've already taken
1690e4b17023SJohn Marino 	 care for error returns and other cases are often used for
1691e4b17023SJohn Marino 	 fast paths through function.
1692e4b17023SJohn Marino 
1693e4b17023SJohn Marino 	 Since we've already removed the return statements, we are
1694e4b17023SJohn Marino 	 looking for CFG like:
1695e4b17023SJohn Marino 
1696e4b17023SJohn Marino 	 if (conditional)
1697e4b17023SJohn Marino 	 {
1698e4b17023SJohn Marino 	 ..
1699e4b17023SJohn Marino 	 goto return_block
1700e4b17023SJohn Marino 	 }
1701e4b17023SJohn Marino 	 some other blocks
1702e4b17023SJohn Marino 	 return_block:
1703e4b17023SJohn Marino 	 return_stmt.  */
1704e4b17023SJohn Marino       if (e->dest != bb->next_bb
1705e4b17023SJohn Marino 	  && e->dest != EXIT_BLOCK_PTR
1706e4b17023SJohn Marino 	  && single_succ_p (e->dest)
1707e4b17023SJohn Marino 	  && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
1708e4b17023SJohn Marino 	  && (last = last_stmt (e->dest)) != NULL
1709e4b17023SJohn Marino 	  && gimple_code (last) == GIMPLE_RETURN)
1710e4b17023SJohn Marino 	{
1711e4b17023SJohn Marino 	  edge e1;
1712e4b17023SJohn Marino 	  edge_iterator ei1;
1713e4b17023SJohn Marino 
1714e4b17023SJohn Marino 	  if (single_succ_p (bb))
1715e4b17023SJohn Marino 	    {
1716e4b17023SJohn Marino 	      FOR_EACH_EDGE (e1, ei1, bb->preds)
1717e4b17023SJohn Marino 		if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
1718e4b17023SJohn Marino 		    && !predicted_by_p (e1->src, PRED_CONST_RETURN)
1719e4b17023SJohn Marino 		    && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
1720e4b17023SJohn Marino 		  predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1721e4b17023SJohn Marino 	    }
1722e4b17023SJohn Marino 	  else
1723e4b17023SJohn Marino 	    if (!predicted_by_p (e->src, PRED_NULL_RETURN)
1724e4b17023SJohn Marino 		&& !predicted_by_p (e->src, PRED_CONST_RETURN)
1725e4b17023SJohn Marino 		&& !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
1726e4b17023SJohn Marino 	      predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1727e4b17023SJohn Marino 	}
1728e4b17023SJohn Marino 
1729e4b17023SJohn Marino       /* Look for block we are guarding (ie we dominate it,
1730e4b17023SJohn Marino 	 but it doesn't postdominate us).  */
1731e4b17023SJohn Marino       if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
1732e4b17023SJohn Marino 	  && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
1733e4b17023SJohn Marino 	  && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
1734e4b17023SJohn Marino 	{
1735e4b17023SJohn Marino 	  gimple_stmt_iterator bi;
1736e4b17023SJohn Marino 
1737e4b17023SJohn Marino 	  /* The call heuristic claims that a guarded function call
1738e4b17023SJohn Marino 	     is improbable.  This is because such calls are often used
1739e4b17023SJohn Marino 	     to signal exceptional situations such as printing error
1740e4b17023SJohn Marino 	     messages.  */
1741e4b17023SJohn Marino 	  for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
1742e4b17023SJohn Marino 	       gsi_next (&bi))
1743e4b17023SJohn Marino 	    {
1744e4b17023SJohn Marino 	      gimple stmt = gsi_stmt (bi);
1745e4b17023SJohn Marino 	      if (is_gimple_call (stmt)
1746e4b17023SJohn Marino 		  /* Constant and pure calls are hardly used to signalize
1747e4b17023SJohn Marino 		     something exceptional.  */
1748e4b17023SJohn Marino 		  && gimple_has_side_effects (stmt))
1749e4b17023SJohn Marino 		{
1750e4b17023SJohn Marino 		  predict_edge_def (e, PRED_CALL, NOT_TAKEN);
1751e4b17023SJohn Marino 		  break;
1752e4b17023SJohn Marino 		}
1753e4b17023SJohn Marino 	    }
1754e4b17023SJohn Marino 	}
1755e4b17023SJohn Marino     }
1756e4b17023SJohn Marino   tree_predict_by_opcode (bb);
1757e4b17023SJohn Marino }
1758e4b17023SJohn Marino 
1759e4b17023SJohn Marino /* Predict branch probabilities and estimate profile of the tree CFG.
1760e4b17023SJohn Marino    This function can be called from the loop optimizers to recompute
1761e4b17023SJohn Marino    the profile information.  */
1762e4b17023SJohn Marino 
1763e4b17023SJohn Marino void
tree_estimate_probability(void)1764e4b17023SJohn Marino tree_estimate_probability (void)
1765e4b17023SJohn Marino {
1766e4b17023SJohn Marino   basic_block bb;
1767e4b17023SJohn Marino 
1768e4b17023SJohn Marino   add_noreturn_fake_exit_edges ();
1769e4b17023SJohn Marino   connect_infinite_loops_to_exit ();
1770e4b17023SJohn Marino   /* We use loop_niter_by_eval, which requires that the loops have
1771e4b17023SJohn Marino      preheaders.  */
1772e4b17023SJohn Marino   create_preheaders (CP_SIMPLE_PREHEADERS);
1773e4b17023SJohn Marino   calculate_dominance_info (CDI_POST_DOMINATORS);
1774e4b17023SJohn Marino 
1775e4b17023SJohn Marino   bb_predictions = pointer_map_create ();
1776e4b17023SJohn Marino   tree_bb_level_predictions ();
1777e4b17023SJohn Marino   record_loop_exits ();
1778e4b17023SJohn Marino 
1779e4b17023SJohn Marino   if (number_of_loops () > 1)
1780e4b17023SJohn Marino     predict_loops ();
1781e4b17023SJohn Marino 
1782e4b17023SJohn Marino   FOR_EACH_BB (bb)
1783e4b17023SJohn Marino     tree_estimate_probability_bb (bb);
1784e4b17023SJohn Marino 
1785e4b17023SJohn Marino   FOR_EACH_BB (bb)
1786e4b17023SJohn Marino     combine_predictions_for_bb (bb);
1787e4b17023SJohn Marino 
1788e4b17023SJohn Marino #ifdef ENABLE_CHECKING
1789e4b17023SJohn Marino   pointer_map_traverse (bb_predictions, assert_is_empty, NULL);
1790e4b17023SJohn Marino #endif
1791e4b17023SJohn Marino   pointer_map_destroy (bb_predictions);
1792e4b17023SJohn Marino   bb_predictions = NULL;
1793e4b17023SJohn Marino 
1794e4b17023SJohn Marino   estimate_bb_frequencies ();
1795e4b17023SJohn Marino   free_dominance_info (CDI_POST_DOMINATORS);
1796e4b17023SJohn Marino   remove_fake_exit_edges ();
1797e4b17023SJohn Marino }
1798e4b17023SJohn Marino 
1799e4b17023SJohn Marino /* Predict branch probabilities and estimate profile of the tree CFG.
1800e4b17023SJohn Marino    This is the driver function for PASS_PROFILE.  */
1801e4b17023SJohn Marino 
1802e4b17023SJohn Marino static unsigned int
tree_estimate_probability_driver(void)1803e4b17023SJohn Marino tree_estimate_probability_driver (void)
1804e4b17023SJohn Marino {
1805e4b17023SJohn Marino   unsigned nb_loops;
1806e4b17023SJohn Marino 
1807e4b17023SJohn Marino   loop_optimizer_init (0);
1808e4b17023SJohn Marino   if (dump_file && (dump_flags & TDF_DETAILS))
1809e4b17023SJohn Marino     flow_loops_dump (dump_file, NULL, 0);
1810e4b17023SJohn Marino 
1811e4b17023SJohn Marino   mark_irreducible_loops ();
1812e4b17023SJohn Marino 
1813e4b17023SJohn Marino   nb_loops = number_of_loops ();
1814e4b17023SJohn Marino   if (nb_loops > 1)
1815e4b17023SJohn Marino     scev_initialize ();
1816e4b17023SJohn Marino 
1817e4b17023SJohn Marino   tree_estimate_probability ();
1818e4b17023SJohn Marino 
1819e4b17023SJohn Marino   if (nb_loops > 1)
1820e4b17023SJohn Marino     scev_finalize ();
1821e4b17023SJohn Marino 
1822e4b17023SJohn Marino   loop_optimizer_finalize ();
1823e4b17023SJohn Marino   if (dump_file && (dump_flags & TDF_DETAILS))
1824e4b17023SJohn Marino     gimple_dump_cfg (dump_file, dump_flags);
1825e4b17023SJohn Marino   if (profile_status == PROFILE_ABSENT)
1826e4b17023SJohn Marino     profile_status = PROFILE_GUESSED;
1827e4b17023SJohn Marino   return 0;
1828e4b17023SJohn Marino }
1829e4b17023SJohn Marino 
1830e4b17023SJohn Marino /* Predict edges to successors of CUR whose sources are not postdominated by
1831e4b17023SJohn Marino    BB by PRED and recurse to all postdominators.  */
1832e4b17023SJohn Marino 
1833e4b17023SJohn Marino static void
predict_paths_for_bb(basic_block cur,basic_block bb,enum br_predictor pred,enum prediction taken,bitmap visited)1834e4b17023SJohn Marino predict_paths_for_bb (basic_block cur, basic_block bb,
1835e4b17023SJohn Marino 		      enum br_predictor pred,
1836e4b17023SJohn Marino 		      enum prediction taken,
1837e4b17023SJohn Marino 		      bitmap visited)
1838e4b17023SJohn Marino {
1839e4b17023SJohn Marino   edge e;
1840e4b17023SJohn Marino   edge_iterator ei;
1841e4b17023SJohn Marino   basic_block son;
1842e4b17023SJohn Marino 
1843e4b17023SJohn Marino   /* We are looking for all edges forming edge cut induced by
1844e4b17023SJohn Marino      set of all blocks postdominated by BB.  */
1845e4b17023SJohn Marino   FOR_EACH_EDGE (e, ei, cur->preds)
1846e4b17023SJohn Marino     if (e->src->index >= NUM_FIXED_BLOCKS
1847e4b17023SJohn Marino 	&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
1848e4b17023SJohn Marino     {
1849e4b17023SJohn Marino       edge e2;
1850e4b17023SJohn Marino       edge_iterator ei2;
1851e4b17023SJohn Marino       bool found = false;
1852e4b17023SJohn Marino 
1853e4b17023SJohn Marino       /* Ignore fake edges and eh, we predict them as not taken anyway.  */
1854e4b17023SJohn Marino       if (e->flags & (EDGE_EH | EDGE_FAKE))
1855e4b17023SJohn Marino 	continue;
1856e4b17023SJohn Marino       gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
1857e4b17023SJohn Marino 
1858e4b17023SJohn Marino       /* See if there is an edge from e->src that is not abnormal
1859e4b17023SJohn Marino 	 and does not lead to BB.  */
1860e4b17023SJohn Marino       FOR_EACH_EDGE (e2, ei2, e->src->succs)
1861e4b17023SJohn Marino 	if (e2 != e
1862e4b17023SJohn Marino 	    && !(e2->flags & (EDGE_EH | EDGE_FAKE))
1863e4b17023SJohn Marino 	    && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb))
1864e4b17023SJohn Marino 	  {
1865e4b17023SJohn Marino 	    found = true;
1866e4b17023SJohn Marino 	    break;
1867e4b17023SJohn Marino 	  }
1868e4b17023SJohn Marino 
1869e4b17023SJohn Marino       /* If there is non-abnormal path leaving e->src, predict edge
1870e4b17023SJohn Marino 	 using predictor.  Otherwise we need to look for paths
1871e4b17023SJohn Marino 	 leading to e->src.
1872e4b17023SJohn Marino 
1873e4b17023SJohn Marino 	 The second may lead to infinite loop in the case we are predicitng
1874e4b17023SJohn Marino 	 regions that are only reachable by abnormal edges.  We simply
1875e4b17023SJohn Marino 	 prevent visiting given BB twice.  */
1876e4b17023SJohn Marino       if (found)
1877e4b17023SJohn Marino         predict_edge_def (e, pred, taken);
1878e4b17023SJohn Marino       else if (bitmap_set_bit (visited, e->src->index))
1879e4b17023SJohn Marino 	predict_paths_for_bb (e->src, e->src, pred, taken, visited);
1880e4b17023SJohn Marino     }
1881e4b17023SJohn Marino   for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
1882e4b17023SJohn Marino        son;
1883e4b17023SJohn Marino        son = next_dom_son (CDI_POST_DOMINATORS, son))
1884e4b17023SJohn Marino     predict_paths_for_bb (son, bb, pred, taken, visited);
1885e4b17023SJohn Marino }
1886e4b17023SJohn Marino 
1887e4b17023SJohn Marino /* Sets branch probabilities according to PREDiction and
1888e4b17023SJohn Marino    FLAGS.  */
1889e4b17023SJohn Marino 
1890e4b17023SJohn Marino static void
predict_paths_leading_to(basic_block bb,enum br_predictor pred,enum prediction taken)1891e4b17023SJohn Marino predict_paths_leading_to (basic_block bb, enum br_predictor pred,
1892e4b17023SJohn Marino 			  enum prediction taken)
1893e4b17023SJohn Marino {
1894e4b17023SJohn Marino   bitmap visited = BITMAP_ALLOC (NULL);
1895e4b17023SJohn Marino   predict_paths_for_bb (bb, bb, pred, taken, visited);
1896e4b17023SJohn Marino   BITMAP_FREE (visited);
1897e4b17023SJohn Marino }
1898e4b17023SJohn Marino 
1899e4b17023SJohn Marino /* Like predict_paths_leading_to but take edge instead of basic block.  */
1900e4b17023SJohn Marino 
1901e4b17023SJohn Marino static void
predict_paths_leading_to_edge(edge e,enum br_predictor pred,enum prediction taken)1902e4b17023SJohn Marino predict_paths_leading_to_edge (edge e, enum br_predictor pred,
1903e4b17023SJohn Marino 			       enum prediction taken)
1904e4b17023SJohn Marino {
1905e4b17023SJohn Marino   bool has_nonloop_edge = false;
1906e4b17023SJohn Marino   edge_iterator ei;
1907e4b17023SJohn Marino   edge e2;
1908e4b17023SJohn Marino 
1909e4b17023SJohn Marino   basic_block bb = e->src;
1910e4b17023SJohn Marino   FOR_EACH_EDGE (e2, ei, bb->succs)
1911e4b17023SJohn Marino     if (e2->dest != e->src && e2->dest != e->dest
1912e4b17023SJohn Marino 	&& !(e->flags & (EDGE_EH | EDGE_FAKE))
1913e4b17023SJohn Marino 	&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
1914e4b17023SJohn Marino       {
1915e4b17023SJohn Marino 	has_nonloop_edge = true;
1916e4b17023SJohn Marino 	break;
1917e4b17023SJohn Marino       }
1918e4b17023SJohn Marino   if (!has_nonloop_edge)
1919e4b17023SJohn Marino     {
1920e4b17023SJohn Marino       bitmap visited = BITMAP_ALLOC (NULL);
1921e4b17023SJohn Marino       predict_paths_for_bb (bb, bb, pred, taken, visited);
1922e4b17023SJohn Marino       BITMAP_FREE (visited);
1923e4b17023SJohn Marino     }
1924e4b17023SJohn Marino   else
1925e4b17023SJohn Marino     predict_edge_def (e, pred, taken);
1926e4b17023SJohn Marino }
1927e4b17023SJohn Marino 
1928e4b17023SJohn Marino /* This is used to carry information about basic blocks.  It is
1929e4b17023SJohn Marino    attached to the AUX field of the standard CFG block.  */
1930e4b17023SJohn Marino 
1931e4b17023SJohn Marino typedef struct block_info_def
1932e4b17023SJohn Marino {
1933e4b17023SJohn Marino   /* Estimated frequency of execution of basic_block.  */
1934e4b17023SJohn Marino   sreal frequency;
1935e4b17023SJohn Marino 
1936e4b17023SJohn Marino   /* To keep queue of basic blocks to process.  */
1937e4b17023SJohn Marino   basic_block next;
1938e4b17023SJohn Marino 
1939e4b17023SJohn Marino   /* Number of predecessors we need to visit first.  */
1940e4b17023SJohn Marino   int npredecessors;
1941e4b17023SJohn Marino } *block_info;
1942e4b17023SJohn Marino 
1943e4b17023SJohn Marino /* Similar information for edges.  */
1944e4b17023SJohn Marino typedef struct edge_info_def
1945e4b17023SJohn Marino {
1946e4b17023SJohn Marino   /* In case edge is a loopback edge, the probability edge will be reached
1947e4b17023SJohn Marino      in case header is.  Estimated number of iterations of the loop can be
1948e4b17023SJohn Marino      then computed as 1 / (1 - back_edge_prob).  */
1949e4b17023SJohn Marino   sreal back_edge_prob;
1950e4b17023SJohn Marino   /* True if the edge is a loopback edge in the natural loop.  */
1951e4b17023SJohn Marino   unsigned int back_edge:1;
1952e4b17023SJohn Marino } *edge_info;
1953e4b17023SJohn Marino 
1954e4b17023SJohn Marino #define BLOCK_INFO(B)	((block_info) (B)->aux)
1955e4b17023SJohn Marino #define EDGE_INFO(E)	((edge_info) (E)->aux)
1956e4b17023SJohn Marino 
1957e4b17023SJohn Marino /* Helper function for estimate_bb_frequencies.
1958e4b17023SJohn Marino    Propagate the frequencies in blocks marked in
1959e4b17023SJohn Marino    TOVISIT, starting in HEAD.  */
1960e4b17023SJohn Marino 
1961e4b17023SJohn Marino static void
propagate_freq(basic_block head,bitmap tovisit)1962e4b17023SJohn Marino propagate_freq (basic_block head, bitmap tovisit)
1963e4b17023SJohn Marino {
1964e4b17023SJohn Marino   basic_block bb;
1965e4b17023SJohn Marino   basic_block last;
1966e4b17023SJohn Marino   unsigned i;
1967e4b17023SJohn Marino   edge e;
1968e4b17023SJohn Marino   basic_block nextbb;
1969e4b17023SJohn Marino   bitmap_iterator bi;
1970e4b17023SJohn Marino 
1971e4b17023SJohn Marino   /* For each basic block we need to visit count number of his predecessors
1972e4b17023SJohn Marino      we need to visit first.  */
1973e4b17023SJohn Marino   EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
1974e4b17023SJohn Marino     {
1975e4b17023SJohn Marino       edge_iterator ei;
1976e4b17023SJohn Marino       int count = 0;
1977e4b17023SJohn Marino 
1978e4b17023SJohn Marino       bb = BASIC_BLOCK (i);
1979e4b17023SJohn Marino 
1980e4b17023SJohn Marino       FOR_EACH_EDGE (e, ei, bb->preds)
1981e4b17023SJohn Marino 	{
1982e4b17023SJohn Marino 	  bool visit = bitmap_bit_p (tovisit, e->src->index);
1983e4b17023SJohn Marino 
1984e4b17023SJohn Marino 	  if (visit && !(e->flags & EDGE_DFS_BACK))
1985e4b17023SJohn Marino 	    count++;
1986e4b17023SJohn Marino 	  else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
1987e4b17023SJohn Marino 	    fprintf (dump_file,
1988e4b17023SJohn Marino 		     "Irreducible region hit, ignoring edge to %i->%i\n",
1989e4b17023SJohn Marino 		     e->src->index, bb->index);
1990e4b17023SJohn Marino 	}
1991e4b17023SJohn Marino       BLOCK_INFO (bb)->npredecessors = count;
1992e4b17023SJohn Marino       /* When function never returns, we will never process exit block.  */
1993e4b17023SJohn Marino       if (!count && bb == EXIT_BLOCK_PTR)
1994e4b17023SJohn Marino 	bb->count = bb->frequency = 0;
1995e4b17023SJohn Marino     }
1996e4b17023SJohn Marino 
1997e4b17023SJohn Marino   memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
1998e4b17023SJohn Marino   last = head;
1999e4b17023SJohn Marino   for (bb = head; bb; bb = nextbb)
2000e4b17023SJohn Marino     {
2001e4b17023SJohn Marino       edge_iterator ei;
2002e4b17023SJohn Marino       sreal cyclic_probability, frequency;
2003e4b17023SJohn Marino 
2004e4b17023SJohn Marino       memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
2005e4b17023SJohn Marino       memcpy (&frequency, &real_zero, sizeof (real_zero));
2006e4b17023SJohn Marino 
2007e4b17023SJohn Marino       nextbb = BLOCK_INFO (bb)->next;
2008e4b17023SJohn Marino       BLOCK_INFO (bb)->next = NULL;
2009e4b17023SJohn Marino 
2010e4b17023SJohn Marino       /* Compute frequency of basic block.  */
2011e4b17023SJohn Marino       if (bb != head)
2012e4b17023SJohn Marino 	{
2013e4b17023SJohn Marino #ifdef ENABLE_CHECKING
2014e4b17023SJohn Marino 	  FOR_EACH_EDGE (e, ei, bb->preds)
2015e4b17023SJohn Marino 	    gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
2016e4b17023SJohn Marino 			|| (e->flags & EDGE_DFS_BACK));
2017e4b17023SJohn Marino #endif
2018e4b17023SJohn Marino 
2019e4b17023SJohn Marino 	  FOR_EACH_EDGE (e, ei, bb->preds)
2020e4b17023SJohn Marino 	    if (EDGE_INFO (e)->back_edge)
2021e4b17023SJohn Marino 	      {
2022e4b17023SJohn Marino 		sreal_add (&cyclic_probability, &cyclic_probability,
2023e4b17023SJohn Marino 			   &EDGE_INFO (e)->back_edge_prob);
2024e4b17023SJohn Marino 	      }
2025e4b17023SJohn Marino 	    else if (!(e->flags & EDGE_DFS_BACK))
2026e4b17023SJohn Marino 	      {
2027e4b17023SJohn Marino 		sreal tmp;
2028e4b17023SJohn Marino 
2029e4b17023SJohn Marino 		/*  frequency += (e->probability
2030e4b17023SJohn Marino 				  * BLOCK_INFO (e->src)->frequency /
2031e4b17023SJohn Marino 				  REG_BR_PROB_BASE);  */
2032e4b17023SJohn Marino 
2033e4b17023SJohn Marino 		sreal_init (&tmp, e->probability, 0);
2034e4b17023SJohn Marino 		sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
2035e4b17023SJohn Marino 		sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
2036e4b17023SJohn Marino 		sreal_add (&frequency, &frequency, &tmp);
2037e4b17023SJohn Marino 	      }
2038e4b17023SJohn Marino 
2039e4b17023SJohn Marino 	  if (sreal_compare (&cyclic_probability, &real_zero) == 0)
2040e4b17023SJohn Marino 	    {
2041e4b17023SJohn Marino 	      memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
2042e4b17023SJohn Marino 		      sizeof (frequency));
2043e4b17023SJohn Marino 	    }
2044e4b17023SJohn Marino 	  else
2045e4b17023SJohn Marino 	    {
2046e4b17023SJohn Marino 	      if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
2047e4b17023SJohn Marino 		{
2048e4b17023SJohn Marino 		  memcpy (&cyclic_probability, &real_almost_one,
2049e4b17023SJohn Marino 			  sizeof (real_almost_one));
2050e4b17023SJohn Marino 		}
2051e4b17023SJohn Marino 
2052e4b17023SJohn Marino 	      /* BLOCK_INFO (bb)->frequency = frequency
2053e4b17023SJohn Marino 					      / (1 - cyclic_probability) */
2054e4b17023SJohn Marino 
2055e4b17023SJohn Marino 	      sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
2056e4b17023SJohn Marino 	      sreal_div (&BLOCK_INFO (bb)->frequency,
2057e4b17023SJohn Marino 			 &frequency, &cyclic_probability);
2058e4b17023SJohn Marino 	    }
2059e4b17023SJohn Marino 	}
2060e4b17023SJohn Marino 
2061e4b17023SJohn Marino       bitmap_clear_bit (tovisit, bb->index);
2062e4b17023SJohn Marino 
2063e4b17023SJohn Marino       e = find_edge (bb, head);
2064e4b17023SJohn Marino       if (e)
2065e4b17023SJohn Marino 	{
2066e4b17023SJohn Marino 	  sreal tmp;
2067e4b17023SJohn Marino 
2068e4b17023SJohn Marino 	  /* EDGE_INFO (e)->back_edge_prob
2069e4b17023SJohn Marino 	     = ((e->probability * BLOCK_INFO (bb)->frequency)
2070e4b17023SJohn Marino 	     / REG_BR_PROB_BASE); */
2071e4b17023SJohn Marino 
2072e4b17023SJohn Marino 	  sreal_init (&tmp, e->probability, 0);
2073e4b17023SJohn Marino 	  sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
2074e4b17023SJohn Marino 	  sreal_mul (&EDGE_INFO (e)->back_edge_prob,
2075e4b17023SJohn Marino 		     &tmp, &real_inv_br_prob_base);
2076e4b17023SJohn Marino 	}
2077e4b17023SJohn Marino 
2078e4b17023SJohn Marino       /* Propagate to successor blocks.  */
2079e4b17023SJohn Marino       FOR_EACH_EDGE (e, ei, bb->succs)
2080e4b17023SJohn Marino 	if (!(e->flags & EDGE_DFS_BACK)
2081e4b17023SJohn Marino 	    && BLOCK_INFO (e->dest)->npredecessors)
2082e4b17023SJohn Marino 	  {
2083e4b17023SJohn Marino 	    BLOCK_INFO (e->dest)->npredecessors--;
2084e4b17023SJohn Marino 	    if (!BLOCK_INFO (e->dest)->npredecessors)
2085e4b17023SJohn Marino 	      {
2086e4b17023SJohn Marino 		if (!nextbb)
2087e4b17023SJohn Marino 		  nextbb = e->dest;
2088e4b17023SJohn Marino 		else
2089e4b17023SJohn Marino 		  BLOCK_INFO (last)->next = e->dest;
2090e4b17023SJohn Marino 
2091e4b17023SJohn Marino 		last = e->dest;
2092e4b17023SJohn Marino 	      }
2093e4b17023SJohn Marino 	  }
2094e4b17023SJohn Marino     }
2095e4b17023SJohn Marino }
2096e4b17023SJohn Marino 
2097e4b17023SJohn Marino /* Estimate probabilities of loopback edges in loops at same nest level.  */
2098e4b17023SJohn Marino 
2099e4b17023SJohn Marino static void
estimate_loops_at_level(struct loop * first_loop)2100e4b17023SJohn Marino estimate_loops_at_level (struct loop *first_loop)
2101e4b17023SJohn Marino {
2102e4b17023SJohn Marino   struct loop *loop;
2103e4b17023SJohn Marino 
2104e4b17023SJohn Marino   for (loop = first_loop; loop; loop = loop->next)
2105e4b17023SJohn Marino     {
2106e4b17023SJohn Marino       edge e;
2107e4b17023SJohn Marino       basic_block *bbs;
2108e4b17023SJohn Marino       unsigned i;
2109e4b17023SJohn Marino       bitmap tovisit = BITMAP_ALLOC (NULL);
2110e4b17023SJohn Marino 
2111e4b17023SJohn Marino       estimate_loops_at_level (loop->inner);
2112e4b17023SJohn Marino 
2113e4b17023SJohn Marino       /* Find current loop back edge and mark it.  */
2114e4b17023SJohn Marino       e = loop_latch_edge (loop);
2115e4b17023SJohn Marino       EDGE_INFO (e)->back_edge = 1;
2116e4b17023SJohn Marino 
2117e4b17023SJohn Marino       bbs = get_loop_body (loop);
2118e4b17023SJohn Marino       for (i = 0; i < loop->num_nodes; i++)
2119e4b17023SJohn Marino 	bitmap_set_bit (tovisit, bbs[i]->index);
2120e4b17023SJohn Marino       free (bbs);
2121e4b17023SJohn Marino       propagate_freq (loop->header, tovisit);
2122e4b17023SJohn Marino       BITMAP_FREE (tovisit);
2123e4b17023SJohn Marino     }
2124e4b17023SJohn Marino }
2125e4b17023SJohn Marino 
2126e4b17023SJohn Marino /* Propagates frequencies through structure of loops.  */
2127e4b17023SJohn Marino 
2128e4b17023SJohn Marino static void
estimate_loops(void)2129e4b17023SJohn Marino estimate_loops (void)
2130e4b17023SJohn Marino {
2131e4b17023SJohn Marino   bitmap tovisit = BITMAP_ALLOC (NULL);
2132e4b17023SJohn Marino   basic_block bb;
2133e4b17023SJohn Marino 
2134e4b17023SJohn Marino   /* Start by estimating the frequencies in the loops.  */
2135e4b17023SJohn Marino   if (number_of_loops () > 1)
2136e4b17023SJohn Marino     estimate_loops_at_level (current_loops->tree_root->inner);
2137e4b17023SJohn Marino 
2138e4b17023SJohn Marino   /* Now propagate the frequencies through all the blocks.  */
2139e4b17023SJohn Marino   FOR_ALL_BB (bb)
2140e4b17023SJohn Marino     {
2141e4b17023SJohn Marino       bitmap_set_bit (tovisit, bb->index);
2142e4b17023SJohn Marino     }
2143e4b17023SJohn Marino   propagate_freq (ENTRY_BLOCK_PTR, tovisit);
2144e4b17023SJohn Marino   BITMAP_FREE (tovisit);
2145e4b17023SJohn Marino }
2146e4b17023SJohn Marino 
2147e4b17023SJohn Marino /* Convert counts measured by profile driven feedback to frequencies.
2148e4b17023SJohn Marino    Return nonzero iff there was any nonzero execution count.  */
2149e4b17023SJohn Marino 
2150e4b17023SJohn Marino int
counts_to_freqs(void)2151e4b17023SJohn Marino counts_to_freqs (void)
2152e4b17023SJohn Marino {
2153e4b17023SJohn Marino   gcov_type count_max, true_count_max = 0;
2154e4b17023SJohn Marino   basic_block bb;
2155e4b17023SJohn Marino 
2156e4b17023SJohn Marino   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2157e4b17023SJohn Marino     true_count_max = MAX (bb->count, true_count_max);
2158e4b17023SJohn Marino 
2159e4b17023SJohn Marino   count_max = MAX (true_count_max, 1);
2160e4b17023SJohn Marino   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2161e4b17023SJohn Marino     bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
2162e4b17023SJohn Marino 
2163e4b17023SJohn Marino   return true_count_max;
2164e4b17023SJohn Marino }
2165e4b17023SJohn Marino 
2166e4b17023SJohn Marino /* Return true if function is likely to be expensive, so there is no point to
2167e4b17023SJohn Marino    optimize performance of prologue, epilogue or do inlining at the expense
2168e4b17023SJohn Marino    of code size growth.  THRESHOLD is the limit of number of instructions
2169e4b17023SJohn Marino    function can execute at average to be still considered not expensive.  */
2170e4b17023SJohn Marino 
2171e4b17023SJohn Marino bool
expensive_function_p(int threshold)2172e4b17023SJohn Marino expensive_function_p (int threshold)
2173e4b17023SJohn Marino {
2174e4b17023SJohn Marino   unsigned int sum = 0;
2175e4b17023SJohn Marino   basic_block bb;
2176e4b17023SJohn Marino   unsigned int limit;
2177e4b17023SJohn Marino 
2178e4b17023SJohn Marino   /* We can not compute accurately for large thresholds due to scaled
2179e4b17023SJohn Marino      frequencies.  */
2180e4b17023SJohn Marino   gcc_assert (threshold <= BB_FREQ_MAX);
2181e4b17023SJohn Marino 
2182e4b17023SJohn Marino   /* Frequencies are out of range.  This either means that function contains
2183e4b17023SJohn Marino      internal loop executing more than BB_FREQ_MAX times or profile feedback
2184e4b17023SJohn Marino      is available and function has not been executed at all.  */
2185e4b17023SJohn Marino   if (ENTRY_BLOCK_PTR->frequency == 0)
2186e4b17023SJohn Marino     return true;
2187e4b17023SJohn Marino 
2188e4b17023SJohn Marino   /* Maximally BB_FREQ_MAX^2 so overflow won't happen.  */
2189e4b17023SJohn Marino   limit = ENTRY_BLOCK_PTR->frequency * threshold;
2190e4b17023SJohn Marino   FOR_EACH_BB (bb)
2191e4b17023SJohn Marino     {
2192e4b17023SJohn Marino       rtx insn;
2193e4b17023SJohn Marino 
2194e4b17023SJohn Marino       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2195e4b17023SJohn Marino 	   insn = NEXT_INSN (insn))
2196e4b17023SJohn Marino 	if (active_insn_p (insn))
2197e4b17023SJohn Marino 	  {
2198e4b17023SJohn Marino 	    sum += bb->frequency;
2199e4b17023SJohn Marino 	    if (sum > limit)
2200e4b17023SJohn Marino 	      return true;
2201e4b17023SJohn Marino 	}
2202e4b17023SJohn Marino     }
2203e4b17023SJohn Marino 
2204e4b17023SJohn Marino   return false;
2205e4b17023SJohn Marino }
2206e4b17023SJohn Marino 
2207e4b17023SJohn Marino /* Estimate basic blocks frequency by given branch probabilities.  */
2208e4b17023SJohn Marino 
2209e4b17023SJohn Marino void
estimate_bb_frequencies(void)2210e4b17023SJohn Marino estimate_bb_frequencies (void)
2211e4b17023SJohn Marino {
2212e4b17023SJohn Marino   basic_block bb;
2213e4b17023SJohn Marino   sreal freq_max;
2214e4b17023SJohn Marino 
2215e4b17023SJohn Marino   if (profile_status != PROFILE_READ || !counts_to_freqs ())
2216e4b17023SJohn Marino     {
2217e4b17023SJohn Marino       static int real_values_initialized = 0;
2218e4b17023SJohn Marino 
2219e4b17023SJohn Marino       if (!real_values_initialized)
2220e4b17023SJohn Marino         {
2221e4b17023SJohn Marino 	  real_values_initialized = 1;
2222e4b17023SJohn Marino 	  sreal_init (&real_zero, 0, 0);
2223e4b17023SJohn Marino 	  sreal_init (&real_one, 1, 0);
2224e4b17023SJohn Marino 	  sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
2225e4b17023SJohn Marino 	  sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
2226e4b17023SJohn Marino 	  sreal_init (&real_one_half, 1, -1);
2227e4b17023SJohn Marino 	  sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
2228e4b17023SJohn Marino 	  sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
2229e4b17023SJohn Marino 	}
2230e4b17023SJohn Marino 
2231e4b17023SJohn Marino       mark_dfs_back_edges ();
2232e4b17023SJohn Marino 
2233e4b17023SJohn Marino       single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE;
2234e4b17023SJohn Marino 
2235e4b17023SJohn Marino       /* Set up block info for each basic block.  */
2236e4b17023SJohn Marino       alloc_aux_for_blocks (sizeof (struct block_info_def));
2237e4b17023SJohn Marino       alloc_aux_for_edges (sizeof (struct edge_info_def));
2238e4b17023SJohn Marino       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2239e4b17023SJohn Marino 	{
2240e4b17023SJohn Marino 	  edge e;
2241e4b17023SJohn Marino 	  edge_iterator ei;
2242e4b17023SJohn Marino 
2243e4b17023SJohn Marino 	  FOR_EACH_EDGE (e, ei, bb->succs)
2244e4b17023SJohn Marino 	    {
2245e4b17023SJohn Marino 	      sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
2246e4b17023SJohn Marino 	      sreal_mul (&EDGE_INFO (e)->back_edge_prob,
2247e4b17023SJohn Marino 			 &EDGE_INFO (e)->back_edge_prob,
2248e4b17023SJohn Marino 			 &real_inv_br_prob_base);
2249e4b17023SJohn Marino 	    }
2250e4b17023SJohn Marino 	}
2251e4b17023SJohn Marino 
2252e4b17023SJohn Marino       /* First compute probabilities locally for each loop from innermost
2253e4b17023SJohn Marino          to outermost to examine probabilities for back edges.  */
2254e4b17023SJohn Marino       estimate_loops ();
2255e4b17023SJohn Marino 
2256e4b17023SJohn Marino       memcpy (&freq_max, &real_zero, sizeof (real_zero));
2257e4b17023SJohn Marino       FOR_EACH_BB (bb)
2258e4b17023SJohn Marino 	if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
2259e4b17023SJohn Marino 	  memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
2260e4b17023SJohn Marino 
2261e4b17023SJohn Marino       sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
2262e4b17023SJohn Marino       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2263e4b17023SJohn Marino 	{
2264e4b17023SJohn Marino 	  sreal tmp;
2265e4b17023SJohn Marino 
2266e4b17023SJohn Marino 	  sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
2267e4b17023SJohn Marino 	  sreal_add (&tmp, &tmp, &real_one_half);
2268e4b17023SJohn Marino 	  bb->frequency = sreal_to_int (&tmp);
2269e4b17023SJohn Marino 	}
2270e4b17023SJohn Marino 
2271e4b17023SJohn Marino       free_aux_for_blocks ();
2272e4b17023SJohn Marino       free_aux_for_edges ();
2273e4b17023SJohn Marino     }
2274e4b17023SJohn Marino   compute_function_frequency ();
2275e4b17023SJohn Marino }
2276e4b17023SJohn Marino 
2277e4b17023SJohn Marino /* Decide whether function is hot, cold or unlikely executed.  */
2278e4b17023SJohn Marino void
compute_function_frequency(void)2279e4b17023SJohn Marino compute_function_frequency (void)
2280e4b17023SJohn Marino {
2281e4b17023SJohn Marino   basic_block bb;
2282e4b17023SJohn Marino   struct cgraph_node *node = cgraph_get_node (current_function_decl);
2283e4b17023SJohn Marino   if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2284e4b17023SJohn Marino       || MAIN_NAME_P (DECL_NAME (current_function_decl)))
2285e4b17023SJohn Marino     node->only_called_at_startup = true;
2286e4b17023SJohn Marino   if (DECL_STATIC_DESTRUCTOR (current_function_decl))
2287e4b17023SJohn Marino     node->only_called_at_exit = true;
2288e4b17023SJohn Marino 
2289e4b17023SJohn Marino   if (!profile_info || !flag_branch_probabilities)
2290e4b17023SJohn Marino     {
2291e4b17023SJohn Marino       int flags = flags_from_decl_or_type (current_function_decl);
2292e4b17023SJohn Marino       if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
2293e4b17023SJohn Marino 	  != NULL)
2294e4b17023SJohn Marino         node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2295e4b17023SJohn Marino       else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
2296e4b17023SJohn Marino 	       != NULL)
2297e4b17023SJohn Marino         node->frequency = NODE_FREQUENCY_HOT;
2298e4b17023SJohn Marino       else if (flags & ECF_NORETURN)
2299e4b17023SJohn Marino         node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2300e4b17023SJohn Marino       else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
2301e4b17023SJohn Marino         node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2302e4b17023SJohn Marino       else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2303e4b17023SJohn Marino 	       || DECL_STATIC_DESTRUCTOR (current_function_decl))
2304e4b17023SJohn Marino         node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2305e4b17023SJohn Marino       return;
2306e4b17023SJohn Marino     }
2307e4b17023SJohn Marino   node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2308e4b17023SJohn Marino   FOR_EACH_BB (bb)
2309e4b17023SJohn Marino     {
2310e4b17023SJohn Marino       if (maybe_hot_bb_p (bb))
2311e4b17023SJohn Marino 	{
2312e4b17023SJohn Marino 	  node->frequency = NODE_FREQUENCY_HOT;
2313e4b17023SJohn Marino 	  return;
2314e4b17023SJohn Marino 	}
2315e4b17023SJohn Marino       if (!probably_never_executed_bb_p (bb))
2316e4b17023SJohn Marino 	node->frequency = NODE_FREQUENCY_NORMAL;
2317e4b17023SJohn Marino     }
2318e4b17023SJohn Marino }
2319e4b17023SJohn Marino 
2320e4b17023SJohn Marino static bool
gate_estimate_probability(void)2321e4b17023SJohn Marino gate_estimate_probability (void)
2322e4b17023SJohn Marino {
2323e4b17023SJohn Marino   return flag_guess_branch_prob;
2324e4b17023SJohn Marino }
2325e4b17023SJohn Marino 
2326e4b17023SJohn Marino /* Build PREDICT_EXPR.  */
2327e4b17023SJohn Marino tree
build_predict_expr(enum br_predictor predictor,enum prediction taken)2328e4b17023SJohn Marino build_predict_expr (enum br_predictor predictor, enum prediction taken)
2329e4b17023SJohn Marino {
2330e4b17023SJohn Marino   tree t = build1 (PREDICT_EXPR, void_type_node,
2331e4b17023SJohn Marino 		   build_int_cst (integer_type_node, predictor));
2332e4b17023SJohn Marino   SET_PREDICT_EXPR_OUTCOME (t, taken);
2333e4b17023SJohn Marino   return t;
2334e4b17023SJohn Marino }
2335e4b17023SJohn Marino 
2336e4b17023SJohn Marino const char *
predictor_name(enum br_predictor predictor)2337e4b17023SJohn Marino predictor_name (enum br_predictor predictor)
2338e4b17023SJohn Marino {
2339e4b17023SJohn Marino   return predictor_info[predictor].name;
2340e4b17023SJohn Marino }
2341e4b17023SJohn Marino 
2342e4b17023SJohn Marino struct gimple_opt_pass pass_profile =
2343e4b17023SJohn Marino {
2344e4b17023SJohn Marino  {
2345e4b17023SJohn Marino   GIMPLE_PASS,
2346e4b17023SJohn Marino   "profile_estimate",			/* name */
2347e4b17023SJohn Marino   gate_estimate_probability,		/* gate */
2348e4b17023SJohn Marino   tree_estimate_probability_driver,	/* execute */
2349e4b17023SJohn Marino   NULL,					/* sub */
2350e4b17023SJohn Marino   NULL,					/* next */
2351e4b17023SJohn Marino   0,					/* static_pass_number */
2352e4b17023SJohn Marino   TV_BRANCH_PROB,			/* tv_id */
2353e4b17023SJohn Marino   PROP_cfg,				/* properties_required */
2354e4b17023SJohn Marino   0,					/* properties_provided */
2355e4b17023SJohn Marino   0,					/* properties_destroyed */
2356e4b17023SJohn Marino   0,					/* todo_flags_start */
2357e4b17023SJohn Marino   TODO_ggc_collect | TODO_verify_ssa			/* todo_flags_finish */
2358e4b17023SJohn Marino  }
2359e4b17023SJohn Marino };
2360e4b17023SJohn Marino 
2361e4b17023SJohn Marino struct gimple_opt_pass pass_strip_predict_hints =
2362e4b17023SJohn Marino {
2363e4b17023SJohn Marino  {
2364e4b17023SJohn Marino   GIMPLE_PASS,
2365e4b17023SJohn Marino   "*strip_predict_hints",		/* name */
2366e4b17023SJohn Marino   NULL,					/* gate */
2367e4b17023SJohn Marino   strip_predict_hints,			/* execute */
2368e4b17023SJohn Marino   NULL,					/* sub */
2369e4b17023SJohn Marino   NULL,					/* next */
2370e4b17023SJohn Marino   0,					/* static_pass_number */
2371e4b17023SJohn Marino   TV_BRANCH_PROB,			/* tv_id */
2372e4b17023SJohn Marino   PROP_cfg,				/* properties_required */
2373e4b17023SJohn Marino   0,					/* properties_provided */
2374e4b17023SJohn Marino   0,					/* properties_destroyed */
2375e4b17023SJohn Marino   0,					/* todo_flags_start */
2376e4b17023SJohn Marino   TODO_ggc_collect | TODO_verify_ssa			/* todo_flags_finish */
2377e4b17023SJohn Marino  }
2378e4b17023SJohn Marino };
2379e4b17023SJohn Marino 
2380e4b17023SJohn Marino /* Rebuild function frequencies.  Passes are in general expected to
2381e4b17023SJohn Marino    maintain profile by hand, however in some cases this is not possible:
2382e4b17023SJohn Marino    for example when inlining several functions with loops freuqencies might run
2383e4b17023SJohn Marino    out of scale and thus needs to be recomputed.  */
2384e4b17023SJohn Marino 
2385e4b17023SJohn Marino void
rebuild_frequencies(void)2386e4b17023SJohn Marino rebuild_frequencies (void)
2387e4b17023SJohn Marino {
2388e4b17023SJohn Marino   timevar_push (TV_REBUILD_FREQUENCIES);
2389e4b17023SJohn Marino   if (profile_status == PROFILE_GUESSED)
2390e4b17023SJohn Marino     {
2391e4b17023SJohn Marino       loop_optimizer_init (0);
2392e4b17023SJohn Marino       add_noreturn_fake_exit_edges ();
2393e4b17023SJohn Marino       mark_irreducible_loops ();
2394e4b17023SJohn Marino       connect_infinite_loops_to_exit ();
2395e4b17023SJohn Marino       estimate_bb_frequencies ();
2396e4b17023SJohn Marino       remove_fake_exit_edges ();
2397e4b17023SJohn Marino       loop_optimizer_finalize ();
2398e4b17023SJohn Marino     }
2399e4b17023SJohn Marino   else if (profile_status == PROFILE_READ)
2400e4b17023SJohn Marino     counts_to_freqs ();
2401e4b17023SJohn Marino   else
2402e4b17023SJohn Marino     gcc_unreachable ();
2403e4b17023SJohn Marino   timevar_pop (TV_REBUILD_FREQUENCIES);
2404e4b17023SJohn Marino }
2405