predict.c revision 90075
190075Sobrien/* Branch prediction routines for the GNU compiler. 290075Sobrien Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc. 390075Sobrien 490075SobrienThis file is part of GCC. 590075Sobrien 690075SobrienGCC is free software; you can redistribute it and/or modify it under 790075Sobrienthe terms of the GNU General Public License as published by the Free 890075SobrienSoftware Foundation; either version 2, or (at your option) any later 990075Sobrienversion. 1090075Sobrien 1190075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1290075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1390075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1490075Sobrienfor more details. 1590075Sobrien 1690075SobrienYou should have received a copy of the GNU General Public License 1790075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 1890075SobrienSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 1990075Sobrien02111-1307, USA. */ 2090075Sobrien 2190075Sobrien/* References: 2290075Sobrien 2390075Sobrien [1] "Branch Prediction for Free" 2490075Sobrien Ball and Larus; PLDI '93. 2590075Sobrien [2] "Static Branch Frequency and Program Profile Analysis" 2690075Sobrien Wu and Larus; MICRO-27. 2790075Sobrien [3] "Corpus-based Static Branch Prediction" 2890075Sobrien Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */ 2990075Sobrien 3090075Sobrien 3190075Sobrien#include "config.h" 3290075Sobrien#include "system.h" 3390075Sobrien#include "tree.h" 3490075Sobrien#include "rtl.h" 3590075Sobrien#include "tm_p.h" 3690075Sobrien#include "hard-reg-set.h" 3790075Sobrien#include "basic-block.h" 3890075Sobrien#include "insn-config.h" 3990075Sobrien#include "regs.h" 4090075Sobrien#include "flags.h" 4190075Sobrien#include "output.h" 4290075Sobrien#include "function.h" 4390075Sobrien#include "except.h" 4490075Sobrien#include "toplev.h" 4590075Sobrien#include "recog.h" 4690075Sobrien#include "expr.h" 4790075Sobrien#include "predict.h" 4890075Sobrien 4990075Sobrien/* Random guesstimation given names. */ 5090075Sobrien#define PROB_NEVER (0) 5190075Sobrien#define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1) 5290075Sobrien#define PROB_UNLIKELY (REG_BR_PROB_BASE * 4 / 10 - 1) 5390075Sobrien#define PROB_EVEN (REG_BR_PROB_BASE / 2) 5490075Sobrien#define PROB_LIKELY (REG_BR_PROB_BASE - PROB_UNLIKELY) 5590075Sobrien#define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY) 5690075Sobrien#define PROB_ALWAYS (REG_BR_PROB_BASE) 5790075Sobrien 5890075Sobrienstatic void combine_predictions_for_insn PARAMS ((rtx, basic_block)); 5990075Sobrienstatic void dump_prediction PARAMS ((enum br_predictor, int, 6090075Sobrien basic_block, int)); 6190075Sobrienstatic void estimate_loops_at_level PARAMS ((struct loop *loop)); 6290075Sobrienstatic void propagate_freq PARAMS ((basic_block)); 6390075Sobrienstatic void estimate_bb_frequencies PARAMS ((struct loops *)); 6490075Sobrienstatic void counts_to_freqs PARAMS ((void)); 6590075Sobrien 6690075Sobrien/* Information we hold about each branch predictor. 6790075Sobrien Filled using information from predict.def. */ 6890075Sobrien 6990075Sobrienstruct predictor_info 7090075Sobrien{ 7190075Sobrien const char *const name; /* Name used in the debugging dumps. */ 7290075Sobrien const int hitrate; /* Expected hitrate used by 7390075Sobrien predict_insn_def call. */ 7490075Sobrien const int flags; 7590075Sobrien}; 7690075Sobrien 7790075Sobrien/* Use given predictor without Dempster-Shaffer theory if it matches 7890075Sobrien using first_match heuristics. */ 7990075Sobrien#define PRED_FLAG_FIRST_MATCH 1 8090075Sobrien 8190075Sobrien/* Recompute hitrate in percent to our representation. */ 8290075Sobrien 8390075Sobrien#define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100) 8490075Sobrien 8590075Sobrien#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS}, 8690075Sobrienstatic const struct predictor_info predictor_info[]= { 8790075Sobrien#include "predict.def" 8890075Sobrien 8990075Sobrien /* Upper bound on predictors. */ 9090075Sobrien {NULL, 0, 0} 9190075Sobrien}; 9290075Sobrien#undef DEF_PREDICTOR 9390075Sobrien 9490075Sobrienvoid 9590075Sobrienpredict_insn (insn, predictor, probability) 9690075Sobrien rtx insn; 9790075Sobrien int probability; 9890075Sobrien enum br_predictor predictor; 9990075Sobrien{ 10090075Sobrien if (!any_condjump_p (insn)) 10190075Sobrien abort (); 10290075Sobrien 10390075Sobrien REG_NOTES (insn) 10490075Sobrien = gen_rtx_EXPR_LIST (REG_BR_PRED, 10590075Sobrien gen_rtx_CONCAT (VOIDmode, 10690075Sobrien GEN_INT ((int) predictor), 10790075Sobrien GEN_INT ((int) probability)), 10890075Sobrien REG_NOTES (insn)); 10990075Sobrien} 11090075Sobrien 11190075Sobrien/* Predict insn by given predictor. */ 11290075Sobrien 11390075Sobrienvoid 11490075Sobrienpredict_insn_def (insn, predictor, taken) 11590075Sobrien rtx insn; 11690075Sobrien enum br_predictor predictor; 11790075Sobrien enum prediction taken; 11890075Sobrien{ 11990075Sobrien int probability = predictor_info[(int) predictor].hitrate; 12090075Sobrien 12190075Sobrien if (taken != TAKEN) 12290075Sobrien probability = REG_BR_PROB_BASE - probability; 12390075Sobrien 12490075Sobrien predict_insn (insn, predictor, probability); 12590075Sobrien} 12690075Sobrien 12790075Sobrien/* Predict edge E with given probability if possible. */ 12890075Sobrien 12990075Sobrienvoid 13090075Sobrienpredict_edge (e, predictor, probability) 13190075Sobrien edge e; 13290075Sobrien int probability; 13390075Sobrien enum br_predictor predictor; 13490075Sobrien{ 13590075Sobrien rtx last_insn; 13690075Sobrien last_insn = e->src->end; 13790075Sobrien 13890075Sobrien /* We can store the branch prediction information only about 13990075Sobrien conditional jumps. */ 14090075Sobrien if (!any_condjump_p (last_insn)) 14190075Sobrien return; 14290075Sobrien 14390075Sobrien /* We always store probability of branching. */ 14490075Sobrien if (e->flags & EDGE_FALLTHRU) 14590075Sobrien probability = REG_BR_PROB_BASE - probability; 14690075Sobrien 14790075Sobrien predict_insn (last_insn, predictor, probability); 14890075Sobrien} 14990075Sobrien 15090075Sobrien/* Predict edge E by given predictor if possible. */ 15190075Sobrien 15290075Sobrienvoid 15390075Sobrienpredict_edge_def (e, predictor, taken) 15490075Sobrien edge e; 15590075Sobrien enum br_predictor predictor; 15690075Sobrien enum prediction taken; 15790075Sobrien{ 15890075Sobrien int probability = predictor_info[(int) predictor].hitrate; 15990075Sobrien 16090075Sobrien if (taken != TAKEN) 16190075Sobrien probability = REG_BR_PROB_BASE - probability; 16290075Sobrien 16390075Sobrien predict_edge (e, predictor, probability); 16490075Sobrien} 16590075Sobrien 16690075Sobrien/* Invert all branch predictions or probability notes in the INSN. This needs 16790075Sobrien to be done each time we invert the condition used by the jump. */ 16890075Sobrien 16990075Sobrienvoid 17090075Sobrieninvert_br_probabilities (insn) 17190075Sobrien rtx insn; 17290075Sobrien{ 17390075Sobrien rtx note; 17490075Sobrien 17590075Sobrien for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 17690075Sobrien if (REG_NOTE_KIND (note) == REG_BR_PROB) 17790075Sobrien XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0))); 17890075Sobrien else if (REG_NOTE_KIND (note) == REG_BR_PRED) 17990075Sobrien XEXP (XEXP (note, 0), 1) 18090075Sobrien = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1))); 18190075Sobrien} 18290075Sobrien 18390075Sobrien/* Dump information about the branch prediction to the output file. */ 18490075Sobrien 18590075Sobrienstatic void 18690075Sobriendump_prediction (predictor, probability, bb, used) 18790075Sobrien enum br_predictor predictor; 18890075Sobrien int probability; 18990075Sobrien basic_block bb; 19090075Sobrien int used; 19190075Sobrien{ 19290075Sobrien edge e = bb->succ; 19390075Sobrien 19490075Sobrien if (!rtl_dump_file) 19590075Sobrien return; 19690075Sobrien 19790075Sobrien while (e->flags & EDGE_FALLTHRU) 19890075Sobrien e = e->succ_next; 19990075Sobrien 20090075Sobrien fprintf (rtl_dump_file, " %s heuristics%s: %.1f%%", 20190075Sobrien predictor_info[predictor].name, 20290075Sobrien used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE); 20390075Sobrien 20490075Sobrien if (bb->count) 20590075Sobrien { 20690075Sobrien fprintf (rtl_dump_file, " exec "); 20790075Sobrien fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, bb->count); 20890075Sobrien fprintf (rtl_dump_file, " hit "); 20990075Sobrien fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, e->count); 21090075Sobrien fprintf (rtl_dump_file, " (%.1f%%)", e->count * 100.0 / bb->count); 21190075Sobrien } 21290075Sobrien 21390075Sobrien fprintf (rtl_dump_file, "\n"); 21490075Sobrien} 21590075Sobrien 21690075Sobrien/* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB 21790075Sobrien note if not already present. Remove now useless REG_BR_PRED notes. */ 21890075Sobrien 21990075Sobrienstatic void 22090075Sobriencombine_predictions_for_insn (insn, bb) 22190075Sobrien rtx insn; 22290075Sobrien basic_block bb; 22390075Sobrien{ 22490075Sobrien rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0); 22590075Sobrien rtx *pnote = ®_NOTES (insn); 22690075Sobrien rtx note; 22790075Sobrien int best_probability = PROB_EVEN; 22890075Sobrien int best_predictor = END_PREDICTORS; 22990075Sobrien int combined_probability = REG_BR_PROB_BASE / 2; 23090075Sobrien int d; 23190075Sobrien bool first_match = false; 23290075Sobrien bool found = false; 23390075Sobrien 23490075Sobrien if (rtl_dump_file) 23590075Sobrien fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn), 23690075Sobrien bb->index); 23790075Sobrien 23890075Sobrien /* We implement "first match" heuristics and use probability guessed 23990075Sobrien by predictor with smallest index. In the future we will use better 24090075Sobrien probability combination techniques. */ 24190075Sobrien for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 24290075Sobrien if (REG_NOTE_KIND (note) == REG_BR_PRED) 24390075Sobrien { 24490075Sobrien int predictor = INTVAL (XEXP (XEXP (note, 0), 0)); 24590075Sobrien int probability = INTVAL (XEXP (XEXP (note, 0), 1)); 24690075Sobrien 24790075Sobrien found = true; 24890075Sobrien if (best_predictor > predictor) 24990075Sobrien best_probability = probability, best_predictor = predictor; 25090075Sobrien 25190075Sobrien d = (combined_probability * probability 25290075Sobrien + (REG_BR_PROB_BASE - combined_probability) 25390075Sobrien * (REG_BR_PROB_BASE - probability)); 25490075Sobrien 25590075Sobrien /* Use FP math to avoid overflows of 32bit integers. */ 25690075Sobrien if (d == 0) 25790075Sobrien /* If one probability is 0% and one 100%, avoid division by zero. */ 25890075Sobrien combined_probability = REG_BR_PROB_BASE / 2; 25990075Sobrien else 26090075Sobrien combined_probability = (((double) combined_probability) * probability 26190075Sobrien * REG_BR_PROB_BASE / d + 0.5); 26290075Sobrien } 26390075Sobrien 26490075Sobrien /* Decide which heuristic to use. In case we didn't match anything, 26590075Sobrien use no_prediction heuristic, in case we did match, use either 26690075Sobrien first match or Dempster-Shaffer theory depending on the flags. */ 26790075Sobrien 26890075Sobrien if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH) 26990075Sobrien first_match = true; 27090075Sobrien 27190075Sobrien if (!found) 27290075Sobrien dump_prediction (PRED_NO_PREDICTION, combined_probability, bb, true); 27390075Sobrien else 27490075Sobrien { 27590075Sobrien dump_prediction (PRED_DS_THEORY, combined_probability, bb, !first_match); 27690075Sobrien dump_prediction (PRED_FIRST_MATCH, best_probability, bb, first_match); 27790075Sobrien } 27890075Sobrien 27990075Sobrien if (first_match) 28090075Sobrien combined_probability = best_probability; 28190075Sobrien dump_prediction (PRED_COMBINED, combined_probability, bb, true); 28290075Sobrien 28390075Sobrien while (*pnote) 28490075Sobrien { 28590075Sobrien if (REG_NOTE_KIND (*pnote) == REG_BR_PRED) 28690075Sobrien { 28790075Sobrien int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0)); 28890075Sobrien int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1)); 28990075Sobrien 29090075Sobrien dump_prediction (predictor, probability, bb, 29190075Sobrien !first_match || best_predictor == predictor); 29290075Sobrien *pnote = XEXP (*pnote, 1); 29390075Sobrien } 29490075Sobrien else 29590075Sobrien pnote = &XEXP (*pnote, 1); 29690075Sobrien } 29790075Sobrien 29890075Sobrien if (!prob_note) 29990075Sobrien { 30090075Sobrien REG_NOTES (insn) 30190075Sobrien = gen_rtx_EXPR_LIST (REG_BR_PROB, 30290075Sobrien GEN_INT (combined_probability), REG_NOTES (insn)); 30390075Sobrien 30490075Sobrien /* Save the prediction into CFG in case we are seeing non-degenerated 30590075Sobrien conditional jump. */ 30690075Sobrien if (bb->succ->succ_next) 30790075Sobrien { 30890075Sobrien BRANCH_EDGE (bb)->probability = combined_probability; 30990075Sobrien FALLTHRU_EDGE (bb)->probability 31090075Sobrien = REG_BR_PROB_BASE - combined_probability; 31190075Sobrien } 31290075Sobrien } 31390075Sobrien} 31490075Sobrien 31590075Sobrien/* Statically estimate the probability that a branch will be taken. 31690075Sobrien ??? In the next revision there will be a number of other predictors added 31790075Sobrien from the above references. Further, each heuristic will be factored out 31890075Sobrien into its own function for clarity (and to facilitate the combination of 31990075Sobrien predictions). */ 32090075Sobrien 32190075Sobrienvoid 32290075Sobrienestimate_probability (loops_info) 32390075Sobrien struct loops *loops_info; 32490075Sobrien{ 32590075Sobrien sbitmap *dominators, *post_dominators; 32690075Sobrien int i; 32790075Sobrien int found_noreturn = 0; 32890075Sobrien 32990075Sobrien dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); 33090075Sobrien post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); 33190075Sobrien calculate_dominance_info (NULL, dominators, CDI_DOMINATORS); 33290075Sobrien calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS); 33390075Sobrien 33490075Sobrien /* Try to predict out blocks in a loop that are not part of a 33590075Sobrien natural loop. */ 33690075Sobrien for (i = 0; i < loops_info->num; i++) 33790075Sobrien { 33890075Sobrien int j; 33990075Sobrien int exits; 34090075Sobrien struct loop *loop = &loops_info->array[i]; 34190075Sobrien 34290075Sobrien flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES); 34390075Sobrien exits = loop->num_exits; 34490075Sobrien 34590075Sobrien for (j = loop->first->index; j <= loop->last->index; ++j) 34690075Sobrien if (TEST_BIT (loop->nodes, j)) 34790075Sobrien { 34890075Sobrien int header_found = 0; 34990075Sobrien edge e; 35090075Sobrien 35190075Sobrien /* Loop branch heuristics - predict an edge back to a 35290075Sobrien loop's head as taken. */ 35390075Sobrien for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next) 35490075Sobrien if (e->dest == loop->header 35590075Sobrien && e->src == loop->latch) 35690075Sobrien { 35790075Sobrien header_found = 1; 35890075Sobrien predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN); 35990075Sobrien } 36090075Sobrien 36190075Sobrien /* Loop exit heuristics - predict an edge exiting the loop if the 36290075Sobrien conditinal has no loop header successors as not taken. */ 36390075Sobrien if (!header_found) 36490075Sobrien for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next) 36590075Sobrien if (e->dest->index < 0 36690075Sobrien || !TEST_BIT (loop->nodes, e->dest->index)) 36790075Sobrien predict_edge 36890075Sobrien (e, PRED_LOOP_EXIT, 36990075Sobrien (REG_BR_PROB_BASE 37090075Sobrien - predictor_info [(int) PRED_LOOP_EXIT].hitrate) 37190075Sobrien / exits); 37290075Sobrien } 37390075Sobrien } 37490075Sobrien 37590075Sobrien /* Attempt to predict conditional jumps using a number of heuristics. */ 37690075Sobrien for (i = 0; i < n_basic_blocks; i++) 37790075Sobrien { 37890075Sobrien basic_block bb = BASIC_BLOCK (i); 37990075Sobrien rtx last_insn = bb->end; 38090075Sobrien rtx cond, earliest; 38190075Sobrien edge e; 38290075Sobrien 38390075Sobrien /* If block has no successor, predict all possible paths to it as 38490075Sobrien improbable, as the block contains a call to a noreturn function and 38590075Sobrien thus can be executed only once. */ 38690075Sobrien if (bb->succ == NULL && !found_noreturn) 38790075Sobrien { 38890075Sobrien int y; 38990075Sobrien 39090075Sobrien /* ??? Postdominator claims each noreturn block to be postdominated 39190075Sobrien by each, so we need to run only once. This needs to be changed 39290075Sobrien once postdominace algorithm is updated to say something more 39390075Sobrien sane. */ 39490075Sobrien found_noreturn = 1; 39590075Sobrien for (y = 0; y < n_basic_blocks; y++) 39690075Sobrien if (!TEST_BIT (post_dominators[y], i)) 39790075Sobrien for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next) 39890075Sobrien if (e->dest->index >= 0 39990075Sobrien && TEST_BIT (post_dominators[e->dest->index], i)) 40090075Sobrien predict_edge_def (e, PRED_NORETURN, NOT_TAKEN); 40190075Sobrien } 40290075Sobrien 40390075Sobrien if (GET_CODE (last_insn) != JUMP_INSN || ! any_condjump_p (last_insn)) 40490075Sobrien continue; 40590075Sobrien 40690075Sobrien for (e = bb->succ; e; e = e->succ_next) 40790075Sobrien { 40890075Sobrien /* Predict edges to blocks that return immediately to be 40990075Sobrien improbable. These are usually used to signal error states. */ 41090075Sobrien if (e->dest == EXIT_BLOCK_PTR 41190075Sobrien || (e->dest->succ && !e->dest->succ->succ_next 41290075Sobrien && e->dest->succ->dest == EXIT_BLOCK_PTR)) 41390075Sobrien predict_edge_def (e, PRED_ERROR_RETURN, NOT_TAKEN); 41490075Sobrien 41590075Sobrien /* Look for block we are guarding (ie we dominate it, 41690075Sobrien but it doesn't postdominate us). */ 41790075Sobrien if (e->dest != EXIT_BLOCK_PTR && e->dest != bb 41890075Sobrien && TEST_BIT (dominators[e->dest->index], e->src->index) 41990075Sobrien && !TEST_BIT (post_dominators[e->src->index], e->dest->index)) 42090075Sobrien { 42190075Sobrien rtx insn; 42290075Sobrien 42390075Sobrien /* The call heuristic claims that a guarded function call 42490075Sobrien is improbable. This is because such calls are often used 42590075Sobrien to signal exceptional situations such as printing error 42690075Sobrien messages. */ 42790075Sobrien for (insn = e->dest->head; insn != NEXT_INSN (e->dest->end); 42890075Sobrien insn = NEXT_INSN (insn)) 42990075Sobrien if (GET_CODE (insn) == CALL_INSN 43090075Sobrien /* Constant and pure calls are hardly used to signalize 43190075Sobrien something exceptional. */ 43290075Sobrien && ! CONST_OR_PURE_CALL_P (insn)) 43390075Sobrien { 43490075Sobrien predict_edge_def (e, PRED_CALL, NOT_TAKEN); 43590075Sobrien break; 43690075Sobrien } 43790075Sobrien } 43890075Sobrien } 43990075Sobrien 44090075Sobrien cond = get_condition (last_insn, &earliest); 44190075Sobrien if (! cond) 44290075Sobrien continue; 44390075Sobrien 44490075Sobrien /* Try "pointer heuristic." 44590075Sobrien A comparison ptr == 0 is predicted as false. 44690075Sobrien Similarly, a comparison ptr1 == ptr2 is predicted as false. */ 44790075Sobrien if (GET_RTX_CLASS (GET_CODE (cond)) == '<' 44890075Sobrien && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0))) 44990075Sobrien || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1))))) 45090075Sobrien { 45190075Sobrien if (GET_CODE (cond) == EQ) 45290075Sobrien predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN); 45390075Sobrien else if (GET_CODE (cond) == NE) 45490075Sobrien predict_insn_def (last_insn, PRED_POINTER, TAKEN); 45590075Sobrien } 45690075Sobrien else 45790075Sobrien 45890075Sobrien /* Try "opcode heuristic." 45990075Sobrien EQ tests are usually false and NE tests are usually true. Also, 46090075Sobrien most quantities are positive, so we can make the appropriate guesses 46190075Sobrien about signed comparisons against zero. */ 46290075Sobrien switch (GET_CODE (cond)) 46390075Sobrien { 46490075Sobrien case CONST_INT: 46590075Sobrien /* Unconditional branch. */ 46690075Sobrien predict_insn_def (last_insn, PRED_UNCONDITIONAL, 46790075Sobrien cond == const0_rtx ? NOT_TAKEN : TAKEN); 46890075Sobrien break; 46990075Sobrien 47090075Sobrien case EQ: 47190075Sobrien case UNEQ: 47290075Sobrien /* Floating point comparisons appears to behave in a very 47390075Sobrien inpredictable way because of special role of = tests in 47490075Sobrien FP code. */ 47590075Sobrien if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) 47690075Sobrien ; 47790075Sobrien /* Comparisons with 0 are often used for booleans and there is 47890075Sobrien nothing usefull to predict about them. */ 47990075Sobrien else if (XEXP (cond, 1) == const0_rtx 48090075Sobrien || XEXP (cond, 0) == const0_rtx) 48190075Sobrien ; 48290075Sobrien else 48390075Sobrien predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN); 48490075Sobrien break; 48590075Sobrien 48690075Sobrien case NE: 48790075Sobrien case LTGT: 48890075Sobrien /* Floating point comparisons appears to behave in a very 48990075Sobrien inpredictable way because of special role of = tests in 49090075Sobrien FP code. */ 49190075Sobrien if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) 49290075Sobrien ; 49390075Sobrien /* Comparisons with 0 are often used for booleans and there is 49490075Sobrien nothing usefull to predict about them. */ 49590075Sobrien else if (XEXP (cond, 1) == const0_rtx 49690075Sobrien || XEXP (cond, 0) == const0_rtx) 49790075Sobrien ; 49890075Sobrien else 49990075Sobrien predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN); 50090075Sobrien break; 50190075Sobrien 50290075Sobrien case ORDERED: 50390075Sobrien predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN); 50490075Sobrien break; 50590075Sobrien 50690075Sobrien case UNORDERED: 50790075Sobrien predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN); 50890075Sobrien break; 50990075Sobrien 51090075Sobrien case LE: 51190075Sobrien case LT: 51290075Sobrien if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx 51390075Sobrien || XEXP (cond, 1) == constm1_rtx) 51490075Sobrien predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN); 51590075Sobrien break; 51690075Sobrien 51790075Sobrien case GE: 51890075Sobrien case GT: 51990075Sobrien if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx 52090075Sobrien || XEXP (cond, 1) == constm1_rtx) 52190075Sobrien predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN); 52290075Sobrien break; 52390075Sobrien 52490075Sobrien default: 52590075Sobrien break; 52690075Sobrien } 52790075Sobrien } 52890075Sobrien 52990075Sobrien /* Attach the combined probability to each conditional jump. */ 53090075Sobrien for (i = 0; i < n_basic_blocks; i++) 53190075Sobrien if (GET_CODE (BLOCK_END (i)) == JUMP_INSN 53290075Sobrien && any_condjump_p (BLOCK_END (i))) 53390075Sobrien combine_predictions_for_insn (BLOCK_END (i), BASIC_BLOCK (i)); 53490075Sobrien 53590075Sobrien sbitmap_vector_free (post_dominators); 53690075Sobrien sbitmap_vector_free (dominators); 53790075Sobrien 53890075Sobrien estimate_bb_frequencies (loops_info); 53990075Sobrien} 54090075Sobrien 54190075Sobrien/* __builtin_expect dropped tokens into the insn stream describing expected 54290075Sobrien values of registers. Generate branch probabilities based off these 54390075Sobrien values. */ 54490075Sobrien 54590075Sobrienvoid 54690075Sobrienexpected_value_to_br_prob () 54790075Sobrien{ 54890075Sobrien rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX; 54990075Sobrien 55090075Sobrien for (insn = get_insns (); insn ; insn = NEXT_INSN (insn)) 55190075Sobrien { 55290075Sobrien switch (GET_CODE (insn)) 55390075Sobrien { 55490075Sobrien case NOTE: 55590075Sobrien /* Look for expected value notes. */ 55690075Sobrien if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE) 55790075Sobrien { 55890075Sobrien ev = NOTE_EXPECTED_VALUE (insn); 55990075Sobrien ev_reg = XEXP (ev, 0); 56090075Sobrien delete_insn (insn); 56190075Sobrien } 56290075Sobrien continue; 56390075Sobrien 56490075Sobrien case CODE_LABEL: 56590075Sobrien /* Never propagate across labels. */ 56690075Sobrien ev = NULL_RTX; 56790075Sobrien continue; 56890075Sobrien 56990075Sobrien case JUMP_INSN: 57090075Sobrien /* Look for simple conditional branches. If we haven't got an 57190075Sobrien expected value yet, no point going further. */ 57290075Sobrien if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX 57390075Sobrien || ! any_condjump_p (insn)) 57490075Sobrien continue; 57590075Sobrien break; 57690075Sobrien 57790075Sobrien default: 57890075Sobrien /* Look for insns that clobber the EV register. */ 57990075Sobrien if (ev && reg_set_p (ev_reg, insn)) 58090075Sobrien ev = NULL_RTX; 58190075Sobrien continue; 58290075Sobrien } 58390075Sobrien 58490075Sobrien /* Collect the branch condition, hopefully relative to EV_REG. */ 58590075Sobrien /* ??? At present we'll miss things like 58690075Sobrien (expected_value (eq r70 0)) 58790075Sobrien (set r71 -1) 58890075Sobrien (set r80 (lt r70 r71)) 58990075Sobrien (set pc (if_then_else (ne r80 0) ...)) 59090075Sobrien as canonicalize_condition will render this to us as 59190075Sobrien (lt r70, r71) 59290075Sobrien Could use cselib to try and reduce this further. */ 59390075Sobrien cond = XEXP (SET_SRC (pc_set (insn)), 0); 59490075Sobrien cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg); 59590075Sobrien if (! cond || XEXP (cond, 0) != ev_reg 59690075Sobrien || GET_CODE (XEXP (cond, 1)) != CONST_INT) 59790075Sobrien continue; 59890075Sobrien 59990075Sobrien /* Substitute and simplify. Given that the expression we're 60090075Sobrien building involves two constants, we should wind up with either 60190075Sobrien true or false. */ 60290075Sobrien cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode, 60390075Sobrien XEXP (ev, 1), XEXP (cond, 1)); 60490075Sobrien cond = simplify_rtx (cond); 60590075Sobrien 60690075Sobrien /* Turn the condition into a scaled branch probability. */ 60790075Sobrien if (cond != const_true_rtx && cond != const0_rtx) 60890075Sobrien abort (); 60990075Sobrien predict_insn_def (insn, PRED_BUILTIN_EXPECT, 61090075Sobrien cond == const_true_rtx ? TAKEN : NOT_TAKEN); 61190075Sobrien } 61290075Sobrien} 61390075Sobrien 61490075Sobrien/* This is used to carry information about basic blocks. It is 61590075Sobrien attached to the AUX field of the standard CFG block. */ 61690075Sobrien 61790075Sobrientypedef struct block_info_def 61890075Sobrien{ 61990075Sobrien /* Estimated frequency of execution of basic_block. */ 62090075Sobrien volatile double frequency; 62190075Sobrien 62290075Sobrien /* To keep queue of basic blocks to process. */ 62390075Sobrien basic_block next; 62490075Sobrien 62590075Sobrien /* True if block needs to be visited in prop_freqency. */ 62690075Sobrien int tovisit:1; 62790075Sobrien 62890075Sobrien /* Number of predecessors we need to visit first. */ 62990075Sobrien int npredecessors; 63090075Sobrien} *block_info; 63190075Sobrien 63290075Sobrien/* Similar information for edges. */ 63390075Sobrientypedef struct edge_info_def 63490075Sobrien{ 63590075Sobrien /* In case edge is an loopback edge, the probability edge will be reached 63690075Sobrien in case header is. Estimated number of iterations of the loop can be 63790075Sobrien then computed as 1 / (1 - back_edge_prob). 63890075Sobrien 63990075Sobrien Volatile is needed to avoid differences in the optimized and unoptimized 64090075Sobrien builds on machines where FP registers are wider than double. */ 64190075Sobrien volatile double back_edge_prob; 64290075Sobrien /* True if the edge is an loopback edge in the natural loop. */ 64390075Sobrien int back_edge:1; 64490075Sobrien} *edge_info; 64590075Sobrien 64690075Sobrien#define BLOCK_INFO(B) ((block_info) (B)->aux) 64790075Sobrien#define EDGE_INFO(E) ((edge_info) (E)->aux) 64890075Sobrien 64990075Sobrien/* Helper function for estimate_bb_frequencies. 65090075Sobrien Propagate the frequencies for loops headed by HEAD. */ 65190075Sobrien 65290075Sobrienstatic void 65390075Sobrienpropagate_freq (head) 65490075Sobrien basic_block head; 65590075Sobrien{ 65690075Sobrien basic_block bb = head; 65790075Sobrien basic_block last = bb; 65890075Sobrien edge e; 65990075Sobrien basic_block nextbb; 66090075Sobrien int n; 66190075Sobrien 66290075Sobrien /* For each basic block we need to visit count number of his predecessors 66390075Sobrien we need to visit first. */ 66490075Sobrien for (n = 0; n < n_basic_blocks; n++) 66590075Sobrien { 66690075Sobrien basic_block bb = BASIC_BLOCK (n); 66790075Sobrien if (BLOCK_INFO (bb)->tovisit) 66890075Sobrien { 66990075Sobrien int count = 0; 67090075Sobrien 67190075Sobrien for (e = bb->pred; e; e = e->pred_next) 67290075Sobrien if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK)) 67390075Sobrien count++; 67490075Sobrien else if (BLOCK_INFO (e->src)->tovisit 67590075Sobrien && rtl_dump_file && !EDGE_INFO (e)->back_edge) 67690075Sobrien fprintf (rtl_dump_file, 67790075Sobrien "Irreducible region hit, ignoring edge to %i->%i\n", 67890075Sobrien e->src->index, bb->index); 67990075Sobrien BLOCK_INFO (bb)->npredecessors = count; 68090075Sobrien } 68190075Sobrien } 68290075Sobrien 68390075Sobrien BLOCK_INFO (head)->frequency = 1; 68490075Sobrien for (; bb; bb = nextbb) 68590075Sobrien { 68690075Sobrien double cyclic_probability = 0, frequency = 0; 68790075Sobrien 68890075Sobrien nextbb = BLOCK_INFO (bb)->next; 68990075Sobrien BLOCK_INFO (bb)->next = NULL; 69090075Sobrien 69190075Sobrien /* Compute frequency of basic block. */ 69290075Sobrien if (bb != head) 69390075Sobrien { 69490075Sobrien#ifdef ENABLE_CHECKING 69590075Sobrien for (e = bb->pred; e; e = e->pred_next) 69690075Sobrien if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK)) 69790075Sobrien abort (); 69890075Sobrien#endif 69990075Sobrien 70090075Sobrien for (e = bb->pred; e; e = e->pred_next) 70190075Sobrien if (EDGE_INFO (e)->back_edge) 70290075Sobrien cyclic_probability += EDGE_INFO (e)->back_edge_prob; 70390075Sobrien else if (!(e->flags & EDGE_DFS_BACK)) 70490075Sobrien frequency += (e->probability 70590075Sobrien * BLOCK_INFO (e->src)->frequency / 70690075Sobrien REG_BR_PROB_BASE); 70790075Sobrien 70890075Sobrien if (cyclic_probability > 1.0 - 1.0 / REG_BR_PROB_BASE) 70990075Sobrien cyclic_probability = 1.0 - 1.0 / REG_BR_PROB_BASE; 71090075Sobrien 71190075Sobrien BLOCK_INFO (bb)->frequency = frequency / (1 - cyclic_probability); 71290075Sobrien } 71390075Sobrien 71490075Sobrien BLOCK_INFO (bb)->tovisit = 0; 71590075Sobrien 71690075Sobrien /* Compute back edge frequencies. */ 71790075Sobrien for (e = bb->succ; e; e = e->succ_next) 71890075Sobrien if (e->dest == head) 71990075Sobrien EDGE_INFO (e)->back_edge_prob 72090075Sobrien = ((e->probability * BLOCK_INFO (bb)->frequency) 72190075Sobrien / REG_BR_PROB_BASE); 72290075Sobrien 72390075Sobrien /* Propagate to successor blocks. */ 72490075Sobrien for (e = bb->succ; e; e = e->succ_next) 72590075Sobrien if (!(e->flags & EDGE_DFS_BACK) 72690075Sobrien && BLOCK_INFO (e->dest)->npredecessors) 72790075Sobrien { 72890075Sobrien BLOCK_INFO (e->dest)->npredecessors--; 72990075Sobrien if (!BLOCK_INFO (e->dest)->npredecessors) 73090075Sobrien { 73190075Sobrien if (!nextbb) 73290075Sobrien nextbb = e->dest; 73390075Sobrien else 73490075Sobrien BLOCK_INFO (last)->next = e->dest; 73590075Sobrien 73690075Sobrien last = e->dest; 73790075Sobrien } 73890075Sobrien } 73990075Sobrien } 74090075Sobrien} 74190075Sobrien 74290075Sobrien/* Estimate probabilities of loopback edges in loops at same nest level. */ 74390075Sobrien 74490075Sobrienstatic void 74590075Sobrienestimate_loops_at_level (first_loop) 74690075Sobrien struct loop *first_loop; 74790075Sobrien{ 74890075Sobrien struct loop *l, *loop = first_loop; 74990075Sobrien 75090075Sobrien for (loop = first_loop; loop; loop = loop->next) 75190075Sobrien { 75290075Sobrien int n; 75390075Sobrien edge e; 75490075Sobrien 75590075Sobrien estimate_loops_at_level (loop->inner); 75690075Sobrien 75790075Sobrien /* Find current loop back edge and mark it. */ 75890075Sobrien for (e = loop->latch->succ; e->dest != loop->header; e = e->succ_next) 75990075Sobrien ; 76090075Sobrien 76190075Sobrien EDGE_INFO (e)->back_edge = 1; 76290075Sobrien 76390075Sobrien /* In case the loop header is shared, ensure that it is the last 76490075Sobrien one sharing the same header, so we avoid redundant work. */ 76590075Sobrien if (loop->shared) 76690075Sobrien { 76790075Sobrien for (l = loop->next; l; l = l->next) 76890075Sobrien if (l->header == loop->header) 76990075Sobrien break; 77090075Sobrien 77190075Sobrien if (l) 77290075Sobrien continue; 77390075Sobrien } 77490075Sobrien 77590075Sobrien /* Now merge all nodes of all loops with given header as not visited. */ 77690075Sobrien for (l = loop->shared ? first_loop : loop; l != loop->next; l = l->next) 77790075Sobrien if (loop->header == l->header) 77890075Sobrien EXECUTE_IF_SET_IN_SBITMAP (l->nodes, 0, n, 77990075Sobrien BLOCK_INFO (BASIC_BLOCK (n))->tovisit = 1 78090075Sobrien ); 78190075Sobrien 78290075Sobrien propagate_freq (loop->header); 78390075Sobrien } 78490075Sobrien} 78590075Sobrien 78690075Sobrien/* Convert counts measured by profile driven feedback to frequencies. */ 78790075Sobrien 78890075Sobrienstatic void 78990075Sobriencounts_to_freqs () 79090075Sobrien{ 79190075Sobrien HOST_WIDEST_INT count_max = 1; 79290075Sobrien int i; 79390075Sobrien 79490075Sobrien for (i = 0; i < n_basic_blocks; i++) 79590075Sobrien count_max = MAX (BASIC_BLOCK (i)->count, count_max); 79690075Sobrien 79790075Sobrien for (i = -2; i < n_basic_blocks; i++) 79890075Sobrien { 79990075Sobrien basic_block bb; 80090075Sobrien 80190075Sobrien if (i == -2) 80290075Sobrien bb = ENTRY_BLOCK_PTR; 80390075Sobrien else if (i == -1) 80490075Sobrien bb = EXIT_BLOCK_PTR; 80590075Sobrien else 80690075Sobrien bb = BASIC_BLOCK (i); 80790075Sobrien 80890075Sobrien bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max; 80990075Sobrien } 81090075Sobrien} 81190075Sobrien 81290075Sobrien/* Return true if function is likely to be expensive, so there is no point to 81390075Sobrien optimize performance of prologue, epilogue or do inlining at the expense 81490075Sobrien of code size growth. THRESHOLD is the limit of number of isntructions 81590075Sobrien function can execute at average to be still considered not expensive. */ 81690075Sobrien 81790075Sobrienbool 81890075Sobrienexpensive_function_p (threshold) 81990075Sobrien int threshold; 82090075Sobrien{ 82190075Sobrien unsigned int sum = 0; 82290075Sobrien int i; 82390075Sobrien unsigned int limit; 82490075Sobrien 82590075Sobrien /* We can not compute accurately for large thresholds due to scaled 82690075Sobrien frequencies. */ 82790075Sobrien if (threshold > BB_FREQ_MAX) 82890075Sobrien abort (); 82990075Sobrien 83090075Sobrien /* Frequencies are out of range. This either means that function contains 83190075Sobrien internal loop executing more than BB_FREQ_MAX times or profile feedback 83290075Sobrien is available and function has not been executed at all. */ 83390075Sobrien if (ENTRY_BLOCK_PTR->frequency == 0) 83490075Sobrien return true; 83590075Sobrien 83690075Sobrien /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */ 83790075Sobrien limit = ENTRY_BLOCK_PTR->frequency * threshold; 83890075Sobrien for (i = 0; i < n_basic_blocks; i++) 83990075Sobrien { 84090075Sobrien basic_block bb = BASIC_BLOCK (i); 84190075Sobrien rtx insn; 84290075Sobrien 84390075Sobrien for (insn = bb->head; insn != NEXT_INSN (bb->end); 84490075Sobrien insn = NEXT_INSN (insn)) 84590075Sobrien if (active_insn_p (insn)) 84690075Sobrien { 84790075Sobrien sum += bb->frequency; 84890075Sobrien if (sum > limit) 84990075Sobrien return true; 85090075Sobrien } 85190075Sobrien } 85290075Sobrien 85390075Sobrien return false; 85490075Sobrien} 85590075Sobrien 85690075Sobrien/* Estimate basic blocks frequency by given branch probabilities. */ 85790075Sobrien 85890075Sobrienstatic void 85990075Sobrienestimate_bb_frequencies (loops) 86090075Sobrien struct loops *loops; 86190075Sobrien{ 86290075Sobrien int i; 86390075Sobrien double freq_max = 0; 86490075Sobrien 86590075Sobrien mark_dfs_back_edges (); 86690075Sobrien if (flag_branch_probabilities) 86790075Sobrien { 86890075Sobrien counts_to_freqs (); 86990075Sobrien return; 87090075Sobrien } 87190075Sobrien 87290075Sobrien /* Fill in the probability values in flowgraph based on the REG_BR_PROB 87390075Sobrien notes. */ 87490075Sobrien for (i = 0; i < n_basic_blocks; i++) 87590075Sobrien { 87690075Sobrien rtx last_insn = BLOCK_END (i); 87790075Sobrien int probability; 87890075Sobrien edge fallthru, branch; 87990075Sobrien 88090075Sobrien if (GET_CODE (last_insn) != JUMP_INSN || !any_condjump_p (last_insn) 88190075Sobrien /* Avoid handling of conditional jumps jumping to fallthru edge. */ 88290075Sobrien || BASIC_BLOCK (i)->succ->succ_next == NULL) 88390075Sobrien { 88490075Sobrien /* We can predict only conditional jumps at the moment. 88590075Sobrien Expect each edge to be equally probable. 88690075Sobrien ?? In the future we want to make abnormal edges improbable. */ 88790075Sobrien int nedges = 0; 88890075Sobrien edge e; 88990075Sobrien 89090075Sobrien for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next) 89190075Sobrien { 89290075Sobrien nedges++; 89390075Sobrien if (e->probability != 0) 89490075Sobrien break; 89590075Sobrien } 89690075Sobrien if (!e) 89790075Sobrien for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next) 89890075Sobrien e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges; 89990075Sobrien } 90090075Sobrien else 90190075Sobrien { 90290075Sobrien probability = INTVAL (XEXP (find_reg_note (last_insn, 90390075Sobrien REG_BR_PROB, 0), 0)); 90490075Sobrien fallthru = BASIC_BLOCK (i)->succ; 90590075Sobrien if (!fallthru->flags & EDGE_FALLTHRU) 90690075Sobrien fallthru = fallthru->succ_next; 90790075Sobrien branch = BASIC_BLOCK (i)->succ; 90890075Sobrien if (branch->flags & EDGE_FALLTHRU) 90990075Sobrien branch = branch->succ_next; 91090075Sobrien 91190075Sobrien branch->probability = probability; 91290075Sobrien fallthru->probability = REG_BR_PROB_BASE - probability; 91390075Sobrien } 91490075Sobrien } 91590075Sobrien 91690075Sobrien ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE; 91790075Sobrien 91890075Sobrien /* Set up block info for each basic block. */ 91990075Sobrien alloc_aux_for_blocks (sizeof (struct block_info_def)); 92090075Sobrien alloc_aux_for_edges (sizeof (struct edge_info_def)); 92190075Sobrien for (i = -2; i < n_basic_blocks; i++) 92290075Sobrien { 92390075Sobrien edge e; 92490075Sobrien basic_block bb; 92590075Sobrien 92690075Sobrien if (i == -2) 92790075Sobrien bb = ENTRY_BLOCK_PTR; 92890075Sobrien else if (i == -1) 92990075Sobrien bb = EXIT_BLOCK_PTR; 93090075Sobrien else 93190075Sobrien bb = BASIC_BLOCK (i); 93290075Sobrien 93390075Sobrien BLOCK_INFO (bb)->tovisit = 0; 93490075Sobrien for (e = bb->succ; e; e = e->succ_next) 93590075Sobrien EDGE_INFO (e)->back_edge_prob = ((double) e->probability 93690075Sobrien / REG_BR_PROB_BASE); 93790075Sobrien } 93890075Sobrien 93990075Sobrien /* First compute probabilities locally for each loop from innermost 94090075Sobrien to outermost to examine probabilities for back edges. */ 94190075Sobrien estimate_loops_at_level (loops->tree_root); 94290075Sobrien 94390075Sobrien /* Now fake loop around whole function to finalize probabilities. */ 94490075Sobrien for (i = 0; i < n_basic_blocks; i++) 94590075Sobrien BLOCK_INFO (BASIC_BLOCK (i))->tovisit = 1; 94690075Sobrien 94790075Sobrien BLOCK_INFO (ENTRY_BLOCK_PTR)->tovisit = 1; 94890075Sobrien BLOCK_INFO (EXIT_BLOCK_PTR)->tovisit = 1; 94990075Sobrien propagate_freq (ENTRY_BLOCK_PTR); 95090075Sobrien 95190075Sobrien for (i = 0; i < n_basic_blocks; i++) 95290075Sobrien if (BLOCK_INFO (BASIC_BLOCK (i))->frequency > freq_max) 95390075Sobrien freq_max = BLOCK_INFO (BASIC_BLOCK (i))->frequency; 95490075Sobrien 95590075Sobrien for (i = -2; i < n_basic_blocks; i++) 95690075Sobrien { 95790075Sobrien basic_block bb; 95890075Sobrien 95990075Sobrien if (i == -2) 96090075Sobrien bb = ENTRY_BLOCK_PTR; 96190075Sobrien else if (i == -1) 96290075Sobrien bb = EXIT_BLOCK_PTR; 96390075Sobrien else 96490075Sobrien bb = BASIC_BLOCK (i); 96590075Sobrien bb->frequency 96690075Sobrien = BLOCK_INFO (bb)->frequency * BB_FREQ_MAX / freq_max + 0.5; 96790075Sobrien } 96890075Sobrien 96990075Sobrien free_aux_for_blocks (); 97090075Sobrien free_aux_for_edges (); 97190075Sobrien} 972