1 /* Branch prediction routines for the GNU compiler. 2 Copyright (C) 2000-2016 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free 8 Software Foundation; either version 3, or (at your option) any later 9 version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12 WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 /* References: 21 22 [1] "Branch Prediction for Free" 23 Ball and Larus; PLDI '93. 24 [2] "Static Branch Frequency and Program Profile Analysis" 25 Wu and Larus; MICRO-27. 26 [3] "Corpus-based Static Branch Prediction" 27 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */ 28 29 30 #include "config.h" 31 #include "system.h" 32 #include "coretypes.h" 33 #include "backend.h" 34 #include "rtl.h" 35 #include "tree.h" 36 #include "gimple.h" 37 #include "cfghooks.h" 38 #include "tree-pass.h" 39 #include "ssa.h" 40 #include "emit-rtl.h" 41 #include "cgraph.h" 42 #include "coverage.h" 43 #include "diagnostic-core.h" 44 #include "gimple-predict.h" 45 #include "fold-const.h" 46 #include "calls.h" 47 #include "cfganal.h" 48 #include "profile.h" 49 #include "sreal.h" 50 #include "params.h" 51 #include "cfgloop.h" 52 #include "gimple-iterator.h" 53 #include "tree-cfg.h" 54 #include "tree-ssa-loop-niter.h" 55 #include "tree-ssa-loop.h" 56 #include "tree-scalar-evolution.h" 57 58 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE, 59 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */ 60 static sreal real_almost_one, real_br_prob_base, 61 real_inv_br_prob_base, real_one_half, real_bb_freq_max; 62 63 static void combine_predictions_for_insn (rtx_insn *, basic_block); 64 static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int); 65 static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction); 66 static void predict_paths_leading_to_edge (edge, enum br_predictor, enum prediction); 67 static bool can_predict_insn_p (const rtx_insn *); 68 69 /* Information we hold about each branch predictor. 70 Filled using information from predict.def. */ 71 72 struct predictor_info 73 { 74 const char *const name; /* Name used in the debugging dumps. */ 75 const int hitrate; /* Expected hitrate used by 76 predict_insn_def call. */ 77 const int flags; 78 }; 79 80 /* Use given predictor without Dempster-Shaffer theory if it matches 81 using first_match heuristics. */ 82 #define PRED_FLAG_FIRST_MATCH 1 83 84 /* Recompute hitrate in percent to our representation. */ 85 86 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100) 87 88 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS}, 89 static const struct predictor_info predictor_info[]= { 90 #include "predict.def" 91 92 /* Upper bound on predictors. */ 93 {NULL, 0, 0} 94 }; 95 #undef DEF_PREDICTOR 96 97 /* Return TRUE if frequency FREQ is considered to be hot. */ 98 99 static inline bool 100 maybe_hot_frequency_p (struct function *fun, int freq) 101 { 102 struct cgraph_node *node = cgraph_node::get (fun->decl); 103 if (!profile_info 104 || !opt_for_fn (fun->decl, flag_branch_probabilities)) 105 { 106 if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED) 107 return false; 108 if (node->frequency == NODE_FREQUENCY_HOT) 109 return true; 110 } 111 if (profile_status_for_fn (fun) == PROFILE_ABSENT) 112 return true; 113 if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE 114 && freq < (ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency * 2 / 3)) 115 return false; 116 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION) == 0) 117 return false; 118 if (freq < (ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency 119 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))) 120 return false; 121 return true; 122 } 123 124 static gcov_type min_count = -1; 125 126 /* Determine the threshold for hot BB counts. */ 127 128 gcov_type 129 get_hot_bb_threshold () 130 { 131 gcov_working_set_t *ws; 132 if (min_count == -1) 133 { 134 ws = find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE)); 135 gcc_assert (ws); 136 min_count = ws->min_counter; 137 } 138 return min_count; 139 } 140 141 /* Set the threshold for hot BB counts. */ 142 143 void 144 set_hot_bb_threshold (gcov_type min) 145 { 146 min_count = min; 147 } 148 149 /* Return TRUE if frequency FREQ is considered to be hot. */ 150 151 bool 152 maybe_hot_count_p (struct function *fun, gcov_type count) 153 { 154 if (fun && profile_status_for_fn (fun) != PROFILE_READ) 155 return true; 156 /* Code executed at most once is not hot. */ 157 if (profile_info->runs >= count) 158 return false; 159 return (count >= get_hot_bb_threshold ()); 160 } 161 162 /* Return true in case BB can be CPU intensive and should be optimized 163 for maximal performance. */ 164 165 bool 166 maybe_hot_bb_p (struct function *fun, const_basic_block bb) 167 { 168 gcc_checking_assert (fun); 169 if (profile_status_for_fn (fun) == PROFILE_READ) 170 return maybe_hot_count_p (fun, bb->count); 171 return maybe_hot_frequency_p (fun, bb->frequency); 172 } 173 174 /* Return true in case BB can be CPU intensive and should be optimized 175 for maximal performance. */ 176 177 bool 178 maybe_hot_edge_p (edge e) 179 { 180 if (profile_status_for_fn (cfun) == PROFILE_READ) 181 return maybe_hot_count_p (cfun, e->count); 182 return maybe_hot_frequency_p (cfun, EDGE_FREQUENCY (e)); 183 } 184 185 /* Return true if profile COUNT and FREQUENCY, or function FUN static 186 node frequency reflects never being executed. */ 187 188 static bool 189 probably_never_executed (struct function *fun, 190 gcov_type count, int frequency) 191 { 192 gcc_checking_assert (fun); 193 if (profile_status_for_fn (fun) == PROFILE_READ) 194 { 195 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION); 196 if (count * unlikely_count_fraction >= profile_info->runs) 197 return false; 198 if (!frequency) 199 return true; 200 if (!ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency) 201 return false; 202 if (ENTRY_BLOCK_PTR_FOR_FN (fun)->count) 203 { 204 gcov_type computed_count; 205 /* Check for possibility of overflow, in which case entry bb count 206 is large enough to do the division first without losing much 207 precision. */ 208 if (ENTRY_BLOCK_PTR_FOR_FN (fun)->count < REG_BR_PROB_BASE * 209 REG_BR_PROB_BASE) 210 { 211 gcov_type scaled_count 212 = frequency * ENTRY_BLOCK_PTR_FOR_FN (fun)->count * 213 unlikely_count_fraction; 214 computed_count = RDIV (scaled_count, 215 ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency); 216 } 217 else 218 { 219 computed_count = RDIV (ENTRY_BLOCK_PTR_FOR_FN (fun)->count, 220 ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency); 221 computed_count *= frequency * unlikely_count_fraction; 222 } 223 if (computed_count >= profile_info->runs) 224 return false; 225 } 226 return true; 227 } 228 if ((!profile_info || !(opt_for_fn (fun->decl, flag_branch_probabilities))) 229 && (cgraph_node::get (fun->decl)->frequency 230 == NODE_FREQUENCY_UNLIKELY_EXECUTED)) 231 return true; 232 return false; 233 } 234 235 236 /* Return true in case BB is probably never executed. */ 237 238 bool 239 probably_never_executed_bb_p (struct function *fun, const_basic_block bb) 240 { 241 return probably_never_executed (fun, bb->count, bb->frequency); 242 } 243 244 245 /* Return true in case edge E is probably never executed. */ 246 247 bool 248 probably_never_executed_edge_p (struct function *fun, edge e) 249 { 250 return probably_never_executed (fun, e->count, EDGE_FREQUENCY (e)); 251 } 252 253 /* Return true when current function should always be optimized for size. */ 254 255 bool 256 optimize_function_for_size_p (struct function *fun) 257 { 258 if (!fun || !fun->decl) 259 return optimize_size; 260 cgraph_node *n = cgraph_node::get (fun->decl); 261 return n && n->optimize_for_size_p (); 262 } 263 264 /* Return true when current function should always be optimized for speed. */ 265 266 bool 267 optimize_function_for_speed_p (struct function *fun) 268 { 269 return !optimize_function_for_size_p (fun); 270 } 271 272 /* Return the optimization type that should be used for the function FUN. */ 273 274 optimization_type 275 function_optimization_type (struct function *fun) 276 { 277 return (optimize_function_for_speed_p (fun) 278 ? OPTIMIZE_FOR_SPEED 279 : OPTIMIZE_FOR_SIZE); 280 } 281 282 /* Return TRUE when BB should be optimized for size. */ 283 284 bool 285 optimize_bb_for_size_p (const_basic_block bb) 286 { 287 return (optimize_function_for_size_p (cfun) 288 || (bb && !maybe_hot_bb_p (cfun, bb))); 289 } 290 291 /* Return TRUE when BB should be optimized for speed. */ 292 293 bool 294 optimize_bb_for_speed_p (const_basic_block bb) 295 { 296 return !optimize_bb_for_size_p (bb); 297 } 298 299 /* Return the optimization type that should be used for block BB. */ 300 301 optimization_type 302 bb_optimization_type (const_basic_block bb) 303 { 304 return (optimize_bb_for_speed_p (bb) 305 ? OPTIMIZE_FOR_SPEED 306 : OPTIMIZE_FOR_SIZE); 307 } 308 309 /* Return TRUE when BB should be optimized for size. */ 310 311 bool 312 optimize_edge_for_size_p (edge e) 313 { 314 return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e); 315 } 316 317 /* Return TRUE when BB should be optimized for speed. */ 318 319 bool 320 optimize_edge_for_speed_p (edge e) 321 { 322 return !optimize_edge_for_size_p (e); 323 } 324 325 /* Return TRUE when BB should be optimized for size. */ 326 327 bool 328 optimize_insn_for_size_p (void) 329 { 330 return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p; 331 } 332 333 /* Return TRUE when BB should be optimized for speed. */ 334 335 bool 336 optimize_insn_for_speed_p (void) 337 { 338 return !optimize_insn_for_size_p (); 339 } 340 341 /* Return TRUE when LOOP should be optimized for size. */ 342 343 bool 344 optimize_loop_for_size_p (struct loop *loop) 345 { 346 return optimize_bb_for_size_p (loop->header); 347 } 348 349 /* Return TRUE when LOOP should be optimized for speed. */ 350 351 bool 352 optimize_loop_for_speed_p (struct loop *loop) 353 { 354 return optimize_bb_for_speed_p (loop->header); 355 } 356 357 /* Return TRUE when LOOP nest should be optimized for speed. */ 358 359 bool 360 optimize_loop_nest_for_speed_p (struct loop *loop) 361 { 362 struct loop *l = loop; 363 if (optimize_loop_for_speed_p (loop)) 364 return true; 365 l = loop->inner; 366 while (l && l != loop) 367 { 368 if (optimize_loop_for_speed_p (l)) 369 return true; 370 if (l->inner) 371 l = l->inner; 372 else if (l->next) 373 l = l->next; 374 else 375 { 376 while (l != loop && !l->next) 377 l = loop_outer (l); 378 if (l != loop) 379 l = l->next; 380 } 381 } 382 return false; 383 } 384 385 /* Return TRUE when LOOP nest should be optimized for size. */ 386 387 bool 388 optimize_loop_nest_for_size_p (struct loop *loop) 389 { 390 return !optimize_loop_nest_for_speed_p (loop); 391 } 392 393 /* Return true when edge E is likely to be well predictable by branch 394 predictor. */ 395 396 bool 397 predictable_edge_p (edge e) 398 { 399 if (profile_status_for_fn (cfun) == PROFILE_ABSENT) 400 return false; 401 if ((e->probability 402 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100) 403 || (REG_BR_PROB_BASE - e->probability 404 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)) 405 return true; 406 return false; 407 } 408 409 410 /* Set RTL expansion for BB profile. */ 411 412 void 413 rtl_profile_for_bb (basic_block bb) 414 { 415 crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb); 416 } 417 418 /* Set RTL expansion for edge profile. */ 419 420 void 421 rtl_profile_for_edge (edge e) 422 { 423 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e); 424 } 425 426 /* Set RTL expansion to default mode (i.e. when profile info is not known). */ 427 void 428 default_rtl_profile (void) 429 { 430 crtl->maybe_hot_insn_p = true; 431 } 432 433 /* Return true if the one of outgoing edges is already predicted by 434 PREDICTOR. */ 435 436 bool 437 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor) 438 { 439 rtx note; 440 if (!INSN_P (BB_END (bb))) 441 return false; 442 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1)) 443 if (REG_NOTE_KIND (note) == REG_BR_PRED 444 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor) 445 return true; 446 return false; 447 } 448 449 /* Structure representing predictions in tree level. */ 450 451 struct edge_prediction { 452 struct edge_prediction *ep_next; 453 edge ep_edge; 454 enum br_predictor ep_predictor; 455 int ep_probability; 456 }; 457 458 /* This map contains for a basic block the list of predictions for the 459 outgoing edges. */ 460 461 static hash_map<const_basic_block, edge_prediction *> *bb_predictions; 462 463 /* Return true if the one of outgoing edges is already predicted by 464 PREDICTOR. */ 465 466 bool 467 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor) 468 { 469 struct edge_prediction *i; 470 edge_prediction **preds = bb_predictions->get (bb); 471 472 if (!preds) 473 return false; 474 475 for (i = *preds; i; i = i->ep_next) 476 if (i->ep_predictor == predictor) 477 return true; 478 return false; 479 } 480 481 /* Return true when the probability of edge is reliable. 482 483 The profile guessing code is good at predicting branch outcome (ie. 484 taken/not taken), that is predicted right slightly over 75% of time. 485 It is however notoriously poor on predicting the probability itself. 486 In general the profile appear a lot flatter (with probabilities closer 487 to 50%) than the reality so it is bad idea to use it to drive optimization 488 such as those disabling dynamic branch prediction for well predictable 489 branches. 490 491 There are two exceptions - edges leading to noreturn edges and edges 492 predicted by number of iterations heuristics are predicted well. This macro 493 should be able to distinguish those, but at the moment it simply check for 494 noreturn heuristic that is only one giving probability over 99% or bellow 495 1%. In future we might want to propagate reliability information across the 496 CFG if we find this information useful on multiple places. */ 497 static bool 498 probability_reliable_p (int prob) 499 { 500 return (profile_status_for_fn (cfun) == PROFILE_READ 501 || (profile_status_for_fn (cfun) == PROFILE_GUESSED 502 && (prob <= HITRATE (1) || prob >= HITRATE (99)))); 503 } 504 505 /* Same predicate as above, working on edges. */ 506 bool 507 edge_probability_reliable_p (const_edge e) 508 { 509 return probability_reliable_p (e->probability); 510 } 511 512 /* Same predicate as edge_probability_reliable_p, working on notes. */ 513 bool 514 br_prob_note_reliable_p (const_rtx note) 515 { 516 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB); 517 return probability_reliable_p (XINT (note, 0)); 518 } 519 520 static void 521 predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability) 522 { 523 gcc_assert (any_condjump_p (insn)); 524 if (!flag_guess_branch_prob) 525 return; 526 527 add_reg_note (insn, REG_BR_PRED, 528 gen_rtx_CONCAT (VOIDmode, 529 GEN_INT ((int) predictor), 530 GEN_INT ((int) probability))); 531 } 532 533 /* Predict insn by given predictor. */ 534 535 void 536 predict_insn_def (rtx_insn *insn, enum br_predictor predictor, 537 enum prediction taken) 538 { 539 int probability = predictor_info[(int) predictor].hitrate; 540 541 if (taken != TAKEN) 542 probability = REG_BR_PROB_BASE - probability; 543 544 predict_insn (insn, predictor, probability); 545 } 546 547 /* Predict edge E with given probability if possible. */ 548 549 void 550 rtl_predict_edge (edge e, enum br_predictor predictor, int probability) 551 { 552 rtx_insn *last_insn; 553 last_insn = BB_END (e->src); 554 555 /* We can store the branch prediction information only about 556 conditional jumps. */ 557 if (!any_condjump_p (last_insn)) 558 return; 559 560 /* We always store probability of branching. */ 561 if (e->flags & EDGE_FALLTHRU) 562 probability = REG_BR_PROB_BASE - probability; 563 564 predict_insn (last_insn, predictor, probability); 565 } 566 567 /* Predict edge E with the given PROBABILITY. */ 568 void 569 gimple_predict_edge (edge e, enum br_predictor predictor, int probability) 570 { 571 gcc_assert (profile_status_for_fn (cfun) != PROFILE_GUESSED); 572 if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) && EDGE_COUNT (e->src->succs) > 573 1) 574 && flag_guess_branch_prob && optimize) 575 { 576 struct edge_prediction *i = XNEW (struct edge_prediction); 577 edge_prediction *&preds = bb_predictions->get_or_insert (e->src); 578 579 i->ep_next = preds; 580 preds = i; 581 i->ep_probability = probability; 582 i->ep_predictor = predictor; 583 i->ep_edge = e; 584 } 585 } 586 587 /* Remove all predictions on given basic block that are attached 588 to edge E. */ 589 void 590 remove_predictions_associated_with_edge (edge e) 591 { 592 if (!bb_predictions) 593 return; 594 595 edge_prediction **preds = bb_predictions->get (e->src); 596 597 if (preds) 598 { 599 struct edge_prediction **prediction = preds; 600 struct edge_prediction *next; 601 602 while (*prediction) 603 { 604 if ((*prediction)->ep_edge == e) 605 { 606 next = (*prediction)->ep_next; 607 free (*prediction); 608 *prediction = next; 609 } 610 else 611 prediction = &((*prediction)->ep_next); 612 } 613 } 614 } 615 616 /* Clears the list of predictions stored for BB. */ 617 618 static void 619 clear_bb_predictions (basic_block bb) 620 { 621 edge_prediction **preds = bb_predictions->get (bb); 622 struct edge_prediction *pred, *next; 623 624 if (!preds) 625 return; 626 627 for (pred = *preds; pred; pred = next) 628 { 629 next = pred->ep_next; 630 free (pred); 631 } 632 *preds = NULL; 633 } 634 635 /* Return true when we can store prediction on insn INSN. 636 At the moment we represent predictions only on conditional 637 jumps, not at computed jump or other complicated cases. */ 638 static bool 639 can_predict_insn_p (const rtx_insn *insn) 640 { 641 return (JUMP_P (insn) 642 && any_condjump_p (insn) 643 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2); 644 } 645 646 /* Predict edge E by given predictor if possible. */ 647 648 void 649 predict_edge_def (edge e, enum br_predictor predictor, 650 enum prediction taken) 651 { 652 int probability = predictor_info[(int) predictor].hitrate; 653 654 if (taken != TAKEN) 655 probability = REG_BR_PROB_BASE - probability; 656 657 predict_edge (e, predictor, probability); 658 } 659 660 /* Invert all branch predictions or probability notes in the INSN. This needs 661 to be done each time we invert the condition used by the jump. */ 662 663 void 664 invert_br_probabilities (rtx insn) 665 { 666 rtx note; 667 668 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 669 if (REG_NOTE_KIND (note) == REG_BR_PROB) 670 XINT (note, 0) = REG_BR_PROB_BASE - XINT (note, 0); 671 else if (REG_NOTE_KIND (note) == REG_BR_PRED) 672 XEXP (XEXP (note, 0), 1) 673 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1))); 674 } 675 676 /* Dump information about the branch prediction to the output file. */ 677 678 static void 679 dump_prediction (FILE *file, enum br_predictor predictor, int probability, 680 basic_block bb, int used) 681 { 682 edge e; 683 edge_iterator ei; 684 685 if (!file) 686 return; 687 688 FOR_EACH_EDGE (e, ei, bb->succs) 689 if (! (e->flags & EDGE_FALLTHRU)) 690 break; 691 692 fprintf (file, " %s heuristics%s: %.1f%%", 693 predictor_info[predictor].name, 694 used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE); 695 696 if (bb->count) 697 { 698 fprintf (file, " exec %" PRId64, bb->count); 699 if (e) 700 { 701 fprintf (file, " hit %" PRId64, e->count); 702 fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count); 703 } 704 } 705 706 fprintf (file, "\n"); 707 } 708 709 /* We can not predict the probabilities of outgoing edges of bb. Set them 710 evenly and hope for the best. */ 711 static void 712 set_even_probabilities (basic_block bb) 713 { 714 int nedges = 0; 715 edge e; 716 edge_iterator ei; 717 718 FOR_EACH_EDGE (e, ei, bb->succs) 719 if (!(e->flags & (EDGE_EH | EDGE_FAKE))) 720 nedges ++; 721 FOR_EACH_EDGE (e, ei, bb->succs) 722 if (!(e->flags & (EDGE_EH | EDGE_FAKE))) 723 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges; 724 else 725 e->probability = 0; 726 } 727 728 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB 729 note if not already present. Remove now useless REG_BR_PRED notes. */ 730 731 static void 732 combine_predictions_for_insn (rtx_insn *insn, basic_block bb) 733 { 734 rtx prob_note; 735 rtx *pnote; 736 rtx note; 737 int best_probability = PROB_EVEN; 738 enum br_predictor best_predictor = END_PREDICTORS; 739 int combined_probability = REG_BR_PROB_BASE / 2; 740 int d; 741 bool first_match = false; 742 bool found = false; 743 744 if (!can_predict_insn_p (insn)) 745 { 746 set_even_probabilities (bb); 747 return; 748 } 749 750 prob_note = find_reg_note (insn, REG_BR_PROB, 0); 751 pnote = ®_NOTES (insn); 752 if (dump_file) 753 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn), 754 bb->index); 755 756 /* We implement "first match" heuristics and use probability guessed 757 by predictor with smallest index. */ 758 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 759 if (REG_NOTE_KIND (note) == REG_BR_PRED) 760 { 761 enum br_predictor predictor = ((enum br_predictor) 762 INTVAL (XEXP (XEXP (note, 0), 0))); 763 int probability = INTVAL (XEXP (XEXP (note, 0), 1)); 764 765 found = true; 766 if (best_predictor > predictor) 767 best_probability = probability, best_predictor = predictor; 768 769 d = (combined_probability * probability 770 + (REG_BR_PROB_BASE - combined_probability) 771 * (REG_BR_PROB_BASE - probability)); 772 773 /* Use FP math to avoid overflows of 32bit integers. */ 774 if (d == 0) 775 /* If one probability is 0% and one 100%, avoid division by zero. */ 776 combined_probability = REG_BR_PROB_BASE / 2; 777 else 778 combined_probability = (((double) combined_probability) * probability 779 * REG_BR_PROB_BASE / d + 0.5); 780 } 781 782 /* Decide which heuristic to use. In case we didn't match anything, 783 use no_prediction heuristic, in case we did match, use either 784 first match or Dempster-Shaffer theory depending on the flags. */ 785 786 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH) 787 first_match = true; 788 789 if (!found) 790 dump_prediction (dump_file, PRED_NO_PREDICTION, 791 combined_probability, bb, true); 792 else 793 { 794 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, 795 bb, !first_match); 796 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, 797 bb, first_match); 798 } 799 800 if (first_match) 801 combined_probability = best_probability; 802 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true); 803 804 while (*pnote) 805 { 806 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED) 807 { 808 enum br_predictor predictor = ((enum br_predictor) 809 INTVAL (XEXP (XEXP (*pnote, 0), 0))); 810 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1)); 811 812 dump_prediction (dump_file, predictor, probability, bb, 813 !first_match || best_predictor == predictor); 814 *pnote = XEXP (*pnote, 1); 815 } 816 else 817 pnote = &XEXP (*pnote, 1); 818 } 819 820 if (!prob_note) 821 { 822 add_int_reg_note (insn, REG_BR_PROB, combined_probability); 823 824 /* Save the prediction into CFG in case we are seeing non-degenerated 825 conditional jump. */ 826 if (!single_succ_p (bb)) 827 { 828 BRANCH_EDGE (bb)->probability = combined_probability; 829 FALLTHRU_EDGE (bb)->probability 830 = REG_BR_PROB_BASE - combined_probability; 831 } 832 } 833 else if (!single_succ_p (bb)) 834 { 835 int prob = XINT (prob_note, 0); 836 837 BRANCH_EDGE (bb)->probability = prob; 838 FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob; 839 } 840 else 841 single_succ_edge (bb)->probability = REG_BR_PROB_BASE; 842 } 843 844 /* Combine predictions into single probability and store them into CFG. 845 Remove now useless prediction entries. */ 846 847 static void 848 combine_predictions_for_bb (basic_block bb) 849 { 850 int best_probability = PROB_EVEN; 851 enum br_predictor best_predictor = END_PREDICTORS; 852 int combined_probability = REG_BR_PROB_BASE / 2; 853 int d; 854 bool first_match = false; 855 bool found = false; 856 struct edge_prediction *pred; 857 int nedges = 0; 858 edge e, first = NULL, second = NULL; 859 edge_iterator ei; 860 861 FOR_EACH_EDGE (e, ei, bb->succs) 862 if (!(e->flags & (EDGE_EH | EDGE_FAKE))) 863 { 864 nedges ++; 865 if (first && !second) 866 second = e; 867 if (!first) 868 first = e; 869 } 870 871 /* When there is no successor or only one choice, prediction is easy. 872 873 We are lazy for now and predict only basic blocks with two outgoing 874 edges. It is possible to predict generic case too, but we have to 875 ignore first match heuristics and do more involved combining. Implement 876 this later. */ 877 if (nedges != 2) 878 { 879 if (!bb->count) 880 set_even_probabilities (bb); 881 clear_bb_predictions (bb); 882 if (dump_file) 883 fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n", 884 nedges, bb->index); 885 return; 886 } 887 888 if (dump_file) 889 fprintf (dump_file, "Predictions for bb %i\n", bb->index); 890 891 edge_prediction **preds = bb_predictions->get (bb); 892 if (preds) 893 { 894 /* We implement "first match" heuristics and use probability guessed 895 by predictor with smallest index. */ 896 for (pred = *preds; pred; pred = pred->ep_next) 897 { 898 enum br_predictor predictor = pred->ep_predictor; 899 int probability = pred->ep_probability; 900 901 if (pred->ep_edge != first) 902 probability = REG_BR_PROB_BASE - probability; 903 904 found = true; 905 /* First match heuristics would be widly confused if we predicted 906 both directions. */ 907 if (best_predictor > predictor) 908 { 909 struct edge_prediction *pred2; 910 int prob = probability; 911 912 for (pred2 = (struct edge_prediction *) *preds; 913 pred2; pred2 = pred2->ep_next) 914 if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor) 915 { 916 int probability2 = pred->ep_probability; 917 918 if (pred2->ep_edge != first) 919 probability2 = REG_BR_PROB_BASE - probability2; 920 921 if ((probability < REG_BR_PROB_BASE / 2) != 922 (probability2 < REG_BR_PROB_BASE / 2)) 923 break; 924 925 /* If the same predictor later gave better result, go for it! */ 926 if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability)) 927 || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability))) 928 prob = probability2; 929 } 930 if (!pred2) 931 best_probability = prob, best_predictor = predictor; 932 } 933 934 d = (combined_probability * probability 935 + (REG_BR_PROB_BASE - combined_probability) 936 * (REG_BR_PROB_BASE - probability)); 937 938 /* Use FP math to avoid overflows of 32bit integers. */ 939 if (d == 0) 940 /* If one probability is 0% and one 100%, avoid division by zero. */ 941 combined_probability = REG_BR_PROB_BASE / 2; 942 else 943 combined_probability = (((double) combined_probability) 944 * probability 945 * REG_BR_PROB_BASE / d + 0.5); 946 } 947 } 948 949 /* Decide which heuristic to use. In case we didn't match anything, 950 use no_prediction heuristic, in case we did match, use either 951 first match or Dempster-Shaffer theory depending on the flags. */ 952 953 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH) 954 first_match = true; 955 956 if (!found) 957 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true); 958 else 959 { 960 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb, 961 !first_match); 962 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb, 963 first_match); 964 } 965 966 if (first_match) 967 combined_probability = best_probability; 968 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true); 969 970 if (preds) 971 { 972 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next) 973 { 974 enum br_predictor predictor = pred->ep_predictor; 975 int probability = pred->ep_probability; 976 977 if (pred->ep_edge != EDGE_SUCC (bb, 0)) 978 probability = REG_BR_PROB_BASE - probability; 979 dump_prediction (dump_file, predictor, probability, bb, 980 !first_match || best_predictor == predictor); 981 } 982 } 983 clear_bb_predictions (bb); 984 985 if (!bb->count) 986 { 987 first->probability = combined_probability; 988 second->probability = REG_BR_PROB_BASE - combined_probability; 989 } 990 } 991 992 /* Check if T1 and T2 satisfy the IV_COMPARE condition. 993 Return the SSA_NAME if the condition satisfies, NULL otherwise. 994 995 T1 and T2 should be one of the following cases: 996 1. T1 is SSA_NAME, T2 is NULL 997 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4] 998 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */ 999 1000 static tree 1001 strips_small_constant (tree t1, tree t2) 1002 { 1003 tree ret = NULL; 1004 int value = 0; 1005 1006 if (!t1) 1007 return NULL; 1008 else if (TREE_CODE (t1) == SSA_NAME) 1009 ret = t1; 1010 else if (tree_fits_shwi_p (t1)) 1011 value = tree_to_shwi (t1); 1012 else 1013 return NULL; 1014 1015 if (!t2) 1016 return ret; 1017 else if (tree_fits_shwi_p (t2)) 1018 value = tree_to_shwi (t2); 1019 else if (TREE_CODE (t2) == SSA_NAME) 1020 { 1021 if (ret) 1022 return NULL; 1023 else 1024 ret = t2; 1025 } 1026 1027 if (value <= 4 && value >= -4) 1028 return ret; 1029 else 1030 return NULL; 1031 } 1032 1033 /* Return the SSA_NAME in T or T's operands. 1034 Return NULL if SSA_NAME cannot be found. */ 1035 1036 static tree 1037 get_base_value (tree t) 1038 { 1039 if (TREE_CODE (t) == SSA_NAME) 1040 return t; 1041 1042 if (!BINARY_CLASS_P (t)) 1043 return NULL; 1044 1045 switch (TREE_OPERAND_LENGTH (t)) 1046 { 1047 case 1: 1048 return strips_small_constant (TREE_OPERAND (t, 0), NULL); 1049 case 2: 1050 return strips_small_constant (TREE_OPERAND (t, 0), 1051 TREE_OPERAND (t, 1)); 1052 default: 1053 return NULL; 1054 } 1055 } 1056 1057 /* Check the compare STMT in LOOP. If it compares an induction 1058 variable to a loop invariant, return true, and save 1059 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP. 1060 Otherwise return false and set LOOP_INVAIANT to NULL. */ 1061 1062 static bool 1063 is_comparison_with_loop_invariant_p (gcond *stmt, struct loop *loop, 1064 tree *loop_invariant, 1065 enum tree_code *compare_code, 1066 tree *loop_step, 1067 tree *loop_iv_base) 1068 { 1069 tree op0, op1, bound, base; 1070 affine_iv iv0, iv1; 1071 enum tree_code code; 1072 tree step; 1073 1074 code = gimple_cond_code (stmt); 1075 *loop_invariant = NULL; 1076 1077 switch (code) 1078 { 1079 case GT_EXPR: 1080 case GE_EXPR: 1081 case NE_EXPR: 1082 case LT_EXPR: 1083 case LE_EXPR: 1084 case EQ_EXPR: 1085 break; 1086 1087 default: 1088 return false; 1089 } 1090 1091 op0 = gimple_cond_lhs (stmt); 1092 op1 = gimple_cond_rhs (stmt); 1093 1094 if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST) 1095 || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST)) 1096 return false; 1097 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true)) 1098 return false; 1099 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true)) 1100 return false; 1101 if (TREE_CODE (iv0.step) != INTEGER_CST 1102 || TREE_CODE (iv1.step) != INTEGER_CST) 1103 return false; 1104 if ((integer_zerop (iv0.step) && integer_zerop (iv1.step)) 1105 || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step))) 1106 return false; 1107 1108 if (integer_zerop (iv0.step)) 1109 { 1110 if (code != NE_EXPR && code != EQ_EXPR) 1111 code = invert_tree_comparison (code, false); 1112 bound = iv0.base; 1113 base = iv1.base; 1114 if (tree_fits_shwi_p (iv1.step)) 1115 step = iv1.step; 1116 else 1117 return false; 1118 } 1119 else 1120 { 1121 bound = iv1.base; 1122 base = iv0.base; 1123 if (tree_fits_shwi_p (iv0.step)) 1124 step = iv0.step; 1125 else 1126 return false; 1127 } 1128 1129 if (TREE_CODE (bound) != INTEGER_CST) 1130 bound = get_base_value (bound); 1131 if (!bound) 1132 return false; 1133 if (TREE_CODE (base) != INTEGER_CST) 1134 base = get_base_value (base); 1135 if (!base) 1136 return false; 1137 1138 *loop_invariant = bound; 1139 *compare_code = code; 1140 *loop_step = step; 1141 *loop_iv_base = base; 1142 return true; 1143 } 1144 1145 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */ 1146 1147 static bool 1148 expr_coherent_p (tree t1, tree t2) 1149 { 1150 gimple *stmt; 1151 tree ssa_name_1 = NULL; 1152 tree ssa_name_2 = NULL; 1153 1154 gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST); 1155 gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST); 1156 1157 if (t1 == t2) 1158 return true; 1159 1160 if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST) 1161 return true; 1162 if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST) 1163 return false; 1164 1165 /* Check to see if t1 is expressed/defined with t2. */ 1166 stmt = SSA_NAME_DEF_STMT (t1); 1167 gcc_assert (stmt != NULL); 1168 if (is_gimple_assign (stmt)) 1169 { 1170 ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE); 1171 if (ssa_name_1 && ssa_name_1 == t2) 1172 return true; 1173 } 1174 1175 /* Check to see if t2 is expressed/defined with t1. */ 1176 stmt = SSA_NAME_DEF_STMT (t2); 1177 gcc_assert (stmt != NULL); 1178 if (is_gimple_assign (stmt)) 1179 { 1180 ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE); 1181 if (ssa_name_2 && ssa_name_2 == t1) 1182 return true; 1183 } 1184 1185 /* Compare if t1 and t2's def_stmts are identical. */ 1186 if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2) 1187 return true; 1188 else 1189 return false; 1190 } 1191 1192 /* Predict branch probability of BB when BB contains a branch that compares 1193 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The 1194 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP. 1195 1196 E.g. 1197 for (int i = 0; i < bound; i++) { 1198 if (i < bound - 2) 1199 computation_1(); 1200 else 1201 computation_2(); 1202 } 1203 1204 In this loop, we will predict the branch inside the loop to be taken. */ 1205 1206 static void 1207 predict_iv_comparison (struct loop *loop, basic_block bb, 1208 tree loop_bound_var, 1209 tree loop_iv_base_var, 1210 enum tree_code loop_bound_code, 1211 int loop_bound_step) 1212 { 1213 gimple *stmt; 1214 tree compare_var, compare_base; 1215 enum tree_code compare_code; 1216 tree compare_step_var; 1217 edge then_edge; 1218 edge_iterator ei; 1219 1220 if (predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED) 1221 || predicted_by_p (bb, PRED_LOOP_ITERATIONS) 1222 || predicted_by_p (bb, PRED_LOOP_EXIT)) 1223 return; 1224 1225 stmt = last_stmt (bb); 1226 if (!stmt || gimple_code (stmt) != GIMPLE_COND) 1227 return; 1228 if (!is_comparison_with_loop_invariant_p (as_a <gcond *> (stmt), 1229 loop, &compare_var, 1230 &compare_code, 1231 &compare_step_var, 1232 &compare_base)) 1233 return; 1234 1235 /* Find the taken edge. */ 1236 FOR_EACH_EDGE (then_edge, ei, bb->succs) 1237 if (then_edge->flags & EDGE_TRUE_VALUE) 1238 break; 1239 1240 /* When comparing an IV to a loop invariant, NE is more likely to be 1241 taken while EQ is more likely to be not-taken. */ 1242 if (compare_code == NE_EXPR) 1243 { 1244 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN); 1245 return; 1246 } 1247 else if (compare_code == EQ_EXPR) 1248 { 1249 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN); 1250 return; 1251 } 1252 1253 if (!expr_coherent_p (loop_iv_base_var, compare_base)) 1254 return; 1255 1256 /* If loop bound, base and compare bound are all constants, we can 1257 calculate the probability directly. */ 1258 if (tree_fits_shwi_p (loop_bound_var) 1259 && tree_fits_shwi_p (compare_var) 1260 && tree_fits_shwi_p (compare_base)) 1261 { 1262 int probability; 1263 bool overflow, overall_overflow = false; 1264 widest_int compare_count, tem; 1265 1266 /* (loop_bound - base) / compare_step */ 1267 tem = wi::sub (wi::to_widest (loop_bound_var), 1268 wi::to_widest (compare_base), SIGNED, &overflow); 1269 overall_overflow |= overflow; 1270 widest_int loop_count = wi::div_trunc (tem, 1271 wi::to_widest (compare_step_var), 1272 SIGNED, &overflow); 1273 overall_overflow |= overflow; 1274 1275 if (!wi::neg_p (wi::to_widest (compare_step_var)) 1276 ^ (compare_code == LT_EXPR || compare_code == LE_EXPR)) 1277 { 1278 /* (loop_bound - compare_bound) / compare_step */ 1279 tem = wi::sub (wi::to_widest (loop_bound_var), 1280 wi::to_widest (compare_var), SIGNED, &overflow); 1281 overall_overflow |= overflow; 1282 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var), 1283 SIGNED, &overflow); 1284 overall_overflow |= overflow; 1285 } 1286 else 1287 { 1288 /* (compare_bound - base) / compare_step */ 1289 tem = wi::sub (wi::to_widest (compare_var), 1290 wi::to_widest (compare_base), SIGNED, &overflow); 1291 overall_overflow |= overflow; 1292 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var), 1293 SIGNED, &overflow); 1294 overall_overflow |= overflow; 1295 } 1296 if (compare_code == LE_EXPR || compare_code == GE_EXPR) 1297 ++compare_count; 1298 if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR) 1299 ++loop_count; 1300 if (wi::neg_p (compare_count)) 1301 compare_count = 0; 1302 if (wi::neg_p (loop_count)) 1303 loop_count = 0; 1304 if (loop_count == 0) 1305 probability = 0; 1306 else if (wi::cmps (compare_count, loop_count) == 1) 1307 probability = REG_BR_PROB_BASE; 1308 else 1309 { 1310 tem = compare_count * REG_BR_PROB_BASE; 1311 tem = wi::udiv_trunc (tem, loop_count); 1312 probability = tem.to_uhwi (); 1313 } 1314 1315 if (!overall_overflow) 1316 predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability); 1317 1318 return; 1319 } 1320 1321 if (expr_coherent_p (loop_bound_var, compare_var)) 1322 { 1323 if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR) 1324 && (compare_code == LT_EXPR || compare_code == LE_EXPR)) 1325 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN); 1326 else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR) 1327 && (compare_code == GT_EXPR || compare_code == GE_EXPR)) 1328 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN); 1329 else if (loop_bound_code == NE_EXPR) 1330 { 1331 /* If the loop backedge condition is "(i != bound)", we do 1332 the comparison based on the step of IV: 1333 * step < 0 : backedge condition is like (i > bound) 1334 * step > 0 : backedge condition is like (i < bound) */ 1335 gcc_assert (loop_bound_step != 0); 1336 if (loop_bound_step > 0 1337 && (compare_code == LT_EXPR 1338 || compare_code == LE_EXPR)) 1339 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN); 1340 else if (loop_bound_step < 0 1341 && (compare_code == GT_EXPR 1342 || compare_code == GE_EXPR)) 1343 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN); 1344 else 1345 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN); 1346 } 1347 else 1348 /* The branch is predicted not-taken if loop_bound_code is 1349 opposite with compare_code. */ 1350 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN); 1351 } 1352 else if (expr_coherent_p (loop_iv_base_var, compare_var)) 1353 { 1354 /* For cases like: 1355 for (i = s; i < h; i++) 1356 if (i > s + 2) .... 1357 The branch should be predicted taken. */ 1358 if (loop_bound_step > 0 1359 && (compare_code == GT_EXPR || compare_code == GE_EXPR)) 1360 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN); 1361 else if (loop_bound_step < 0 1362 && (compare_code == LT_EXPR || compare_code == LE_EXPR)) 1363 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN); 1364 else 1365 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN); 1366 } 1367 } 1368 1369 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop 1370 exits are resulted from short-circuit conditions that will generate an 1371 if_tmp. E.g.: 1372 1373 if (foo() || global > 10) 1374 break; 1375 1376 This will be translated into: 1377 1378 BB3: 1379 loop header... 1380 BB4: 1381 if foo() goto BB6 else goto BB5 1382 BB5: 1383 if global > 10 goto BB6 else goto BB7 1384 BB6: 1385 goto BB7 1386 BB7: 1387 iftmp = (PHI 0(BB5), 1(BB6)) 1388 if iftmp == 1 goto BB8 else goto BB3 1389 BB8: 1390 outside of the loop... 1391 1392 The edge BB7->BB8 is loop exit because BB8 is outside of the loop. 1393 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop 1394 exits. This function takes BB7->BB8 as input, and finds out the extra loop 1395 exits to predict them using PRED_LOOP_EXIT. */ 1396 1397 static void 1398 predict_extra_loop_exits (edge exit_edge) 1399 { 1400 unsigned i; 1401 bool check_value_one; 1402 gimple *lhs_def_stmt; 1403 gphi *phi_stmt; 1404 tree cmp_rhs, cmp_lhs; 1405 gimple *last; 1406 gcond *cmp_stmt; 1407 1408 last = last_stmt (exit_edge->src); 1409 if (!last) 1410 return; 1411 cmp_stmt = dyn_cast <gcond *> (last); 1412 if (!cmp_stmt) 1413 return; 1414 1415 cmp_rhs = gimple_cond_rhs (cmp_stmt); 1416 cmp_lhs = gimple_cond_lhs (cmp_stmt); 1417 if (!TREE_CONSTANT (cmp_rhs) 1418 || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs))) 1419 return; 1420 if (TREE_CODE (cmp_lhs) != SSA_NAME) 1421 return; 1422 1423 /* If check_value_one is true, only the phi_args with value '1' will lead 1424 to loop exit. Otherwise, only the phi_args with value '0' will lead to 1425 loop exit. */ 1426 check_value_one = (((integer_onep (cmp_rhs)) 1427 ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR)) 1428 ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0)); 1429 1430 lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs); 1431 if (!lhs_def_stmt) 1432 return; 1433 1434 phi_stmt = dyn_cast <gphi *> (lhs_def_stmt); 1435 if (!phi_stmt) 1436 return; 1437 1438 for (i = 0; i < gimple_phi_num_args (phi_stmt); i++) 1439 { 1440 edge e1; 1441 edge_iterator ei; 1442 tree val = gimple_phi_arg_def (phi_stmt, i); 1443 edge e = gimple_phi_arg_edge (phi_stmt, i); 1444 1445 if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val))) 1446 continue; 1447 if ((check_value_one ^ integer_onep (val)) == 1) 1448 continue; 1449 if (EDGE_COUNT (e->src->succs) != 1) 1450 { 1451 predict_paths_leading_to_edge (e, PRED_LOOP_EXIT, NOT_TAKEN); 1452 continue; 1453 } 1454 1455 FOR_EACH_EDGE (e1, ei, e->src->preds) 1456 predict_paths_leading_to_edge (e1, PRED_LOOP_EXIT, NOT_TAKEN); 1457 } 1458 } 1459 1460 /* Predict edge probabilities by exploiting loop structure. */ 1461 1462 static void 1463 predict_loops (void) 1464 { 1465 struct loop *loop; 1466 1467 /* Try to predict out blocks in a loop that are not part of a 1468 natural loop. */ 1469 FOR_EACH_LOOP (loop, 0) 1470 { 1471 basic_block bb, *bbs; 1472 unsigned j, n_exits; 1473 vec<edge> exits; 1474 struct tree_niter_desc niter_desc; 1475 edge ex; 1476 struct nb_iter_bound *nb_iter; 1477 enum tree_code loop_bound_code = ERROR_MARK; 1478 tree loop_bound_step = NULL; 1479 tree loop_bound_var = NULL; 1480 tree loop_iv_base = NULL; 1481 gcond *stmt = NULL; 1482 1483 exits = get_loop_exit_edges (loop); 1484 n_exits = exits.length (); 1485 if (!n_exits) 1486 { 1487 exits.release (); 1488 continue; 1489 } 1490 1491 FOR_EACH_VEC_ELT (exits, j, ex) 1492 { 1493 tree niter = NULL; 1494 HOST_WIDE_INT nitercst; 1495 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS); 1496 int probability; 1497 enum br_predictor predictor; 1498 1499 predict_extra_loop_exits (ex); 1500 1501 if (number_of_iterations_exit (loop, ex, &niter_desc, false, false)) 1502 niter = niter_desc.niter; 1503 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST) 1504 niter = loop_niter_by_eval (loop, ex); 1505 1506 if (TREE_CODE (niter) == INTEGER_CST) 1507 { 1508 if (tree_fits_uhwi_p (niter) 1509 && max 1510 && compare_tree_int (niter, max - 1) == -1) 1511 nitercst = tree_to_uhwi (niter) + 1; 1512 else 1513 nitercst = max; 1514 predictor = PRED_LOOP_ITERATIONS; 1515 } 1516 /* If we have just one exit and we can derive some information about 1517 the number of iterations of the loop from the statements inside 1518 the loop, use it to predict this exit. */ 1519 else if (n_exits == 1) 1520 { 1521 nitercst = estimated_stmt_executions_int (loop); 1522 if (nitercst < 0) 1523 continue; 1524 if (nitercst > max) 1525 nitercst = max; 1526 1527 predictor = PRED_LOOP_ITERATIONS_GUESSED; 1528 } 1529 else 1530 continue; 1531 1532 /* If the prediction for number of iterations is zero, do not 1533 predict the exit edges. */ 1534 if (nitercst == 0) 1535 continue; 1536 1537 probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst); 1538 predict_edge (ex, predictor, probability); 1539 } 1540 exits.release (); 1541 1542 /* Find information about loop bound variables. */ 1543 for (nb_iter = loop->bounds; nb_iter; 1544 nb_iter = nb_iter->next) 1545 if (nb_iter->stmt 1546 && gimple_code (nb_iter->stmt) == GIMPLE_COND) 1547 { 1548 stmt = as_a <gcond *> (nb_iter->stmt); 1549 break; 1550 } 1551 if (!stmt && last_stmt (loop->header) 1552 && gimple_code (last_stmt (loop->header)) == GIMPLE_COND) 1553 stmt = as_a <gcond *> (last_stmt (loop->header)); 1554 if (stmt) 1555 is_comparison_with_loop_invariant_p (stmt, loop, 1556 &loop_bound_var, 1557 &loop_bound_code, 1558 &loop_bound_step, 1559 &loop_iv_base); 1560 1561 bbs = get_loop_body (loop); 1562 1563 for (j = 0; j < loop->num_nodes; j++) 1564 { 1565 int header_found = 0; 1566 edge e; 1567 edge_iterator ei; 1568 1569 bb = bbs[j]; 1570 1571 /* Bypass loop heuristics on continue statement. These 1572 statements construct loops via "non-loop" constructs 1573 in the source language and are better to be handled 1574 separately. */ 1575 if (predicted_by_p (bb, PRED_CONTINUE)) 1576 continue; 1577 1578 /* Loop branch heuristics - predict an edge back to a 1579 loop's head as taken. */ 1580 if (bb == loop->latch) 1581 { 1582 e = find_edge (loop->latch, loop->header); 1583 if (e) 1584 { 1585 header_found = 1; 1586 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN); 1587 } 1588 } 1589 1590 /* Loop exit heuristics - predict an edge exiting the loop if the 1591 conditional has no loop header successors as not taken. */ 1592 if (!header_found 1593 /* If we already used more reliable loop exit predictors, do not 1594 bother with PRED_LOOP_EXIT. */ 1595 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED) 1596 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS)) 1597 { 1598 /* For loop with many exits we don't want to predict all exits 1599 with the pretty large probability, because if all exits are 1600 considered in row, the loop would be predicted to iterate 1601 almost never. The code to divide probability by number of 1602 exits is very rough. It should compute the number of exits 1603 taken in each patch through function (not the overall number 1604 of exits that might be a lot higher for loops with wide switch 1605 statements in them) and compute n-th square root. 1606 1607 We limit the minimal probability by 2% to avoid 1608 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction 1609 as this was causing regression in perl benchmark containing such 1610 a wide loop. */ 1611 1612 int probability = ((REG_BR_PROB_BASE 1613 - predictor_info [(int) PRED_LOOP_EXIT].hitrate) 1614 / n_exits); 1615 if (probability < HITRATE (2)) 1616 probability = HITRATE (2); 1617 FOR_EACH_EDGE (e, ei, bb->succs) 1618 if (e->dest->index < NUM_FIXED_BLOCKS 1619 || !flow_bb_inside_loop_p (loop, e->dest)) 1620 predict_edge (e, PRED_LOOP_EXIT, probability); 1621 } 1622 if (loop_bound_var) 1623 predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base, 1624 loop_bound_code, 1625 tree_to_shwi (loop_bound_step)); 1626 } 1627 1628 /* Free basic blocks from get_loop_body. */ 1629 free (bbs); 1630 } 1631 } 1632 1633 /* Attempt to predict probabilities of BB outgoing edges using local 1634 properties. */ 1635 static void 1636 bb_estimate_probability_locally (basic_block bb) 1637 { 1638 rtx_insn *last_insn = BB_END (bb); 1639 rtx cond; 1640 1641 if (! can_predict_insn_p (last_insn)) 1642 return; 1643 cond = get_condition (last_insn, NULL, false, false); 1644 if (! cond) 1645 return; 1646 1647 /* Try "pointer heuristic." 1648 A comparison ptr == 0 is predicted as false. 1649 Similarly, a comparison ptr1 == ptr2 is predicted as false. */ 1650 if (COMPARISON_P (cond) 1651 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0))) 1652 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1))))) 1653 { 1654 if (GET_CODE (cond) == EQ) 1655 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN); 1656 else if (GET_CODE (cond) == NE) 1657 predict_insn_def (last_insn, PRED_POINTER, TAKEN); 1658 } 1659 else 1660 1661 /* Try "opcode heuristic." 1662 EQ tests are usually false and NE tests are usually true. Also, 1663 most quantities are positive, so we can make the appropriate guesses 1664 about signed comparisons against zero. */ 1665 switch (GET_CODE (cond)) 1666 { 1667 case CONST_INT: 1668 /* Unconditional branch. */ 1669 predict_insn_def (last_insn, PRED_UNCONDITIONAL, 1670 cond == const0_rtx ? NOT_TAKEN : TAKEN); 1671 break; 1672 1673 case EQ: 1674 case UNEQ: 1675 /* Floating point comparisons appears to behave in a very 1676 unpredictable way because of special role of = tests in 1677 FP code. */ 1678 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) 1679 ; 1680 /* Comparisons with 0 are often used for booleans and there is 1681 nothing useful to predict about them. */ 1682 else if (XEXP (cond, 1) == const0_rtx 1683 || XEXP (cond, 0) == const0_rtx) 1684 ; 1685 else 1686 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN); 1687 break; 1688 1689 case NE: 1690 case LTGT: 1691 /* Floating point comparisons appears to behave in a very 1692 unpredictable way because of special role of = tests in 1693 FP code. */ 1694 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) 1695 ; 1696 /* Comparisons with 0 are often used for booleans and there is 1697 nothing useful to predict about them. */ 1698 else if (XEXP (cond, 1) == const0_rtx 1699 || XEXP (cond, 0) == const0_rtx) 1700 ; 1701 else 1702 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN); 1703 break; 1704 1705 case ORDERED: 1706 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN); 1707 break; 1708 1709 case UNORDERED: 1710 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN); 1711 break; 1712 1713 case LE: 1714 case LT: 1715 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx 1716 || XEXP (cond, 1) == constm1_rtx) 1717 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN); 1718 break; 1719 1720 case GE: 1721 case GT: 1722 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx 1723 || XEXP (cond, 1) == constm1_rtx) 1724 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN); 1725 break; 1726 1727 default: 1728 break; 1729 } 1730 } 1731 1732 /* Set edge->probability for each successor edge of BB. */ 1733 void 1734 guess_outgoing_edge_probabilities (basic_block bb) 1735 { 1736 bb_estimate_probability_locally (bb); 1737 combine_predictions_for_insn (BB_END (bb), bb); 1738 } 1739 1740 static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor); 1741 1742 /* Helper function for expr_expected_value. */ 1743 1744 static tree 1745 expr_expected_value_1 (tree type, tree op0, enum tree_code code, 1746 tree op1, bitmap visited, enum br_predictor *predictor) 1747 { 1748 gimple *def; 1749 1750 if (predictor) 1751 *predictor = PRED_UNCONDITIONAL; 1752 1753 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) 1754 { 1755 if (TREE_CONSTANT (op0)) 1756 return op0; 1757 1758 if (code != SSA_NAME) 1759 return NULL_TREE; 1760 1761 def = SSA_NAME_DEF_STMT (op0); 1762 1763 /* If we were already here, break the infinite cycle. */ 1764 if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0))) 1765 return NULL; 1766 1767 if (gimple_code (def) == GIMPLE_PHI) 1768 { 1769 /* All the arguments of the PHI node must have the same constant 1770 length. */ 1771 int i, n = gimple_phi_num_args (def); 1772 tree val = NULL, new_val; 1773 1774 for (i = 0; i < n; i++) 1775 { 1776 tree arg = PHI_ARG_DEF (def, i); 1777 enum br_predictor predictor2; 1778 1779 /* If this PHI has itself as an argument, we cannot 1780 determine the string length of this argument. However, 1781 if we can find an expected constant value for the other 1782 PHI args then we can still be sure that this is 1783 likely a constant. So be optimistic and just 1784 continue with the next argument. */ 1785 if (arg == PHI_RESULT (def)) 1786 continue; 1787 1788 new_val = expr_expected_value (arg, visited, &predictor2); 1789 1790 /* It is difficult to combine value predictors. Simply assume 1791 that later predictor is weaker and take its prediction. */ 1792 if (predictor && *predictor < predictor2) 1793 *predictor = predictor2; 1794 if (!new_val) 1795 return NULL; 1796 if (!val) 1797 val = new_val; 1798 else if (!operand_equal_p (val, new_val, false)) 1799 return NULL; 1800 } 1801 return val; 1802 } 1803 if (is_gimple_assign (def)) 1804 { 1805 if (gimple_assign_lhs (def) != op0) 1806 return NULL; 1807 1808 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)), 1809 gimple_assign_rhs1 (def), 1810 gimple_assign_rhs_code (def), 1811 gimple_assign_rhs2 (def), 1812 visited, predictor); 1813 } 1814 1815 if (is_gimple_call (def)) 1816 { 1817 tree decl = gimple_call_fndecl (def); 1818 if (!decl) 1819 { 1820 if (gimple_call_internal_p (def) 1821 && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT) 1822 { 1823 gcc_assert (gimple_call_num_args (def) == 3); 1824 tree val = gimple_call_arg (def, 0); 1825 if (TREE_CONSTANT (val)) 1826 return val; 1827 if (predictor) 1828 { 1829 tree val2 = gimple_call_arg (def, 2); 1830 gcc_assert (TREE_CODE (val2) == INTEGER_CST 1831 && tree_fits_uhwi_p (val2) 1832 && tree_to_uhwi (val2) < END_PREDICTORS); 1833 *predictor = (enum br_predictor) tree_to_uhwi (val2); 1834 } 1835 return gimple_call_arg (def, 1); 1836 } 1837 return NULL; 1838 } 1839 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL) 1840 switch (DECL_FUNCTION_CODE (decl)) 1841 { 1842 case BUILT_IN_EXPECT: 1843 { 1844 tree val; 1845 if (gimple_call_num_args (def) != 2) 1846 return NULL; 1847 val = gimple_call_arg (def, 0); 1848 if (TREE_CONSTANT (val)) 1849 return val; 1850 if (predictor) 1851 *predictor = PRED_BUILTIN_EXPECT; 1852 return gimple_call_arg (def, 1); 1853 } 1854 1855 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N: 1856 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1: 1857 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2: 1858 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4: 1859 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8: 1860 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16: 1861 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE: 1862 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N: 1863 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1: 1864 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2: 1865 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4: 1866 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8: 1867 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16: 1868 /* Assume that any given atomic operation has low contention, 1869 and thus the compare-and-swap operation succeeds. */ 1870 if (predictor) 1871 *predictor = PRED_COMPARE_AND_SWAP; 1872 return boolean_true_node; 1873 default: 1874 break; 1875 } 1876 } 1877 1878 return NULL; 1879 } 1880 1881 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS) 1882 { 1883 tree res; 1884 enum br_predictor predictor2; 1885 op0 = expr_expected_value (op0, visited, predictor); 1886 if (!op0) 1887 return NULL; 1888 op1 = expr_expected_value (op1, visited, &predictor2); 1889 if (predictor && *predictor < predictor2) 1890 *predictor = predictor2; 1891 if (!op1) 1892 return NULL; 1893 res = fold_build2 (code, type, op0, op1); 1894 if (TREE_CONSTANT (res)) 1895 return res; 1896 return NULL; 1897 } 1898 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS) 1899 { 1900 tree res; 1901 op0 = expr_expected_value (op0, visited, predictor); 1902 if (!op0) 1903 return NULL; 1904 res = fold_build1 (code, type, op0); 1905 if (TREE_CONSTANT (res)) 1906 return res; 1907 return NULL; 1908 } 1909 return NULL; 1910 } 1911 1912 /* Return constant EXPR will likely have at execution time, NULL if unknown. 1913 The function is used by builtin_expect branch predictor so the evidence 1914 must come from this construct and additional possible constant folding. 1915 1916 We may want to implement more involved value guess (such as value range 1917 propagation based prediction), but such tricks shall go to new 1918 implementation. */ 1919 1920 static tree 1921 expr_expected_value (tree expr, bitmap visited, 1922 enum br_predictor *predictor) 1923 { 1924 enum tree_code code; 1925 tree op0, op1; 1926 1927 if (TREE_CONSTANT (expr)) 1928 { 1929 if (predictor) 1930 *predictor = PRED_UNCONDITIONAL; 1931 return expr; 1932 } 1933 1934 extract_ops_from_tree (expr, &code, &op0, &op1); 1935 return expr_expected_value_1 (TREE_TYPE (expr), 1936 op0, code, op1, visited, predictor); 1937 } 1938 1939 /* Predict using opcode of the last statement in basic block. */ 1940 static void 1941 tree_predict_by_opcode (basic_block bb) 1942 { 1943 gimple *stmt = last_stmt (bb); 1944 edge then_edge; 1945 tree op0, op1; 1946 tree type; 1947 tree val; 1948 enum tree_code cmp; 1949 bitmap visited; 1950 edge_iterator ei; 1951 enum br_predictor predictor; 1952 1953 if (!stmt || gimple_code (stmt) != GIMPLE_COND) 1954 return; 1955 FOR_EACH_EDGE (then_edge, ei, bb->succs) 1956 if (then_edge->flags & EDGE_TRUE_VALUE) 1957 break; 1958 op0 = gimple_cond_lhs (stmt); 1959 op1 = gimple_cond_rhs (stmt); 1960 cmp = gimple_cond_code (stmt); 1961 type = TREE_TYPE (op0); 1962 visited = BITMAP_ALLOC (NULL); 1963 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited, 1964 &predictor); 1965 BITMAP_FREE (visited); 1966 if (val && TREE_CODE (val) == INTEGER_CST) 1967 { 1968 if (predictor == PRED_BUILTIN_EXPECT) 1969 { 1970 int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY); 1971 1972 gcc_assert (percent >= 0 && percent <= 100); 1973 if (integer_zerop (val)) 1974 percent = 100 - percent; 1975 predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent)); 1976 } 1977 else 1978 predict_edge (then_edge, predictor, 1979 integer_zerop (val) ? NOT_TAKEN : TAKEN); 1980 } 1981 /* Try "pointer heuristic." 1982 A comparison ptr == 0 is predicted as false. 1983 Similarly, a comparison ptr1 == ptr2 is predicted as false. */ 1984 if (POINTER_TYPE_P (type)) 1985 { 1986 if (cmp == EQ_EXPR) 1987 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN); 1988 else if (cmp == NE_EXPR) 1989 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN); 1990 } 1991 else 1992 1993 /* Try "opcode heuristic." 1994 EQ tests are usually false and NE tests are usually true. Also, 1995 most quantities are positive, so we can make the appropriate guesses 1996 about signed comparisons against zero. */ 1997 switch (cmp) 1998 { 1999 case EQ_EXPR: 2000 case UNEQ_EXPR: 2001 /* Floating point comparisons appears to behave in a very 2002 unpredictable way because of special role of = tests in 2003 FP code. */ 2004 if (FLOAT_TYPE_P (type)) 2005 ; 2006 /* Comparisons with 0 are often used for booleans and there is 2007 nothing useful to predict about them. */ 2008 else if (integer_zerop (op0) || integer_zerop (op1)) 2009 ; 2010 else 2011 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN); 2012 break; 2013 2014 case NE_EXPR: 2015 case LTGT_EXPR: 2016 /* Floating point comparisons appears to behave in a very 2017 unpredictable way because of special role of = tests in 2018 FP code. */ 2019 if (FLOAT_TYPE_P (type)) 2020 ; 2021 /* Comparisons with 0 are often used for booleans and there is 2022 nothing useful to predict about them. */ 2023 else if (integer_zerop (op0) 2024 || integer_zerop (op1)) 2025 ; 2026 else 2027 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN); 2028 break; 2029 2030 case ORDERED_EXPR: 2031 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN); 2032 break; 2033 2034 case UNORDERED_EXPR: 2035 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN); 2036 break; 2037 2038 case LE_EXPR: 2039 case LT_EXPR: 2040 if (integer_zerop (op1) 2041 || integer_onep (op1) 2042 || integer_all_onesp (op1) 2043 || real_zerop (op1) 2044 || real_onep (op1) 2045 || real_minus_onep (op1)) 2046 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN); 2047 break; 2048 2049 case GE_EXPR: 2050 case GT_EXPR: 2051 if (integer_zerop (op1) 2052 || integer_onep (op1) 2053 || integer_all_onesp (op1) 2054 || real_zerop (op1) 2055 || real_onep (op1) 2056 || real_minus_onep (op1)) 2057 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN); 2058 break; 2059 2060 default: 2061 break; 2062 } 2063 } 2064 2065 /* Try to guess whether the value of return means error code. */ 2066 2067 static enum br_predictor 2068 return_prediction (tree val, enum prediction *prediction) 2069 { 2070 /* VOID. */ 2071 if (!val) 2072 return PRED_NO_PREDICTION; 2073 /* Different heuristics for pointers and scalars. */ 2074 if (POINTER_TYPE_P (TREE_TYPE (val))) 2075 { 2076 /* NULL is usually not returned. */ 2077 if (integer_zerop (val)) 2078 { 2079 *prediction = NOT_TAKEN; 2080 return PRED_NULL_RETURN; 2081 } 2082 } 2083 else if (INTEGRAL_TYPE_P (TREE_TYPE (val))) 2084 { 2085 /* Negative return values are often used to indicate 2086 errors. */ 2087 if (TREE_CODE (val) == INTEGER_CST 2088 && tree_int_cst_sgn (val) < 0) 2089 { 2090 *prediction = NOT_TAKEN; 2091 return PRED_NEGATIVE_RETURN; 2092 } 2093 /* Constant return values seems to be commonly taken. 2094 Zero/one often represent booleans so exclude them from the 2095 heuristics. */ 2096 if (TREE_CONSTANT (val) 2097 && (!integer_zerop (val) && !integer_onep (val))) 2098 { 2099 *prediction = TAKEN; 2100 return PRED_CONST_RETURN; 2101 } 2102 } 2103 return PRED_NO_PREDICTION; 2104 } 2105 2106 /* Find the basic block with return expression and look up for possible 2107 return value trying to apply RETURN_PREDICTION heuristics. */ 2108 static void 2109 apply_return_prediction (void) 2110 { 2111 greturn *return_stmt = NULL; 2112 tree return_val; 2113 edge e; 2114 gphi *phi; 2115 int phi_num_args, i; 2116 enum br_predictor pred; 2117 enum prediction direction; 2118 edge_iterator ei; 2119 2120 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds) 2121 { 2122 gimple *last = last_stmt (e->src); 2123 if (last 2124 && gimple_code (last) == GIMPLE_RETURN) 2125 { 2126 return_stmt = as_a <greturn *> (last); 2127 break; 2128 } 2129 } 2130 if (!e) 2131 return; 2132 return_val = gimple_return_retval (return_stmt); 2133 if (!return_val) 2134 return; 2135 if (TREE_CODE (return_val) != SSA_NAME 2136 || !SSA_NAME_DEF_STMT (return_val) 2137 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI) 2138 return; 2139 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val)); 2140 phi_num_args = gimple_phi_num_args (phi); 2141 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction); 2142 2143 /* Avoid the degenerate case where all return values form the function 2144 belongs to same category (ie they are all positive constants) 2145 so we can hardly say something about them. */ 2146 for (i = 1; i < phi_num_args; i++) 2147 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction)) 2148 break; 2149 if (i != phi_num_args) 2150 for (i = 0; i < phi_num_args; i++) 2151 { 2152 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction); 2153 if (pred != PRED_NO_PREDICTION) 2154 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred, 2155 direction); 2156 } 2157 } 2158 2159 /* Look for basic block that contains unlikely to happen events 2160 (such as noreturn calls) and mark all paths leading to execution 2161 of this basic blocks as unlikely. */ 2162 2163 static void 2164 tree_bb_level_predictions (void) 2165 { 2166 basic_block bb; 2167 bool has_return_edges = false; 2168 edge e; 2169 edge_iterator ei; 2170 2171 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds) 2172 if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH))) 2173 { 2174 has_return_edges = true; 2175 break; 2176 } 2177 2178 apply_return_prediction (); 2179 2180 FOR_EACH_BB_FN (bb, cfun) 2181 { 2182 gimple_stmt_iterator gsi; 2183 2184 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2185 { 2186 gimple *stmt = gsi_stmt (gsi); 2187 tree decl; 2188 2189 if (is_gimple_call (stmt)) 2190 { 2191 if ((gimple_call_flags (stmt) & ECF_NORETURN) 2192 && has_return_edges) 2193 predict_paths_leading_to (bb, PRED_NORETURN, 2194 NOT_TAKEN); 2195 decl = gimple_call_fndecl (stmt); 2196 if (decl 2197 && lookup_attribute ("cold", 2198 DECL_ATTRIBUTES (decl))) 2199 predict_paths_leading_to (bb, PRED_COLD_FUNCTION, 2200 NOT_TAKEN); 2201 } 2202 else if (gimple_code (stmt) == GIMPLE_PREDICT) 2203 { 2204 predict_paths_leading_to (bb, gimple_predict_predictor (stmt), 2205 gimple_predict_outcome (stmt)); 2206 /* Keep GIMPLE_PREDICT around so early inlining will propagate 2207 hints to callers. */ 2208 } 2209 } 2210 } 2211 } 2212 2213 /* Callback for hash_map::traverse, asserts that the pointer map is 2214 empty. */ 2215 2216 bool 2217 assert_is_empty (const_basic_block const &, edge_prediction *const &value, 2218 void *) 2219 { 2220 gcc_assert (!value); 2221 return false; 2222 } 2223 2224 /* Predict branch probabilities and estimate profile for basic block BB. */ 2225 2226 static void 2227 tree_estimate_probability_bb (basic_block bb) 2228 { 2229 edge e; 2230 edge_iterator ei; 2231 gimple *last; 2232 2233 FOR_EACH_EDGE (e, ei, bb->succs) 2234 { 2235 /* Predict edges to user labels with attributes. */ 2236 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) 2237 { 2238 gimple_stmt_iterator gi; 2239 for (gi = gsi_start_bb (e->dest); !gsi_end_p (gi); gsi_next (&gi)) 2240 { 2241 glabel *label_stmt = dyn_cast <glabel *> (gsi_stmt (gi)); 2242 tree decl; 2243 2244 if (!label_stmt) 2245 break; 2246 decl = gimple_label_label (label_stmt); 2247 if (DECL_ARTIFICIAL (decl)) 2248 continue; 2249 2250 /* Finally, we have a user-defined label. */ 2251 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl))) 2252 predict_edge_def (e, PRED_COLD_LABEL, NOT_TAKEN); 2253 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl))) 2254 predict_edge_def (e, PRED_HOT_LABEL, TAKEN); 2255 } 2256 } 2257 2258 /* Predict early returns to be probable, as we've already taken 2259 care for error returns and other cases are often used for 2260 fast paths through function. 2261 2262 Since we've already removed the return statements, we are 2263 looking for CFG like: 2264 2265 if (conditional) 2266 { 2267 .. 2268 goto return_block 2269 } 2270 some other blocks 2271 return_block: 2272 return_stmt. */ 2273 if (e->dest != bb->next_bb 2274 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) 2275 && single_succ_p (e->dest) 2276 && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) 2277 && (last = last_stmt (e->dest)) != NULL 2278 && gimple_code (last) == GIMPLE_RETURN) 2279 { 2280 edge e1; 2281 edge_iterator ei1; 2282 2283 if (single_succ_p (bb)) 2284 { 2285 FOR_EACH_EDGE (e1, ei1, bb->preds) 2286 if (!predicted_by_p (e1->src, PRED_NULL_RETURN) 2287 && !predicted_by_p (e1->src, PRED_CONST_RETURN) 2288 && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN)) 2289 predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN); 2290 } 2291 else 2292 if (!predicted_by_p (e->src, PRED_NULL_RETURN) 2293 && !predicted_by_p (e->src, PRED_CONST_RETURN) 2294 && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN)) 2295 predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN); 2296 } 2297 2298 /* Look for block we are guarding (ie we dominate it, 2299 but it doesn't postdominate us). */ 2300 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb 2301 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src) 2302 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest)) 2303 { 2304 gimple_stmt_iterator bi; 2305 2306 /* The call heuristic claims that a guarded function call 2307 is improbable. This is because such calls are often used 2308 to signal exceptional situations such as printing error 2309 messages. */ 2310 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi); 2311 gsi_next (&bi)) 2312 { 2313 gimple *stmt = gsi_stmt (bi); 2314 if (is_gimple_call (stmt) 2315 /* Constant and pure calls are hardly used to signalize 2316 something exceptional. */ 2317 && gimple_has_side_effects (stmt)) 2318 { 2319 predict_edge_def (e, PRED_CALL, NOT_TAKEN); 2320 break; 2321 } 2322 } 2323 } 2324 } 2325 tree_predict_by_opcode (bb); 2326 } 2327 2328 /* Predict branch probabilities and estimate profile of the tree CFG. 2329 This function can be called from the loop optimizers to recompute 2330 the profile information. */ 2331 2332 void 2333 tree_estimate_probability (void) 2334 { 2335 basic_block bb; 2336 2337 add_noreturn_fake_exit_edges (); 2338 connect_infinite_loops_to_exit (); 2339 /* We use loop_niter_by_eval, which requires that the loops have 2340 preheaders. */ 2341 create_preheaders (CP_SIMPLE_PREHEADERS); 2342 calculate_dominance_info (CDI_POST_DOMINATORS); 2343 2344 bb_predictions = new hash_map<const_basic_block, edge_prediction *>; 2345 tree_bb_level_predictions (); 2346 record_loop_exits (); 2347 2348 if (number_of_loops (cfun) > 1) 2349 predict_loops (); 2350 2351 FOR_EACH_BB_FN (bb, cfun) 2352 tree_estimate_probability_bb (bb); 2353 2354 FOR_EACH_BB_FN (bb, cfun) 2355 combine_predictions_for_bb (bb); 2356 2357 if (flag_checking) 2358 bb_predictions->traverse<void *, assert_is_empty> (NULL); 2359 2360 delete bb_predictions; 2361 bb_predictions = NULL; 2362 2363 estimate_bb_frequencies (false); 2364 free_dominance_info (CDI_POST_DOMINATORS); 2365 remove_fake_exit_edges (); 2366 } 2367 2368 /* Predict edges to successors of CUR whose sources are not postdominated by 2369 BB by PRED and recurse to all postdominators. */ 2370 2371 static void 2372 predict_paths_for_bb (basic_block cur, basic_block bb, 2373 enum br_predictor pred, 2374 enum prediction taken, 2375 bitmap visited) 2376 { 2377 edge e; 2378 edge_iterator ei; 2379 basic_block son; 2380 2381 /* We are looking for all edges forming edge cut induced by 2382 set of all blocks postdominated by BB. */ 2383 FOR_EACH_EDGE (e, ei, cur->preds) 2384 if (e->src->index >= NUM_FIXED_BLOCKS 2385 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb)) 2386 { 2387 edge e2; 2388 edge_iterator ei2; 2389 bool found = false; 2390 2391 /* Ignore fake edges and eh, we predict them as not taken anyway. */ 2392 if (e->flags & (EDGE_EH | EDGE_FAKE)) 2393 continue; 2394 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb)); 2395 2396 /* See if there is an edge from e->src that is not abnormal 2397 and does not lead to BB. */ 2398 FOR_EACH_EDGE (e2, ei2, e->src->succs) 2399 if (e2 != e 2400 && !(e2->flags & (EDGE_EH | EDGE_FAKE)) 2401 && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)) 2402 { 2403 found = true; 2404 break; 2405 } 2406 2407 /* If there is non-abnormal path leaving e->src, predict edge 2408 using predictor. Otherwise we need to look for paths 2409 leading to e->src. 2410 2411 The second may lead to infinite loop in the case we are predicitng 2412 regions that are only reachable by abnormal edges. We simply 2413 prevent visiting given BB twice. */ 2414 if (found) 2415 predict_edge_def (e, pred, taken); 2416 else if (bitmap_set_bit (visited, e->src->index)) 2417 predict_paths_for_bb (e->src, e->src, pred, taken, visited); 2418 } 2419 for (son = first_dom_son (CDI_POST_DOMINATORS, cur); 2420 son; 2421 son = next_dom_son (CDI_POST_DOMINATORS, son)) 2422 predict_paths_for_bb (son, bb, pred, taken, visited); 2423 } 2424 2425 /* Sets branch probabilities according to PREDiction and 2426 FLAGS. */ 2427 2428 static void 2429 predict_paths_leading_to (basic_block bb, enum br_predictor pred, 2430 enum prediction taken) 2431 { 2432 bitmap visited = BITMAP_ALLOC (NULL); 2433 predict_paths_for_bb (bb, bb, pred, taken, visited); 2434 BITMAP_FREE (visited); 2435 } 2436 2437 /* Like predict_paths_leading_to but take edge instead of basic block. */ 2438 2439 static void 2440 predict_paths_leading_to_edge (edge e, enum br_predictor pred, 2441 enum prediction taken) 2442 { 2443 bool has_nonloop_edge = false; 2444 edge_iterator ei; 2445 edge e2; 2446 2447 basic_block bb = e->src; 2448 FOR_EACH_EDGE (e2, ei, bb->succs) 2449 if (e2->dest != e->src && e2->dest != e->dest 2450 && !(e->flags & (EDGE_EH | EDGE_FAKE)) 2451 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest)) 2452 { 2453 has_nonloop_edge = true; 2454 break; 2455 } 2456 if (!has_nonloop_edge) 2457 { 2458 bitmap visited = BITMAP_ALLOC (NULL); 2459 predict_paths_for_bb (bb, bb, pred, taken, visited); 2460 BITMAP_FREE (visited); 2461 } 2462 else 2463 predict_edge_def (e, pred, taken); 2464 } 2465 2466 /* This is used to carry information about basic blocks. It is 2467 attached to the AUX field of the standard CFG block. */ 2468 2469 struct block_info 2470 { 2471 /* Estimated frequency of execution of basic_block. */ 2472 sreal frequency; 2473 2474 /* To keep queue of basic blocks to process. */ 2475 basic_block next; 2476 2477 /* Number of predecessors we need to visit first. */ 2478 int npredecessors; 2479 }; 2480 2481 /* Similar information for edges. */ 2482 struct edge_prob_info 2483 { 2484 /* In case edge is a loopback edge, the probability edge will be reached 2485 in case header is. Estimated number of iterations of the loop can be 2486 then computed as 1 / (1 - back_edge_prob). */ 2487 sreal back_edge_prob; 2488 /* True if the edge is a loopback edge in the natural loop. */ 2489 unsigned int back_edge:1; 2490 }; 2491 2492 #define BLOCK_INFO(B) ((block_info *) (B)->aux) 2493 #undef EDGE_INFO 2494 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux) 2495 2496 /* Helper function for estimate_bb_frequencies. 2497 Propagate the frequencies in blocks marked in 2498 TOVISIT, starting in HEAD. */ 2499 2500 static void 2501 propagate_freq (basic_block head, bitmap tovisit) 2502 { 2503 basic_block bb; 2504 basic_block last; 2505 unsigned i; 2506 edge e; 2507 basic_block nextbb; 2508 bitmap_iterator bi; 2509 2510 /* For each basic block we need to visit count number of his predecessors 2511 we need to visit first. */ 2512 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi) 2513 { 2514 edge_iterator ei; 2515 int count = 0; 2516 2517 bb = BASIC_BLOCK_FOR_FN (cfun, i); 2518 2519 FOR_EACH_EDGE (e, ei, bb->preds) 2520 { 2521 bool visit = bitmap_bit_p (tovisit, e->src->index); 2522 2523 if (visit && !(e->flags & EDGE_DFS_BACK)) 2524 count++; 2525 else if (visit && dump_file && !EDGE_INFO (e)->back_edge) 2526 fprintf (dump_file, 2527 "Irreducible region hit, ignoring edge to %i->%i\n", 2528 e->src->index, bb->index); 2529 } 2530 BLOCK_INFO (bb)->npredecessors = count; 2531 /* When function never returns, we will never process exit block. */ 2532 if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) 2533 bb->count = bb->frequency = 0; 2534 } 2535 2536 BLOCK_INFO (head)->frequency = 1; 2537 last = head; 2538 for (bb = head; bb; bb = nextbb) 2539 { 2540 edge_iterator ei; 2541 sreal cyclic_probability = 0; 2542 sreal frequency = 0; 2543 2544 nextbb = BLOCK_INFO (bb)->next; 2545 BLOCK_INFO (bb)->next = NULL; 2546 2547 /* Compute frequency of basic block. */ 2548 if (bb != head) 2549 { 2550 if (flag_checking) 2551 FOR_EACH_EDGE (e, ei, bb->preds) 2552 gcc_assert (!bitmap_bit_p (tovisit, e->src->index) 2553 || (e->flags & EDGE_DFS_BACK)); 2554 2555 FOR_EACH_EDGE (e, ei, bb->preds) 2556 if (EDGE_INFO (e)->back_edge) 2557 { 2558 cyclic_probability += EDGE_INFO (e)->back_edge_prob; 2559 } 2560 else if (!(e->flags & EDGE_DFS_BACK)) 2561 { 2562 /* frequency += (e->probability 2563 * BLOCK_INFO (e->src)->frequency / 2564 REG_BR_PROB_BASE); */ 2565 2566 sreal tmp = e->probability; 2567 tmp *= BLOCK_INFO (e->src)->frequency; 2568 tmp *= real_inv_br_prob_base; 2569 frequency += tmp; 2570 } 2571 2572 if (cyclic_probability == 0) 2573 { 2574 BLOCK_INFO (bb)->frequency = frequency; 2575 } 2576 else 2577 { 2578 if (cyclic_probability > real_almost_one) 2579 cyclic_probability = real_almost_one; 2580 2581 /* BLOCK_INFO (bb)->frequency = frequency 2582 / (1 - cyclic_probability) */ 2583 2584 cyclic_probability = sreal (1) - cyclic_probability; 2585 BLOCK_INFO (bb)->frequency = frequency / cyclic_probability; 2586 } 2587 } 2588 2589 bitmap_clear_bit (tovisit, bb->index); 2590 2591 e = find_edge (bb, head); 2592 if (e) 2593 { 2594 /* EDGE_INFO (e)->back_edge_prob 2595 = ((e->probability * BLOCK_INFO (bb)->frequency) 2596 / REG_BR_PROB_BASE); */ 2597 2598 sreal tmp = e->probability; 2599 tmp *= BLOCK_INFO (bb)->frequency; 2600 EDGE_INFO (e)->back_edge_prob = tmp * real_inv_br_prob_base; 2601 } 2602 2603 /* Propagate to successor blocks. */ 2604 FOR_EACH_EDGE (e, ei, bb->succs) 2605 if (!(e->flags & EDGE_DFS_BACK) 2606 && BLOCK_INFO (e->dest)->npredecessors) 2607 { 2608 BLOCK_INFO (e->dest)->npredecessors--; 2609 if (!BLOCK_INFO (e->dest)->npredecessors) 2610 { 2611 if (!nextbb) 2612 nextbb = e->dest; 2613 else 2614 BLOCK_INFO (last)->next = e->dest; 2615 2616 last = e->dest; 2617 } 2618 } 2619 } 2620 } 2621 2622 /* Estimate frequencies in loops at same nest level. */ 2623 2624 static void 2625 estimate_loops_at_level (struct loop *first_loop) 2626 { 2627 struct loop *loop; 2628 2629 for (loop = first_loop; loop; loop = loop->next) 2630 { 2631 edge e; 2632 basic_block *bbs; 2633 unsigned i; 2634 bitmap tovisit = BITMAP_ALLOC (NULL); 2635 2636 estimate_loops_at_level (loop->inner); 2637 2638 /* Find current loop back edge and mark it. */ 2639 e = loop_latch_edge (loop); 2640 EDGE_INFO (e)->back_edge = 1; 2641 2642 bbs = get_loop_body (loop); 2643 for (i = 0; i < loop->num_nodes; i++) 2644 bitmap_set_bit (tovisit, bbs[i]->index); 2645 free (bbs); 2646 propagate_freq (loop->header, tovisit); 2647 BITMAP_FREE (tovisit); 2648 } 2649 } 2650 2651 /* Propagates frequencies through structure of loops. */ 2652 2653 static void 2654 estimate_loops (void) 2655 { 2656 bitmap tovisit = BITMAP_ALLOC (NULL); 2657 basic_block bb; 2658 2659 /* Start by estimating the frequencies in the loops. */ 2660 if (number_of_loops (cfun) > 1) 2661 estimate_loops_at_level (current_loops->tree_root->inner); 2662 2663 /* Now propagate the frequencies through all the blocks. */ 2664 FOR_ALL_BB_FN (bb, cfun) 2665 { 2666 bitmap_set_bit (tovisit, bb->index); 2667 } 2668 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit); 2669 BITMAP_FREE (tovisit); 2670 } 2671 2672 /* Drop the profile for NODE to guessed, and update its frequency based on 2673 whether it is expected to be hot given the CALL_COUNT. */ 2674 2675 static void 2676 drop_profile (struct cgraph_node *node, gcov_type call_count) 2677 { 2678 struct function *fn = DECL_STRUCT_FUNCTION (node->decl); 2679 /* In the case where this was called by another function with a 2680 dropped profile, call_count will be 0. Since there are no 2681 non-zero call counts to this function, we don't know for sure 2682 whether it is hot, and therefore it will be marked normal below. */ 2683 bool hot = maybe_hot_count_p (NULL, call_count); 2684 2685 if (dump_file) 2686 fprintf (dump_file, 2687 "Dropping 0 profile for %s/%i. %s based on calls.\n", 2688 node->name (), node->order, 2689 hot ? "Function is hot" : "Function is normal"); 2690 /* We only expect to miss profiles for functions that are reached 2691 via non-zero call edges in cases where the function may have 2692 been linked from another module or library (COMDATs and extern 2693 templates). See the comments below for handle_missing_profiles. 2694 Also, only warn in cases where the missing counts exceed the 2695 number of training runs. In certain cases with an execv followed 2696 by a no-return call the profile for the no-return call is not 2697 dumped and there can be a mismatch. */ 2698 if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl) 2699 && call_count > profile_info->runs) 2700 { 2701 if (flag_profile_correction) 2702 { 2703 if (dump_file) 2704 fprintf (dump_file, 2705 "Missing counts for called function %s/%i\n", 2706 node->name (), node->order); 2707 } 2708 else 2709 warning (0, "Missing counts for called function %s/%i", 2710 node->name (), node->order); 2711 } 2712 2713 profile_status_for_fn (fn) 2714 = (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT); 2715 node->frequency 2716 = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL; 2717 } 2718 2719 /* In the case of COMDAT routines, multiple object files will contain the same 2720 function and the linker will select one for the binary. In that case 2721 all the other copies from the profile instrument binary will be missing 2722 profile counts. Look for cases where this happened, due to non-zero 2723 call counts going to 0-count functions, and drop the profile to guessed 2724 so that we can use the estimated probabilities and avoid optimizing only 2725 for size. 2726 2727 The other case where the profile may be missing is when the routine 2728 is not going to be emitted to the object file, e.g. for "extern template" 2729 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in 2730 all other cases of non-zero calls to 0-count functions. */ 2731 2732 void 2733 handle_missing_profiles (void) 2734 { 2735 struct cgraph_node *node; 2736 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION); 2737 vec<struct cgraph_node *> worklist; 2738 worklist.create (64); 2739 2740 /* See if 0 count function has non-0 count callers. In this case we 2741 lost some profile. Drop its function profile to PROFILE_GUESSED. */ 2742 FOR_EACH_DEFINED_FUNCTION (node) 2743 { 2744 struct cgraph_edge *e; 2745 gcov_type call_count = 0; 2746 gcov_type max_tp_first_run = 0; 2747 struct function *fn = DECL_STRUCT_FUNCTION (node->decl); 2748 2749 if (node->count) 2750 continue; 2751 for (e = node->callers; e; e = e->next_caller) 2752 { 2753 call_count += e->count; 2754 2755 if (e->caller->tp_first_run > max_tp_first_run) 2756 max_tp_first_run = e->caller->tp_first_run; 2757 } 2758 2759 /* If time profile is missing, let assign the maximum that comes from 2760 caller functions. */ 2761 if (!node->tp_first_run && max_tp_first_run) 2762 node->tp_first_run = max_tp_first_run + 1; 2763 2764 if (call_count 2765 && fn && fn->cfg 2766 && (call_count * unlikely_count_fraction >= profile_info->runs)) 2767 { 2768 drop_profile (node, call_count); 2769 worklist.safe_push (node); 2770 } 2771 } 2772 2773 /* Propagate the profile dropping to other 0-count COMDATs that are 2774 potentially called by COMDATs we already dropped the profile on. */ 2775 while (worklist.length () > 0) 2776 { 2777 struct cgraph_edge *e; 2778 2779 node = worklist.pop (); 2780 for (e = node->callees; e; e = e->next_caller) 2781 { 2782 struct cgraph_node *callee = e->callee; 2783 struct function *fn = DECL_STRUCT_FUNCTION (callee->decl); 2784 2785 if (callee->count > 0) 2786 continue; 2787 if (DECL_COMDAT (callee->decl) && fn && fn->cfg 2788 && profile_status_for_fn (fn) == PROFILE_READ) 2789 { 2790 drop_profile (node, 0); 2791 worklist.safe_push (callee); 2792 } 2793 } 2794 } 2795 worklist.release (); 2796 } 2797 2798 /* Convert counts measured by profile driven feedback to frequencies. 2799 Return nonzero iff there was any nonzero execution count. */ 2800 2801 int 2802 counts_to_freqs (void) 2803 { 2804 gcov_type count_max, true_count_max = 0; 2805 basic_block bb; 2806 2807 /* Don't overwrite the estimated frequencies when the profile for 2808 the function is missing. We may drop this function PROFILE_GUESSED 2809 later in drop_profile (). */ 2810 if (!flag_auto_profile && !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count) 2811 return 0; 2812 2813 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) 2814 true_count_max = MAX (bb->count, true_count_max); 2815 2816 count_max = MAX (true_count_max, 1); 2817 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) 2818 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max; 2819 2820 return true_count_max; 2821 } 2822 2823 /* Return true if function is likely to be expensive, so there is no point to 2824 optimize performance of prologue, epilogue or do inlining at the expense 2825 of code size growth. THRESHOLD is the limit of number of instructions 2826 function can execute at average to be still considered not expensive. */ 2827 2828 bool 2829 expensive_function_p (int threshold) 2830 { 2831 unsigned int sum = 0; 2832 basic_block bb; 2833 unsigned int limit; 2834 2835 /* We can not compute accurately for large thresholds due to scaled 2836 frequencies. */ 2837 gcc_assert (threshold <= BB_FREQ_MAX); 2838 2839 /* Frequencies are out of range. This either means that function contains 2840 internal loop executing more than BB_FREQ_MAX times or profile feedback 2841 is available and function has not been executed at all. */ 2842 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency == 0) 2843 return true; 2844 2845 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */ 2846 limit = ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency * threshold; 2847 FOR_EACH_BB_FN (bb, cfun) 2848 { 2849 rtx_insn *insn; 2850 2851 FOR_BB_INSNS (bb, insn) 2852 if (active_insn_p (insn)) 2853 { 2854 sum += bb->frequency; 2855 if (sum > limit) 2856 return true; 2857 } 2858 } 2859 2860 return false; 2861 } 2862 2863 /* Estimate and propagate basic block frequencies using the given branch 2864 probabilities. If FORCE is true, the frequencies are used to estimate 2865 the counts even when there are already non-zero profile counts. */ 2866 2867 void 2868 estimate_bb_frequencies (bool force) 2869 { 2870 basic_block bb; 2871 sreal freq_max; 2872 2873 if (force || profile_status_for_fn (cfun) != PROFILE_READ || !counts_to_freqs ()) 2874 { 2875 static int real_values_initialized = 0; 2876 2877 if (!real_values_initialized) 2878 { 2879 real_values_initialized = 1; 2880 real_br_prob_base = REG_BR_PROB_BASE; 2881 real_bb_freq_max = BB_FREQ_MAX; 2882 real_one_half = sreal (1, -1); 2883 real_inv_br_prob_base = sreal (1) / real_br_prob_base; 2884 real_almost_one = sreal (1) - real_inv_br_prob_base; 2885 } 2886 2887 mark_dfs_back_edges (); 2888 2889 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability = 2890 REG_BR_PROB_BASE; 2891 2892 /* Set up block info for each basic block. */ 2893 alloc_aux_for_blocks (sizeof (block_info)); 2894 alloc_aux_for_edges (sizeof (edge_prob_info)); 2895 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) 2896 { 2897 edge e; 2898 edge_iterator ei; 2899 2900 FOR_EACH_EDGE (e, ei, bb->succs) 2901 { 2902 EDGE_INFO (e)->back_edge_prob = e->probability; 2903 EDGE_INFO (e)->back_edge_prob *= real_inv_br_prob_base; 2904 } 2905 } 2906 2907 /* First compute frequencies locally for each loop from innermost 2908 to outermost to examine frequencies for back edges. */ 2909 estimate_loops (); 2910 2911 freq_max = 0; 2912 FOR_EACH_BB_FN (bb, cfun) 2913 if (freq_max < BLOCK_INFO (bb)->frequency) 2914 freq_max = BLOCK_INFO (bb)->frequency; 2915 2916 freq_max = real_bb_freq_max / freq_max; 2917 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) 2918 { 2919 sreal tmp = BLOCK_INFO (bb)->frequency * freq_max + real_one_half; 2920 bb->frequency = tmp.to_int (); 2921 } 2922 2923 free_aux_for_blocks (); 2924 free_aux_for_edges (); 2925 } 2926 compute_function_frequency (); 2927 } 2928 2929 /* Decide whether function is hot, cold or unlikely executed. */ 2930 void 2931 compute_function_frequency (void) 2932 { 2933 basic_block bb; 2934 struct cgraph_node *node = cgraph_node::get (current_function_decl); 2935 2936 if (DECL_STATIC_CONSTRUCTOR (current_function_decl) 2937 || MAIN_NAME_P (DECL_NAME (current_function_decl))) 2938 node->only_called_at_startup = true; 2939 if (DECL_STATIC_DESTRUCTOR (current_function_decl)) 2940 node->only_called_at_exit = true; 2941 2942 if (profile_status_for_fn (cfun) != PROFILE_READ) 2943 { 2944 int flags = flags_from_decl_or_type (current_function_decl); 2945 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)) 2946 != NULL) 2947 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED; 2948 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl)) 2949 != NULL) 2950 node->frequency = NODE_FREQUENCY_HOT; 2951 else if (flags & ECF_NORETURN) 2952 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE; 2953 else if (MAIN_NAME_P (DECL_NAME (current_function_decl))) 2954 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE; 2955 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl) 2956 || DECL_STATIC_DESTRUCTOR (current_function_decl)) 2957 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE; 2958 return; 2959 } 2960 2961 /* Only first time try to drop function into unlikely executed. 2962 After inlining the roundoff errors may confuse us. 2963 Ipa-profile pass will drop functions only called from unlikely 2964 functions to unlikely and that is most of what we care about. */ 2965 if (!cfun->after_inlining) 2966 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED; 2967 FOR_EACH_BB_FN (bb, cfun) 2968 { 2969 if (maybe_hot_bb_p (cfun, bb)) 2970 { 2971 node->frequency = NODE_FREQUENCY_HOT; 2972 return; 2973 } 2974 if (!probably_never_executed_bb_p (cfun, bb)) 2975 node->frequency = NODE_FREQUENCY_NORMAL; 2976 } 2977 } 2978 2979 /* Build PREDICT_EXPR. */ 2980 tree 2981 build_predict_expr (enum br_predictor predictor, enum prediction taken) 2982 { 2983 tree t = build1 (PREDICT_EXPR, void_type_node, 2984 build_int_cst (integer_type_node, predictor)); 2985 SET_PREDICT_EXPR_OUTCOME (t, taken); 2986 return t; 2987 } 2988 2989 const char * 2990 predictor_name (enum br_predictor predictor) 2991 { 2992 return predictor_info[predictor].name; 2993 } 2994 2995 /* Predict branch probabilities and estimate profile of the tree CFG. */ 2996 2997 namespace { 2998 2999 const pass_data pass_data_profile = 3000 { 3001 GIMPLE_PASS, /* type */ 3002 "profile_estimate", /* name */ 3003 OPTGROUP_NONE, /* optinfo_flags */ 3004 TV_BRANCH_PROB, /* tv_id */ 3005 PROP_cfg, /* properties_required */ 3006 0, /* properties_provided */ 3007 0, /* properties_destroyed */ 3008 0, /* todo_flags_start */ 3009 0, /* todo_flags_finish */ 3010 }; 3011 3012 class pass_profile : public gimple_opt_pass 3013 { 3014 public: 3015 pass_profile (gcc::context *ctxt) 3016 : gimple_opt_pass (pass_data_profile, ctxt) 3017 {} 3018 3019 /* opt_pass methods: */ 3020 virtual bool gate (function *) { return flag_guess_branch_prob; } 3021 virtual unsigned int execute (function *); 3022 3023 }; // class pass_profile 3024 3025 unsigned int 3026 pass_profile::execute (function *fun) 3027 { 3028 unsigned nb_loops; 3029 3030 if (profile_status_for_fn (cfun) == PROFILE_GUESSED) 3031 return 0; 3032 3033 loop_optimizer_init (LOOPS_NORMAL); 3034 if (dump_file && (dump_flags & TDF_DETAILS)) 3035 flow_loops_dump (dump_file, NULL, 0); 3036 3037 mark_irreducible_loops (); 3038 3039 nb_loops = number_of_loops (fun); 3040 if (nb_loops > 1) 3041 scev_initialize (); 3042 3043 tree_estimate_probability (); 3044 3045 if (nb_loops > 1) 3046 scev_finalize (); 3047 3048 loop_optimizer_finalize (); 3049 if (dump_file && (dump_flags & TDF_DETAILS)) 3050 gimple_dump_cfg (dump_file, dump_flags); 3051 if (profile_status_for_fn (fun) == PROFILE_ABSENT) 3052 profile_status_for_fn (fun) = PROFILE_GUESSED; 3053 return 0; 3054 } 3055 3056 } // anon namespace 3057 3058 gimple_opt_pass * 3059 make_pass_profile (gcc::context *ctxt) 3060 { 3061 return new pass_profile (ctxt); 3062 } 3063 3064 namespace { 3065 3066 const pass_data pass_data_strip_predict_hints = 3067 { 3068 GIMPLE_PASS, /* type */ 3069 "*strip_predict_hints", /* name */ 3070 OPTGROUP_NONE, /* optinfo_flags */ 3071 TV_BRANCH_PROB, /* tv_id */ 3072 PROP_cfg, /* properties_required */ 3073 0, /* properties_provided */ 3074 0, /* properties_destroyed */ 3075 0, /* todo_flags_start */ 3076 0, /* todo_flags_finish */ 3077 }; 3078 3079 class pass_strip_predict_hints : public gimple_opt_pass 3080 { 3081 public: 3082 pass_strip_predict_hints (gcc::context *ctxt) 3083 : gimple_opt_pass (pass_data_strip_predict_hints, ctxt) 3084 {} 3085 3086 /* opt_pass methods: */ 3087 opt_pass * clone () { return new pass_strip_predict_hints (m_ctxt); } 3088 virtual unsigned int execute (function *); 3089 3090 }; // class pass_strip_predict_hints 3091 3092 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements 3093 we no longer need. */ 3094 unsigned int 3095 pass_strip_predict_hints::execute (function *fun) 3096 { 3097 basic_block bb; 3098 gimple *ass_stmt; 3099 tree var; 3100 3101 FOR_EACH_BB_FN (bb, fun) 3102 { 3103 gimple_stmt_iterator bi; 3104 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);) 3105 { 3106 gimple *stmt = gsi_stmt (bi); 3107 3108 if (gimple_code (stmt) == GIMPLE_PREDICT) 3109 { 3110 gsi_remove (&bi, true); 3111 continue; 3112 } 3113 else if (is_gimple_call (stmt)) 3114 { 3115 tree fndecl = gimple_call_fndecl (stmt); 3116 3117 if ((fndecl 3118 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL 3119 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT 3120 && gimple_call_num_args (stmt) == 2) 3121 || (gimple_call_internal_p (stmt) 3122 && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT)) 3123 { 3124 var = gimple_call_lhs (stmt); 3125 if (var) 3126 { 3127 ass_stmt 3128 = gimple_build_assign (var, gimple_call_arg (stmt, 0)); 3129 gsi_replace (&bi, ass_stmt, true); 3130 } 3131 else 3132 { 3133 gsi_remove (&bi, true); 3134 continue; 3135 } 3136 } 3137 } 3138 gsi_next (&bi); 3139 } 3140 } 3141 return 0; 3142 } 3143 3144 } // anon namespace 3145 3146 gimple_opt_pass * 3147 make_pass_strip_predict_hints (gcc::context *ctxt) 3148 { 3149 return new pass_strip_predict_hints (ctxt); 3150 } 3151 3152 /* Rebuild function frequencies. Passes are in general expected to 3153 maintain profile by hand, however in some cases this is not possible: 3154 for example when inlining several functions with loops freuqencies might run 3155 out of scale and thus needs to be recomputed. */ 3156 3157 void 3158 rebuild_frequencies (void) 3159 { 3160 timevar_push (TV_REBUILD_FREQUENCIES); 3161 3162 /* When the max bb count in the function is small, there is a higher 3163 chance that there were truncation errors in the integer scaling 3164 of counts by inlining and other optimizations. This could lead 3165 to incorrect classification of code as being cold when it isn't. 3166 In that case, force the estimation of bb counts/frequencies from the 3167 branch probabilities, rather than computing frequencies from counts, 3168 which may also lead to frequencies incorrectly reduced to 0. There 3169 is less precision in the probabilities, so we only do this for small 3170 max counts. */ 3171 gcov_type count_max = 0; 3172 basic_block bb; 3173 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) 3174 count_max = MAX (bb->count, count_max); 3175 3176 if (profile_status_for_fn (cfun) == PROFILE_GUESSED 3177 || (!flag_auto_profile && profile_status_for_fn (cfun) == PROFILE_READ 3178 && count_max < REG_BR_PROB_BASE/10)) 3179 { 3180 loop_optimizer_init (0); 3181 add_noreturn_fake_exit_edges (); 3182 mark_irreducible_loops (); 3183 connect_infinite_loops_to_exit (); 3184 estimate_bb_frequencies (true); 3185 remove_fake_exit_edges (); 3186 loop_optimizer_finalize (); 3187 } 3188 else if (profile_status_for_fn (cfun) == PROFILE_READ) 3189 counts_to_freqs (); 3190 else 3191 gcc_unreachable (); 3192 timevar_pop (TV_REBUILD_FREQUENCIES); 3193 } 3194