predict.c revision 146895
1/* Branch prediction routines for the GNU compiler. 2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005 3 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 59 Temple Place - Suite 330, Boston, MA 2002111-1307, USA. */ 21 22/* References: 23 24 [1] "Branch Prediction for Free" 25 Ball and Larus; PLDI '93. 26 [2] "Static Branch Frequency and Program Profile Analysis" 27 Wu and Larus; MICRO-27. 28 [3] "Corpus-based Static Branch Prediction" 29 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */ 30 31 32#include "config.h" 33#include "system.h" 34#include "coretypes.h" 35#include "tm.h" 36#include "tree.h" 37#include "rtl.h" 38#include "tm_p.h" 39#include "hard-reg-set.h" 40#include "basic-block.h" 41#include "insn-config.h" 42#include "regs.h" 43#include "flags.h" 44#include "output.h" 45#include "function.h" 46#include "except.h" 47#include "toplev.h" 48#include "recog.h" 49#include "expr.h" 50#include "predict.h" 51#include "coverage.h" 52#include "sreal.h" 53#include "params.h" 54#include "target.h" 55#include "loop.h" 56#include "cfgloop.h" 57 58/* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE, 59 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */ 60static sreal real_zero, real_one, real_almost_one, real_br_prob_base, 61 real_inv_br_prob_base, real_one_half, real_bb_freq_max; 62 63/* Random guesstimation given names. */ 64#define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 100 - 1) 65#define PROB_EVEN (REG_BR_PROB_BASE / 2) 66#define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY) 67#define PROB_ALWAYS (REG_BR_PROB_BASE) 68 69static bool predicted_by_p (basic_block, enum br_predictor); 70static void combine_predictions_for_insn (rtx, basic_block); 71static void dump_prediction (enum br_predictor, int, basic_block, int); 72static void estimate_loops_at_level (struct loop *loop); 73static void propagate_freq (struct loop *); 74static void estimate_bb_frequencies (struct loops *); 75static void counts_to_freqs (void); 76static void process_note_predictions (basic_block, int *); 77static void process_note_prediction (basic_block, int *, int, int); 78static bool last_basic_block_p (basic_block); 79static void compute_function_frequency (void); 80static void choose_function_section (void); 81static bool can_predict_insn_p (rtx); 82 83/* Information we hold about each branch predictor. 84 Filled using information from predict.def. */ 85 86struct 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}, 103static 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 in case BB can be CPU intensive and should be optimized 112 for maximal performance. */ 113 114bool 115maybe_hot_bb_p (basic_block bb) 116{ 117 if (profile_info && flag_branch_probabilities 118 && (bb->count 119 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION))) 120 return false; 121 if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)) 122 return false; 123 return true; 124} 125 126/* Return true in case BB is cold and should be optimized for size. */ 127 128bool 129probably_cold_bb_p (basic_block bb) 130{ 131 if (profile_info && flag_branch_probabilities 132 && (bb->count 133 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION))) 134 return true; 135 if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)) 136 return true; 137 return false; 138} 139 140/* Return true in case BB is probably never executed. */ 141bool 142probably_never_executed_bb_p (basic_block bb) 143{ 144 if (profile_info && flag_branch_probabilities) 145 return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0; 146 return false; 147} 148 149/* Return true if the one of outgoing edges is already predicted by 150 PREDICTOR. */ 151 152static bool 153predicted_by_p (basic_block bb, enum br_predictor predictor) 154{ 155 rtx note; 156 if (!INSN_P (BB_END (bb))) 157 return false; 158 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1)) 159 if (REG_NOTE_KIND (note) == REG_BR_PRED 160 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor) 161 return true; 162 return false; 163} 164 165void 166predict_insn (rtx insn, enum br_predictor predictor, int probability) 167{ 168 if (!any_condjump_p (insn)) 169 abort (); 170 if (!flag_guess_branch_prob) 171 return; 172 173 REG_NOTES (insn) 174 = gen_rtx_EXPR_LIST (REG_BR_PRED, 175 gen_rtx_CONCAT (VOIDmode, 176 GEN_INT ((int) predictor), 177 GEN_INT ((int) probability)), 178 REG_NOTES (insn)); 179} 180 181/* Predict insn by given predictor. */ 182 183void 184predict_insn_def (rtx insn, enum br_predictor predictor, 185 enum prediction taken) 186{ 187 int probability = predictor_info[(int) predictor].hitrate; 188 189 if (taken != TAKEN) 190 probability = REG_BR_PROB_BASE - probability; 191 192 predict_insn (insn, predictor, probability); 193} 194 195/* Predict edge E with given probability if possible. */ 196 197void 198predict_edge (edge e, enum br_predictor predictor, int probability) 199{ 200 rtx last_insn; 201 last_insn = BB_END (e->src); 202 203 /* We can store the branch prediction information only about 204 conditional jumps. */ 205 if (!any_condjump_p (last_insn)) 206 return; 207 208 /* We always store probability of branching. */ 209 if (e->flags & EDGE_FALLTHRU) 210 probability = REG_BR_PROB_BASE - probability; 211 212 predict_insn (last_insn, predictor, probability); 213} 214 215/* Return true when we can store prediction on insn INSN. 216 At the moment we represent predictions only on conditional 217 jumps, not at computed jump or other complicated cases. */ 218static bool 219can_predict_insn_p (rtx insn) 220{ 221 return (GET_CODE (insn) == JUMP_INSN 222 && any_condjump_p (insn) 223 && BLOCK_FOR_INSN (insn)->succ->succ_next); 224} 225 226/* Predict edge E by given predictor if possible. */ 227 228void 229predict_edge_def (edge e, enum br_predictor predictor, 230 enum prediction taken) 231{ 232 int probability = predictor_info[(int) predictor].hitrate; 233 234 if (taken != TAKEN) 235 probability = REG_BR_PROB_BASE - probability; 236 237 predict_edge (e, predictor, probability); 238} 239 240/* Invert all branch predictions or probability notes in the INSN. This needs 241 to be done each time we invert the condition used by the jump. */ 242 243void 244invert_br_probabilities (rtx insn) 245{ 246 rtx note; 247 248 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 249 if (REG_NOTE_KIND (note) == REG_BR_PROB) 250 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0))); 251 else if (REG_NOTE_KIND (note) == REG_BR_PRED) 252 XEXP (XEXP (note, 0), 1) 253 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1))); 254} 255 256/* Dump information about the branch prediction to the output file. */ 257 258static void 259dump_prediction (enum br_predictor predictor, int probability, 260 basic_block bb, int used) 261{ 262 edge e = bb->succ; 263 264 if (!rtl_dump_file) 265 return; 266 267 while (e && (e->flags & EDGE_FALLTHRU)) 268 e = e->succ_next; 269 270 fprintf (rtl_dump_file, " %s heuristics%s: %.1f%%", 271 predictor_info[predictor].name, 272 used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE); 273 274 if (bb->count) 275 { 276 fprintf (rtl_dump_file, " exec "); 277 fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, bb->count); 278 if (e) 279 { 280 fprintf (rtl_dump_file, " hit "); 281 fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, e->count); 282 fprintf (rtl_dump_file, " (%.1f%%)", e->count * 100.0 / bb->count); 283 } 284 } 285 286 fprintf (rtl_dump_file, "\n"); 287} 288 289/* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB 290 note if not already present. Remove now useless REG_BR_PRED notes. */ 291 292static void 293combine_predictions_for_insn (rtx insn, basic_block bb) 294{ 295 rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0); 296 rtx *pnote = ®_NOTES (insn); 297 rtx note; 298 int best_probability = PROB_EVEN; 299 int best_predictor = END_PREDICTORS; 300 int combined_probability = REG_BR_PROB_BASE / 2; 301 int d; 302 bool first_match = false; 303 bool found = false; 304 305 if (rtl_dump_file) 306 fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn), 307 bb->index); 308 309 /* We implement "first match" heuristics and use probability guessed 310 by predictor with smallest index. In the future we will use better 311 probability combination techniques. */ 312 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 313 if (REG_NOTE_KIND (note) == REG_BR_PRED) 314 { 315 int predictor = INTVAL (XEXP (XEXP (note, 0), 0)); 316 int probability = INTVAL (XEXP (XEXP (note, 0), 1)); 317 318 found = true; 319 if (best_predictor > predictor) 320 best_probability = probability, best_predictor = predictor; 321 322 d = (combined_probability * probability 323 + (REG_BR_PROB_BASE - combined_probability) 324 * (REG_BR_PROB_BASE - probability)); 325 326 /* Use FP math to avoid overflows of 32bit integers. */ 327 if (d == 0) 328 /* If one probability is 0% and one 100%, avoid division by zero. */ 329 combined_probability = REG_BR_PROB_BASE / 2; 330 else 331 combined_probability = (((double) combined_probability) * probability 332 * REG_BR_PROB_BASE / d + 0.5); 333 } 334 335 /* Decide which heuristic to use. In case we didn't match anything, 336 use no_prediction heuristic, in case we did match, use either 337 first match or Dempster-Shaffer theory depending on the flags. */ 338 339 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH) 340 first_match = true; 341 342 if (!found) 343 dump_prediction (PRED_NO_PREDICTION, combined_probability, bb, true); 344 else 345 { 346 dump_prediction (PRED_DS_THEORY, combined_probability, bb, !first_match); 347 dump_prediction (PRED_FIRST_MATCH, best_probability, bb, first_match); 348 } 349 350 if (first_match) 351 combined_probability = best_probability; 352 dump_prediction (PRED_COMBINED, combined_probability, bb, true); 353 354 while (*pnote) 355 { 356 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED) 357 { 358 int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0)); 359 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1)); 360 361 dump_prediction (predictor, probability, bb, 362 !first_match || best_predictor == predictor); 363 *pnote = XEXP (*pnote, 1); 364 } 365 else 366 pnote = &XEXP (*pnote, 1); 367 } 368 369 if (!prob_note) 370 { 371 REG_NOTES (insn) 372 = gen_rtx_EXPR_LIST (REG_BR_PROB, 373 GEN_INT (combined_probability), REG_NOTES (insn)); 374 375 /* Save the prediction into CFG in case we are seeing non-degenerated 376 conditional jump. */ 377 if (bb->succ->succ_next) 378 { 379 BRANCH_EDGE (bb)->probability = combined_probability; 380 FALLTHRU_EDGE (bb)->probability 381 = REG_BR_PROB_BASE - combined_probability; 382 } 383 } 384} 385 386/* Statically estimate the probability that a branch will be taken. 387 ??? In the next revision there will be a number of other predictors added 388 from the above references. Further, each heuristic will be factored out 389 into its own function for clarity (and to facilitate the combination of 390 predictions). */ 391 392void 393estimate_probability (struct loops *loops_info) 394{ 395 basic_block bb; 396 unsigned i; 397 398 connect_infinite_loops_to_exit (); 399 calculate_dominance_info (CDI_DOMINATORS); 400 calculate_dominance_info (CDI_POST_DOMINATORS); 401 402 /* Try to predict out blocks in a loop that are not part of a 403 natural loop. */ 404 for (i = 1; i < loops_info->num; i++) 405 { 406 basic_block bb, *bbs; 407 unsigned j; 408 int exits; 409 struct loop *loop = loops_info->parray[i]; 410 struct loop_desc desc; 411 unsigned HOST_WIDE_INT niter; 412 413 flow_loop_scan (loop, LOOP_EXIT_EDGES); 414 exits = loop->num_exits; 415 416 if (simple_loop_p (loop, &desc) && desc.const_iter) 417 { 418 int prob; 419 niter = desc.niter + 1; 420 if (niter == 0) /* We might overflow here. */ 421 niter = desc.niter; 422 423 prob = (REG_BR_PROB_BASE 424 - (REG_BR_PROB_BASE + niter /2) / niter); 425 /* Branch prediction algorithm gives 0 frequency for everything 426 after the end of loop for loop having 0 probability to finish. */ 427 if (prob == REG_BR_PROB_BASE) 428 prob = REG_BR_PROB_BASE - 1; 429 predict_edge (desc.in_edge, PRED_LOOP_ITERATIONS, 430 prob); 431 } 432 433 bbs = get_loop_body (loop); 434 for (j = 0; j < loop->num_nodes; j++) 435 { 436 int header_found = 0; 437 edge e; 438 439 bb = bbs[j]; 440 441 /* Bypass loop heuristics on continue statement. These 442 statements construct loops via "non-loop" constructs 443 in the source language and are better to be handled 444 separately. */ 445 if (!can_predict_insn_p (BB_END (bb)) 446 || predicted_by_p (bb, PRED_CONTINUE)) 447 continue; 448 449 /* Loop branch heuristics - predict an edge back to a 450 loop's head as taken. */ 451 for (e = bb->succ; e; e = e->succ_next) 452 if (e->dest == loop->header 453 && e->src == loop->latch) 454 { 455 header_found = 1; 456 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN); 457 } 458 459 /* Loop exit heuristics - predict an edge exiting the loop if the 460 conditional has no loop header successors as not taken. */ 461 if (!header_found) 462 for (e = bb->succ; e; e = e->succ_next) 463 if (e->dest->index < 0 464 || !flow_bb_inside_loop_p (loop, e->dest)) 465 predict_edge 466 (e, PRED_LOOP_EXIT, 467 (REG_BR_PROB_BASE 468 - predictor_info [(int) PRED_LOOP_EXIT].hitrate) 469 / exits); 470 } 471 472 /* Free basic blocks from get_loop_body. */ 473 free (bbs); 474 } 475 476 /* Attempt to predict conditional jumps using a number of heuristics. */ 477 FOR_EACH_BB (bb) 478 { 479 rtx last_insn = BB_END (bb); 480 rtx cond, earliest; 481 edge e; 482 483 if (! can_predict_insn_p (last_insn)) 484 continue; 485 486 for (e = bb->succ; e; e = e->succ_next) 487 { 488 /* Predict early returns to be probable, as we've already taken 489 care for error returns and other are often used for fast paths 490 trought function. */ 491 if ((e->dest == EXIT_BLOCK_PTR 492 || (e->dest->succ && !e->dest->succ->succ_next 493 && e->dest->succ->dest == EXIT_BLOCK_PTR)) 494 && !predicted_by_p (bb, PRED_NULL_RETURN) 495 && !predicted_by_p (bb, PRED_CONST_RETURN) 496 && !predicted_by_p (bb, PRED_NEGATIVE_RETURN) 497 && !last_basic_block_p (e->dest)) 498 predict_edge_def (e, PRED_EARLY_RETURN, TAKEN); 499 500 /* Look for block we are guarding (ie we dominate it, 501 but it doesn't postdominate us). */ 502 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb 503 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src) 504 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest)) 505 { 506 rtx insn; 507 508 /* The call heuristic claims that a guarded function call 509 is improbable. This is because such calls are often used 510 to signal exceptional situations such as printing error 511 messages. */ 512 for (insn = BB_HEAD (e->dest); insn != NEXT_INSN (BB_END (e->dest)); 513 insn = NEXT_INSN (insn)) 514 if (GET_CODE (insn) == CALL_INSN 515 /* Constant and pure calls are hardly used to signalize 516 something exceptional. */ 517 && ! CONST_OR_PURE_CALL_P (insn)) 518 { 519 predict_edge_def (e, PRED_CALL, NOT_TAKEN); 520 break; 521 } 522 } 523 } 524 525 cond = get_condition (last_insn, &earliest, false); 526 if (! cond) 527 continue; 528 529 /* Try "pointer heuristic." 530 A comparison ptr == 0 is predicted as false. 531 Similarly, a comparison ptr1 == ptr2 is predicted as false. */ 532 if (GET_RTX_CLASS (GET_CODE (cond)) == '<' 533 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0))) 534 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1))))) 535 { 536 if (GET_CODE (cond) == EQ) 537 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN); 538 else if (GET_CODE (cond) == NE) 539 predict_insn_def (last_insn, PRED_POINTER, TAKEN); 540 } 541 else 542 543 /* Try "opcode heuristic." 544 EQ tests are usually false and NE tests are usually true. Also, 545 most quantities are positive, so we can make the appropriate guesses 546 about signed comparisons against zero. */ 547 switch (GET_CODE (cond)) 548 { 549 case CONST_INT: 550 /* Unconditional branch. */ 551 predict_insn_def (last_insn, PRED_UNCONDITIONAL, 552 cond == const0_rtx ? NOT_TAKEN : TAKEN); 553 break; 554 555 case EQ: 556 case UNEQ: 557 /* Floating point comparisons appears to behave in a very 558 unpredictable way because of special role of = tests in 559 FP code. */ 560 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) 561 ; 562 /* Comparisons with 0 are often used for booleans and there is 563 nothing useful to predict about them. */ 564 else if (XEXP (cond, 1) == const0_rtx 565 || XEXP (cond, 0) == const0_rtx) 566 ; 567 else 568 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN); 569 break; 570 571 case NE: 572 case LTGT: 573 /* Floating point comparisons appears to behave in a very 574 unpredictable way because of special role of = tests in 575 FP code. */ 576 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) 577 ; 578 /* Comparisons with 0 are often used for booleans and there is 579 nothing useful to predict about them. */ 580 else if (XEXP (cond, 1) == const0_rtx 581 || XEXP (cond, 0) == const0_rtx) 582 ; 583 else 584 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN); 585 break; 586 587 case ORDERED: 588 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN); 589 break; 590 591 case UNORDERED: 592 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN); 593 break; 594 595 case LE: 596 case LT: 597 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx 598 || XEXP (cond, 1) == constm1_rtx) 599 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN); 600 break; 601 602 case GE: 603 case GT: 604 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx 605 || XEXP (cond, 1) == constm1_rtx) 606 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN); 607 break; 608 609 default: 610 break; 611 } 612 } 613 614 /* Attach the combined probability to each conditional jump. */ 615 FOR_EACH_BB (bb) 616 if (GET_CODE (BB_END (bb)) == JUMP_INSN 617 && any_condjump_p (BB_END (bb)) 618 && bb->succ->succ_next != NULL) 619 combine_predictions_for_insn (BB_END (bb), bb); 620 621 free_dominance_info (CDI_POST_DOMINATORS); 622 623 remove_fake_edges (); 624 estimate_bb_frequencies (loops_info); 625} 626 627/* __builtin_expect dropped tokens into the insn stream describing expected 628 values of registers. Generate branch probabilities based off these 629 values. */ 630 631void 632expected_value_to_br_prob (void) 633{ 634 rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX; 635 636 for (insn = get_insns (); insn ; insn = NEXT_INSN (insn)) 637 { 638 switch (GET_CODE (insn)) 639 { 640 case NOTE: 641 /* Look for expected value notes. */ 642 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE) 643 { 644 ev = NOTE_EXPECTED_VALUE (insn); 645 ev_reg = XEXP (ev, 0); 646 delete_insn (insn); 647 } 648 continue; 649 650 case CODE_LABEL: 651 /* Never propagate across labels. */ 652 ev = NULL_RTX; 653 continue; 654 655 case JUMP_INSN: 656 /* Look for simple conditional branches. If we haven't got an 657 expected value yet, no point going further. */ 658 if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX 659 || ! any_condjump_p (insn)) 660 continue; 661 break; 662 663 default: 664 /* Look for insns that clobber the EV register. */ 665 if (ev && reg_set_p (ev_reg, insn)) 666 ev = NULL_RTX; 667 continue; 668 } 669 670 /* Collect the branch condition, hopefully relative to EV_REG. */ 671 /* ??? At present we'll miss things like 672 (expected_value (eq r70 0)) 673 (set r71 -1) 674 (set r80 (lt r70 r71)) 675 (set pc (if_then_else (ne r80 0) ...)) 676 as canonicalize_condition will render this to us as 677 (lt r70, r71) 678 Could use cselib to try and reduce this further. */ 679 cond = XEXP (SET_SRC (pc_set (insn)), 0); 680 cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg, false); 681 if (! cond || XEXP (cond, 0) != ev_reg 682 || GET_CODE (XEXP (cond, 1)) != CONST_INT) 683 continue; 684 685 /* Substitute and simplify. Given that the expression we're 686 building involves two constants, we should wind up with either 687 true or false. */ 688 cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode, 689 XEXP (ev, 1), XEXP (cond, 1)); 690 cond = simplify_rtx (cond); 691 692 /* Turn the condition into a scaled branch probability. */ 693 if (cond != const_true_rtx && cond != const0_rtx) 694 abort (); 695 predict_insn_def (insn, PRED_BUILTIN_EXPECT, 696 cond == const_true_rtx ? TAKEN : NOT_TAKEN); 697 } 698} 699 700/* Check whether this is the last basic block of function. Commonly 701 there is one extra common cleanup block. */ 702static bool 703last_basic_block_p (basic_block bb) 704{ 705 if (bb == EXIT_BLOCK_PTR) 706 return false; 707 708 return (bb->next_bb == EXIT_BLOCK_PTR 709 || (bb->next_bb->next_bb == EXIT_BLOCK_PTR 710 && bb->succ && !bb->succ->succ_next 711 && bb->succ->dest->next_bb == EXIT_BLOCK_PTR)); 712} 713 714/* Sets branch probabilities according to PREDiction and 715 FLAGS. HEADS[bb->index] should be index of basic block in that we 716 need to alter branch predictions (i.e. the first of our dominators 717 such that we do not post-dominate it) (but we fill this information 718 on demand, so -1 may be there in case this was not needed yet). */ 719 720static void 721process_note_prediction (basic_block bb, int *heads, int pred, int flags) 722{ 723 edge e; 724 int y; 725 bool taken; 726 727 taken = flags & IS_TAKEN; 728 729 if (heads[bb->index] < 0) 730 { 731 /* This is first time we need this field in heads array; so 732 find first dominator that we do not post-dominate (we are 733 using already known members of heads array). */ 734 basic_block ai = bb; 735 basic_block next_ai = get_immediate_dominator (CDI_DOMINATORS, bb); 736 int head; 737 738 while (heads[next_ai->index] < 0) 739 { 740 if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb)) 741 break; 742 heads[next_ai->index] = ai->index; 743 ai = next_ai; 744 next_ai = get_immediate_dominator (CDI_DOMINATORS, next_ai); 745 } 746 if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb)) 747 head = next_ai->index; 748 else 749 head = heads[next_ai->index]; 750 while (next_ai != bb) 751 { 752 next_ai = ai; 753 if (heads[ai->index] == ENTRY_BLOCK) 754 ai = ENTRY_BLOCK_PTR; 755 else 756 ai = BASIC_BLOCK (heads[ai->index]); 757 heads[next_ai->index] = head; 758 } 759 } 760 y = heads[bb->index]; 761 762 /* Now find the edge that leads to our branch and aply the prediction. */ 763 764 if (y == last_basic_block || !can_predict_insn_p (BB_END (BASIC_BLOCK (y)))) 765 return; 766 for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next) 767 if (e->dest->index >= 0 768 && dominated_by_p (CDI_POST_DOMINATORS, e->dest, bb)) 769 predict_edge_def (e, pred, taken); 770} 771 772/* Gathers NOTE_INSN_PREDICTIONs in given basic block and turns them 773 into branch probabilities. For description of heads array, see 774 process_note_prediction. */ 775 776static void 777process_note_predictions (basic_block bb, int *heads) 778{ 779 rtx insn; 780 edge e; 781 782 /* Additionally, we check here for blocks with no successors. */ 783 int contained_noreturn_call = 0; 784 int was_bb_head = 0; 785 int noreturn_block = 1; 786 787 for (insn = BB_END (bb); insn; 788 was_bb_head |= (insn == BB_HEAD (bb)), insn = PREV_INSN (insn)) 789 { 790 if (GET_CODE (insn) != NOTE) 791 { 792 if (was_bb_head) 793 break; 794 else 795 { 796 /* Noreturn calls cause program to exit, therefore they are 797 always predicted as not taken. */ 798 if (GET_CODE (insn) == CALL_INSN 799 && find_reg_note (insn, REG_NORETURN, NULL)) 800 contained_noreturn_call = 1; 801 continue; 802 } 803 } 804 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_PREDICTION) 805 { 806 int alg = (int) NOTE_PREDICTION_ALG (insn); 807 /* Process single prediction note. */ 808 process_note_prediction (bb, 809 heads, 810 alg, (int) NOTE_PREDICTION_FLAGS (insn)); 811 delete_insn (insn); 812 } 813 } 814 for (e = bb->succ; e; e = e->succ_next) 815 if (!(e->flags & EDGE_FAKE)) 816 noreturn_block = 0; 817 if (contained_noreturn_call) 818 { 819 /* This block ended from other reasons than because of return. 820 If it is because of noreturn call, this should certainly not 821 be taken. Otherwise it is probably some error recovery. */ 822 process_note_prediction (bb, heads, PRED_NORETURN, NOT_TAKEN); 823 } 824} 825 826/* Gathers NOTE_INSN_PREDICTIONs and turns them into 827 branch probabilities. */ 828 829void 830note_prediction_to_br_prob (void) 831{ 832 basic_block bb; 833 int *heads; 834 835 /* To enable handling of noreturn blocks. */ 836 add_noreturn_fake_exit_edges (); 837 connect_infinite_loops_to_exit (); 838 839 calculate_dominance_info (CDI_POST_DOMINATORS); 840 calculate_dominance_info (CDI_DOMINATORS); 841 842 heads = xmalloc (sizeof (int) * last_basic_block); 843 memset (heads, -1, sizeof (int) * last_basic_block); 844 heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block; 845 846 /* Process all prediction notes. */ 847 848 FOR_EACH_BB (bb) 849 process_note_predictions (bb, heads); 850 851 free_dominance_info (CDI_POST_DOMINATORS); 852 free_dominance_info (CDI_DOMINATORS); 853 free (heads); 854 855 remove_fake_edges (); 856} 857 858/* This is used to carry information about basic blocks. It is 859 attached to the AUX field of the standard CFG block. */ 860 861typedef struct block_info_def 862{ 863 /* Estimated frequency of execution of basic_block. */ 864 sreal frequency; 865 866 /* To keep queue of basic blocks to process. */ 867 basic_block next; 868 869 /* True if block needs to be visited in propagate_freq. */ 870 unsigned int tovisit:1; 871 872 /* Number of predecessors we need to visit first. */ 873 int npredecessors; 874} *block_info; 875 876/* Similar information for edges. */ 877typedef struct edge_info_def 878{ 879 /* In case edge is an loopback edge, the probability edge will be reached 880 in case header is. Estimated number of iterations of the loop can be 881 then computed as 1 / (1 - back_edge_prob). */ 882 sreal back_edge_prob; 883 /* True if the edge is an loopback edge in the natural loop. */ 884 unsigned int back_edge:1; 885} *edge_info; 886 887#define BLOCK_INFO(B) ((block_info) (B)->aux) 888#define EDGE_INFO(E) ((edge_info) (E)->aux) 889 890/* Helper function for estimate_bb_frequencies. 891 Propagate the frequencies for LOOP. */ 892 893static void 894propagate_freq (struct loop *loop) 895{ 896 basic_block head = loop->header; 897 basic_block bb; 898 basic_block last; 899 edge e; 900 basic_block nextbb; 901 902 /* For each basic block we need to visit count number of his predecessors 903 we need to visit first. */ 904 FOR_EACH_BB (bb) 905 { 906 if (BLOCK_INFO (bb)->tovisit) 907 { 908 int count = 0; 909 910 for (e = bb->pred; e; e = e->pred_next) 911 if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK)) 912 count++; 913 else if (BLOCK_INFO (e->src)->tovisit 914 && rtl_dump_file && !EDGE_INFO (e)->back_edge) 915 fprintf (rtl_dump_file, 916 "Irreducible region hit, ignoring edge to %i->%i\n", 917 e->src->index, bb->index); 918 BLOCK_INFO (bb)->npredecessors = count; 919 } 920 } 921 922 memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one)); 923 last = head; 924 for (bb = head; bb; bb = nextbb) 925 { 926 sreal cyclic_probability, frequency; 927 928 memcpy (&cyclic_probability, &real_zero, sizeof (real_zero)); 929 memcpy (&frequency, &real_zero, sizeof (real_zero)); 930 931 nextbb = BLOCK_INFO (bb)->next; 932 BLOCK_INFO (bb)->next = NULL; 933 934 /* Compute frequency of basic block. */ 935 if (bb != head) 936 { 937#ifdef ENABLE_CHECKING 938 for (e = bb->pred; e; e = e->pred_next) 939 if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK)) 940 abort (); 941#endif 942 943 for (e = bb->pred; e; e = e->pred_next) 944 if (EDGE_INFO (e)->back_edge) 945 { 946 sreal_add (&cyclic_probability, &cyclic_probability, 947 &EDGE_INFO (e)->back_edge_prob); 948 } 949 else if (!(e->flags & EDGE_DFS_BACK)) 950 { 951 sreal tmp; 952 953 /* frequency += (e->probability 954 * BLOCK_INFO (e->src)->frequency / 955 REG_BR_PROB_BASE); */ 956 957 sreal_init (&tmp, e->probability, 0); 958 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency); 959 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base); 960 sreal_add (&frequency, &frequency, &tmp); 961 } 962 963 if (sreal_compare (&cyclic_probability, &real_zero) == 0) 964 { 965 memcpy (&BLOCK_INFO (bb)->frequency, &frequency, 966 sizeof (frequency)); 967 } 968 else 969 { 970 if (sreal_compare (&cyclic_probability, &real_almost_one) > 0) 971 { 972 memcpy (&cyclic_probability, &real_almost_one, 973 sizeof (real_almost_one)); 974 } 975 976 /* BLOCK_INFO (bb)->frequency = frequency 977 / (1 - cyclic_probability) */ 978 979 sreal_sub (&cyclic_probability, &real_one, &cyclic_probability); 980 sreal_div (&BLOCK_INFO (bb)->frequency, 981 &frequency, &cyclic_probability); 982 } 983 } 984 985 BLOCK_INFO (bb)->tovisit = 0; 986 987 /* Compute back edge frequencies. */ 988 for (e = bb->succ; e; e = e->succ_next) 989 if (e->dest == head) 990 { 991 sreal tmp; 992 993 /* EDGE_INFO (e)->back_edge_prob 994 = ((e->probability * BLOCK_INFO (bb)->frequency) 995 / REG_BR_PROB_BASE); */ 996 997 sreal_init (&tmp, e->probability, 0); 998 sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency); 999 sreal_mul (&EDGE_INFO (e)->back_edge_prob, 1000 &tmp, &real_inv_br_prob_base); 1001 } 1002 1003 /* Propagate to successor blocks. */ 1004 for (e = bb->succ; e; e = e->succ_next) 1005 if (!(e->flags & EDGE_DFS_BACK) 1006 && BLOCK_INFO (e->dest)->npredecessors) 1007 { 1008 BLOCK_INFO (e->dest)->npredecessors--; 1009 if (!BLOCK_INFO (e->dest)->npredecessors) 1010 { 1011 if (!nextbb) 1012 nextbb = e->dest; 1013 else 1014 BLOCK_INFO (last)->next = e->dest; 1015 1016 last = e->dest; 1017 } 1018 } 1019 } 1020} 1021 1022/* Estimate probabilities of loopback edges in loops at same nest level. */ 1023 1024static void 1025estimate_loops_at_level (struct loop *first_loop) 1026{ 1027 struct loop *loop; 1028 1029 for (loop = first_loop; loop; loop = loop->next) 1030 { 1031 edge e; 1032 basic_block *bbs; 1033 unsigned i; 1034 1035 estimate_loops_at_level (loop->inner); 1036 1037 if (loop->latch->succ) /* Do not do this for dummy function loop. */ 1038 { 1039 /* Find current loop back edge and mark it. */ 1040 e = loop_latch_edge (loop); 1041 EDGE_INFO (e)->back_edge = 1; 1042 } 1043 1044 bbs = get_loop_body (loop); 1045 for (i = 0; i < loop->num_nodes; i++) 1046 BLOCK_INFO (bbs[i])->tovisit = 1; 1047 free (bbs); 1048 propagate_freq (loop); 1049 } 1050} 1051 1052/* Convert counts measured by profile driven feedback to frequencies. */ 1053 1054static void 1055counts_to_freqs (void) 1056{ 1057 gcov_type count_max = 1; 1058 basic_block bb; 1059 1060 FOR_EACH_BB (bb) 1061 count_max = MAX (bb->count, count_max); 1062 1063 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1064 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max; 1065} 1066 1067/* Return true if function is likely to be expensive, so there is no point to 1068 optimize performance of prologue, epilogue or do inlining at the expense 1069 of code size growth. THRESHOLD is the limit of number of instructions 1070 function can execute at average to be still considered not expensive. */ 1071 1072bool 1073expensive_function_p (int threshold) 1074{ 1075 unsigned int sum = 0; 1076 basic_block bb; 1077 unsigned int limit; 1078 1079 /* We can not compute accurately for large thresholds due to scaled 1080 frequencies. */ 1081 if (threshold > BB_FREQ_MAX) 1082 abort (); 1083 1084 /* Frequencies are out of range. This either means that function contains 1085 internal loop executing more than BB_FREQ_MAX times or profile feedback 1086 is available and function has not been executed at all. */ 1087 if (ENTRY_BLOCK_PTR->frequency == 0) 1088 return true; 1089 1090 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */ 1091 limit = ENTRY_BLOCK_PTR->frequency * threshold; 1092 FOR_EACH_BB (bb) 1093 { 1094 rtx insn; 1095 1096 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 1097 insn = NEXT_INSN (insn)) 1098 if (active_insn_p (insn)) 1099 { 1100 sum += bb->frequency; 1101 if (sum > limit) 1102 return true; 1103 } 1104 } 1105 1106 return false; 1107} 1108 1109/* Estimate basic blocks frequency by given branch probabilities. */ 1110 1111static void 1112estimate_bb_frequencies (struct loops *loops) 1113{ 1114 basic_block bb; 1115 sreal freq_max; 1116 1117 if (flag_branch_probabilities) 1118 counts_to_freqs (); 1119 else 1120 { 1121 static int real_values_initialized = 0; 1122 1123 if (!real_values_initialized) 1124 { 1125 real_values_initialized = 1; 1126 sreal_init (&real_zero, 0, 0); 1127 sreal_init (&real_one, 1, 0); 1128 sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0); 1129 sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0); 1130 sreal_init (&real_one_half, 1, -1); 1131 sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base); 1132 sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base); 1133 } 1134 1135 mark_dfs_back_edges (); 1136 /* Fill in the probability values in flowgraph based on the REG_BR_PROB 1137 notes. */ 1138 FOR_EACH_BB (bb) 1139 { 1140 rtx last_insn = BB_END (bb); 1141 1142 if (!can_predict_insn_p (last_insn)) 1143 { 1144 /* We can predict only conditional jumps at the moment. 1145 Expect each edge to be equally probable. 1146 ?? In the future we want to make abnormal edges improbable. */ 1147 int nedges = 0; 1148 edge e; 1149 1150 for (e = bb->succ; e; e = e->succ_next) 1151 { 1152 nedges++; 1153 if (e->probability != 0) 1154 break; 1155 } 1156 if (!e) 1157 for (e = bb->succ; e; e = e->succ_next) 1158 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges; 1159 } 1160 } 1161 1162 ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE; 1163 1164 /* Set up block info for each basic block. */ 1165 alloc_aux_for_blocks (sizeof (struct block_info_def)); 1166 alloc_aux_for_edges (sizeof (struct edge_info_def)); 1167 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1168 { 1169 edge e; 1170 1171 BLOCK_INFO (bb)->tovisit = 0; 1172 for (e = bb->succ; e; e = e->succ_next) 1173 { 1174 sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0); 1175 sreal_mul (&EDGE_INFO (e)->back_edge_prob, 1176 &EDGE_INFO (e)->back_edge_prob, 1177 &real_inv_br_prob_base); 1178 } 1179 } 1180 1181 /* First compute probabilities locally for each loop from innermost 1182 to outermost to examine probabilities for back edges. */ 1183 estimate_loops_at_level (loops->tree_root); 1184 1185 memcpy (&freq_max, &real_zero, sizeof (real_zero)); 1186 FOR_EACH_BB (bb) 1187 if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0) 1188 memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max)); 1189 1190 sreal_div (&freq_max, &real_bb_freq_max, &freq_max); 1191 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1192 { 1193 sreal tmp; 1194 1195 sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max); 1196 sreal_add (&tmp, &tmp, &real_one_half); 1197 bb->frequency = sreal_to_int (&tmp); 1198 } 1199 1200 free_aux_for_blocks (); 1201 free_aux_for_edges (); 1202 } 1203 compute_function_frequency (); 1204 if (flag_reorder_functions) 1205 choose_function_section (); 1206} 1207 1208/* Decide whether function is hot, cold or unlikely executed. */ 1209static void 1210compute_function_frequency (void) 1211{ 1212 basic_block bb; 1213 1214 if (!profile_info || !flag_branch_probabilities) 1215 return; 1216 cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED; 1217 FOR_EACH_BB (bb) 1218 { 1219 if (maybe_hot_bb_p (bb)) 1220 { 1221 cfun->function_frequency = FUNCTION_FREQUENCY_HOT; 1222 return; 1223 } 1224 if (!probably_never_executed_bb_p (bb)) 1225 cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL; 1226 } 1227} 1228 1229/* Choose appropriate section for the function. */ 1230static void 1231choose_function_section (void) 1232{ 1233 if (DECL_SECTION_NAME (current_function_decl) 1234 || !targetm.have_named_sections 1235 /* Theoretically we can split the gnu.linkonce text section too, 1236 but this requires more work as the frequency needs to match 1237 for all generated objects so we need to merge the frequency 1238 of all instances. For now just never set frequency for these. */ 1239 || DECL_ONE_ONLY (current_function_decl)) 1240 return; 1241 if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT) 1242 DECL_SECTION_NAME (current_function_decl) = 1243 build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME); 1244 if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED) 1245 DECL_SECTION_NAME (current_function_decl) = 1246 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME), 1247 UNLIKELY_EXECUTED_TEXT_SECTION_NAME); 1248} 1249