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 = ®_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