1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 [1] "Branch Prediction for Free"
24 Ball and Larus; PLDI '93.
25 [2] "Static Branch Frequency and Program Profile Analysis"
26 Wu and Larus; MICRO-27.
27 [3] "Corpus-based Static Branch Prediction"
28 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95.
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
40 #include "insn-config.h"
51 /* Random guesstimation given names. */
52 #define PROB_NEVER (0)
53 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1)
54 #define PROB_UNLIKELY (REG_BR_PROB_BASE * 4 / 10 - 1)
55 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
56 #define PROB_LIKELY (REG_BR_PROB_BASE - PROB_UNLIKELY)
57 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
58 #define PROB_ALWAYS (REG_BR_PROB_BASE)
60 static void combine_predictions_for_insn PARAMS ((rtx, basic_block));
61 static void dump_prediction PARAMS ((enum br_predictor, int,
63 static void estimate_loops_at_level PARAMS ((struct loop *loop));
64 static void propagate_freq PARAMS ((basic_block));
65 static void estimate_bb_frequencies PARAMS ((struct loops *));
66 static void counts_to_freqs PARAMS ((void));
68 /* Information we hold about each branch predictor.
69 Filled using information from predict.def. */
72 const char *name; /* Name used in the debugging dumps. */
73 int hitrate; /* Expected hitrate used by
74 predict_insn_def call. */
78 /* Use given predictor without Dempster-Shaffer theory if it matches
79 using first_match heuristics. */
80 #define PRED_FLAG_FIRST_MATCH 1
82 /* Recompute hitrate in percent to our representation. */
84 #define HITRATE(VAL) ((int)((VAL) * REG_BR_PROB_BASE + 50) / 100)
86 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
87 struct predictor_info predictor_info[] = {
88 #include "predict.def"
90 /* Upper bound on predictors. */
96 predict_insn (insn, predictor, probability)
99 enum br_predictor predictor;
101 if (!any_condjump_p (insn))
104 = gen_rtx_EXPR_LIST (REG_BR_PRED,
105 gen_rtx_CONCAT (VOIDmode,
106 GEN_INT ((int) predictor),
107 GEN_INT ((int) probability)),
111 /* Predict insn by given predictor. */
113 predict_insn_def (insn, predictor, taken)
115 enum br_predictor predictor;
116 enum prediction taken;
118 int probability = predictor_info[(int) predictor].hitrate;
120 probability = REG_BR_PROB_BASE - probability;
121 predict_insn (insn, predictor, probability);
124 /* Predict edge E with given probability if possible. */
126 predict_edge (e, predictor, probability)
129 enum br_predictor predictor;
132 last_insn = e->src->end;
134 /* We can store the branch prediction information only about
135 conditional jumps. */
136 if (!any_condjump_p (last_insn))
139 /* We always store probability of branching. */
140 if (e->flags & EDGE_FALLTHRU)
141 probability = REG_BR_PROB_BASE - probability;
143 predict_insn (last_insn, predictor, probability);
146 /* Predict edge E by given predictor if possible. */
148 predict_edge_def (e, predictor, taken)
150 enum br_predictor predictor;
151 enum prediction taken;
153 int probability = predictor_info[(int) predictor].hitrate;
156 probability = REG_BR_PROB_BASE - probability;
157 predict_edge (e, predictor, probability);
160 /* Invert all branch predictions or probability notes in the INSN. This needs
161 to be done each time we invert the condition used by the jump. */
163 invert_br_probabilities (insn)
166 rtx note = REG_NOTES (insn);
170 if (REG_NOTE_KIND (note) == REG_BR_PROB)
171 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
172 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
173 XEXP (XEXP (note, 0), 1)
174 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
175 note = XEXP (note, 1);
179 /* Dump information about the branch prediction to the output file. */
181 dump_prediction (predictor, probability, bb, used)
182 enum br_predictor predictor;
192 while (e->flags & EDGE_FALLTHRU)
195 fprintf (rtl_dump_file, " %s heuristics%s: %.1f%%",
196 predictor_info[predictor].name,
197 used ? "" : " (ignored)",
198 probability * 100.0 / REG_BR_PROB_BASE);
202 fprintf (rtl_dump_file, " exec ");
203 fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,
204 (HOST_WIDEST_INT) bb->count);
205 fprintf (rtl_dump_file, " hit ");
206 fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,
207 (HOST_WIDEST_INT) e->count);
208 fprintf (rtl_dump_file, " (%.1f%%)",
209 e->count * 100.0 / bb->count);
211 fprintf (rtl_dump_file, "\n");
214 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
215 note if not already present. Remove now useless REG_BR_PRED notes. */
217 combine_predictions_for_insn (insn, bb)
221 rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0);
222 rtx *pnote = ®_NOTES (insn);
223 rtx note = REG_NOTES (insn);
224 int best_probability = PROB_EVEN;
225 int best_predictor = END_PREDICTORS;
226 int combined_probability = REG_BR_PROB_BASE / 2;
228 bool first_match = false;
232 fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
235 /* We implement "first match" heuristics and use probability guessed
236 by predictor with smallest index. In the future we will use better
237 probability combination techniques. */
240 if (REG_NOTE_KIND (note) == REG_BR_PRED)
242 int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
243 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
246 if (best_predictor > predictor)
247 best_probability = probability, best_predictor = predictor;
249 d = (combined_probability * probability
250 + (REG_BR_PROB_BASE - combined_probability)
251 * (REG_BR_PROB_BASE - probability));
252 /* An FP math to avoid overflows of 32bit integers. */
253 combined_probability = (((double)combined_probability) * probability
254 * REG_BR_PROB_BASE / d + 0.5);
256 note = XEXP (note, 1);
259 /* Decide heuristic to use. In case we didn't match anything, use
260 no_prediction heuristic, in case we did match, use either
261 first match or Dempster-Shaffer theory depending on the flags. */
263 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
267 dump_prediction (PRED_NO_PREDICTION, combined_probability, bb, true);
270 dump_prediction (PRED_DS_THEORY, combined_probability, bb,
272 dump_prediction (PRED_FIRST_MATCH, best_probability, bb, first_match);
276 combined_probability = best_probability;
277 dump_prediction (PRED_COMBINED, combined_probability, bb, true);
281 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
283 int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
284 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
286 dump_prediction (predictor, probability, bb,
287 !first_match || best_predictor == predictor);
288 *pnote = XEXP (*pnote, 1);
291 pnote = &XEXP (*pnote, 1);
296 = gen_rtx_EXPR_LIST (REG_BR_PROB,
297 GEN_INT (combined_probability), REG_NOTES (insn));
298 /* Save the prediction into CFG in case we are seeing non-degenerated
300 if (bb->succ->succ_next)
302 BRANCH_EDGE (bb)->probability = combined_probability;
303 FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - combined_probability;
308 /* Statically estimate the probability that a branch will be taken.
309 ??? In the next revision there will be a number of other predictors added
310 from the above references. Further, each heuristic will be factored out
311 into its own function for clarity (and to facilitate the combination of
315 estimate_probability (loops_info)
316 struct loops *loops_info;
318 sbitmap *dominators, *post_dominators;
320 int found_noreturn = 0;
322 dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
323 post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
324 calculate_dominance_info (NULL, dominators, CDI_DOMINATORS);
325 calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
327 /* Try to predict out blocks in a loop that are not part of a
329 for (i = 0; i < loops_info->num; i++)
333 for (j = loops_info->array[i].first->index;
334 j <= loops_info->array[i].last->index;
337 if (TEST_BIT (loops_info->array[i].nodes, j))
339 int header_found = 0;
342 /* Loop branch heuristics - predict as taken an edge back to
344 for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
345 if (e->dest == loops_info->array[i].header
346 && e->src == loops_info->array[i].latch)
349 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
351 /* Loop exit heuristics - predict as not taken an edge
352 exiting the loop if the conditinal has no loop header
355 for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
356 if (e->dest->index <= 0
357 || !TEST_BIT (loops_info->array[i].nodes, e->dest->index))
358 predict_edge_def (e, PRED_LOOP_EXIT, NOT_TAKEN);
363 /* Attempt to predict conditional jumps using a number of heuristics. */
364 for (i = 0; i < n_basic_blocks; i++)
366 basic_block bb = BASIC_BLOCK (i);
367 rtx last_insn = bb->end;
371 /* If block has no sucessor, predict all possible paths to
372 it as improbable, as the block contains a call to a noreturn
373 function and thus can be executed only once. */
374 if (bb->succ == NULL && !found_noreturn)
378 /* ??? Postdominator claims each noreturn block to be postdominated
379 by each, so we need to run only once. This needs to be changed
380 once postdominace algorithm is updated to say something more sane.
383 for (y = 0; y < n_basic_blocks; y++)
384 if (!TEST_BIT (post_dominators[y], i))
386 for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
387 if (e->dest->index >= 0
388 && TEST_BIT (post_dominators[e->dest->index], i))
389 predict_edge_def (e, PRED_NORETURN, NOT_TAKEN);
393 if (GET_CODE (last_insn) != JUMP_INSN
394 || ! any_condjump_p (last_insn))
397 for (e = bb->succ; e; e = e->succ_next)
399 /* Predict edges to blocks that return immediately to be
400 improbable. These are usually used to signal error states. */
401 if (e->dest == EXIT_BLOCK_PTR
402 || (e->dest->succ && !e->dest->succ->succ_next
403 && e->dest->succ->dest == EXIT_BLOCK_PTR))
404 predict_edge_def (e, PRED_ERROR_RETURN, NOT_TAKEN);
406 /* Look for block we are guarding (ie we dominate it,
407 but it doesn't postdominate us). */
408 if (e->dest != EXIT_BLOCK_PTR
410 && TEST_BIT (dominators[e->dest->index], e->src->index)
411 && !TEST_BIT (post_dominators[e->src->index], e->dest->index))
414 /* The call heuristic claims that a guarded function call
415 is improbable. This is because such calls are often used
416 to signal exceptional situations such as printing error
418 for (insn = e->dest->head; insn != NEXT_INSN (e->dest->end);
419 insn = NEXT_INSN (insn))
420 if (GET_CODE (insn) == CALL_INSN
421 /* Constant and pure calls are hardly used to signalize
422 something exceptional. */
423 && ! CONST_OR_PURE_CALL_P (insn))
425 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
431 cond = get_condition (last_insn, &earliest);
435 /* Try "pointer heuristic."
436 A comparison ptr == 0 is predicted as false.
437 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
438 switch (GET_CODE (cond))
441 if (GET_CODE (XEXP (cond, 0)) == REG
442 && REG_POINTER (XEXP (cond, 0))
443 && (XEXP (cond, 1) == const0_rtx
444 || (GET_CODE (XEXP (cond, 1)) == REG
445 && REG_POINTER (XEXP (cond, 1)))))
447 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
450 if (GET_CODE (XEXP (cond, 0)) == REG
451 && REG_POINTER (XEXP (cond, 0))
452 && (XEXP (cond, 1) == const0_rtx
453 || (GET_CODE (XEXP (cond, 1)) == REG
454 && REG_POINTER (XEXP (cond, 1)))))
455 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
462 /* Try "opcode heuristic."
463 EQ tests are usually false and NE tests are usually true. Also,
464 most quantities are positive, so we can make the appropriate guesses
465 about signed comparisons against zero. */
466 switch (GET_CODE (cond))
469 /* Unconditional branch. */
470 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
471 cond == const0_rtx ? NOT_TAKEN : TAKEN);
476 predict_insn_def (last_insn, PRED_OPCODE, NOT_TAKEN);
480 predict_insn_def (last_insn, PRED_OPCODE, TAKEN);
483 predict_insn_def (last_insn, PRED_OPCODE, TAKEN);
486 predict_insn_def (last_insn, PRED_OPCODE, NOT_TAKEN);
490 if (XEXP (cond, 1) == const0_rtx
491 || (GET_CODE (XEXP (cond, 1)) == CONST_INT
492 && INTVAL (XEXP (cond, 1)) == -1))
493 predict_insn_def (last_insn, PRED_OPCODE, NOT_TAKEN);
497 if (XEXP (cond, 1) == const0_rtx
498 || (GET_CODE (XEXP (cond, 1)) == CONST_INT
499 && INTVAL (XEXP (cond, 1)) == -1))
500 predict_insn_def (last_insn, PRED_OPCODE, TAKEN);
508 /* Attach the combined probability to each conditional jump. */
509 for (i = 0; i < n_basic_blocks; i++)
511 rtx last_insn = BLOCK_END (i);
513 if (GET_CODE (last_insn) != JUMP_INSN
514 || ! any_condjump_p (last_insn))
516 combine_predictions_for_insn (last_insn, BASIC_BLOCK (i));
518 sbitmap_vector_free (post_dominators);
519 sbitmap_vector_free (dominators);
521 estimate_bb_frequencies (loops_info);
524 /* __builtin_expect dropped tokens into the insn stream describing
525 expected values of registers. Generate branch probabilities
526 based off these values. */
529 expected_value_to_br_prob ()
531 rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
533 for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
535 switch (GET_CODE (insn))
538 /* Look for expected value notes. */
539 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
541 ev = NOTE_EXPECTED_VALUE (insn);
542 ev_reg = XEXP (ev, 0);
547 /* Never propagate across labels. */
552 /* Look for insns that clobber the EV register. */
553 if (ev && reg_set_p (ev_reg, insn))
558 /* Look for simple conditional branches. If we havn't got an
559 expected value yet, no point going further. */
560 if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX)
562 if (! any_condjump_p (insn))
567 /* Collect the branch condition, hopefully relative to EV_REG. */
568 /* ??? At present we'll miss things like
569 (expected_value (eq r70 0))
571 (set r80 (lt r70 r71))
572 (set pc (if_then_else (ne r80 0) ...))
573 as canonicalize_condition will render this to us as
575 Could use cselib to try and reduce this further. */
576 cond = XEXP (SET_SRC (PATTERN (insn)), 0);
577 cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
579 || XEXP (cond, 0) != ev_reg
580 || GET_CODE (XEXP (cond, 1)) != CONST_INT)
583 /* Substitute and simplify. Given that the expression we're
584 building involves two constants, we should wind up with either
586 cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
587 XEXP (ev, 1), XEXP (cond, 1));
588 cond = simplify_rtx (cond);
590 /* Turn the condition into a scaled branch probability. */
591 if (cond != const_true_rtx && cond != const0_rtx)
593 predict_insn_def (insn, PRED_BUILTIN_EXPECT,
594 cond == const_true_rtx ? TAKEN : NOT_TAKEN);
598 /* This is used to carry information about basic blocks. It is
599 attached to the AUX field of the standard CFG block. */
601 typedef struct block_info_def
603 /* Estimated frequency of execution of basic_block. */
606 /* To keep queue of basic blocks to process. */
609 /* True if block needs to be visited in prop_freqency. */
612 /* Number of predecesors we need to visit first. */
616 /* Similar information for edges. */
617 typedef struct edge_info_def
619 /* In case edge is an loopback edge, the probability edge will be reached
620 in case header is. Estimated number of iterations of the loop can be
621 then computed as 1 / (1 - back_edge_prob). */
622 double back_edge_prob;
623 /* True if the edge is an loopback edge in the natural loop. */
627 #define BLOCK_INFO(B) ((block_info) (B)->aux)
628 #define EDGE_INFO(E) ((edge_info) (E)->aux)
630 /* Helper function for estimate_bb_frequencies.
631 Propagate the frequencies for loops headed by HEAD. */
633 propagate_freq (head)
636 basic_block bb = head;
637 basic_block last = bb;
642 /* For each basic block we need to visit count number of his predecesors
643 we need to visit first. */
644 for (n = 0; n < n_basic_blocks; n++)
646 basic_block bb = BASIC_BLOCK (n);
647 if (BLOCK_INFO (bb)->tovisit)
650 for (e = bb->pred; e; e = e->pred_next)
651 if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
653 else if (BLOCK_INFO (e->src)->tovisit
654 && rtl_dump_file && !EDGE_INFO (e)->back_edge)
655 fprintf (rtl_dump_file,
656 "Irreducible region hit, ignoring edge to %i->%i\n",
657 e->src->index, bb->index);
658 BLOCK_INFO (bb)->npredecesors = count;
662 BLOCK_INFO (head)->frequency = 1;
663 for (; bb; bb = nextbb)
665 double cyclic_probability = 0, frequency = 0;
667 nextbb = BLOCK_INFO (bb)->next;
668 BLOCK_INFO (bb)->next = NULL;
670 /* Compute frequency of basic block. */
673 #ifdef ENABLE_CHECKING
674 for (e = bb->pred; e; e = e->pred_next)
675 if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
679 for (e = bb->pred; e; e = e->pred_next)
680 if (EDGE_INFO (e)->back_edge)
681 cyclic_probability += EDGE_INFO (e)->back_edge_prob;
682 else if (!(e->flags & EDGE_DFS_BACK))
683 frequency += (e->probability
684 * BLOCK_INFO (e->src)->frequency /
687 if (cyclic_probability > 1.0 - 1.0 / REG_BR_PROB_BASE)
688 cyclic_probability = 1.0 - 1.0 / REG_BR_PROB_BASE;
690 BLOCK_INFO (bb)->frequency = frequency / (1 - cyclic_probability);
693 BLOCK_INFO (bb)->tovisit = 0;
695 /* Compute back edge frequencies. */
696 for (e = bb->succ; e; e = e->succ_next)
698 EDGE_INFO (e)->back_edge_prob = (e->probability
699 * BLOCK_INFO (bb)->frequency
702 /* Propagate to successor blocks. */
703 for (e = bb->succ; e; e = e->succ_next)
704 if (!(e->flags & EDGE_DFS_BACK)
705 && BLOCK_INFO (e->dest)->npredecesors)
707 BLOCK_INFO (e->dest)->npredecesors--;
708 if (!BLOCK_INFO (e->dest)->npredecesors)
713 BLOCK_INFO (last)->next = e->dest;
720 /* Estimate probabilities of loopback edges in loops at same nest level. */
722 estimate_loops_at_level (first_loop)
723 struct loop *first_loop;
725 struct loop *l, *loop = first_loop;
727 for (loop = first_loop; loop; loop = loop->next)
732 estimate_loops_at_level (loop->inner);
734 /* Find current loop back edge and mark it. */
735 for (e = loop->latch->succ; e->dest != loop->header; e = e->succ_next);
737 EDGE_INFO (e)->back_edge = 1;
739 /* In case the loop header is shared, ensure that it is the last
740 one sharing the same header, so we avoid redundant work. */
743 for (l = loop->next; l; l = l->next)
744 if (l->header == loop->header)
750 /* Now merge all nodes of all loops with given header as not visited. */
751 for (l = loop->shared ? first_loop : loop; l != loop->next; l = l->next)
752 if (loop->header == l->header)
753 EXECUTE_IF_SET_IN_SBITMAP (l->nodes, 0, n,
754 BLOCK_INFO (BASIC_BLOCK (n))->tovisit = 1
756 propagate_freq (loop->header);
760 /* Convert counts measured by profile driven feedback to frequencies. */
764 HOST_WIDEST_INT count_max = 1;
767 for (i = 0; i < n_basic_blocks; i++)
768 if (BASIC_BLOCK (i)->count > count_max)
769 count_max = BASIC_BLOCK (i)->count;
771 for (i = -2; i < n_basic_blocks; i++)
775 bb = ENTRY_BLOCK_PTR;
779 bb = BASIC_BLOCK (i);
780 bb->frequency = ((bb->count * BB_FREQ_MAX + count_max / 2)
785 /* Estimate basic blocks frequency by given branch probabilities. */
787 estimate_bb_frequencies (loops)
796 mark_dfs_back_edges ();
797 if (flag_branch_probabilities)
803 /* Fill in the probability values in flowgraph based on the REG_BR_PROB
805 for (i = 0; i < n_basic_blocks; i++)
807 rtx last_insn = BLOCK_END (i);
809 edge fallthru, branch;
811 if (GET_CODE (last_insn) != JUMP_INSN || !any_condjump_p (last_insn)
812 /* Avoid handling of conditional jumps jumping to fallthru edge. */
813 || BASIC_BLOCK (i)->succ->succ_next == NULL)
815 /* We can predict only conditional jumps at the moment.
816 Expect each edge to be equally probable.
817 ?? In the future we want to make abnormal edges improbable. */
821 for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
824 if (e->probability != 0)
828 for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
829 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
833 probability = INTVAL (XEXP (find_reg_note (last_insn,
834 REG_BR_PROB, 0), 0));
835 fallthru = BASIC_BLOCK (i)->succ;
836 if (!fallthru->flags & EDGE_FALLTHRU)
837 fallthru = fallthru->succ_next;
838 branch = BASIC_BLOCK (i)->succ;
839 if (branch->flags & EDGE_FALLTHRU)
840 branch = branch->succ_next;
842 branch->probability = probability;
843 fallthru->probability = REG_BR_PROB_BASE - probability;
846 ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE;
848 /* Set up block info for each basic block. */
849 bi = (block_info) xcalloc ((n_basic_blocks + 2), sizeof (*bi));
850 ei = (edge_info) xcalloc ((n_edges), sizeof (*ei));
851 for (i = -2; i < n_basic_blocks; i++)
857 bb = ENTRY_BLOCK_PTR;
861 bb = BASIC_BLOCK (i);
862 bb->aux = bi + i + 2;
863 BLOCK_INFO (bb)->tovisit = 0;
864 for (e = bb->succ; e; e = e->succ_next)
866 e->aux = ei + edgenum, edgenum++;
867 EDGE_INFO (e)->back_edge_prob = ((double) e->probability
871 /* First compute probabilities locally for each loop from innermost
872 to outermost to examine probabilities for back edges. */
873 estimate_loops_at_level (loops->tree_root);
875 /* Now fake loop around whole function to finalize probabilities. */
876 for (i = 0; i < n_basic_blocks; i++)
877 BLOCK_INFO (BASIC_BLOCK (i))->tovisit = 1;
878 BLOCK_INFO (ENTRY_BLOCK_PTR)->tovisit = 1;
879 BLOCK_INFO (EXIT_BLOCK_PTR)->tovisit = 1;
880 propagate_freq (ENTRY_BLOCK_PTR);
882 for (i = 0; i < n_basic_blocks; i++)
883 if (BLOCK_INFO (BASIC_BLOCK (i))->frequency > freq_max)
884 freq_max = BLOCK_INFO (BASIC_BLOCK (i))->frequency;
885 for (i = -2; i < n_basic_blocks; i++)
889 bb = ENTRY_BLOCK_PTR;
893 bb = BASIC_BLOCK (i);
894 bb->frequency = (BLOCK_INFO (bb)->frequency * BB_FREQ_MAX / freq_max