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 && compare_tree_int (niter, max-1) == -1) 987 nitercst = tree_low_cst (niter, 1) + 1; 988 else 989 nitercst = max; 990 predictor = PRED_LOOP_ITERATIONS; 991 } 992 /* If we have just one exit and we can derive some information about 993 the number of iterations of the loop from the statements inside 994 the loop, use it to predict this exit. */ 995 else if (n_exits == 1) 996 { 997 nitercst = max_stmt_executions_int (loop, false); 998 if (nitercst < 0) 999 continue; 1000 if (nitercst > max) 1001 nitercst = max; 1002 1003 predictor = PRED_LOOP_ITERATIONS_GUESSED; 1004 } 1005 else 1006 continue; 1007 1008 probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst); 1009 predict_edge (ex, predictor, probability); 1010 } 1011 VEC_free (edge, heap, exits); 1012 1013 bbs = get_loop_body (loop); 1014 1015 for (j = 0; j < loop->num_nodes; j++) 1016 { 1017 int header_found = 0; 1018 edge e; 1019 edge_iterator ei; 1020 1021 bb = bbs[j]; 1022 1023 /* Bypass loop heuristics on continue statement. These 1024 statements construct loops via "non-loop" constructs 1025 in the source language and are better to be handled 1026 separately. */ 1027 if (predicted_by_p (bb, PRED_CONTINUE)) 1028 continue; 1029 1030 /* Loop branch heuristics - predict an edge back to a 1031 loop's head as taken. */ 1032 if (bb == loop->latch) 1033 { 1034 e = find_edge (loop->latch, loop->header); 1035 if (e) 1036 { 1037 header_found = 1; 1038 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN); 1039 } 1040 } 1041 1042 /* Loop exit heuristics - predict an edge exiting the loop if the 1043 conditional has no loop header successors as not taken. */ 1044 if (!header_found 1045 /* If we already used more reliable loop exit predictors, do not 1046 bother with PRED_LOOP_EXIT. */ 1047 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED) 1048 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS)) 1049 { 1050 /* For loop with many exits we don't want to predict all exits 1051 with the pretty large probability, because if all exits are 1052 considered in row, the loop would be predicted to iterate 1053 almost never. The code to divide probability by number of 1054 exits is very rough. It should compute the number of exits 1055 taken in each patch through function (not the overall number 1056 of exits that might be a lot higher for loops with wide switch 1057 statements in them) and compute n-th square root. 1058 1059 We limit the minimal probability by 2% to avoid 1060 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction 1061 as this was causing regression in perl benchmark containing such 1062 a wide loop. */ 1063 1064 int probability = ((REG_BR_PROB_BASE 1065 - predictor_info [(int) PRED_LOOP_EXIT].hitrate) 1066 / n_exits); 1067 if (probability < HITRATE (2)) 1068 probability = HITRATE (2); 1069 FOR_EACH_EDGE (e, ei, bb->succs) 1070 if (e->dest->index < NUM_FIXED_BLOCKS 1071 || !flow_bb_inside_loop_p (loop, e->dest)) 1072 predict_edge (e, PRED_LOOP_EXIT, probability); 1073 } 1074 } 1075 1076 /* Free basic blocks from get_loop_body. */ 1077 free (bbs); 1078 } 1079 } 1080 1081 /* Attempt to predict probabilities of BB outgoing edges using local 1082 properties. */ 1083 static void 1084 bb_estimate_probability_locally (basic_block bb) 1085 { 1086 rtx last_insn = BB_END (bb); 1087 rtx cond; 1088 1089 if (! can_predict_insn_p (last_insn)) 1090 return; 1091 cond = get_condition (last_insn, NULL, false, false); 1092 if (! cond) 1093 return; 1094 1095 /* Try "pointer heuristic." 1096 A comparison ptr == 0 is predicted as false. 1097 Similarly, a comparison ptr1 == ptr2 is predicted as false. */ 1098 if (COMPARISON_P (cond) 1099 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0))) 1100 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1))))) 1101 { 1102 if (GET_CODE (cond) == EQ) 1103 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN); 1104 else if (GET_CODE (cond) == NE) 1105 predict_insn_def (last_insn, PRED_POINTER, TAKEN); 1106 } 1107 else 1108 1109 /* Try "opcode heuristic." 1110 EQ tests are usually false and NE tests are usually true. Also, 1111 most quantities are positive, so we can make the appropriate guesses 1112 about signed comparisons against zero. */ 1113 switch (GET_CODE (cond)) 1114 { 1115 case CONST_INT: 1116 /* Unconditional branch. */ 1117 predict_insn_def (last_insn, PRED_UNCONDITIONAL, 1118 cond == const0_rtx ? NOT_TAKEN : TAKEN); 1119 break; 1120 1121 case EQ: 1122 case UNEQ: 1123 /* Floating point comparisons appears to behave in a very 1124 unpredictable way because of special role of = tests in 1125 FP code. */ 1126 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) 1127 ; 1128 /* Comparisons with 0 are often used for booleans and there is 1129 nothing useful to predict about them. */ 1130 else if (XEXP (cond, 1) == const0_rtx 1131 || XEXP (cond, 0) == const0_rtx) 1132 ; 1133 else 1134 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN); 1135 break; 1136 1137 case NE: 1138 case LTGT: 1139 /* Floating point comparisons appears to behave in a very 1140 unpredictable way because of special role of = tests in 1141 FP code. */ 1142 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) 1143 ; 1144 /* Comparisons with 0 are often used for booleans and there is 1145 nothing useful to predict about them. */ 1146 else if (XEXP (cond, 1) == const0_rtx 1147 || XEXP (cond, 0) == const0_rtx) 1148 ; 1149 else 1150 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN); 1151 break; 1152 1153 case ORDERED: 1154 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN); 1155 break; 1156 1157 case UNORDERED: 1158 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN); 1159 break; 1160 1161 case LE: 1162 case LT: 1163 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx 1164 || XEXP (cond, 1) == constm1_rtx) 1165 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN); 1166 break; 1167 1168 case GE: 1169 case GT: 1170 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx 1171 || XEXP (cond, 1) == constm1_rtx) 1172 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN); 1173 break; 1174 1175 default: 1176 break; 1177 } 1178 } 1179 1180 /* Set edge->probability for each successor edge of BB. */ 1181 void 1182 guess_outgoing_edge_probabilities (basic_block bb) 1183 { 1184 bb_estimate_probability_locally (bb); 1185 combine_predictions_for_insn (BB_END (bb), bb); 1186 } 1187 1188 static tree expr_expected_value (tree, bitmap); 1189 1190 /* Helper function for expr_expected_value. */ 1191 1192 static tree 1193 expr_expected_value_1 (tree type, tree op0, enum tree_code code, 1194 tree op1, bitmap visited) 1195 { 1196 gimple def; 1197 1198 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) 1199 { 1200 if (TREE_CONSTANT (op0)) 1201 return op0; 1202 1203 if (code != SSA_NAME) 1204 return NULL_TREE; 1205 1206 def = SSA_NAME_DEF_STMT (op0); 1207 1208 /* If we were already here, break the infinite cycle. */ 1209 if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0))) 1210 return NULL; 1211 1212 if (gimple_code (def) == GIMPLE_PHI) 1213 { 1214 /* All the arguments of the PHI node must have the same constant 1215 length. */ 1216 int i, n = gimple_phi_num_args (def); 1217 tree val = NULL, new_val; 1218 1219 for (i = 0; i < n; i++) 1220 { 1221 tree arg = PHI_ARG_DEF (def, i); 1222 1223 /* If this PHI has itself as an argument, we cannot 1224 determine the string length of this argument. However, 1225 if we can find an expected constant value for the other 1226 PHI args then we can still be sure that this is 1227 likely a constant. So be optimistic and just 1228 continue with the next argument. */ 1229 if (arg == PHI_RESULT (def)) 1230 continue; 1231 1232 new_val = expr_expected_value (arg, visited); 1233 if (!new_val) 1234 return NULL; 1235 if (!val) 1236 val = new_val; 1237 else if (!operand_equal_p (val, new_val, false)) 1238 return NULL; 1239 } 1240 return val; 1241 } 1242 if (is_gimple_assign (def)) 1243 { 1244 if (gimple_assign_lhs (def) != op0) 1245 return NULL; 1246 1247 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)), 1248 gimple_assign_rhs1 (def), 1249 gimple_assign_rhs_code (def), 1250 gimple_assign_rhs2 (def), 1251 visited); 1252 } 1253 1254 if (is_gimple_call (def)) 1255 { 1256 tree decl = gimple_call_fndecl (def); 1257 if (!decl) 1258 return NULL; 1259 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL) 1260 switch (DECL_FUNCTION_CODE (decl)) 1261 { 1262 case BUILT_IN_EXPECT: 1263 { 1264 tree val; 1265 if (gimple_call_num_args (def) != 2) 1266 return NULL; 1267 val = gimple_call_arg (def, 0); 1268 if (TREE_CONSTANT (val)) 1269 return val; 1270 return gimple_call_arg (def, 1); 1271 } 1272 1273 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N: 1274 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1: 1275 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2: 1276 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4: 1277 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8: 1278 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16: 1279 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE: 1280 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N: 1281 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1: 1282 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2: 1283 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4: 1284 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8: 1285 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16: 1286 /* Assume that any given atomic operation has low contention, 1287 and thus the compare-and-swap operation succeeds. */ 1288 return boolean_true_node; 1289 } 1290 } 1291 1292 return NULL; 1293 } 1294 1295 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS) 1296 { 1297 tree res; 1298 op0 = expr_expected_value (op0, visited); 1299 if (!op0) 1300 return NULL; 1301 op1 = expr_expected_value (op1, visited); 1302 if (!op1) 1303 return NULL; 1304 res = fold_build2 (code, type, op0, op1); 1305 if (TREE_CONSTANT (res)) 1306 return res; 1307 return NULL; 1308 } 1309 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS) 1310 { 1311 tree res; 1312 op0 = expr_expected_value (op0, visited); 1313 if (!op0) 1314 return NULL; 1315 res = fold_build1 (code, type, op0); 1316 if (TREE_CONSTANT (res)) 1317 return res; 1318 return NULL; 1319 } 1320 return NULL; 1321 } 1322 1323 /* Return constant EXPR will likely have at execution time, NULL if unknown. 1324 The function is used by builtin_expect branch predictor so the evidence 1325 must come from this construct and additional possible constant folding. 1326 1327 We may want to implement more involved value guess (such as value range 1328 propagation based prediction), but such tricks shall go to new 1329 implementation. */ 1330 1331 static tree 1332 expr_expected_value (tree expr, bitmap visited) 1333 { 1334 enum tree_code code; 1335 tree op0, op1; 1336 1337 if (TREE_CONSTANT (expr)) 1338 return expr; 1339 1340 extract_ops_from_tree (expr, &code, &op0, &op1); 1341 return expr_expected_value_1 (TREE_TYPE (expr), 1342 op0, code, op1, visited); 1343 } 1344 1345 1346 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements 1347 we no longer need. */ 1348 static unsigned int 1349 strip_predict_hints (void) 1350 { 1351 basic_block bb; 1352 gimple ass_stmt; 1353 tree var; 1354 1355 FOR_EACH_BB (bb) 1356 { 1357 gimple_stmt_iterator bi; 1358 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);) 1359 { 1360 gimple stmt = gsi_stmt (bi); 1361 1362 if (gimple_code (stmt) == GIMPLE_PREDICT) 1363 { 1364 gsi_remove (&bi, true); 1365 continue; 1366 } 1367 else if (gimple_code (stmt) == GIMPLE_CALL) 1368 { 1369 tree fndecl = gimple_call_fndecl (stmt); 1370 1371 if (fndecl 1372 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL 1373 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT 1374 && gimple_call_num_args (stmt) == 2) 1375 { 1376 var = gimple_call_lhs (stmt); 1377 if (var) 1378 { 1379 ass_stmt 1380 = gimple_build_assign (var, gimple_call_arg (stmt, 0)); 1381 gsi_replace (&bi, ass_stmt, true); 1382 } 1383 else 1384 { 1385 gsi_remove (&bi, true); 1386 continue; 1387 } 1388 } 1389 } 1390 gsi_next (&bi); 1391 } 1392 } 1393 return 0; 1394 } 1395 1396 /* Predict using opcode of the last statement in basic block. */ 1397 static void 1398 tree_predict_by_opcode (basic_block bb) 1399 { 1400 gimple stmt = last_stmt (bb); 1401 edge then_edge; 1402 tree op0, op1; 1403 tree type; 1404 tree val; 1405 enum tree_code cmp; 1406 bitmap visited; 1407 edge_iterator ei; 1408 1409 if (!stmt || gimple_code (stmt) != GIMPLE_COND) 1410 return; 1411 FOR_EACH_EDGE (then_edge, ei, bb->succs) 1412 if (then_edge->flags & EDGE_TRUE_VALUE) 1413 break; 1414 op0 = gimple_cond_lhs (stmt); 1415 op1 = gimple_cond_rhs (stmt); 1416 cmp = gimple_cond_code (stmt); 1417 type = TREE_TYPE (op0); 1418 visited = BITMAP_ALLOC (NULL); 1419 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited); 1420 BITMAP_FREE (visited); 1421 if (val) 1422 { 1423 if (integer_zerop (val)) 1424 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN); 1425 else 1426 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN); 1427 return; 1428 } 1429 /* Try "pointer heuristic." 1430 A comparison ptr == 0 is predicted as false. 1431 Similarly, a comparison ptr1 == ptr2 is predicted as false. */ 1432 if (POINTER_TYPE_P (type)) 1433 { 1434 if (cmp == EQ_EXPR) 1435 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN); 1436 else if (cmp == NE_EXPR) 1437 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN); 1438 } 1439 else 1440 1441 /* Try "opcode heuristic." 1442 EQ tests are usually false and NE tests are usually true. Also, 1443 most quantities are positive, so we can make the appropriate guesses 1444 about signed comparisons against zero. */ 1445 switch (cmp) 1446 { 1447 case EQ_EXPR: 1448 case UNEQ_EXPR: 1449 /* Floating point comparisons appears to behave in a very 1450 unpredictable way because of special role of = tests in 1451 FP code. */ 1452 if (FLOAT_TYPE_P (type)) 1453 ; 1454 /* Comparisons with 0 are often used for booleans and there is 1455 nothing useful to predict about them. */ 1456 else if (integer_zerop (op0) || integer_zerop (op1)) 1457 ; 1458 else 1459 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN); 1460 break; 1461 1462 case NE_EXPR: 1463 case LTGT_EXPR: 1464 /* Floating point comparisons appears to behave in a very 1465 unpredictable way because of special role of = tests in 1466 FP code. */ 1467 if (FLOAT_TYPE_P (type)) 1468 ; 1469 /* Comparisons with 0 are often used for booleans and there is 1470 nothing useful to predict about them. */ 1471 else if (integer_zerop (op0) 1472 || integer_zerop (op1)) 1473 ; 1474 else 1475 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN); 1476 break; 1477 1478 case ORDERED_EXPR: 1479 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN); 1480 break; 1481 1482 case UNORDERED_EXPR: 1483 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN); 1484 break; 1485 1486 case LE_EXPR: 1487 case LT_EXPR: 1488 if (integer_zerop (op1) 1489 || integer_onep (op1) 1490 || integer_all_onesp (op1) 1491 || real_zerop (op1) 1492 || real_onep (op1) 1493 || real_minus_onep (op1)) 1494 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN); 1495 break; 1496 1497 case GE_EXPR: 1498 case GT_EXPR: 1499 if (integer_zerop (op1) 1500 || integer_onep (op1) 1501 || integer_all_onesp (op1) 1502 || real_zerop (op1) 1503 || real_onep (op1) 1504 || real_minus_onep (op1)) 1505 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN); 1506 break; 1507 1508 default: 1509 break; 1510 } 1511 } 1512 1513 /* Try to guess whether the value of return means error code. */ 1514 1515 static enum br_predictor 1516 return_prediction (tree val, enum prediction *prediction) 1517 { 1518 /* VOID. */ 1519 if (!val) 1520 return PRED_NO_PREDICTION; 1521 /* Different heuristics for pointers and scalars. */ 1522 if (POINTER_TYPE_P (TREE_TYPE (val))) 1523 { 1524 /* NULL is usually not returned. */ 1525 if (integer_zerop (val)) 1526 { 1527 *prediction = NOT_TAKEN; 1528 return PRED_NULL_RETURN; 1529 } 1530 } 1531 else if (INTEGRAL_TYPE_P (TREE_TYPE (val))) 1532 { 1533 /* Negative return values are often used to indicate 1534 errors. */ 1535 if (TREE_CODE (val) == INTEGER_CST 1536 && tree_int_cst_sgn (val) < 0) 1537 { 1538 *prediction = NOT_TAKEN; 1539 return PRED_NEGATIVE_RETURN; 1540 } 1541 /* Constant return values seems to be commonly taken. 1542 Zero/one often represent booleans so exclude them from the 1543 heuristics. */ 1544 if (TREE_CONSTANT (val) 1545 && (!integer_zerop (val) && !integer_onep (val))) 1546 { 1547 *prediction = TAKEN; 1548 return PRED_CONST_RETURN; 1549 } 1550 } 1551 return PRED_NO_PREDICTION; 1552 } 1553 1554 /* Find the basic block with return expression and look up for possible 1555 return value trying to apply RETURN_PREDICTION heuristics. */ 1556 static void 1557 apply_return_prediction (void) 1558 { 1559 gimple return_stmt = NULL; 1560 tree return_val; 1561 edge e; 1562 gimple phi; 1563 int phi_num_args, i; 1564 enum br_predictor pred; 1565 enum prediction direction; 1566 edge_iterator ei; 1567 1568 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 1569 { 1570 return_stmt = last_stmt (e->src); 1571 if (return_stmt 1572 && gimple_code (return_stmt) == GIMPLE_RETURN) 1573 break; 1574 } 1575 if (!e) 1576 return; 1577 return_val = gimple_return_retval (return_stmt); 1578 if (!return_val) 1579 return; 1580 if (TREE_CODE (return_val) != SSA_NAME 1581 || !SSA_NAME_DEF_STMT (return_val) 1582 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI) 1583 return; 1584 phi = SSA_NAME_DEF_STMT (return_val); 1585 phi_num_args = gimple_phi_num_args (phi); 1586 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction); 1587 1588 /* Avoid the degenerate case where all return values form the function 1589 belongs to same category (ie they are all positive constants) 1590 so we can hardly say something about them. */ 1591 for (i = 1; i < phi_num_args; i++) 1592 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction)) 1593 break; 1594 if (i != phi_num_args) 1595 for (i = 0; i < phi_num_args; i++) 1596 { 1597 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction); 1598 if (pred != PRED_NO_PREDICTION) 1599 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred, 1600 direction); 1601 } 1602 } 1603 1604 /* Look for basic block that contains unlikely to happen events 1605 (such as noreturn calls) and mark all paths leading to execution 1606 of this basic blocks as unlikely. */ 1607 1608 static void 1609 tree_bb_level_predictions (void) 1610 { 1611 basic_block bb; 1612 bool has_return_edges = false; 1613 edge e; 1614 edge_iterator ei; 1615 1616 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 1617 if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH))) 1618 { 1619 has_return_edges = true; 1620 break; 1621 } 1622 1623 apply_return_prediction (); 1624 1625 FOR_EACH_BB (bb) 1626 { 1627 gimple_stmt_iterator gsi; 1628 1629 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1630 { 1631 gimple stmt = gsi_stmt (gsi); 1632 tree decl; 1633 1634 if (is_gimple_call (stmt)) 1635 { 1636 if ((gimple_call_flags (stmt) & ECF_NORETURN) 1637 && has_return_edges) 1638 predict_paths_leading_to (bb, PRED_NORETURN, 1639 NOT_TAKEN); 1640 decl = gimple_call_fndecl (stmt); 1641 if (decl 1642 && lookup_attribute ("cold", 1643 DECL_ATTRIBUTES (decl))) 1644 predict_paths_leading_to (bb, PRED_COLD_FUNCTION, 1645 NOT_TAKEN); 1646 } 1647 else if (gimple_code (stmt) == GIMPLE_PREDICT) 1648 { 1649 predict_paths_leading_to (bb, gimple_predict_predictor (stmt), 1650 gimple_predict_outcome (stmt)); 1651 /* Keep GIMPLE_PREDICT around so early inlining will propagate 1652 hints to callers. */ 1653 } 1654 } 1655 } 1656 } 1657 1658 #ifdef ENABLE_CHECKING 1659 1660 /* Callback for pointer_map_traverse, asserts that the pointer map is 1661 empty. */ 1662 1663 static bool 1664 assert_is_empty (const void *key ATTRIBUTE_UNUSED, void **value, 1665 void *data ATTRIBUTE_UNUSED) 1666 { 1667 gcc_assert (!*value); 1668 return false; 1669 } 1670 #endif 1671 1672 /* Predict branch probabilities and estimate profile for basic block BB. */ 1673 1674 static void 1675 tree_estimate_probability_bb (basic_block bb) 1676 { 1677 edge e; 1678 edge_iterator ei; 1679 gimple last; 1680 1681 FOR_EACH_EDGE (e, ei, bb->succs) 1682 { 1683 /* Predict early returns to be probable, as we've already taken 1684 care for error returns and other cases are often used for 1685 fast paths through function. 1686 1687 Since we've already removed the return statements, we are 1688 looking for CFG like: 1689 1690 if (conditional) 1691 { 1692 .. 1693 goto return_block 1694 } 1695 some other blocks 1696 return_block: 1697 return_stmt. */ 1698 if (e->dest != bb->next_bb 1699 && e->dest != EXIT_BLOCK_PTR 1700 && single_succ_p (e->dest) 1701 && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR 1702 && (last = last_stmt (e->dest)) != NULL 1703 && gimple_code (last) == GIMPLE_RETURN) 1704 { 1705 edge e1; 1706 edge_iterator ei1; 1707 1708 if (single_succ_p (bb)) 1709 { 1710 FOR_EACH_EDGE (e1, ei1, bb->preds) 1711 if (!predicted_by_p (e1->src, PRED_NULL_RETURN) 1712 && !predicted_by_p (e1->src, PRED_CONST_RETURN) 1713 && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN)) 1714 predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN); 1715 } 1716 else 1717 if (!predicted_by_p (e->src, PRED_NULL_RETURN) 1718 && !predicted_by_p (e->src, PRED_CONST_RETURN) 1719 && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN)) 1720 predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN); 1721 } 1722 1723 /* Look for block we are guarding (ie we dominate it, 1724 but it doesn't postdominate us). */ 1725 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb 1726 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src) 1727 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest)) 1728 { 1729 gimple_stmt_iterator bi; 1730 1731 /* The call heuristic claims that a guarded function call 1732 is improbable. This is because such calls are often used 1733 to signal exceptional situations such as printing error 1734 messages. */ 1735 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi); 1736 gsi_next (&bi)) 1737 { 1738 gimple stmt = gsi_stmt (bi); 1739 if (is_gimple_call (stmt) 1740 /* Constant and pure calls are hardly used to signalize 1741 something exceptional. */ 1742 && gimple_has_side_effects (stmt)) 1743 { 1744 predict_edge_def (e, PRED_CALL, NOT_TAKEN); 1745 break; 1746 } 1747 } 1748 } 1749 } 1750 tree_predict_by_opcode (bb); 1751 } 1752 1753 /* Predict branch probabilities and estimate profile of the tree CFG. 1754 This function can be called from the loop optimizers to recompute 1755 the profile information. */ 1756 1757 void 1758 tree_estimate_probability (void) 1759 { 1760 basic_block bb; 1761 1762 add_noreturn_fake_exit_edges (); 1763 connect_infinite_loops_to_exit (); 1764 /* We use loop_niter_by_eval, which requires that the loops have 1765 preheaders. */ 1766 create_preheaders (CP_SIMPLE_PREHEADERS); 1767 calculate_dominance_info (CDI_POST_DOMINATORS); 1768 1769 bb_predictions = pointer_map_create (); 1770 tree_bb_level_predictions (); 1771 record_loop_exits (); 1772 1773 if (number_of_loops () > 1) 1774 predict_loops (); 1775 1776 FOR_EACH_BB (bb) 1777 tree_estimate_probability_bb (bb); 1778 1779 FOR_EACH_BB (bb) 1780 combine_predictions_for_bb (bb); 1781 1782 #ifdef ENABLE_CHECKING 1783 pointer_map_traverse (bb_predictions, assert_is_empty, NULL); 1784 #endif 1785 pointer_map_destroy (bb_predictions); 1786 bb_predictions = NULL; 1787 1788 estimate_bb_frequencies (); 1789 free_dominance_info (CDI_POST_DOMINATORS); 1790 remove_fake_exit_edges (); 1791 } 1792 1793 /* Predict branch probabilities and estimate profile of the tree CFG. 1794 This is the driver function for PASS_PROFILE. */ 1795 1796 static unsigned int 1797 tree_estimate_probability_driver (void) 1798 { 1799 unsigned nb_loops; 1800 1801 loop_optimizer_init (0); 1802 if (dump_file && (dump_flags & TDF_DETAILS)) 1803 flow_loops_dump (dump_file, NULL, 0); 1804 1805 mark_irreducible_loops (); 1806 1807 nb_loops = number_of_loops (); 1808 if (nb_loops > 1) 1809 scev_initialize (); 1810 1811 tree_estimate_probability (); 1812 1813 if (nb_loops > 1) 1814 scev_finalize (); 1815 1816 loop_optimizer_finalize (); 1817 if (dump_file && (dump_flags & TDF_DETAILS)) 1818 gimple_dump_cfg (dump_file, dump_flags); 1819 if (profile_status == PROFILE_ABSENT) 1820 profile_status = PROFILE_GUESSED; 1821 return 0; 1822 } 1823 1824 /* Predict edges to successors of CUR whose sources are not postdominated by 1825 BB by PRED and recurse to all postdominators. */ 1826 1827 static void 1828 predict_paths_for_bb (basic_block cur, basic_block bb, 1829 enum br_predictor pred, 1830 enum prediction taken, 1831 bitmap visited) 1832 { 1833 edge e; 1834 edge_iterator ei; 1835 basic_block son; 1836 1837 /* We are looking for all edges forming edge cut induced by 1838 set of all blocks postdominated by BB. */ 1839 FOR_EACH_EDGE (e, ei, cur->preds) 1840 if (e->src->index >= NUM_FIXED_BLOCKS 1841 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb)) 1842 { 1843 edge e2; 1844 edge_iterator ei2; 1845 bool found = false; 1846 1847 /* Ignore fake edges and eh, we predict them as not taken anyway. */ 1848 if (e->flags & (EDGE_EH | EDGE_FAKE)) 1849 continue; 1850 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb)); 1851 1852 /* See if there is an edge from e->src that is not abnormal 1853 and does not lead to BB. */ 1854 FOR_EACH_EDGE (e2, ei2, e->src->succs) 1855 if (e2 != e 1856 && !(e2->flags & (EDGE_EH | EDGE_FAKE)) 1857 && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)) 1858 { 1859 found = true; 1860 break; 1861 } 1862 1863 /* If there is non-abnormal path leaving e->src, predict edge 1864 using predictor. Otherwise we need to look for paths 1865 leading to e->src. 1866 1867 The second may lead to infinite loop in the case we are predicitng 1868 regions that are only reachable by abnormal edges. We simply 1869 prevent visiting given BB twice. */ 1870 if (found) 1871 predict_edge_def (e, pred, taken); 1872 else if (bitmap_set_bit (visited, e->src->index)) 1873 predict_paths_for_bb (e->src, e->src, pred, taken, visited); 1874 } 1875 for (son = first_dom_son (CDI_POST_DOMINATORS, cur); 1876 son; 1877 son = next_dom_son (CDI_POST_DOMINATORS, son)) 1878 predict_paths_for_bb (son, bb, pred, taken, visited); 1879 } 1880 1881 /* Sets branch probabilities according to PREDiction and 1882 FLAGS. */ 1883 1884 static void 1885 predict_paths_leading_to (basic_block bb, enum br_predictor pred, 1886 enum prediction taken) 1887 { 1888 bitmap visited = BITMAP_ALLOC (NULL); 1889 predict_paths_for_bb (bb, bb, pred, taken, visited); 1890 BITMAP_FREE (visited); 1891 } 1892 1893 /* Like predict_paths_leading_to but take edge instead of basic block. */ 1894 1895 static void 1896 predict_paths_leading_to_edge (edge e, enum br_predictor pred, 1897 enum prediction taken) 1898 { 1899 bool has_nonloop_edge = false; 1900 edge_iterator ei; 1901 edge e2; 1902 1903 basic_block bb = e->src; 1904 FOR_EACH_EDGE (e2, ei, bb->succs) 1905 if (e2->dest != e->src && e2->dest != e->dest 1906 && !(e->flags & (EDGE_EH | EDGE_FAKE)) 1907 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest)) 1908 { 1909 has_nonloop_edge = true; 1910 break; 1911 } 1912 if (!has_nonloop_edge) 1913 { 1914 bitmap visited = BITMAP_ALLOC (NULL); 1915 predict_paths_for_bb (bb, bb, pred, taken, visited); 1916 BITMAP_FREE (visited); 1917 } 1918 else 1919 predict_edge_def (e, pred, taken); 1920 } 1921 1922 /* This is used to carry information about basic blocks. It is 1923 attached to the AUX field of the standard CFG block. */ 1924 1925 typedef struct block_info_def 1926 { 1927 /* Estimated frequency of execution of basic_block. */ 1928 sreal frequency; 1929 1930 /* To keep queue of basic blocks to process. */ 1931 basic_block next; 1932 1933 /* Number of predecessors we need to visit first. */ 1934 int npredecessors; 1935 } *block_info; 1936 1937 /* Similar information for edges. */ 1938 typedef struct edge_info_def 1939 { 1940 /* In case edge is a loopback edge, the probability edge will be reached 1941 in case header is. Estimated number of iterations of the loop can be 1942 then computed as 1 / (1 - back_edge_prob). */ 1943 sreal back_edge_prob; 1944 /* True if the edge is a loopback edge in the natural loop. */ 1945 unsigned int back_edge:1; 1946 } *edge_info; 1947 1948 #define BLOCK_INFO(B) ((block_info) (B)->aux) 1949 #define EDGE_INFO(E) ((edge_info) (E)->aux) 1950 1951 /* Helper function for estimate_bb_frequencies. 1952 Propagate the frequencies in blocks marked in 1953 TOVISIT, starting in HEAD. */ 1954 1955 static void 1956 propagate_freq (basic_block head, bitmap tovisit) 1957 { 1958 basic_block bb; 1959 basic_block last; 1960 unsigned i; 1961 edge e; 1962 basic_block nextbb; 1963 bitmap_iterator bi; 1964 1965 /* For each basic block we need to visit count number of his predecessors 1966 we need to visit first. */ 1967 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi) 1968 { 1969 edge_iterator ei; 1970 int count = 0; 1971 1972 bb = BASIC_BLOCK (i); 1973 1974 FOR_EACH_EDGE (e, ei, bb->preds) 1975 { 1976 bool visit = bitmap_bit_p (tovisit, e->src->index); 1977 1978 if (visit && !(e->flags & EDGE_DFS_BACK)) 1979 count++; 1980 else if (visit && dump_file && !EDGE_INFO (e)->back_edge) 1981 fprintf (dump_file, 1982 "Irreducible region hit, ignoring edge to %i->%i\n", 1983 e->src->index, bb->index); 1984 } 1985 BLOCK_INFO (bb)->npredecessors = count; 1986 /* When function never returns, we will never process exit block. */ 1987 if (!count && bb == EXIT_BLOCK_PTR) 1988 bb->count = bb->frequency = 0; 1989 } 1990 1991 memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one)); 1992 last = head; 1993 for (bb = head; bb; bb = nextbb) 1994 { 1995 edge_iterator ei; 1996 sreal cyclic_probability, frequency; 1997 1998 memcpy (&cyclic_probability, &real_zero, sizeof (real_zero)); 1999 memcpy (&frequency, &real_zero, sizeof (real_zero)); 2000 2001 nextbb = BLOCK_INFO (bb)->next; 2002 BLOCK_INFO (bb)->next = NULL; 2003 2004 /* Compute frequency of basic block. */ 2005 if (bb != head) 2006 { 2007 #ifdef ENABLE_CHECKING 2008 FOR_EACH_EDGE (e, ei, bb->preds) 2009 gcc_assert (!bitmap_bit_p (tovisit, e->src->index) 2010 || (e->flags & EDGE_DFS_BACK)); 2011 #endif 2012 2013 FOR_EACH_EDGE (e, ei, bb->preds) 2014 if (EDGE_INFO (e)->back_edge) 2015 { 2016 sreal_add (&cyclic_probability, &cyclic_probability, 2017 &EDGE_INFO (e)->back_edge_prob); 2018 } 2019 else if (!(e->flags & EDGE_DFS_BACK)) 2020 { 2021 sreal tmp; 2022 2023 /* frequency += (e->probability 2024 * BLOCK_INFO (e->src)->frequency / 2025 REG_BR_PROB_BASE); */ 2026 2027 sreal_init (&tmp, e->probability, 0); 2028 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency); 2029 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base); 2030 sreal_add (&frequency, &frequency, &tmp); 2031 } 2032 2033 if (sreal_compare (&cyclic_probability, &real_zero) == 0) 2034 { 2035 memcpy (&BLOCK_INFO (bb)->frequency, &frequency, 2036 sizeof (frequency)); 2037 } 2038 else 2039 { 2040 if (sreal_compare (&cyclic_probability, &real_almost_one) > 0) 2041 { 2042 memcpy (&cyclic_probability, &real_almost_one, 2043 sizeof (real_almost_one)); 2044 } 2045 2046 /* BLOCK_INFO (bb)->frequency = frequency 2047 / (1 - cyclic_probability) */ 2048 2049 sreal_sub (&cyclic_probability, &real_one, &cyclic_probability); 2050 sreal_div (&BLOCK_INFO (bb)->frequency, 2051 &frequency, &cyclic_probability); 2052 } 2053 } 2054 2055 bitmap_clear_bit (tovisit, bb->index); 2056 2057 e = find_edge (bb, head); 2058 if (e) 2059 { 2060 sreal tmp; 2061 2062 /* EDGE_INFO (e)->back_edge_prob 2063 = ((e->probability * BLOCK_INFO (bb)->frequency) 2064 / REG_BR_PROB_BASE); */ 2065 2066 sreal_init (&tmp, e->probability, 0); 2067 sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency); 2068 sreal_mul (&EDGE_INFO (e)->back_edge_prob, 2069 &tmp, &real_inv_br_prob_base); 2070 } 2071 2072 /* Propagate to successor blocks. */ 2073 FOR_EACH_EDGE (e, ei, bb->succs) 2074 if (!(e->flags & EDGE_DFS_BACK) 2075 && BLOCK_INFO (e->dest)->npredecessors) 2076 { 2077 BLOCK_INFO (e->dest)->npredecessors--; 2078 if (!BLOCK_INFO (e->dest)->npredecessors) 2079 { 2080 if (!nextbb) 2081 nextbb = e->dest; 2082 else 2083 BLOCK_INFO (last)->next = e->dest; 2084 2085 last = e->dest; 2086 } 2087 } 2088 } 2089 } 2090 2091 /* Estimate probabilities of loopback edges in loops at same nest level. */ 2092 2093 static void 2094 estimate_loops_at_level (struct loop *first_loop) 2095 { 2096 struct loop *loop; 2097 2098 for (loop = first_loop; loop; loop = loop->next) 2099 { 2100 edge e; 2101 basic_block *bbs; 2102 unsigned i; 2103 bitmap tovisit = BITMAP_ALLOC (NULL); 2104 2105 estimate_loops_at_level (loop->inner); 2106 2107 /* Find current loop back edge and mark it. */ 2108 e = loop_latch_edge (loop); 2109 EDGE_INFO (e)->back_edge = 1; 2110 2111 bbs = get_loop_body (loop); 2112 for (i = 0; i < loop->num_nodes; i++) 2113 bitmap_set_bit (tovisit, bbs[i]->index); 2114 free (bbs); 2115 propagate_freq (loop->header, tovisit); 2116 BITMAP_FREE (tovisit); 2117 } 2118 } 2119 2120 /* Propagates frequencies through structure of loops. */ 2121 2122 static void 2123 estimate_loops (void) 2124 { 2125 bitmap tovisit = BITMAP_ALLOC (NULL); 2126 basic_block bb; 2127 2128 /* Start by estimating the frequencies in the loops. */ 2129 if (number_of_loops () > 1) 2130 estimate_loops_at_level (current_loops->tree_root->inner); 2131 2132 /* Now propagate the frequencies through all the blocks. */ 2133 FOR_ALL_BB (bb) 2134 { 2135 bitmap_set_bit (tovisit, bb->index); 2136 } 2137 propagate_freq (ENTRY_BLOCK_PTR, tovisit); 2138 BITMAP_FREE (tovisit); 2139 } 2140 2141 /* Convert counts measured by profile driven feedback to frequencies. 2142 Return nonzero iff there was any nonzero execution count. */ 2143 2144 int 2145 counts_to_freqs (void) 2146 { 2147 gcov_type count_max, true_count_max = 0; 2148 basic_block bb; 2149 2150 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 2151 true_count_max = MAX (bb->count, true_count_max); 2152 2153 count_max = MAX (true_count_max, 1); 2154 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 2155 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max; 2156 2157 return true_count_max; 2158 } 2159 2160 /* Return true if function is likely to be expensive, so there is no point to 2161 optimize performance of prologue, epilogue or do inlining at the expense 2162 of code size growth. THRESHOLD is the limit of number of instructions 2163 function can execute at average to be still considered not expensive. */ 2164 2165 bool 2166 expensive_function_p (int threshold) 2167 { 2168 unsigned int sum = 0; 2169 basic_block bb; 2170 unsigned int limit; 2171 2172 /* We can not compute accurately for large thresholds due to scaled 2173 frequencies. */ 2174 gcc_assert (threshold <= BB_FREQ_MAX); 2175 2176 /* Frequencies are out of range. This either means that function contains 2177 internal loop executing more than BB_FREQ_MAX times or profile feedback 2178 is available and function has not been executed at all. */ 2179 if (ENTRY_BLOCK_PTR->frequency == 0) 2180 return true; 2181 2182 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */ 2183 limit = ENTRY_BLOCK_PTR->frequency * threshold; 2184 FOR_EACH_BB (bb) 2185 { 2186 rtx insn; 2187 2188 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 2189 insn = NEXT_INSN (insn)) 2190 if (active_insn_p (insn)) 2191 { 2192 sum += bb->frequency; 2193 if (sum > limit) 2194 return true; 2195 } 2196 } 2197 2198 return false; 2199 } 2200 2201 /* Estimate basic blocks frequency by given branch probabilities. */ 2202 2203 void 2204 estimate_bb_frequencies (void) 2205 { 2206 basic_block bb; 2207 sreal freq_max; 2208 2209 if (profile_status != PROFILE_READ || !counts_to_freqs ()) 2210 { 2211 static int real_values_initialized = 0; 2212 2213 if (!real_values_initialized) 2214 { 2215 real_values_initialized = 1; 2216 sreal_init (&real_zero, 0, 0); 2217 sreal_init (&real_one, 1, 0); 2218 sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0); 2219 sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0); 2220 sreal_init (&real_one_half, 1, -1); 2221 sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base); 2222 sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base); 2223 } 2224 2225 mark_dfs_back_edges (); 2226 2227 single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE; 2228 2229 /* Set up block info for each basic block. */ 2230 alloc_aux_for_blocks (sizeof (struct block_info_def)); 2231 alloc_aux_for_edges (sizeof (struct edge_info_def)); 2232 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 2233 { 2234 edge e; 2235 edge_iterator ei; 2236 2237 FOR_EACH_EDGE (e, ei, bb->succs) 2238 { 2239 sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0); 2240 sreal_mul (&EDGE_INFO (e)->back_edge_prob, 2241 &EDGE_INFO (e)->back_edge_prob, 2242 &real_inv_br_prob_base); 2243 } 2244 } 2245 2246 /* First compute probabilities locally for each loop from innermost 2247 to outermost to examine probabilities for back edges. */ 2248 estimate_loops (); 2249 2250 memcpy (&freq_max, &real_zero, sizeof (real_zero)); 2251 FOR_EACH_BB (bb) 2252 if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0) 2253 memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max)); 2254 2255 sreal_div (&freq_max, &real_bb_freq_max, &freq_max); 2256 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 2257 { 2258 sreal tmp; 2259 2260 sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max); 2261 sreal_add (&tmp, &tmp, &real_one_half); 2262 bb->frequency = sreal_to_int (&tmp); 2263 } 2264 2265 free_aux_for_blocks (); 2266 free_aux_for_edges (); 2267 } 2268 compute_function_frequency (); 2269 } 2270 2271 /* Decide whether function is hot, cold or unlikely executed. */ 2272 void 2273 compute_function_frequency (void) 2274 { 2275 basic_block bb; 2276 struct cgraph_node *node = cgraph_get_node (current_function_decl); 2277 if (DECL_STATIC_CONSTRUCTOR (current_function_decl) 2278 || MAIN_NAME_P (DECL_NAME (current_function_decl))) 2279 node->only_called_at_startup = true; 2280 if (DECL_STATIC_DESTRUCTOR (current_function_decl)) 2281 node->only_called_at_exit = true; 2282 2283 if (!profile_info || !flag_branch_probabilities) 2284 { 2285 int flags = flags_from_decl_or_type (current_function_decl); 2286 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)) 2287 != NULL) 2288 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED; 2289 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl)) 2290 != NULL) 2291 node->frequency = NODE_FREQUENCY_HOT; 2292 else if (flags & ECF_NORETURN) 2293 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE; 2294 else if (MAIN_NAME_P (DECL_NAME (current_function_decl))) 2295 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE; 2296 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl) 2297 || DECL_STATIC_DESTRUCTOR (current_function_decl)) 2298 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE; 2299 return; 2300 } 2301 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED; 2302 FOR_EACH_BB (bb) 2303 { 2304 if (maybe_hot_bb_p (bb)) 2305 { 2306 node->frequency = NODE_FREQUENCY_HOT; 2307 return; 2308 } 2309 if (!probably_never_executed_bb_p (bb)) 2310 node->frequency = NODE_FREQUENCY_NORMAL; 2311 } 2312 } 2313 2314 static bool 2315 gate_estimate_probability (void) 2316 { 2317 return flag_guess_branch_prob; 2318 } 2319 2320 /* Build PREDICT_EXPR. */ 2321 tree 2322 build_predict_expr (enum br_predictor predictor, enum prediction taken) 2323 { 2324 tree t = build1 (PREDICT_EXPR, void_type_node, 2325 build_int_cst (integer_type_node, predictor)); 2326 SET_PREDICT_EXPR_OUTCOME (t, taken); 2327 return t; 2328 } 2329 2330 const char * 2331 predictor_name (enum br_predictor predictor) 2332 { 2333 return predictor_info[predictor].name; 2334 } 2335 2336 struct gimple_opt_pass pass_profile = 2337 { 2338 { 2339 GIMPLE_PASS, 2340 "profile_estimate", /* name */ 2341 gate_estimate_probability, /* gate */ 2342 tree_estimate_probability_driver, /* execute */ 2343 NULL, /* sub */ 2344 NULL, /* next */ 2345 0, /* static_pass_number */ 2346 TV_BRANCH_PROB, /* tv_id */ 2347 PROP_cfg, /* properties_required */ 2348 0, /* properties_provided */ 2349 0, /* properties_destroyed */ 2350 0, /* todo_flags_start */ 2351 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ 2352 } 2353 }; 2354 2355 struct gimple_opt_pass pass_strip_predict_hints = 2356 { 2357 { 2358 GIMPLE_PASS, 2359 "*strip_predict_hints", /* name */ 2360 NULL, /* gate */ 2361 strip_predict_hints, /* execute */ 2362 NULL, /* sub */ 2363 NULL, /* next */ 2364 0, /* static_pass_number */ 2365 TV_BRANCH_PROB, /* tv_id */ 2366 PROP_cfg, /* properties_required */ 2367 0, /* properties_provided */ 2368 0, /* properties_destroyed */ 2369 0, /* todo_flags_start */ 2370 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ 2371 } 2372 }; 2373 2374 /* Rebuild function frequencies. Passes are in general expected to 2375 maintain profile by hand, however in some cases this is not possible: 2376 for example when inlining several functions with loops freuqencies might run 2377 out of scale and thus needs to be recomputed. */ 2378 2379 void 2380 rebuild_frequencies (void) 2381 { 2382 timevar_push (TV_REBUILD_FREQUENCIES); 2383 if (profile_status == PROFILE_GUESSED) 2384 { 2385 loop_optimizer_init (0); 2386 add_noreturn_fake_exit_edges (); 2387 mark_irreducible_loops (); 2388 connect_infinite_loops_to_exit (); 2389 estimate_bb_frequencies (); 2390 remove_fake_exit_edges (); 2391 loop_optimizer_finalize (); 2392 } 2393 else if (profile_status == PROFILE_READ) 2394 counts_to_freqs (); 2395 else 2396 gcc_unreachable (); 2397 timevar_pop (TV_REBUILD_FREQUENCIES); 2398 } 2399