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. */
150 FOR_EACH_EDGE (e
, bb
->succs
)
153 VEC_truncate (edge
, bb
->succs
, 0);
154 VEC_truncate (edge
, bb
->preds
, 0);
157 FOR_EACH_EDGE (e
, ENTRY_BLOCK_PTR
->succs
)
160 VEC_truncate (edge
, EXIT_BLOCK_PTR
->preds
, 0);
161 VEC_truncate (edge
, ENTRY_BLOCK_PTR
->succs
, 0);
163 gcc_assert (!n_edges
);
166 /* Allocate memory for basic_block. */
172 bb
= ggc_alloc_cleared (sizeof (*bb
));
176 /* Create memory pool for rbi_pool. */
179 alloc_rbi_pool (void)
181 rbi_pool
= create_alloc_pool ("rbi pool",
182 sizeof (struct reorder_block_def
),
191 free_alloc_pool (rbi_pool
);
194 /* Initialize rbi (the structure containing data used by basic block
195 duplication and reordering) for the given basic block. */
198 initialize_bb_rbi (basic_block bb
)
200 gcc_assert (!bb
->rbi
);
201 bb
->rbi
= pool_alloc (rbi_pool
);
202 memset (bb
->rbi
, 0, sizeof (struct reorder_block_def
));
205 /* Link block B to chain after AFTER. */
207 link_block (basic_block b
, basic_block after
)
209 b
->next_bb
= after
->next_bb
;
212 b
->next_bb
->prev_bb
= b
;
215 /* Unlink block B from chain. */
217 unlink_block (basic_block b
)
219 b
->next_bb
->prev_bb
= b
->prev_bb
;
220 b
->prev_bb
->next_bb
= b
->next_bb
;
225 /* Sequentially order blocks and compact the arrays. */
227 compact_blocks (void)
235 BASIC_BLOCK (i
) = bb
;
240 gcc_assert (i
== n_basic_blocks
);
242 for (; i
< last_basic_block
; i
++)
243 BASIC_BLOCK (i
) = NULL
;
245 last_basic_block
= n_basic_blocks
;
248 /* Remove block B from the basic block array. */
251 expunge_block (basic_block b
)
254 BASIC_BLOCK (b
->index
) = NULL
;
259 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
260 created edge. Use this only if you are sure that this edge can't
261 possibly already exist. */
264 unchecked_make_edge (basic_block src
, basic_block dst
, int flags
)
267 e
= ggc_alloc_cleared (sizeof (*e
));
270 VEC_safe_push (edge
, src
->succs
, e
);
271 VEC_safe_push (edge
, dst
->preds
, e
);
280 /* Create an edge connecting SRC and DST with FLAGS optionally using
281 edge cache CACHE. Return the new edge, NULL if already exist. */
284 cached_make_edge (sbitmap
*edge_cache
, basic_block src
, basic_block dst
, int flags
)
289 /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
290 many edges to them, or we didn't allocate memory for it. */
291 use_edge_cache
= (edge_cache
292 && src
!= ENTRY_BLOCK_PTR
&& dst
!= EXIT_BLOCK_PTR
);
294 /* Make sure we don't add duplicate edges. */
295 switch (use_edge_cache
)
298 /* Quick test for non-existence of the edge. */
299 if (! TEST_BIT (edge_cache
[src
->index
], dst
->index
))
302 /* The edge exists; early exit if no work to do. */
308 FOR_EACH_EDGE (e
, src
->succs
)
320 e
= unchecked_make_edge (src
, dst
, flags
);
323 SET_BIT (edge_cache
[src
->index
], dst
->index
);
328 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
329 created edge or NULL if already exist. */
332 make_edge (basic_block src
, basic_block dest
, int flags
)
334 return cached_make_edge (NULL
, src
, dest
, flags
);
337 /* Create an edge connecting SRC to DEST and set probability by knowing
338 that it is the single edge leaving SRC. */
341 make_single_succ_edge (basic_block src
, basic_block dest
, int flags
)
343 edge e
= make_edge (src
, dest
, flags
);
345 e
->probability
= REG_BR_PROB_BASE
;
346 e
->count
= src
->count
;
350 /* This function will remove an edge from the flow graph. */
356 basic_block src
, dest
;
363 for (ix
= 0; VEC_iterate (edge
, src
->succs
, ix
, tmp
); )
367 VEC_unordered_remove (edge
, src
->succs
, ix
);
381 for (ix
= 0; VEC_iterate (edge
, dest
->preds
, ix
, tmp
); )
385 VEC_unordered_remove (edge
, dest
->preds
, ix
);
398 /* Redirect an edge's successor from one block to another. */
401 redirect_edge_succ (edge e
, basic_block new_succ
)
407 /* Disconnect the edge from the old successor block. */
408 for (ix
= 0; VEC_iterate (edge
, e
->dest
->preds
, ix
, tmp
); )
412 VEC_unordered_remove (edge
, e
->dest
->preds
, ix
);
423 /* Reconnect the edge to the new successor block. */
424 VEC_safe_push (edge
, new_succ
->preds
, e
);
428 /* Like previous but avoid possible duplicate edge. */
431 redirect_edge_succ_nodup (edge e
, basic_block new_succ
)
435 /* Check whether the edge is already present. */
436 FOR_EACH_EDGE (s
, e
->src
->succs
)
438 if (s
->dest
== new_succ
&& s
!= e
)
445 s
->flags
|= e
->flags
;
446 s
->probability
+= e
->probability
;
447 if (s
->probability
> REG_BR_PROB_BASE
)
448 s
->probability
= REG_BR_PROB_BASE
;
449 s
->count
+= e
->count
;
454 redirect_edge_succ (e
, new_succ
);
459 /* Redirect an edge's predecessor from one block to another. */
462 redirect_edge_pred (edge e
, basic_block new_pred
)
468 /* Disconnect the edge from the old predecessor block. */
469 for (ix
= 0; VEC_iterate (edge
, e
->src
->succs
, ix
, tmp
); )
473 VEC_unordered_remove (edge
, e
->src
->succs
, ix
);
484 /* Reconnect the edge to the new predecessor block. */
485 VEC_safe_push (edge
, new_pred
->succs
, e
);
489 /* Clear all basic block flags, with the exception of partitioning. */
491 clear_bb_flags (void)
495 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
496 bb
->flags
= BB_PARTITION (bb
);
499 /* Check the consistency of profile information. We can't do that
500 in verify_flow_info, as the counts may get invalid for incompletely
501 solved graphs, later eliminating of conditionals or roundoff errors.
502 It is still practical to have them reported for debugging of simple
505 check_bb_profile (basic_block bb
, FILE * file
)
511 if (profile_status
== PROFILE_ABSENT
)
514 if (bb
!= EXIT_BLOCK_PTR
)
516 FOR_EACH_EDGE (e
, bb
->succs
)
517 sum
+= e
->probability
;
519 if (EDGE_COUNT (bb
->succs
) && abs (sum
- REG_BR_PROB_BASE
) > 100)
520 fprintf (file
, "Invalid sum of outgoing probabilities %.1f%%\n",
521 sum
* 100.0 / REG_BR_PROB_BASE
);
523 FOR_EACH_EDGE (e
, bb
->succs
)
526 if (EDGE_COUNT (bb
->succs
)
527 && (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
528 fprintf (file
, "Invalid sum of outgoing counts %i, should be %i\n",
529 (int) lsum
, (int) bb
->count
);
531 if (bb
!= ENTRY_BLOCK_PTR
)
534 FOR_EACH_EDGE (e
, bb
->preds
)
535 sum
+= EDGE_FREQUENCY (e
);
537 if (abs (sum
- bb
->frequency
) > 100)
539 "Invalid sum of incoming frequencies %i, should be %i\n",
542 FOR_EACH_EDGE (e
, bb
->preds
)
545 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
546 fprintf (file
, "Invalid sum of incoming counts %i, should be %i\n",
547 (int) lsum
, (int) bb
->count
);
552 dump_flow_info (FILE *file
)
556 static const char * const reg_class_names
[] = REG_CLASS_NAMES
;
560 int max_regno
= max_reg_num ();
561 fprintf (file
, "%d registers.\n", max_regno
);
562 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
565 enum reg_class
class, altclass
;
567 fprintf (file
, "\nRegister %d used %d times across %d insns",
568 i
, REG_N_REFS (i
), REG_LIVE_LENGTH (i
));
569 if (REG_BASIC_BLOCK (i
) >= 0)
570 fprintf (file
, " in block %d", REG_BASIC_BLOCK (i
));
572 fprintf (file
, "; set %d time%s", REG_N_SETS (i
),
573 (REG_N_SETS (i
) == 1) ? "" : "s");
574 if (regno_reg_rtx
[i
] != NULL
&& REG_USERVAR_P (regno_reg_rtx
[i
]))
575 fprintf (file
, "; user var");
576 if (REG_N_DEATHS (i
) != 1)
577 fprintf (file
, "; dies in %d places", REG_N_DEATHS (i
));
578 if (REG_N_CALLS_CROSSED (i
) == 1)
579 fprintf (file
, "; crosses 1 call");
580 else if (REG_N_CALLS_CROSSED (i
))
581 fprintf (file
, "; crosses %d calls", REG_N_CALLS_CROSSED (i
));
582 if (regno_reg_rtx
[i
] != NULL
583 && PSEUDO_REGNO_BYTES (i
) != UNITS_PER_WORD
)
584 fprintf (file
, "; %d bytes", PSEUDO_REGNO_BYTES (i
));
586 class = reg_preferred_class (i
);
587 altclass
= reg_alternate_class (i
);
588 if (class != GENERAL_REGS
|| altclass
!= ALL_REGS
)
590 if (altclass
== ALL_REGS
|| class == ALL_REGS
)
591 fprintf (file
, "; pref %s", reg_class_names
[(int) class]);
592 else if (altclass
== NO_REGS
)
593 fprintf (file
, "; %s or none", reg_class_names
[(int) class]);
595 fprintf (file
, "; pref %s, else %s",
596 reg_class_names
[(int) class],
597 reg_class_names
[(int) altclass
]);
600 if (regno_reg_rtx
[i
] != NULL
&& REG_POINTER (regno_reg_rtx
[i
]))
601 fprintf (file
, "; pointer");
602 fprintf (file
, ".\n");
606 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks
, n_edges
);
611 fprintf (file
, "\nBasic block %d ", bb
->index
);
612 fprintf (file
, "prev %d, next %d, ",
613 bb
->prev_bb
->index
, bb
->next_bb
->index
);
614 fprintf (file
, "loop_depth %d, count ", bb
->loop_depth
);
615 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
616 fprintf (file
, ", freq %i", bb
->frequency
);
617 if (maybe_hot_bb_p (bb
))
618 fprintf (file
, ", maybe hot");
619 if (probably_never_executed_bb_p (bb
))
620 fprintf (file
, ", probably never executed");
621 fprintf (file
, ".\n");
623 fprintf (file
, "Predecessors: ");
624 FOR_EACH_EDGE (e
, bb
->preds
)
625 dump_edge_info (file
, e
, 0);
628 fprintf (file
, "\nSuccessors: ");
629 FOR_EACH_EDGE (e
, bb
->succs
)
630 dump_edge_info (file
, e
, 1);
633 fprintf (file
, "\nRegisters live at start:");
634 dump_regset (bb
->global_live_at_start
, file
);
636 fprintf (file
, "\nRegisters live at end:");
637 dump_regset (bb
->global_live_at_end
, file
);
641 if (bb
->global_live_at_start
)
643 fprintf (file
, "\nRegisters live at start:");
644 dump_regset (bb
->global_live_at_start
, file
);
647 if (bb
->global_live_at_end
)
649 fprintf (file
, "\nRegisters live at end:");
650 dump_regset (bb
->global_live_at_end
, file
);
654 check_bb_profile (bb
, file
);
661 debug_flow_info (void)
663 dump_flow_info (stderr
);
667 dump_edge_info (FILE *file
, edge e
, int do_succ
)
669 basic_block side
= (do_succ
? e
->dest
: e
->src
);
671 if (side
== ENTRY_BLOCK_PTR
)
672 fputs (" ENTRY", file
);
673 else if (side
== EXIT_BLOCK_PTR
)
674 fputs (" EXIT", file
);
676 fprintf (file
, " %d", side
->index
);
679 fprintf (file
, " [%.1f%%] ", e
->probability
* 100.0 / REG_BR_PROB_BASE
);
683 fprintf (file
, " count:");
684 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
689 static const char * const bitnames
[] = {
690 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
691 "can_fallthru", "irreducible", "sibcall", "loop_exit",
692 "true", "false", "exec"
695 int i
, flags
= e
->flags
;
698 for (i
= 0; flags
; i
++)
699 if (flags
& (1 << i
))
705 if (i
< (int) ARRAY_SIZE (bitnames
))
706 fputs (bitnames
[i
], file
);
708 fprintf (file
, "%d", i
);
716 /* Simple routines to easily allocate AUX fields of basic blocks. */
718 static struct obstack block_aux_obstack
;
719 static void *first_block_aux_obj
= 0;
720 static struct obstack edge_aux_obstack
;
721 static void *first_edge_aux_obj
= 0;
723 /* Allocate a memory block of SIZE as BB->aux. The obstack must
724 be first initialized by alloc_aux_for_blocks. */
727 alloc_aux_for_block (basic_block bb
, int size
)
729 /* Verify that aux field is clear. */
730 gcc_assert (!bb
->aux
&& first_block_aux_obj
);
731 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
732 memset (bb
->aux
, 0, size
);
735 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
736 alloc_aux_for_block for each basic block. */
739 alloc_aux_for_blocks (int size
)
741 static int initialized
;
745 gcc_obstack_init (&block_aux_obstack
);
749 /* Check whether AUX data are still allocated. */
750 gcc_assert (!first_block_aux_obj
);
752 first_block_aux_obj
= obstack_alloc (&block_aux_obstack
, 0);
757 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
758 alloc_aux_for_block (bb
, size
);
762 /* Clear AUX pointers of all blocks. */
765 clear_aux_for_blocks (void)
769 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
773 /* Free data allocated in block_aux_obstack and clear AUX pointers
777 free_aux_for_blocks (void)
779 gcc_assert (first_block_aux_obj
);
780 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
781 first_block_aux_obj
= NULL
;
783 clear_aux_for_blocks ();
786 /* Allocate a memory edge of SIZE as BB->aux. The obstack must
787 be first initialized by alloc_aux_for_edges. */
790 alloc_aux_for_edge (edge e
, int size
)
792 /* Verify that aux field is clear. */
793 gcc_assert (!e
->aux
&& first_edge_aux_obj
);
794 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
795 memset (e
->aux
, 0, size
);
798 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
799 alloc_aux_for_edge for each basic edge. */
802 alloc_aux_for_edges (int size
)
804 static int initialized
;
808 gcc_obstack_init (&edge_aux_obstack
);
812 /* Check whether AUX data are still allocated. */
813 gcc_assert (!first_edge_aux_obj
);
815 first_edge_aux_obj
= obstack_alloc (&edge_aux_obstack
, 0);
820 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
824 FOR_EACH_EDGE (e
, bb
->succs
)
825 alloc_aux_for_edge (e
, size
);
831 /* Clear AUX pointers of all edges. */
834 clear_aux_for_edges (void)
839 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
841 FOR_EACH_EDGE (e
, bb
->succs
)
847 /* Free data allocated in edge_aux_obstack and clear AUX pointers
851 free_aux_for_edges (void)
853 gcc_assert (first_edge_aux_obj
);
854 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
855 first_edge_aux_obj
= NULL
;
857 clear_aux_for_edges ();
861 debug_bb (basic_block bb
)
863 dump_bb (bb
, stderr
, 0);
869 basic_block bb
= BASIC_BLOCK (n
);
870 dump_bb (bb
, stderr
, 0);
874 /* Dumps cfg related information about basic block BB to FILE. */
877 dump_cfg_bb_info (FILE *file
, basic_block bb
)
881 static const char * const bb_bitnames
[] =
883 "dirty", "new", "reachable", "visited", "irreducible_loop", "superblock"
885 const unsigned n_bitnames
= sizeof (bb_bitnames
) / sizeof (char *);
888 fprintf (file
, "Basic block %d", bb
->index
);
889 for (i
= 0; i
< n_bitnames
; i
++)
890 if (bb
->flags
& (1 << i
))
893 fprintf (file
, " (");
895 fprintf (file
, ", ");
897 fprintf (file
, bb_bitnames
[i
]);
901 fprintf (file
, "\n");
903 fprintf (file
, "Predecessors: ");
904 FOR_EACH_EDGE (e
, bb
->preds
)
905 dump_edge_info (file
, e
, 0);
908 fprintf (file
, "\nSuccessors: ");
909 FOR_EACH_EDGE (e
, bb
->succs
)
910 dump_edge_info (file
, e
, 1);
912 fprintf (file
, "\n\n");
915 /* Dumps a brief description of cfg to FILE. */
918 brief_dump_cfg (FILE *file
)
924 dump_cfg_bb_info (file
, bb
);