1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it 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 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
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
)
182 enum br_predictor predictor
;
191 while (e
->flags
& EDGE_FALLTHRU
)
194 fprintf (rtl_dump_file
, " %s heuristics: %.1f%%",
195 predictor_info
[predictor
].name
,
196 probability
* 100.0 / REG_BR_PROB_BASE
);
200 fprintf (rtl_dump_file
, " exec ");
201 fprintf (rtl_dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
202 (HOST_WIDEST_INT
) bb
->count
);
203 fprintf (rtl_dump_file
, " hit ");
204 fprintf (rtl_dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
205 (HOST_WIDEST_INT
) e
->count
);
206 fprintf (rtl_dump_file
, " (%.1f%%)",
207 e
->count
* 100.0 / bb
->count
);
209 fprintf (rtl_dump_file
, "\n");
212 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
213 note if not already present. Remove now useless REG_BR_PRED notes. */
215 combine_predictions_for_insn (insn
, bb
)
219 rtx prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
220 rtx
*pnote
= ®_NOTES (insn
);
221 int best_probability
= PROB_EVEN
;
222 int best_predictor
= END_PREDICTORS
;
223 int combined_probability
= REG_BR_PROB_BASE
/ 2;
227 fprintf (rtl_dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
230 /* We implement "first match" heuristics and use probability guessed
231 by predictor with smallest index. In the future we will use better
232 probability combination techniques. */
235 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
237 int predictor
= INTVAL (XEXP (XEXP (*pnote
, 0), 0));
238 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
240 dump_prediction (predictor
, probability
, bb
);
241 if (best_predictor
> predictor
)
242 best_probability
= probability
, best_predictor
= predictor
;
243 *pnote
= XEXP (*pnote
, 1);
245 d
= (combined_probability
* probability
246 + (REG_BR_PROB_BASE
- combined_probability
)
247 * (REG_BR_PROB_BASE
- probability
));
248 /* An FP math to avoid overflows of 32bit integers. */
249 combined_probability
= (((double)combined_probability
) * probability
250 * REG_BR_PROB_BASE
/ d
+ 0.5);
253 pnote
= &XEXP (*pnote
, 1);
255 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
256 combined_probability
= best_probability
;
257 dump_prediction (PRED_FIRST_MATCH
, best_probability
, bb
);
258 dump_prediction (PRED_COMBINED
, combined_probability
, bb
);
262 = gen_rtx_EXPR_LIST (REG_BR_PROB
,
263 GEN_INT (combined_probability
), REG_NOTES (insn
));
264 /* Save the prediction into CFG in case we are seeing non-degenerated
266 if (bb
->succ
->succ_next
)
268 BRANCH_EDGE (bb
)->probability
= combined_probability
;
269 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- combined_probability
;
274 /* Statically estimate the probability that a branch will be taken.
275 ??? In the next revision there will be a number of other predictors added
276 from the above references. Further, each heuristic will be factored out
277 into its own function for clarity (and to facilitate the combination of
281 estimate_probability (loops_info
)
282 struct loops
*loops_info
;
284 sbitmap
*dominators
, *post_dominators
;
286 int found_noreturn
= 0;
288 dominators
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
289 post_dominators
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
290 calculate_dominance_info (NULL
, dominators
, CDI_DOMINATORS
);
291 calculate_dominance_info (NULL
, post_dominators
, CDI_POST_DOMINATORS
);
293 /* Try to predict out blocks in a loop that are not part of a
295 for (i
= 0; i
< loops_info
->num
; i
++)
299 for (j
= loops_info
->array
[i
].first
->index
;
300 j
<= loops_info
->array
[i
].last
->index
;
303 if (TEST_BIT (loops_info
->array
[i
].nodes
, j
))
305 int header_found
= 0;
308 /* Loop branch heuristics - predict as taken an edge back to
310 for (e
= BASIC_BLOCK(j
)->succ
; e
; e
= e
->succ_next
)
311 if (e
->dest
== loops_info
->array
[i
].header
312 && e
->src
== loops_info
->array
[i
].latch
)
315 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
317 /* Loop exit heuristics - predict as not taken an edge
318 exiting the loop if the conditinal has no loop header
321 for (e
= BASIC_BLOCK(j
)->succ
; e
; e
= e
->succ_next
)
322 if (e
->dest
->index
<= 0
323 || !TEST_BIT (loops_info
->array
[i
].nodes
, e
->dest
->index
))
324 predict_edge_def (e
, PRED_LOOP_EXIT
, NOT_TAKEN
);
329 /* Attempt to predict conditional jumps using a number of heuristics. */
330 for (i
= 0; i
< n_basic_blocks
; i
++)
332 basic_block bb
= BASIC_BLOCK (i
);
333 rtx last_insn
= bb
->end
;
337 /* If block has no sucessor, predict all possible paths to
338 it as improbable, as the block contains a call to a noreturn
339 function and thus can be executed only once. */
340 if (bb
->succ
== NULL
&& !found_noreturn
)
344 /* ??? Postdominator claims each noreturn block to be postdominated
345 by each, so we need to run only once. This needs to be changed
346 once postdominace algorithm is updated to say something more sane.
349 for (y
= 0; y
< n_basic_blocks
; y
++)
350 if (!TEST_BIT (post_dominators
[y
], i
))
352 for (e
= BASIC_BLOCK (y
)->succ
; e
; e
= e
->succ_next
)
353 if (e
->dest
->index
>= 0
354 && TEST_BIT (post_dominators
[e
->dest
->index
], i
))
355 predict_edge_def (e
, PRED_NORETURN
, NOT_TAKEN
);
359 if (GET_CODE (last_insn
) != JUMP_INSN
360 || ! any_condjump_p (last_insn
))
363 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
365 /* Predict edges to blocks that return immediately to be
366 improbable. These are usually used to signal error states. */
367 if (e
->dest
== EXIT_BLOCK_PTR
368 || (e
->dest
->succ
&& !e
->dest
->succ
->succ_next
369 && e
->dest
->succ
->dest
== EXIT_BLOCK_PTR
))
370 predict_edge_def (e
, PRED_ERROR_RETURN
, NOT_TAKEN
);
372 /* Look for block we are guarding (ie we dominate it,
373 but it doesn't postdominate us). */
374 if (e
->dest
!= EXIT_BLOCK_PTR
376 && TEST_BIT (dominators
[e
->dest
->index
], e
->src
->index
)
377 && !TEST_BIT (post_dominators
[e
->src
->index
], e
->dest
->index
))
380 /* The call heuristic claims that a guarded function call
381 is improbable. This is because such calls are often used
382 to signal exceptional situations such as printing error
384 for (insn
= e
->dest
->head
; insn
!= NEXT_INSN (e
->dest
->end
);
385 insn
= NEXT_INSN (insn
))
386 if (GET_CODE (insn
) == CALL_INSN
387 /* Constant and pure calls are hardly used to signalize
388 something exceptional. */
389 && ! CONST_OR_PURE_CALL_P (insn
))
391 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
397 cond
= get_condition (last_insn
, &earliest
);
401 /* Try "pointer heuristic."
402 A comparison ptr == 0 is predicted as false.
403 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
404 switch (GET_CODE (cond
))
407 if (GET_CODE (XEXP (cond
, 0)) == REG
408 && REG_POINTER (XEXP (cond
, 0))
409 && (XEXP (cond
, 1) == const0_rtx
410 || (GET_CODE (XEXP (cond
, 1)) == REG
411 && REG_POINTER (XEXP (cond
, 1)))))
413 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
416 if (GET_CODE (XEXP (cond
, 0)) == REG
417 && REG_POINTER (XEXP (cond
, 0))
418 && (XEXP (cond
, 1) == const0_rtx
419 || (GET_CODE (XEXP (cond
, 1)) == REG
420 && REG_POINTER (XEXP (cond
, 1)))))
421 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
428 /* Try "opcode heuristic."
429 EQ tests are usually false and NE tests are usually true. Also,
430 most quantities are positive, so we can make the appropriate guesses
431 about signed comparisons against zero. */
432 switch (GET_CODE (cond
))
435 /* Unconditional branch. */
436 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
437 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
442 predict_insn_def (last_insn
, PRED_OPCODE
, NOT_TAKEN
);
446 predict_insn_def (last_insn
, PRED_OPCODE
, TAKEN
);
449 predict_insn_def (last_insn
, PRED_OPCODE
, TAKEN
);
452 predict_insn_def (last_insn
, PRED_OPCODE
, NOT_TAKEN
);
456 if (XEXP (cond
, 1) == const0_rtx
457 || (GET_CODE (XEXP (cond
, 1)) == CONST_INT
458 && INTVAL (XEXP (cond
, 1)) == -1))
459 predict_insn_def (last_insn
, PRED_OPCODE
, NOT_TAKEN
);
463 if (XEXP (cond
, 1) == const0_rtx
464 || (GET_CODE (XEXP (cond
, 1)) == CONST_INT
465 && INTVAL (XEXP (cond
, 1)) == -1))
466 predict_insn_def (last_insn
, PRED_OPCODE
, TAKEN
);
474 /* Attach the combined probability to each conditional jump. */
475 for (i
= 0; i
< n_basic_blocks
; i
++)
477 rtx last_insn
= BLOCK_END (i
);
479 if (GET_CODE (last_insn
) != JUMP_INSN
480 || ! any_condjump_p (last_insn
))
482 combine_predictions_for_insn (last_insn
, BASIC_BLOCK (i
));
484 sbitmap_vector_free (post_dominators
);
485 sbitmap_vector_free (dominators
);
487 estimate_bb_frequencies (loops_info
);
490 /* __builtin_expect dropped tokens into the insn stream describing
491 expected values of registers. Generate branch probabilities
492 based off these values. */
495 expected_value_to_br_prob ()
497 rtx insn
, cond
, ev
= NULL_RTX
, ev_reg
= NULL_RTX
;
499 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
501 switch (GET_CODE (insn
))
504 /* Look for expected value notes. */
505 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EXPECTED_VALUE
)
507 ev
= NOTE_EXPECTED_VALUE (insn
);
508 ev_reg
= XEXP (ev
, 0);
513 /* Never propagate across labels. */
518 /* Look for insns that clobber the EV register. */
519 if (ev
&& reg_set_p (ev_reg
, insn
))
524 /* Look for simple conditional branches. If we havn't got an
525 expected value yet, no point going further. */
526 if (GET_CODE (insn
) != JUMP_INSN
|| ev
== NULL_RTX
)
528 if (! any_condjump_p (insn
))
533 /* Collect the branch condition, hopefully relative to EV_REG. */
534 /* ??? At present we'll miss things like
535 (expected_value (eq r70 0))
537 (set r80 (lt r70 r71))
538 (set pc (if_then_else (ne r80 0) ...))
539 as canonicalize_condition will render this to us as
541 Could use cselib to try and reduce this further. */
542 cond
= XEXP (SET_SRC (PATTERN (insn
)), 0);
543 cond
= canonicalize_condition (insn
, cond
, 0, NULL
, ev_reg
);
545 || XEXP (cond
, 0) != ev_reg
546 || GET_CODE (XEXP (cond
, 1)) != CONST_INT
)
549 /* Substitute and simplify. Given that the expression we're
550 building involves two constants, we should wind up with either
552 cond
= gen_rtx_fmt_ee (GET_CODE (cond
), VOIDmode
,
553 XEXP (ev
, 1), XEXP (cond
, 1));
554 cond
= simplify_rtx (cond
);
556 /* Turn the condition into a scaled branch probability. */
557 if (cond
!= const_true_rtx
&& cond
!= const0_rtx
)
559 predict_insn_def (insn
, PRED_BUILTIN_EXPECT
,
560 cond
== const_true_rtx
? TAKEN
: NOT_TAKEN
);
564 /* This is used to carry information about basic blocks. It is
565 attached to the AUX field of the standard CFG block. */
567 typedef struct block_info_def
569 /* Estimated frequency of execution of basic_block. */
572 /* To keep queue of basic blocks to process. */
575 /* True if block already converted. */
578 /* Number of block proceeded before adding basic block to the queue. Used
579 to recognize irregular regions. */
583 /* Similar information for edges. */
584 typedef struct edge_info_def
586 /* In case edge is an loopback edge, the probability edge will be reached
587 in case header is. Estimated number of iterations of the loop can be
588 then computed as 1 / (1 - back_edge_prob). */
589 double back_edge_prob
;
590 /* True if the edge is an loopback edge in the natural loop. */
594 #define BLOCK_INFO(B) ((block_info) (B)->aux)
595 #define EDGE_INFO(E) ((edge_info) (E)->aux)
597 /* Helper function for estimate_bb_frequencies.
598 Propagate the frequencies for loops headed by HEAD. */
600 propagate_freq (head
)
603 basic_block bb
= head
;
604 basic_block last
= bb
;
609 BLOCK_INFO (head
)->frequency
= 1;
610 for (; bb
; bb
= nextbb
)
612 double cyclic_probability
= 0, frequency
= 0;
614 nextbb
= BLOCK_INFO (bb
)->next
;
615 BLOCK_INFO (bb
)->next
= NULL
;
617 /* Compute frequency of basic block. */
620 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
621 if (!BLOCK_INFO (e
->src
)->visited
&& !EDGE_INFO (e
)->back_edge
)
624 /* We haven't proceeded all predecessors of edge e yet.
625 These may be waiting in the queue or we may hit an
628 To avoid infinite looping on irrecudible regions, count
629 the number of blocks proceeded at the time the basic
630 block has been queued. In the case the number doesn't
631 change, we've hit an irreducible region and we can forget
632 the backward edge. This can increase the time complexity
633 by the number of irreducible blocks, but in the same way
634 the standard the loop does, so it should not result in a
637 Alternatively we may distinguish backward and cross edges
638 in the DFS tree by the preprocessing pass and ignore the
639 existence of non-loop backward edges. */
640 if (e
&& BLOCK_INFO (bb
)->nvisited
!= nvisited
)
645 BLOCK_INFO (last
)->next
= e
->dest
;
646 BLOCK_INFO (last
)->nvisited
= nvisited
;
650 else if (e
&& rtl_dump_file
)
651 fprintf (rtl_dump_file
, "Irreducible region hit, ignoring edge to bb %i\n",
654 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
655 if (EDGE_INFO (e
)->back_edge
)
656 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
657 else if (BLOCK_INFO (e
->src
)->visited
)
658 frequency
+= (e
->probability
659 * BLOCK_INFO (e
->src
)->frequency
/
662 if (cyclic_probability
> 1.0 - 1.0 / REG_BR_PROB_BASE
)
663 cyclic_probability
= 1.0 - 1.0 / REG_BR_PROB_BASE
;
665 BLOCK_INFO (bb
)->frequency
= frequency
/ (1 - cyclic_probability
);
668 BLOCK_INFO (bb
)->visited
= 1;
670 /* Compute back edge frequencies. */
671 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
673 EDGE_INFO (e
)->back_edge_prob
= (e
->probability
674 * BLOCK_INFO (bb
)->frequency
677 /* Propagate to successor blocks. */
678 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
679 if (!EDGE_INFO (e
)->back_edge
680 && !BLOCK_INFO (e
->dest
)->visited
681 && !BLOCK_INFO (e
->dest
)->next
&& e
->dest
!= last
)
686 BLOCK_INFO (last
)->next
= e
->dest
;
687 BLOCK_INFO (last
)->nvisited
= nvisited
;
694 /* Estimate probabilities of loopback edges in loops at same nest level. */
696 estimate_loops_at_level (first_loop
)
697 struct loop
*first_loop
;
699 struct loop
*l
, *loop
= first_loop
;
701 for (loop
= first_loop
; loop
; loop
= loop
->next
)
706 estimate_loops_at_level (loop
->inner
);
708 /* Find current loop back edge and mark it. */
709 for (e
= loop
->latch
->succ
; e
->dest
!= loop
->header
; e
= e
->succ_next
);
711 EDGE_INFO (e
)->back_edge
= 1;
713 /* In case the loop header is shared, ensure that it is the last
714 one sharing the same header, so we avoid redundant work. */
717 for (l
= loop
->next
; l
; l
= l
->next
)
718 if (l
->header
== loop
->header
)
724 /* Now merge all nodes of all loops with given header as not visited. */
725 for (l
= loop
->shared
? first_loop
: loop
; l
!= loop
->next
; l
= l
->next
)
726 if (loop
->header
== l
->header
)
727 EXECUTE_IF_SET_IN_SBITMAP (l
->nodes
, 0, n
,
728 BLOCK_INFO (BASIC_BLOCK (n
))->visited
=
730 propagate_freq (loop
->header
);
734 /* Convert counts measured by profile driven feedback to frequencies. */
738 HOST_WIDEST_INT count_max
= 1;
741 for (i
= 0; i
< n_basic_blocks
; i
++)
742 if (BASIC_BLOCK (i
)->count
> count_max
)
743 count_max
= BASIC_BLOCK (i
)->count
;
745 for (i
= -2; i
< n_basic_blocks
; i
++)
749 bb
= ENTRY_BLOCK_PTR
;
753 bb
= BASIC_BLOCK (i
);
754 bb
->frequency
= ((bb
->count
* BB_FREQ_MAX
+ count_max
/ 2)
759 /* Estimate basic blocks frequency by given branch probabilities. */
761 estimate_bb_frequencies (loops
)
770 if (flag_branch_probabilities
)
776 /* Fill in the probability values in flowgraph based on the REG_BR_PROB
778 for (i
= 0; i
< n_basic_blocks
; i
++)
780 rtx last_insn
= BLOCK_END (i
);
782 edge fallthru
, branch
;
784 if (GET_CODE (last_insn
) != JUMP_INSN
|| !any_condjump_p (last_insn
)
785 /* Avoid handling of conditional jumps jumping to fallthru edge. */
786 || BASIC_BLOCK (i
)->succ
->succ_next
== NULL
)
788 /* We can predict only conditional jumps at the moment.
789 Expect each edge to be equally probable.
790 ?? In the future we want to make abnormal edges improbable. */
794 for (e
= BASIC_BLOCK (i
)->succ
; e
; e
= e
->succ_next
)
797 if (e
->probability
!= 0)
801 for (e
= BASIC_BLOCK (i
)->succ
; e
; e
= e
->succ_next
)
802 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
806 probability
= INTVAL (XEXP (find_reg_note (last_insn
,
807 REG_BR_PROB
, 0), 0));
808 fallthru
= BASIC_BLOCK (i
)->succ
;
809 if (!fallthru
->flags
& EDGE_FALLTHRU
)
810 fallthru
= fallthru
->succ_next
;
811 branch
= BASIC_BLOCK (i
)->succ
;
812 if (branch
->flags
& EDGE_FALLTHRU
)
813 branch
= branch
->succ_next
;
815 branch
->probability
= probability
;
816 fallthru
->probability
= REG_BR_PROB_BASE
- probability
;
819 ENTRY_BLOCK_PTR
->succ
->probability
= REG_BR_PROB_BASE
;
821 /* Set up block info for each basic block. */
822 bi
= (block_info
) xcalloc ((n_basic_blocks
+ 2), sizeof (*bi
));
823 ei
= (edge_info
) xcalloc ((n_edges
), sizeof (*ei
));
824 for (i
= -2; i
< n_basic_blocks
; i
++)
830 bb
= ENTRY_BLOCK_PTR
;
834 bb
= BASIC_BLOCK (i
);
835 bb
->aux
= bi
+ i
+ 2;
836 BLOCK_INFO (bb
)->visited
= 1;
837 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
839 e
->aux
= ei
+ edgenum
, edgenum
++;
840 EDGE_INFO (e
)->back_edge_prob
= ((double) e
->probability
844 /* First compute probabilities locally for each loop from innermost
845 to outermost to examine probabilities for back edges. */
846 estimate_loops_at_level (loops
->tree_root
);
848 /* Now fake loop around whole function to finalize probabilities. */
849 for (i
= 0; i
< n_basic_blocks
; i
++)
850 BLOCK_INFO (BASIC_BLOCK (i
))->visited
= 0;
851 BLOCK_INFO (ENTRY_BLOCK_PTR
)->visited
= 0;
852 BLOCK_INFO (EXIT_BLOCK_PTR
)->visited
= 0;
853 propagate_freq (ENTRY_BLOCK_PTR
);
855 for (i
= 0; i
< n_basic_blocks
; i
++)
856 if (BLOCK_INFO (BASIC_BLOCK (i
))->frequency
> freq_max
)
857 freq_max
= BLOCK_INFO (BASIC_BLOCK (i
))->frequency
;
858 for (i
= -2; i
< n_basic_blocks
; i
++)
862 bb
= ENTRY_BLOCK_PTR
;
866 bb
= BASIC_BLOCK (i
);
867 bb
->frequency
= (BLOCK_INFO (bb
)->frequency
* BB_FREQ_MAX
/ freq_max