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, 2006, 2007
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 3, 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 COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file contains low level functions to manipulate the CFG and
23 analyze it. All other modules should not transform the data structure
24 directly and use abstraction instead. The file is supposed to be
25 ordered bottom-up and should not contain any code dependent on a
26 particular intermediate language (RTL or trees).
28 Available functionality:
29 - Initialization/deallocation
30 init_flow, clear_edges
31 - Low level basic block manipulation
32 alloc_block, expunge_block
34 make_edge, make_single_succ_edge, cached_make_edge, remove_edge
35 - Low level edge redirection (without updating instruction chain)
36 redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
37 - Dumping and debugging
38 dump_flow_info, debug_flow_info, dump_edge_info
39 - Allocation of AUX fields for basic blocks
40 alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
42 - Consistency checking
44 - Dumping and debugging
45 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
50 #include "coretypes.h"
54 #include "hard-reg-set.h"
64 #include "tree-pass.h"
67 #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_CNEW (struct control_flow_graph
);
88 ENTRY_BLOCK_PTR
= GGC_CNEW (struct basic_block_def
);
89 ENTRY_BLOCK_PTR
->index
= ENTRY_BLOCK
;
90 EXIT_BLOCK_PTR
= GGC_CNEW (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_CNEW (struct basic_block_def
);
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)
167 SET_BASIC_BLOCK (ENTRY_BLOCK
, ENTRY_BLOCK_PTR
);
168 SET_BASIC_BLOCK (EXIT_BLOCK
, EXIT_BLOCK_PTR
);
171 df_compact_blocks ();
176 i
= NUM_FIXED_BLOCKS
;
179 SET_BASIC_BLOCK (i
, bb
);
183 gcc_assert (i
== n_basic_blocks
);
185 for (; i
< last_basic_block
; i
++)
186 SET_BASIC_BLOCK (i
, NULL
);
188 last_basic_block
= n_basic_blocks
;
191 /* Remove block B from the basic block array. */
194 expunge_block (basic_block b
)
197 SET_BASIC_BLOCK (b
->index
, NULL
);
199 /* We should be able to ggc_free here, but we are not.
200 The dead SSA_NAMES are left pointing to dead statements that are pointing
201 to dead basic blocks making garbage collector to die.
202 We should be able to release all dead SSA_NAMES and at the same time we should
203 clear out BB pointer of dead statements consistently. */
206 /* Connect E to E->src. */
211 VEC_safe_push (edge
, gc
, e
->src
->succs
, e
);
212 df_mark_solutions_dirty ();
215 /* Connect E to E->dest. */
218 connect_dest (edge e
)
220 basic_block dest
= e
->dest
;
221 VEC_safe_push (edge
, gc
, dest
->preds
, e
);
222 e
->dest_idx
= EDGE_COUNT (dest
->preds
) - 1;
223 df_mark_solutions_dirty ();
226 /* Disconnect edge E from E->src. */
229 disconnect_src (edge e
)
231 basic_block src
= e
->src
;
235 for (ei
= ei_start (src
->succs
); (tmp
= ei_safe_edge (ei
)); )
239 VEC_unordered_remove (edge
, src
->succs
, ei
.index
);
246 df_mark_solutions_dirty ();
250 /* Disconnect edge E from E->dest. */
253 disconnect_dest (edge e
)
255 basic_block dest
= e
->dest
;
256 unsigned int dest_idx
= e
->dest_idx
;
258 VEC_unordered_remove (edge
, dest
->preds
, dest_idx
);
260 /* If we removed an edge in the middle of the edge vector, we need
261 to update dest_idx of the edge that moved into the "hole". */
262 if (dest_idx
< EDGE_COUNT (dest
->preds
))
263 EDGE_PRED (dest
, dest_idx
)->dest_idx
= dest_idx
;
264 df_mark_solutions_dirty ();
267 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
268 created edge. Use this only if you are sure that this edge can't
269 possibly already exist. */
272 unchecked_make_edge (basic_block src
, basic_block dst
, int flags
)
275 e
= GGC_CNEW (struct edge_def
);
285 execute_on_growing_pred (e
);
289 /* Create an edge connecting SRC and DST with FLAGS optionally using
290 edge cache CACHE. Return the new edge, NULL if already exist. */
293 cached_make_edge (sbitmap edge_cache
, basic_block src
, basic_block dst
, int flags
)
295 if (edge_cache
== NULL
296 || src
== ENTRY_BLOCK_PTR
297 || dst
== EXIT_BLOCK_PTR
)
298 return make_edge (src
, dst
, flags
);
300 /* Does the requested edge already exist? */
301 if (! TEST_BIT (edge_cache
, dst
->index
))
303 /* The edge does not exist. Create one and update the
305 SET_BIT (edge_cache
, dst
->index
);
306 return unchecked_make_edge (src
, dst
, flags
);
309 /* At this point, we know that the requested edge exists. Adjust
310 flags if necessary. */
313 edge e
= find_edge (src
, dst
);
320 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
321 created edge or NULL if already exist. */
324 make_edge (basic_block src
, basic_block dest
, int flags
)
326 edge e
= find_edge (src
, dest
);
328 /* Make sure we don't add duplicate edges. */
335 return unchecked_make_edge (src
, dest
, flags
);
338 /* Create an edge connecting SRC to DEST and set probability by knowing
339 that it is the single edge leaving SRC. */
342 make_single_succ_edge (basic_block src
, basic_block dest
, int flags
)
344 edge e
= make_edge (src
, dest
, flags
);
346 e
->probability
= REG_BR_PROB_BASE
;
347 e
->count
= src
->count
;
351 /* This function will remove an edge from the flow graph. */
354 remove_edge_raw (edge e
)
356 remove_predictions_associated_with_edge (e
);
357 execute_on_shrinking_pred (e
);
365 /* Redirect an edge's successor from one block to another. */
368 redirect_edge_succ (edge e
, basic_block new_succ
)
370 execute_on_shrinking_pred (e
);
376 /* Reconnect the edge to the new successor block. */
379 execute_on_growing_pred (e
);
382 /* Like previous but avoid possible duplicate edge. */
385 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
389 s
= find_edge (e
->src
, new_succ
);
392 s
->flags
|= e
->flags
;
393 s
->probability
+= e
->probability
;
394 if (s
->probability
> REG_BR_PROB_BASE
)
395 s
->probability
= REG_BR_PROB_BASE
;
396 s
->count
+= e
->count
;
401 redirect_edge_succ (e
, new_succ
);
406 /* Redirect an edge's predecessor from one block to another. */
409 redirect_edge_pred (edge e
, basic_block new_pred
)
415 /* Reconnect the edge to the new predecessor block. */
419 /* Clear all basic block flags, with the exception of partitioning and
422 clear_bb_flags (void)
426 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
427 bb
->flags
= (BB_PARTITION (bb
)
428 | (bb
->flags
& (BB_DISABLE_SCHEDULE
+ BB_RTL
+ BB_NON_LOCAL_GOTO_TARGET
)));
431 /* Check the consistency of profile information. We can't do that
432 in verify_flow_info, as the counts may get invalid for incompletely
433 solved graphs, later eliminating of conditionals or roundoff errors.
434 It is still practical to have them reported for debugging of simple
437 check_bb_profile (basic_block bb
, FILE * file
)
444 if (profile_status
== PROFILE_ABSENT
)
447 if (bb
!= EXIT_BLOCK_PTR
)
449 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
450 sum
+= e
->probability
;
451 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
452 fprintf (file
, "Invalid sum of outgoing probabilities %.1f%%\n",
453 sum
* 100.0 / REG_BR_PROB_BASE
);
455 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
457 if (EDGE_COUNT (bb
->succs
)
458 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
459 fprintf (file
, "Invalid sum of outgoing counts %i, should be %i\n",
460 (int) lsum
, (int) bb
->count
);
462 if (bb
!= ENTRY_BLOCK_PTR
)
465 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
466 sum
+= EDGE_FREQUENCY (e
);
467 if (abs (sum
- bb
->frequency
) > 100)
469 "Invalid sum of incoming frequencies %i, should be %i\n",
472 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
474 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
475 fprintf (file
, "Invalid sum of incoming counts %i, should be %i\n",
476 (int) lsum
, (int) bb
->count
);
480 /* Write information about registers and basic blocks into FILE.
481 This is part of making a debugging dump. */
484 dump_regset (regset r
, FILE *outf
)
487 reg_set_iterator rsi
;
491 fputs (" (nil)", outf
);
495 EXECUTE_IF_SET_IN_REG_SET (r
, 0, i
, rsi
)
497 fprintf (outf
, " %d", i
);
498 if (i
< FIRST_PSEUDO_REGISTER
)
499 fprintf (outf
, " [%s]",
504 /* Print a human-readable representation of R on the standard error
505 stream. This function is designed to be used from within the
509 debug_regset (regset r
)
511 dump_regset (r
, stderr
);
515 /* Emit basic block information for BB. HEADER is true if the user wants
516 the generic information and the predecessors, FOOTER is true if they want
517 the successors. FLAGS is the dump flags of interest; TDF_DETAILS emit
518 global register liveness information. PREFIX is put in front of every
519 line. The output is emitted to FILE. */
521 dump_bb_info (basic_block bb
, bool header
, bool footer
, int flags
,
522 const char *prefix
, FILE *file
)
529 fprintf (file
, "\n%sBasic block %d ", prefix
, bb
->index
);
531 fprintf (file
, ", prev %d", bb
->prev_bb
->index
);
533 fprintf (file
, ", next %d", bb
->next_bb
->index
);
534 fprintf (file
, ", loop_depth %d, count ", bb
->loop_depth
);
535 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
536 fprintf (file
, ", freq %i", bb
->frequency
);
537 /* Both maybe_hot_bb_p & probably_never_executed_bb_p functions
538 crash without cfun. */
539 if (cfun
&& maybe_hot_bb_p (bb
))
540 fprintf (file
, ", maybe hot");
541 if (cfun
&& probably_never_executed_bb_p (bb
))
542 fprintf (file
, ", probably never executed");
543 fprintf (file
, ".\n");
545 fprintf (file
, "%sPredecessors: ", prefix
);
546 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
547 dump_edge_info (file
, e
, 0);
549 if ((flags
& TDF_DETAILS
)
550 && (bb
->flags
& BB_RTL
)
553 fprintf (file
, "\n");
554 df_dump_top (bb
, file
);
560 fprintf (file
, "\n%sSuccessors: ", prefix
);
561 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
562 dump_edge_info (file
, e
, 1);
564 if ((flags
& TDF_DETAILS
)
565 && (bb
->flags
& BB_RTL
)
568 fprintf (file
, "\n");
569 df_dump_bottom (bb
, file
);
576 /* Dump the register info to FILE. */
579 dump_reg_info (FILE *file
)
581 unsigned int i
, max
= max_reg_num ();
582 if (reload_completed
)
585 if (reg_info_p_size
< max
)
586 max
= reg_info_p_size
;
588 fprintf (file
, "%d registers.\n", max
);
589 for (i
= FIRST_PSEUDO_REGISTER
; i
< max
; i
++)
591 enum reg_class
class, altclass
;
593 if (regstat_n_sets_and_refs
)
594 fprintf (file
, "\nRegister %d used %d times across %d insns",
595 i
, REG_N_REFS (i
), REG_LIVE_LENGTH (i
));
597 fprintf (file
, "\nRegister %d used %d times across %d insns",
598 i
, DF_REG_USE_COUNT (i
) + DF_REG_DEF_COUNT (i
), REG_LIVE_LENGTH (i
));
600 if (REG_BASIC_BLOCK (i
) >= NUM_FIXED_BLOCKS
)
601 fprintf (file
, " in block %d", REG_BASIC_BLOCK (i
));
602 if (regstat_n_sets_and_refs
)
603 fprintf (file
, "; set %d time%s", REG_N_SETS (i
),
604 (REG_N_SETS (i
) == 1) ? "" : "s");
606 fprintf (file
, "; set %d time%s", DF_REG_DEF_COUNT (i
),
607 (DF_REG_DEF_COUNT (i
) == 1) ? "" : "s");
608 if (regno_reg_rtx
[i
] != NULL
&& REG_USERVAR_P (regno_reg_rtx
[i
]))
609 fprintf (file
, "; user var");
610 if (REG_N_DEATHS (i
) != 1)
611 fprintf (file
, "; dies in %d places", REG_N_DEATHS (i
));
612 if (REG_N_CALLS_CROSSED (i
) == 1)
613 fprintf (file
, "; crosses 1 call");
614 else if (REG_N_CALLS_CROSSED (i
))
615 fprintf (file
, "; crosses %d calls", REG_N_CALLS_CROSSED (i
));
616 if (regno_reg_rtx
[i
] != NULL
617 && PSEUDO_REGNO_BYTES (i
) != UNITS_PER_WORD
)
618 fprintf (file
, "; %d bytes", PSEUDO_REGNO_BYTES (i
));
620 class = reg_preferred_class (i
);
621 altclass
= reg_alternate_class (i
);
622 if (class != GENERAL_REGS
|| altclass
!= ALL_REGS
)
624 if (altclass
== ALL_REGS
|| class == ALL_REGS
)
625 fprintf (file
, "; pref %s", reg_class_names
[(int) class]);
626 else if (altclass
== NO_REGS
)
627 fprintf (file
, "; %s or none", reg_class_names
[(int) class]);
629 fprintf (file
, "; pref %s, else %s",
630 reg_class_names
[(int) class],
631 reg_class_names
[(int) altclass
]);
634 if (regno_reg_rtx
[i
] != NULL
&& REG_POINTER (regno_reg_rtx
[i
]))
635 fprintf (file
, "; pointer");
636 fprintf (file
, ".\n");
642 dump_flow_info (FILE *file
, int flags
)
646 /* There are no pseudo registers after reload. Don't dump them. */
647 if (reg_info_p_size
&& (flags
& TDF_DETAILS
) != 0)
648 dump_reg_info (file
);
650 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks
, n_edges
);
653 dump_bb_info (bb
, true, true, flags
, "", file
);
654 check_bb_profile (bb
, file
);
661 debug_flow_info (void)
663 dump_flow_info (stderr
, TDF_DETAILS
);
667 dump_edge_info (FILE *file
, edge e
, int do_succ
)
669 basic_block side
= (do_succ
? e
->dest
: e
->src
);
670 /* both ENTRY_BLOCK_PTR & EXIT_BLOCK_PTR depend upon cfun. */
671 if (cfun
&& side
== ENTRY_BLOCK_PTR
)
672 fputs (" ENTRY", file
);
673 else if (cfun
&& side
== EXIT_BLOCK_PTR
)
674 fputs (" EXIT", file
);
676 fprintf (file
, " %d", side
->index
);
679 fprintf (file
, " [%.1f%%] ", e
->probability
* 100.0 / REG_BR_PROB_BASE
);
683 fprintf (file
, " count:");
684 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
689 static const char * const bitnames
[] = {
690 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
691 "can_fallthru", "irreducible", "sibcall", "loop_exit",
692 "true", "false", "exec"
695 int i
, flags
= e
->flags
;
698 for (i
= 0; flags
; i
++)
699 if (flags
& (1 << i
))
705 if (i
< (int) ARRAY_SIZE (bitnames
))
706 fputs (bitnames
[i
], file
);
708 fprintf (file
, "%d", i
);
716 /* Simple routines to easily allocate AUX fields of basic blocks. */
718 static struct obstack block_aux_obstack
;
719 static void *first_block_aux_obj
= 0;
720 static struct obstack edge_aux_obstack
;
721 static void *first_edge_aux_obj
= 0;
723 /* Allocate a memory block of SIZE as BB->aux. The obstack must
724 be first initialized by alloc_aux_for_blocks. */
727 alloc_aux_for_block (basic_block bb
, int size
)
729 /* Verify that aux field is clear. */
730 gcc_assert (!bb
->aux
&& first_block_aux_obj
);
731 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
732 memset (bb
->aux
, 0, size
);
735 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
736 alloc_aux_for_block for each basic block. */
739 alloc_aux_for_blocks (int size
)
741 static int initialized
;
745 gcc_obstack_init (&block_aux_obstack
);
749 /* Check whether AUX data are still allocated. */
750 gcc_assert (!first_block_aux_obj
);
752 first_block_aux_obj
= obstack_alloc (&block_aux_obstack
, 0);
757 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
758 alloc_aux_for_block (bb
, size
);
762 /* Clear AUX pointers of all blocks. */
765 clear_aux_for_blocks (void)
769 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
773 /* Free data allocated in block_aux_obstack and clear AUX pointers
777 free_aux_for_blocks (void)
779 gcc_assert (first_block_aux_obj
);
780 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
781 first_block_aux_obj
= NULL
;
783 clear_aux_for_blocks ();
786 /* Allocate a memory edge of SIZE as BB->aux. The obstack must
787 be first initialized by alloc_aux_for_edges. */
790 alloc_aux_for_edge (edge e
, int size
)
792 /* Verify that aux field is clear. */
793 gcc_assert (!e
->aux
&& first_edge_aux_obj
);
794 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
795 memset (e
->aux
, 0, size
);
798 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
799 alloc_aux_for_edge for each basic edge. */
802 alloc_aux_for_edges (int size
)
804 static int initialized
;
808 gcc_obstack_init (&edge_aux_obstack
);
812 /* Check whether AUX data are still allocated. */
813 gcc_assert (!first_edge_aux_obj
);
815 first_edge_aux_obj
= obstack_alloc (&edge_aux_obstack
, 0);
820 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
825 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
826 alloc_aux_for_edge (e
, size
);
831 /* Clear AUX pointers of all edges. */
834 clear_aux_for_edges (void)
839 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
842 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
847 /* Free data allocated in edge_aux_obstack and clear AUX pointers
851 free_aux_for_edges (void)
853 gcc_assert (first_edge_aux_obj
);
854 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
855 first_edge_aux_obj
= NULL
;
857 clear_aux_for_edges ();
861 debug_bb (basic_block bb
)
863 dump_bb (bb
, stderr
, 0);
869 basic_block bb
= BASIC_BLOCK (n
);
870 dump_bb (bb
, stderr
, 0);
874 /* Dumps cfg related information about basic block BB to FILE. */
877 dump_cfg_bb_info (FILE *file
, basic_block bb
)
882 static const char * const bb_bitnames
[] =
884 "dirty", "new", "reachable", "visited", "irreducible_loop", "superblock"
886 const unsigned n_bitnames
= sizeof (bb_bitnames
) / sizeof (char *);
889 fprintf (file
, "Basic block %d", bb
->index
);
890 for (i
= 0; i
< n_bitnames
; i
++)
891 if (bb
->flags
& (1 << i
))
894 fprintf (file
, " (");
896 fprintf (file
, ", ");
898 fprintf (file
, bb_bitnames
[i
]);
902 fprintf (file
, "\n");
904 fprintf (file
, "Predecessors: ");
905 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
906 dump_edge_info (file
, e
, 0);
908 fprintf (file
, "\nSuccessors: ");
909 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
910 dump_edge_info (file
, e
, 1);
911 fprintf (file
, "\n\n");
914 /* Dumps a brief description of cfg to FILE. */
917 brief_dump_cfg (FILE *file
)
923 dump_cfg_bb_info (file
, bb
);
927 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
928 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
929 redirected to destination of TAKEN_EDGE.
931 This function may leave the profile inconsistent in the case TAKEN_EDGE
932 frequency or count is believed to be lower than FREQUENCY or COUNT
935 update_bb_profile_for_threading (basic_block bb
, int edge_frequency
,
936 gcov_type count
, edge taken_edge
)
946 fprintf (dump_file
, "bb %i count became negative after threading",
951 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
952 Watch for overflows. */
954 prob
= edge_frequency
* REG_BR_PROB_BASE
/ bb
->frequency
;
957 if (prob
> taken_edge
->probability
)
960 fprintf (dump_file
, "Jump threading proved probability of edge "
961 "%i->%i too small (it is %i, should be %i).\n",
962 taken_edge
->src
->index
, taken_edge
->dest
->index
,
963 taken_edge
->probability
, prob
);
964 prob
= taken_edge
->probability
;
967 /* Now rescale the probabilities. */
968 taken_edge
->probability
-= prob
;
969 prob
= REG_BR_PROB_BASE
- prob
;
970 bb
->frequency
-= edge_frequency
;
971 if (bb
->frequency
< 0)
976 fprintf (dump_file
, "Edge frequencies of bb %i has been reset, "
977 "frequency of block should end up being 0, it is %i\n",
978 bb
->index
, bb
->frequency
);
979 EDGE_SUCC (bb
, 0)->probability
= REG_BR_PROB_BASE
;
980 ei
= ei_start (bb
->succs
);
982 for (; (c
= ei_safe_edge (ei
)); ei_next (&ei
))
985 else if (prob
!= REG_BR_PROB_BASE
)
987 int scale
= RDIV (65536 * REG_BR_PROB_BASE
, prob
);
989 FOR_EACH_EDGE (c
, ei
, bb
->succs
)
991 c
->probability
= RDIV (c
->probability
* scale
, 65536);
992 if (c
->probability
> REG_BR_PROB_BASE
)
993 c
->probability
= REG_BR_PROB_BASE
;
997 gcc_assert (bb
== taken_edge
->src
);
998 taken_edge
->count
-= count
;
999 if (taken_edge
->count
< 0)
1002 fprintf (dump_file
, "edge %i->%i count became negative after threading",
1003 taken_edge
->src
->index
, taken_edge
->dest
->index
);
1004 taken_edge
->count
= 0;
1008 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1009 by NUM/DEN, in int arithmetic. May lose some accuracy. */
1011 scale_bbs_frequencies_int (basic_block
*bbs
, int nbbs
, int num
, int den
)
1018 /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
1019 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
1020 and still safely fit in int during calculations. */
1026 num
= RDIV (1000 * num
, den
);
1029 if (num
> 100 * den
)
1032 for (i
= 0; i
< nbbs
; i
++)
1035 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
1036 /* Make sure the frequencies do not grow over BB_FREQ_MAX. */
1037 if (bbs
[i
]->frequency
> BB_FREQ_MAX
)
1038 bbs
[i
]->frequency
= BB_FREQ_MAX
;
1039 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
1040 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1041 e
->count
= RDIV (e
->count
* num
, den
);
1045 /* numbers smaller than this value are safe to multiply without getting
1047 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
1049 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1050 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
1051 function but considerably slower. */
1053 scale_bbs_frequencies_gcov_type (basic_block
*bbs
, int nbbs
, gcov_type num
,
1058 gcov_type fraction
= RDIV (num
* 65536, den
);
1060 gcc_assert (fraction
>= 0);
1062 if (num
< MAX_SAFE_MULTIPLIER
)
1063 for (i
= 0; i
< nbbs
; i
++)
1066 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
1067 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
1068 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
1070 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
1071 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1072 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
1073 e
->count
= RDIV (e
->count
* num
, den
);
1075 e
->count
= RDIV (e
->count
* fraction
, 65536);
1078 for (i
= 0; i
< nbbs
; i
++)
1081 if (sizeof (gcov_type
) > sizeof (int))
1082 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
1084 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* fraction
, 65536);
1085 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
1086 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1087 e
->count
= RDIV (e
->count
* fraction
, 65536);
1091 /* Data structures used to maintain mapping between basic blocks and
1093 static htab_t bb_original
;
1094 static htab_t bb_copy
;
1096 /* And between loops and copies. */
1097 static htab_t loop_copy
;
1098 static alloc_pool original_copy_bb_pool
;
1100 struct htab_bb_copy_original_entry
1102 /* Block we are attaching info to. */
1104 /* Index of original or copy (depending on the hashtable) */
1109 bb_copy_original_hash (const void *p
)
1111 const struct htab_bb_copy_original_entry
*data
1112 = ((const struct htab_bb_copy_original_entry
*)p
);
1114 return data
->index1
;
1117 bb_copy_original_eq (const void *p
, const void *q
)
1119 const struct htab_bb_copy_original_entry
*data
1120 = ((const struct htab_bb_copy_original_entry
*)p
);
1121 const struct htab_bb_copy_original_entry
*data2
1122 = ((const struct htab_bb_copy_original_entry
*)q
);
1124 return data
->index1
== data2
->index1
;
1127 /* Initialize the data structures to maintain mapping between blocks
1130 initialize_original_copy_tables (void)
1132 gcc_assert (!original_copy_bb_pool
);
1133 original_copy_bb_pool
1134 = create_alloc_pool ("original_copy",
1135 sizeof (struct htab_bb_copy_original_entry
), 10);
1136 bb_original
= htab_create (10, bb_copy_original_hash
,
1137 bb_copy_original_eq
, NULL
);
1138 bb_copy
= htab_create (10, bb_copy_original_hash
, bb_copy_original_eq
, NULL
);
1139 loop_copy
= htab_create (10, bb_copy_original_hash
, bb_copy_original_eq
, NULL
);
1142 /* Free the data structures to maintain mapping between blocks and
1145 free_original_copy_tables (void)
1147 gcc_assert (original_copy_bb_pool
);
1148 htab_delete (bb_copy
);
1149 htab_delete (bb_original
);
1150 htab_delete (loop_copy
);
1151 free_alloc_pool (original_copy_bb_pool
);
1155 original_copy_bb_pool
= NULL
;
1158 /* Removes the value associated with OBJ from table TAB. */
1161 copy_original_table_clear (htab_t tab
, unsigned obj
)
1164 struct htab_bb_copy_original_entry key
, *elt
;
1166 if (!original_copy_bb_pool
)
1170 slot
= htab_find_slot (tab
, &key
, NO_INSERT
);
1174 elt
= (struct htab_bb_copy_original_entry
*) *slot
;
1175 htab_clear_slot (tab
, slot
);
1176 pool_free (original_copy_bb_pool
, elt
);
1179 /* Sets the value associated with OBJ in table TAB to VAL.
1180 Do nothing when data structures are not initialized. */
1183 copy_original_table_set (htab_t tab
, unsigned obj
, unsigned val
)
1185 struct htab_bb_copy_original_entry
**slot
;
1186 struct htab_bb_copy_original_entry key
;
1188 if (!original_copy_bb_pool
)
1192 slot
= (struct htab_bb_copy_original_entry
**)
1193 htab_find_slot (tab
, &key
, INSERT
);
1196 *slot
= (struct htab_bb_copy_original_entry
*)
1197 pool_alloc (original_copy_bb_pool
);
1198 (*slot
)->index1
= obj
;
1200 (*slot
)->index2
= val
;
1203 /* Set original for basic block. Do nothing when data structures are not
1204 initialized so passes not needing this don't need to care. */
1206 set_bb_original (basic_block bb
, basic_block original
)
1208 copy_original_table_set (bb_original
, bb
->index
, original
->index
);
1211 /* Get the original basic block. */
1213 get_bb_original (basic_block bb
)
1215 struct htab_bb_copy_original_entry
*entry
;
1216 struct htab_bb_copy_original_entry key
;
1218 gcc_assert (original_copy_bb_pool
);
1220 key
.index1
= bb
->index
;
1221 entry
= (struct htab_bb_copy_original_entry
*) htab_find (bb_original
, &key
);
1223 return BASIC_BLOCK (entry
->index2
);
1228 /* Set copy for basic block. Do nothing when data structures are not
1229 initialized so passes not needing this don't need to care. */
1231 set_bb_copy (basic_block bb
, basic_block copy
)
1233 copy_original_table_set (bb_copy
, bb
->index
, copy
->index
);
1236 /* Get the copy of basic block. */
1238 get_bb_copy (basic_block bb
)
1240 struct htab_bb_copy_original_entry
*entry
;
1241 struct htab_bb_copy_original_entry key
;
1243 gcc_assert (original_copy_bb_pool
);
1245 key
.index1
= bb
->index
;
1246 entry
= (struct htab_bb_copy_original_entry
*) htab_find (bb_copy
, &key
);
1248 return BASIC_BLOCK (entry
->index2
);
1253 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1254 initialized so passes not needing this don't need to care. */
1257 set_loop_copy (struct loop
*loop
, struct loop
*copy
)
1260 copy_original_table_clear (loop_copy
, loop
->num
);
1262 copy_original_table_set (loop_copy
, loop
->num
, copy
->num
);
1265 /* Get the copy of LOOP. */
1268 get_loop_copy (struct loop
*loop
)
1270 struct htab_bb_copy_original_entry
*entry
;
1271 struct htab_bb_copy_original_entry key
;
1273 gcc_assert (original_copy_bb_pool
);
1275 key
.index1
= loop
->num
;
1276 entry
= (struct htab_bb_copy_original_entry
*) htab_find (loop_copy
, &key
);
1278 return get_loop (entry
->index2
);