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