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