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