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 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
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"
55 #include "basic-block.h"
64 #include "alloc-pool.h"
68 /* The obstack on which the flow graph components are allocated. */
70 struct obstack flow_obstack
;
71 static char *flow_firstobj
;
73 /* Number of basic blocks in the current function. */
77 /* First free basic block number. */
81 /* Number of edges in the current function. */
85 /* The basic block array. */
87 varray_type basic_block_info
;
89 /* The special entry and exit blocks. */
90 basic_block ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
;
92 /* Memory alloc pool for bb member rbi. */
95 void debug_flow_info (void);
96 static void free_edge (edge
);
98 /* Indicate the presence of the profile. */
99 enum profile_status profile_status
;
101 /* Called once at initialization time. */
106 static int initialized
;
112 gcc_obstack_init (&flow_obstack
);
113 flow_firstobj
= obstack_alloc (&flow_obstack
, 0);
118 obstack_free (&flow_obstack
, flow_firstobj
);
119 flow_firstobj
= obstack_alloc (&flow_obstack
, 0);
122 ENTRY_BLOCK_PTR
= ggc_alloc_cleared (sizeof (*ENTRY_BLOCK_PTR
));
123 ENTRY_BLOCK_PTR
->index
= ENTRY_BLOCK
;
124 EXIT_BLOCK_PTR
= ggc_alloc_cleared (sizeof (*EXIT_BLOCK_PTR
));
125 EXIT_BLOCK_PTR
->index
= EXIT_BLOCK
;
126 ENTRY_BLOCK_PTR
->next_bb
= EXIT_BLOCK_PTR
;
127 EXIT_BLOCK_PTR
->prev_bb
= ENTRY_BLOCK_PTR
;
130 /* Helper function for remove_edge and clear_edges. Frees edge structure
131 without actually unlinking it from the pred/succ lists. */
134 free_edge (edge e ATTRIBUTE_UNUSED
)
140 /* Free the memory associated with the edge structures. */
151 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
153 VEC_truncate (edge
, bb
->succs
, 0);
154 VEC_truncate (edge
, bb
->preds
, 0);
157 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
159 VEC_truncate (edge
, EXIT_BLOCK_PTR
->preds
, 0);
160 VEC_truncate (edge
, ENTRY_BLOCK_PTR
->succs
, 0);
162 gcc_assert (!n_edges
);
165 /* Allocate memory for basic_block. */
171 bb
= ggc_alloc_cleared (sizeof (*bb
));
175 /* Create memory pool for rbi_pool. */
178 alloc_rbi_pool (void)
180 rbi_pool
= create_alloc_pool ("rbi pool",
181 sizeof (struct reorder_block_def
),
190 free_alloc_pool (rbi_pool
);
193 /* Initialize rbi (the structure containing data used by basic block
194 duplication and reordering) for the given basic block. */
197 initialize_bb_rbi (basic_block bb
)
199 gcc_assert (!bb
->rbi
);
200 bb
->rbi
= pool_alloc (rbi_pool
);
201 memset (bb
->rbi
, 0, sizeof (struct reorder_block_def
));
204 /* Link block B to chain after AFTER. */
206 link_block (basic_block b
, basic_block after
)
208 b
->next_bb
= after
->next_bb
;
211 b
->next_bb
->prev_bb
= b
;
214 /* Unlink block B from chain. */
216 unlink_block (basic_block b
)
218 b
->next_bb
->prev_bb
= b
->prev_bb
;
219 b
->prev_bb
->next_bb
= b
->next_bb
;
224 /* Sequentially order blocks and compact the arrays. */
226 compact_blocks (void)
234 BASIC_BLOCK (i
) = bb
;
239 gcc_assert (i
== n_basic_blocks
);
241 for (; i
< last_basic_block
; i
++)
242 BASIC_BLOCK (i
) = NULL
;
244 last_basic_block
= n_basic_blocks
;
247 /* Remove block B from the basic block array. */
250 expunge_block (basic_block b
)
253 BASIC_BLOCK (b
->index
) = NULL
;
255 /* We should be able to ggc_free here, but we are not.
256 The dead SSA_NAMES are left pointing to dead statements that are pointing
257 to dead basic blocks making garbage collector to die.
258 We should be able to release all dead SSA_NAMES and at the same time we should
259 clear out BB pointer of dead statements consistently. */
262 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
263 created edge. Use this only if you are sure that this edge can't
264 possibly already exist. */
267 unchecked_make_edge (basic_block src
, basic_block dst
, int flags
)
270 e
= ggc_alloc_cleared (sizeof (*e
));
273 VEC_safe_push (edge
, src
->succs
, e
);
274 VEC_safe_push (edge
, dst
->preds
, e
);
283 /* Create an edge connecting SRC and DST with FLAGS optionally using
284 edge cache CACHE. Return the new edge, NULL if already exist. */
287 cached_make_edge (sbitmap
*edge_cache
, basic_block src
, basic_block dst
, int flags
)
293 /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
294 many edges to them, or we didn't allocate memory for it. */
295 use_edge_cache
= (edge_cache
296 && src
!= ENTRY_BLOCK_PTR
&& dst
!= EXIT_BLOCK_PTR
);
298 /* Make sure we don't add duplicate edges. */
299 switch (use_edge_cache
)
302 /* Quick test for non-existence of the edge. */
303 if (! TEST_BIT (edge_cache
[src
->index
], dst
->index
))
306 /* The edge exists; early exit if no work to do. */
312 FOR_EACH_EDGE (e
, ei
, src
->succs
)
321 e
= unchecked_make_edge (src
, dst
, flags
);
324 SET_BIT (edge_cache
[src
->index
], dst
->index
);
329 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
330 created edge or NULL if already exist. */
333 make_edge (basic_block src
, basic_block dest
, int flags
)
335 return cached_make_edge (NULL
, src
, dest
, flags
);
338 /* Create an edge connecting SRC to DEST and set probability by knowing
339 that it is the single edge leaving SRC. */
342 make_single_succ_edge (basic_block src
, basic_block dest
, int flags
)
344 edge e
= make_edge (src
, dest
, flags
);
346 e
->probability
= REG_BR_PROB_BASE
;
347 e
->count
= src
->count
;
351 /* This function will remove an edge from the flow graph. */
357 basic_block src
, dest
;
364 for (ei
= ei_start (src
->succs
); (tmp
= ei_safe_edge (ei
)); )
368 VEC_unordered_remove (edge
, src
->succs
, ei
.index
);
379 for (ei
= ei_start (dest
->preds
); (tmp
= ei_safe_edge (ei
)); )
383 VEC_unordered_remove (edge
, dest
->preds
, ei
.index
);
396 /* Redirect an edge's successor from one block to another. */
399 redirect_edge_succ (edge e
, basic_block new_succ
)
405 /* Disconnect the edge from the old successor block. */
406 for (ei
= ei_start (e
->dest
->preds
); (tmp
= ei_safe_edge (ei
)); )
410 VEC_unordered_remove (edge
, e
->dest
->preds
, ei
.index
);
420 /* Reconnect the edge to the new successor block. */
421 VEC_safe_push (edge
, new_succ
->preds
, e
);
425 /* Like previous but avoid possible duplicate edge. */
428 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
432 s
= find_edge (e
->src
, new_succ
);
435 s
->flags
|= e
->flags
;
436 s
->probability
+= e
->probability
;
437 if (s
->probability
> REG_BR_PROB_BASE
)
438 s
->probability
= REG_BR_PROB_BASE
;
439 s
->count
+= e
->count
;
444 redirect_edge_succ (e
, new_succ
);
449 /* Redirect an edge's predecessor from one block to another. */
452 redirect_edge_pred (edge e
, basic_block new_pred
)
458 /* Disconnect the edge from the old predecessor block. */
459 for (ei
= ei_start (e
->src
->succs
); (tmp
= ei_safe_edge (ei
)); )
463 VEC_unordered_remove (edge
, e
->src
->succs
, ei
.index
);
473 /* Reconnect the edge to the new predecessor block. */
474 VEC_safe_push (edge
, new_pred
->succs
, e
);
478 /* Clear all basic block flags, with the exception of partitioning. */
480 clear_bb_flags (void)
484 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
485 bb
->flags
= BB_PARTITION (bb
);
488 /* Check the consistency of profile information. We can't do that
489 in verify_flow_info, as the counts may get invalid for incompletely
490 solved graphs, later eliminating of conditionals or roundoff errors.
491 It is still practical to have them reported for debugging of simple
494 check_bb_profile (basic_block bb
, FILE * file
)
501 if (profile_status
== PROFILE_ABSENT
)
504 if (bb
!= EXIT_BLOCK_PTR
)
506 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
507 sum
+= e
->probability
;
508 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
509 fprintf (file
, "Invalid sum of outgoing probabilities %.1f%%\n",
510 sum
* 100.0 / REG_BR_PROB_BASE
);
512 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
514 if (EDGE_COUNT (bb
->succs
)
515 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
516 fprintf (file
, "Invalid sum of outgoing counts %i, should be %i\n",
517 (int) lsum
, (int) bb
->count
);
519 if (bb
!= ENTRY_BLOCK_PTR
)
522 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
523 sum
+= EDGE_FREQUENCY (e
);
524 if (abs (sum
- bb
->frequency
) > 100)
526 "Invalid sum of incoming frequencies %i, should be %i\n",
529 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
531 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
532 fprintf (file
, "Invalid sum of incoming counts %i, should be %i\n",
533 (int) lsum
, (int) bb
->count
);
538 dump_flow_info (FILE *file
)
542 static const char * const reg_class_names
[] = REG_CLASS_NAMES
;
546 int max_regno
= max_reg_num ();
547 fprintf (file
, "%d registers.\n", max_regno
);
548 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
551 enum reg_class
class, altclass
;
553 fprintf (file
, "\nRegister %d used %d times across %d insns",
554 i
, REG_N_REFS (i
), REG_LIVE_LENGTH (i
));
555 if (REG_BASIC_BLOCK (i
) >= 0)
556 fprintf (file
, " in block %d", REG_BASIC_BLOCK (i
));
558 fprintf (file
, "; set %d time%s", REG_N_SETS (i
),
559 (REG_N_SETS (i
) == 1) ? "" : "s");
560 if (regno_reg_rtx
[i
] != NULL
&& REG_USERVAR_P (regno_reg_rtx
[i
]))
561 fprintf (file
, "; user var");
562 if (REG_N_DEATHS (i
) != 1)
563 fprintf (file
, "; dies in %d places", REG_N_DEATHS (i
));
564 if (REG_N_CALLS_CROSSED (i
) == 1)
565 fprintf (file
, "; crosses 1 call");
566 else if (REG_N_CALLS_CROSSED (i
))
567 fprintf (file
, "; crosses %d calls", REG_N_CALLS_CROSSED (i
));
568 if (regno_reg_rtx
[i
] != NULL
569 && PSEUDO_REGNO_BYTES (i
) != UNITS_PER_WORD
)
570 fprintf (file
, "; %d bytes", PSEUDO_REGNO_BYTES (i
));
572 class = reg_preferred_class (i
);
573 altclass
= reg_alternate_class (i
);
574 if (class != GENERAL_REGS
|| altclass
!= ALL_REGS
)
576 if (altclass
== ALL_REGS
|| class == ALL_REGS
)
577 fprintf (file
, "; pref %s", reg_class_names
[(int) class]);
578 else if (altclass
== NO_REGS
)
579 fprintf (file
, "; %s or none", reg_class_names
[(int) class]);
581 fprintf (file
, "; pref %s, else %s",
582 reg_class_names
[(int) class],
583 reg_class_names
[(int) altclass
]);
586 if (regno_reg_rtx
[i
] != NULL
&& REG_POINTER (regno_reg_rtx
[i
]))
587 fprintf (file
, "; pointer");
588 fprintf (file
, ".\n");
592 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks
, n_edges
);
598 fprintf (file
, "\nBasic block %d ", bb
->index
);
599 fprintf (file
, "prev %d, next %d, ",
600 bb
->prev_bb
->index
, bb
->next_bb
->index
);
601 fprintf (file
, "loop_depth %d, count ", bb
->loop_depth
);
602 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
603 fprintf (file
, ", freq %i", bb
->frequency
);
604 if (maybe_hot_bb_p (bb
))
605 fprintf (file
, ", maybe hot");
606 if (probably_never_executed_bb_p (bb
))
607 fprintf (file
, ", probably never executed");
608 fprintf (file
, ".\n");
610 fprintf (file
, "Predecessors: ");
611 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
612 dump_edge_info (file
, e
, 0);
614 fprintf (file
, "\nSuccessors: ");
615 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
616 dump_edge_info (file
, e
, 1);
618 if (bb
->global_live_at_start
)
620 fprintf (file
, "\nRegisters live at start:");
621 dump_regset (bb
->global_live_at_start
, file
);
624 if (bb
->global_live_at_end
)
626 fprintf (file
, "\nRegisters live at end:");
627 dump_regset (bb
->global_live_at_end
, file
);
631 check_bb_profile (bb
, file
);
638 debug_flow_info (void)
640 dump_flow_info (stderr
);
644 dump_edge_info (FILE *file
, edge e
, int do_succ
)
646 basic_block side
= (do_succ
? e
->dest
: e
->src
);
648 if (side
== ENTRY_BLOCK_PTR
)
649 fputs (" ENTRY", file
);
650 else if (side
== EXIT_BLOCK_PTR
)
651 fputs (" EXIT", file
);
653 fprintf (file
, " %d", side
->index
);
656 fprintf (file
, " [%.1f%%] ", e
->probability
* 100.0 / REG_BR_PROB_BASE
);
660 fprintf (file
, " count:");
661 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
666 static const char * const bitnames
[] = {
667 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
668 "can_fallthru", "irreducible", "sibcall", "loop_exit",
669 "true", "false", "exec"
672 int i
, flags
= e
->flags
;
675 for (i
= 0; flags
; i
++)
676 if (flags
& (1 << i
))
682 if (i
< (int) ARRAY_SIZE (bitnames
))
683 fputs (bitnames
[i
], file
);
685 fprintf (file
, "%d", i
);
693 /* Simple routines to easily allocate AUX fields of basic blocks. */
695 static struct obstack block_aux_obstack
;
696 static void *first_block_aux_obj
= 0;
697 static struct obstack edge_aux_obstack
;
698 static void *first_edge_aux_obj
= 0;
700 /* Allocate a memory block of SIZE as BB->aux. The obstack must
701 be first initialized by alloc_aux_for_blocks. */
704 alloc_aux_for_block (basic_block bb
, int size
)
706 /* Verify that aux field is clear. */
707 gcc_assert (!bb
->aux
&& first_block_aux_obj
);
708 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
709 memset (bb
->aux
, 0, size
);
712 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
713 alloc_aux_for_block for each basic block. */
716 alloc_aux_for_blocks (int size
)
718 static int initialized
;
722 gcc_obstack_init (&block_aux_obstack
);
726 /* Check whether AUX data are still allocated. */
727 gcc_assert (!first_block_aux_obj
);
729 first_block_aux_obj
= obstack_alloc (&block_aux_obstack
, 0);
734 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
735 alloc_aux_for_block (bb
, size
);
739 /* Clear AUX pointers of all blocks. */
742 clear_aux_for_blocks (void)
746 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
750 /* Free data allocated in block_aux_obstack and clear AUX pointers
754 free_aux_for_blocks (void)
756 gcc_assert (first_block_aux_obj
);
757 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
758 first_block_aux_obj
= NULL
;
760 clear_aux_for_blocks ();
763 /* Allocate a memory edge of SIZE as BB->aux. The obstack must
764 be first initialized by alloc_aux_for_edges. */
767 alloc_aux_for_edge (edge e
, int size
)
769 /* Verify that aux field is clear. */
770 gcc_assert (!e
->aux
&& first_edge_aux_obj
);
771 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
772 memset (e
->aux
, 0, size
);
775 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
776 alloc_aux_for_edge for each basic edge. */
779 alloc_aux_for_edges (int size
)
781 static int initialized
;
785 gcc_obstack_init (&edge_aux_obstack
);
789 /* Check whether AUX data are still allocated. */
790 gcc_assert (!first_edge_aux_obj
);
792 first_edge_aux_obj
= obstack_alloc (&edge_aux_obstack
, 0);
797 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
802 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
803 alloc_aux_for_edge (e
, size
);
808 /* Clear AUX pointers of all edges. */
811 clear_aux_for_edges (void)
816 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
819 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
824 /* Free data allocated in edge_aux_obstack and clear AUX pointers
828 free_aux_for_edges (void)
830 gcc_assert (first_edge_aux_obj
);
831 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
832 first_edge_aux_obj
= NULL
;
834 clear_aux_for_edges ();
838 debug_bb (basic_block bb
)
840 dump_bb (bb
, stderr
, 0);
846 basic_block bb
= BASIC_BLOCK (n
);
847 dump_bb (bb
, stderr
, 0);
851 /* Dumps cfg related information about basic block BB to FILE. */
854 dump_cfg_bb_info (FILE *file
, basic_block bb
)
859 static const char * const bb_bitnames
[] =
861 "dirty", "new", "reachable", "visited", "irreducible_loop", "superblock"
863 const unsigned n_bitnames
= sizeof (bb_bitnames
) / sizeof (char *);
866 fprintf (file
, "Basic block %d", bb
->index
);
867 for (i
= 0; i
< n_bitnames
; i
++)
868 if (bb
->flags
& (1 << i
))
871 fprintf (file
, " (");
873 fprintf (file
, ", ");
875 fprintf (file
, bb_bitnames
[i
]);
879 fprintf (file
, "\n");
881 fprintf (file
, "Predecessors: ");
882 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
883 dump_edge_info (file
, e
, 0);
885 fprintf (file
, "\nSuccessors: ");
886 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
887 dump_edge_info (file
, e
, 1);
888 fprintf (file
, "\n\n");
891 /* Dumps a brief description of cfg to FILE. */
894 brief_dump_cfg (FILE *file
)
900 dump_cfg_bb_info (file
, bb
);
904 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
905 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
906 redirected to destination of TAKEN_EDGE.
908 This function may leave the profile inconsistent in the case TAKEN_EDGE
909 frequency or count is believed to be lower than FREQUENCY or COUNT
912 update_bb_profile_for_threading (basic_block bb
, int edge_frequency
,
913 gcov_type count
, edge taken_edge
)
923 /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
924 Watch for overflows. */
926 prob
= edge_frequency
* REG_BR_PROB_BASE
/ bb
->frequency
;
929 if (prob
> taken_edge
->probability
)
932 fprintf (dump_file
, "Jump threading proved probability of edge "
933 "%i->%i too small (it is %i, should be %i).\n",
934 taken_edge
->src
->index
, taken_edge
->dest
->index
,
935 taken_edge
->probability
, prob
);
936 prob
= taken_edge
->probability
;
939 /* Now rescale the probabilities. */
940 taken_edge
->probability
-= prob
;
941 prob
= REG_BR_PROB_BASE
- prob
;
942 bb
->frequency
-= edge_frequency
;
943 if (bb
->frequency
< 0)
948 fprintf (dump_file
, "Edge frequencies of bb %i has been reset, "
949 "frequency of block should end up being 0, it is %i\n",
950 bb
->index
, bb
->frequency
);
951 EDGE_SUCC (bb
, 0)->probability
= REG_BR_PROB_BASE
;
952 ei
= ei_start (bb
->succs
);
954 for (; (c
= ei_safe_edge (ei
)); ei_next (&ei
))
958 FOR_EACH_EDGE (c
, ei
, bb
->succs
)
959 c
->probability
= ((c
->probability
* REG_BR_PROB_BASE
) / (double) prob
);
961 if (bb
!= taken_edge
->src
)
963 taken_edge
->count
-= count
;
964 if (taken_edge
->count
< 0)
965 taken_edge
->count
= 0;