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