Mercurial > hg > CbC > CbC_gcc
annotate gcc/predict.c @ 88:f214c1d5b862
merge 89
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 20 Dec 2011 18:53:46 +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 } |