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 the_fun
->cfg
->count_max
= profile_count::uninitialized ();
72 ENTRY_BLOCK_PTR_FOR_FN (the_fun
)
74 ENTRY_BLOCK_PTR_FOR_FN (the_fun
)->index
= ENTRY_BLOCK
;
75 EXIT_BLOCK_PTR_FOR_FN (the_fun
)
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
> ();
126 bb
->count
= profile_count::uninitialized ();
130 /* Link block B to chain after AFTER. */
132 link_block (basic_block b
, basic_block after
)
134 b
->next_bb
= after
->next_bb
;
137 b
->next_bb
->prev_bb
= b
;
140 /* Unlink block B from chain. */
142 unlink_block (basic_block b
)
144 b
->next_bb
->prev_bb
= b
->prev_bb
;
145 b
->prev_bb
->next_bb
= b
->next_bb
;
150 /* Sequentially order blocks and compact the arrays. */
152 compact_blocks (void)
156 SET_BASIC_BLOCK_FOR_FN (cfun
, ENTRY_BLOCK
, ENTRY_BLOCK_PTR_FOR_FN (cfun
));
157 SET_BASIC_BLOCK_FOR_FN (cfun
, EXIT_BLOCK
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
160 df_compact_blocks ();
165 i
= NUM_FIXED_BLOCKS
;
166 FOR_EACH_BB_FN (bb
, cfun
)
168 SET_BASIC_BLOCK_FOR_FN (cfun
, i
, bb
);
172 gcc_assert (i
== n_basic_blocks_for_fn (cfun
));
174 for (; i
< last_basic_block_for_fn (cfun
); i
++)
175 SET_BASIC_BLOCK_FOR_FN (cfun
, i
, NULL
);
177 last_basic_block_for_fn (cfun
) = n_basic_blocks_for_fn (cfun
);
180 /* Remove block B from the basic block array. */
183 expunge_block (basic_block b
)
186 SET_BASIC_BLOCK_FOR_FN (cfun
, b
->index
, NULL
);
187 n_basic_blocks_for_fn (cfun
)--;
188 /* We should be able to ggc_free here, but we are not.
189 The dead SSA_NAMES are left pointing to dead statements that are pointing
190 to dead basic blocks making garbage collector to die.
191 We should be able to release all dead SSA_NAMES and at the same time we should
192 clear out BB pointer of dead statements consistently. */
195 /* Connect E to E->src. */
200 vec_safe_push (e
->src
->succs
, e
);
201 df_mark_solutions_dirty ();
204 /* Connect E to E->dest. */
207 connect_dest (edge e
)
209 basic_block dest
= e
->dest
;
210 vec_safe_push (dest
->preds
, e
);
211 e
->dest_idx
= EDGE_COUNT (dest
->preds
) - 1;
212 df_mark_solutions_dirty ();
215 /* Disconnect edge E from E->src. */
218 disconnect_src (edge e
)
220 basic_block src
= e
->src
;
224 for (ei
= ei_start (src
->succs
); (tmp
= ei_safe_edge (ei
)); )
228 src
->succs
->unordered_remove (ei
.index
);
229 df_mark_solutions_dirty ();
239 /* Disconnect edge E from E->dest. */
242 disconnect_dest (edge e
)
244 basic_block dest
= e
->dest
;
245 unsigned int dest_idx
= e
->dest_idx
;
247 dest
->preds
->unordered_remove (dest_idx
);
249 /* If we removed an edge in the middle of the edge vector, we need
250 to update dest_idx of the edge that moved into the "hole". */
251 if (dest_idx
< EDGE_COUNT (dest
->preds
))
252 EDGE_PRED (dest
, dest_idx
)->dest_idx
= dest_idx
;
253 df_mark_solutions_dirty ();
256 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
257 created edge. Use this only if you are sure that this edge can't
258 possibly already exist. */
261 unchecked_make_edge (basic_block src
, basic_block dst
, int flags
)
264 e
= ggc_cleared_alloc
<edge_def
> ();
265 n_edges_for_fn (cfun
)++;
267 e
->probability
= profile_probability::uninitialized ();
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_FOR_FN (cfun
)
287 || dst
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
288 return make_edge (src
, dst
, flags
);
290 /* Does the requested edge already exist? */
291 if (! bitmap_bit_p (edge_cache
, dst
->index
))
293 /* The edge does not exist. Create one and update the
295 bitmap_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
= profile_probability::always ();
340 /* This function will remove an edge from the flow graph. */
343 remove_edge_raw (edge e
)
345 remove_predictions_associated_with_edge (e
);
346 execute_on_shrinking_pred (e
);
354 /* Redirect an edge's successor from one block to another. */
357 redirect_edge_succ (edge e
, basic_block new_succ
)
359 execute_on_shrinking_pred (e
);
365 /* Reconnect the edge to the new successor block. */
368 execute_on_growing_pred (e
);
371 /* Redirect an edge's predecessor from one block to another. */
374 redirect_edge_pred (edge e
, basic_block new_pred
)
380 /* Reconnect the edge to the new predecessor block. */
384 /* Clear all basic block flags that do not have to be preserved. */
386 clear_bb_flags (void)
390 FOR_ALL_BB_FN (bb
, cfun
)
391 bb
->flags
&= BB_FLAGS_TO_PRESERVE
;
394 /* Check the consistency of profile information. We can't do that
395 in verify_flow_info, as the counts may get invalid for incompletely
396 solved graphs, later eliminating of conditionals or roundoff errors.
397 It is still practical to have them reported for debugging of simple
400 check_bb_profile (basic_block bb
, FILE * file
, int indent
)
404 struct function
*fun
= DECL_STRUCT_FUNCTION (current_function_decl
);
405 char *s_indent
= (char *) alloca ((size_t) indent
+ 1);
406 memset ((void *) s_indent
, ' ', (size_t) indent
);
407 s_indent
[indent
] = '\0';
409 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
412 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
415 profile_probability sum
= profile_probability::never ();
418 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
420 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
422 sum
+= e
->probability
;
423 if (e
->probability
.initialized_p ())
424 isum
+= e
->probability
.to_reg_br_prob_base ();
426 /* Only report mismatches for non-EH control flow. If there are only EH
427 edges it means that the BB ends by noreturn call. Here the control
428 flow may just terminate. */
431 if (sum
.differs_from_p (profile_probability::always ()))
434 ";; %sInvalid sum of outgoing probabilities ",
437 fprintf (file
, "\n");
439 /* Probabilities caps to 100% and thus the previous test will never
440 fire if the sum of probabilities is too large. */
441 else if (isum
> REG_BR_PROB_BASE
+ 100)
444 ";; %sInvalid sum of outgoing probabilities %.1f%%\n",
445 s_indent
, isum
* 100.0 / REG_BR_PROB_BASE
);
449 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (fun
))
451 profile_count sum
= profile_count::zero ();
452 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
454 if (sum
.differs_from_p (bb
->count
))
456 fprintf (file
, ";; %sInvalid sum of incoming counts ",
459 fprintf (file
, ", should be ");
460 bb
->count
.dump (file
);
461 fprintf (file
, "\n");
464 if (BB_PARTITION (bb
) == BB_COLD_PARTITION
)
466 /* Warn about inconsistencies in the partitioning that are
467 currently caused by profile insanities created via optimization. */
468 if (!probably_never_executed_bb_p (fun
, bb
))
469 fprintf (file
, ";; %sBlock in cold partition with hot count\n",
471 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
473 if (!probably_never_executed_edge_p (fun
, e
))
475 ";; %sBlock in cold partition with incoming hot edge\n",
482 dump_edge_info (FILE *file
, edge e
, dump_flags_t flags
, int do_succ
)
484 basic_block side
= (do_succ
? e
->dest
: e
->src
);
485 bool do_details
= false;
487 if ((flags
& TDF_DETAILS
) != 0
488 && (flags
& TDF_SLIM
) == 0)
491 if (side
->index
== ENTRY_BLOCK
)
492 fputs (" ENTRY", file
);
493 else if (side
->index
== EXIT_BLOCK
)
494 fputs (" EXIT", file
);
496 fprintf (file
, " %d", side
->index
);
498 if (e
->probability
.initialized_p () && do_details
)
500 fprintf (file
, " [");
501 e
->probability
.dump (file
);
502 fprintf (file
, "] ");
505 if (e
->count ().initialized_p () && do_details
)
507 fputs (" count:", file
);
508 e
->count ().dump (file
);
511 if (e
->flags
&& do_details
)
513 static const char * const bitnames
[] =
515 #define DEF_EDGE_FLAG(NAME,IDX) #NAME ,
516 #include "cfg-flags.def"
521 int i
, flags
= e
->flags
;
523 gcc_assert (e
->flags
<= EDGE_ALL_FLAGS
);
525 for (i
= 0; flags
; i
++)
526 if (flags
& (1 << i
))
532 fputs (bitnames
[i
], file
);
541 debug (edge_def
&ref
)
543 /* FIXME (crowl): Is this desireable? */
544 dump_edge_info (stderr
, &ref
, 0, false);
545 dump_edge_info (stderr
, &ref
, 0, true);
549 debug (edge_def
*ptr
)
554 fprintf (stderr
, "<nil>\n");
557 /* Simple routines to easily allocate AUX fields of basic blocks. */
559 static struct obstack block_aux_obstack
;
560 static void *first_block_aux_obj
= 0;
561 static struct obstack edge_aux_obstack
;
562 static void *first_edge_aux_obj
= 0;
564 /* Allocate a memory block of SIZE as BB->aux. The obstack must
565 be first initialized by alloc_aux_for_blocks. */
568 alloc_aux_for_block (basic_block bb
, int size
)
570 /* Verify that aux field is clear. */
571 gcc_assert (!bb
->aux
&& first_block_aux_obj
);
572 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
573 memset (bb
->aux
, 0, size
);
576 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
577 alloc_aux_for_block for each basic block. */
580 alloc_aux_for_blocks (int size
)
582 static int initialized
;
586 gcc_obstack_init (&block_aux_obstack
);
590 /* Check whether AUX data are still allocated. */
591 gcc_assert (!first_block_aux_obj
);
593 first_block_aux_obj
= obstack_alloc (&block_aux_obstack
, 0);
598 FOR_ALL_BB_FN (bb
, cfun
)
599 alloc_aux_for_block (bb
, size
);
603 /* Clear AUX pointers of all blocks. */
606 clear_aux_for_blocks (void)
610 FOR_ALL_BB_FN (bb
, cfun
)
614 /* Free data allocated in block_aux_obstack and clear AUX pointers
618 free_aux_for_blocks (void)
620 gcc_assert (first_block_aux_obj
);
621 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
622 first_block_aux_obj
= NULL
;
624 clear_aux_for_blocks ();
627 /* Allocate a memory edge of SIZE as E->aux. The obstack must
628 be first initialized by alloc_aux_for_edges. */
631 alloc_aux_for_edge (edge e
, int size
)
633 /* Verify that aux field is clear. */
634 gcc_assert (!e
->aux
&& first_edge_aux_obj
);
635 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
636 memset (e
->aux
, 0, size
);
639 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
640 alloc_aux_for_edge for each basic edge. */
643 alloc_aux_for_edges (int size
)
645 static int initialized
;
649 gcc_obstack_init (&edge_aux_obstack
);
653 /* Check whether AUX data are still allocated. */
654 gcc_assert (!first_edge_aux_obj
);
656 first_edge_aux_obj
= obstack_alloc (&edge_aux_obstack
, 0);
661 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
662 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
667 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
668 alloc_aux_for_edge (e
, size
);
673 /* Clear AUX pointers of all edges. */
676 clear_aux_for_edges (void)
681 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
682 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
685 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
690 /* Free data allocated in edge_aux_obstack and clear AUX pointers
694 free_aux_for_edges (void)
696 gcc_assert (first_edge_aux_obj
);
697 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
698 first_edge_aux_obj
= NULL
;
700 clear_aux_for_edges ();
704 debug_bb (basic_block bb
)
706 dump_bb (stderr
, bb
, 0, dump_flags
);
709 DEBUG_FUNCTION basic_block
712 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, n
);
717 /* Dumps cfg related information about basic block BB to OUTF.
718 If HEADER is true, dump things that appear before the instructions
719 contained in BB. If FOOTER is true, dump things that appear after.
720 Flags are the TDF_* masks as documented in dumpfile.h.
721 NB: With TDF_DETAILS, it is assumed that cfun is available, so
722 that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE. */
725 dump_bb_info (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
,
726 bool do_header
, bool do_footer
)
730 static const char * const bb_bitnames
[] =
732 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) #NAME ,
733 #include "cfg-flags.def"
735 #undef DEF_BASIC_BLOCK_FLAG
737 const unsigned n_bitnames
= sizeof (bb_bitnames
) / sizeof (char *);
739 char *s_indent
= (char *) alloca ((size_t) indent
+ 1);
740 memset ((void *) s_indent
, ' ', (size_t) indent
);
741 s_indent
[indent
] = '\0';
743 gcc_assert (bb
->flags
<= BB_ALL_FLAGS
);
750 fprintf (outf
, "%sbasic block %d, loop depth %d",
751 s_indent
, bb
->index
, bb_loop_depth (bb
));
752 if (flags
& TDF_DETAILS
)
754 struct function
*fun
= DECL_STRUCT_FUNCTION (current_function_decl
);
755 if (bb
->count
.initialized_p ())
757 fputs (", count ", outf
);
758 bb
->count
.dump (outf
);
760 if (maybe_hot_bb_p (fun
, bb
))
761 fputs (", maybe hot", outf
);
762 if (probably_never_executed_bb_p (fun
, bb
))
763 fputs (", probably never executed", outf
);
767 if (flags
& TDF_DETAILS
)
769 check_bb_profile (bb
, outf
, indent
);
771 fprintf (outf
, "%s prev block ", s_indent
);
773 fprintf (outf
, "%d", bb
->prev_bb
->index
);
775 fprintf (outf
, "(nil)");
776 fprintf (outf
, ", next block ");
778 fprintf (outf
, "%d", bb
->next_bb
->index
);
780 fprintf (outf
, "(nil)");
782 fputs (", flags:", outf
);
784 for (i
= 0; i
< n_bitnames
; i
++)
785 if (bb
->flags
& (1 << i
))
792 fputs (bb_bitnames
[i
], outf
);
800 fprintf (outf
, "%s pred: ", s_indent
);
802 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
807 fprintf (outf
, "%s ", s_indent
);
810 dump_edge_info (outf
, e
, flags
, 0);
820 fprintf (outf
, "%s succ: ", s_indent
);
822 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
827 fprintf (outf
, "%s ", s_indent
);
830 dump_edge_info (outf
, e
, flags
, 1);
838 /* Dumps a brief description of cfg to FILE. */
841 brief_dump_cfg (FILE *file
, dump_flags_t flags
)
845 FOR_EACH_BB_FN (bb
, cfun
)
847 dump_bb_info (file
, bb
, 0, flags
& TDF_DETAILS
, true, true);
851 /* An edge originally destinating BB of COUNT has been proved to
852 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
853 redirected to destination of TAKEN_EDGE.
855 This function may leave the profile inconsistent in the case TAKEN_EDGE
856 frequency or count is believed to be lower than COUNT
859 update_bb_profile_for_threading (basic_block bb
,
860 profile_count count
, edge taken_edge
)
863 profile_probability prob
;
866 if (bb
->count
< count
)
869 fprintf (dump_file
, "bb %i count became negative after threading",
874 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
875 Watch for overflows. */
876 if (bb
->count
.nonzero_p ())
877 prob
= count
.probability_in (bb
->count
);
879 prob
= profile_probability::never ();
880 if (prob
> taken_edge
->probability
)
884 fprintf (dump_file
, "Jump threading proved probability of edge "
885 "%i->%i too small (it is ",
886 taken_edge
->src
->index
, taken_edge
->dest
->index
);
887 taken_edge
->probability
.dump (dump_file
);
888 fprintf (dump_file
, " should be ");
889 prob
.dump (dump_file
);
890 fprintf (dump_file
, ")\n");
892 prob
= taken_edge
->probability
.apply_scale (6, 8);
895 /* Now rescale the probabilities. */
896 taken_edge
->probability
-= prob
;
897 prob
= prob
.invert ();
898 if (prob
== profile_probability::never ())
901 fprintf (dump_file
, "Edge probabilities of bb %i has been reset, "
902 "count of block should end up being 0, it is non-zero\n",
904 EDGE_SUCC (bb
, 0)->probability
= profile_probability::guessed_always ();
905 ei
= ei_start (bb
->succs
);
907 for (; (c
= ei_safe_edge (ei
)); ei_next (&ei
))
908 c
->probability
= profile_probability::guessed_never ();
910 else if (!(prob
== profile_probability::always ()))
912 FOR_EACH_EDGE (c
, ei
, bb
->succs
)
913 c
->probability
/= prob
;
916 gcc_assert (bb
== taken_edge
->src
);
919 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
920 by NUM/DEN, in int arithmetic. May lose some accuracy. */
922 scale_bbs_frequencies_int (basic_block
*bbs
, int nbbs
, int num
, int den
)
928 /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
929 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
930 and still safely fit in int during calculations. */
936 num
= RDIV (1000 * num
, den
);
942 for (i
= 0; i
< nbbs
; i
++)
944 bbs
[i
]->count
= bbs
[i
]->count
.apply_scale (num
, den
);
948 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
949 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
950 function but considerably slower. */
952 scale_bbs_frequencies_gcov_type (basic_block
*bbs
, int nbbs
, gcov_type num
,
957 for (i
= 0; i
< nbbs
; i
++)
958 bbs
[i
]->count
= bbs
[i
]->count
.apply_scale (num
, den
);
961 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
962 by NUM/DEN, in profile_count arithmetic. More accurate than previous
963 function but considerably slower. */
965 scale_bbs_frequencies_profile_count (basic_block
*bbs
, int nbbs
,
966 profile_count num
, profile_count den
)
969 if (num
== profile_count::zero () || den
.nonzero_p ())
970 for (i
= 0; i
< nbbs
; i
++)
971 bbs
[i
]->count
= bbs
[i
]->count
.apply_scale (num
, den
);
974 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
975 by NUM/DEN, in profile_count arithmetic. More accurate than previous
976 function but considerably slower. */
978 scale_bbs_frequencies (basic_block
*bbs
, int nbbs
,
979 profile_probability p
)
983 for (i
= 0; i
< nbbs
; i
++)
984 bbs
[i
]->count
= bbs
[i
]->count
.apply_probability (p
);
987 /* Helper types for hash tables. */
989 struct htab_bb_copy_original_entry
991 /* Block we are attaching info to. */
993 /* Index of original or copy (depending on the hashtable) */
997 struct bb_copy_hasher
: nofree_ptr_hash
<htab_bb_copy_original_entry
>
999 static inline hashval_t
hash (const htab_bb_copy_original_entry
*);
1000 static inline bool equal (const htab_bb_copy_original_entry
*existing
,
1001 const htab_bb_copy_original_entry
* candidate
);
1005 bb_copy_hasher::hash (const htab_bb_copy_original_entry
*data
)
1007 return data
->index1
;
1011 bb_copy_hasher::equal (const htab_bb_copy_original_entry
*data
,
1012 const htab_bb_copy_original_entry
*data2
)
1014 return data
->index1
== data2
->index1
;
1017 /* Data structures used to maintain mapping between basic blocks and
1019 static hash_table
<bb_copy_hasher
> *bb_original
;
1020 static hash_table
<bb_copy_hasher
> *bb_copy
;
1022 /* And between loops and copies. */
1023 static hash_table
<bb_copy_hasher
> *loop_copy
;
1024 static object_allocator
<htab_bb_copy_original_entry
> *original_copy_bb_pool
;
1026 /* Initialize the data structures to maintain mapping between blocks
1029 initialize_original_copy_tables (void)
1031 original_copy_bb_pool
= new object_allocator
<htab_bb_copy_original_entry
>
1033 bb_original
= new hash_table
<bb_copy_hasher
> (10);
1034 bb_copy
= new hash_table
<bb_copy_hasher
> (10);
1035 loop_copy
= new hash_table
<bb_copy_hasher
> (10);
1038 /* Reset the data structures to maintain mapping between blocks and
1042 reset_original_copy_tables (void)
1044 gcc_assert (original_copy_bb_pool
);
1045 bb_original
->empty ();
1047 loop_copy
->empty ();
1050 /* Free the data structures to maintain mapping between blocks and
1053 free_original_copy_tables (void)
1055 gcc_assert (original_copy_bb_pool
);
1062 delete original_copy_bb_pool
;
1063 original_copy_bb_pool
= NULL
;
1066 /* Return true iff we have had a call to initialize_original_copy_tables
1067 without a corresponding call to free_original_copy_tables. */
1070 original_copy_tables_initialized_p (void)
1072 return original_copy_bb_pool
!= NULL
;
1075 /* Removes the value associated with OBJ from table TAB. */
1078 copy_original_table_clear (hash_table
<bb_copy_hasher
> *tab
, unsigned obj
)
1080 htab_bb_copy_original_entry
**slot
;
1081 struct htab_bb_copy_original_entry key
, *elt
;
1083 if (!original_copy_bb_pool
)
1087 slot
= tab
->find_slot (&key
, NO_INSERT
);
1092 tab
->clear_slot (slot
);
1093 original_copy_bb_pool
->remove (elt
);
1096 /* Sets the value associated with OBJ in table TAB to VAL.
1097 Do nothing when data structures are not initialized. */
1100 copy_original_table_set (hash_table
<bb_copy_hasher
> *tab
,
1101 unsigned obj
, unsigned val
)
1103 struct htab_bb_copy_original_entry
**slot
;
1104 struct htab_bb_copy_original_entry key
;
1106 if (!original_copy_bb_pool
)
1110 slot
= tab
->find_slot (&key
, INSERT
);
1113 *slot
= original_copy_bb_pool
->allocate ();
1114 (*slot
)->index1
= obj
;
1116 (*slot
)->index2
= val
;
1119 /* Set original for basic block. Do nothing when data structures are not
1120 initialized so passes not needing this don't need to care. */
1122 set_bb_original (basic_block bb
, basic_block original
)
1124 copy_original_table_set (bb_original
, bb
->index
, original
->index
);
1127 /* Get the original basic block. */
1129 get_bb_original (basic_block bb
)
1131 struct htab_bb_copy_original_entry
*entry
;
1132 struct htab_bb_copy_original_entry key
;
1134 gcc_assert (original_copy_bb_pool
);
1136 key
.index1
= bb
->index
;
1137 entry
= bb_original
->find (&key
);
1139 return BASIC_BLOCK_FOR_FN (cfun
, entry
->index2
);
1144 /* Set copy for basic block. Do nothing when data structures are not
1145 initialized so passes not needing this don't need to care. */
1147 set_bb_copy (basic_block bb
, basic_block copy
)
1149 copy_original_table_set (bb_copy
, bb
->index
, copy
->index
);
1152 /* Get the copy of basic block. */
1154 get_bb_copy (basic_block bb
)
1156 struct htab_bb_copy_original_entry
*entry
;
1157 struct htab_bb_copy_original_entry key
;
1159 gcc_assert (original_copy_bb_pool
);
1161 key
.index1
= bb
->index
;
1162 entry
= bb_copy
->find (&key
);
1164 return BASIC_BLOCK_FOR_FN (cfun
, entry
->index2
);
1169 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1170 initialized so passes not needing this don't need to care. */
1173 set_loop_copy (struct loop
*loop
, struct loop
*copy
)
1176 copy_original_table_clear (loop_copy
, loop
->num
);
1178 copy_original_table_set (loop_copy
, loop
->num
, copy
->num
);
1181 /* Get the copy of LOOP. */
1184 get_loop_copy (struct loop
*loop
)
1186 struct htab_bb_copy_original_entry
*entry
;
1187 struct htab_bb_copy_original_entry key
;
1189 gcc_assert (original_copy_bb_pool
);
1191 key
.index1
= loop
->num
;
1192 entry
= loop_copy
->find (&key
);
1194 return get_loop (cfun
, entry
->index2
);