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