gcc/predict.c

   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 = &REG_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 \f
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 \f
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 \f
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 \f
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   warn_function_cold (current_function_decl);
3945   if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
3946     return;
3947   FOR_EACH_BB_FN (bb, cfun)
3948     {
3949       if (maybe_hot_bb_p (cfun, bb))
3950         {
3951           node->frequency = NODE_FREQUENCY_HOT;
3952           return;
3953         }
3954       if (!probably_never_executed_bb_p (cfun, bb))
3955         node->frequency = NODE_FREQUENCY_NORMAL;
3956     }
3957 }
3958
3959 /* Build PREDICT_EXPR.  */
3960 tree
3961 build_predict_expr (enum br_predictor predictor, enum prediction taken)
3962 {
3963   tree t = build1 (PREDICT_EXPR, void_type_node,
3964                    build_int_cst (integer_type_node, predictor));
3965   SET_PREDICT_EXPR_OUTCOME (t, taken);
3966   return t;
3967 }
3968
3969 const char *
3970 predictor_name (enum br_predictor predictor)
3971 {
3972   return predictor_info[predictor].name;
3973 }
3974
3975 /* Predict branch probabilities and estimate profile of the tree CFG. */
3976
3977 namespace {
3978
3979 const pass_data pass_data_profile =
3980 {
3981   GIMPLE_PASS, /* type */
3982   "profile_estimate", /* name */
3983   OPTGROUP_NONE, /* optinfo_flags */
3984   TV_BRANCH_PROB, /* tv_id */
3985   PROP_cfg, /* properties_required */
3986   0, /* properties_provided */
3987   0, /* properties_destroyed */
3988   0, /* todo_flags_start */
3989   0, /* todo_flags_finish */
3990 };
3991
3992 class pass_profile : public gimple_opt_pass
3993 {
3994 public:
3995   pass_profile (gcc::context *ctxt)
3996     : gimple_opt_pass (pass_data_profile, ctxt)
3997   {}
3998
3999   /* opt_pass methods: */
4000   virtual bool gate (function *) { return flag_guess_branch_prob; }
4001   virtual unsigned int execute (function *);
4002
4003 }; // class pass_profile
4004
4005 unsigned int
4006 pass_profile::execute (function *fun)
4007 {
4008   unsigned nb_loops;
4009
4010   if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
4011     return 0;
4012
4013   loop_optimizer_init (LOOPS_NORMAL);
4014   if (dump_file && (dump_flags & TDF_DETAILS))
4015     flow_loops_dump (dump_file, NULL, 0);
4016
4017   mark_irreducible_loops ();
4018
4019   nb_loops = number_of_loops (fun);
4020   if (nb_loops > 1)
4021     scev_initialize ();
4022
4023   tree_estimate_probability (false);
4024
4025   if (nb_loops > 1)
4026     scev_finalize ();
4027
4028   loop_optimizer_finalize ();
4029   if (dump_file && (dump_flags & TDF_DETAILS))
4030     gimple_dump_cfg (dump_file, dump_flags);
4031  if (profile_status_for_fn (fun) == PROFILE_ABSENT)
4032     profile_status_for_fn (fun) = PROFILE_GUESSED;
4033  if (dump_file && (dump_flags & TDF_DETAILS))
4034    {
4035      class loop *loop;
4036      FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
4037        if (loop->header->count.initialized_p ())
4038          fprintf (dump_file, "Loop got predicted %d to iterate %i times.\n",
4039            loop->num,
4040            (int)expected_loop_iterations_unbounded (loop));
4041    }
4042   return 0;
4043 }
4044
4045 } // anon namespace
4046
4047 gimple_opt_pass *
4048 make_pass_profile (gcc::context *ctxt)
4049 {
4050   return new pass_profile (ctxt);
4051 }
4052
4053 /* Return true when PRED predictor should be removed after early
4054    tree passes.  Most of the predictors are beneficial to survive
4055    as early inlining can also distribute then into caller's bodies.  */
4056
4057 static bool
4058 strip_predictor_early (enum br_predictor pred)
4059 {
4060   switch (pred)
4061     {
4062     case PRED_TREE_EARLY_RETURN:
4063       return true;
4064     default:
4065       return false;
4066     }
4067 }
4068
4069 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
4070    we no longer need.  EARLY is set to true when called from early
4071    optimizations.  */
4072
4073 unsigned int
4074 strip_predict_hints (function *fun, bool early)
4075 {
4076   basic_block bb;
4077   gimple *ass_stmt;
4078   tree var;
4079   bool changed = false;
4080
4081   FOR_EACH_BB_FN (bb, fun)
4082     {
4083       gimple_stmt_iterator bi;
4084       for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
4085         {
4086           gimple *stmt = gsi_stmt (bi);
4087
4088           if (gimple_code (stmt) == GIMPLE_PREDICT)
4089             {
4090               if (!early
4091                   || strip_predictor_early (gimple_predict_predictor (stmt)))
4092                 {
4093                   gsi_remove (&bi, true);
4094                   changed = true;
4095                   continue;
4096                 }
4097             }
4098           else if (is_gimple_call (stmt))
4099             {
4100               tree fndecl = gimple_call_fndecl (stmt);
4101
4102               if (!early
4103                   && ((fndecl != NULL_TREE
4104                        && fndecl_built_in_p (fndecl, BUILT_IN_EXPECT)
4105                        && gimple_call_num_args (stmt) == 2)
4106                       || (fndecl != NULL_TREE
4107                           && fndecl_built_in_p (fndecl,
4108                                                 BUILT_IN_EXPECT_WITH_PROBABILITY)
4109                           && gimple_call_num_args (stmt) == 3)
4110                       || (gimple_call_internal_p (stmt)
4111                           && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT)))
4112                 {
4113                   var = gimple_call_lhs (stmt);
4114                   changed = true;
4115                   if (var)
4116                     {
4117                       ass_stmt
4118                         = gimple_build_assign (var, gimple_call_arg (stmt, 0));
4119                       gsi_replace (&bi, ass_stmt, true);
4120                     }
4121                   else
4122                     {
4123                       gsi_remove (&bi, true);
4124                       continue;
4125                     }
4126                 }
4127             }
4128           gsi_next (&bi);
4129         }
4130     }
4131   return changed ? TODO_cleanup_cfg : 0;
4132 }
4133
4134 namespace {
4135
4136 const pass_data pass_data_strip_predict_hints =
4137 {
4138   GIMPLE_PASS, /* type */
4139   "*strip_predict_hints", /* name */
4140   OPTGROUP_NONE, /* optinfo_flags */
4141   TV_BRANCH_PROB, /* tv_id */
4142   PROP_cfg, /* properties_required */
4143   0, /* properties_provided */
4144   0, /* properties_destroyed */
4145   0, /* todo_flags_start */
4146   0, /* todo_flags_finish */
4147 };
4148
4149 class pass_strip_predict_hints : public gimple_opt_pass
4150 {
4151 public:
4152   pass_strip_predict_hints (gcc::context *ctxt)
4153     : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
4154   {}
4155
4156   /* opt_pass methods: */
4157   opt_pass * clone () { return new pass_strip_predict_hints (m_ctxt); }
4158   void set_pass_param (unsigned int n, bool param)
4159     {
4160       gcc_assert (n == 0);
4161       early_p = param;
4162     }
4163
4164   virtual unsigned int execute (function *);
4165
4166 private:
4167   bool early_p;
4168
4169 }; // class pass_strip_predict_hints
4170
4171 unsigned int
4172 pass_strip_predict_hints::execute (function *fun)
4173 {
4174   return strip_predict_hints (fun, early_p);
4175 }
4176
4177 } // anon namespace
4178
4179 gimple_opt_pass *
4180 make_pass_strip_predict_hints (gcc::context *ctxt)
4181 {
4182   return new pass_strip_predict_hints (ctxt);
4183 }
4184
4185 /* Rebuild function frequencies.  Passes are in general expected to
4186    maintain profile by hand, however in some cases this is not possible:
4187    for example when inlining several functions with loops freuqencies might run
4188    out of scale and thus needs to be recomputed.  */
4189
4190 void
4191 rebuild_frequencies (void)
4192 {
4193   timevar_push (TV_REBUILD_FREQUENCIES);
4194
4195   /* When the max bb count in the function is small, there is a higher
4196      chance that there were truncation errors in the integer scaling
4197      of counts by inlining and other optimizations. This could lead
4198      to incorrect classification of code as being cold when it isn't.
4199      In that case, force the estimation of bb counts/frequencies from the
4200      branch probabilities, rather than computing frequencies from counts,
4201      which may also lead to frequencies incorrectly reduced to 0. There
4202      is less precision in the probabilities, so we only do this for small
4203      max counts.  */
4204   cfun->cfg->count_max = profile_count::uninitialized ();
4205   basic_block bb;
4206   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4207     cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
4208
4209   if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
4210     {
4211       loop_optimizer_init (0);
4212       add_noreturn_fake_exit_edges ();
4213       mark_irreducible_loops ();
4214       connect_infinite_loops_to_exit ();
4215       estimate_bb_frequencies (true);
4216       remove_fake_exit_edges ();
4217       loop_optimizer_finalize ();
4218     }
4219   else if (profile_status_for_fn (cfun) == PROFILE_READ)
4220     update_max_bb_count ();
4221   else if (profile_status_for_fn (cfun) == PROFILE_ABSENT
4222            && !flag_guess_branch_prob)
4223     ;
4224   else
4225     gcc_unreachable ();
4226   timevar_pop (TV_REBUILD_FREQUENCIES);
4227 }
4228
4229 /* Perform a dry run of the branch prediction pass and report comparsion of
4230    the predicted and real profile into the dump file.  */
4231
4232 void
4233 report_predictor_hitrates (void)
4234 {
4235   unsigned nb_loops;
4236
4237   loop_optimizer_init (LOOPS_NORMAL);
4238   if (dump_file && (dump_flags & TDF_DETAILS))
4239     flow_loops_dump (dump_file, NULL, 0);
4240
4241   mark_irreducible_loops ();
4242
4243   nb_loops = number_of_loops (cfun);
4244   if (nb_loops > 1)
4245     scev_initialize ();
4246
4247   tree_estimate_probability (true);
4248
4249   if (nb_loops > 1)
4250     scev_finalize ();
4251
4252   loop_optimizer_finalize ();
4253 }
4254
4255 /* Force edge E to be cold.
4256    If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4257    keep low probability to represent possible error in a guess.  This is used
4258    i.e. in case we predict loop to likely iterate given number of times but
4259    we are not 100% sure.
4260
4261    This function locally updates profile without attempt to keep global
4262    consistency which cannot be reached in full generality without full profile
4263    rebuild from probabilities alone.  Doing so is not necessarily a good idea
4264    because frequencies and counts may be more realistic then probabilities.
4265
4266    In some cases (such as for elimination of early exits during full loop
4267    unrolling) the caller can ensure that profile will get consistent
4268    afterwards.  */
4269
4270 void
4271 force_edge_cold (edge e, bool impossible)
4272 {
4273   profile_count count_sum = profile_count::zero ();
4274   profile_probability prob_sum = profile_probability::never ();
4275   edge_iterator ei;
4276   edge e2;
4277   bool uninitialized_exit = false;
4278
4279   /* When branch probability guesses are not known, then do nothing.  */
4280   if (!impossible && !e->count ().initialized_p ())
4281     return;
4282
4283   profile_probability goal = (impossible ? profile_probability::never ()
4284                               : profile_probability::very_unlikely ());
4285
4286   /* If edge is already improbably or cold, just return.  */
4287   if (e->probability <= goal
4288       && (!impossible || e->count () == profile_count::zero ()))
4289     return;
4290   FOR_EACH_EDGE (e2, ei, e->src->succs)
4291     if (e2 != e)
4292       {
4293         if (e->flags & EDGE_FAKE)
4294           continue;
4295         if (e2->count ().initialized_p ())
4296           count_sum += e2->count ();
4297         if (e2->probability.initialized_p ())
4298           prob_sum += e2->probability;
4299         else
4300           uninitialized_exit = true;
4301       }
4302
4303   /* If we are not guessing profiles but have some other edges out,
4304      just assume the control flow goes elsewhere.  */
4305   if (uninitialized_exit)
4306     e->probability = goal;
4307   /* If there are other edges out of e->src, redistribute probabilitity
4308      there.  */
4309   else if (prob_sum > profile_probability::never ())
4310     {
4311       if (!(e->probability < goal))
4312         e->probability = goal;
4313
4314       profile_probability prob_comp = prob_sum / e->probability.invert ();
4315
4316       if (dump_file && (dump_flags & TDF_DETAILS))
4317         fprintf (dump_file, "Making edge %i->%i %s by redistributing "
4318                  "probability to other edges.\n",
4319                  e->src->index, e->dest->index,
4320                  impossible ? "impossible" : "cold");
4321       FOR_EACH_EDGE (e2, ei, e->src->succs)
4322         if (e2 != e)
4323           {
4324             e2->probability /= prob_comp;
4325           }
4326       if (current_ir_type () != IR_GIMPLE
4327           && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4328         update_br_prob_note (e->src);
4329     }
4330   /* If all edges out of e->src are unlikely, the basic block itself
4331      is unlikely.  */
4332   else
4333     {
4334       if (prob_sum == profile_probability::never ())
4335         e->probability = profile_probability::always ();
4336       else
4337         {
4338           if (impossible)
4339             e->probability = profile_probability::never ();
4340           /* If BB has some edges out that are not impossible, we cannot
4341              assume that BB itself is.  */
4342           impossible = false;
4343         }
4344       if (current_ir_type () != IR_GIMPLE
4345           && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4346         update_br_prob_note (e->src);
4347       if (e->src->count == profile_count::zero ())
4348         return;
4349       if (count_sum == profile_count::zero () && impossible)
4350         {
4351           bool found = false;
4352           if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
4353             ;
4354           else if (current_ir_type () == IR_GIMPLE)
4355             for (gimple_stmt_iterator gsi = gsi_start_bb (e->src);
4356                  !gsi_end_p (gsi); gsi_next (&gsi))
4357               {
4358                 if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
4359                   {
4360                     found = true;
4361                     break;
4362                   }
4363               }
4364           /* FIXME: Implement RTL path.  */
4365           else
4366             found = true;
4367           if (!found)
4368             {
4369               if (dump_file && (dump_flags & TDF_DETAILS))
4370                 fprintf (dump_file,
4371                          "Making bb %i impossible and dropping count to 0.\n",
4372                          e->src->index);
4373               e->src->count = profile_count::zero ();
4374               FOR_EACH_EDGE (e2, ei, e->src->preds)
4375                 force_edge_cold (e2, impossible);
4376               return;
4377             }
4378         }
4379
4380       /* If we did not adjusting, the source basic block has no likely edeges
4381          leaving other direction. In that case force that bb cold, too.
4382          This in general is difficult task to do, but handle special case when
4383          BB has only one predecestor.  This is common case when we are updating
4384          after loop transforms.  */
4385       if (!(prob_sum > profile_probability::never ())
4386           && count_sum == profile_count::zero ()
4387           && single_pred_p (e->src) && e->src->count.to_frequency (cfun)
4388              > (impossible ? 0 : 1))
4389         {
4390           int old_frequency = e->src->count.to_frequency (cfun);
4391           if (dump_file && (dump_flags & TDF_DETAILS))
4392             fprintf (dump_file, "Making bb %i %s.\n", e->src->index,
4393                      impossible ? "impossible" : "cold");
4394           int new_frequency = MIN (e->src->count.to_frequency (cfun),
4395                                    impossible ? 0 : 1);
4396           if (impossible)
4397             e->src->count = profile_count::zero ();
4398           else
4399             e->src->count = e->count ().apply_scale (new_frequency,
4400                                                      old_frequency);
4401           force_edge_cold (single_pred_edge (e->src), impossible);
4402         }
4403       else if (dump_file && (dump_flags & TDF_DETAILS)
4404                && maybe_hot_bb_p (cfun, e->src))
4405         fprintf (dump_file, "Giving up on making bb %i %s.\n", e->src->index,
4406                  impossible ? "impossible" : "cold");
4407     }
4408 }
4409
4410 #if CHECKING_P
4411
4412 namespace selftest {
4413
4414 /* Test that value range of predictor values defined in predict.def is
4415    within range (50, 100].  */
4416
4417 struct branch_predictor
4418 {
4419   const char *name;
4420   int probability;
4421 };
4422
4423 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4424
4425 static void
4426 test_prediction_value_range ()
4427 {
4428   branch_predictor predictors[] = {
4429 #include "predict.def"
4430     { NULL, PROB_UNINITIALIZED }
4431   };
4432
4433   for (unsigned i = 0; predictors[i].name != NULL; i++)
4434     {
4435       if (predictors[i].probability == PROB_UNINITIALIZED)
4436         continue;
4437
4438       unsigned p = 100 * predictors[i].probability / REG_BR_PROB_BASE;
4439       ASSERT_TRUE (p >= 50 && p <= 100);
4440     }
4441 }
4442
4443 #undef DEF_PREDICTOR
4444
4445 /* Run all of the selfests within this file.  */
4446
4447 void
4448 predict_c_tests ()
4449 {
4450   test_prediction_value_range ();
4451 }
4452
4453 } // namespace selftest
4454 #endif /* CHECKING_P.  */