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, 2008, 2009, 2010
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
47 TODO: Document these "Available functionality" functions in the files
53 #include "coretypes.h"
57 #include "alloc-pool.h"
58 #include "basic-block.h"
60 #include "cfgloop.h" /* FIXME: For struct loop. */
64 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
66 /* Called once at initialization time. */
69 init_flow (struct function
*the_fun
)
72 the_fun
->cfg
= ggc_alloc_cleared_control_flow_graph ();
73 n_edges_for_function (the_fun
) = 0;
74 ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun
)
75 = ggc_alloc_cleared_basic_block_def ();
76 ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun
)->index
= ENTRY_BLOCK
;
77 EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun
)
78 = ggc_alloc_cleared_basic_block_def ();
79 EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun
)->index
= EXIT_BLOCK
;
80 ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun
)->next_bb
81 = EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun
);
82 EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun
)->prev_bb
83 = ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun
);
86 /* Helper function for remove_edge and clear_edges. Frees edge structure
87 without actually removing it from the pred/succ arrays. */
96 /* Free the memory associated with the edge structures. */
107 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
109 VEC_truncate (edge
, bb
->succs
, 0);
110 VEC_truncate (edge
, bb
->preds
, 0);
113 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
115 VEC_truncate (edge
, EXIT_BLOCK_PTR
->preds
, 0);
116 VEC_truncate (edge
, ENTRY_BLOCK_PTR
->succs
, 0);
118 gcc_assert (!n_edges
);
121 /* Allocate memory for basic_block. */
127 bb
= ggc_alloc_cleared_basic_block_def ();
131 /* Link block B to chain after AFTER. */
133 link_block (basic_block b
, basic_block after
)
135 b
->next_bb
= after
->next_bb
;
138 b
->next_bb
->prev_bb
= b
;
141 /* Unlink block B from chain. */
143 unlink_block (basic_block b
)
145 b
->next_bb
->prev_bb
= b
->prev_bb
;
146 b
->prev_bb
->next_bb
= b
->next_bb
;
151 /* Sequentially order blocks and compact the arrays. */
153 compact_blocks (void)
157 SET_BASIC_BLOCK (ENTRY_BLOCK
, ENTRY_BLOCK_PTR
);
158 SET_BASIC_BLOCK (EXIT_BLOCK
, EXIT_BLOCK_PTR
);
161 df_compact_blocks ();
166 i
= NUM_FIXED_BLOCKS
;
169 SET_BASIC_BLOCK (i
, bb
);
173 gcc_assert (i
== n_basic_blocks
);
175 for (; i
< last_basic_block
; i
++)
176 SET_BASIC_BLOCK (i
, NULL
);
178 last_basic_block
= n_basic_blocks
;
181 /* Remove block B from the basic block array. */
184 expunge_block (basic_block b
)
187 SET_BASIC_BLOCK (b
->index
, NULL
);
189 /* We should be able to ggc_free here, but we are not.
190 The dead SSA_NAMES are left pointing to dead statements that are pointing
191 to dead basic blocks making garbage collector to die.
192 We should be able to release all dead SSA_NAMES and at the same time we should
193 clear out BB pointer of dead statements consistently. */
196 /* Connect E to E->src. */
201 VEC_safe_push (edge
, gc
, e
->src
->succs
, e
);
202 df_mark_solutions_dirty ();
205 /* Connect E to E->dest. */
208 connect_dest (edge e
)
210 basic_block dest
= e
->dest
;
211 VEC_safe_push (edge
, gc
, dest
->preds
, e
);
212 e
->dest_idx
= EDGE_COUNT (dest
->preds
) - 1;
213 df_mark_solutions_dirty ();
216 /* Disconnect edge E from E->src. */
219 disconnect_src (edge e
)
221 basic_block src
= e
->src
;
225 for (ei
= ei_start (src
->succs
); (tmp
= ei_safe_edge (ei
)); )
229 VEC_unordered_remove (edge
, src
->succs
, ei
.index
);
230 df_mark_solutions_dirty ();
240 /* Disconnect edge E from E->dest. */
243 disconnect_dest (edge e
)
245 basic_block dest
= e
->dest
;
246 unsigned int dest_idx
= e
->dest_idx
;
248 VEC_unordered_remove (edge
, dest
->preds
, dest_idx
);
250 /* If we removed an edge in the middle of the edge vector, we need
251 to update dest_idx of the edge that moved into the "hole". */
252 if (dest_idx
< EDGE_COUNT (dest
->preds
))
253 EDGE_PRED (dest
, dest_idx
)->dest_idx
= dest_idx
;
254 df_mark_solutions_dirty ();
257 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
258 created edge. Use this only if you are sure that this edge can't
259 possibly already exist. */
262 unchecked_make_edge (basic_block src
, basic_block dst
, int flags
)
265 e
= ggc_alloc_cleared_edge_def ();
275 execute_on_growing_pred (e
);
279 /* Create an edge connecting SRC and DST with FLAGS optionally using
280 edge cache CACHE. Return the new edge, NULL if already exist. */
283 cached_make_edge (sbitmap edge_cache
, basic_block src
, basic_block dst
, int flags
)
285 if (edge_cache
== NULL
286 || src
== ENTRY_BLOCK_PTR
287 || dst
== EXIT_BLOCK_PTR
)
288 return make_edge (src
, dst
, flags
);
290 /* Does the requested edge already exist? */
291 if (! TEST_BIT (edge_cache
, dst
->index
))
293 /* The edge does not exist. Create one and update the
295 SET_BIT (edge_cache
, dst
->index
);
296 return unchecked_make_edge (src
, dst
, flags
);
299 /* At this point, we know that the requested edge exists. Adjust
300 flags if necessary. */
303 edge e
= find_edge (src
, dst
);
310 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
311 created edge or NULL if already exist. */
314 make_edge (basic_block src
, basic_block dest
, int flags
)
316 edge e
= find_edge (src
, dest
);
318 /* Make sure we don't add duplicate edges. */
325 return unchecked_make_edge (src
, dest
, flags
);
328 /* Create an edge connecting SRC to DEST and set probability by knowing
329 that it is the single edge leaving SRC. */
332 make_single_succ_edge (basic_block src
, basic_block dest
, int flags
)
334 edge e
= make_edge (src
, dest
, flags
);
336 e
->probability
= REG_BR_PROB_BASE
;
337 e
->count
= src
->count
;
341 /* This function will remove an edge from the flow graph. */
344 remove_edge_raw (edge e
)
346 remove_predictions_associated_with_edge (e
);
347 execute_on_shrinking_pred (e
);
355 /* Redirect an edge's successor from one block to another. */
358 redirect_edge_succ (edge e
, basic_block new_succ
)
360 execute_on_shrinking_pred (e
);
366 /* Reconnect the edge to the new successor block. */
369 execute_on_growing_pred (e
);
372 /* Redirect an edge's predecessor from one block to another. */
375 redirect_edge_pred (edge e
, basic_block new_pred
)
381 /* Reconnect the edge to the new predecessor block. */
385 /* Clear all basic block flags, with the exception of partitioning and
388 clear_bb_flags (void)
392 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
393 bb
->flags
= (BB_PARTITION (bb
)
394 | (bb
->flags
& (BB_DISABLE_SCHEDULE
+ BB_RTL
+ BB_NON_LOCAL_GOTO_TARGET
)));
397 /* Check the consistency of profile information. We can't do that
398 in verify_flow_info, as the counts may get invalid for incompletely
399 solved graphs, later eliminating of conditionals or roundoff errors.
400 It is still practical to have them reported for debugging of simple
403 check_bb_profile (basic_block bb
, FILE * file
)
410 if (profile_status
== PROFILE_ABSENT
)
413 if (bb
!= EXIT_BLOCK_PTR
)
415 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
416 sum
+= e
->probability
;
417 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
418 fprintf (file
, "Invalid sum of outgoing probabilities %.1f%%\n",
419 sum
* 100.0 / REG_BR_PROB_BASE
);
421 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
423 if (EDGE_COUNT (bb
->succs
)
424 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
425 fprintf (file
, "Invalid sum of outgoing counts %i, should be %i\n",
426 (int) lsum
, (int) bb
->count
);
428 if (bb
!= ENTRY_BLOCK_PTR
)
431 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
432 sum
+= EDGE_FREQUENCY (e
);
433 if (abs (sum
- bb
->frequency
) > 100)
435 "Invalid sum of incoming frequencies %i, should be %i\n",
438 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
440 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
441 fprintf (file
, "Invalid sum of incoming counts %i, should be %i\n",
442 (int) lsum
, (int) bb
->count
);
447 dump_edge_info (FILE *file
, edge e
, int flags
, int do_succ
)
449 basic_block side
= (do_succ
? e
->dest
: e
->src
);
450 bool do_details
= false;
452 if ((flags
& TDF_DETAILS
) != 0
453 && (flags
& TDF_SLIM
) == 0)
456 /* ENTRY_BLOCK_PTR/EXIT_BLOCK_PTR depend on cfun.
457 Compare against ENTRY_BLOCK/EXIT_BLOCK to avoid that dependency. */
458 if (side
->index
== ENTRY_BLOCK
)
459 fputs (" ENTRY", file
);
460 else if (side
->index
== EXIT_BLOCK
)
461 fputs (" EXIT", file
);
463 fprintf (file
, " %d", side
->index
);
465 if (e
->probability
&& do_details
)
466 fprintf (file
, " [%.1f%%] ", e
->probability
* 100.0 / REG_BR_PROB_BASE
);
468 if (e
->count
&& do_details
)
470 fputs (" count:", file
);
471 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
474 if (e
->flags
&& do_details
)
476 static const char * const bitnames
[] =
478 #define DEF_EDGE_FLAG(NAME,IDX) #NAME ,
479 #include "cfg-flags.def"
484 int i
, flags
= e
->flags
;
486 gcc_assert (e
->flags
<= EDGE_ALL_FLAGS
);
488 for (i
= 0; flags
; i
++)
489 if (flags
& (1 << i
))
495 fputs (bitnames
[i
], file
);
503 /* Simple routines to easily allocate AUX fields of basic blocks. */
505 static struct obstack block_aux_obstack
;
506 static void *first_block_aux_obj
= 0;
507 static struct obstack edge_aux_obstack
;
508 static void *first_edge_aux_obj
= 0;
510 /* Allocate a memory block of SIZE as BB->aux. The obstack must
511 be first initialized by alloc_aux_for_blocks. */
514 alloc_aux_for_block (basic_block bb
, int size
)
516 /* Verify that aux field is clear. */
517 gcc_assert (!bb
->aux
&& first_block_aux_obj
);
518 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
519 memset (bb
->aux
, 0, size
);
522 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
523 alloc_aux_for_block for each basic block. */
526 alloc_aux_for_blocks (int size
)
528 static int initialized
;
532 gcc_obstack_init (&block_aux_obstack
);
536 /* Check whether AUX data are still allocated. */
537 gcc_assert (!first_block_aux_obj
);
539 first_block_aux_obj
= obstack_alloc (&block_aux_obstack
, 0);
545 alloc_aux_for_block (bb
, size
);
549 /* Clear AUX pointers of all blocks. */
552 clear_aux_for_blocks (void)
560 /* Free data allocated in block_aux_obstack and clear AUX pointers
564 free_aux_for_blocks (void)
566 gcc_assert (first_block_aux_obj
);
567 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
568 first_block_aux_obj
= NULL
;
570 clear_aux_for_blocks ();
573 /* Allocate a memory edge of SIZE as E->aux. The obstack must
574 be first initialized by alloc_aux_for_edges. */
577 alloc_aux_for_edge (edge e
, int size
)
579 /* Verify that aux field is clear. */
580 gcc_assert (!e
->aux
&& first_edge_aux_obj
);
581 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
582 memset (e
->aux
, 0, size
);
585 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
586 alloc_aux_for_edge for each basic edge. */
589 alloc_aux_for_edges (int size
)
591 static int initialized
;
595 gcc_obstack_init (&edge_aux_obstack
);
599 /* Check whether AUX data are still allocated. */
600 gcc_assert (!first_edge_aux_obj
);
602 first_edge_aux_obj
= obstack_alloc (&edge_aux_obstack
, 0);
607 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
612 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
613 alloc_aux_for_edge (e
, size
);
618 /* Clear AUX pointers of all edges. */
621 clear_aux_for_edges (void)
626 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
629 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
634 /* Free data allocated in edge_aux_obstack and clear AUX pointers
638 free_aux_for_edges (void)
640 gcc_assert (first_edge_aux_obj
);
641 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
642 first_edge_aux_obj
= NULL
;
644 clear_aux_for_edges ();
648 debug_bb (basic_block bb
)
650 dump_bb (stderr
, bb
, 0, dump_flags
| TDF_BLOCKS
);
653 DEBUG_FUNCTION basic_block
656 basic_block bb
= BASIC_BLOCK (n
);
661 /* Dumps cfg related information about basic block BB to OUTF.
662 If HEADER is true, dump things that appear before the instructions
663 contained in BB. If FOOTER is true, dump things that appear after.
664 Flags are the TDF_* masks as documented in dumpfile.h.
665 NB: With TDF_DETAILS, it is assumed that cfun is available, so
666 that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE. */
669 dump_bb_info (FILE *outf
, basic_block bb
, int indent
, int flags
,
670 bool do_header
, bool do_footer
)
674 static const char * const bb_bitnames
[] =
676 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) #NAME ,
677 #include "cfg-flags.def"
679 #undef DEF_BASIC_BLOCK_FLAG
681 const unsigned n_bitnames
= sizeof (bb_bitnames
) / sizeof (char *);
682 char *s_indent
= (char *) alloca ((size_t) indent
+ 1);
683 memset ((void *) s_indent
, ' ', (size_t) indent
);
684 s_indent
[indent
] = '\0';
686 gcc_assert (bb
->flags
<= BB_ALL_FLAGS
);
692 if (flags
& TDF_COMMENT
)
694 fprintf (outf
, "%sbasic block %d", s_indent
, bb
->index
);
695 if (flags
& TDF_DETAILS
)
697 fprintf (outf
, ", loop depth %d, count " HOST_WIDEST_INT_PRINT_DEC
,
698 bb
->loop_depth
, (HOST_WIDEST_INT
) bb
->count
);
699 fprintf (outf
, ", freq %i", bb
->frequency
);
700 if (maybe_hot_bb_p (bb
))
701 fputs (", maybe hot", outf
);
702 if (probably_never_executed_bb_p (bb
))
703 fputs (", probably never executed", outf
);
707 if (flags
& TDF_DETAILS
)
711 if (flags
& TDF_COMMENT
)
713 fprintf (outf
, "%s prev block ", s_indent
);
715 fprintf (outf
, "%d", bb
->prev_bb
->index
);
717 fprintf (outf
, "(nil)");
718 fprintf (outf
, ", next block ");
720 fprintf (outf
, "%d", bb
->next_bb
->index
);
722 fprintf (outf
, "(nil)");
724 fputs (", flags:", outf
);
725 for (i
= 0; i
< n_bitnames
; i
++)
726 if (bb
->flags
& (1 << i
))
733 fputs (bb_bitnames
[i
], outf
);
740 if (flags
& TDF_COMMENT
)
742 fprintf (outf
, "%s pred: ", s_indent
);
743 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
744 dump_edge_info (outf
, e
, flags
, 0);
751 if (flags
& TDF_COMMENT
)
753 fprintf (outf
, "%s succ: ", s_indent
);
754 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
755 dump_edge_info (outf
, e
, flags
, 1);
756 fputs ("\n\n", outf
);
760 /* Dumps a brief description of cfg to FILE. */
763 brief_dump_cfg (FILE *file
)
769 dump_bb_info (file
, bb
, 0, 0, true, true);
773 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
774 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
775 redirected to destination of TAKEN_EDGE.
777 This function may leave the profile inconsistent in the case TAKEN_EDGE
778 frequency or count is believed to be lower than FREQUENCY or COUNT
781 update_bb_profile_for_threading (basic_block bb
, int edge_frequency
,
782 gcov_type count
, edge taken_edge
)
792 fprintf (dump_file
, "bb %i count became negative after threading",
797 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
798 Watch for overflows. */
800 prob
= edge_frequency
* REG_BR_PROB_BASE
/ bb
->frequency
;
803 if (prob
> taken_edge
->probability
)
806 fprintf (dump_file
, "Jump threading proved probability of edge "
807 "%i->%i too small (it is %i, should be %i).\n",
808 taken_edge
->src
->index
, taken_edge
->dest
->index
,
809 taken_edge
->probability
, prob
);
810 prob
= taken_edge
->probability
;
813 /* Now rescale the probabilities. */
814 taken_edge
->probability
-= prob
;
815 prob
= REG_BR_PROB_BASE
- prob
;
816 bb
->frequency
-= edge_frequency
;
817 if (bb
->frequency
< 0)
822 fprintf (dump_file
, "Edge frequencies of bb %i has been reset, "
823 "frequency of block should end up being 0, it is %i\n",
824 bb
->index
, bb
->frequency
);
825 EDGE_SUCC (bb
, 0)->probability
= REG_BR_PROB_BASE
;
826 ei
= ei_start (bb
->succs
);
828 for (; (c
= ei_safe_edge (ei
)); ei_next (&ei
))
831 else if (prob
!= REG_BR_PROB_BASE
)
833 int scale
= RDIV (65536 * REG_BR_PROB_BASE
, prob
);
835 FOR_EACH_EDGE (c
, ei
, bb
->succs
)
837 /* Protect from overflow due to additional scaling. */
838 if (c
->probability
> prob
)
839 c
->probability
= REG_BR_PROB_BASE
;
842 c
->probability
= RDIV (c
->probability
* scale
, 65536);
843 if (c
->probability
> REG_BR_PROB_BASE
)
844 c
->probability
= REG_BR_PROB_BASE
;
849 gcc_assert (bb
== taken_edge
->src
);
850 taken_edge
->count
-= count
;
851 if (taken_edge
->count
< 0)
854 fprintf (dump_file
, "edge %i->%i count became negative after threading",
855 taken_edge
->src
->index
, taken_edge
->dest
->index
);
856 taken_edge
->count
= 0;
860 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
861 by NUM/DEN, in int arithmetic. May lose some accuracy. */
863 scale_bbs_frequencies_int (basic_block
*bbs
, int nbbs
, int num
, int den
)
870 /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
871 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
872 and still safely fit in int during calculations. */
878 num
= RDIV (1000 * num
, den
);
884 for (i
= 0; i
< nbbs
; i
++)
887 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
888 /* Make sure the frequencies do not grow over BB_FREQ_MAX. */
889 if (bbs
[i
]->frequency
> BB_FREQ_MAX
)
890 bbs
[i
]->frequency
= BB_FREQ_MAX
;
891 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
892 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
893 e
->count
= RDIV (e
->count
* num
, den
);
897 /* numbers smaller than this value are safe to multiply without getting
899 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
901 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
902 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
903 function but considerably slower. */
905 scale_bbs_frequencies_gcov_type (basic_block
*bbs
, int nbbs
, gcov_type num
,
910 gcov_type fraction
= RDIV (num
* 65536, den
);
912 gcc_assert (fraction
>= 0);
914 if (num
< MAX_SAFE_MULTIPLIER
)
915 for (i
= 0; i
< nbbs
; i
++)
918 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
919 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
920 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
922 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
923 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
924 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
925 e
->count
= RDIV (e
->count
* num
, den
);
927 e
->count
= RDIV (e
->count
* fraction
, 65536);
930 for (i
= 0; i
< nbbs
; i
++)
933 if (sizeof (gcov_type
) > sizeof (int))
934 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
936 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* fraction
, 65536);
937 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
938 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
939 e
->count
= RDIV (e
->count
* fraction
, 65536);
943 /* Data structures used to maintain mapping between basic blocks and
945 static htab_t bb_original
;
946 static htab_t bb_copy
;
948 /* And between loops and copies. */
949 static htab_t loop_copy
;
950 static alloc_pool original_copy_bb_pool
;
952 struct htab_bb_copy_original_entry
954 /* Block we are attaching info to. */
956 /* Index of original or copy (depending on the hashtable) */
961 bb_copy_original_hash (const void *p
)
963 const struct htab_bb_copy_original_entry
*data
964 = ((const struct htab_bb_copy_original_entry
*)p
);
969 bb_copy_original_eq (const void *p
, const void *q
)
971 const struct htab_bb_copy_original_entry
*data
972 = ((const struct htab_bb_copy_original_entry
*)p
);
973 const struct htab_bb_copy_original_entry
*data2
974 = ((const struct htab_bb_copy_original_entry
*)q
);
976 return data
->index1
== data2
->index1
;
979 /* Initialize the data structures to maintain mapping between blocks
982 initialize_original_copy_tables (void)
984 gcc_assert (!original_copy_bb_pool
);
985 original_copy_bb_pool
986 = create_alloc_pool ("original_copy",
987 sizeof (struct htab_bb_copy_original_entry
), 10);
988 bb_original
= htab_create (10, bb_copy_original_hash
,
989 bb_copy_original_eq
, NULL
);
990 bb_copy
= htab_create (10, bb_copy_original_hash
, bb_copy_original_eq
, NULL
);
991 loop_copy
= htab_create (10, bb_copy_original_hash
, bb_copy_original_eq
, NULL
);
994 /* Free the data structures to maintain mapping between blocks and
997 free_original_copy_tables (void)
999 gcc_assert (original_copy_bb_pool
);
1000 htab_delete (bb_copy
);
1001 htab_delete (bb_original
);
1002 htab_delete (loop_copy
);
1003 free_alloc_pool (original_copy_bb_pool
);
1007 original_copy_bb_pool
= NULL
;
1010 /* Removes the value associated with OBJ from table TAB. */
1013 copy_original_table_clear (htab_t tab
, unsigned obj
)
1016 struct htab_bb_copy_original_entry key
, *elt
;
1018 if (!original_copy_bb_pool
)
1022 slot
= htab_find_slot (tab
, &key
, NO_INSERT
);
1026 elt
= (struct htab_bb_copy_original_entry
*) *slot
;
1027 htab_clear_slot (tab
, slot
);
1028 pool_free (original_copy_bb_pool
, elt
);
1031 /* Sets the value associated with OBJ in table TAB to VAL.
1032 Do nothing when data structures are not initialized. */
1035 copy_original_table_set (htab_t tab
, unsigned obj
, unsigned val
)
1037 struct htab_bb_copy_original_entry
**slot
;
1038 struct htab_bb_copy_original_entry key
;
1040 if (!original_copy_bb_pool
)
1044 slot
= (struct htab_bb_copy_original_entry
**)
1045 htab_find_slot (tab
, &key
, INSERT
);
1048 *slot
= (struct htab_bb_copy_original_entry
*)
1049 pool_alloc (original_copy_bb_pool
);
1050 (*slot
)->index1
= obj
;
1052 (*slot
)->index2
= val
;
1055 /* Set original for basic block. Do nothing when data structures are not
1056 initialized so passes not needing this don't need to care. */
1058 set_bb_original (basic_block bb
, basic_block original
)
1060 copy_original_table_set (bb_original
, bb
->index
, original
->index
);
1063 /* Get the original basic block. */
1065 get_bb_original (basic_block bb
)
1067 struct htab_bb_copy_original_entry
*entry
;
1068 struct htab_bb_copy_original_entry key
;
1070 gcc_assert (original_copy_bb_pool
);
1072 key
.index1
= bb
->index
;
1073 entry
= (struct htab_bb_copy_original_entry
*) htab_find (bb_original
, &key
);
1075 return BASIC_BLOCK (entry
->index2
);
1080 /* Set copy for basic block. Do nothing when data structures are not
1081 initialized so passes not needing this don't need to care. */
1083 set_bb_copy (basic_block bb
, basic_block copy
)
1085 copy_original_table_set (bb_copy
, bb
->index
, copy
->index
);
1088 /* Get the copy of basic block. */
1090 get_bb_copy (basic_block bb
)
1092 struct htab_bb_copy_original_entry
*entry
;
1093 struct htab_bb_copy_original_entry key
;
1095 gcc_assert (original_copy_bb_pool
);
1097 key
.index1
= bb
->index
;
1098 entry
= (struct htab_bb_copy_original_entry
*) htab_find (bb_copy
, &key
);
1100 return BASIC_BLOCK (entry
->index2
);
1105 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1106 initialized so passes not needing this don't need to care. */
1109 set_loop_copy (struct loop
*loop
, struct loop
*copy
)
1112 copy_original_table_clear (loop_copy
, loop
->num
);
1114 copy_original_table_set (loop_copy
, loop
->num
, copy
->num
);
1117 /* Get the copy of LOOP. */
1120 get_loop_copy (struct loop
*loop
)
1122 struct htab_bb_copy_original_entry
*entry
;
1123 struct htab_bb_copy_original_entry key
;
1125 gcc_assert (original_copy_bb_pool
);
1127 key
.index1
= loop
->num
;
1128 entry
= (struct htab_bb_copy_original_entry
*) htab_find (loop_copy
, &key
);
1130 return get_loop (entry
->index2
);