190075Sobrien/* Branch prediction routines for the GNU compiler. 2146895Skan Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005 3146895Skan Free Software Foundation, Inc. 490075Sobrien 590075SobrienThis file is part of GCC. 690075Sobrien 790075SobrienGCC is free software; you can redistribute it and/or modify it under 890075Sobrienthe terms of the GNU General Public License as published by the Free 990075SobrienSoftware Foundation; either version 2, or (at your option) any later 1090075Sobrienversion. 1190075Sobrien 1290075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1390075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1490075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1590075Sobrienfor more details. 1690075Sobrien 1790075SobrienYou should have received a copy of the GNU General Public License 1890075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 2190075Sobrien 2290075Sobrien/* References: 2390075Sobrien 2490075Sobrien [1] "Branch Prediction for Free" 2590075Sobrien Ball and Larus; PLDI '93. 2690075Sobrien [2] "Static Branch Frequency and Program Profile Analysis" 2790075Sobrien Wu and Larus; MICRO-27. 2890075Sobrien [3] "Corpus-based Static Branch Prediction" 2990075Sobrien Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */ 3090075Sobrien 3190075Sobrien 3290075Sobrien#include "config.h" 3390075Sobrien#include "system.h" 34132718Skan#include "coretypes.h" 35132718Skan#include "tm.h" 3690075Sobrien#include "tree.h" 3790075Sobrien#include "rtl.h" 3890075Sobrien#include "tm_p.h" 3990075Sobrien#include "hard-reg-set.h" 4090075Sobrien#include "basic-block.h" 4190075Sobrien#include "insn-config.h" 4290075Sobrien#include "regs.h" 4390075Sobrien#include "flags.h" 4490075Sobrien#include "output.h" 4590075Sobrien#include "function.h" 4690075Sobrien#include "except.h" 4790075Sobrien#include "toplev.h" 4890075Sobrien#include "recog.h" 4990075Sobrien#include "expr.h" 5090075Sobrien#include "predict.h" 51132718Skan#include "coverage.h" 52132718Skan#include "sreal.h" 53117395Skan#include "params.h" 54117395Skan#include "target.h" 55132718Skan#include "cfgloop.h" 56169689Skan#include "tree-flow.h" 57169689Skan#include "ggc.h" 58169689Skan#include "tree-dump.h" 59169689Skan#include "tree-pass.h" 60169689Skan#include "timevar.h" 61169689Skan#include "tree-scalar-evolution.h" 62169689Skan#include "cfgloop.h" 6390075Sobrien 64117395Skan/* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE, 65117395Skan 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */ 66132718Skanstatic sreal real_zero, real_one, real_almost_one, real_br_prob_base, 67132718Skan real_inv_br_prob_base, real_one_half, real_bb_freq_max; 68117395Skan 6990075Sobrien/* Random guesstimation given names. */ 70146895Skan#define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 100 - 1) 7190075Sobrien#define PROB_EVEN (REG_BR_PROB_BASE / 2) 7290075Sobrien#define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY) 7390075Sobrien#define PROB_ALWAYS (REG_BR_PROB_BASE) 7490075Sobrien 75132718Skanstatic void combine_predictions_for_insn (rtx, basic_block); 76169689Skanstatic void dump_prediction (FILE *, enum br_predictor, int, basic_block, int); 77169689Skanstatic void estimate_loops_at_level (struct loop *, bitmap); 78169689Skanstatic void propagate_freq (struct loop *, bitmap); 79132718Skanstatic void estimate_bb_frequencies (struct loops *); 80169689Skanstatic void predict_paths_leading_to (basic_block, int *, enum br_predictor, enum prediction); 81132718Skanstatic bool last_basic_block_p (basic_block); 82132718Skanstatic void compute_function_frequency (void); 83132718Skanstatic void choose_function_section (void); 84132718Skanstatic bool can_predict_insn_p (rtx); 8590075Sobrien 8690075Sobrien/* Information we hold about each branch predictor. 8790075Sobrien Filled using information from predict.def. */ 8890075Sobrien 8990075Sobrienstruct predictor_info 9090075Sobrien{ 9190075Sobrien const char *const name; /* Name used in the debugging dumps. */ 9290075Sobrien const int hitrate; /* Expected hitrate used by 9390075Sobrien predict_insn_def call. */ 9490075Sobrien const int flags; 9590075Sobrien}; 9690075Sobrien 9790075Sobrien/* Use given predictor without Dempster-Shaffer theory if it matches 9890075Sobrien using first_match heuristics. */ 9990075Sobrien#define PRED_FLAG_FIRST_MATCH 1 10090075Sobrien 10190075Sobrien/* Recompute hitrate in percent to our representation. */ 10290075Sobrien 10390075Sobrien#define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100) 10490075Sobrien 10590075Sobrien#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS}, 10690075Sobrienstatic const struct predictor_info predictor_info[]= { 10790075Sobrien#include "predict.def" 10890075Sobrien 10990075Sobrien /* Upper bound on predictors. */ 11090075Sobrien {NULL, 0, 0} 11190075Sobrien}; 11290075Sobrien#undef DEF_PREDICTOR 11390075Sobrien 114117395Skan/* Return true in case BB can be CPU intensive and should be optimized 115132718Skan for maximal performance. */ 116117395Skan 117117395Skanbool 118132718Skanmaybe_hot_bb_p (basic_block bb) 119117395Skan{ 120132718Skan if (profile_info && flag_branch_probabilities 121117395Skan && (bb->count 122132718Skan < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION))) 123117395Skan return false; 124117395Skan if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)) 125117395Skan return false; 126117395Skan return true; 127117395Skan} 128117395Skan 129117395Skan/* Return true in case BB is cold and should be optimized for size. */ 130117395Skan 131117395Skanbool 132132718Skanprobably_cold_bb_p (basic_block bb) 133117395Skan{ 134132718Skan if (profile_info && flag_branch_probabilities 135117395Skan && (bb->count 136132718Skan < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION))) 137117395Skan return true; 138117395Skan if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)) 139117395Skan return true; 140117395Skan return false; 141117395Skan} 142117395Skan 143117395Skan/* Return true in case BB is probably never executed. */ 144117395Skanbool 145132718Skanprobably_never_executed_bb_p (basic_block bb) 146117395Skan{ 147132718Skan if (profile_info && flag_branch_probabilities) 148132718Skan return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0; 149117395Skan return false; 150117395Skan} 151117395Skan 152117395Skan/* Return true if the one of outgoing edges is already predicted by 153117395Skan PREDICTOR. */ 154117395Skan 155169689Skanbool 156169689Skanrtl_predicted_by_p (basic_block bb, enum br_predictor predictor) 157117395Skan{ 158117395Skan rtx note; 159132718Skan if (!INSN_P (BB_END (bb))) 160117395Skan return false; 161132718Skan for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1)) 162117395Skan if (REG_NOTE_KIND (note) == REG_BR_PRED 163117395Skan && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor) 164117395Skan return true; 165117395Skan return false; 166117395Skan} 167117395Skan 168169689Skan/* Return true if the one of outgoing edges is already predicted by 169169689Skan PREDICTOR. */ 170169689Skan 171169689Skanbool 172169689Skantree_predicted_by_p (basic_block bb, enum br_predictor predictor) 173169689Skan{ 174169689Skan struct edge_prediction *i; 175169689Skan for (i = bb->predictions; i; i = i->ep_next) 176169689Skan if (i->ep_predictor == predictor) 177169689Skan return true; 178169689Skan return false; 179169689Skan} 180169689Skan 181169689Skan/* Return true when the probability of edge is reliable. 182169689Skan 183169689Skan The profile guessing code is good at predicting branch outcome (ie. 184169689Skan taken/not taken), that is predicted right slightly over 75% of time. 185169689Skan It is however notoriously poor on predicting the probability itself. 186169689Skan In general the profile appear a lot flatter (with probabilities closer 187169689Skan to 50%) than the reality so it is bad idea to use it to drive optimization 188169689Skan such as those disabling dynamic branch prediction for well predictable 189169689Skan branches. 190169689Skan 191169689Skan There are two exceptions - edges leading to noreturn edges and edges 192169689Skan predicted by number of iterations heuristics are predicted well. This macro 193169689Skan should be able to distinguish those, but at the moment it simply check for 194169689Skan noreturn heuristic that is only one giving probability over 99% or bellow 195169689Skan 1%. In future we might want to propagate reliability information across the 196169689Skan CFG if we find this information useful on multiple places. */ 197169689Skanstatic bool 198169689Skanprobability_reliable_p (int prob) 199169689Skan{ 200169689Skan return (profile_status == PROFILE_READ 201169689Skan || (profile_status == PROFILE_GUESSED 202169689Skan && (prob <= HITRATE (1) || prob >= HITRATE (99)))); 203169689Skan} 204169689Skan 205169689Skan/* Same predicate as above, working on edges. */ 206169689Skanbool 207169689Skanedge_probability_reliable_p (edge e) 208169689Skan{ 209169689Skan return probability_reliable_p (e->probability); 210169689Skan} 211169689Skan 212169689Skan/* Same predicate as edge_probability_reliable_p, working on notes. */ 213169689Skanbool 214169689Skanbr_prob_note_reliable_p (rtx note) 215169689Skan{ 216169689Skan gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB); 217169689Skan return probability_reliable_p (INTVAL (XEXP (note, 0))); 218169689Skan} 219169689Skan 220169689Skanstatic void 221132718Skanpredict_insn (rtx insn, enum br_predictor predictor, int probability) 22290075Sobrien{ 223169689Skan gcc_assert (any_condjump_p (insn)); 224117395Skan if (!flag_guess_branch_prob) 225117395Skan return; 22690075Sobrien 22790075Sobrien REG_NOTES (insn) 22890075Sobrien = gen_rtx_EXPR_LIST (REG_BR_PRED, 22990075Sobrien gen_rtx_CONCAT (VOIDmode, 23090075Sobrien GEN_INT ((int) predictor), 23190075Sobrien GEN_INT ((int) probability)), 23290075Sobrien REG_NOTES (insn)); 23390075Sobrien} 23490075Sobrien 23590075Sobrien/* Predict insn by given predictor. */ 23690075Sobrien 23790075Sobrienvoid 238132718Skanpredict_insn_def (rtx insn, enum br_predictor predictor, 239132718Skan enum prediction taken) 24090075Sobrien{ 24190075Sobrien int probability = predictor_info[(int) predictor].hitrate; 24290075Sobrien 24390075Sobrien if (taken != TAKEN) 24490075Sobrien probability = REG_BR_PROB_BASE - probability; 24590075Sobrien 24690075Sobrien predict_insn (insn, predictor, probability); 24790075Sobrien} 24890075Sobrien 24990075Sobrien/* Predict edge E with given probability if possible. */ 25090075Sobrien 25190075Sobrienvoid 252169689Skanrtl_predict_edge (edge e, enum br_predictor predictor, int probability) 25390075Sobrien{ 25490075Sobrien rtx last_insn; 255132718Skan last_insn = BB_END (e->src); 25690075Sobrien 25790075Sobrien /* We can store the branch prediction information only about 25890075Sobrien conditional jumps. */ 25990075Sobrien if (!any_condjump_p (last_insn)) 26090075Sobrien return; 26190075Sobrien 26290075Sobrien /* We always store probability of branching. */ 26390075Sobrien if (e->flags & EDGE_FALLTHRU) 26490075Sobrien probability = REG_BR_PROB_BASE - probability; 26590075Sobrien 26690075Sobrien predict_insn (last_insn, predictor, probability); 26790075Sobrien} 26890075Sobrien 269169689Skan/* Predict edge E with the given PROBABILITY. */ 270169689Skanvoid 271169689Skantree_predict_edge (edge e, enum br_predictor predictor, int probability) 272169689Skan{ 273169689Skan gcc_assert (profile_status != PROFILE_GUESSED); 274169689Skan if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1) 275169689Skan && flag_guess_branch_prob && optimize) 276169689Skan { 277169689Skan struct edge_prediction *i = ggc_alloc (sizeof (struct edge_prediction)); 278169689Skan 279169689Skan i->ep_next = e->src->predictions; 280169689Skan e->src->predictions = i; 281169689Skan i->ep_probability = probability; 282169689Skan i->ep_predictor = predictor; 283169689Skan i->ep_edge = e; 284169689Skan } 285169689Skan} 286169689Skan 287169689Skan/* Remove all predictions on given basic block that are attached 288169689Skan to edge E. */ 289169689Skanvoid 290169689Skanremove_predictions_associated_with_edge (edge e) 291169689Skan{ 292169689Skan if (e->src->predictions) 293169689Skan { 294169689Skan struct edge_prediction **prediction = &e->src->predictions; 295169689Skan while (*prediction) 296169689Skan { 297169689Skan if ((*prediction)->ep_edge == e) 298169689Skan *prediction = (*prediction)->ep_next; 299169689Skan else 300169689Skan prediction = &((*prediction)->ep_next); 301169689Skan } 302169689Skan } 303169689Skan} 304169689Skan 305117395Skan/* Return true when we can store prediction on insn INSN. 306117395Skan At the moment we represent predictions only on conditional 307117395Skan jumps, not at computed jump or other complicated cases. */ 308117395Skanstatic bool 309132718Skancan_predict_insn_p (rtx insn) 310117395Skan{ 311169689Skan return (JUMP_P (insn) 312117395Skan && any_condjump_p (insn) 313169689Skan && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2); 314117395Skan} 315117395Skan 31690075Sobrien/* Predict edge E by given predictor if possible. */ 31790075Sobrien 31890075Sobrienvoid 319132718Skanpredict_edge_def (edge e, enum br_predictor predictor, 320132718Skan enum prediction taken) 32190075Sobrien{ 32290075Sobrien int probability = predictor_info[(int) predictor].hitrate; 32390075Sobrien 32490075Sobrien if (taken != TAKEN) 32590075Sobrien probability = REG_BR_PROB_BASE - probability; 32690075Sobrien 32790075Sobrien predict_edge (e, predictor, probability); 32890075Sobrien} 32990075Sobrien 33090075Sobrien/* Invert all branch predictions or probability notes in the INSN. This needs 33190075Sobrien to be done each time we invert the condition used by the jump. */ 33290075Sobrien 33390075Sobrienvoid 334132718Skaninvert_br_probabilities (rtx insn) 33590075Sobrien{ 33690075Sobrien rtx note; 33790075Sobrien 33890075Sobrien for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 33990075Sobrien if (REG_NOTE_KIND (note) == REG_BR_PROB) 34090075Sobrien XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0))); 34190075Sobrien else if (REG_NOTE_KIND (note) == REG_BR_PRED) 34290075Sobrien XEXP (XEXP (note, 0), 1) 34390075Sobrien = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1))); 34490075Sobrien} 34590075Sobrien 34690075Sobrien/* Dump information about the branch prediction to the output file. */ 34790075Sobrien 34890075Sobrienstatic void 349169689Skandump_prediction (FILE *file, enum br_predictor predictor, int probability, 350132718Skan basic_block bb, int used) 35190075Sobrien{ 352169689Skan edge e; 353169689Skan edge_iterator ei; 35490075Sobrien 355169689Skan if (!file) 35690075Sobrien return; 35790075Sobrien 358169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 359169689Skan if (! (e->flags & EDGE_FALLTHRU)) 360169689Skan break; 36190075Sobrien 362169689Skan fprintf (file, " %s heuristics%s: %.1f%%", 36390075Sobrien predictor_info[predictor].name, 36490075Sobrien used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE); 36590075Sobrien 36690075Sobrien if (bb->count) 36790075Sobrien { 368169689Skan fprintf (file, " exec "); 369169689Skan fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count); 370117395Skan if (e) 371117395Skan { 372169689Skan fprintf (file, " hit "); 373169689Skan fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count); 374169689Skan fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count); 375117395Skan } 37690075Sobrien } 37790075Sobrien 378169689Skan fprintf (file, "\n"); 37990075Sobrien} 38090075Sobrien 381169689Skan/* We can not predict the probabilities of outgoing edges of bb. Set them 382169689Skan evenly and hope for the best. */ 383169689Skanstatic void 384169689Skanset_even_probabilities (basic_block bb) 385169689Skan{ 386169689Skan int nedges = 0; 387169689Skan edge e; 388169689Skan edge_iterator ei; 389169689Skan 390169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 391169689Skan if (!(e->flags & (EDGE_EH | EDGE_FAKE))) 392169689Skan nedges ++; 393169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 394169689Skan if (!(e->flags & (EDGE_EH | EDGE_FAKE))) 395169689Skan e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges; 396169689Skan else 397169689Skan e->probability = 0; 398169689Skan} 399169689Skan 40090075Sobrien/* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB 40190075Sobrien note if not already present. Remove now useless REG_BR_PRED notes. */ 40290075Sobrien 40390075Sobrienstatic void 404132718Skancombine_predictions_for_insn (rtx insn, basic_block bb) 40590075Sobrien{ 406169689Skan rtx prob_note; 407169689Skan rtx *pnote; 40890075Sobrien rtx note; 40990075Sobrien int best_probability = PROB_EVEN; 41090075Sobrien int best_predictor = END_PREDICTORS; 41190075Sobrien int combined_probability = REG_BR_PROB_BASE / 2; 41290075Sobrien int d; 41390075Sobrien bool first_match = false; 41490075Sobrien bool found = false; 41590075Sobrien 416169689Skan if (!can_predict_insn_p (insn)) 417169689Skan { 418169689Skan set_even_probabilities (bb); 419169689Skan return; 420169689Skan } 421169689Skan 422169689Skan prob_note = find_reg_note (insn, REG_BR_PROB, 0); 423169689Skan pnote = ®_NOTES (insn); 424169689Skan if (dump_file) 425169689Skan fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn), 42690075Sobrien bb->index); 42790075Sobrien 42890075Sobrien /* We implement "first match" heuristics and use probability guessed 429169689Skan by predictor with smallest index. */ 43090075Sobrien for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 43190075Sobrien if (REG_NOTE_KIND (note) == REG_BR_PRED) 43290075Sobrien { 43390075Sobrien int predictor = INTVAL (XEXP (XEXP (note, 0), 0)); 43490075Sobrien int probability = INTVAL (XEXP (XEXP (note, 0), 1)); 43590075Sobrien 43690075Sobrien found = true; 43790075Sobrien if (best_predictor > predictor) 43890075Sobrien best_probability = probability, best_predictor = predictor; 43990075Sobrien 44090075Sobrien d = (combined_probability * probability 44190075Sobrien + (REG_BR_PROB_BASE - combined_probability) 44290075Sobrien * (REG_BR_PROB_BASE - probability)); 44390075Sobrien 44490075Sobrien /* Use FP math to avoid overflows of 32bit integers. */ 44590075Sobrien if (d == 0) 44690075Sobrien /* If one probability is 0% and one 100%, avoid division by zero. */ 44790075Sobrien combined_probability = REG_BR_PROB_BASE / 2; 44890075Sobrien else 44990075Sobrien combined_probability = (((double) combined_probability) * probability 45090075Sobrien * REG_BR_PROB_BASE / d + 0.5); 45190075Sobrien } 45290075Sobrien 45390075Sobrien /* Decide which heuristic to use. In case we didn't match anything, 45490075Sobrien use no_prediction heuristic, in case we did match, use either 45590075Sobrien first match or Dempster-Shaffer theory depending on the flags. */ 45690075Sobrien 45790075Sobrien if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH) 45890075Sobrien first_match = true; 45990075Sobrien 46090075Sobrien if (!found) 461169689Skan dump_prediction (dump_file, PRED_NO_PREDICTION, 462169689Skan combined_probability, bb, true); 46390075Sobrien else 46490075Sobrien { 465169689Skan dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, 466169689Skan bb, !first_match); 467169689Skan dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, 468169689Skan bb, first_match); 46990075Sobrien } 47090075Sobrien 47190075Sobrien if (first_match) 47290075Sobrien combined_probability = best_probability; 473169689Skan dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true); 47490075Sobrien 47590075Sobrien while (*pnote) 47690075Sobrien { 47790075Sobrien if (REG_NOTE_KIND (*pnote) == REG_BR_PRED) 47890075Sobrien { 47990075Sobrien int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0)); 48090075Sobrien int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1)); 48190075Sobrien 482169689Skan dump_prediction (dump_file, predictor, probability, bb, 48390075Sobrien !first_match || best_predictor == predictor); 484117395Skan *pnote = XEXP (*pnote, 1); 48590075Sobrien } 48690075Sobrien else 487117395Skan pnote = &XEXP (*pnote, 1); 48890075Sobrien } 48990075Sobrien 49090075Sobrien if (!prob_note) 49190075Sobrien { 49290075Sobrien REG_NOTES (insn) 49390075Sobrien = gen_rtx_EXPR_LIST (REG_BR_PROB, 49490075Sobrien GEN_INT (combined_probability), REG_NOTES (insn)); 49590075Sobrien 49690075Sobrien /* Save the prediction into CFG in case we are seeing non-degenerated 49790075Sobrien conditional jump. */ 498169689Skan if (!single_succ_p (bb)) 49990075Sobrien { 50090075Sobrien BRANCH_EDGE (bb)->probability = combined_probability; 50190075Sobrien FALLTHRU_EDGE (bb)->probability 50290075Sobrien = REG_BR_PROB_BASE - combined_probability; 50390075Sobrien } 50490075Sobrien } 505169689Skan else if (!single_succ_p (bb)) 506169689Skan { 507169689Skan int prob = INTVAL (XEXP (prob_note, 0)); 508169689Skan 509169689Skan BRANCH_EDGE (bb)->probability = prob; 510169689Skan FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob; 511169689Skan } 512169689Skan else 513169689Skan single_succ_edge (bb)->probability = REG_BR_PROB_BASE; 51490075Sobrien} 51590075Sobrien 516169689Skan/* Combine predictions into single probability and store them into CFG. 517169689Skan Remove now useless prediction entries. */ 51890075Sobrien 519169689Skanstatic void 520169689Skancombine_predictions_for_bb (basic_block bb) 52190075Sobrien{ 522169689Skan int best_probability = PROB_EVEN; 523169689Skan int best_predictor = END_PREDICTORS; 524169689Skan int combined_probability = REG_BR_PROB_BASE / 2; 525169689Skan int d; 526169689Skan bool first_match = false; 527169689Skan bool found = false; 528169689Skan struct edge_prediction *pred; 529169689Skan int nedges = 0; 530169689Skan edge e, first = NULL, second = NULL; 531169689Skan edge_iterator ei; 532169689Skan 533169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 534169689Skan if (!(e->flags & (EDGE_EH | EDGE_FAKE))) 535169689Skan { 536169689Skan nedges ++; 537169689Skan if (first && !second) 538169689Skan second = e; 539169689Skan if (!first) 540169689Skan first = e; 541169689Skan } 542169689Skan 543169689Skan /* When there is no successor or only one choice, prediction is easy. 544169689Skan 545169689Skan We are lazy for now and predict only basic blocks with two outgoing 546169689Skan edges. It is possible to predict generic case too, but we have to 547169689Skan ignore first match heuristics and do more involved combining. Implement 548169689Skan this later. */ 549169689Skan if (nedges != 2) 550169689Skan { 551169689Skan if (!bb->count) 552169689Skan set_even_probabilities (bb); 553169689Skan bb->predictions = NULL; 554169689Skan if (dump_file) 555169689Skan fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n", 556169689Skan nedges, bb->index); 557169689Skan return; 558169689Skan } 559169689Skan 560169689Skan if (dump_file) 561169689Skan fprintf (dump_file, "Predictions for bb %i\n", bb->index); 562169689Skan 563169689Skan /* We implement "first match" heuristics and use probability guessed 564169689Skan by predictor with smallest index. */ 565169689Skan for (pred = bb->predictions; pred; pred = pred->ep_next) 566169689Skan { 567169689Skan int predictor = pred->ep_predictor; 568169689Skan int probability = pred->ep_probability; 569169689Skan 570169689Skan if (pred->ep_edge != first) 571169689Skan probability = REG_BR_PROB_BASE - probability; 572169689Skan 573169689Skan found = true; 574169689Skan if (best_predictor > predictor) 575169689Skan best_probability = probability, best_predictor = predictor; 576169689Skan 577169689Skan d = (combined_probability * probability 578169689Skan + (REG_BR_PROB_BASE - combined_probability) 579169689Skan * (REG_BR_PROB_BASE - probability)); 580169689Skan 581169689Skan /* Use FP math to avoid overflows of 32bit integers. */ 582169689Skan if (d == 0) 583169689Skan /* If one probability is 0% and one 100%, avoid division by zero. */ 584169689Skan combined_probability = REG_BR_PROB_BASE / 2; 585169689Skan else 586169689Skan combined_probability = (((double) combined_probability) * probability 587169689Skan * REG_BR_PROB_BASE / d + 0.5); 588169689Skan } 589169689Skan 590169689Skan /* Decide which heuristic to use. In case we didn't match anything, 591169689Skan use no_prediction heuristic, in case we did match, use either 592169689Skan first match or Dempster-Shaffer theory depending on the flags. */ 593169689Skan 594169689Skan if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH) 595169689Skan first_match = true; 596169689Skan 597169689Skan if (!found) 598169689Skan dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true); 599169689Skan else 600169689Skan { 601169689Skan dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb, 602169689Skan !first_match); 603169689Skan dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb, 604169689Skan first_match); 605169689Skan } 606169689Skan 607169689Skan if (first_match) 608169689Skan combined_probability = best_probability; 609169689Skan dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true); 610169689Skan 611169689Skan for (pred = bb->predictions; pred; pred = pred->ep_next) 612169689Skan { 613169689Skan int predictor = pred->ep_predictor; 614169689Skan int probability = pred->ep_probability; 615169689Skan 616169689Skan if (pred->ep_edge != EDGE_SUCC (bb, 0)) 617169689Skan probability = REG_BR_PROB_BASE - probability; 618169689Skan dump_prediction (dump_file, predictor, probability, bb, 619169689Skan !first_match || best_predictor == predictor); 620169689Skan } 621169689Skan bb->predictions = NULL; 622169689Skan 623169689Skan if (!bb->count) 624169689Skan { 625169689Skan first->probability = combined_probability; 626169689Skan second->probability = REG_BR_PROB_BASE - combined_probability; 627169689Skan } 628169689Skan} 629169689Skan 630169689Skan/* Predict edge probabilities by exploiting loop structure. 631169689Skan When RTLSIMPLELOOPS is set, attempt to count number of iterations by analyzing 632169689Skan RTL otherwise use tree based approach. */ 633169689Skanstatic void 634169689Skanpredict_loops (struct loops *loops_info, bool rtlsimpleloops) 635169689Skan{ 636132718Skan unsigned i; 63790075Sobrien 638169689Skan if (!rtlsimpleloops) 639169689Skan scev_initialize (loops_info); 64090075Sobrien 64190075Sobrien /* Try to predict out blocks in a loop that are not part of a 64290075Sobrien natural loop. */ 643117395Skan for (i = 1; i < loops_info->num; i++) 64490075Sobrien { 645117395Skan basic_block bb, *bbs; 646132718Skan unsigned j; 647169689Skan unsigned n_exits; 648117395Skan struct loop *loop = loops_info->parray[i]; 649169689Skan struct niter_desc desc; 650132718Skan unsigned HOST_WIDE_INT niter; 651169689Skan edge *exits; 65290075Sobrien 653169689Skan exits = get_loop_exit_edges (loop, &n_exits); 65490075Sobrien 655169689Skan if (rtlsimpleloops) 656132718Skan { 657169689Skan iv_analysis_loop_init (loop); 658169689Skan find_simple_exit (loop, &desc); 659132718Skan 660169689Skan if (desc.simple_p && desc.const_iter) 661169689Skan { 662169689Skan int prob; 663169689Skan niter = desc.niter + 1; 664169689Skan if (niter == 0) /* We might overflow here. */ 665169689Skan niter = desc.niter; 666169689Skan if (niter 667169689Skan > (unsigned int) PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS)) 668169689Skan niter = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS); 669169689Skan 670169689Skan prob = (REG_BR_PROB_BASE 671169689Skan - (REG_BR_PROB_BASE + niter /2) / niter); 672169689Skan /* Branch prediction algorithm gives 0 frequency for everything 673169689Skan after the end of loop for loop having 0 probability to finish. */ 674169689Skan if (prob == REG_BR_PROB_BASE) 675169689Skan prob = REG_BR_PROB_BASE - 1; 676169689Skan predict_edge (desc.in_edge, PRED_LOOP_ITERATIONS, 677169689Skan prob); 678169689Skan } 679132718Skan } 680169689Skan else 681169689Skan { 682169689Skan struct tree_niter_desc niter_desc; 683132718Skan 684169689Skan for (j = 0; j < n_exits; j++) 685169689Skan { 686169689Skan tree niter = NULL; 687169689Skan 688169689Skan if (number_of_iterations_exit (loop, exits[j], &niter_desc, false)) 689169689Skan niter = niter_desc.niter; 690169689Skan if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST) 691169689Skan niter = loop_niter_by_eval (loop, exits[j]); 692169689Skan 693169689Skan if (TREE_CODE (niter) == INTEGER_CST) 694169689Skan { 695169689Skan int probability; 696169689Skan int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS); 697169689Skan if (host_integerp (niter, 1) 698169689Skan && tree_int_cst_lt (niter, 699169689Skan build_int_cstu (NULL_TREE, max - 1))) 700169689Skan { 701169689Skan HOST_WIDE_INT nitercst = tree_low_cst (niter, 1) + 1; 702169689Skan probability = ((REG_BR_PROB_BASE + nitercst / 2) 703169689Skan / nitercst); 704169689Skan } 705169689Skan else 706169689Skan probability = ((REG_BR_PROB_BASE + max / 2) / max); 707169689Skan 708169689Skan predict_edge (exits[j], PRED_LOOP_ITERATIONS, probability); 709169689Skan } 710169689Skan } 711169689Skan 712169689Skan } 713169689Skan free (exits); 714169689Skan 715117395Skan bbs = get_loop_body (loop); 716169689Skan 717117395Skan for (j = 0; j < loop->num_nodes; j++) 718117395Skan { 719117395Skan int header_found = 0; 720117395Skan edge e; 721169689Skan edge_iterator ei; 72290075Sobrien 723117395Skan bb = bbs[j]; 72490075Sobrien 725117395Skan /* Bypass loop heuristics on continue statement. These 726117395Skan statements construct loops via "non-loop" constructs 727117395Skan in the source language and are better to be handled 728117395Skan separately. */ 729169689Skan if ((rtlsimpleloops && !can_predict_insn_p (BB_END (bb))) 730117395Skan || predicted_by_p (bb, PRED_CONTINUE)) 731117395Skan continue; 732117395Skan 733117395Skan /* Loop branch heuristics - predict an edge back to a 734117395Skan loop's head as taken. */ 735169689Skan if (bb == loop->latch) 736169689Skan { 737169689Skan e = find_edge (loop->latch, loop->header); 738169689Skan if (e) 739169689Skan { 740169689Skan header_found = 1; 741169689Skan predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN); 742169689Skan } 743169689Skan } 744117395Skan 745117395Skan /* Loop exit heuristics - predict an edge exiting the loop if the 746132718Skan conditional has no loop header successors as not taken. */ 747117395Skan if (!header_found) 748169689Skan { 749169689Skan /* For loop with many exits we don't want to predict all exits 750169689Skan with the pretty large probability, because if all exits are 751169689Skan considered in row, the loop would be predicted to iterate 752169689Skan almost never. The code to divide probability by number of 753169689Skan exits is very rough. It should compute the number of exits 754169689Skan taken in each patch through function (not the overall number 755169689Skan of exits that might be a lot higher for loops with wide switch 756169689Skan statements in them) and compute n-th square root. 757169689Skan 758169689Skan We limit the minimal probability by 2% to avoid 759169689Skan EDGE_PROBABILITY_RELIABLE from trusting the branch prediction 760169689Skan as this was causing regression in perl benchmark containing such 761169689Skan a wide loop. */ 762169689Skan 763169689Skan int probability = ((REG_BR_PROB_BASE 764169689Skan - predictor_info [(int) PRED_LOOP_EXIT].hitrate) 765169689Skan / n_exits); 766169689Skan if (probability < HITRATE (2)) 767169689Skan probability = HITRATE (2); 768169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 769169689Skan if (e->dest->index < NUM_FIXED_BLOCKS 770169689Skan || !flow_bb_inside_loop_p (loop, e->dest)) 771169689Skan predict_edge (e, PRED_LOOP_EXIT, probability); 772169689Skan } 773117395Skan } 774132718Skan 775132718Skan /* Free basic blocks from get_loop_body. */ 776132718Skan free (bbs); 77790075Sobrien } 77890075Sobrien 779169689Skan if (!rtlsimpleloops) 78090075Sobrien { 781169689Skan scev_finalize (); 782169689Skan current_loops = NULL; 783169689Skan } 784169689Skan} 78590075Sobrien 786169689Skan/* Attempt to predict probabilities of BB outgoing edges using local 787169689Skan properties. */ 788169689Skanstatic void 789169689Skanbb_estimate_probability_locally (basic_block bb) 790169689Skan{ 791169689Skan rtx last_insn = BB_END (bb); 792169689Skan rtx cond; 79390075Sobrien 794169689Skan if (! can_predict_insn_p (last_insn)) 795169689Skan return; 796169689Skan cond = get_condition (last_insn, NULL, false, false); 797169689Skan if (! cond) 798169689Skan return; 799169689Skan 800169689Skan /* Try "pointer heuristic." 801169689Skan A comparison ptr == 0 is predicted as false. 802169689Skan Similarly, a comparison ptr1 == ptr2 is predicted as false. */ 803169689Skan if (COMPARISON_P (cond) 804169689Skan && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0))) 805169689Skan || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1))))) 806169689Skan { 807169689Skan if (GET_CODE (cond) == EQ) 808169689Skan predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN); 809169689Skan else if (GET_CODE (cond) == NE) 810169689Skan predict_insn_def (last_insn, PRED_POINTER, TAKEN); 811169689Skan } 812169689Skan else 813169689Skan 814169689Skan /* Try "opcode heuristic." 815169689Skan EQ tests are usually false and NE tests are usually true. Also, 816169689Skan most quantities are positive, so we can make the appropriate guesses 817169689Skan about signed comparisons against zero. */ 818169689Skan switch (GET_CODE (cond)) 819169689Skan { 820169689Skan case CONST_INT: 821169689Skan /* Unconditional branch. */ 822169689Skan predict_insn_def (last_insn, PRED_UNCONDITIONAL, 823169689Skan cond == const0_rtx ? NOT_TAKEN : TAKEN); 824169689Skan break; 825169689Skan 826169689Skan case EQ: 827169689Skan case UNEQ: 828169689Skan /* Floating point comparisons appears to behave in a very 829169689Skan unpredictable way because of special role of = tests in 830169689Skan FP code. */ 831169689Skan if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) 832169689Skan ; 833169689Skan /* Comparisons with 0 are often used for booleans and there is 834169689Skan nothing useful to predict about them. */ 835169689Skan else if (XEXP (cond, 1) == const0_rtx 836169689Skan || XEXP (cond, 0) == const0_rtx) 837169689Skan ; 838169689Skan else 839169689Skan predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN); 840169689Skan break; 841169689Skan 842169689Skan case NE: 843169689Skan case LTGT: 844169689Skan /* Floating point comparisons appears to behave in a very 845169689Skan unpredictable way because of special role of = tests in 846169689Skan FP code. */ 847169689Skan if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) 848169689Skan ; 849169689Skan /* Comparisons with 0 are often used for booleans and there is 850169689Skan nothing useful to predict about them. */ 851169689Skan else if (XEXP (cond, 1) == const0_rtx 852169689Skan || XEXP (cond, 0) == const0_rtx) 853169689Skan ; 854169689Skan else 855169689Skan predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN); 856169689Skan break; 857169689Skan 858169689Skan case ORDERED: 859169689Skan predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN); 860169689Skan break; 861169689Skan 862169689Skan case UNORDERED: 863169689Skan predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN); 864169689Skan break; 865169689Skan 866169689Skan case LE: 867169689Skan case LT: 868169689Skan if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx 869169689Skan || XEXP (cond, 1) == constm1_rtx) 870169689Skan predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN); 871169689Skan break; 872169689Skan 873169689Skan case GE: 874169689Skan case GT: 875169689Skan if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx 876169689Skan || XEXP (cond, 1) == constm1_rtx) 877169689Skan predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN); 878169689Skan break; 879169689Skan 880169689Skan default: 881169689Skan break; 882169689Skan } 883169689Skan} 884169689Skan 885169689Skan/* Set edge->probability for each successor edge of BB. */ 886169689Skanvoid 887169689Skanguess_outgoing_edge_probabilities (basic_block bb) 888169689Skan{ 889169689Skan bb_estimate_probability_locally (bb); 890169689Skan combine_predictions_for_insn (BB_END (bb), bb); 891169689Skan} 892169689Skan 893169689Skan/* Return constant EXPR will likely have at execution time, NULL if unknown. 894169689Skan The function is used by builtin_expect branch predictor so the evidence 895169689Skan must come from this construct and additional possible constant folding. 896169689Skan 897169689Skan We may want to implement more involved value guess (such as value range 898169689Skan propagation based prediction), but such tricks shall go to new 899169689Skan implementation. */ 900169689Skan 901169689Skanstatic tree 902169689Skanexpr_expected_value (tree expr, bitmap visited) 903169689Skan{ 904169689Skan if (TREE_CONSTANT (expr)) 905169689Skan return expr; 906169689Skan else if (TREE_CODE (expr) == SSA_NAME) 907169689Skan { 908169689Skan tree def = SSA_NAME_DEF_STMT (expr); 909169689Skan 910169689Skan /* If we were already here, break the infinite cycle. */ 911169689Skan if (bitmap_bit_p (visited, SSA_NAME_VERSION (expr))) 912169689Skan return NULL; 913169689Skan bitmap_set_bit (visited, SSA_NAME_VERSION (expr)); 914169689Skan 915169689Skan if (TREE_CODE (def) == PHI_NODE) 91690075Sobrien { 917169689Skan /* All the arguments of the PHI node must have the same constant 918169689Skan length. */ 919169689Skan int i; 920169689Skan tree val = NULL, new_val; 92190075Sobrien 922169689Skan for (i = 0; i < PHI_NUM_ARGS (def); i++) 92390075Sobrien { 924169689Skan tree arg = PHI_ARG_DEF (def, i); 92590075Sobrien 926169689Skan /* If this PHI has itself as an argument, we cannot 927169689Skan determine the string length of this argument. However, 928169689Skan if we can find an expected constant value for the other 929169689Skan PHI args then we can still be sure that this is 930169689Skan likely a constant. So be optimistic and just 931169689Skan continue with the next argument. */ 932169689Skan if (arg == PHI_RESULT (def)) 933169689Skan continue; 934169689Skan 935169689Skan new_val = expr_expected_value (arg, visited); 936169689Skan if (!new_val) 937169689Skan return NULL; 938169689Skan if (!val) 939169689Skan val = new_val; 940169689Skan else if (!operand_equal_p (val, new_val, false)) 941169689Skan return NULL; 94290075Sobrien } 943169689Skan return val; 94490075Sobrien } 945169689Skan if (TREE_CODE (def) != MODIFY_EXPR || TREE_OPERAND (def, 0) != expr) 946169689Skan return NULL; 947169689Skan return expr_expected_value (TREE_OPERAND (def, 1), visited); 948169689Skan } 949169689Skan else if (TREE_CODE (expr) == CALL_EXPR) 950169689Skan { 951169689Skan tree decl = get_callee_fndecl (expr); 952169689Skan if (!decl) 953169689Skan return NULL; 954169689Skan if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL 955169689Skan && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT) 956169689Skan { 957169689Skan tree arglist = TREE_OPERAND (expr, 1); 958169689Skan tree val; 95990075Sobrien 960169689Skan if (arglist == NULL_TREE 961169689Skan || TREE_CHAIN (arglist) == NULL_TREE) 962169689Skan return NULL; 963169689Skan val = TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr, 1))); 964169689Skan if (TREE_CONSTANT (val)) 965169689Skan return val; 966169689Skan return TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr, 1))); 967169689Skan } 968169689Skan } 969169689Skan if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr)) 970169689Skan { 971169689Skan tree op0, op1, res; 972169689Skan op0 = expr_expected_value (TREE_OPERAND (expr, 0), visited); 973169689Skan if (!op0) 974169689Skan return NULL; 975169689Skan op1 = expr_expected_value (TREE_OPERAND (expr, 1), visited); 976169689Skan if (!op1) 977169689Skan return NULL; 978169689Skan res = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr), op0, op1); 979169689Skan if (TREE_CONSTANT (res)) 980169689Skan return res; 981169689Skan return NULL; 982169689Skan } 983169689Skan if (UNARY_CLASS_P (expr)) 984169689Skan { 985169689Skan tree op0, res; 986169689Skan op0 = expr_expected_value (TREE_OPERAND (expr, 0), visited); 987169689Skan if (!op0) 988169689Skan return NULL; 989169689Skan res = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr), op0); 990169689Skan if (TREE_CONSTANT (res)) 991169689Skan return res; 992169689Skan return NULL; 993169689Skan } 994169689Skan return NULL; 995169689Skan} 996169689Skan 997169689Skan/* Get rid of all builtin_expect calls we no longer need. */ 998169689Skanstatic void 999169689Skanstrip_builtin_expect (void) 1000169689Skan{ 1001169689Skan basic_block bb; 1002169689Skan FOR_EACH_BB (bb) 1003169689Skan { 1004169689Skan block_stmt_iterator bi; 1005169689Skan for (bi = bsi_start (bb); !bsi_end_p (bi); bsi_next (&bi)) 1006169689Skan { 1007169689Skan tree stmt = bsi_stmt (bi); 1008169689Skan tree fndecl; 1009169689Skan tree arglist; 101090075Sobrien 1011169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 1012169689Skan && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR 1013169689Skan && (fndecl = get_callee_fndecl (TREE_OPERAND (stmt, 1))) 1014169689Skan && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL 1015169689Skan && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT 1016169689Skan && (arglist = TREE_OPERAND (TREE_OPERAND (stmt, 1), 1)) 1017169689Skan && TREE_CHAIN (arglist)) 1018169689Skan { 1019169689Skan TREE_OPERAND (stmt, 1) = TREE_VALUE (arglist); 1020169689Skan update_stmt (stmt); 1021169689Skan } 102290075Sobrien } 1023169689Skan } 1024169689Skan} 1025169689Skan 1026169689Skan/* Predict using opcode of the last statement in basic block. */ 1027169689Skanstatic void 1028169689Skantree_predict_by_opcode (basic_block bb) 1029169689Skan{ 1030169689Skan tree stmt = last_stmt (bb); 1031169689Skan edge then_edge; 1032169689Skan tree cond; 1033169689Skan tree op0; 1034169689Skan tree type; 1035169689Skan tree val; 1036169689Skan bitmap visited; 1037169689Skan edge_iterator ei; 1038169689Skan 1039169689Skan if (!stmt || TREE_CODE (stmt) != COND_EXPR) 1040169689Skan return; 1041169689Skan FOR_EACH_EDGE (then_edge, ei, bb->succs) 1042169689Skan if (then_edge->flags & EDGE_TRUE_VALUE) 1043169689Skan break; 1044169689Skan cond = TREE_OPERAND (stmt, 0); 1045169689Skan if (!COMPARISON_CLASS_P (cond)) 1046169689Skan return; 1047169689Skan op0 = TREE_OPERAND (cond, 0); 1048169689Skan type = TREE_TYPE (op0); 1049169689Skan visited = BITMAP_ALLOC (NULL); 1050169689Skan val = expr_expected_value (cond, visited); 1051169689Skan BITMAP_FREE (visited); 1052169689Skan if (val) 1053169689Skan { 1054169689Skan if (integer_zerop (val)) 1055169689Skan predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN); 105690075Sobrien else 1057169689Skan predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN); 1058169689Skan return; 1059169689Skan } 1060169689Skan /* Try "pointer heuristic." 1061169689Skan A comparison ptr == 0 is predicted as false. 1062169689Skan Similarly, a comparison ptr1 == ptr2 is predicted as false. */ 1063169689Skan if (POINTER_TYPE_P (type)) 1064169689Skan { 1065169689Skan if (TREE_CODE (cond) == EQ_EXPR) 1066169689Skan predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN); 1067169689Skan else if (TREE_CODE (cond) == NE_EXPR) 1068169689Skan predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN); 1069169689Skan } 1070169689Skan else 107190075Sobrien 1072169689Skan /* Try "opcode heuristic." 1073169689Skan EQ tests are usually false and NE tests are usually true. Also, 1074169689Skan most quantities are positive, so we can make the appropriate guesses 1075169689Skan about signed comparisons against zero. */ 1076169689Skan switch (TREE_CODE (cond)) 1077169689Skan { 1078169689Skan case EQ_EXPR: 1079169689Skan case UNEQ_EXPR: 1080169689Skan /* Floating point comparisons appears to behave in a very 1081169689Skan unpredictable way because of special role of = tests in 1082169689Skan FP code. */ 1083169689Skan if (FLOAT_TYPE_P (type)) 1084169689Skan ; 1085169689Skan /* Comparisons with 0 are often used for booleans and there is 1086169689Skan nothing useful to predict about them. */ 1087169689Skan else if (integer_zerop (op0) 1088169689Skan || integer_zerop (TREE_OPERAND (cond, 1))) 1089169689Skan ; 1090169689Skan else 1091169689Skan predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN); 1092169689Skan break; 109390075Sobrien 1094169689Skan case NE_EXPR: 1095169689Skan case LTGT_EXPR: 1096169689Skan /* Floating point comparisons appears to behave in a very 1097169689Skan unpredictable way because of special role of = tests in 1098169689Skan FP code. */ 1099169689Skan if (FLOAT_TYPE_P (type)) 1100169689Skan ; 1101169689Skan /* Comparisons with 0 are often used for booleans and there is 1102169689Skan nothing useful to predict about them. */ 1103169689Skan else if (integer_zerop (op0) 1104169689Skan || integer_zerop (TREE_OPERAND (cond, 1))) 1105169689Skan ; 1106169689Skan else 1107169689Skan predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN); 1108169689Skan break; 110990075Sobrien 1110169689Skan case ORDERED_EXPR: 1111169689Skan predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN); 1112169689Skan break; 111390075Sobrien 1114169689Skan case UNORDERED_EXPR: 1115169689Skan predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN); 1116169689Skan break; 111790075Sobrien 1118169689Skan case LE_EXPR: 1119169689Skan case LT_EXPR: 1120169689Skan if (integer_zerop (TREE_OPERAND (cond, 1)) 1121169689Skan || integer_onep (TREE_OPERAND (cond, 1)) 1122169689Skan || integer_all_onesp (TREE_OPERAND (cond, 1)) 1123169689Skan || real_zerop (TREE_OPERAND (cond, 1)) 1124169689Skan || real_onep (TREE_OPERAND (cond, 1)) 1125169689Skan || real_minus_onep (TREE_OPERAND (cond, 1))) 1126169689Skan predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN); 1127169689Skan break; 112890075Sobrien 1129169689Skan case GE_EXPR: 1130169689Skan case GT_EXPR: 1131169689Skan if (integer_zerop (TREE_OPERAND (cond, 1)) 1132169689Skan || integer_onep (TREE_OPERAND (cond, 1)) 1133169689Skan || integer_all_onesp (TREE_OPERAND (cond, 1)) 1134169689Skan || real_zerop (TREE_OPERAND (cond, 1)) 1135169689Skan || real_onep (TREE_OPERAND (cond, 1)) 1136169689Skan || real_minus_onep (TREE_OPERAND (cond, 1))) 1137169689Skan predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN); 1138169689Skan break; 113990075Sobrien 1140169689Skan default: 1141169689Skan break; 1142169689Skan } 1143169689Skan} 114490075Sobrien 1145169689Skan/* Try to guess whether the value of return means error code. */ 1146169689Skanstatic enum br_predictor 1147169689Skanreturn_prediction (tree val, enum prediction *prediction) 1148169689Skan{ 1149169689Skan /* VOID. */ 1150169689Skan if (!val) 1151169689Skan return PRED_NO_PREDICTION; 1152169689Skan /* Different heuristics for pointers and scalars. */ 1153169689Skan if (POINTER_TYPE_P (TREE_TYPE (val))) 1154169689Skan { 1155169689Skan /* NULL is usually not returned. */ 1156169689Skan if (integer_zerop (val)) 1157169689Skan { 1158169689Skan *prediction = NOT_TAKEN; 1159169689Skan return PRED_NULL_RETURN; 1160169689Skan } 116190075Sobrien } 1162169689Skan else if (INTEGRAL_TYPE_P (TREE_TYPE (val))) 1163169689Skan { 1164169689Skan /* Negative return values are often used to indicate 1165169689Skan errors. */ 1166169689Skan if (TREE_CODE (val) == INTEGER_CST 1167169689Skan && tree_int_cst_sgn (val) < 0) 1168169689Skan { 1169169689Skan *prediction = NOT_TAKEN; 1170169689Skan return PRED_NEGATIVE_RETURN; 1171169689Skan } 1172169689Skan /* Constant return values seems to be commonly taken. 1173169689Skan Zero/one often represent booleans so exclude them from the 1174169689Skan heuristics. */ 1175169689Skan if (TREE_CONSTANT (val) 1176169689Skan && (!integer_zerop (val) && !integer_onep (val))) 1177169689Skan { 1178169689Skan *prediction = TAKEN; 1179169689Skan return PRED_NEGATIVE_RETURN; 1180169689Skan } 1181169689Skan } 1182169689Skan return PRED_NO_PREDICTION; 1183169689Skan} 118490075Sobrien 1185169689Skan/* Find the basic block with return expression and look up for possible 1186169689Skan return value trying to apply RETURN_PREDICTION heuristics. */ 1187169689Skanstatic void 1188169689Skanapply_return_prediction (int *heads) 1189169689Skan{ 1190169689Skan tree return_stmt = NULL; 1191169689Skan tree return_val; 1192169689Skan edge e; 1193169689Skan tree phi; 1194169689Skan int phi_num_args, i; 1195169689Skan enum br_predictor pred; 1196169689Skan enum prediction direction; 1197169689Skan edge_iterator ei; 1198169689Skan 1199169689Skan FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 1200169689Skan { 1201169689Skan return_stmt = last_stmt (e->src); 1202169689Skan if (TREE_CODE (return_stmt) == RETURN_EXPR) 1203169689Skan break; 1204169689Skan } 1205169689Skan if (!e) 1206169689Skan return; 1207169689Skan return_val = TREE_OPERAND (return_stmt, 0); 1208169689Skan if (!return_val) 1209169689Skan return; 1210169689Skan if (TREE_CODE (return_val) == MODIFY_EXPR) 1211169689Skan return_val = TREE_OPERAND (return_val, 1); 1212169689Skan if (TREE_CODE (return_val) != SSA_NAME 1213169689Skan || !SSA_NAME_DEF_STMT (return_val) 1214169689Skan || TREE_CODE (SSA_NAME_DEF_STMT (return_val)) != PHI_NODE) 1215169689Skan return; 1216169689Skan for (phi = SSA_NAME_DEF_STMT (return_val); phi; phi = PHI_CHAIN (phi)) 1217169689Skan if (PHI_RESULT (phi) == return_val) 1218169689Skan break; 1219169689Skan if (!phi) 1220169689Skan return; 1221169689Skan phi_num_args = PHI_NUM_ARGS (phi); 1222169689Skan pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction); 1223169689Skan 1224169689Skan /* Avoid the degenerate case where all return values form the function 1225169689Skan belongs to same category (ie they are all positive constants) 1226169689Skan so we can hardly say something about them. */ 1227169689Skan for (i = 1; i < phi_num_args; i++) 1228169689Skan if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction)) 1229169689Skan break; 1230169689Skan if (i != phi_num_args) 1231169689Skan for (i = 0; i < phi_num_args; i++) 1232169689Skan { 1233169689Skan pred = return_prediction (PHI_ARG_DEF (phi, i), &direction); 1234169689Skan if (pred != PRED_NO_PREDICTION) 1235169689Skan predict_paths_leading_to (PHI_ARG_EDGE (phi, i)->src, heads, pred, 1236169689Skan direction); 1237169689Skan } 1238169689Skan} 1239169689Skan 1240169689Skan/* Look for basic block that contains unlikely to happen events 1241169689Skan (such as noreturn calls) and mark all paths leading to execution 1242169689Skan of this basic blocks as unlikely. */ 1243169689Skan 1244169689Skanstatic void 1245169689Skantree_bb_level_predictions (void) 1246169689Skan{ 1247169689Skan basic_block bb; 1248169689Skan int *heads; 1249169689Skan 1250169689Skan heads = XNEWVEC (int, last_basic_block); 1251169689Skan memset (heads, ENTRY_BLOCK, sizeof (int) * last_basic_block); 1252169689Skan heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block; 1253169689Skan 1254169689Skan apply_return_prediction (heads); 1255169689Skan 1256117395Skan FOR_EACH_BB (bb) 1257169689Skan { 1258169689Skan block_stmt_iterator bsi = bsi_last (bb); 125990075Sobrien 1260169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1261169689Skan { 1262169689Skan tree stmt = bsi_stmt (bsi); 1263169689Skan switch (TREE_CODE (stmt)) 1264169689Skan { 1265169689Skan case MODIFY_EXPR: 1266169689Skan if (TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR) 1267169689Skan { 1268169689Skan stmt = TREE_OPERAND (stmt, 1); 1269169689Skan goto call_expr; 1270169689Skan } 1271169689Skan break; 1272169689Skan case CALL_EXPR: 1273169689Skancall_expr:; 1274169689Skan if (call_expr_flags (stmt) & ECF_NORETURN) 1275169689Skan predict_paths_leading_to (bb, heads, PRED_NORETURN, 1276169689Skan NOT_TAKEN); 1277169689Skan break; 1278169689Skan default: 1279169689Skan break; 1280169689Skan } 1281169689Skan } 1282169689Skan } 128390075Sobrien 1284169689Skan free (heads); 128590075Sobrien} 1286169689Skan 1287169689Skan/* Predict branch probabilities and estimate profile of the tree CFG. */ 1288169689Skanstatic unsigned int 1289169689Skantree_estimate_probability (void) 1290169689Skan{ 1291169689Skan basic_block bb; 1292169689Skan struct loops loops_info; 1293169689Skan 1294169689Skan flow_loops_find (&loops_info); 1295169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1296169689Skan flow_loops_dump (&loops_info, dump_file, NULL, 0); 1297169689Skan 1298169689Skan add_noreturn_fake_exit_edges (); 1299169689Skan connect_infinite_loops_to_exit (); 1300169689Skan calculate_dominance_info (CDI_DOMINATORS); 1301169689Skan calculate_dominance_info (CDI_POST_DOMINATORS); 1302169689Skan 1303169689Skan tree_bb_level_predictions (); 1304169689Skan 1305169689Skan mark_irreducible_loops (&loops_info); 1306169689Skan predict_loops (&loops_info, false); 1307169689Skan 1308169689Skan FOR_EACH_BB (bb) 1309169689Skan { 1310169689Skan edge e; 1311169689Skan edge_iterator ei; 1312169689Skan 1313169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1314169689Skan { 1315169689Skan /* Predict early returns to be probable, as we've already taken 1316169689Skan care for error returns and other cases are often used for 1317169689Skan fast paths through function. */ 1318169689Skan if (e->dest == EXIT_BLOCK_PTR 1319169689Skan && TREE_CODE (last_stmt (bb)) == RETURN_EXPR 1320169689Skan && !single_pred_p (bb)) 1321169689Skan { 1322169689Skan edge e1; 1323169689Skan edge_iterator ei1; 1324169689Skan 1325169689Skan FOR_EACH_EDGE (e1, ei1, bb->preds) 1326169689Skan if (!predicted_by_p (e1->src, PRED_NULL_RETURN) 1327169689Skan && !predicted_by_p (e1->src, PRED_CONST_RETURN) 1328169689Skan && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN) 1329169689Skan && !last_basic_block_p (e1->src)) 1330169689Skan predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN); 1331169689Skan } 1332169689Skan 1333169689Skan /* Look for block we are guarding (ie we dominate it, 1334169689Skan but it doesn't postdominate us). */ 1335169689Skan if (e->dest != EXIT_BLOCK_PTR && e->dest != bb 1336169689Skan && dominated_by_p (CDI_DOMINATORS, e->dest, e->src) 1337169689Skan && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest)) 1338169689Skan { 1339169689Skan block_stmt_iterator bi; 1340169689Skan 1341169689Skan /* The call heuristic claims that a guarded function call 1342169689Skan is improbable. This is because such calls are often used 1343169689Skan to signal exceptional situations such as printing error 1344169689Skan messages. */ 1345169689Skan for (bi = bsi_start (e->dest); !bsi_end_p (bi); 1346169689Skan bsi_next (&bi)) 1347169689Skan { 1348169689Skan tree stmt = bsi_stmt (bi); 1349169689Skan if ((TREE_CODE (stmt) == CALL_EXPR 1350169689Skan || (TREE_CODE (stmt) == MODIFY_EXPR 1351169689Skan && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)) 1352169689Skan /* Constant and pure calls are hardly used to signalize 1353169689Skan something exceptional. */ 1354169689Skan && TREE_SIDE_EFFECTS (stmt)) 1355169689Skan { 1356169689Skan predict_edge_def (e, PRED_CALL, NOT_TAKEN); 1357169689Skan break; 1358169689Skan } 1359169689Skan } 1360169689Skan } 1361169689Skan } 1362169689Skan tree_predict_by_opcode (bb); 1363169689Skan } 1364169689Skan FOR_EACH_BB (bb) 1365169689Skan combine_predictions_for_bb (bb); 1366169689Skan 1367169689Skan strip_builtin_expect (); 1368169689Skan estimate_bb_frequencies (&loops_info); 1369169689Skan free_dominance_info (CDI_POST_DOMINATORS); 1370169689Skan remove_fake_exit_edges (); 1371169689Skan flow_loops_free (&loops_info); 1372169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1373169689Skan dump_tree_cfg (dump_file, dump_flags); 1374169689Skan if (profile_status == PROFILE_ABSENT) 1375169689Skan profile_status = PROFILE_GUESSED; 1376169689Skan return 0; 1377169689Skan} 137890075Sobrien 137990075Sobrien/* __builtin_expect dropped tokens into the insn stream describing expected 138090075Sobrien values of registers. Generate branch probabilities based off these 138190075Sobrien values. */ 138290075Sobrien 138390075Sobrienvoid 1384132718Skanexpected_value_to_br_prob (void) 138590075Sobrien{ 138690075Sobrien rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX; 138790075Sobrien 138890075Sobrien for (insn = get_insns (); insn ; insn = NEXT_INSN (insn)) 138990075Sobrien { 139090075Sobrien switch (GET_CODE (insn)) 139190075Sobrien { 139290075Sobrien case NOTE: 139390075Sobrien /* Look for expected value notes. */ 139490075Sobrien if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE) 139590075Sobrien { 139690075Sobrien ev = NOTE_EXPECTED_VALUE (insn); 139790075Sobrien ev_reg = XEXP (ev, 0); 139890075Sobrien delete_insn (insn); 139990075Sobrien } 140090075Sobrien continue; 140190075Sobrien 140290075Sobrien case CODE_LABEL: 140390075Sobrien /* Never propagate across labels. */ 140490075Sobrien ev = NULL_RTX; 140590075Sobrien continue; 140690075Sobrien 140790075Sobrien case JUMP_INSN: 140890075Sobrien /* Look for simple conditional branches. If we haven't got an 140990075Sobrien expected value yet, no point going further. */ 1410169689Skan if (!JUMP_P (insn) || ev == NULL_RTX 141190075Sobrien || ! any_condjump_p (insn)) 141290075Sobrien continue; 141390075Sobrien break; 141490075Sobrien 141590075Sobrien default: 141690075Sobrien /* Look for insns that clobber the EV register. */ 141790075Sobrien if (ev && reg_set_p (ev_reg, insn)) 141890075Sobrien ev = NULL_RTX; 141990075Sobrien continue; 142090075Sobrien } 142190075Sobrien 142290075Sobrien /* Collect the branch condition, hopefully relative to EV_REG. */ 142390075Sobrien /* ??? At present we'll miss things like 142490075Sobrien (expected_value (eq r70 0)) 142590075Sobrien (set r71 -1) 142690075Sobrien (set r80 (lt r70 r71)) 142790075Sobrien (set pc (if_then_else (ne r80 0) ...)) 142890075Sobrien as canonicalize_condition will render this to us as 142990075Sobrien (lt r70, r71) 143090075Sobrien Could use cselib to try and reduce this further. */ 143190075Sobrien cond = XEXP (SET_SRC (pc_set (insn)), 0); 1432169689Skan cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg, 1433169689Skan false, false); 143490075Sobrien if (! cond || XEXP (cond, 0) != ev_reg 143590075Sobrien || GET_CODE (XEXP (cond, 1)) != CONST_INT) 143690075Sobrien continue; 143790075Sobrien 143890075Sobrien /* Substitute and simplify. Given that the expression we're 143990075Sobrien building involves two constants, we should wind up with either 144090075Sobrien true or false. */ 144190075Sobrien cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode, 144290075Sobrien XEXP (ev, 1), XEXP (cond, 1)); 144390075Sobrien cond = simplify_rtx (cond); 144490075Sobrien 144590075Sobrien /* Turn the condition into a scaled branch probability. */ 1446169689Skan gcc_assert (cond == const_true_rtx || cond == const0_rtx); 144790075Sobrien predict_insn_def (insn, PRED_BUILTIN_EXPECT, 144890075Sobrien cond == const_true_rtx ? TAKEN : NOT_TAKEN); 144990075Sobrien } 145090075Sobrien} 145190075Sobrien 1452132718Skan/* Check whether this is the last basic block of function. Commonly 1453132718Skan there is one extra common cleanup block. */ 1454117395Skanstatic bool 1455132718Skanlast_basic_block_p (basic_block bb) 1456117395Skan{ 1457117395Skan if (bb == EXIT_BLOCK_PTR) 1458117395Skan return false; 1459117395Skan 1460117395Skan return (bb->next_bb == EXIT_BLOCK_PTR 1461117395Skan || (bb->next_bb->next_bb == EXIT_BLOCK_PTR 1462169689Skan && single_succ_p (bb) 1463169689Skan && single_succ (bb)->next_bb == EXIT_BLOCK_PTR)); 1464117395Skan} 1465117395Skan 1466132718Skan/* Sets branch probabilities according to PREDiction and 1467132718Skan FLAGS. HEADS[bb->index] should be index of basic block in that we 1468132718Skan need to alter branch predictions (i.e. the first of our dominators 1469132718Skan such that we do not post-dominate it) (but we fill this information 1470132718Skan on demand, so -1 may be there in case this was not needed yet). */ 1471117395Skan 1472117395Skanstatic void 1473169689Skanpredict_paths_leading_to (basic_block bb, int *heads, enum br_predictor pred, 1474169689Skan enum prediction taken) 1475117395Skan{ 1476117395Skan edge e; 1477169689Skan edge_iterator ei; 1478117395Skan int y; 1479117395Skan 1480169689Skan if (heads[bb->index] == ENTRY_BLOCK) 1481117395Skan { 1482117395Skan /* This is first time we need this field in heads array; so 1483117395Skan find first dominator that we do not post-dominate (we are 1484117395Skan using already known members of heads array). */ 1485117395Skan basic_block ai = bb; 1486132718Skan basic_block next_ai = get_immediate_dominator (CDI_DOMINATORS, bb); 1487117395Skan int head; 1488117395Skan 1489169689Skan while (heads[next_ai->index] == ENTRY_BLOCK) 1490117395Skan { 1491132718Skan if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb)) 1492117395Skan break; 1493117395Skan heads[next_ai->index] = ai->index; 1494117395Skan ai = next_ai; 1495132718Skan next_ai = get_immediate_dominator (CDI_DOMINATORS, next_ai); 1496117395Skan } 1497132718Skan if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb)) 1498117395Skan head = next_ai->index; 1499117395Skan else 1500117395Skan head = heads[next_ai->index]; 1501117395Skan while (next_ai != bb) 1502117395Skan { 1503117395Skan next_ai = ai; 1504169689Skan ai = BASIC_BLOCK (heads[ai->index]); 1505117395Skan heads[next_ai->index] = head; 1506117395Skan } 1507117395Skan } 1508117395Skan y = heads[bb->index]; 1509117395Skan 1510117395Skan /* Now find the edge that leads to our branch and aply the prediction. */ 1511117395Skan 1512169689Skan if (y == last_basic_block) 1513117395Skan return; 1514169689Skan FOR_EACH_EDGE (e, ei, BASIC_BLOCK (y)->succs) 1515169689Skan if (e->dest->index >= NUM_FIXED_BLOCKS 1516132718Skan && dominated_by_p (CDI_POST_DOMINATORS, e->dest, bb)) 1517117395Skan predict_edge_def (e, pred, taken); 1518117395Skan} 1519117395Skan 152090075Sobrien/* This is used to carry information about basic blocks. It is 152190075Sobrien attached to the AUX field of the standard CFG block. */ 152290075Sobrien 152390075Sobrientypedef struct block_info_def 152490075Sobrien{ 152590075Sobrien /* Estimated frequency of execution of basic_block. */ 1526132718Skan sreal frequency; 152790075Sobrien 152890075Sobrien /* To keep queue of basic blocks to process. */ 152990075Sobrien basic_block next; 153090075Sobrien 153190075Sobrien /* Number of predecessors we need to visit first. */ 153290075Sobrien int npredecessors; 153390075Sobrien} *block_info; 153490075Sobrien 153590075Sobrien/* Similar information for edges. */ 153690075Sobrientypedef struct edge_info_def 153790075Sobrien{ 1538169689Skan /* In case edge is a loopback edge, the probability edge will be reached 153990075Sobrien in case header is. Estimated number of iterations of the loop can be 1540117395Skan then computed as 1 / (1 - back_edge_prob). */ 1541132718Skan sreal back_edge_prob; 1542169689Skan /* True if the edge is a loopback edge in the natural loop. */ 1543132718Skan unsigned int back_edge:1; 154490075Sobrien} *edge_info; 154590075Sobrien 154690075Sobrien#define BLOCK_INFO(B) ((block_info) (B)->aux) 154790075Sobrien#define EDGE_INFO(E) ((edge_info) (E)->aux) 154890075Sobrien 154990075Sobrien/* Helper function for estimate_bb_frequencies. 1550117395Skan Propagate the frequencies for LOOP. */ 155190075Sobrien 155290075Sobrienstatic void 1553169689Skanpropagate_freq (struct loop *loop, bitmap tovisit) 155490075Sobrien{ 1555117395Skan basic_block head = loop->header; 1556117395Skan basic_block bb; 1557117395Skan basic_block last; 1558169689Skan unsigned i; 155990075Sobrien edge e; 156090075Sobrien basic_block nextbb; 1561169689Skan bitmap_iterator bi; 156290075Sobrien 156390075Sobrien /* For each basic block we need to visit count number of his predecessors 156490075Sobrien we need to visit first. */ 1565169689Skan EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi) 156690075Sobrien { 1567169689Skan edge_iterator ei; 1568169689Skan int count = 0; 1569169689Skan 1570169689Skan /* The outermost "loop" includes the exit block, which we can not 1571169689Skan look up via BASIC_BLOCK. Detect this and use EXIT_BLOCK_PTR 1572169689Skan directly. Do the same for the entry block. */ 1573169689Skan bb = BASIC_BLOCK (i); 1574169689Skan 1575169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 157690075Sobrien { 1577169689Skan bool visit = bitmap_bit_p (tovisit, e->src->index); 157890075Sobrien 1579169689Skan if (visit && !(e->flags & EDGE_DFS_BACK)) 1580169689Skan count++; 1581169689Skan else if (visit && dump_file && !EDGE_INFO (e)->back_edge) 1582169689Skan fprintf (dump_file, 1583169689Skan "Irreducible region hit, ignoring edge to %i->%i\n", 1584169689Skan e->src->index, bb->index); 158590075Sobrien } 1586169689Skan BLOCK_INFO (bb)->npredecessors = count; 158790075Sobrien } 158890075Sobrien 1589117395Skan memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one)); 1590117395Skan last = head; 1591117395Skan for (bb = head; bb; bb = nextbb) 159290075Sobrien { 1593169689Skan edge_iterator ei; 1594132718Skan sreal cyclic_probability, frequency; 159590075Sobrien 1596117395Skan memcpy (&cyclic_probability, &real_zero, sizeof (real_zero)); 1597117395Skan memcpy (&frequency, &real_zero, sizeof (real_zero)); 1598117395Skan 159990075Sobrien nextbb = BLOCK_INFO (bb)->next; 160090075Sobrien BLOCK_INFO (bb)->next = NULL; 160190075Sobrien 160290075Sobrien /* Compute frequency of basic block. */ 160390075Sobrien if (bb != head) 160490075Sobrien { 160590075Sobrien#ifdef ENABLE_CHECKING 1606169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 1607169689Skan gcc_assert (!bitmap_bit_p (tovisit, e->src->index) 1608169689Skan || (e->flags & EDGE_DFS_BACK)); 160990075Sobrien#endif 161090075Sobrien 1611169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 161290075Sobrien if (EDGE_INFO (e)->back_edge) 1613117395Skan { 1614132718Skan sreal_add (&cyclic_probability, &cyclic_probability, 1615132718Skan &EDGE_INFO (e)->back_edge_prob); 1616117395Skan } 161790075Sobrien else if (!(e->flags & EDGE_DFS_BACK)) 1618117395Skan { 1619132718Skan sreal tmp; 162090075Sobrien 1621117395Skan /* frequency += (e->probability 1622117395Skan * BLOCK_INFO (e->src)->frequency / 1623117395Skan REG_BR_PROB_BASE); */ 162490075Sobrien 1625132718Skan sreal_init (&tmp, e->probability, 0); 1626132718Skan sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency); 1627132718Skan sreal_mul (&tmp, &tmp, &real_inv_br_prob_base); 1628132718Skan sreal_add (&frequency, &frequency, &tmp); 1629117395Skan } 1630117395Skan 1631132718Skan if (sreal_compare (&cyclic_probability, &real_zero) == 0) 1632132718Skan { 1633132718Skan memcpy (&BLOCK_INFO (bb)->frequency, &frequency, 1634132718Skan sizeof (frequency)); 1635132718Skan } 1636117395Skan else 1637117395Skan { 1638132718Skan if (sreal_compare (&cyclic_probability, &real_almost_one) > 0) 1639132718Skan { 1640132718Skan memcpy (&cyclic_probability, &real_almost_one, 1641132718Skan sizeof (real_almost_one)); 1642132718Skan } 1643117395Skan 1644132718Skan /* BLOCK_INFO (bb)->frequency = frequency 1645132718Skan / (1 - cyclic_probability) */ 1646117395Skan 1647132718Skan sreal_sub (&cyclic_probability, &real_one, &cyclic_probability); 1648132718Skan sreal_div (&BLOCK_INFO (bb)->frequency, 1649132718Skan &frequency, &cyclic_probability); 1650117395Skan } 165190075Sobrien } 165290075Sobrien 1653169689Skan bitmap_clear_bit (tovisit, bb->index); 165490075Sobrien 1655169689Skan e = find_edge (bb, head); 1656169689Skan if (e) 1657169689Skan { 1658169689Skan sreal tmp; 1659169689Skan 1660169689Skan /* EDGE_INFO (e)->back_edge_prob 1661169689Skan = ((e->probability * BLOCK_INFO (bb)->frequency) 1662169689Skan / REG_BR_PROB_BASE); */ 1663169689Skan 1664169689Skan sreal_init (&tmp, e->probability, 0); 1665169689Skan sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency); 1666169689Skan sreal_mul (&EDGE_INFO (e)->back_edge_prob, 1667169689Skan &tmp, &real_inv_br_prob_base); 1668169689Skan } 166990075Sobrien 167090075Sobrien /* Propagate to successor blocks. */ 1671169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 167290075Sobrien if (!(e->flags & EDGE_DFS_BACK) 167390075Sobrien && BLOCK_INFO (e->dest)->npredecessors) 167490075Sobrien { 167590075Sobrien BLOCK_INFO (e->dest)->npredecessors--; 167690075Sobrien if (!BLOCK_INFO (e->dest)->npredecessors) 167790075Sobrien { 167890075Sobrien if (!nextbb) 167990075Sobrien nextbb = e->dest; 168090075Sobrien else 168190075Sobrien BLOCK_INFO (last)->next = e->dest; 1682169689Skan 168390075Sobrien last = e->dest; 168490075Sobrien } 1685169689Skan } 168690075Sobrien } 168790075Sobrien} 168890075Sobrien 168990075Sobrien/* Estimate probabilities of loopback edges in loops at same nest level. */ 169090075Sobrien 169190075Sobrienstatic void 1692169689Skanestimate_loops_at_level (struct loop *first_loop, bitmap tovisit) 169390075Sobrien{ 1694117395Skan struct loop *loop; 169590075Sobrien 169690075Sobrien for (loop = first_loop; loop; loop = loop->next) 169790075Sobrien { 169890075Sobrien edge e; 1699117395Skan basic_block *bbs; 1700132718Skan unsigned i; 170190075Sobrien 1702169689Skan estimate_loops_at_level (loop->inner, tovisit); 1703132718Skan 1704169689Skan /* Do not do this for dummy function loop. */ 1705169689Skan if (EDGE_COUNT (loop->latch->succs) > 0) 170690075Sobrien { 1707117395Skan /* Find current loop back edge and mark it. */ 1708117395Skan e = loop_latch_edge (loop); 1709117395Skan EDGE_INFO (e)->back_edge = 1; 1710117395Skan } 171190075Sobrien 1712117395Skan bbs = get_loop_body (loop); 1713117395Skan for (i = 0; i < loop->num_nodes; i++) 1714169689Skan bitmap_set_bit (tovisit, bbs[i]->index); 1715117395Skan free (bbs); 1716169689Skan propagate_freq (loop, tovisit); 171790075Sobrien } 171890075Sobrien} 171990075Sobrien 1720169689Skan/* Convert counts measured by profile driven feedback to frequencies. 1721169689Skan Return nonzero iff there was any nonzero execution count. */ 172290075Sobrien 1723169689Skanint 1724132718Skancounts_to_freqs (void) 172590075Sobrien{ 1726169689Skan gcov_type count_max, true_count_max = 0; 1727117395Skan basic_block bb; 172890075Sobrien 1729117395Skan FOR_EACH_BB (bb) 1730169689Skan true_count_max = MAX (bb->count, true_count_max); 173190075Sobrien 1732169689Skan count_max = MAX (true_count_max, 1); 1733117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1734117395Skan bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max; 1735169689Skan return true_count_max; 173690075Sobrien} 173790075Sobrien 173890075Sobrien/* Return true if function is likely to be expensive, so there is no point to 173990075Sobrien optimize performance of prologue, epilogue or do inlining at the expense 1740132718Skan of code size growth. THRESHOLD is the limit of number of instructions 174190075Sobrien function can execute at average to be still considered not expensive. */ 174290075Sobrien 174390075Sobrienbool 1744132718Skanexpensive_function_p (int threshold) 174590075Sobrien{ 174690075Sobrien unsigned int sum = 0; 1747117395Skan basic_block bb; 174890075Sobrien unsigned int limit; 174990075Sobrien 175090075Sobrien /* We can not compute accurately for large thresholds due to scaled 175190075Sobrien frequencies. */ 1752169689Skan gcc_assert (threshold <= BB_FREQ_MAX); 175390075Sobrien 175490075Sobrien /* Frequencies are out of range. This either means that function contains 175590075Sobrien internal loop executing more than BB_FREQ_MAX times or profile feedback 175690075Sobrien is available and function has not been executed at all. */ 175790075Sobrien if (ENTRY_BLOCK_PTR->frequency == 0) 175890075Sobrien return true; 1759117395Skan 176090075Sobrien /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */ 176190075Sobrien limit = ENTRY_BLOCK_PTR->frequency * threshold; 1762117395Skan FOR_EACH_BB (bb) 176390075Sobrien { 176490075Sobrien rtx insn; 176590075Sobrien 1766132718Skan for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 176790075Sobrien insn = NEXT_INSN (insn)) 176890075Sobrien if (active_insn_p (insn)) 176990075Sobrien { 177090075Sobrien sum += bb->frequency; 177190075Sobrien if (sum > limit) 177290075Sobrien return true; 177390075Sobrien } 177490075Sobrien } 177590075Sobrien 177690075Sobrien return false; 177790075Sobrien} 177890075Sobrien 177990075Sobrien/* Estimate basic blocks frequency by given branch probabilities. */ 178090075Sobrien 178190075Sobrienstatic void 1782132718Skanestimate_bb_frequencies (struct loops *loops) 178390075Sobrien{ 1784117395Skan basic_block bb; 1785132718Skan sreal freq_max; 178690075Sobrien 1787169689Skan if (!flag_branch_probabilities || !counts_to_freqs ()) 178890075Sobrien { 1789132718Skan static int real_values_initialized = 0; 1790169689Skan bitmap tovisit; 179190075Sobrien 1792132718Skan if (!real_values_initialized) 1793132718Skan { 1794132718Skan real_values_initialized = 1; 1795132718Skan sreal_init (&real_zero, 0, 0); 1796132718Skan sreal_init (&real_one, 1, 0); 1797132718Skan sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0); 1798132718Skan sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0); 1799132718Skan sreal_init (&real_one_half, 1, -1); 1800132718Skan sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base); 1801132718Skan sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base); 1802132718Skan } 1803132718Skan 1804117395Skan mark_dfs_back_edges (); 180590075Sobrien 1806169689Skan single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE; 1807117395Skan 1808117395Skan /* Set up block info for each basic block. */ 1809169689Skan tovisit = BITMAP_ALLOC (NULL); 1810117395Skan alloc_aux_for_blocks (sizeof (struct block_info_def)); 1811117395Skan alloc_aux_for_edges (sizeof (struct edge_info_def)); 1812117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 181390075Sobrien { 1814117395Skan edge e; 1815169689Skan edge_iterator ei; 181690075Sobrien 1817169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1818117395Skan { 1819132718Skan sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0); 1820132718Skan sreal_mul (&EDGE_INFO (e)->back_edge_prob, 1821132718Skan &EDGE_INFO (e)->back_edge_prob, 1822132718Skan &real_inv_br_prob_base); 1823117395Skan } 182490075Sobrien } 182590075Sobrien 1826117395Skan /* First compute probabilities locally for each loop from innermost 1827117395Skan to outermost to examine probabilities for back edges. */ 1828169689Skan estimate_loops_at_level (loops->tree_root, tovisit); 182990075Sobrien 1830117395Skan memcpy (&freq_max, &real_zero, sizeof (real_zero)); 1831117395Skan FOR_EACH_BB (bb) 1832132718Skan if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0) 1833132718Skan memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max)); 183490075Sobrien 1835132718Skan sreal_div (&freq_max, &real_bb_freq_max, &freq_max); 1836117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1837117395Skan { 1838132718Skan sreal tmp; 183990075Sobrien 1840132718Skan sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max); 1841132718Skan sreal_add (&tmp, &tmp, &real_one_half); 1842132718Skan bb->frequency = sreal_to_int (&tmp); 1843117395Skan } 184490075Sobrien 1845117395Skan free_aux_for_blocks (); 1846117395Skan free_aux_for_edges (); 1847169689Skan BITMAP_FREE (tovisit); 1848117395Skan } 1849117395Skan compute_function_frequency (); 1850117395Skan if (flag_reorder_functions) 1851117395Skan choose_function_section (); 1852117395Skan} 185390075Sobrien 1854117395Skan/* Decide whether function is hot, cold or unlikely executed. */ 1855117395Skanstatic void 1856132718Skancompute_function_frequency (void) 1857117395Skan{ 1858117395Skan basic_block bb; 185990075Sobrien 1860132718Skan if (!profile_info || !flag_branch_probabilities) 1861117395Skan return; 1862117395Skan cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED; 1863117395Skan FOR_EACH_BB (bb) 186490075Sobrien { 1865117395Skan if (maybe_hot_bb_p (bb)) 1866117395Skan { 1867117395Skan cfun->function_frequency = FUNCTION_FREQUENCY_HOT; 1868117395Skan return; 1869117395Skan } 1870117395Skan if (!probably_never_executed_bb_p (bb)) 1871117395Skan cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL; 187290075Sobrien } 1873117395Skan} 187490075Sobrien 1875117395Skan/* Choose appropriate section for the function. */ 1876117395Skanstatic void 1877132718Skanchoose_function_section (void) 1878117395Skan{ 1879117395Skan if (DECL_SECTION_NAME (current_function_decl) 1880117395Skan || !targetm.have_named_sections 1881117395Skan /* Theoretically we can split the gnu.linkonce text section too, 1882132718Skan but this requires more work as the frequency needs to match 1883117395Skan for all generated objects so we need to merge the frequency 1884117395Skan of all instances. For now just never set frequency for these. */ 1885117395Skan || DECL_ONE_ONLY (current_function_decl)) 1886117395Skan return; 1887169689Skan 1888169689Skan /* If we are doing the partitioning optimization, let the optimization 1889169689Skan choose the correct section into which to put things. */ 1890169689Skan 1891169689Skan if (flag_reorder_blocks_and_partition) 1892169689Skan return; 1893169689Skan 1894117395Skan if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT) 1895117395Skan DECL_SECTION_NAME (current_function_decl) = 1896117395Skan build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME); 1897117395Skan if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED) 1898117395Skan DECL_SECTION_NAME (current_function_decl) = 1899117395Skan build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME), 1900117395Skan UNLIKELY_EXECUTED_TEXT_SECTION_NAME); 190190075Sobrien} 1902169689Skan 1903169689Skanstatic bool 1904169689Skangate_estimate_probability (void) 1905169689Skan{ 1906169689Skan return flag_guess_branch_prob; 1907169689Skan} 1908169689Skan 1909169689Skanstruct tree_opt_pass pass_profile = 1910169689Skan{ 1911169689Skan "profile", /* name */ 1912169689Skan gate_estimate_probability, /* gate */ 1913169689Skan tree_estimate_probability, /* execute */ 1914169689Skan NULL, /* sub */ 1915169689Skan NULL, /* next */ 1916169689Skan 0, /* static_pass_number */ 1917169689Skan TV_BRANCH_PROB, /* tv_id */ 1918169689Skan PROP_cfg, /* properties_required */ 1919169689Skan 0, /* properties_provided */ 1920169689Skan 0, /* properties_destroyed */ 1921169689Skan 0, /* todo_flags_start */ 1922169689Skan TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */ 1923169689Skan 0 /* letter */ 1924169689Skan}; 1925