1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2023 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
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
);
82 the_fun
->cfg
->edge_flags_allocated
= EDGE_ALL_FLAGS
;
83 the_fun
->cfg
->bb_flags_allocated
= BB_ALL_FLAGS
;
86 /* Helper function for remove_edge and free_cffg. Frees edge structure
87 without actually removing it from the pred/succ arrays. */
90 free_edge (function
*fn
, edge e
)
92 n_edges_for_fn (fn
)--;
96 /* Free basic block BB. */
99 free_block (basic_block bb
)
101 vec_free (bb
->succs
);
103 vec_free (bb
->preds
);
108 /* Free the memory associated with the CFG in FN. */
111 free_cfg (struct function
*fn
)
117 for (basic_block bb
= ENTRY_BLOCK_PTR_FOR_FN (fn
); bb
; bb
= next
)
120 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
125 gcc_assert (!n_edges_for_fn (fn
));
126 /* Sanity check that dominance tree is freed. */
127 gcc_assert (!fn
->cfg
->x_dom_computed
[0] && !fn
->cfg
->x_dom_computed
[1]);
129 vec_free (fn
->cfg
->x_label_to_block_map
);
130 vec_free (basic_block_info_for_fn (fn
));
135 /* Allocate memory for basic_block. */
141 bb
= ggc_cleared_alloc
<basic_block_def
> ();
142 bb
->count
= profile_count::uninitialized ();
146 /* Link block B to chain after AFTER. */
148 link_block (basic_block b
, basic_block after
)
150 b
->next_bb
= after
->next_bb
;
153 b
->next_bb
->prev_bb
= b
;
156 /* Unlink block B from chain. */
158 unlink_block (basic_block b
)
160 b
->next_bb
->prev_bb
= b
->prev_bb
;
161 b
->prev_bb
->next_bb
= b
->next_bb
;
166 /* Sequentially order blocks and compact the arrays. */
168 compact_blocks (void)
172 SET_BASIC_BLOCK_FOR_FN (cfun
, ENTRY_BLOCK
, ENTRY_BLOCK_PTR_FOR_FN (cfun
));
173 SET_BASIC_BLOCK_FOR_FN (cfun
, EXIT_BLOCK
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
176 df_compact_blocks ();
181 i
= NUM_FIXED_BLOCKS
;
182 FOR_EACH_BB_FN (bb
, cfun
)
184 SET_BASIC_BLOCK_FOR_FN (cfun
, i
, bb
);
188 gcc_assert (i
== n_basic_blocks_for_fn (cfun
));
190 for (; i
< last_basic_block_for_fn (cfun
); i
++)
191 SET_BASIC_BLOCK_FOR_FN (cfun
, i
, NULL
);
193 last_basic_block_for_fn (cfun
) = n_basic_blocks_for_fn (cfun
);
196 /* Remove block B from the basic block array. */
199 expunge_block (basic_block b
)
202 SET_BASIC_BLOCK_FOR_FN (cfun
, b
->index
, NULL
);
203 n_basic_blocks_for_fn (cfun
)--;
204 /* We should be able to ggc_free here, but we are not.
205 The dead SSA_NAMES are left pointing to dead statements that are pointing
206 to dead basic blocks making garbage collector to die.
207 We should be able to release all dead SSA_NAMES and at the same time we
208 should clear out BB pointer of dead statements consistently. */
211 /* Connect E to E->src. */
216 vec_safe_push (e
->src
->succs
, e
);
217 df_mark_solutions_dirty ();
220 /* Connect E to E->dest. */
223 connect_dest (edge e
)
225 basic_block dest
= e
->dest
;
226 vec_safe_push (dest
->preds
, e
);
227 e
->dest_idx
= EDGE_COUNT (dest
->preds
) - 1;
228 df_mark_solutions_dirty ();
231 /* Disconnect edge E from E->src. */
234 disconnect_src (edge e
)
236 basic_block src
= e
->src
;
240 for (ei
= ei_start (src
->succs
); (tmp
= ei_safe_edge (ei
)); )
244 src
->succs
->unordered_remove (ei
.index
);
245 df_mark_solutions_dirty ();
255 /* Disconnect edge E from E->dest. */
258 disconnect_dest (edge e
)
260 basic_block dest
= e
->dest
;
261 unsigned int dest_idx
= e
->dest_idx
;
263 dest
->preds
->unordered_remove (dest_idx
);
265 /* If we removed an edge in the middle of the edge vector, we need
266 to update dest_idx of the edge that moved into the "hole". */
267 if (dest_idx
< EDGE_COUNT (dest
->preds
))
268 EDGE_PRED (dest
, dest_idx
)->dest_idx
= dest_idx
;
269 df_mark_solutions_dirty ();
272 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
273 created edge. Use this only if you are sure that this edge can't
274 possibly already exist. */
277 unchecked_make_edge (basic_block src
, basic_block dst
, int flags
)
280 e
= ggc_cleared_alloc
<edge_def
> ();
281 n_edges_for_fn (cfun
)++;
283 e
->probability
= profile_probability::uninitialized ();
291 execute_on_growing_pred (e
);
295 /* Create an edge connecting SRC and DST with FLAGS optionally using
296 edge cache CACHE. Return the new edge, NULL if already exist. */
299 cached_make_edge (sbitmap edge_cache
, basic_block src
, basic_block dst
, int flags
)
301 if (edge_cache
== NULL
302 || src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
303 || dst
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
304 return make_edge (src
, dst
, flags
);
306 /* Does the requested edge already exist? */
307 if (! bitmap_bit_p (edge_cache
, dst
->index
))
309 /* The edge does not exist. Create one and update the
311 bitmap_set_bit (edge_cache
, dst
->index
);
312 return unchecked_make_edge (src
, dst
, flags
);
315 /* At this point, we know that the requested edge exists. Adjust
316 flags if necessary. */
319 edge e
= find_edge (src
, dst
);
326 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
327 created edge or NULL if already exist. */
330 make_edge (basic_block src
, basic_block dest
, int flags
)
332 edge e
= find_edge (src
, dest
);
334 /* Make sure we don't add duplicate edges. */
341 return unchecked_make_edge (src
, dest
, flags
);
344 /* Create an edge connecting SRC to DEST and set probability by knowing
345 that it is the single edge leaving SRC. */
348 make_single_succ_edge (basic_block src
, basic_block dest
, int flags
)
350 edge e
= make_edge (src
, dest
, flags
);
352 e
->probability
= profile_probability::always ();
356 /* This function will remove an edge from the flow graph. */
359 remove_edge_raw (edge e
)
361 remove_predictions_associated_with_edge (e
);
362 execute_on_shrinking_pred (e
);
370 /* Redirect an edge's successor from one block to another. */
373 redirect_edge_succ (edge e
, basic_block new_succ
)
375 execute_on_shrinking_pred (e
);
381 /* Reconnect the edge to the new successor block. */
384 execute_on_growing_pred (e
);
387 /* Redirect an edge's predecessor from one block to another. */
390 redirect_edge_pred (edge e
, basic_block new_pred
)
396 /* Reconnect the edge to the new predecessor block. */
400 /* Clear all basic block flags that do not have to be preserved. */
402 clear_bb_flags (void)
405 int flags_to_preserve
= BB_FLAGS_TO_PRESERVE
;
407 && loops_state_satisfies_p (cfun
, LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
408 flags_to_preserve
|= BB_IRREDUCIBLE_LOOP
;
410 FOR_ALL_BB_FN (bb
, cfun
)
411 bb
->flags
&= flags_to_preserve
;
414 /* Check the consistency of profile information. We can't do that
415 in verify_flow_info, as the counts may get invalid for incompletely
416 solved graphs, later eliminating of conditionals or roundoff errors.
417 It is still practical to have them reported for debugging of simple
420 check_bb_profile (basic_block bb
, FILE * file
, int indent
)
424 struct function
*fun
= DECL_STRUCT_FUNCTION (current_function_decl
);
425 char *s_indent
= (char *) alloca ((size_t) indent
+ 1);
426 memset ((void *) s_indent
, ' ', (size_t) indent
);
427 s_indent
[indent
] = '\0';
429 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
432 if (bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
435 profile_probability sum
= profile_probability::never ();
438 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
440 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
442 sum
+= e
->probability
;
443 if (e
->probability
.initialized_p ())
444 isum
+= e
->probability
.to_reg_br_prob_base ();
446 /* Only report mismatches for non-EH control flow. If there are only EH
447 edges it means that the BB ends by noreturn call. Here the control
448 flow may just terminate. */
451 if (sum
.differs_from_p (profile_probability::always ()))
454 ";; %sInvalid sum of outgoing probabilities ",
457 fprintf (file
, "\n");
459 /* Probabilities caps to 100% and thus the previous test will never
460 fire if the sum of probabilities is too large. */
461 else if (isum
> REG_BR_PROB_BASE
+ 100)
464 ";; %sInvalid sum of outgoing probabilities %.1f%%\n",
465 s_indent
, isum
* 100.0 / REG_BR_PROB_BASE
);
469 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (fun
))
471 profile_count sum
= profile_count::zero ();
472 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
474 if (sum
.differs_from_p (bb
->count
))
476 fprintf (file
, ";; %sInvalid sum of incoming counts ",
478 sum
.dump (file
, fun
);
479 fprintf (file
, ", should be ");
480 bb
->count
.dump (file
, fun
);
481 fprintf (file
, "\n");
484 if (BB_PARTITION (bb
) == BB_COLD_PARTITION
)
486 /* Warn about inconsistencies in the partitioning that are
487 currently caused by profile insanities created via optimization. */
488 if (!probably_never_executed_bb_p (fun
, bb
))
489 fprintf (file
, ";; %sBlock in cold partition with hot count\n",
491 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
493 if (!probably_never_executed_edge_p (fun
, e
))
495 ";; %sBlock in cold partition with incoming hot edge\n",
502 dump_edge_info (FILE *file
, edge e
, dump_flags_t flags
, int do_succ
)
504 basic_block side
= (do_succ
? e
->dest
: e
->src
);
505 bool do_details
= false;
507 if ((flags
& TDF_DETAILS
) != 0
508 && (flags
& TDF_SLIM
) == 0)
511 if (side
->index
== ENTRY_BLOCK
)
512 fputs (" ENTRY", file
);
513 else if (side
->index
== EXIT_BLOCK
)
514 fputs (" EXIT", file
);
516 fprintf (file
, " %d", side
->index
);
518 if (e
->probability
.initialized_p () && do_details
)
520 fprintf (file
, " [");
521 e
->probability
.dump (file
);
522 fprintf (file
, "] ");
525 if (e
->count ().initialized_p () && do_details
)
527 fputs (" count:", file
);
528 e
->count ().dump (file
, cfun
);
531 if (e
->flags
&& do_details
)
533 static const char * const bitnames
[] =
535 #define DEF_EDGE_FLAG(NAME,IDX) #NAME ,
536 #include "cfg-flags.def"
541 int i
, flags
= e
->flags
;
543 gcc_assert (e
->flags
<= EDGE_ALL_FLAGS
);
545 for (i
= 0; flags
; i
++)
546 if (flags
& (1 << i
))
552 fputs (bitnames
[i
], file
);
559 if (do_details
&& LOCATION_LOCUS (e
->goto_locus
) > BUILTINS_LOCATION
)
560 fprintf (file
, " %s:%d:%d", LOCATION_FILE (e
->goto_locus
),
561 LOCATION_LINE (e
->goto_locus
), LOCATION_COLUMN (e
->goto_locus
));
565 debug (edge_def
&ref
)
567 fprintf (stderr
, "<edge (%d -> %d)>\n",
568 ref
.src
->index
, ref
.dest
->index
);
569 dump_edge_info (stderr
, &ref
, TDF_DETAILS
, false);
570 fprintf (stderr
, "\n");
574 debug (edge_def
*ptr
)
579 fprintf (stderr
, "<nil>\n");
585 fprintf (stderr
, "<edge 0x%p (%d -> %d)>", (void *) e
,
586 e
->src
->index
, e
->dest
->index
);
589 DEFINE_DEBUG_VEC (edge
)
590 DEFINE_DEBUG_HASH_SET (edge
)
592 /* Simple routines to easily allocate AUX fields of basic blocks. */
594 static struct obstack block_aux_obstack
;
595 static void *first_block_aux_obj
= 0;
596 static struct obstack edge_aux_obstack
;
597 static void *first_edge_aux_obj
= 0;
599 /* Allocate a memory block of SIZE as BB->aux. The obstack must
600 be first initialized by alloc_aux_for_blocks. */
603 alloc_aux_for_block (basic_block bb
, int size
)
605 /* Verify that aux field is clear. */
606 gcc_assert (!bb
->aux
&& first_block_aux_obj
);
607 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
608 memset (bb
->aux
, 0, size
);
611 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
612 alloc_aux_for_block for each basic block. */
615 alloc_aux_for_blocks (int size
)
617 static int initialized
;
621 gcc_obstack_init (&block_aux_obstack
);
625 /* Check whether AUX data are still allocated. */
626 gcc_assert (!first_block_aux_obj
);
628 first_block_aux_obj
= obstack_alloc (&block_aux_obstack
, 0);
633 FOR_ALL_BB_FN (bb
, cfun
)
634 alloc_aux_for_block (bb
, size
);
638 /* Clear AUX pointers of all blocks. */
641 clear_aux_for_blocks (void)
645 FOR_ALL_BB_FN (bb
, cfun
)
649 /* Free data allocated in block_aux_obstack and clear AUX pointers
653 free_aux_for_blocks (void)
655 gcc_assert (first_block_aux_obj
);
656 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
657 first_block_aux_obj
= NULL
;
659 clear_aux_for_blocks ();
662 /* Allocate a memory edge of SIZE as E->aux. The obstack must
663 be first initialized by alloc_aux_for_edges. */
666 alloc_aux_for_edge (edge e
, int size
)
668 /* Verify that aux field is clear. */
669 gcc_assert (!e
->aux
&& first_edge_aux_obj
);
670 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
671 memset (e
->aux
, 0, size
);
674 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
675 alloc_aux_for_edge for each basic edge. */
678 alloc_aux_for_edges (int size
)
680 static int initialized
;
684 gcc_obstack_init (&edge_aux_obstack
);
688 /* Check whether AUX data are still allocated. */
689 gcc_assert (!first_edge_aux_obj
);
691 first_edge_aux_obj
= obstack_alloc (&edge_aux_obstack
, 0);
696 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
697 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
702 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
703 alloc_aux_for_edge (e
, size
);
708 /* Clear AUX pointers of all edges. */
711 clear_aux_for_edges (void)
716 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
717 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
720 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
725 /* Free data allocated in edge_aux_obstack and clear AUX pointers
729 free_aux_for_edges (void)
731 gcc_assert (first_edge_aux_obj
);
732 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
733 first_edge_aux_obj
= NULL
;
735 clear_aux_for_edges ();
739 debug_bb (basic_block bb
)
741 debug_bb (bb
, dump_flags
);
744 DEBUG_FUNCTION basic_block
747 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, n
);
752 /* Print BB with specified FLAGS. */
755 debug_bb (basic_block bb
, dump_flags_t flags
)
757 dump_bb (stderr
, bb
, 0, flags
);
760 /* Print basic block numbered N with specified FLAGS. */
762 DEBUG_FUNCTION basic_block
763 debug_bb_n (int n
, dump_flags_t flags
)
765 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, n
);
766 debug_bb (bb
, flags
);
770 /* Dumps cfg related information about basic block BB to OUTF.
771 If HEADER is true, dump things that appear before the instructions
772 contained in BB. If FOOTER is true, dump things that appear after.
773 Flags are the TDF_* masks as documented in dumpfile.h.
774 NB: With TDF_DETAILS, it is assumed that cfun is available, so
775 that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE. */
778 dump_bb_info (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
,
779 bool do_header
, bool do_footer
)
783 static const char * const bb_bitnames
[] =
785 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) #NAME ,
786 #include "cfg-flags.def"
788 #undef DEF_BASIC_BLOCK_FLAG
790 const unsigned n_bitnames
= ARRAY_SIZE (bb_bitnames
);
792 char *s_indent
= (char *) alloca ((size_t) indent
+ 1);
793 memset ((void *) s_indent
, ' ', (size_t) indent
);
794 s_indent
[indent
] = '\0';
796 gcc_assert (bb
->flags
<= BB_ALL_FLAGS
);
803 fprintf (outf
, "%sbasic block %d, loop depth %d",
804 s_indent
, bb
->index
, bb_loop_depth (bb
));
805 if (flags
& TDF_DETAILS
)
807 struct function
*fun
= DECL_STRUCT_FUNCTION (current_function_decl
);
808 if (bb
->count
.initialized_p ())
810 fputs (", count ", outf
);
811 bb
->count
.dump (outf
, cfun
);
813 if (maybe_hot_bb_p (fun
, bb
))
814 fputs (", maybe hot", outf
);
815 if (probably_never_executed_bb_p (fun
, bb
))
816 fputs (", probably never executed", outf
);
820 if (flags
& TDF_DETAILS
)
822 check_bb_profile (bb
, outf
, indent
);
824 fprintf (outf
, "%s prev block ", s_indent
);
826 fprintf (outf
, "%d", bb
->prev_bb
->index
);
828 fprintf (outf
, "(nil)");
829 fprintf (outf
, ", next block ");
831 fprintf (outf
, "%d", bb
->next_bb
->index
);
833 fprintf (outf
, "(nil)");
835 fputs (", flags:", outf
);
837 for (i
= 0; i
< n_bitnames
; i
++)
838 if (bb
->flags
& (1 << i
))
845 fputs (bb_bitnames
[i
], outf
);
853 fprintf (outf
, "%s pred: ", s_indent
);
855 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
860 fprintf (outf
, "%s ", s_indent
);
863 dump_edge_info (outf
, e
, flags
, 0);
873 fprintf (outf
, "%s succ: ", s_indent
);
875 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
880 fprintf (outf
, "%s ", s_indent
);
883 dump_edge_info (outf
, e
, flags
, 1);
891 /* Dumps a brief description of cfg to FILE. */
894 brief_dump_cfg (FILE *file
, dump_flags_t flags
)
898 FOR_EACH_BB_FN (bb
, cfun
)
900 dump_bb_info (file
, bb
, 0, flags
& TDF_DETAILS
, true, true);
904 /* Set probability of E to NEW_PROB and rescale other edges
905 from E->src so their sum remains the same. */
908 set_edge_probability_and_rescale_others (edge e
, profile_probability new_prob
)
912 if (e
->probability
== new_prob
)
914 /* If we made E unconditional, drop other frequencies to 0. */
915 if (new_prob
== profile_probability::always ())
917 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
919 e2
->probability
= profile_probability::never ();
926 /* See how many other edges are leaving exit_edge->src. */
927 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
928 if (e2
!= e
&& !(e2
->flags
& EDGE_FAKE
))
933 /* If there is only one other edge with non-zero probability we do not
934 need to scale which drops quality of profile from precise
937 other_e
->probability
= new_prob
.invert ();
938 /* Nothing to do if there are no other edges. */
941 /* Do scaling if possible. */
942 else if (e
->probability
.invert ().nonzero_p ())
944 profile_probability num
= new_prob
.invert (),
945 den
= e
->probability
.invert ();
946 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
947 if (e2
!= e
&& !(e2
->flags
& EDGE_FAKE
))
948 e2
->probability
= e2
->probability
.apply_scale (num
, den
);
952 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
954 ";; probability of edge %i->%i set reduced from 1."
955 " The remaining edges are left inconsistent.\n",
956 e
->src
->index
, e
->dest
->index
);
957 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
958 if (e2
!= e
&& !(e2
->flags
& EDGE_FAKE
))
959 e2
->probability
= new_prob
.invert ().guessed () / n
;
962 e
->probability
= new_prob
;
965 /* An edge originally destinating BB of COUNT has been proved to
966 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
967 redirected to destination of TAKEN_EDGE.
969 This function may leave the profile inconsistent in the case TAKEN_EDGE
970 frequency or count is believed to be lower than COUNT
973 update_bb_profile_for_threading (basic_block bb
,
974 profile_count count
, edge taken_edge
)
976 gcc_assert (bb
== taken_edge
->src
);
978 /* If there is no profile or the threaded path is never executed
979 we don't need to upate. */
980 if (!bb
->count
.initialized_p ()
981 || count
== profile_count::zero ())
984 if (bb
->count
< count
)
987 fprintf (dump_file
, "bb %i count became negative after threading",
989 /* If probabilities looks very off, scale down and reduce to guesses
990 to avoid dropping the other path close to zero. */
991 if (bb
->count
< count
.apply_scale (7, 8))
992 count
= bb
->count
.apply_scale (1, 2).guessed ();
995 /* If bb->count will become zero, the probabilities on the original path
996 are not really known, but it is probably better to keep original ones
997 then try to invent something new. */
998 if (!(bb
->count
<= count
))
1000 profile_probability prob
;
1001 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
1002 Watch for overflows. */
1003 if (bb
->count
.nonzero_p ())
1004 prob
= count
.probability_in (bb
->count
);
1006 prob
= taken_edge
->probability
.apply_scale (1, 2).guessed ();
1007 if (prob
> taken_edge
->probability
)
1011 fprintf (dump_file
, "Jump threading proved that the probability "
1012 "of edge %i->%i was originally estimated too small. "
1014 taken_edge
->src
->index
, taken_edge
->dest
->index
);
1015 taken_edge
->probability
.dump (dump_file
);
1016 fprintf (dump_file
, " should be ");
1017 prob
.dump (dump_file
);
1018 fprintf (dump_file
, ")\n");
1020 prob
= taken_edge
->probability
.apply_scale (6, 8).guessed ();
1022 set_edge_probability_and_rescale_others (taken_edge
,
1023 (taken_edge
->probability
- prob
)
1029 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1030 by NUM/DEN, in profile_count arithmetic. More accurate than previous
1031 function but considerably slower. */
1033 scale_bbs_frequencies_profile_count (basic_block
*bbs
, int nbbs
,
1034 profile_count num
, profile_count den
)
1037 if (num
== profile_count::zero () || den
.nonzero_p ())
1038 for (i
= 0; i
< nbbs
; i
++)
1039 bbs
[i
]->count
= bbs
[i
]->count
.apply_scale (num
, den
);
1042 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1043 by NUM/DEN, in profile_count arithmetic. More accurate than previous
1044 function but considerably slower. */
1046 scale_bbs_frequencies (basic_block
*bbs
, int nbbs
,
1047 profile_probability p
)
1051 for (i
= 0; i
< nbbs
; i
++)
1052 bbs
[i
]->count
= bbs
[i
]->count
.apply_probability (p
);
1055 /* Data structures used to maintain mapping between basic blocks and
1057 typedef hash_map
<int_hash
<int, -1, -2>, int> copy_map_t
;
1058 static copy_map_t
*bb_original
;
1059 static copy_map_t
*bb_copy
;
1061 /* And between loops and copies. */
1062 static copy_map_t
*loop_copy
;
1064 /* Initialize the data structures to maintain mapping between blocks
1067 initialize_original_copy_tables (void)
1069 bb_original
= new copy_map_t (10);
1070 bb_copy
= new copy_map_t (10);
1071 loop_copy
= new copy_map_t (10);
1074 /* Reset the data structures to maintain mapping between blocks and
1078 reset_original_copy_tables (void)
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)
1098 /* Return true iff we have had a call to initialize_original_copy_tables
1099 without a corresponding call to free_original_copy_tables. */
1102 original_copy_tables_initialized_p (void)
1104 return bb_copy
!= NULL
;
1107 /* Removes the value associated with OBJ from table TAB. */
1110 copy_original_table_clear (copy_map_t
*tab
, unsigned obj
)
1112 if (!original_copy_tables_initialized_p ())
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 (copy_map_t
*tab
,
1123 unsigned obj
, unsigned val
)
1125 if (!original_copy_tables_initialized_p ())
1128 tab
->put (obj
, val
);
1131 /* Set original for basic block. Do nothing when data structures are not
1132 initialized so passes not needing this don't need to care. */
1134 set_bb_original (basic_block bb
, basic_block original
)
1136 copy_original_table_set (bb_original
, bb
->index
, original
->index
);
1139 /* Get the original basic block. */
1141 get_bb_original (basic_block bb
)
1143 gcc_assert (original_copy_tables_initialized_p ());
1145 int *entry
= bb_original
->get (bb
->index
);
1147 return BASIC_BLOCK_FOR_FN (cfun
, *entry
);
1152 /* Set copy for basic block. Do nothing when data structures are not
1153 initialized so passes not needing this don't need to care. */
1155 set_bb_copy (basic_block bb
, basic_block copy
)
1157 copy_original_table_set (bb_copy
, bb
->index
, copy
->index
);
1160 /* Get the copy of basic block. */
1162 get_bb_copy (basic_block bb
)
1164 gcc_assert (original_copy_tables_initialized_p ());
1166 int *entry
= bb_copy
->get (bb
->index
);
1168 return BASIC_BLOCK_FOR_FN (cfun
, *entry
);
1173 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1174 initialized so passes not needing this don't need to care. */
1177 set_loop_copy (class loop
*loop
, class loop
*copy
)
1180 copy_original_table_clear (loop_copy
, loop
->num
);
1182 copy_original_table_set (loop_copy
, loop
->num
, copy
->num
);
1185 /* Get the copy of LOOP. */
1188 get_loop_copy (class loop
*loop
)
1190 gcc_assert (original_copy_tables_initialized_p ());
1192 int *entry
= loop_copy
->get (loop
->num
);
1194 return get_loop (cfun
, *entry
);
1199 /* Scales the frequencies of all basic blocks that are strictly
1200 dominated by BB by NUM/DEN. */
1203 scale_strictly_dominated_blocks (basic_block bb
,
1204 profile_count num
, profile_count den
)
1208 if (!den
.nonzero_p () && !(num
== profile_count::zero ()))
1210 auto_vec
<basic_block
, 8> worklist
;
1211 worklist
.safe_push (bb
);
1213 while (!worklist
.is_empty ())
1214 for (son
= first_dom_son (CDI_DOMINATORS
, worklist
.pop ());
1216 son
= next_dom_son (CDI_DOMINATORS
, son
))
1218 son
->count
= son
->count
.apply_scale (num
, den
);
1219 worklist
.safe_push (son
);