1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 /* This file contains low level functions to manipulate the CFG and
24 analyze it. All other modules should not transform the data structure
25 directly and use abstraction instead. The file is supposed to be
26 ordered bottom-up and should not contain any code dependent on a
27 particular intermediate language (RTL or trees).
29 Available functionality:
30 - Initialization/deallocation
31 init_flow, clear_edges
32 - Low level basic block manipulation
33 alloc_block, expunge_block
35 make_edge, make_single_succ_edge, cached_make_edge, remove_edge
36 - Low level edge redirection (without updating instruction chain)
37 redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
38 - Dumping and debugging
39 dump_flow_info, debug_flow_info, dump_edge_info
40 - Allocation of AUX fields for basic blocks
41 alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
43 - Consistency checking
45 - Dumping and debugging
46 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
51 #include "coretypes.h"
55 #include "hard-reg-set.h"
65 #include "tree-pass.h"
68 #include "alloc-pool.h"
71 /* The obstack on which the flow graph components are allocated. */
73 struct bitmap_obstack reg_obstack
;
75 void debug_flow_info (void);
76 static void free_edge (edge
);
78 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
80 /* Called once at initialization time. */
86 cfun
->cfg
= ggc_alloc_cleared (sizeof (struct control_flow_graph
));
88 ENTRY_BLOCK_PTR
= ggc_alloc_cleared (sizeof (struct basic_block_def
));
89 ENTRY_BLOCK_PTR
->index
= ENTRY_BLOCK
;
90 EXIT_BLOCK_PTR
= ggc_alloc_cleared (sizeof (struct basic_block_def
));
91 EXIT_BLOCK_PTR
->index
= EXIT_BLOCK
;
92 ENTRY_BLOCK_PTR
->next_bb
= EXIT_BLOCK_PTR
;
93 EXIT_BLOCK_PTR
->prev_bb
= ENTRY_BLOCK_PTR
;
96 /* Helper function for remove_edge and clear_edges. Frees edge structure
97 without actually unlinking it from the pred/succ lists. */
100 free_edge (edge e ATTRIBUTE_UNUSED
)
106 /* Free the memory associated with the edge structures. */
117 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
119 VEC_truncate (edge
, bb
->succs
, 0);
120 VEC_truncate (edge
, bb
->preds
, 0);
123 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
125 VEC_truncate (edge
, EXIT_BLOCK_PTR
->preds
, 0);
126 VEC_truncate (edge
, ENTRY_BLOCK_PTR
->succs
, 0);
128 gcc_assert (!n_edges
);
131 /* Allocate memory for basic_block. */
137 bb
= ggc_alloc_cleared (sizeof (*bb
));
141 /* Link block B to chain after AFTER. */
143 link_block (basic_block b
, basic_block after
)
145 b
->next_bb
= after
->next_bb
;
148 b
->next_bb
->prev_bb
= b
;
151 /* Unlink block B from chain. */
153 unlink_block (basic_block b
)
155 b
->next_bb
->prev_bb
= b
->prev_bb
;
156 b
->prev_bb
->next_bb
= b
->next_bb
;
161 /* Sequentially order blocks and compact the arrays. */
163 compact_blocks (void)
168 SET_BASIC_BLOCK (ENTRY_BLOCK
, ENTRY_BLOCK_PTR
);
169 SET_BASIC_BLOCK (EXIT_BLOCK
, EXIT_BLOCK_PTR
);
171 i
= NUM_FIXED_BLOCKS
;
174 SET_BASIC_BLOCK (i
, bb
);
179 gcc_assert (i
== n_basic_blocks
);
181 for (; i
< last_basic_block
; i
++)
182 SET_BASIC_BLOCK (i
, NULL
);
184 last_basic_block
= n_basic_blocks
;
187 /* Remove block B from the basic block array. */
190 expunge_block (basic_block b
)
193 SET_BASIC_BLOCK (b
->index
, NULL
);
195 /* We should be able to ggc_free here, but we are not.
196 The dead SSA_NAMES are left pointing to dead statements that are pointing
197 to dead basic blocks making garbage collector to die.
198 We should be able to release all dead SSA_NAMES and at the same time we should
199 clear out BB pointer of dead statements consistently. */
202 /* Connect E to E->src. */
207 VEC_safe_push (edge
, gc
, e
->src
->succs
, e
);
210 /* Connect E to E->dest. */
213 connect_dest (edge e
)
215 basic_block dest
= e
->dest
;
216 VEC_safe_push (edge
, gc
, dest
->preds
, e
);
217 e
->dest_idx
= EDGE_COUNT (dest
->preds
) - 1;
220 /* Disconnect edge E from E->src. */
223 disconnect_src (edge e
)
225 basic_block src
= e
->src
;
229 for (ei
= ei_start (src
->succs
); (tmp
= ei_safe_edge (ei
)); )
233 VEC_unordered_remove (edge
, src
->succs
, ei
.index
);
243 /* Disconnect edge E from E->dest. */
246 disconnect_dest (edge e
)
248 basic_block dest
= e
->dest
;
249 unsigned int dest_idx
= e
->dest_idx
;
251 VEC_unordered_remove (edge
, dest
->preds
, dest_idx
);
253 /* If we removed an edge in the middle of the edge vector, we need
254 to update dest_idx of the edge that moved into the "hole". */
255 if (dest_idx
< EDGE_COUNT (dest
->preds
))
256 EDGE_PRED (dest
, dest_idx
)->dest_idx
= dest_idx
;
259 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
260 created edge. Use this only if you are sure that this edge can't
261 possibly already exist. */
264 unchecked_make_edge (basic_block src
, basic_block dst
, int flags
)
267 e
= ggc_alloc_cleared (sizeof (*e
));
277 execute_on_growing_pred (e
);
282 /* Create an edge connecting SRC and DST with FLAGS optionally using
283 edge cache CACHE. Return the new edge, NULL if already exist. */
286 cached_make_edge (sbitmap edge_cache
, basic_block src
, basic_block dst
, int flags
)
288 if (edge_cache
== NULL
289 || src
== ENTRY_BLOCK_PTR
290 || dst
== EXIT_BLOCK_PTR
)
291 return make_edge (src
, dst
, flags
);
293 /* Does the requested edge already exist? */
294 if (! TEST_BIT (edge_cache
, dst
->index
))
296 /* The edge does not exist. Create one and update the
298 SET_BIT (edge_cache
, dst
->index
);
299 return unchecked_make_edge (src
, dst
, flags
);
302 /* At this point, we know that the requested edge exists. Adjust
303 flags if necessary. */
306 edge e
= find_edge (src
, dst
);
313 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
314 created edge or NULL if already exist. */
317 make_edge (basic_block src
, basic_block dest
, int flags
)
319 edge e
= find_edge (src
, dest
);
321 /* Make sure we don't add duplicate edges. */
328 return unchecked_make_edge (src
, dest
, flags
);
331 /* Create an edge connecting SRC to DEST and set probability by knowing
332 that it is the single edge leaving SRC. */
335 make_single_succ_edge (basic_block src
, basic_block dest
, int flags
)
337 edge e
= make_edge (src
, dest
, flags
);
339 e
->probability
= REG_BR_PROB_BASE
;
340 e
->count
= src
->count
;
344 /* This function will remove an edge from the flow graph. */
349 remove_predictions_associated_with_edge (e
);
350 execute_on_shrinking_pred (e
);
358 /* Redirect an edge's successor from one block to another. */
361 redirect_edge_succ (edge e
, basic_block new_succ
)
363 execute_on_shrinking_pred (e
);
369 /* Reconnect the edge to the new successor block. */
372 execute_on_growing_pred (e
);
375 /* Like previous but avoid possible duplicate edge. */
378 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
382 s
= find_edge (e
->src
, new_succ
);
385 s
->flags
|= e
->flags
;
386 s
->probability
+= e
->probability
;
387 if (s
->probability
> REG_BR_PROB_BASE
)
388 s
->probability
= REG_BR_PROB_BASE
;
389 s
->count
+= e
->count
;
394 redirect_edge_succ (e
, new_succ
);
399 /* Redirect an edge's predecessor from one block to another. */
402 redirect_edge_pred (edge e
, basic_block new_pred
)
408 /* Reconnect the edge to the new predecessor block. */
412 /* Clear all basic block flags, with the exception of partitioning. */
414 clear_bb_flags (void)
418 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
419 bb
->flags
= (BB_PARTITION (bb
) | (bb
->flags
& BB_DISABLE_SCHEDULE
)
420 | (bb
->flags
& BB_RTL
));
423 /* Check the consistency of profile information. We can't do that
424 in verify_flow_info, as the counts may get invalid for incompletely
425 solved graphs, later eliminating of conditionals or roundoff errors.
426 It is still practical to have them reported for debugging of simple
429 check_bb_profile (basic_block bb
, FILE * file
)
436 if (profile_status
== PROFILE_ABSENT
)
439 if (bb
!= EXIT_BLOCK_PTR
)
441 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
442 sum
+= e
->probability
;
443 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
444 fprintf (file
, "Invalid sum of outgoing probabilities %.1f%%\n",
445 sum
* 100.0 / REG_BR_PROB_BASE
);
447 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
449 if (EDGE_COUNT (bb
->succs
)
450 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
451 fprintf (file
, "Invalid sum of outgoing counts %i, should be %i\n",
452 (int) lsum
, (int) bb
->count
);
454 if (bb
!= ENTRY_BLOCK_PTR
)
457 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
458 sum
+= EDGE_FREQUENCY (e
);
459 if (abs (sum
- bb
->frequency
) > 100)
461 "Invalid sum of incoming frequencies %i, should be %i\n",
464 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
466 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
467 fprintf (file
, "Invalid sum of incoming counts %i, should be %i\n",
468 (int) lsum
, (int) bb
->count
);
472 /* Emit basic block information for BB. HEADER is true if the user wants
473 the generic information and the predecessors, FOOTER is true if they want
474 the successors. FLAGS is the dump flags of interest; TDF_DETAILS emit
475 global register liveness information. PREFIX is put in front of every
476 line. The output is emitted to FILE. */
478 dump_bb_info (basic_block bb
, bool header
, bool footer
, int flags
,
479 const char *prefix
, FILE *file
)
486 fprintf (file
, "\n%sBasic block %d ", prefix
, bb
->index
);
488 fprintf (file
, ", prev %d", bb
->prev_bb
->index
);
490 fprintf (file
, ", next %d", bb
->next_bb
->index
);
491 fprintf (file
, ", loop_depth %d, count ", bb
->loop_depth
);
492 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
493 fprintf (file
, ", freq %i", bb
->frequency
);
494 if (maybe_hot_bb_p (bb
))
495 fprintf (file
, ", maybe hot");
496 if (probably_never_executed_bb_p (bb
))
497 fprintf (file
, ", probably never executed");
498 fprintf (file
, ".\n");
500 fprintf (file
, "%sPredecessors: ", prefix
);
501 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
502 dump_edge_info (file
, e
, 0);
507 fprintf (file
, "\n%sSuccessors: ", prefix
);
508 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
509 dump_edge_info (file
, e
, 1);
512 if ((flags
& TDF_DETAILS
)
513 && (bb
->flags
& BB_RTL
))
515 if (bb
->il
.rtl
->global_live_at_start
&& header
)
517 fprintf (file
, "\n%sRegisters live at start:", prefix
);
518 dump_regset (bb
->il
.rtl
->global_live_at_start
, file
);
521 if (bb
->il
.rtl
->global_live_at_end
&& footer
)
523 fprintf (file
, "\n%sRegisters live at end:", prefix
);
524 dump_regset (bb
->il
.rtl
->global_live_at_end
, file
);
532 dump_flow_info (FILE *file
, int flags
)
536 /* There are no pseudo registers after reload. Don't dump them. */
537 if (reg_n_info
&& !reload_completed
538 && (flags
& TDF_DETAILS
) != 0)
540 unsigned int i
, max
= max_reg_num ();
541 fprintf (file
, "%d registers.\n", max
);
542 for (i
= FIRST_PSEUDO_REGISTER
; i
< max
; i
++)
545 enum reg_class
class, altclass
;
547 fprintf (file
, "\nRegister %d used %d times across %d insns",
548 i
, REG_N_REFS (i
), REG_LIVE_LENGTH (i
));
549 if (REG_BASIC_BLOCK (i
) >= 0)
550 fprintf (file
, " in block %d", REG_BASIC_BLOCK (i
));
552 fprintf (file
, "; set %d time%s", REG_N_SETS (i
),
553 (REG_N_SETS (i
) == 1) ? "" : "s");
554 if (regno_reg_rtx
[i
] != NULL
&& REG_USERVAR_P (regno_reg_rtx
[i
]))
555 fprintf (file
, "; user var");
556 if (REG_N_DEATHS (i
) != 1)
557 fprintf (file
, "; dies in %d places", REG_N_DEATHS (i
));
558 if (REG_N_CALLS_CROSSED (i
) == 1)
559 fprintf (file
, "; crosses 1 call");
560 else if (REG_N_CALLS_CROSSED (i
))
561 fprintf (file
, "; crosses %d calls", REG_N_CALLS_CROSSED (i
));
562 if (regno_reg_rtx
[i
] != NULL
563 && PSEUDO_REGNO_BYTES (i
) != UNITS_PER_WORD
)
564 fprintf (file
, "; %d bytes", PSEUDO_REGNO_BYTES (i
));
566 class = reg_preferred_class (i
);
567 altclass
= reg_alternate_class (i
);
568 if (class != GENERAL_REGS
|| altclass
!= ALL_REGS
)
570 if (altclass
== ALL_REGS
|| class == ALL_REGS
)
571 fprintf (file
, "; pref %s", reg_class_names
[(int) class]);
572 else if (altclass
== NO_REGS
)
573 fprintf (file
, "; %s or none", reg_class_names
[(int) class]);
575 fprintf (file
, "; pref %s, else %s",
576 reg_class_names
[(int) class],
577 reg_class_names
[(int) altclass
]);
580 if (regno_reg_rtx
[i
] != NULL
&& REG_POINTER (regno_reg_rtx
[i
]))
581 fprintf (file
, "; pointer");
582 fprintf (file
, ".\n");
586 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks
, n_edges
);
589 dump_bb_info (bb
, true, true, flags
, "", file
);
590 check_bb_profile (bb
, file
);
597 debug_flow_info (void)
599 dump_flow_info (stderr
, TDF_DETAILS
);
603 dump_edge_info (FILE *file
, edge e
, int do_succ
)
605 basic_block side
= (do_succ
? e
->dest
: e
->src
);
607 if (side
== ENTRY_BLOCK_PTR
)
608 fputs (" ENTRY", file
);
609 else if (side
== EXIT_BLOCK_PTR
)
610 fputs (" EXIT", file
);
612 fprintf (file
, " %d", side
->index
);
615 fprintf (file
, " [%.1f%%] ", e
->probability
* 100.0 / REG_BR_PROB_BASE
);
619 fprintf (file
, " count:");
620 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
625 static const char * const bitnames
[] = {
626 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
627 "can_fallthru", "irreducible", "sibcall", "loop_exit",
628 "true", "false", "exec"
631 int i
, flags
= e
->flags
;
634 for (i
= 0; flags
; i
++)
635 if (flags
& (1 << i
))
641 if (i
< (int) ARRAY_SIZE (bitnames
))
642 fputs (bitnames
[i
], file
);
644 fprintf (file
, "%d", i
);
652 /* Simple routines to easily allocate AUX fields of basic blocks. */
654 static struct obstack block_aux_obstack
;
655 static void *first_block_aux_obj
= 0;
656 static struct obstack edge_aux_obstack
;
657 static void *first_edge_aux_obj
= 0;
659 /* Allocate a memory block of SIZE as BB->aux. The obstack must
660 be first initialized by alloc_aux_for_blocks. */
663 alloc_aux_for_block (basic_block bb
, int size
)
665 /* Verify that aux field is clear. */
666 gcc_assert (!bb
->aux
&& first_block_aux_obj
);
667 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
668 memset (bb
->aux
, 0, size
);
671 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
672 alloc_aux_for_block for each basic block. */
675 alloc_aux_for_blocks (int size
)
677 static int initialized
;
681 gcc_obstack_init (&block_aux_obstack
);
685 /* Check whether AUX data are still allocated. */
686 gcc_assert (!first_block_aux_obj
);
688 first_block_aux_obj
= obstack_alloc (&block_aux_obstack
, 0);
693 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
694 alloc_aux_for_block (bb
, size
);
698 /* Clear AUX pointers of all blocks. */
701 clear_aux_for_blocks (void)
705 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
709 /* Free data allocated in block_aux_obstack and clear AUX pointers
713 free_aux_for_blocks (void)
715 gcc_assert (first_block_aux_obj
);
716 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
717 first_block_aux_obj
= NULL
;
719 clear_aux_for_blocks ();
722 /* Allocate a memory edge of SIZE as BB->aux. The obstack must
723 be first initialized by alloc_aux_for_edges. */
726 alloc_aux_for_edge (edge e
, int size
)
728 /* Verify that aux field is clear. */
729 gcc_assert (!e
->aux
&& first_edge_aux_obj
);
730 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
731 memset (e
->aux
, 0, size
);
734 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
735 alloc_aux_for_edge for each basic edge. */
738 alloc_aux_for_edges (int size
)
740 static int initialized
;
744 gcc_obstack_init (&edge_aux_obstack
);
748 /* Check whether AUX data are still allocated. */
749 gcc_assert (!first_edge_aux_obj
);
751 first_edge_aux_obj
= obstack_alloc (&edge_aux_obstack
, 0);
756 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
761 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
762 alloc_aux_for_edge (e
, size
);
767 /* Clear AUX pointers of all edges. */
770 clear_aux_for_edges (void)
775 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
778 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
783 /* Free data allocated in edge_aux_obstack and clear AUX pointers
787 free_aux_for_edges (void)
789 gcc_assert (first_edge_aux_obj
);
790 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
791 first_edge_aux_obj
= NULL
;
793 clear_aux_for_edges ();
797 debug_bb (basic_block bb
)
799 dump_bb (bb
, stderr
, 0);
805 basic_block bb
= BASIC_BLOCK (n
);
806 dump_bb (bb
, stderr
, 0);
810 /* Dumps cfg related information about basic block BB to FILE. */
813 dump_cfg_bb_info (FILE *file
, basic_block bb
)
818 static const char * const bb_bitnames
[] =
820 "dirty", "new", "reachable", "visited", "irreducible_loop", "superblock"
822 const unsigned n_bitnames
= sizeof (bb_bitnames
) / sizeof (char *);
825 fprintf (file
, "Basic block %d", bb
->index
);
826 for (i
= 0; i
< n_bitnames
; i
++)
827 if (bb
->flags
& (1 << i
))
830 fprintf (file
, " (");
832 fprintf (file
, ", ");
834 fprintf (file
, bb_bitnames
[i
]);
838 fprintf (file
, "\n");
840 fprintf (file
, "Predecessors: ");
841 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
842 dump_edge_info (file
, e
, 0);
844 fprintf (file
, "\nSuccessors: ");
845 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
846 dump_edge_info (file
, e
, 1);
847 fprintf (file
, "\n\n");
850 /* Dumps a brief description of cfg to FILE. */
853 brief_dump_cfg (FILE *file
)
859 dump_cfg_bb_info (file
, bb
);
863 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
864 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
865 redirected to destination of TAKEN_EDGE.
867 This function may leave the profile inconsistent in the case TAKEN_EDGE
868 frequency or count is believed to be lower than FREQUENCY or COUNT
871 update_bb_profile_for_threading (basic_block bb
, int edge_frequency
,
872 gcov_type count
, edge taken_edge
)
882 fprintf (dump_file
, "bb %i count became negative after threading",
887 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
888 Watch for overflows. */
890 prob
= edge_frequency
* REG_BR_PROB_BASE
/ bb
->frequency
;
893 if (prob
> taken_edge
->probability
)
896 fprintf (dump_file
, "Jump threading proved probability of edge "
897 "%i->%i too small (it is %i, should be %i).\n",
898 taken_edge
->src
->index
, taken_edge
->dest
->index
,
899 taken_edge
->probability
, prob
);
900 prob
= taken_edge
->probability
;
903 /* Now rescale the probabilities. */
904 taken_edge
->probability
-= prob
;
905 prob
= REG_BR_PROB_BASE
- prob
;
906 bb
->frequency
-= edge_frequency
;
907 if (bb
->frequency
< 0)
912 fprintf (dump_file
, "Edge frequencies of bb %i has been reset, "
913 "frequency of block should end up being 0, it is %i\n",
914 bb
->index
, bb
->frequency
);
915 EDGE_SUCC (bb
, 0)->probability
= REG_BR_PROB_BASE
;
916 ei
= ei_start (bb
->succs
);
918 for (; (c
= ei_safe_edge (ei
)); ei_next (&ei
))
921 else if (prob
!= REG_BR_PROB_BASE
)
923 int scale
= RDIV (65536 * REG_BR_PROB_BASE
, prob
);
925 FOR_EACH_EDGE (c
, ei
, bb
->succs
)
927 c
->probability
= RDIV (c
->probability
* scale
, 65536);
928 if (c
->probability
> REG_BR_PROB_BASE
)
929 c
->probability
= REG_BR_PROB_BASE
;
933 gcc_assert (bb
== taken_edge
->src
);
934 taken_edge
->count
-= count
;
935 if (taken_edge
->count
< 0)
938 fprintf (dump_file
, "edge %i->%i count became negative after threading",
939 taken_edge
->src
->index
, taken_edge
->dest
->index
);
940 taken_edge
->count
= 0;
944 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
945 by NUM/DEN, in int arithmetic. May lose some accuracy. */
947 scale_bbs_frequencies_int (basic_block
*bbs
, int nbbs
, int num
, int den
)
954 /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
955 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
956 and still safely fit in int during calculations. */
962 num
= RDIV (1000 * num
, den
);
968 for (i
= 0; i
< nbbs
; i
++)
971 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
972 /* Make sure the frequencies do not grow over BB_FREQ_MAX. */
973 if (bbs
[i
]->frequency
> BB_FREQ_MAX
)
974 bbs
[i
]->frequency
= BB_FREQ_MAX
;
975 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
976 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
977 e
->count
= RDIV (e
->count
* num
, den
);
981 /* numbers smaller than this value are safe to multiply without getting
983 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
985 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
986 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
987 function but considerably slower. */
989 scale_bbs_frequencies_gcov_type (basic_block
*bbs
, int nbbs
, gcov_type num
,
994 gcov_type fraction
= RDIV (num
* 65536, den
);
996 gcc_assert (fraction
>= 0);
998 if (num
< MAX_SAFE_MULTIPLIER
)
999 for (i
= 0; i
< nbbs
; i
++)
1002 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
1003 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
1004 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
1006 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
1007 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1008 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
1009 e
->count
= RDIV (e
->count
* num
, den
);
1011 e
->count
= RDIV (e
->count
* fraction
, 65536);
1014 for (i
= 0; i
< nbbs
; i
++)
1017 if (sizeof (gcov_type
) > sizeof (int))
1018 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
1020 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* fraction
, 65536);
1021 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
1022 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1023 e
->count
= RDIV (e
->count
* fraction
, 65536);
1027 /* Data structures used to maintain mapping between basic blocks and
1029 static htab_t bb_original
;
1030 static htab_t bb_copy
;
1032 /* And between loops and copies. */
1033 static htab_t loop_copy
;
1034 static alloc_pool original_copy_bb_pool
;
1036 struct htab_bb_copy_original_entry
1038 /* Block we are attaching info to. */
1040 /* Index of original or copy (depending on the hashtable) */
1045 bb_copy_original_hash (const void *p
)
1047 struct htab_bb_copy_original_entry
*data
1048 = ((struct htab_bb_copy_original_entry
*)p
);
1050 return data
->index1
;
1053 bb_copy_original_eq (const void *p
, const void *q
)
1055 struct htab_bb_copy_original_entry
*data
1056 = ((struct htab_bb_copy_original_entry
*)p
);
1057 struct htab_bb_copy_original_entry
*data2
1058 = ((struct htab_bb_copy_original_entry
*)q
);
1060 return data
->index1
== data2
->index1
;
1063 /* Initialize the data structures to maintain mapping between blocks
1066 initialize_original_copy_tables (void)
1068 gcc_assert (!original_copy_bb_pool
);
1069 original_copy_bb_pool
1070 = create_alloc_pool ("original_copy",
1071 sizeof (struct htab_bb_copy_original_entry
), 10);
1072 bb_original
= htab_create (10, bb_copy_original_hash
,
1073 bb_copy_original_eq
, NULL
);
1074 bb_copy
= htab_create (10, bb_copy_original_hash
, bb_copy_original_eq
, NULL
);
1075 loop_copy
= htab_create (10, bb_copy_original_hash
, bb_copy_original_eq
, NULL
);
1078 /* Free the data structures to maintain mapping between blocks and
1081 free_original_copy_tables (void)
1083 gcc_assert (original_copy_bb_pool
);
1084 htab_delete (bb_copy
);
1085 htab_delete (bb_original
);
1086 htab_delete (loop_copy
);
1087 free_alloc_pool (original_copy_bb_pool
);
1091 original_copy_bb_pool
= NULL
;
1094 /* Removes the value associated with OBJ from table TAB. */
1097 copy_original_table_clear (htab_t tab
, unsigned obj
)
1100 struct htab_bb_copy_original_entry key
, *elt
;
1102 if (!original_copy_bb_pool
)
1106 slot
= htab_find_slot (tab
, &key
, NO_INSERT
);
1111 htab_clear_slot (tab
, slot
);
1112 pool_free (original_copy_bb_pool
, elt
);
1115 /* Sets the value associated with OBJ in table TAB to VAL.
1116 Do nothing when data structures are not initialized. */
1119 copy_original_table_set (htab_t tab
, unsigned obj
, unsigned val
)
1121 struct htab_bb_copy_original_entry
**slot
;
1122 struct htab_bb_copy_original_entry key
;
1124 if (!original_copy_bb_pool
)
1128 slot
= (struct htab_bb_copy_original_entry
**)
1129 htab_find_slot (tab
, &key
, INSERT
);
1132 *slot
= pool_alloc (original_copy_bb_pool
);
1133 (*slot
)->index1
= obj
;
1135 (*slot
)->index2
= val
;
1138 /* Set original for basic block. Do nothing when data structures are not
1139 initialized so passes not needing this don't need to care. */
1141 set_bb_original (basic_block bb
, basic_block original
)
1143 copy_original_table_set (bb_original
, bb
->index
, original
->index
);
1146 /* Get the original basic block. */
1148 get_bb_original (basic_block bb
)
1150 struct htab_bb_copy_original_entry
*entry
;
1151 struct htab_bb_copy_original_entry key
;
1153 gcc_assert (original_copy_bb_pool
);
1155 key
.index1
= bb
->index
;
1156 entry
= (struct htab_bb_copy_original_entry
*) htab_find (bb_original
, &key
);
1158 return BASIC_BLOCK (entry
->index2
);
1163 /* Set copy for basic block. Do nothing when data structures are not
1164 initialized so passes not needing this don't need to care. */
1166 set_bb_copy (basic_block bb
, basic_block copy
)
1168 copy_original_table_set (bb_copy
, bb
->index
, copy
->index
);
1171 /* Get the copy of basic block. */
1173 get_bb_copy (basic_block bb
)
1175 struct htab_bb_copy_original_entry
*entry
;
1176 struct htab_bb_copy_original_entry key
;
1178 gcc_assert (original_copy_bb_pool
);
1180 key
.index1
= bb
->index
;
1181 entry
= (struct htab_bb_copy_original_entry
*) htab_find (bb_copy
, &key
);
1183 return BASIC_BLOCK (entry
->index2
);
1188 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1189 initialized so passes not needing this don't need to care. */
1192 set_loop_copy (struct loop
*loop
, struct loop
*copy
)
1195 copy_original_table_clear (loop_copy
, loop
->num
);
1197 copy_original_table_set (loop_copy
, loop
->num
, copy
->num
);
1200 /* Get the copy of LOOP. */
1203 get_loop_copy (struct loop
*loop
)
1205 struct htab_bb_copy_original_entry
*entry
;
1206 struct htab_bb_copy_original_entry key
;
1208 gcc_assert (original_copy_bb_pool
);
1210 key
.index1
= loop
->num
;
1211 entry
= (struct htab_bb_copy_original_entry
*) htab_find (loop_copy
, &key
);
1213 return get_loop (entry
->index2
);