1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2013 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"
54 #include "hash-table.h"
55 #include "alloc-pool.h"
57 #include "basic-block.h"
59 #include "cfgloop.h" /* FIXME: For struct loop. */
63 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
65 /* Called once at initialization time. */
68 init_flow (struct function
*the_fun
)
71 the_fun
->cfg
= ggc_alloc_cleared_control_flow_graph ();
72 n_edges_for_fn (the_fun
) = 0;
73 ENTRY_BLOCK_PTR_FOR_FN (the_fun
)
74 = ggc_alloc_cleared_basic_block_def ();
75 ENTRY_BLOCK_PTR_FOR_FN (the_fun
)->index
= ENTRY_BLOCK
;
76 EXIT_BLOCK_PTR_FOR_FN (the_fun
)
77 = ggc_alloc_cleared_basic_block_def ();
78 EXIT_BLOCK_PTR_FOR_FN (the_fun
)->index
= EXIT_BLOCK
;
79 ENTRY_BLOCK_PTR_FOR_FN (the_fun
)->next_bb
80 = EXIT_BLOCK_PTR_FOR_FN (the_fun
);
81 EXIT_BLOCK_PTR_FOR_FN (the_fun
)->prev_bb
82 = ENTRY_BLOCK_PTR_FOR_FN (the_fun
);
85 /* Helper function for remove_edge and clear_edges. Frees edge structure
86 without actually removing it from the pred/succ arrays. */
91 n_edges_for_fn (cfun
)--;
95 /* Free the memory associated with the edge structures. */
106 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
108 vec_safe_truncate (bb
->succs
, 0);
109 vec_safe_truncate (bb
->preds
, 0);
112 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
114 vec_safe_truncate (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
, 0);
115 vec_safe_truncate (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
, 0);
117 gcc_assert (!n_edges_for_fn (cfun
));
120 /* Allocate memory for basic_block. */
126 bb
= ggc_alloc_cleared_basic_block_def ();
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 (ENTRY_BLOCK
, ENTRY_BLOCK_PTR_FOR_FN (cfun
));
157 SET_BASIC_BLOCK (EXIT_BLOCK
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
160 df_compact_blocks ();
165 i
= NUM_FIXED_BLOCKS
;
168 SET_BASIC_BLOCK (i
, bb
);
172 gcc_assert (i
== n_basic_blocks_for_fn (cfun
));
174 for (; i
< last_basic_block
; i
++)
175 SET_BASIC_BLOCK (i
, NULL
);
177 last_basic_block
= 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 (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_alloc_cleared_edge_def ();
265 n_edges_for_fn (cfun
)++;
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
= REG_BR_PROB_BASE
;
336 e
->count
= src
->count
;
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_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
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
, int flags
)
406 struct function
*fun
= DECL_STRUCT_FUNCTION (current_function_decl
);
407 char *s_indent
= (char *) alloca ((size_t) indent
+ 1);
408 memset ((void *) s_indent
, ' ', (size_t) indent
);
409 s_indent
[indent
] = '\0';
411 if (profile_status_for_function (fun
) == PROFILE_ABSENT
)
414 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
416 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
417 sum
+= e
->probability
;
418 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
419 fprintf (file
, "%s%sInvalid sum of outgoing probabilities %.1f%%\n",
420 (flags
& TDF_COMMENT
) ? ";; " : "", s_indent
,
421 sum
* 100.0 / REG_BR_PROB_BASE
);
423 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
425 if (EDGE_COUNT (bb
->succs
)
426 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
427 fprintf (file
, "%s%sInvalid sum of outgoing counts %i, should be %i\n",
428 (flags
& TDF_COMMENT
) ? ";; " : "", s_indent
,
429 (int) lsum
, (int) bb
->count
);
431 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (fun
))
434 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
435 sum
+= EDGE_FREQUENCY (e
);
436 if (abs (sum
- bb
->frequency
) > 100)
438 "%s%sInvalid sum of incoming frequencies %i, should be %i\n",
439 (flags
& TDF_COMMENT
) ? ";; " : "", s_indent
,
442 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
444 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
445 fprintf (file
, "%s%sInvalid sum of incoming counts %i, should be %i\n",
446 (flags
& TDF_COMMENT
) ? ";; " : "", s_indent
,
447 (int) lsum
, (int) bb
->count
);
449 if (BB_PARTITION (bb
) == BB_COLD_PARTITION
)
451 /* Warn about inconsistencies in the partitioning that are
452 currently caused by profile insanities created via optimization. */
453 if (!probably_never_executed_bb_p (fun
, bb
))
454 fprintf (file
, "%s%sBlock in cold partition with hot count\n",
455 (flags
& TDF_COMMENT
) ? ";; " : "", s_indent
);
456 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
458 if (!probably_never_executed_edge_p (fun
, e
))
460 "%s%sBlock in cold partition with incoming hot edge\n",
461 (flags
& TDF_COMMENT
) ? ";; " : "", s_indent
);
467 dump_edge_info (FILE *file
, edge e
, int flags
, int do_succ
)
469 basic_block side
= (do_succ
? e
->dest
: e
->src
);
470 bool do_details
= false;
472 if ((flags
& TDF_DETAILS
) != 0
473 && (flags
& TDF_SLIM
) == 0)
476 /* ENTRY_BLOCK_PTR/EXIT_BLOCK_PTR depend on cfun.
477 Compare against ENTRY_BLOCK/EXIT_BLOCK to avoid that dependency. */
478 if (side
->index
== ENTRY_BLOCK
)
479 fputs (" ENTRY", file
);
480 else if (side
->index
== EXIT_BLOCK
)
481 fputs (" EXIT", file
);
483 fprintf (file
, " %d", side
->index
);
485 if (e
->probability
&& do_details
)
486 fprintf (file
, " [%.1f%%] ", e
->probability
* 100.0 / REG_BR_PROB_BASE
);
488 if (e
->count
&& do_details
)
490 fputs (" count:", file
);
491 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
494 if (e
->flags
&& do_details
)
496 static const char * const bitnames
[] =
498 #define DEF_EDGE_FLAG(NAME,IDX) #NAME ,
499 #include "cfg-flags.def"
504 int i
, flags
= e
->flags
;
506 gcc_assert (e
->flags
<= EDGE_ALL_FLAGS
);
508 for (i
= 0; flags
; i
++)
509 if (flags
& (1 << i
))
515 fputs (bitnames
[i
], file
);
524 debug (edge_def
&ref
)
526 /* FIXME (crowl): Is this desireable? */
527 dump_edge_info (stderr
, &ref
, 0, false);
528 dump_edge_info (stderr
, &ref
, 0, true);
532 debug (edge_def
*ptr
)
537 fprintf (stderr
, "<nil>\n");
540 /* Simple routines to easily allocate AUX fields of basic blocks. */
542 static struct obstack block_aux_obstack
;
543 static void *first_block_aux_obj
= 0;
544 static struct obstack edge_aux_obstack
;
545 static void *first_edge_aux_obj
= 0;
547 /* Allocate a memory block of SIZE as BB->aux. The obstack must
548 be first initialized by alloc_aux_for_blocks. */
551 alloc_aux_for_block (basic_block bb
, int size
)
553 /* Verify that aux field is clear. */
554 gcc_assert (!bb
->aux
&& first_block_aux_obj
);
555 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
556 memset (bb
->aux
, 0, size
);
559 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
560 alloc_aux_for_block for each basic block. */
563 alloc_aux_for_blocks (int size
)
565 static int initialized
;
569 gcc_obstack_init (&block_aux_obstack
);
573 /* Check whether AUX data are still allocated. */
574 gcc_assert (!first_block_aux_obj
);
576 first_block_aux_obj
= obstack_alloc (&block_aux_obstack
, 0);
582 alloc_aux_for_block (bb
, size
);
586 /* Clear AUX pointers of all blocks. */
589 clear_aux_for_blocks (void)
597 /* Free data allocated in block_aux_obstack and clear AUX pointers
601 free_aux_for_blocks (void)
603 gcc_assert (first_block_aux_obj
);
604 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
605 first_block_aux_obj
= NULL
;
607 clear_aux_for_blocks ();
610 /* Allocate a memory edge of SIZE as E->aux. The obstack must
611 be first initialized by alloc_aux_for_edges. */
614 alloc_aux_for_edge (edge e
, int size
)
616 /* Verify that aux field is clear. */
617 gcc_assert (!e
->aux
&& first_edge_aux_obj
);
618 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
619 memset (e
->aux
, 0, size
);
622 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
623 alloc_aux_for_edge for each basic edge. */
626 alloc_aux_for_edges (int size
)
628 static int initialized
;
632 gcc_obstack_init (&edge_aux_obstack
);
636 /* Check whether AUX data are still allocated. */
637 gcc_assert (!first_edge_aux_obj
);
639 first_edge_aux_obj
= obstack_alloc (&edge_aux_obstack
, 0);
644 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
645 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
650 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
651 alloc_aux_for_edge (e
, size
);
656 /* Clear AUX pointers of all edges. */
659 clear_aux_for_edges (void)
664 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
665 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
668 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
673 /* Free data allocated in edge_aux_obstack and clear AUX pointers
677 free_aux_for_edges (void)
679 gcc_assert (first_edge_aux_obj
);
680 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
681 first_edge_aux_obj
= NULL
;
683 clear_aux_for_edges ();
687 debug_bb (basic_block bb
)
689 dump_bb (stderr
, bb
, 0, dump_flags
);
692 DEBUG_FUNCTION basic_block
695 basic_block bb
= BASIC_BLOCK (n
);
700 /* Dumps cfg related information about basic block BB to OUTF.
701 If HEADER is true, dump things that appear before the instructions
702 contained in BB. If FOOTER is true, dump things that appear after.
703 Flags are the TDF_* masks as documented in dumpfile.h.
704 NB: With TDF_DETAILS, it is assumed that cfun is available, so
705 that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE. */
708 dump_bb_info (FILE *outf
, basic_block bb
, int indent
, int flags
,
709 bool do_header
, bool do_footer
)
713 static const char * const bb_bitnames
[] =
715 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) #NAME ,
716 #include "cfg-flags.def"
718 #undef DEF_BASIC_BLOCK_FLAG
720 const unsigned n_bitnames
= sizeof (bb_bitnames
) / sizeof (char *);
722 char *s_indent
= (char *) alloca ((size_t) indent
+ 1);
723 memset ((void *) s_indent
, ' ', (size_t) indent
);
724 s_indent
[indent
] = '\0';
726 gcc_assert (bb
->flags
<= BB_ALL_FLAGS
);
732 if (flags
& TDF_COMMENT
)
734 fprintf (outf
, "%sbasic block %d, loop depth %d",
735 s_indent
, bb
->index
, bb_loop_depth (bb
));
736 if (flags
& TDF_DETAILS
)
738 struct function
*fun
= DECL_STRUCT_FUNCTION (current_function_decl
);
739 fprintf (outf
, ", count " HOST_WIDEST_INT_PRINT_DEC
,
740 (HOST_WIDEST_INT
) bb
->count
);
741 fprintf (outf
, ", freq %i", bb
->frequency
);
742 if (maybe_hot_bb_p (fun
, bb
))
743 fputs (", maybe hot", outf
);
744 if (probably_never_executed_bb_p (fun
, bb
))
745 fputs (", probably never executed", outf
);
749 check_bb_profile (bb
, outf
, indent
, flags
);
751 if (flags
& TDF_DETAILS
)
753 if (flags
& TDF_COMMENT
)
755 fprintf (outf
, "%s prev block ", s_indent
);
757 fprintf (outf
, "%d", bb
->prev_bb
->index
);
759 fprintf (outf
, "(nil)");
760 fprintf (outf
, ", next block ");
762 fprintf (outf
, "%d", bb
->next_bb
->index
);
764 fprintf (outf
, "(nil)");
766 fputs (", flags:", outf
);
768 for (i
= 0; i
< n_bitnames
; i
++)
769 if (bb
->flags
& (1 << i
))
776 fputs (bb_bitnames
[i
], outf
);
783 if (flags
& TDF_COMMENT
)
785 fprintf (outf
, "%s pred: ", s_indent
);
787 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
791 if (flags
& TDF_COMMENT
)
793 fprintf (outf
, "%s ", s_indent
);
796 dump_edge_info (outf
, e
, flags
, 0);
805 if (flags
& TDF_COMMENT
)
807 fprintf (outf
, "%s succ: ", s_indent
);
809 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
813 if (flags
& TDF_COMMENT
)
815 fprintf (outf
, "%s ", s_indent
);
818 dump_edge_info (outf
, e
, flags
, 1);
826 /* Dumps a brief description of cfg to FILE. */
829 brief_dump_cfg (FILE *file
, int flags
)
835 dump_bb_info (file
, bb
, 0,
836 flags
& (TDF_COMMENT
| TDF_DETAILS
),
841 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
842 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
843 redirected to destination of TAKEN_EDGE.
845 This function may leave the profile inconsistent in the case TAKEN_EDGE
846 frequency or count is believed to be lower than FREQUENCY or COUNT
849 update_bb_profile_for_threading (basic_block bb
, int edge_frequency
,
850 gcov_type count
, edge taken_edge
)
860 fprintf (dump_file
, "bb %i count became negative after threading",
865 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
866 Watch for overflows. */
868 prob
= GCOV_COMPUTE_SCALE (edge_frequency
, bb
->frequency
);
871 if (prob
> taken_edge
->probability
)
874 fprintf (dump_file
, "Jump threading proved probability of edge "
875 "%i->%i too small (it is %i, should be %i).\n",
876 taken_edge
->src
->index
, taken_edge
->dest
->index
,
877 taken_edge
->probability
, prob
);
878 prob
= taken_edge
->probability
;
881 /* Now rescale the probabilities. */
882 taken_edge
->probability
-= prob
;
883 prob
= REG_BR_PROB_BASE
- prob
;
884 bb
->frequency
-= edge_frequency
;
885 if (bb
->frequency
< 0)
890 fprintf (dump_file
, "Edge frequencies of bb %i has been reset, "
891 "frequency of block should end up being 0, it is %i\n",
892 bb
->index
, bb
->frequency
);
893 EDGE_SUCC (bb
, 0)->probability
= REG_BR_PROB_BASE
;
894 ei
= ei_start (bb
->succs
);
896 for (; (c
= ei_safe_edge (ei
)); ei_next (&ei
))
899 else if (prob
!= REG_BR_PROB_BASE
)
901 int scale
= RDIV (65536 * REG_BR_PROB_BASE
, prob
);
903 FOR_EACH_EDGE (c
, ei
, bb
->succs
)
905 /* Protect from overflow due to additional scaling. */
906 if (c
->probability
> prob
)
907 c
->probability
= REG_BR_PROB_BASE
;
910 c
->probability
= RDIV (c
->probability
* scale
, 65536);
911 if (c
->probability
> REG_BR_PROB_BASE
)
912 c
->probability
= REG_BR_PROB_BASE
;
917 gcc_assert (bb
== taken_edge
->src
);
918 taken_edge
->count
-= count
;
919 if (taken_edge
->count
< 0)
922 fprintf (dump_file
, "edge %i->%i count became negative after threading",
923 taken_edge
->src
->index
, taken_edge
->dest
->index
);
924 taken_edge
->count
= 0;
928 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
929 by NUM/DEN, in int arithmetic. May lose some accuracy. */
931 scale_bbs_frequencies_int (basic_block
*bbs
, int nbbs
, int num
, int den
)
938 /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
939 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
940 and still safely fit in int during calculations. */
946 num
= RDIV (1000 * num
, den
);
952 for (i
= 0; i
< nbbs
; i
++)
955 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
956 /* Make sure the frequencies do not grow over BB_FREQ_MAX. */
957 if (bbs
[i
]->frequency
> BB_FREQ_MAX
)
958 bbs
[i
]->frequency
= BB_FREQ_MAX
;
959 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
960 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
961 e
->count
= RDIV (e
->count
* num
, den
);
965 /* numbers smaller than this value are safe to multiply without getting
967 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
969 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
970 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
971 function but considerably slower. */
973 scale_bbs_frequencies_gcov_type (basic_block
*bbs
, int nbbs
, gcov_type num
,
978 gcov_type fraction
= RDIV (num
* 65536, den
);
980 gcc_assert (fraction
>= 0);
982 if (num
< MAX_SAFE_MULTIPLIER
)
983 for (i
= 0; i
< nbbs
; i
++)
986 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
987 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
988 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
990 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
991 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
992 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
993 e
->count
= RDIV (e
->count
* num
, den
);
995 e
->count
= RDIV (e
->count
* fraction
, 65536);
998 for (i
= 0; i
< nbbs
; i
++)
1001 if (sizeof (gcov_type
) > sizeof (int))
1002 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
1004 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* fraction
, 65536);
1005 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
1006 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1007 e
->count
= RDIV (e
->count
* fraction
, 65536);
1011 /* Helper types for hash tables. */
1013 struct htab_bb_copy_original_entry
1015 /* Block we are attaching info to. */
1017 /* Index of original or copy (depending on the hashtable) */
1021 struct bb_copy_hasher
: typed_noop_remove
<htab_bb_copy_original_entry
>
1023 typedef htab_bb_copy_original_entry value_type
;
1024 typedef htab_bb_copy_original_entry compare_type
;
1025 static inline hashval_t
hash (const value_type
*);
1026 static inline bool equal (const value_type
*existing
,
1027 const compare_type
* candidate
);
1031 bb_copy_hasher::hash (const value_type
*data
)
1033 return data
->index1
;
1037 bb_copy_hasher::equal (const value_type
*data
, const compare_type
*data2
)
1039 return data
->index1
== data2
->index1
;
1042 /* Data structures used to maintain mapping between basic blocks and
1044 static hash_table
<bb_copy_hasher
> bb_original
;
1045 static hash_table
<bb_copy_hasher
> bb_copy
;
1047 /* And between loops and copies. */
1048 static hash_table
<bb_copy_hasher
> loop_copy
;
1049 static alloc_pool original_copy_bb_pool
;
1052 /* Initialize the data structures to maintain mapping between blocks
1055 initialize_original_copy_tables (void)
1057 gcc_assert (!original_copy_bb_pool
);
1058 original_copy_bb_pool
1059 = create_alloc_pool ("original_copy",
1060 sizeof (struct htab_bb_copy_original_entry
), 10);
1061 bb_original
.create (10);
1062 bb_copy
.create (10);
1063 loop_copy
.create (10);
1066 /* Free the data structures to maintain mapping between blocks and
1069 free_original_copy_tables (void)
1071 gcc_assert (original_copy_bb_pool
);
1073 bb_original
.dispose ();
1074 loop_copy
.dispose ();
1075 free_alloc_pool (original_copy_bb_pool
);
1076 original_copy_bb_pool
= NULL
;
1079 /* Removes the value associated with OBJ from table TAB. */
1082 copy_original_table_clear (hash_table
<bb_copy_hasher
> tab
, unsigned obj
)
1084 htab_bb_copy_original_entry
**slot
;
1085 struct htab_bb_copy_original_entry key
, *elt
;
1087 if (!original_copy_bb_pool
)
1091 slot
= tab
.find_slot (&key
, NO_INSERT
);
1096 tab
.clear_slot (slot
);
1097 pool_free (original_copy_bb_pool
, elt
);
1100 /* Sets the value associated with OBJ in table TAB to VAL.
1101 Do nothing when data structures are not initialized. */
1104 copy_original_table_set (hash_table
<bb_copy_hasher
> tab
,
1105 unsigned obj
, unsigned val
)
1107 struct htab_bb_copy_original_entry
**slot
;
1108 struct htab_bb_copy_original_entry key
;
1110 if (!original_copy_bb_pool
)
1114 slot
= tab
.find_slot (&key
, INSERT
);
1117 *slot
= (struct htab_bb_copy_original_entry
*)
1118 pool_alloc (original_copy_bb_pool
);
1119 (*slot
)->index1
= obj
;
1121 (*slot
)->index2
= val
;
1124 /* Set original for basic block. Do nothing when data structures are not
1125 initialized so passes not needing this don't need to care. */
1127 set_bb_original (basic_block bb
, basic_block original
)
1129 copy_original_table_set (bb_original
, bb
->index
, original
->index
);
1132 /* Get the original basic block. */
1134 get_bb_original (basic_block bb
)
1136 struct htab_bb_copy_original_entry
*entry
;
1137 struct htab_bb_copy_original_entry key
;
1139 gcc_assert (original_copy_bb_pool
);
1141 key
.index1
= bb
->index
;
1142 entry
= bb_original
.find (&key
);
1144 return BASIC_BLOCK (entry
->index2
);
1149 /* Set copy for basic block. Do nothing when data structures are not
1150 initialized so passes not needing this don't need to care. */
1152 set_bb_copy (basic_block bb
, basic_block copy
)
1154 copy_original_table_set (bb_copy
, bb
->index
, copy
->index
);
1157 /* Get the copy of basic block. */
1159 get_bb_copy (basic_block bb
)
1161 struct htab_bb_copy_original_entry
*entry
;
1162 struct htab_bb_copy_original_entry key
;
1164 gcc_assert (original_copy_bb_pool
);
1166 key
.index1
= bb
->index
;
1167 entry
= bb_copy
.find (&key
);
1169 return BASIC_BLOCK (entry
->index2
);
1174 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1175 initialized so passes not needing this don't need to care. */
1178 set_loop_copy (struct loop
*loop
, struct loop
*copy
)
1181 copy_original_table_clear (loop_copy
, loop
->num
);
1183 copy_original_table_set (loop_copy
, loop
->num
, copy
->num
);
1186 /* Get the copy of LOOP. */
1189 get_loop_copy (struct loop
*loop
)
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
= loop
->num
;
1197 entry
= loop_copy
.find (&key
);
1199 return get_loop (cfun
, entry
->index2
);