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. */
63 /* Called once at initialization time. */
66 init_flow (struct function
*the_fun
)
69 the_fun
->cfg
= ggc_cleared_alloc
<control_flow_graph
> ();
70 n_edges_for_fn (the_fun
) = 0;
71 ENTRY_BLOCK_PTR_FOR_FN (the_fun
)
73 ENTRY_BLOCK_PTR_FOR_FN (the_fun
)->index
= ENTRY_BLOCK
;
74 EXIT_BLOCK_PTR_FOR_FN (the_fun
)
76 EXIT_BLOCK_PTR_FOR_FN (the_fun
)->index
= EXIT_BLOCK
;
77 ENTRY_BLOCK_PTR_FOR_FN (the_fun
)->next_bb
78 = EXIT_BLOCK_PTR_FOR_FN (the_fun
);
79 EXIT_BLOCK_PTR_FOR_FN (the_fun
)->prev_bb
80 = ENTRY_BLOCK_PTR_FOR_FN (the_fun
);
83 /* Helper function for remove_edge and clear_edges. Frees edge structure
84 without actually removing it from the pred/succ arrays. */
87 free_edge (function
*fn
, edge e
)
89 n_edges_for_fn (fn
)--;
93 /* Free the memory associated with the edge structures. */
96 clear_edges (struct function
*fn
)
102 FOR_EACH_BB_FN (bb
, fn
)
104 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
106 vec_safe_truncate (bb
->succs
, 0);
107 vec_safe_truncate (bb
->preds
, 0);
110 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (fn
)->succs
)
112 vec_safe_truncate (EXIT_BLOCK_PTR_FOR_FN (fn
)->preds
, 0);
113 vec_safe_truncate (ENTRY_BLOCK_PTR_FOR_FN (fn
)->succs
, 0);
115 gcc_assert (!n_edges_for_fn (fn
));
118 /* Allocate memory for basic_block. */
124 bb
= ggc_cleared_alloc
<basic_block_def
> ();
125 bb
->count
= profile_count::uninitialized ();
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
)++;
266 e
->probability
= profile_probability::uninitialized ();
274 execute_on_growing_pred (e
);
278 /* Create an edge connecting SRC and DST with FLAGS optionally using
279 edge cache CACHE. Return the new edge, NULL if already exist. */
282 cached_make_edge (sbitmap edge_cache
, basic_block src
, basic_block dst
, int flags
)
284 if (edge_cache
== NULL
285 || src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
286 || dst
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
287 return make_edge (src
, dst
, flags
);
289 /* Does the requested edge already exist? */
290 if (! bitmap_bit_p (edge_cache
, dst
->index
))
292 /* The edge does not exist. Create one and update the
294 bitmap_set_bit (edge_cache
, dst
->index
);
295 return unchecked_make_edge (src
, dst
, flags
);
298 /* At this point, we know that the requested edge exists. Adjust
299 flags if necessary. */
302 edge e
= find_edge (src
, dst
);
309 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
310 created edge or NULL if already exist. */
313 make_edge (basic_block src
, basic_block dest
, int flags
)
315 edge e
= find_edge (src
, dest
);
317 /* Make sure we don't add duplicate edges. */
324 return unchecked_make_edge (src
, dest
, flags
);
327 /* Create an edge connecting SRC to DEST and set probability by knowing
328 that it is the single edge leaving SRC. */
331 make_single_succ_edge (basic_block src
, basic_block dest
, int flags
)
333 edge e
= make_edge (src
, dest
, flags
);
335 e
->probability
= profile_probability::always ();
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
)
403 struct function
*fun
= DECL_STRUCT_FUNCTION (current_function_decl
);
404 char *s_indent
= (char *) alloca ((size_t) indent
+ 1);
405 memset ((void *) s_indent
, ' ', (size_t) indent
);
406 s_indent
[indent
] = '\0';
408 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
411 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
414 profile_probability sum
= profile_probability::never ();
417 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
419 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
421 sum
+= e
->probability
;
422 if (e
->probability
.initialized_p ())
423 isum
+= e
->probability
.to_reg_br_prob_base ();
425 /* Only report mismatches for non-EH control flow. If there are only EH
426 edges it means that the BB ends by noreturn call. Here the control
427 flow may just terminate. */
430 if (sum
.differs_from_p (profile_probability::always ()))
433 ";; %sInvalid sum of outgoing probabilities ",
436 fprintf (file
, "\n");
438 /* Probabilities caps to 100% and thus the previous test will never
439 fire if the sum of probabilities is too large. */
440 else if (isum
> REG_BR_PROB_BASE
+ 100)
443 ";; %sInvalid sum of outgoing probabilities %.1f%%\n",
444 s_indent
, isum
* 100.0 / REG_BR_PROB_BASE
);
448 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (fun
))
451 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
452 sum
+= EDGE_FREQUENCY (e
);
453 if (abs (sum
- bb
->frequency
) > 100)
455 ";; %sInvalid sum of incoming frequencies %i, should be %i\n",
456 s_indent
, sum
, bb
->frequency
);
458 if (BB_PARTITION (bb
) == BB_COLD_PARTITION
)
460 /* Warn about inconsistencies in the partitioning that are
461 currently caused by profile insanities created via optimization. */
462 if (!probably_never_executed_bb_p (fun
, bb
))
463 fprintf (file
, ";; %sBlock in cold partition with hot count\n",
465 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
467 if (!probably_never_executed_edge_p (fun
, e
))
469 ";; %sBlock in cold partition with incoming hot edge\n",
476 dump_edge_info (FILE *file
, edge e
, dump_flags_t flags
, int do_succ
)
478 basic_block side
= (do_succ
? e
->dest
: e
->src
);
479 bool do_details
= false;
481 if ((flags
& TDF_DETAILS
) != 0
482 && (flags
& TDF_SLIM
) == 0)
485 if (side
->index
== ENTRY_BLOCK
)
486 fputs (" ENTRY", file
);
487 else if (side
->index
== EXIT_BLOCK
)
488 fputs (" EXIT", file
);
490 fprintf (file
, " %d", side
->index
);
492 if (e
->probability
.initialized_p () && do_details
)
494 fprintf (file
, " [");
495 e
->probability
.dump (file
);
496 fprintf (file
, "] ");
499 if (e
->count ().initialized_p () && do_details
)
501 fputs (" count:", file
);
502 e
->count ().dump (file
);
505 if (e
->flags
&& do_details
)
507 static const char * const bitnames
[] =
509 #define DEF_EDGE_FLAG(NAME,IDX) #NAME ,
510 #include "cfg-flags.def"
515 int i
, flags
= e
->flags
;
517 gcc_assert (e
->flags
<= EDGE_ALL_FLAGS
);
519 for (i
= 0; flags
; i
++)
520 if (flags
& (1 << i
))
526 fputs (bitnames
[i
], file
);
535 debug (edge_def
&ref
)
537 /* FIXME (crowl): Is this desireable? */
538 dump_edge_info (stderr
, &ref
, 0, false);
539 dump_edge_info (stderr
, &ref
, 0, true);
543 debug (edge_def
*ptr
)
548 fprintf (stderr
, "<nil>\n");
551 /* Simple routines to easily allocate AUX fields of basic blocks. */
553 static struct obstack block_aux_obstack
;
554 static void *first_block_aux_obj
= 0;
555 static struct obstack edge_aux_obstack
;
556 static void *first_edge_aux_obj
= 0;
558 /* Allocate a memory block of SIZE as BB->aux. The obstack must
559 be first initialized by alloc_aux_for_blocks. */
562 alloc_aux_for_block (basic_block bb
, int size
)
564 /* Verify that aux field is clear. */
565 gcc_assert (!bb
->aux
&& first_block_aux_obj
);
566 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
567 memset (bb
->aux
, 0, size
);
570 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
571 alloc_aux_for_block for each basic block. */
574 alloc_aux_for_blocks (int size
)
576 static int initialized
;
580 gcc_obstack_init (&block_aux_obstack
);
584 /* Check whether AUX data are still allocated. */
585 gcc_assert (!first_block_aux_obj
);
587 first_block_aux_obj
= obstack_alloc (&block_aux_obstack
, 0);
592 FOR_ALL_BB_FN (bb
, cfun
)
593 alloc_aux_for_block (bb
, size
);
597 /* Clear AUX pointers of all blocks. */
600 clear_aux_for_blocks (void)
604 FOR_ALL_BB_FN (bb
, cfun
)
608 /* Free data allocated in block_aux_obstack and clear AUX pointers
612 free_aux_for_blocks (void)
614 gcc_assert (first_block_aux_obj
);
615 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
616 first_block_aux_obj
= NULL
;
618 clear_aux_for_blocks ();
621 /* Allocate a memory edge of SIZE as E->aux. The obstack must
622 be first initialized by alloc_aux_for_edges. */
625 alloc_aux_for_edge (edge e
, int size
)
627 /* Verify that aux field is clear. */
628 gcc_assert (!e
->aux
&& first_edge_aux_obj
);
629 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
630 memset (e
->aux
, 0, size
);
633 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
634 alloc_aux_for_edge for each basic edge. */
637 alloc_aux_for_edges (int size
)
639 static int initialized
;
643 gcc_obstack_init (&edge_aux_obstack
);
647 /* Check whether AUX data are still allocated. */
648 gcc_assert (!first_edge_aux_obj
);
650 first_edge_aux_obj
= obstack_alloc (&edge_aux_obstack
, 0);
655 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
656 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
661 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
662 alloc_aux_for_edge (e
, size
);
667 /* Clear AUX pointers of all edges. */
670 clear_aux_for_edges (void)
675 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
676 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
679 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
684 /* Free data allocated in edge_aux_obstack and clear AUX pointers
688 free_aux_for_edges (void)
690 gcc_assert (first_edge_aux_obj
);
691 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
692 first_edge_aux_obj
= NULL
;
694 clear_aux_for_edges ();
698 debug_bb (basic_block bb
)
700 dump_bb (stderr
, bb
, 0, dump_flags
);
703 DEBUG_FUNCTION basic_block
706 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, n
);
711 /* Dumps cfg related information about basic block BB to OUTF.
712 If HEADER is true, dump things that appear before the instructions
713 contained in BB. If FOOTER is true, dump things that appear after.
714 Flags are the TDF_* masks as documented in dumpfile.h.
715 NB: With TDF_DETAILS, it is assumed that cfun is available, so
716 that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE. */
719 dump_bb_info (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
,
720 bool do_header
, bool do_footer
)
724 static const char * const bb_bitnames
[] =
726 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) #NAME ,
727 #include "cfg-flags.def"
729 #undef DEF_BASIC_BLOCK_FLAG
731 const unsigned n_bitnames
= sizeof (bb_bitnames
) / sizeof (char *);
733 char *s_indent
= (char *) alloca ((size_t) indent
+ 1);
734 memset ((void *) s_indent
, ' ', (size_t) indent
);
735 s_indent
[indent
] = '\0';
737 gcc_assert (bb
->flags
<= BB_ALL_FLAGS
);
744 fprintf (outf
, "%sbasic block %d, loop depth %d",
745 s_indent
, bb
->index
, bb_loop_depth (bb
));
746 if (flags
& TDF_DETAILS
)
748 struct function
*fun
= DECL_STRUCT_FUNCTION (current_function_decl
);
749 if (bb
->count
.initialized_p ())
751 fputs (", count ", outf
);
752 bb
->count
.dump (outf
);
754 fprintf (outf
, ", freq %i", bb
->frequency
);
755 if (maybe_hot_bb_p (fun
, bb
))
756 fputs (", maybe hot", outf
);
757 if (probably_never_executed_bb_p (fun
, bb
))
758 fputs (", probably never executed", outf
);
762 if (flags
& TDF_DETAILS
)
764 check_bb_profile (bb
, outf
, indent
);
766 fprintf (outf
, "%s prev block ", s_indent
);
768 fprintf (outf
, "%d", bb
->prev_bb
->index
);
770 fprintf (outf
, "(nil)");
771 fprintf (outf
, ", next block ");
773 fprintf (outf
, "%d", bb
->next_bb
->index
);
775 fprintf (outf
, "(nil)");
777 fputs (", flags:", outf
);
779 for (i
= 0; i
< n_bitnames
; i
++)
780 if (bb
->flags
& (1 << i
))
787 fputs (bb_bitnames
[i
], outf
);
795 fprintf (outf
, "%s pred: ", s_indent
);
797 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
802 fprintf (outf
, "%s ", s_indent
);
805 dump_edge_info (outf
, e
, flags
, 0);
815 fprintf (outf
, "%s succ: ", s_indent
);
817 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
822 fprintf (outf
, "%s ", s_indent
);
825 dump_edge_info (outf
, e
, flags
, 1);
833 /* Dumps a brief description of cfg to FILE. */
836 brief_dump_cfg (FILE *file
, dump_flags_t flags
)
840 FOR_EACH_BB_FN (bb
, cfun
)
842 dump_bb_info (file
, bb
, 0, flags
& TDF_DETAILS
, true, true);
846 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
847 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
848 redirected to destination of TAKEN_EDGE.
850 This function may leave the profile inconsistent in the case TAKEN_EDGE
851 frequency or count is believed to be lower than FREQUENCY or COUNT
854 update_bb_profile_for_threading (basic_block bb
, int edge_frequency
,
855 profile_count count
, edge taken_edge
)
858 profile_probability prob
;
861 if (bb
->count
< count
)
864 fprintf (dump_file
, "bb %i count became negative after threading",
869 bb
->frequency
-= edge_frequency
;
870 if (bb
->frequency
< 0)
873 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
874 Watch for overflows. */
876 /* FIXME: We should get edge frequency as count. */
877 prob
= profile_probability::probability_in_gcov_type
878 (edge_frequency
, bb
->frequency
);
880 prob
= profile_probability::never ();
881 if (prob
> taken_edge
->probability
)
885 fprintf (dump_file
, "Jump threading proved probability of edge "
886 "%i->%i too small (it is ",
887 taken_edge
->src
->index
, taken_edge
->dest
->index
);
888 taken_edge
->probability
.dump (dump_file
);
889 fprintf (dump_file
, " should be ");
890 prob
.dump (dump_file
);
891 fprintf (dump_file
, ")\n");
893 prob
= taken_edge
->probability
.apply_scale (6, 8);
896 /* Now rescale the probabilities. */
897 taken_edge
->probability
-= prob
;
898 prob
= prob
.invert ();
899 if (prob
== profile_probability::never ())
902 fprintf (dump_file
, "Edge frequencies of bb %i has been reset, "
903 "frequency of block should end up being 0, it is %i\n",
904 bb
->index
, bb
->frequency
);
905 EDGE_SUCC (bb
, 0)->probability
= profile_probability::guessed_always ();
906 ei
= ei_start (bb
->succs
);
908 for (; (c
= ei_safe_edge (ei
)); ei_next (&ei
))
909 c
->probability
= profile_probability::guessed_never ();
911 else if (!(prob
== profile_probability::always ()))
913 FOR_EACH_EDGE (c
, ei
, bb
->succs
)
914 c
->probability
/= prob
;
917 gcc_assert (bb
== taken_edge
->src
);
920 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
921 by NUM/DEN, in int arithmetic. May lose some accuracy. */
923 scale_bbs_frequencies_int (basic_block
*bbs
, int nbbs
, int num
, int den
)
929 /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
930 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
931 and still safely fit in int during calculations. */
937 num
= RDIV (1000 * num
, den
);
943 for (i
= 0; i
< nbbs
; i
++)
945 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
946 /* Make sure the frequencies do not grow over BB_FREQ_MAX. */
947 if (bbs
[i
]->frequency
> BB_FREQ_MAX
)
948 bbs
[i
]->frequency
= BB_FREQ_MAX
;
949 bbs
[i
]->count
= bbs
[i
]->count
.apply_scale (num
, den
);
953 /* numbers smaller than this value are safe to multiply without getting
955 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (int64_t) * 4 - 1))
957 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
958 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
959 function but considerably slower. */
961 scale_bbs_frequencies_gcov_type (basic_block
*bbs
, int nbbs
, gcov_type num
,
965 gcov_type fraction
= RDIV (num
* 65536, den
);
967 gcc_assert (fraction
>= 0);
969 if (num
< MAX_SAFE_MULTIPLIER
)
970 for (i
= 0; i
< nbbs
; i
++)
972 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
973 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
974 bbs
[i
]->count
= bbs
[i
]->count
.apply_scale (num
, den
);
976 bbs
[i
]->count
= bbs
[i
]->count
.apply_scale (fraction
, 65536);
979 for (i
= 0; i
< nbbs
; i
++)
981 if (sizeof (gcov_type
) > sizeof (int))
982 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
984 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* fraction
, 65536);
985 bbs
[i
]->count
= bbs
[i
]->count
.apply_scale (fraction
, 65536);
989 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
990 by NUM/DEN, in profile_count arithmetic. More accurate than previous
991 function but considerably slower. */
993 scale_bbs_frequencies_profile_count (basic_block
*bbs
, int nbbs
,
994 profile_count num
, profile_count den
)
998 for (i
= 0; i
< nbbs
; i
++)
1000 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
.to_gcov_type (),
1001 den
.to_gcov_type ());
1002 bbs
[i
]->count
= bbs
[i
]->count
.apply_scale (num
, den
);
1006 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1007 by NUM/DEN, in profile_count arithmetic. More accurate than previous
1008 function but considerably slower. */
1010 scale_bbs_frequencies (basic_block
*bbs
, int nbbs
,
1011 profile_probability p
)
1015 for (i
= 0; i
< nbbs
; i
++)
1017 bbs
[i
]->frequency
= p
.apply (bbs
[i
]->frequency
);
1018 bbs
[i
]->count
= bbs
[i
]->count
.apply_probability (p
);
1022 /* Helper types for hash tables. */
1024 struct htab_bb_copy_original_entry
1026 /* Block we are attaching info to. */
1028 /* Index of original or copy (depending on the hashtable) */
1032 struct bb_copy_hasher
: nofree_ptr_hash
<htab_bb_copy_original_entry
>
1034 static inline hashval_t
hash (const htab_bb_copy_original_entry
*);
1035 static inline bool equal (const htab_bb_copy_original_entry
*existing
,
1036 const htab_bb_copy_original_entry
* candidate
);
1040 bb_copy_hasher::hash (const htab_bb_copy_original_entry
*data
)
1042 return data
->index1
;
1046 bb_copy_hasher::equal (const htab_bb_copy_original_entry
*data
,
1047 const htab_bb_copy_original_entry
*data2
)
1049 return data
->index1
== data2
->index1
;
1052 /* Data structures used to maintain mapping between basic blocks and
1054 static hash_table
<bb_copy_hasher
> *bb_original
;
1055 static hash_table
<bb_copy_hasher
> *bb_copy
;
1057 /* And between loops and copies. */
1058 static hash_table
<bb_copy_hasher
> *loop_copy
;
1059 static object_allocator
<htab_bb_copy_original_entry
> *original_copy_bb_pool
;
1061 /* Initialize the data structures to maintain mapping between blocks
1064 initialize_original_copy_tables (void)
1066 original_copy_bb_pool
= new object_allocator
<htab_bb_copy_original_entry
>
1068 bb_original
= new hash_table
<bb_copy_hasher
> (10);
1069 bb_copy
= new hash_table
<bb_copy_hasher
> (10);
1070 loop_copy
= new hash_table
<bb_copy_hasher
> (10);
1073 /* Reset the data structures to maintain mapping between blocks and
1077 reset_original_copy_tables (void)
1079 gcc_assert (original_copy_bb_pool
);
1080 bb_original
->empty ();
1082 loop_copy
->empty ();
1085 /* Free the data structures to maintain mapping between blocks and
1088 free_original_copy_tables (void)
1090 gcc_assert (original_copy_bb_pool
);
1097 delete original_copy_bb_pool
;
1098 original_copy_bb_pool
= NULL
;
1101 /* Return true iff we have had a call to initialize_original_copy_tables
1102 without a corresponding call to free_original_copy_tables. */
1105 original_copy_tables_initialized_p (void)
1107 return original_copy_bb_pool
!= NULL
;
1110 /* Removes the value associated with OBJ from table TAB. */
1113 copy_original_table_clear (hash_table
<bb_copy_hasher
> *tab
, unsigned obj
)
1115 htab_bb_copy_original_entry
**slot
;
1116 struct htab_bb_copy_original_entry key
, *elt
;
1118 if (!original_copy_bb_pool
)
1122 slot
= tab
->find_slot (&key
, NO_INSERT
);
1127 tab
->clear_slot (slot
);
1128 original_copy_bb_pool
->remove (elt
);
1131 /* Sets the value associated with OBJ in table TAB to VAL.
1132 Do nothing when data structures are not initialized. */
1135 copy_original_table_set (hash_table
<bb_copy_hasher
> *tab
,
1136 unsigned obj
, unsigned val
)
1138 struct htab_bb_copy_original_entry
**slot
;
1139 struct htab_bb_copy_original_entry key
;
1141 if (!original_copy_bb_pool
)
1145 slot
= tab
->find_slot (&key
, INSERT
);
1148 *slot
= original_copy_bb_pool
->allocate ();
1149 (*slot
)->index1
= obj
;
1151 (*slot
)->index2
= val
;
1154 /* Set original for basic block. Do nothing when data structures are not
1155 initialized so passes not needing this don't need to care. */
1157 set_bb_original (basic_block bb
, basic_block original
)
1159 copy_original_table_set (bb_original
, bb
->index
, original
->index
);
1162 /* Get the original basic block. */
1164 get_bb_original (basic_block bb
)
1166 struct htab_bb_copy_original_entry
*entry
;
1167 struct htab_bb_copy_original_entry key
;
1169 gcc_assert (original_copy_bb_pool
);
1171 key
.index1
= bb
->index
;
1172 entry
= bb_original
->find (&key
);
1174 return BASIC_BLOCK_FOR_FN (cfun
, entry
->index2
);
1179 /* Set copy for basic block. Do nothing when data structures are not
1180 initialized so passes not needing this don't need to care. */
1182 set_bb_copy (basic_block bb
, basic_block copy
)
1184 copy_original_table_set (bb_copy
, bb
->index
, copy
->index
);
1187 /* Get the copy of basic block. */
1189 get_bb_copy (basic_block bb
)
1191 struct htab_bb_copy_original_entry
*entry
;
1192 struct htab_bb_copy_original_entry key
;
1194 gcc_assert (original_copy_bb_pool
);
1196 key
.index1
= bb
->index
;
1197 entry
= bb_copy
->find (&key
);
1199 return BASIC_BLOCK_FOR_FN (cfun
, entry
->index2
);
1204 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1205 initialized so passes not needing this don't need to care. */
1208 set_loop_copy (struct loop
*loop
, struct loop
*copy
)
1211 copy_original_table_clear (loop_copy
, loop
->num
);
1213 copy_original_table_set (loop_copy
, loop
->num
, copy
->num
);
1216 /* Get the copy of LOOP. */
1219 get_loop_copy (struct loop
*loop
)
1221 struct htab_bb_copy_original_entry
*entry
;
1222 struct htab_bb_copy_original_entry key
;
1224 gcc_assert (original_copy_bb_pool
);
1226 key
.index1
= loop
->num
;
1227 entry
= loop_copy
->find (&key
);
1229 return get_loop (cfun
, entry
->index2
);