1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file contains low level functions to manipulate the CFG and
21 analyze it. All other modules should not transform the data structure
22 directly and use abstraction instead. The file is supposed to be
23 ordered bottom-up and should not contain any code dependent on a
24 particular intermediate language (RTL or trees).
26 Available functionality:
27 - Initialization/deallocation
28 init_flow, clear_edges
29 - Low level basic block manipulation
30 alloc_block, expunge_block
32 make_edge, make_single_succ_edge, cached_make_edge, remove_edge
33 - Low level edge redirection (without updating instruction chain)
34 redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
35 - Dumping and debugging
36 dump_flow_info, debug_flow_info, dump_edge_info
37 - Allocation of AUX fields for basic blocks
38 alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
40 - Consistency checking
42 - Dumping and debugging
43 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
45 TODO: Document these "Available functionality" functions in the files
51 #include "coretypes.h"
53 #include "hard-reg-set.h"
58 #include "cfgloop.h" /* FIXME: For struct loop. */
62 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
64 /* Called once at initialization time. */
67 init_flow (struct function
*the_fun
)
70 the_fun
->cfg
= ggc_cleared_alloc
<control_flow_graph
> ();
71 n_edges_for_fn (the_fun
) = 0;
72 ENTRY_BLOCK_PTR_FOR_FN (the_fun
)
73 = ggc_cleared_alloc
<basic_block_def
> ();
74 ENTRY_BLOCK_PTR_FOR_FN (the_fun
)->index
= ENTRY_BLOCK
;
75 EXIT_BLOCK_PTR_FOR_FN (the_fun
)
76 = ggc_cleared_alloc
<basic_block_def
> ();
77 EXIT_BLOCK_PTR_FOR_FN (the_fun
)->index
= EXIT_BLOCK
;
78 ENTRY_BLOCK_PTR_FOR_FN (the_fun
)->next_bb
79 = EXIT_BLOCK_PTR_FOR_FN (the_fun
);
80 EXIT_BLOCK_PTR_FOR_FN (the_fun
)->prev_bb
81 = ENTRY_BLOCK_PTR_FOR_FN (the_fun
);
84 /* Helper function for remove_edge and clear_edges. Frees edge structure
85 without actually removing it from the pred/succ arrays. */
88 free_edge (function
*fn
, edge e
)
90 n_edges_for_fn (fn
)--;
94 /* Free the memory associated with the edge structures. */
97 clear_edges (struct function
*fn
)
103 FOR_EACH_BB_FN (bb
, fn
)
105 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
107 vec_safe_truncate (bb
->succs
, 0);
108 vec_safe_truncate (bb
->preds
, 0);
111 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (fn
)->succs
)
113 vec_safe_truncate (EXIT_BLOCK_PTR_FOR_FN (fn
)->preds
, 0);
114 vec_safe_truncate (ENTRY_BLOCK_PTR_FOR_FN (fn
)->succs
, 0);
116 gcc_assert (!n_edges_for_fn (fn
));
119 /* Allocate memory for basic_block. */
125 bb
= ggc_cleared_alloc
<basic_block_def
> ();
129 /* Link block B to chain after AFTER. */
131 link_block (basic_block b
, basic_block after
)
133 b
->next_bb
= after
->next_bb
;
136 b
->next_bb
->prev_bb
= b
;
139 /* Unlink block B from chain. */
141 unlink_block (basic_block b
)
143 b
->next_bb
->prev_bb
= b
->prev_bb
;
144 b
->prev_bb
->next_bb
= b
->next_bb
;
149 /* Sequentially order blocks and compact the arrays. */
151 compact_blocks (void)
155 SET_BASIC_BLOCK_FOR_FN (cfun
, ENTRY_BLOCK
, ENTRY_BLOCK_PTR_FOR_FN (cfun
));
156 SET_BASIC_BLOCK_FOR_FN (cfun
, EXIT_BLOCK
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
159 df_compact_blocks ();
164 i
= NUM_FIXED_BLOCKS
;
165 FOR_EACH_BB_FN (bb
, cfun
)
167 SET_BASIC_BLOCK_FOR_FN (cfun
, i
, bb
);
171 gcc_assert (i
== n_basic_blocks_for_fn (cfun
));
173 for (; i
< last_basic_block_for_fn (cfun
); i
++)
174 SET_BASIC_BLOCK_FOR_FN (cfun
, i
, NULL
);
176 last_basic_block_for_fn (cfun
) = n_basic_blocks_for_fn (cfun
);
179 /* Remove block B from the basic block array. */
182 expunge_block (basic_block b
)
185 SET_BASIC_BLOCK_FOR_FN (cfun
, b
->index
, NULL
);
186 n_basic_blocks_for_fn (cfun
)--;
187 /* We should be able to ggc_free here, but we are not.
188 The dead SSA_NAMES are left pointing to dead statements that are pointing
189 to dead basic blocks making garbage collector to die.
190 We should be able to release all dead SSA_NAMES and at the same time we should
191 clear out BB pointer of dead statements consistently. */
194 /* Connect E to E->src. */
199 vec_safe_push (e
->src
->succs
, e
);
200 df_mark_solutions_dirty ();
203 /* Connect E to E->dest. */
206 connect_dest (edge e
)
208 basic_block dest
= e
->dest
;
209 vec_safe_push (dest
->preds
, e
);
210 e
->dest_idx
= EDGE_COUNT (dest
->preds
) - 1;
211 df_mark_solutions_dirty ();
214 /* Disconnect edge E from E->src. */
217 disconnect_src (edge e
)
219 basic_block src
= e
->src
;
223 for (ei
= ei_start (src
->succs
); (tmp
= ei_safe_edge (ei
)); )
227 src
->succs
->unordered_remove (ei
.index
);
228 df_mark_solutions_dirty ();
238 /* Disconnect edge E from E->dest. */
241 disconnect_dest (edge e
)
243 basic_block dest
= e
->dest
;
244 unsigned int dest_idx
= e
->dest_idx
;
246 dest
->preds
->unordered_remove (dest_idx
);
248 /* If we removed an edge in the middle of the edge vector, we need
249 to update dest_idx of the edge that moved into the "hole". */
250 if (dest_idx
< EDGE_COUNT (dest
->preds
))
251 EDGE_PRED (dest
, dest_idx
)->dest_idx
= dest_idx
;
252 df_mark_solutions_dirty ();
255 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
256 created edge. Use this only if you are sure that this edge can't
257 possibly already exist. */
260 unchecked_make_edge (basic_block src
, basic_block dst
, int flags
)
263 e
= ggc_cleared_alloc
<edge_def
> ();
264 n_edges_for_fn (cfun
)++;
273 execute_on_growing_pred (e
);
277 /* Create an edge connecting SRC and DST with FLAGS optionally using
278 edge cache CACHE. Return the new edge, NULL if already exist. */
281 cached_make_edge (sbitmap edge_cache
, basic_block src
, basic_block dst
, int flags
)
283 if (edge_cache
== NULL
284 || src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
285 || dst
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
286 return make_edge (src
, dst
, flags
);
288 /* Does the requested edge already exist? */
289 if (! bitmap_bit_p (edge_cache
, dst
->index
))
291 /* The edge does not exist. Create one and update the
293 bitmap_set_bit (edge_cache
, dst
->index
);
294 return unchecked_make_edge (src
, dst
, flags
);
297 /* At this point, we know that the requested edge exists. Adjust
298 flags if necessary. */
301 edge e
= find_edge (src
, dst
);
308 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
309 created edge or NULL if already exist. */
312 make_edge (basic_block src
, basic_block dest
, int flags
)
314 edge e
= find_edge (src
, dest
);
316 /* Make sure we don't add duplicate edges. */
323 return unchecked_make_edge (src
, dest
, flags
);
326 /* Create an edge connecting SRC to DEST and set probability by knowing
327 that it is the single edge leaving SRC. */
330 make_single_succ_edge (basic_block src
, basic_block dest
, int flags
)
332 edge e
= make_edge (src
, dest
, flags
);
334 e
->probability
= REG_BR_PROB_BASE
;
335 e
->count
= src
->count
;
339 /* This function will remove an edge from the flow graph. */
342 remove_edge_raw (edge e
)
344 remove_predictions_associated_with_edge (e
);
345 execute_on_shrinking_pred (e
);
353 /* Redirect an edge's successor from one block to another. */
356 redirect_edge_succ (edge e
, basic_block new_succ
)
358 execute_on_shrinking_pred (e
);
364 /* Reconnect the edge to the new successor block. */
367 execute_on_growing_pred (e
);
370 /* Redirect an edge's predecessor from one block to another. */
373 redirect_edge_pred (edge e
, basic_block new_pred
)
379 /* Reconnect the edge to the new predecessor block. */
383 /* Clear all basic block flags that do not have to be preserved. */
385 clear_bb_flags (void)
389 FOR_ALL_BB_FN (bb
, cfun
)
390 bb
->flags
&= BB_FLAGS_TO_PRESERVE
;
393 /* Check the consistency of profile information. We can't do that
394 in verify_flow_info, as the counts may get invalid for incompletely
395 solved graphs, later eliminating of conditionals or roundoff errors.
396 It is still practical to have them reported for debugging of simple
399 check_bb_profile (basic_block bb
, FILE * file
, int indent
)
405 struct function
*fun
= DECL_STRUCT_FUNCTION (current_function_decl
);
406 char *s_indent
= (char *) alloca ((size_t) indent
+ 1);
407 memset ((void *) s_indent
, ' ', (size_t) indent
);
408 s_indent
[indent
] = '\0';
410 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
413 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
416 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
418 if (!(e
->flags
& EDGE_EH
))
420 sum
+= e
->probability
;
422 /* Only report mismatches for non-EH control flow. If there are only EH
423 edges it means that the BB ends by noreturn call. Here the control
424 flow may just terminate. */
427 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
429 ";; %sInvalid sum of outgoing probabilities %.1f%%\n",
430 s_indent
, sum
* 100.0 / REG_BR_PROB_BASE
);
432 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
434 if (EDGE_COUNT (bb
->succs
)
435 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
437 ";; %sInvalid sum of outgoing counts %i, should be %i\n",
438 s_indent
, (int) lsum
, (int) bb
->count
);
441 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (fun
))
444 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
445 sum
+= EDGE_FREQUENCY (e
);
446 if (abs (sum
- bb
->frequency
) > 100)
448 ";; %sInvalid sum of incoming frequencies %i, should be %i\n",
449 s_indent
, sum
, bb
->frequency
);
451 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
453 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
454 fprintf (file
, ";; %sInvalid sum of incoming counts %i, should be %i\n",
455 s_indent
, (int) lsum
, (int) bb
->count
);
457 if (BB_PARTITION (bb
) == BB_COLD_PARTITION
)
459 /* Warn about inconsistencies in the partitioning that are
460 currently caused by profile insanities created via optimization. */
461 if (!probably_never_executed_bb_p (fun
, bb
))
462 fprintf (file
, ";; %sBlock in cold partition with hot count\n",
464 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
466 if (!probably_never_executed_edge_p (fun
, e
))
468 ";; %sBlock in cold partition with incoming hot edge\n",
475 dump_edge_info (FILE *file
, edge e
, dump_flags_t flags
, int do_succ
)
477 basic_block side
= (do_succ
? e
->dest
: e
->src
);
478 bool do_details
= false;
480 if ((flags
& TDF_DETAILS
) != 0
481 && (flags
& TDF_SLIM
) == 0)
484 if (side
->index
== ENTRY_BLOCK
)
485 fputs (" ENTRY", file
);
486 else if (side
->index
== EXIT_BLOCK
)
487 fputs (" EXIT", file
);
489 fprintf (file
, " %d", side
->index
);
491 if (e
->probability
&& do_details
)
492 fprintf (file
, " [%.1f%%] ", e
->probability
* 100.0 / REG_BR_PROB_BASE
);
494 if (e
->count
&& do_details
)
496 fputs (" count:", file
);
497 fprintf (file
, "%" PRId64
, e
->count
);
500 if (e
->flags
&& do_details
)
502 static const char * const bitnames
[] =
504 #define DEF_EDGE_FLAG(NAME,IDX) #NAME ,
505 #include "cfg-flags.def"
510 int i
, flags
= e
->flags
;
512 gcc_assert (e
->flags
<= EDGE_ALL_FLAGS
);
514 for (i
= 0; flags
; i
++)
515 if (flags
& (1 << i
))
521 fputs (bitnames
[i
], file
);
530 debug (edge_def
&ref
)
532 /* FIXME (crowl): Is this desireable? */
533 dump_edge_info (stderr
, &ref
, 0, false);
534 dump_edge_info (stderr
, &ref
, 0, true);
538 debug (edge_def
*ptr
)
543 fprintf (stderr
, "<nil>\n");
546 /* Simple routines to easily allocate AUX fields of basic blocks. */
548 static struct obstack block_aux_obstack
;
549 static void *first_block_aux_obj
= 0;
550 static struct obstack edge_aux_obstack
;
551 static void *first_edge_aux_obj
= 0;
553 /* Allocate a memory block of SIZE as BB->aux. The obstack must
554 be first initialized by alloc_aux_for_blocks. */
557 alloc_aux_for_block (basic_block bb
, int size
)
559 /* Verify that aux field is clear. */
560 gcc_assert (!bb
->aux
&& first_block_aux_obj
);
561 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
562 memset (bb
->aux
, 0, size
);
565 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
566 alloc_aux_for_block for each basic block. */
569 alloc_aux_for_blocks (int size
)
571 static int initialized
;
575 gcc_obstack_init (&block_aux_obstack
);
579 /* Check whether AUX data are still allocated. */
580 gcc_assert (!first_block_aux_obj
);
582 first_block_aux_obj
= obstack_alloc (&block_aux_obstack
, 0);
587 FOR_ALL_BB_FN (bb
, cfun
)
588 alloc_aux_for_block (bb
, size
);
592 /* Clear AUX pointers of all blocks. */
595 clear_aux_for_blocks (void)
599 FOR_ALL_BB_FN (bb
, cfun
)
603 /* Free data allocated in block_aux_obstack and clear AUX pointers
607 free_aux_for_blocks (void)
609 gcc_assert (first_block_aux_obj
);
610 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
611 first_block_aux_obj
= NULL
;
613 clear_aux_for_blocks ();
616 /* Allocate a memory edge of SIZE as E->aux. The obstack must
617 be first initialized by alloc_aux_for_edges. */
620 alloc_aux_for_edge (edge e
, int size
)
622 /* Verify that aux field is clear. */
623 gcc_assert (!e
->aux
&& first_edge_aux_obj
);
624 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
625 memset (e
->aux
, 0, size
);
628 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
629 alloc_aux_for_edge for each basic edge. */
632 alloc_aux_for_edges (int size
)
634 static int initialized
;
638 gcc_obstack_init (&edge_aux_obstack
);
642 /* Check whether AUX data are still allocated. */
643 gcc_assert (!first_edge_aux_obj
);
645 first_edge_aux_obj
= obstack_alloc (&edge_aux_obstack
, 0);
650 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
651 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
656 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
657 alloc_aux_for_edge (e
, size
);
662 /* Clear AUX pointers of all edges. */
665 clear_aux_for_edges (void)
670 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
671 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
674 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
679 /* Free data allocated in edge_aux_obstack and clear AUX pointers
683 free_aux_for_edges (void)
685 gcc_assert (first_edge_aux_obj
);
686 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
687 first_edge_aux_obj
= NULL
;
689 clear_aux_for_edges ();
693 debug_bb (basic_block bb
)
695 dump_bb (stderr
, bb
, 0, dump_flags
);
698 DEBUG_FUNCTION basic_block
701 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, n
);
706 /* Dumps cfg related information about basic block BB to OUTF.
707 If HEADER is true, dump things that appear before the instructions
708 contained in BB. If FOOTER is true, dump things that appear after.
709 Flags are the TDF_* masks as documented in dumpfile.h.
710 NB: With TDF_DETAILS, it is assumed that cfun is available, so
711 that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE. */
714 dump_bb_info (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
,
715 bool do_header
, bool do_footer
)
719 static const char * const bb_bitnames
[] =
721 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) #NAME ,
722 #include "cfg-flags.def"
724 #undef DEF_BASIC_BLOCK_FLAG
726 const unsigned n_bitnames
= sizeof (bb_bitnames
) / sizeof (char *);
728 char *s_indent
= (char *) alloca ((size_t) indent
+ 1);
729 memset ((void *) s_indent
, ' ', (size_t) indent
);
730 s_indent
[indent
] = '\0';
732 gcc_assert (bb
->flags
<= BB_ALL_FLAGS
);
739 fprintf (outf
, "%sbasic block %d, loop depth %d",
740 s_indent
, bb
->index
, bb_loop_depth (bb
));
741 if (flags
& TDF_DETAILS
)
743 struct function
*fun
= DECL_STRUCT_FUNCTION (current_function_decl
);
744 fprintf (outf
, ", count " "%" PRId64
,
745 (int64_t) bb
->count
);
746 fprintf (outf
, ", freq %i", bb
->frequency
);
747 if (maybe_hot_bb_p (fun
, bb
))
748 fputs (", maybe hot", outf
);
749 if (probably_never_executed_bb_p (fun
, bb
))
750 fputs (", probably never executed", outf
);
754 if (flags
& TDF_DETAILS
)
756 check_bb_profile (bb
, outf
, indent
);
758 fprintf (outf
, "%s prev block ", s_indent
);
760 fprintf (outf
, "%d", bb
->prev_bb
->index
);
762 fprintf (outf
, "(nil)");
763 fprintf (outf
, ", next block ");
765 fprintf (outf
, "%d", bb
->next_bb
->index
);
767 fprintf (outf
, "(nil)");
769 fputs (", flags:", outf
);
771 for (i
= 0; i
< n_bitnames
; i
++)
772 if (bb
->flags
& (1 << i
))
779 fputs (bb_bitnames
[i
], outf
);
787 fprintf (outf
, "%s pred: ", s_indent
);
789 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
794 fprintf (outf
, "%s ", s_indent
);
797 dump_edge_info (outf
, e
, flags
, 0);
807 fprintf (outf
, "%s succ: ", s_indent
);
809 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
814 fprintf (outf
, "%s ", s_indent
);
817 dump_edge_info (outf
, e
, flags
, 1);
825 /* Dumps a brief description of cfg to FILE. */
828 brief_dump_cfg (FILE *file
, dump_flags_t flags
)
832 FOR_EACH_BB_FN (bb
, cfun
)
834 dump_bb_info (file
, bb
, 0, flags
& TDF_DETAILS
, true, true);
838 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
839 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
840 redirected to destination of TAKEN_EDGE.
842 This function may leave the profile inconsistent in the case TAKEN_EDGE
843 frequency or count is believed to be lower than FREQUENCY or COUNT
846 update_bb_profile_for_threading (basic_block bb
, int edge_frequency
,
847 gcov_type count
, edge taken_edge
)
857 fprintf (dump_file
, "bb %i count became negative after threading",
862 bb
->frequency
-= edge_frequency
;
863 if (bb
->frequency
< 0)
866 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
867 Watch for overflows. */
869 prob
= GCOV_COMPUTE_SCALE (edge_frequency
, bb
->frequency
);
872 if (prob
> taken_edge
->probability
)
875 fprintf (dump_file
, "Jump threading proved probability of edge "
876 "%i->%i too small (it is %i, should be %i).\n",
877 taken_edge
->src
->index
, taken_edge
->dest
->index
,
878 taken_edge
->probability
, prob
);
879 prob
= taken_edge
->probability
* 6 / 8;
882 /* Now rescale the probabilities. */
883 taken_edge
->probability
-= prob
;
884 prob
= REG_BR_PROB_BASE
- prob
;
888 fprintf (dump_file
, "Edge frequencies of bb %i has been reset, "
889 "frequency of block should end up being 0, it is %i\n",
890 bb
->index
, bb
->frequency
);
891 EDGE_SUCC (bb
, 0)->probability
= REG_BR_PROB_BASE
;
892 ei
= ei_start (bb
->succs
);
894 for (; (c
= ei_safe_edge (ei
)); ei_next (&ei
))
897 else if (prob
!= REG_BR_PROB_BASE
)
899 int scale
= RDIV (65536 * REG_BR_PROB_BASE
, prob
);
901 FOR_EACH_EDGE (c
, ei
, bb
->succs
)
903 /* Protect from overflow due to additional scaling. */
904 if (c
->probability
> prob
)
905 c
->probability
= REG_BR_PROB_BASE
;
908 c
->probability
= RDIV (c
->probability
* scale
, 65536);
909 if (c
->probability
> REG_BR_PROB_BASE
)
910 c
->probability
= REG_BR_PROB_BASE
;
915 gcc_assert (bb
== taken_edge
->src
);
916 taken_edge
->count
-= count
;
917 if (taken_edge
->count
< 0)
920 fprintf (dump_file
, "edge %i->%i count became negative after threading",
921 taken_edge
->src
->index
, taken_edge
->dest
->index
);
922 taken_edge
->count
= 0;
926 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
927 by NUM/DEN, in int arithmetic. May lose some accuracy. */
929 scale_bbs_frequencies_int (basic_block
*bbs
, int nbbs
, int num
, int den
)
936 /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
937 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
938 and still safely fit in int during calculations. */
944 num
= RDIV (1000 * num
, den
);
950 for (i
= 0; i
< nbbs
; i
++)
953 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
954 /* Make sure the frequencies do not grow over BB_FREQ_MAX. */
955 if (bbs
[i
]->frequency
> BB_FREQ_MAX
)
956 bbs
[i
]->frequency
= BB_FREQ_MAX
;
957 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
958 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
959 e
->count
= RDIV (e
->count
* num
, den
);
963 /* numbers smaller than this value are safe to multiply without getting
965 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (int64_t) * 4 - 1))
967 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
968 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
969 function but considerably slower. */
971 scale_bbs_frequencies_gcov_type (basic_block
*bbs
, int nbbs
, gcov_type num
,
976 gcov_type fraction
= RDIV (num
* 65536, den
);
978 gcc_assert (fraction
>= 0);
980 if (num
< MAX_SAFE_MULTIPLIER
)
981 for (i
= 0; i
< nbbs
; i
++)
984 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
985 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
986 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
988 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
989 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
990 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
991 e
->count
= RDIV (e
->count
* num
, den
);
993 e
->count
= RDIV (e
->count
* fraction
, 65536);
996 for (i
= 0; i
< nbbs
; i
++)
999 if (sizeof (gcov_type
) > sizeof (int))
1000 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
1002 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* fraction
, 65536);
1003 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
1004 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1005 e
->count
= RDIV (e
->count
* fraction
, 65536);
1009 /* Helper types for hash tables. */
1011 struct htab_bb_copy_original_entry
1013 /* Block we are attaching info to. */
1015 /* Index of original or copy (depending on the hashtable) */
1019 struct bb_copy_hasher
: nofree_ptr_hash
<htab_bb_copy_original_entry
>
1021 static inline hashval_t
hash (const htab_bb_copy_original_entry
*);
1022 static inline bool equal (const htab_bb_copy_original_entry
*existing
,
1023 const htab_bb_copy_original_entry
* candidate
);
1027 bb_copy_hasher::hash (const htab_bb_copy_original_entry
*data
)
1029 return data
->index1
;
1033 bb_copy_hasher::equal (const htab_bb_copy_original_entry
*data
,
1034 const htab_bb_copy_original_entry
*data2
)
1036 return data
->index1
== data2
->index1
;
1039 /* Data structures used to maintain mapping between basic blocks and
1041 static hash_table
<bb_copy_hasher
> *bb_original
;
1042 static hash_table
<bb_copy_hasher
> *bb_copy
;
1044 /* And between loops and copies. */
1045 static hash_table
<bb_copy_hasher
> *loop_copy
;
1046 static object_allocator
<htab_bb_copy_original_entry
> *original_copy_bb_pool
;
1048 /* Initialize the data structures to maintain mapping between blocks
1051 initialize_original_copy_tables (void)
1053 original_copy_bb_pool
= new object_allocator
<htab_bb_copy_original_entry
>
1055 bb_original
= new hash_table
<bb_copy_hasher
> (10);
1056 bb_copy
= new hash_table
<bb_copy_hasher
> (10);
1057 loop_copy
= new hash_table
<bb_copy_hasher
> (10);
1060 /* Reset the data structures to maintain mapping between blocks and
1064 reset_original_copy_tables (void)
1066 gcc_assert (original_copy_bb_pool
);
1067 bb_original
->empty ();
1069 loop_copy
->empty ();
1072 /* Free the data structures to maintain mapping between blocks and
1075 free_original_copy_tables (void)
1077 gcc_assert (original_copy_bb_pool
);
1084 delete original_copy_bb_pool
;
1085 original_copy_bb_pool
= NULL
;
1088 /* Return true iff we have had a call to initialize_original_copy_tables
1089 without a corresponding call to free_original_copy_tables. */
1092 original_copy_tables_initialized_p (void)
1094 return original_copy_bb_pool
!= NULL
;
1097 /* Removes the value associated with OBJ from table TAB. */
1100 copy_original_table_clear (hash_table
<bb_copy_hasher
> *tab
, unsigned obj
)
1102 htab_bb_copy_original_entry
**slot
;
1103 struct htab_bb_copy_original_entry key
, *elt
;
1105 if (!original_copy_bb_pool
)
1109 slot
= tab
->find_slot (&key
, NO_INSERT
);
1114 tab
->clear_slot (slot
);
1115 original_copy_bb_pool
->remove (elt
);
1118 /* Sets the value associated with OBJ in table TAB to VAL.
1119 Do nothing when data structures are not initialized. */
1122 copy_original_table_set (hash_table
<bb_copy_hasher
> *tab
,
1123 unsigned obj
, unsigned val
)
1125 struct htab_bb_copy_original_entry
**slot
;
1126 struct htab_bb_copy_original_entry key
;
1128 if (!original_copy_bb_pool
)
1132 slot
= tab
->find_slot (&key
, INSERT
);
1135 *slot
= original_copy_bb_pool
->allocate ();
1136 (*slot
)->index1
= obj
;
1138 (*slot
)->index2
= val
;
1141 /* Set original for basic block. Do nothing when data structures are not
1142 initialized so passes not needing this don't need to care. */
1144 set_bb_original (basic_block bb
, basic_block original
)
1146 copy_original_table_set (bb_original
, bb
->index
, original
->index
);
1149 /* Get the original basic block. */
1151 get_bb_original (basic_block bb
)
1153 struct htab_bb_copy_original_entry
*entry
;
1154 struct htab_bb_copy_original_entry key
;
1156 gcc_assert (original_copy_bb_pool
);
1158 key
.index1
= bb
->index
;
1159 entry
= bb_original
->find (&key
);
1161 return BASIC_BLOCK_FOR_FN (cfun
, entry
->index2
);
1166 /* Set copy for basic block. Do nothing when data structures are not
1167 initialized so passes not needing this don't need to care. */
1169 set_bb_copy (basic_block bb
, basic_block copy
)
1171 copy_original_table_set (bb_copy
, bb
->index
, copy
->index
);
1174 /* Get the copy of basic block. */
1176 get_bb_copy (basic_block bb
)
1178 struct htab_bb_copy_original_entry
*entry
;
1179 struct htab_bb_copy_original_entry key
;
1181 gcc_assert (original_copy_bb_pool
);
1183 key
.index1
= bb
->index
;
1184 entry
= bb_copy
->find (&key
);
1186 return BASIC_BLOCK_FOR_FN (cfun
, entry
->index2
);
1191 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1192 initialized so passes not needing this don't need to care. */
1195 set_loop_copy (struct loop
*loop
, struct loop
*copy
)
1198 copy_original_table_clear (loop_copy
, loop
->num
);
1200 copy_original_table_set (loop_copy
, loop
->num
, copy
->num
);
1203 /* Get the copy of LOOP. */
1206 get_loop_copy (struct loop
*loop
)
1208 struct htab_bb_copy_original_entry
*entry
;
1209 struct htab_bb_copy_original_entry key
;
1211 gcc_assert (original_copy_bb_pool
);
1213 key
.index1
= loop
->num
;
1214 entry
= loop_copy
->find (&key
);
1216 return get_loop (cfun
, entry
->index2
);