1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file contains low level functions to manipulate the CFG and
23 analyze it. All other modules should not transform the data structure
24 directly and use abstraction instead. The file is supposed to be
25 ordered bottom-up and should not contain any code dependent on a
26 particular intermediate language (RTL or trees).
28 Available functionality:
29 - Initialization/deallocation
30 init_flow, clear_edges
31 - Low level basic block manipulation
32 alloc_block, expunge_block
34 make_edge, make_single_succ_edge, cached_make_edge, remove_edge
35 - Low level edge redirection (without updating instruction chain)
36 redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
37 - Dumping and debugging
38 dump_flow_info, debug_flow_info, dump_edge_info
39 - Allocation of AUX fields for basic blocks
40 alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
42 - Consistency checking
44 - Dumping and debugging
45 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
50 #include "coretypes.h"
54 #include "hard-reg-set.h"
60 #include "diagnostic-core.h"
64 #include "tree-pass.h"
67 #include "alloc-pool.h"
70 #include "tree-flow.h"
72 /* The obstack on which the flow graph components are allocated. */
74 struct bitmap_obstack reg_obstack
;
76 void debug_flow_info (void);
77 static void free_edge (edge
);
79 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
81 /* Called once at initialization time. */
84 init_flow (struct function
*the_fun
)
87 the_fun
->cfg
= ggc_alloc_cleared_control_flow_graph ();
88 n_edges_for_function (the_fun
) = 0;
89 ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun
)
90 = ggc_alloc_cleared_basic_block_def ();
91 ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun
)->index
= ENTRY_BLOCK
;
92 EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun
)
93 = ggc_alloc_cleared_basic_block_def ();
94 EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun
)->index
= EXIT_BLOCK
;
95 ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun
)->next_bb
96 = EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun
);
97 EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun
)->prev_bb
98 = ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun
);
101 /* Helper function for remove_edge and clear_edges. Frees edge structure
102 without actually unlinking it from the pred/succ lists. */
105 free_edge (edge e ATTRIBUTE_UNUSED
)
111 /* Free the memory associated with the edge structures. */
122 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
124 VEC_truncate (edge
, bb
->succs
, 0);
125 VEC_truncate (edge
, bb
->preds
, 0);
128 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
130 VEC_truncate (edge
, EXIT_BLOCK_PTR
->preds
, 0);
131 VEC_truncate (edge
, ENTRY_BLOCK_PTR
->succs
, 0);
133 gcc_assert (!n_edges
);
136 /* Allocate memory for basic_block. */
142 bb
= ggc_alloc_cleared_basic_block_def ();
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 (ENTRY_BLOCK
, ENTRY_BLOCK_PTR
);
173 SET_BASIC_BLOCK (EXIT_BLOCK
, EXIT_BLOCK_PTR
);
176 df_compact_blocks ();
181 i
= NUM_FIXED_BLOCKS
;
184 SET_BASIC_BLOCK (i
, bb
);
188 gcc_assert (i
== n_basic_blocks
);
190 for (; i
< last_basic_block
; i
++)
191 SET_BASIC_BLOCK (i
, NULL
);
193 last_basic_block
= n_basic_blocks
;
196 /* Remove block B from the basic block array. */
199 expunge_block (basic_block b
)
202 SET_BASIC_BLOCK (b
->index
, NULL
);
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 should
208 clear out BB pointer of dead statements consistently. */
211 /* Connect E to E->src. */
216 VEC_safe_push (edge
, gc
, 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 (edge
, gc
, 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 VEC_unordered_remove (edge
, src
->succs
, ei
.index
);
251 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 VEC_unordered_remove (edge
, dest
->preds
, 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_alloc_cleared_edge_def ();
290 execute_on_growing_pred (e
);
294 /* Create an edge connecting SRC and DST with FLAGS optionally using
295 edge cache CACHE. Return the new edge, NULL if already exist. */
298 cached_make_edge (sbitmap edge_cache
, basic_block src
, basic_block dst
, int flags
)
300 if (edge_cache
== NULL
301 || src
== ENTRY_BLOCK_PTR
302 || dst
== EXIT_BLOCK_PTR
)
303 return make_edge (src
, dst
, flags
);
305 /* Does the requested edge already exist? */
306 if (! TEST_BIT (edge_cache
, dst
->index
))
308 /* The edge does not exist. Create one and update the
310 SET_BIT (edge_cache
, dst
->index
);
311 return unchecked_make_edge (src
, dst
, flags
);
314 /* At this point, we know that the requested edge exists. Adjust
315 flags if necessary. */
318 edge e
= find_edge (src
, dst
);
325 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
326 created edge or NULL if already exist. */
329 make_edge (basic_block src
, basic_block dest
, int flags
)
331 edge e
= find_edge (src
, dest
);
333 /* Make sure we don't add duplicate edges. */
340 return unchecked_make_edge (src
, dest
, flags
);
343 /* Create an edge connecting SRC to DEST and set probability by knowing
344 that it is the single edge leaving SRC. */
347 make_single_succ_edge (basic_block src
, basic_block dest
, int flags
)
349 edge e
= make_edge (src
, dest
, flags
);
351 e
->probability
= REG_BR_PROB_BASE
;
352 e
->count
= src
->count
;
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
);
367 /* This is probably not needed, but it doesn't hurt. */
368 redirect_edge_var_map_clear (e
);
373 /* Redirect an edge's successor from one block to another. */
376 redirect_edge_succ (edge e
, basic_block new_succ
)
378 execute_on_shrinking_pred (e
);
384 /* Reconnect the edge to the new successor block. */
387 execute_on_growing_pred (e
);
390 /* Like previous but avoid possible duplicate edge. */
393 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
397 s
= find_edge (e
->src
, new_succ
);
400 s
->flags
|= e
->flags
;
401 s
->probability
+= e
->probability
;
402 if (s
->probability
> REG_BR_PROB_BASE
)
403 s
->probability
= REG_BR_PROB_BASE
;
404 s
->count
+= e
->count
;
405 redirect_edge_var_map_dup (s
, e
);
410 redirect_edge_succ (e
, new_succ
);
415 /* Redirect an edge's predecessor from one block to another. */
418 redirect_edge_pred (edge e
, basic_block new_pred
)
424 /* Reconnect the edge to the new predecessor block. */
428 /* Clear all basic block flags, with the exception of partitioning and
431 clear_bb_flags (void)
435 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
436 bb
->flags
= (BB_PARTITION (bb
)
437 | (bb
->flags
& (BB_DISABLE_SCHEDULE
+ BB_RTL
+ BB_NON_LOCAL_GOTO_TARGET
)));
440 /* Check the consistency of profile information. We can't do that
441 in verify_flow_info, as the counts may get invalid for incompletely
442 solved graphs, later eliminating of conditionals or roundoff errors.
443 It is still practical to have them reported for debugging of simple
446 check_bb_profile (basic_block bb
, FILE * file
)
453 if (profile_status
== PROFILE_ABSENT
)
456 if (bb
!= EXIT_BLOCK_PTR
)
458 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
459 sum
+= e
->probability
;
460 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
461 fprintf (file
, "Invalid sum of outgoing probabilities %.1f%%\n",
462 sum
* 100.0 / REG_BR_PROB_BASE
);
464 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
466 if (EDGE_COUNT (bb
->succs
)
467 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
468 fprintf (file
, "Invalid sum of outgoing counts %i, should be %i\n",
469 (int) lsum
, (int) bb
->count
);
471 if (bb
!= ENTRY_BLOCK_PTR
)
474 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
475 sum
+= EDGE_FREQUENCY (e
);
476 if (abs (sum
- bb
->frequency
) > 100)
478 "Invalid sum of incoming frequencies %i, should be %i\n",
481 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
483 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
484 fprintf (file
, "Invalid sum of incoming counts %i, should be %i\n",
485 (int) lsum
, (int) bb
->count
);
489 /* Write information about registers and basic blocks into FILE.
490 This is part of making a debugging dump. */
493 dump_regset (regset r
, FILE *outf
)
496 reg_set_iterator rsi
;
500 fputs (" (nil)", outf
);
504 EXECUTE_IF_SET_IN_REG_SET (r
, 0, i
, rsi
)
506 fprintf (outf
, " %d", i
);
507 if (i
< FIRST_PSEUDO_REGISTER
)
508 fprintf (outf
, " [%s]",
513 /* Print a human-readable representation of R on the standard error
514 stream. This function is designed to be used from within the
518 debug_regset (regset r
)
520 dump_regset (r
, stderr
);
524 /* Emit basic block information for BB. HEADER is true if the user wants
525 the generic information and the predecessors, FOOTER is true if they want
526 the successors. FLAGS is the dump flags of interest; TDF_DETAILS emit
527 global register liveness information. PREFIX is put in front of every
528 line. The output is emitted to FILE. */
530 dump_bb_info (basic_block bb
, bool header
, bool footer
, int flags
,
531 const char *prefix
, FILE *file
)
538 fprintf (file
, "\n%sBasic block %d ", prefix
, bb
->index
);
540 fprintf (file
, ", prev %d", bb
->prev_bb
->index
);
542 fprintf (file
, ", next %d", bb
->next_bb
->index
);
543 fprintf (file
, ", loop_depth %d, count ", bb
->loop_depth
);
544 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
545 fprintf (file
, ", freq %i", bb
->frequency
);
546 /* Both maybe_hot_bb_p & probably_never_executed_bb_p functions
547 crash without cfun. */
548 if (cfun
&& maybe_hot_bb_p (bb
))
549 fputs (", maybe hot", file
);
550 if (cfun
&& probably_never_executed_bb_p (bb
))
551 fputs (", probably never executed", file
);
554 static const char * const bits
[] = {
555 "new", "reachable", "irr_loop", "superblock", "disable_sched",
556 "hot_partition", "cold_partition", "duplicated",
557 "non_local_goto_target", "rtl", "forwarder", "nonthreadable",
562 fputs (", flags:", file
);
563 for (flags
= bb
->flags
; flags
; flags
&= flags
- 1)
565 unsigned i
= ctz_hwi (flags
);
566 if (i
< ARRAY_SIZE (bits
))
567 fprintf (file
, " %s", bits
[i
]);
569 fprintf (file
, " <%d>", i
);
574 fprintf (file
, "%sPredecessors: ", prefix
);
575 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
576 dump_edge_info (file
, e
, 0);
578 if ((flags
& TDF_DETAILS
)
579 && (bb
->flags
& BB_RTL
)
583 df_dump_top (bb
, file
);
589 fprintf (file
, "\n%sSuccessors: ", prefix
);
590 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
591 dump_edge_info (file
, e
, 1);
593 if ((flags
& TDF_DETAILS
)
594 && (bb
->flags
& BB_RTL
)
598 df_dump_bottom (bb
, file
);
605 /* Dump the register info to FILE. */
608 dump_reg_info (FILE *file
)
610 unsigned int i
, max
= max_reg_num ();
611 if (reload_completed
)
614 if (reg_info_p_size
< max
)
615 max
= reg_info_p_size
;
617 fprintf (file
, "%d registers.\n", max
);
618 for (i
= FIRST_PSEUDO_REGISTER
; i
< max
; i
++)
620 enum reg_class rclass
, altclass
;
622 if (regstat_n_sets_and_refs
)
623 fprintf (file
, "\nRegister %d used %d times across %d insns",
624 i
, REG_N_REFS (i
), REG_LIVE_LENGTH (i
));
626 fprintf (file
, "\nRegister %d used %d times across %d insns",
627 i
, DF_REG_USE_COUNT (i
) + DF_REG_DEF_COUNT (i
), REG_LIVE_LENGTH (i
));
629 if (REG_BASIC_BLOCK (i
) >= NUM_FIXED_BLOCKS
)
630 fprintf (file
, " in block %d", REG_BASIC_BLOCK (i
));
631 if (regstat_n_sets_and_refs
)
632 fprintf (file
, "; set %d time%s", REG_N_SETS (i
),
633 (REG_N_SETS (i
) == 1) ? "" : "s");
635 fprintf (file
, "; set %d time%s", DF_REG_DEF_COUNT (i
),
636 (DF_REG_DEF_COUNT (i
) == 1) ? "" : "s");
637 if (regno_reg_rtx
[i
] != NULL
&& REG_USERVAR_P (regno_reg_rtx
[i
]))
638 fputs ("; user var", file
);
639 if (REG_N_DEATHS (i
) != 1)
640 fprintf (file
, "; dies in %d places", REG_N_DEATHS (i
));
641 if (REG_N_CALLS_CROSSED (i
) == 1)
642 fputs ("; crosses 1 call", file
);
643 else if (REG_N_CALLS_CROSSED (i
))
644 fprintf (file
, "; crosses %d calls", REG_N_CALLS_CROSSED (i
));
645 if (REG_FREQ_CALLS_CROSSED (i
))
646 fprintf (file
, "; crosses call with %d frequency", REG_FREQ_CALLS_CROSSED (i
));
647 if (regno_reg_rtx
[i
] != NULL
648 && PSEUDO_REGNO_BYTES (i
) != UNITS_PER_WORD
)
649 fprintf (file
, "; %d bytes", PSEUDO_REGNO_BYTES (i
));
651 rclass
= reg_preferred_class (i
);
652 altclass
= reg_alternate_class (i
);
653 if (rclass
!= GENERAL_REGS
|| altclass
!= ALL_REGS
)
655 if (altclass
== ALL_REGS
|| rclass
== ALL_REGS
)
656 fprintf (file
, "; pref %s", reg_class_names
[(int) rclass
]);
657 else if (altclass
== NO_REGS
)
658 fprintf (file
, "; %s or none", reg_class_names
[(int) rclass
]);
660 fprintf (file
, "; pref %s, else %s",
661 reg_class_names
[(int) rclass
],
662 reg_class_names
[(int) altclass
]);
665 if (regno_reg_rtx
[i
] != NULL
&& REG_POINTER (regno_reg_rtx
[i
]))
666 fputs ("; pointer", file
);
673 dump_flow_info (FILE *file
, int flags
)
677 /* There are no pseudo registers after reload. Don't dump them. */
678 if (reg_info_p_size
&& (flags
& TDF_DETAILS
) != 0)
679 dump_reg_info (file
);
681 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks
, n_edges
);
684 dump_bb_info (bb
, true, true, flags
, "", file
);
685 check_bb_profile (bb
, file
);
692 debug_flow_info (void)
694 dump_flow_info (stderr
, TDF_DETAILS
);
698 dump_edge_info (FILE *file
, edge e
, int do_succ
)
700 basic_block side
= (do_succ
? e
->dest
: e
->src
);
701 /* both ENTRY_BLOCK_PTR & EXIT_BLOCK_PTR depend upon cfun. */
702 if (cfun
&& side
== ENTRY_BLOCK_PTR
)
703 fputs (" ENTRY", file
);
704 else if (cfun
&& side
== EXIT_BLOCK_PTR
)
705 fputs (" EXIT", file
);
707 fprintf (file
, " %d", side
->index
);
710 fprintf (file
, " [%.1f%%] ", e
->probability
* 100.0 / REG_BR_PROB_BASE
);
714 fputs (" count:", file
);
715 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
720 static const char * const bitnames
[] = {
721 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
722 "can_fallthru", "irreducible", "sibcall", "loop_exit",
723 "true", "false", "exec"
726 int i
, flags
= e
->flags
;
729 for (i
= 0; flags
; i
++)
730 if (flags
& (1 << i
))
736 if (i
< (int) ARRAY_SIZE (bitnames
))
737 fputs (bitnames
[i
], file
);
739 fprintf (file
, "%d", i
);
747 /* Simple routines to easily allocate AUX fields of basic blocks. */
749 static struct obstack block_aux_obstack
;
750 static void *first_block_aux_obj
= 0;
751 static struct obstack edge_aux_obstack
;
752 static void *first_edge_aux_obj
= 0;
754 /* Allocate a memory block of SIZE as BB->aux. The obstack must
755 be first initialized by alloc_aux_for_blocks. */
758 alloc_aux_for_block (basic_block bb
, int size
)
760 /* Verify that aux field is clear. */
761 gcc_assert (!bb
->aux
&& first_block_aux_obj
);
762 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
763 memset (bb
->aux
, 0, size
);
766 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
767 alloc_aux_for_block for each basic block. */
770 alloc_aux_for_blocks (int size
)
772 static int initialized
;
776 gcc_obstack_init (&block_aux_obstack
);
780 /* Check whether AUX data are still allocated. */
781 gcc_assert (!first_block_aux_obj
);
783 first_block_aux_obj
= obstack_alloc (&block_aux_obstack
, 0);
789 alloc_aux_for_block (bb
, size
);
793 /* Clear AUX pointers of all blocks. */
796 clear_aux_for_blocks (void)
804 /* Free data allocated in block_aux_obstack and clear AUX pointers
808 free_aux_for_blocks (void)
810 gcc_assert (first_block_aux_obj
);
811 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
812 first_block_aux_obj
= NULL
;
814 clear_aux_for_blocks ();
817 /* Allocate a memory edge of SIZE as BB->aux. The obstack must
818 be first initialized by alloc_aux_for_edges. */
821 alloc_aux_for_edge (edge e
, int size
)
823 /* Verify that aux field is clear. */
824 gcc_assert (!e
->aux
&& first_edge_aux_obj
);
825 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
826 memset (e
->aux
, 0, size
);
829 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
830 alloc_aux_for_edge for each basic edge. */
833 alloc_aux_for_edges (int size
)
835 static int initialized
;
839 gcc_obstack_init (&edge_aux_obstack
);
843 /* Check whether AUX data are still allocated. */
844 gcc_assert (!first_edge_aux_obj
);
846 first_edge_aux_obj
= obstack_alloc (&edge_aux_obstack
, 0);
851 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
856 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
857 alloc_aux_for_edge (e
, size
);
862 /* Clear AUX pointers of all edges. */
865 clear_aux_for_edges (void)
870 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
873 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
878 /* Free data allocated in edge_aux_obstack and clear AUX pointers
882 free_aux_for_edges (void)
884 gcc_assert (first_edge_aux_obj
);
885 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
886 first_edge_aux_obj
= NULL
;
888 clear_aux_for_edges ();
892 debug_bb (basic_block bb
)
894 dump_bb (bb
, stderr
, 0);
897 DEBUG_FUNCTION basic_block
900 basic_block bb
= BASIC_BLOCK (n
);
901 dump_bb (bb
, stderr
, 0);
905 /* Dumps cfg related information about basic block BB to FILE. */
908 dump_cfg_bb_info (FILE *file
, basic_block bb
)
913 static const char * const bb_bitnames
[] =
915 "new", "reachable", "irreducible_loop", "superblock",
916 "nosched", "hot", "cold", "dup", "xlabel", "rtl",
919 const unsigned n_bitnames
= sizeof (bb_bitnames
) / sizeof (char *);
922 fprintf (file
, "Basic block %d", bb
->index
);
923 for (i
= 0; i
< n_bitnames
; i
++)
924 if (bb
->flags
& (1 << i
))
931 fputs (bb_bitnames
[i
], file
);
937 fputs ("Predecessors: ", file
);
938 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
939 dump_edge_info (file
, e
, 0);
941 fprintf (file
, "\nSuccessors: ");
942 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
943 dump_edge_info (file
, e
, 1);
944 fputs ("\n\n", file
);
947 /* Dumps a brief description of cfg to FILE. */
950 brief_dump_cfg (FILE *file
)
956 dump_cfg_bb_info (file
, bb
);
960 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
961 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
962 redirected to destination of TAKEN_EDGE.
964 This function may leave the profile inconsistent in the case TAKEN_EDGE
965 frequency or count is believed to be lower than FREQUENCY or COUNT
968 update_bb_profile_for_threading (basic_block bb
, int edge_frequency
,
969 gcov_type count
, edge taken_edge
)
979 fprintf (dump_file
, "bb %i count became negative after threading",
984 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
985 Watch for overflows. */
987 prob
= edge_frequency
* REG_BR_PROB_BASE
/ bb
->frequency
;
990 if (prob
> taken_edge
->probability
)
993 fprintf (dump_file
, "Jump threading proved probability of edge "
994 "%i->%i too small (it is %i, should be %i).\n",
995 taken_edge
->src
->index
, taken_edge
->dest
->index
,
996 taken_edge
->probability
, prob
);
997 prob
= taken_edge
->probability
;
1000 /* Now rescale the probabilities. */
1001 taken_edge
->probability
-= prob
;
1002 prob
= REG_BR_PROB_BASE
- prob
;
1003 bb
->frequency
-= edge_frequency
;
1004 if (bb
->frequency
< 0)
1009 fprintf (dump_file
, "Edge frequencies of bb %i has been reset, "
1010 "frequency of block should end up being 0, it is %i\n",
1011 bb
->index
, bb
->frequency
);
1012 EDGE_SUCC (bb
, 0)->probability
= REG_BR_PROB_BASE
;
1013 ei
= ei_start (bb
->succs
);
1015 for (; (c
= ei_safe_edge (ei
)); ei_next (&ei
))
1018 else if (prob
!= REG_BR_PROB_BASE
)
1020 int scale
= RDIV (65536 * REG_BR_PROB_BASE
, prob
);
1022 FOR_EACH_EDGE (c
, ei
, bb
->succs
)
1024 /* Protect from overflow due to additional scaling. */
1025 if (c
->probability
> prob
)
1026 c
->probability
= REG_BR_PROB_BASE
;
1029 c
->probability
= RDIV (c
->probability
* scale
, 65536);
1030 if (c
->probability
> REG_BR_PROB_BASE
)
1031 c
->probability
= REG_BR_PROB_BASE
;
1036 gcc_assert (bb
== taken_edge
->src
);
1037 taken_edge
->count
-= count
;
1038 if (taken_edge
->count
< 0)
1041 fprintf (dump_file
, "edge %i->%i count became negative after threading",
1042 taken_edge
->src
->index
, taken_edge
->dest
->index
);
1043 taken_edge
->count
= 0;
1047 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1048 by NUM/DEN, in int arithmetic. May lose some accuracy. */
1050 scale_bbs_frequencies_int (basic_block
*bbs
, int nbbs
, int num
, int den
)
1057 /* Scale NUM and DEN to avoid overflows. Frequencies are in order of
1058 10^4, if we make DEN <= 10^3, we can afford to upscale by 100
1059 and still safely fit in int during calculations. */
1065 num
= RDIV (1000 * num
, den
);
1068 if (num
> 100 * den
)
1071 for (i
= 0; i
< nbbs
; i
++)
1074 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
1075 /* Make sure the frequencies do not grow over BB_FREQ_MAX. */
1076 if (bbs
[i
]->frequency
> BB_FREQ_MAX
)
1077 bbs
[i
]->frequency
= BB_FREQ_MAX
;
1078 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
1079 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1080 e
->count
= RDIV (e
->count
* num
, den
);
1084 /* numbers smaller than this value are safe to multiply without getting
1086 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
1088 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1089 by NUM/DEN, in gcov_type arithmetic. More accurate than previous
1090 function but considerably slower. */
1092 scale_bbs_frequencies_gcov_type (basic_block
*bbs
, int nbbs
, gcov_type num
,
1097 gcov_type fraction
= RDIV (num
* 65536, den
);
1099 gcc_assert (fraction
>= 0);
1101 if (num
< MAX_SAFE_MULTIPLIER
)
1102 for (i
= 0; i
< nbbs
; i
++)
1105 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
1106 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
1107 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* num
, den
);
1109 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
1110 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1111 if (bbs
[i
]->count
<= MAX_SAFE_MULTIPLIER
)
1112 e
->count
= RDIV (e
->count
* num
, den
);
1114 e
->count
= RDIV (e
->count
* fraction
, 65536);
1117 for (i
= 0; i
< nbbs
; i
++)
1120 if (sizeof (gcov_type
) > sizeof (int))
1121 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* num
, den
);
1123 bbs
[i
]->frequency
= RDIV (bbs
[i
]->frequency
* fraction
, 65536);
1124 bbs
[i
]->count
= RDIV (bbs
[i
]->count
* fraction
, 65536);
1125 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1126 e
->count
= RDIV (e
->count
* fraction
, 65536);
1130 /* Data structures used to maintain mapping between basic blocks and
1132 static htab_t bb_original
;
1133 static htab_t bb_copy
;
1135 /* And between loops and copies. */
1136 static htab_t loop_copy
;
1137 static alloc_pool original_copy_bb_pool
;
1139 struct htab_bb_copy_original_entry
1141 /* Block we are attaching info to. */
1143 /* Index of original or copy (depending on the hashtable) */
1148 bb_copy_original_hash (const void *p
)
1150 const struct htab_bb_copy_original_entry
*data
1151 = ((const struct htab_bb_copy_original_entry
*)p
);
1153 return data
->index1
;
1156 bb_copy_original_eq (const void *p
, const void *q
)
1158 const struct htab_bb_copy_original_entry
*data
1159 = ((const struct htab_bb_copy_original_entry
*)p
);
1160 const struct htab_bb_copy_original_entry
*data2
1161 = ((const struct htab_bb_copy_original_entry
*)q
);
1163 return data
->index1
== data2
->index1
;
1166 /* Initialize the data structures to maintain mapping between blocks
1169 initialize_original_copy_tables (void)
1171 gcc_assert (!original_copy_bb_pool
);
1172 original_copy_bb_pool
1173 = create_alloc_pool ("original_copy",
1174 sizeof (struct htab_bb_copy_original_entry
), 10);
1175 bb_original
= htab_create (10, bb_copy_original_hash
,
1176 bb_copy_original_eq
, NULL
);
1177 bb_copy
= htab_create (10, bb_copy_original_hash
, bb_copy_original_eq
, NULL
);
1178 loop_copy
= htab_create (10, bb_copy_original_hash
, bb_copy_original_eq
, NULL
);
1181 /* Free the data structures to maintain mapping between blocks and
1184 free_original_copy_tables (void)
1186 gcc_assert (original_copy_bb_pool
);
1187 htab_delete (bb_copy
);
1188 htab_delete (bb_original
);
1189 htab_delete (loop_copy
);
1190 free_alloc_pool (original_copy_bb_pool
);
1194 original_copy_bb_pool
= NULL
;
1197 /* Removes the value associated with OBJ from table TAB. */
1200 copy_original_table_clear (htab_t tab
, unsigned obj
)
1203 struct htab_bb_copy_original_entry key
, *elt
;
1205 if (!original_copy_bb_pool
)
1209 slot
= htab_find_slot (tab
, &key
, NO_INSERT
);
1213 elt
= (struct htab_bb_copy_original_entry
*) *slot
;
1214 htab_clear_slot (tab
, slot
);
1215 pool_free (original_copy_bb_pool
, elt
);
1218 /* Sets the value associated with OBJ in table TAB to VAL.
1219 Do nothing when data structures are not initialized. */
1222 copy_original_table_set (htab_t tab
, unsigned obj
, unsigned val
)
1224 struct htab_bb_copy_original_entry
**slot
;
1225 struct htab_bb_copy_original_entry key
;
1227 if (!original_copy_bb_pool
)
1231 slot
= (struct htab_bb_copy_original_entry
**)
1232 htab_find_slot (tab
, &key
, INSERT
);
1235 *slot
= (struct htab_bb_copy_original_entry
*)
1236 pool_alloc (original_copy_bb_pool
);
1237 (*slot
)->index1
= obj
;
1239 (*slot
)->index2
= val
;
1242 /* Set original for basic block. Do nothing when data structures are not
1243 initialized so passes not needing this don't need to care. */
1245 set_bb_original (basic_block bb
, basic_block original
)
1247 copy_original_table_set (bb_original
, bb
->index
, original
->index
);
1250 /* Get the original basic block. */
1252 get_bb_original (basic_block bb
)
1254 struct htab_bb_copy_original_entry
*entry
;
1255 struct htab_bb_copy_original_entry key
;
1257 gcc_assert (original_copy_bb_pool
);
1259 key
.index1
= bb
->index
;
1260 entry
= (struct htab_bb_copy_original_entry
*) htab_find (bb_original
, &key
);
1262 return BASIC_BLOCK (entry
->index2
);
1267 /* Set copy for basic block. Do nothing when data structures are not
1268 initialized so passes not needing this don't need to care. */
1270 set_bb_copy (basic_block bb
, basic_block copy
)
1272 copy_original_table_set (bb_copy
, bb
->index
, copy
->index
);
1275 /* Get the copy of basic block. */
1277 get_bb_copy (basic_block bb
)
1279 struct htab_bb_copy_original_entry
*entry
;
1280 struct htab_bb_copy_original_entry key
;
1282 gcc_assert (original_copy_bb_pool
);
1284 key
.index1
= bb
->index
;
1285 entry
= (struct htab_bb_copy_original_entry
*) htab_find (bb_copy
, &key
);
1287 return BASIC_BLOCK (entry
->index2
);
1292 /* Set copy for LOOP to COPY. Do nothing when data structures are not
1293 initialized so passes not needing this don't need to care. */
1296 set_loop_copy (struct loop
*loop
, struct loop
*copy
)
1299 copy_original_table_clear (loop_copy
, loop
->num
);
1301 copy_original_table_set (loop_copy
, loop
->num
, copy
->num
);
1304 /* Get the copy of LOOP. */
1307 get_loop_copy (struct loop
*loop
)
1309 struct htab_bb_copy_original_entry
*entry
;
1310 struct htab_bb_copy_original_entry key
;
1312 gcc_assert (original_copy_bb_pool
);
1314 key
.index1
= loop
->num
;
1315 entry
= (struct htab_bb_copy_original_entry
*) htab_find (loop_copy
, &key
);
1317 return get_loop (entry
->index2
);