predict.c revision 96263
1/* Branch prediction routines for the GNU compiler. 2 Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 2, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 59 Temple Place - Suite 330, Boston, MA 1902111-1307, USA. */ 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 "tree.h" 34#include "rtl.h" 35#include "tm_p.h" 36#include "hard-reg-set.h" 37#include "basic-block.h" 38#include "insn-config.h" 39#include "regs.h" 40#include "flags.h" 41#include "output.h" 42#include "function.h" 43#include "except.h" 44#include "toplev.h" 45#include "recog.h" 46#include "expr.h" 47#include "predict.h" 48 49/* Random guesstimation given names. */ 50#define PROB_NEVER (0) 51#define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1) 52#define PROB_UNLIKELY (REG_BR_PROB_BASE * 4 / 10 - 1) 53#define PROB_EVEN (REG_BR_PROB_BASE / 2) 54#define PROB_LIKELY (REG_BR_PROB_BASE - PROB_UNLIKELY) 55#define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY) 56#define PROB_ALWAYS (REG_BR_PROB_BASE) 57 58static void combine_predictions_for_insn PARAMS ((rtx, basic_block)); 59static void dump_prediction PARAMS ((enum br_predictor, int, 60 basic_block, int)); 61static void estimate_loops_at_level PARAMS ((struct loop *loop)); 62static void propagate_freq PARAMS ((basic_block)); 63static void estimate_bb_frequencies PARAMS ((struct loops *)); 64static void counts_to_freqs PARAMS ((void)); 65 66/* Information we hold about each branch predictor. 67 Filled using information from predict.def. */ 68 69struct predictor_info 70{ 71 const char *const name; /* Name used in the debugging dumps. */ 72 const int hitrate; /* Expected hitrate used by 73 predict_insn_def call. */ 74 const int flags; 75}; 76 77/* Use given predictor without Dempster-Shaffer theory if it matches 78 using first_match heuristics. */ 79#define PRED_FLAG_FIRST_MATCH 1 80 81/* Recompute hitrate in percent to our representation. */ 82 83#define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100) 84 85#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS}, 86static const struct predictor_info predictor_info[]= { 87#include "predict.def" 88 89 /* Upper bound on predictors. */ 90 {NULL, 0, 0} 91}; 92#undef DEF_PREDICTOR 93 94void 95predict_insn (insn, predictor, probability) 96 rtx insn; 97 int probability; 98 enum br_predictor predictor; 99{ 100 if (!any_condjump_p (insn)) 101 abort (); 102 103 REG_NOTES (insn) 104 = gen_rtx_EXPR_LIST (REG_BR_PRED, 105 gen_rtx_CONCAT (VOIDmode, 106 GEN_INT ((int) predictor), 107 GEN_INT ((int) probability)), 108 REG_NOTES (insn)); 109} 110 111/* Predict insn by given predictor. */ 112 113void 114predict_insn_def (insn, predictor, taken) 115 rtx insn; 116 enum br_predictor predictor; 117 enum prediction taken; 118{ 119 int probability = predictor_info[(int) predictor].hitrate; 120 121 if (taken != TAKEN) 122 probability = REG_BR_PROB_BASE - probability; 123 124 predict_insn (insn, predictor, probability); 125} 126 127/* Predict edge E with given probability if possible. */ 128 129void 130predict_edge (e, predictor, probability) 131 edge e; 132 int probability; 133 enum br_predictor predictor; 134{ 135 rtx last_insn; 136 last_insn = e->src->end; 137 138 /* We can store the branch prediction information only about 139 conditional jumps. */ 140 if (!any_condjump_p (last_insn)) 141 return; 142 143 /* We always store probability of branching. */ 144 if (e->flags & EDGE_FALLTHRU) 145 probability = REG_BR_PROB_BASE - probability; 146 147 predict_insn (last_insn, predictor, probability); 148} 149 150/* Predict edge E by given predictor if possible. */ 151 152void 153predict_edge_def (e, predictor, taken) 154 edge e; 155 enum br_predictor predictor; 156 enum prediction taken; 157{ 158 int probability = predictor_info[(int) predictor].hitrate; 159 160 if (taken != TAKEN) 161 probability = REG_BR_PROB_BASE - probability; 162 163 predict_edge (e, predictor, probability); 164} 165 166/* Invert all branch predictions or probability notes in the INSN. This needs 167 to be done each time we invert the condition used by the jump. */ 168 169void 170invert_br_probabilities (insn) 171 rtx insn; 172{ 173 rtx note; 174 175 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 176 if (REG_NOTE_KIND (note) == REG_BR_PROB) 177 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0))); 178 else if (REG_NOTE_KIND (note) == REG_BR_PRED) 179 XEXP (XEXP (note, 0), 1) 180 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1))); 181} 182 183/* Dump information about the branch prediction to the output file. */ 184 185static void 186dump_prediction (predictor, probability, bb, used) 187 enum br_predictor predictor; 188 int probability; 189 basic_block bb; 190 int used; 191{ 192 edge e = bb->succ; 193 194 if (!rtl_dump_file) 195 return; 196 197 while (e->flags & EDGE_FALLTHRU) 198 e = e->succ_next; 199 200 fprintf (rtl_dump_file, " %s heuristics%s: %.1f%%", 201 predictor_info[predictor].name, 202 used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE); 203 204 if (bb->count) 205 { 206 fprintf (rtl_dump_file, " exec "); 207 fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, bb->count); 208 fprintf (rtl_dump_file, " hit "); 209 fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, e->count); 210 fprintf (rtl_dump_file, " (%.1f%%)", e->count * 100.0 / bb->count); 211 } 212 213 fprintf (rtl_dump_file, "\n"); 214} 215 216/* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB 217 note if not already present. Remove now useless REG_BR_PRED notes. */ 218 219static void 220combine_predictions_for_insn (insn, bb) 221 rtx insn; 222 basic_block bb; 223{ 224 rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0); 225 rtx *pnote = ®_NOTES (insn); 226 rtx note; 227 int best_probability = PROB_EVEN; 228 int best_predictor = END_PREDICTORS; 229 int combined_probability = REG_BR_PROB_BASE / 2; 230 int d; 231 bool first_match = false; 232 bool found = false; 233 234 if (rtl_dump_file) 235 fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn), 236 bb->index); 237 238 /* We implement "first match" heuristics and use probability guessed 239 by predictor with smallest index. In the future we will use better 240 probability combination techniques. */ 241 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 242 if (REG_NOTE_KIND (note) == REG_BR_PRED) 243 { 244 int predictor = INTVAL (XEXP (XEXP (note, 0), 0)); 245 int probability = INTVAL (XEXP (XEXP (note, 0), 1)); 246 247 found = true; 248 if (best_predictor > predictor) 249 best_probability = probability, best_predictor = predictor; 250 251 d = (combined_probability * probability 252 + (REG_BR_PROB_BASE - combined_probability) 253 * (REG_BR_PROB_BASE - probability)); 254 255 /* Use FP math to avoid overflows of 32bit integers. */ 256 if (d == 0) 257 /* If one probability is 0% and one 100%, avoid division by zero. */ 258 combined_probability = REG_BR_PROB_BASE / 2; 259 else 260 combined_probability = (((double) combined_probability) * probability 261 * REG_BR_PROB_BASE / d + 0.5); 262 } 263 264 /* Decide which heuristic to use. In case we didn't match anything, 265 use no_prediction heuristic, in case we did match, use either 266 first match or Dempster-Shaffer theory depending on the flags. */ 267 268 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH) 269 first_match = true; 270 271 if (!found) 272 dump_prediction (PRED_NO_PREDICTION, combined_probability, bb, true); 273 else 274 { 275 dump_prediction (PRED_DS_THEORY, combined_probability, bb, !first_match); 276 dump_prediction (PRED_FIRST_MATCH, best_probability, bb, first_match); 277 } 278 279 if (first_match) 280 combined_probability = best_probability; 281 dump_prediction (PRED_COMBINED, combined_probability, bb, true); 282 283 while (*pnote) 284 { 285 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED) 286 { 287 int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0)); 288 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1)); 289 290 dump_prediction (predictor, probability, bb, 291 !first_match || best_predictor == predictor); 292 *pnote = XEXP (*pnote, 1); 293 } 294 else 295 pnote = &XEXP (*pnote, 1); 296 } 297 298 if (!prob_note) 299 { 300 REG_NOTES (insn) 301 = gen_rtx_EXPR_LIST (REG_BR_PROB, 302 GEN_INT (combined_probability), REG_NOTES (insn)); 303 304 /* Save the prediction into CFG in case we are seeing non-degenerated 305 conditional jump. */ 306 if (bb->succ->succ_next) 307 { 308 BRANCH_EDGE (bb)->probability = combined_probability; 309 FALLTHRU_EDGE (bb)->probability 310 = REG_BR_PROB_BASE - combined_probability; 311 } 312 } 313} 314 315/* Statically estimate the probability that a branch will be taken. 316 ??? In the next revision there will be a number of other predictors added 317 from the above references. Further, each heuristic will be factored out 318 into its own function for clarity (and to facilitate the combination of 319 predictions). */ 320 321void 322estimate_probability (loops_info) 323 struct loops *loops_info; 324{ 325 sbitmap *dominators, *post_dominators; 326 int i; 327 int found_noreturn = 0; 328 329 dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); 330 post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); 331 calculate_dominance_info (NULL, dominators, CDI_DOMINATORS); 332 calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS); 333 334 /* Try to predict out blocks in a loop that are not part of a 335 natural loop. */ 336 for (i = 0; i < loops_info->num; i++) 337 { 338 int j; 339 int exits; 340 struct loop *loop = &loops_info->array[i]; 341 342 flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES); 343 exits = loop->num_exits; 344 345 for (j = loop->first->index; j <= loop->last->index; ++j) 346 if (TEST_BIT (loop->nodes, j)) 347 { 348 int header_found = 0; 349 edge e; 350 351 /* Loop branch heuristics - predict an edge back to a 352 loop's head as taken. */ 353 for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next) 354 if (e->dest == loop->header 355 && e->src == loop->latch) 356 { 357 header_found = 1; 358 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN); 359 } 360 361 /* Loop exit heuristics - predict an edge exiting the loop if the 362 conditinal has no loop header successors as not taken. */ 363 if (!header_found) 364 for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next) 365 if (e->dest->index < 0 366 || !TEST_BIT (loop->nodes, e->dest->index)) 367 predict_edge 368 (e, PRED_LOOP_EXIT, 369 (REG_BR_PROB_BASE 370 - predictor_info [(int) PRED_LOOP_EXIT].hitrate) 371 / exits); 372 } 373 } 374 375 /* Attempt to predict conditional jumps using a number of heuristics. */ 376 for (i = 0; i < n_basic_blocks; i++) 377 { 378 basic_block bb = BASIC_BLOCK (i); 379 rtx last_insn = bb->end; 380 rtx cond, earliest; 381 edge e; 382 383 /* If block has no successor, predict all possible paths to it as 384 improbable, as the block contains a call to a noreturn function and 385 thus can be executed only once. */ 386 if (bb->succ == NULL && !found_noreturn) 387 { 388 int y; 389 390 /* ??? Postdominator claims each noreturn block to be postdominated 391 by each, so we need to run only once. This needs to be changed 392 once postdominace algorithm is updated to say something more 393 sane. */ 394 found_noreturn = 1; 395 for (y = 0; y < n_basic_blocks; y++) 396 if (!TEST_BIT (post_dominators[y], i)) 397 for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next) 398 if (e->dest->index >= 0 399 && TEST_BIT (post_dominators[e->dest->index], i)) 400 predict_edge_def (e, PRED_NORETURN, NOT_TAKEN); 401 } 402 403 if (GET_CODE (last_insn) != JUMP_INSN || ! any_condjump_p (last_insn)) 404 continue; 405 406 for (e = bb->succ; e; e = e->succ_next) 407 { 408 /* Predict edges to blocks that return immediately to be 409 improbable. These are usually used to signal error states. */ 410 if (e->dest == EXIT_BLOCK_PTR 411 || (e->dest->succ && !e->dest->succ->succ_next 412 && e->dest->succ->dest == EXIT_BLOCK_PTR)) 413 predict_edge_def (e, PRED_ERROR_RETURN, NOT_TAKEN); 414 415 /* Look for block we are guarding (ie we dominate it, 416 but it doesn't postdominate us). */ 417 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb 418 && TEST_BIT (dominators[e->dest->index], e->src->index) 419 && !TEST_BIT (post_dominators[e->src->index], e->dest->index)) 420 { 421 rtx insn; 422 423 /* The call heuristic claims that a guarded function call 424 is improbable. This is because such calls are often used 425 to signal exceptional situations such as printing error 426 messages. */ 427 for (insn = e->dest->head; insn != NEXT_INSN (e->dest->end); 428 insn = NEXT_INSN (insn)) 429 if (GET_CODE (insn) == CALL_INSN 430 /* Constant and pure calls are hardly used to signalize 431 something exceptional. */ 432 && ! CONST_OR_PURE_CALL_P (insn)) 433 { 434 predict_edge_def (e, PRED_CALL, NOT_TAKEN); 435 break; 436 } 437 } 438 } 439 440 cond = get_condition (last_insn, &earliest); 441 if (! cond) 442 continue; 443 444 /* Try "pointer heuristic." 445 A comparison ptr == 0 is predicted as false. 446 Similarly, a comparison ptr1 == ptr2 is predicted as false. */ 447 if (GET_RTX_CLASS (GET_CODE (cond)) == '<' 448 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0))) 449 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1))))) 450 { 451 if (GET_CODE (cond) == EQ) 452 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN); 453 else if (GET_CODE (cond) == NE) 454 predict_insn_def (last_insn, PRED_POINTER, TAKEN); 455 } 456 else 457 458 /* Try "opcode heuristic." 459 EQ tests are usually false and NE tests are usually true. Also, 460 most quantities are positive, so we can make the appropriate guesses 461 about signed comparisons against zero. */ 462 switch (GET_CODE (cond)) 463 { 464 case CONST_INT: 465 /* Unconditional branch. */ 466 predict_insn_def (last_insn, PRED_UNCONDITIONAL, 467 cond == const0_rtx ? NOT_TAKEN : TAKEN); 468 break; 469 470 case EQ: 471 case UNEQ: 472 /* Floating point comparisons appears to behave in a very 473 inpredictable way because of special role of = tests in 474 FP code. */ 475 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) 476 ; 477 /* Comparisons with 0 are often used for booleans and there is 478 nothing usefull to predict about them. */ 479 else if (XEXP (cond, 1) == const0_rtx 480 || XEXP (cond, 0) == const0_rtx) 481 ; 482 else 483 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN); 484 break; 485 486 case NE: 487 case LTGT: 488 /* Floating point comparisons appears to behave in a very 489 inpredictable way because of special role of = tests in 490 FP code. */ 491 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) 492 ; 493 /* Comparisons with 0 are often used for booleans and there is 494 nothing usefull to predict about them. */ 495 else if (XEXP (cond, 1) == const0_rtx 496 || XEXP (cond, 0) == const0_rtx) 497 ; 498 else 499 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN); 500 break; 501 502 case ORDERED: 503 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN); 504 break; 505 506 case UNORDERED: 507 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN); 508 break; 509 510 case LE: 511 case LT: 512 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx 513 || XEXP (cond, 1) == constm1_rtx) 514 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN); 515 break; 516 517 case GE: 518 case GT: 519 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx 520 || XEXP (cond, 1) == constm1_rtx) 521 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN); 522 break; 523 524 default: 525 break; 526 } 527 } 528 529 /* Attach the combined probability to each conditional jump. */ 530 for (i = 0; i < n_basic_blocks; i++) 531 if (GET_CODE (BLOCK_END (i)) == JUMP_INSN 532 && any_condjump_p (BLOCK_END (i))) 533 combine_predictions_for_insn (BLOCK_END (i), BASIC_BLOCK (i)); 534 535 sbitmap_vector_free (post_dominators); 536 sbitmap_vector_free (dominators); 537 538 estimate_bb_frequencies (loops_info); 539} 540 541/* __builtin_expect dropped tokens into the insn stream describing expected 542 values of registers. Generate branch probabilities based off these 543 values. */ 544 545void 546expected_value_to_br_prob () 547{ 548 rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX; 549 550 for (insn = get_insns (); insn ; insn = NEXT_INSN (insn)) 551 { 552 switch (GET_CODE (insn)) 553 { 554 case NOTE: 555 /* Look for expected value notes. */ 556 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE) 557 { 558 ev = NOTE_EXPECTED_VALUE (insn); 559 ev_reg = XEXP (ev, 0); 560 delete_insn (insn); 561 } 562 continue; 563 564 case CODE_LABEL: 565 /* Never propagate across labels. */ 566 ev = NULL_RTX; 567 continue; 568 569 case JUMP_INSN: 570 /* Look for simple conditional branches. If we haven't got an 571 expected value yet, no point going further. */ 572 if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX 573 || ! any_condjump_p (insn)) 574 continue; 575 break; 576 577 default: 578 /* Look for insns that clobber the EV register. */ 579 if (ev && reg_set_p (ev_reg, insn)) 580 ev = NULL_RTX; 581 continue; 582 } 583 584 /* Collect the branch condition, hopefully relative to EV_REG. */ 585 /* ??? At present we'll miss things like 586 (expected_value (eq r70 0)) 587 (set r71 -1) 588 (set r80 (lt r70 r71)) 589 (set pc (if_then_else (ne r80 0) ...)) 590 as canonicalize_condition will render this to us as 591 (lt r70, r71) 592 Could use cselib to try and reduce this further. */ 593 cond = XEXP (SET_SRC (pc_set (insn)), 0); 594 cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg); 595 if (! cond || XEXP (cond, 0) != ev_reg 596 || GET_CODE (XEXP (cond, 1)) != CONST_INT) 597 continue; 598 599 /* Substitute and simplify. Given that the expression we're 600 building involves two constants, we should wind up with either 601 true or false. */ 602 cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode, 603 XEXP (ev, 1), XEXP (cond, 1)); 604 cond = simplify_rtx (cond); 605 606 /* Turn the condition into a scaled branch probability. */ 607 if (cond != const_true_rtx && cond != const0_rtx) 608 abort (); 609 predict_insn_def (insn, PRED_BUILTIN_EXPECT, 610 cond == const_true_rtx ? TAKEN : NOT_TAKEN); 611 } 612} 613 614/* This is used to carry information about basic blocks. It is 615 attached to the AUX field of the standard CFG block. */ 616 617typedef struct block_info_def 618{ 619 /* Estimated frequency of execution of basic_block. */ 620 volatile double frequency; 621 622 /* To keep queue of basic blocks to process. */ 623 basic_block next; 624 625 /* True if block needs to be visited in prop_freqency. */ 626 int tovisit:1; 627 628 /* Number of predecessors we need to visit first. */ 629 int npredecessors; 630} *block_info; 631 632/* Similar information for edges. */ 633typedef struct edge_info_def 634{ 635 /* In case edge is an loopback edge, the probability edge will be reached 636 in case header is. Estimated number of iterations of the loop can be 637 then computed as 1 / (1 - back_edge_prob). 638 639 Volatile is needed to avoid differences in the optimized and unoptimized 640 builds on machines where FP registers are wider than double. */ 641 volatile double back_edge_prob; 642 /* True if the edge is an loopback edge in the natural loop. */ 643 int back_edge:1; 644} *edge_info; 645 646#define BLOCK_INFO(B) ((block_info) (B)->aux) 647#define EDGE_INFO(E) ((edge_info) (E)->aux) 648 649/* Helper function for estimate_bb_frequencies. 650 Propagate the frequencies for loops headed by HEAD. */ 651 652static void 653propagate_freq (head) 654 basic_block head; 655{ 656 basic_block bb = head; 657 basic_block last = bb; 658 edge e; 659 basic_block nextbb; 660 int n; 661 662 /* For each basic block we need to visit count number of his predecessors 663 we need to visit first. */ 664 for (n = 0; n < n_basic_blocks; n++) 665 { 666 basic_block bb = BASIC_BLOCK (n); 667 if (BLOCK_INFO (bb)->tovisit) 668 { 669 int count = 0; 670 671 for (e = bb->pred; e; e = e->pred_next) 672 if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK)) 673 count++; 674 else if (BLOCK_INFO (e->src)->tovisit 675 && rtl_dump_file && !EDGE_INFO (e)->back_edge) 676 fprintf (rtl_dump_file, 677 "Irreducible region hit, ignoring edge to %i->%i\n", 678 e->src->index, bb->index); 679 BLOCK_INFO (bb)->npredecessors = count; 680 } 681 } 682 683 BLOCK_INFO (head)->frequency = 1; 684 for (; bb; bb = nextbb) 685 { 686 double cyclic_probability = 0, frequency = 0; 687 688 nextbb = BLOCK_INFO (bb)->next; 689 BLOCK_INFO (bb)->next = NULL; 690 691 /* Compute frequency of basic block. */ 692 if (bb != head) 693 { 694#ifdef ENABLE_CHECKING 695 for (e = bb->pred; e; e = e->pred_next) 696 if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK)) 697 abort (); 698#endif 699 700 for (e = bb->pred; e; e = e->pred_next) 701 if (EDGE_INFO (e)->back_edge) 702 cyclic_probability += EDGE_INFO (e)->back_edge_prob; 703 else if (!(e->flags & EDGE_DFS_BACK)) 704 frequency += (e->probability 705 * BLOCK_INFO (e->src)->frequency / 706 REG_BR_PROB_BASE); 707 708 if (cyclic_probability > 1.0 - 1.0 / REG_BR_PROB_BASE) 709 cyclic_probability = 1.0 - 1.0 / REG_BR_PROB_BASE; 710 711 BLOCK_INFO (bb)->frequency = frequency / (1 - cyclic_probability); 712 } 713 714 BLOCK_INFO (bb)->tovisit = 0; 715 716 /* Compute back edge frequencies. */ 717 for (e = bb->succ; e; e = e->succ_next) 718 if (e->dest == head) 719 EDGE_INFO (e)->back_edge_prob 720 = ((e->probability * BLOCK_INFO (bb)->frequency) 721 / REG_BR_PROB_BASE); 722 723 /* Propagate to successor blocks. */ 724 for (e = bb->succ; e; e = e->succ_next) 725 if (!(e->flags & EDGE_DFS_BACK) 726 && BLOCK_INFO (e->dest)->npredecessors) 727 { 728 BLOCK_INFO (e->dest)->npredecessors--; 729 if (!BLOCK_INFO (e->dest)->npredecessors) 730 { 731 if (!nextbb) 732 nextbb = e->dest; 733 else 734 BLOCK_INFO (last)->next = e->dest; 735 736 last = e->dest; 737 } 738 } 739 } 740} 741 742/* Estimate probabilities of loopback edges in loops at same nest level. */ 743 744static void 745estimate_loops_at_level (first_loop) 746 struct loop *first_loop; 747{ 748 struct loop *l, *loop = first_loop; 749 750 for (loop = first_loop; loop; loop = loop->next) 751 { 752 int n; 753 edge e; 754 755 estimate_loops_at_level (loop->inner); 756 757 /* Find current loop back edge and mark it. */ 758 for (e = loop->latch->succ; e->dest != loop->header; e = e->succ_next) 759 ; 760 761 EDGE_INFO (e)->back_edge = 1; 762 763 /* In case the loop header is shared, ensure that it is the last 764 one sharing the same header, so we avoid redundant work. */ 765 if (loop->shared) 766 { 767 for (l = loop->next; l; l = l->next) 768 if (l->header == loop->header) 769 break; 770 771 if (l) 772 continue; 773 } 774 775 /* Now merge all nodes of all loops with given header as not visited. */ 776 for (l = loop->shared ? first_loop : loop; l != loop->next; l = l->next) 777 if (loop->header == l->header) 778 EXECUTE_IF_SET_IN_SBITMAP (l->nodes, 0, n, 779 BLOCK_INFO (BASIC_BLOCK (n))->tovisit = 1 780 ); 781 782 propagate_freq (loop->header); 783 } 784} 785 786/* Convert counts measured by profile driven feedback to frequencies. */ 787 788static void 789counts_to_freqs () 790{ 791 HOST_WIDEST_INT count_max = 1; 792 int i; 793 794 for (i = 0; i < n_basic_blocks; i++) 795 count_max = MAX (BASIC_BLOCK (i)->count, count_max); 796 797 for (i = -2; i < n_basic_blocks; i++) 798 { 799 basic_block bb; 800 801 if (i == -2) 802 bb = ENTRY_BLOCK_PTR; 803 else if (i == -1) 804 bb = EXIT_BLOCK_PTR; 805 else 806 bb = BASIC_BLOCK (i); 807 808 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max; 809 } 810} 811 812/* Return true if function is likely to be expensive, so there is no point to 813 optimize performance of prologue, epilogue or do inlining at the expense 814 of code size growth. THRESHOLD is the limit of number of isntructions 815 function can execute at average to be still considered not expensive. */ 816 817bool 818expensive_function_p (threshold) 819 int threshold; 820{ 821 unsigned int sum = 0; 822 int i; 823 unsigned int limit; 824 825 /* We can not compute accurately for large thresholds due to scaled 826 frequencies. */ 827 if (threshold > BB_FREQ_MAX) 828 abort (); 829 830 /* Frequencies are out of range. This either means that function contains 831 internal loop executing more than BB_FREQ_MAX times or profile feedback 832 is available and function has not been executed at all. */ 833 if (ENTRY_BLOCK_PTR->frequency == 0) 834 return true; 835 836 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */ 837 limit = ENTRY_BLOCK_PTR->frequency * threshold; 838 for (i = 0; i < n_basic_blocks; i++) 839 { 840 basic_block bb = BASIC_BLOCK (i); 841 rtx insn; 842 843 for (insn = bb->head; insn != NEXT_INSN (bb->end); 844 insn = NEXT_INSN (insn)) 845 if (active_insn_p (insn)) 846 { 847 sum += bb->frequency; 848 if (sum > limit) 849 return true; 850 } 851 } 852 853 return false; 854} 855 856/* Estimate basic blocks frequency by given branch probabilities. */ 857 858static void 859estimate_bb_frequencies (loops) 860 struct loops *loops; 861{ 862 int i; 863 double freq_max = 0; 864 865 mark_dfs_back_edges (); 866 if (flag_branch_probabilities) 867 { 868 counts_to_freqs (); 869 return; 870 } 871 872 /* Fill in the probability values in flowgraph based on the REG_BR_PROB 873 notes. */ 874 for (i = 0; i < n_basic_blocks; i++) 875 { 876 rtx last_insn = BLOCK_END (i); 877 int probability; 878 edge fallthru, branch; 879 880 if (GET_CODE (last_insn) != JUMP_INSN || !any_condjump_p (last_insn) 881 /* Avoid handling of conditional jumps jumping to fallthru edge. */ 882 || BASIC_BLOCK (i)->succ->succ_next == NULL) 883 { 884 /* We can predict only conditional jumps at the moment. 885 Expect each edge to be equally probable. 886 ?? In the future we want to make abnormal edges improbable. */ 887 int nedges = 0; 888 edge e; 889 890 for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next) 891 { 892 nedges++; 893 if (e->probability != 0) 894 break; 895 } 896 if (!e) 897 for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next) 898 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges; 899 } 900 else 901 { 902 probability = INTVAL (XEXP (find_reg_note (last_insn, 903 REG_BR_PROB, 0), 0)); 904 fallthru = BASIC_BLOCK (i)->succ; 905 if (!fallthru->flags & EDGE_FALLTHRU) 906 fallthru = fallthru->succ_next; 907 branch = BASIC_BLOCK (i)->succ; 908 if (branch->flags & EDGE_FALLTHRU) 909 branch = branch->succ_next; 910 911 branch->probability = probability; 912 fallthru->probability = REG_BR_PROB_BASE - probability; 913 } 914 } 915 916 ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE; 917 918 /* Set up block info for each basic block. */ 919 alloc_aux_for_blocks (sizeof (struct block_info_def)); 920 alloc_aux_for_edges (sizeof (struct edge_info_def)); 921 for (i = -2; i < n_basic_blocks; i++) 922 { 923 edge e; 924 basic_block bb; 925 926 if (i == -2) 927 bb = ENTRY_BLOCK_PTR; 928 else if (i == -1) 929 bb = EXIT_BLOCK_PTR; 930 else 931 bb = BASIC_BLOCK (i); 932 933 BLOCK_INFO (bb)->tovisit = 0; 934 for (e = bb->succ; e; e = e->succ_next) 935 EDGE_INFO (e)->back_edge_prob = ((double) e->probability 936 / REG_BR_PROB_BASE); 937 } 938 939 /* First compute probabilities locally for each loop from innermost 940 to outermost to examine probabilities for back edges. */ 941 estimate_loops_at_level (loops->tree_root); 942 943 /* Now fake loop around whole function to finalize probabilities. */ 944 for (i = 0; i < n_basic_blocks; i++) 945 BLOCK_INFO (BASIC_BLOCK (i))->tovisit = 1; 946 947 BLOCK_INFO (ENTRY_BLOCK_PTR)->tovisit = 1; 948 BLOCK_INFO (EXIT_BLOCK_PTR)->tovisit = 1; 949 propagate_freq (ENTRY_BLOCK_PTR); 950 951 for (i = 0; i < n_basic_blocks; i++) 952 if (BLOCK_INFO (BASIC_BLOCK (i))->frequency > freq_max) 953 freq_max = BLOCK_INFO (BASIC_BLOCK (i))->frequency; 954 955 for (i = -2; i < n_basic_blocks; i++) 956 { 957 basic_block bb; 958 volatile double tmp; 959 960 if (i == -2) 961 bb = ENTRY_BLOCK_PTR; 962 else if (i == -1) 963 bb = EXIT_BLOCK_PTR; 964 else 965 bb = BASIC_BLOCK (i); 966 967 /* ??? Prevent rounding differences due to optimization on x86. */ 968 tmp = BLOCK_INFO (bb)->frequency * BB_FREQ_MAX; 969 tmp /= freq_max; 970 tmp += 0.5; 971 bb->frequency = tmp; 972 } 973 974 free_aux_for_blocks (); 975 free_aux_for_edges (); 976} 977