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 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 datastructure
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"
66 /* The obstack on which the flow graph components are allocated. */
68 struct obstack flow_obstack;
69 static char *flow_firstobj;
71 /* Basic block object pool. */
73 static alloc_pool bb_pool;
75 /* Edge object pool. */
77 static alloc_pool edge_pool;
79 /* Number of basic blocks in the current function. */
83 /* First free basic block number. */
87 /* Number of edges in the current function. */
91 /* The basic block array. */
93 varray_type basic_block_info;
95 /* The special entry and exit blocks. */
97 struct basic_block_def entry_exit_blocks[2]
100 NULL, /* head_tree */
104 NULL, /* local_set */
105 NULL, /* cond_local_set */
106 NULL, /* global_live_at_start */
107 NULL, /* global_live_at_end */
109 ENTRY_BLOCK, /* index */
111 EXIT_BLOCK_PTR, /* next_bb */
113 NULL, /* loop_father */
121 NULL, /* head_tree */
125 NULL, /* local_set */
126 NULL, /* cond_local_set */
127 NULL, /* global_live_at_start */
128 NULL, /* global_live_at_end */
130 EXIT_BLOCK, /* index */
131 ENTRY_BLOCK_PTR, /* prev_bb */
134 NULL, /* loop_father */
141 void debug_flow_info (void);
142 static void free_edge (edge);
144 /* Called once at initialization time. */
149 static int initialized;
155 gcc_obstack_init (&flow_obstack);
156 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
161 free_alloc_pool (bb_pool);
162 free_alloc_pool (edge_pool);
163 obstack_free (&flow_obstack, flow_firstobj);
164 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
166 bb_pool = create_alloc_pool ("Basic block pool",
167 sizeof (struct basic_block_def), 100);
168 edge_pool = create_alloc_pool ("Edge pool",
169 sizeof (struct edge_def), 100);
172 /* Helper function for remove_edge and clear_edges. Frees edge structure
173 without actually unlinking it from the pred/succ lists. */
179 pool_free (edge_pool, e);
182 /* Free the memory associated with the edge structures. */
196 edge next = e->succ_next;
206 e = ENTRY_BLOCK_PTR->succ;
209 edge next = e->succ_next;
215 EXIT_BLOCK_PTR->pred = NULL;
216 ENTRY_BLOCK_PTR->succ = NULL;
222 /* Allocate memory for basic_block. */
228 bb = pool_alloc (bb_pool);
229 memset (bb, 0, sizeof (*bb));
233 /* Link block B to chain after AFTER. */
235 link_block (basic_block b, basic_block after)
237 b->next_bb = after->next_bb;
240 b->next_bb->prev_bb = b;
243 /* Unlink block B from chain. */
245 unlink_block (basic_block b)
247 b->next_bb->prev_bb = b->prev_bb;
248 b->prev_bb->next_bb = b->next_bb;
251 /* Sequentially order blocks and compact the arrays. */
253 compact_blocks (void)
261 BASIC_BLOCK (i) = bb;
266 if (i != n_basic_blocks)
269 last_basic_block = n_basic_blocks;
272 /* Remove block B from the basic block array. */
275 expunge_block (basic_block b)
278 BASIC_BLOCK (b->index) = NULL;
280 pool_free (bb_pool, b);
283 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
284 created edge. Use this only if you are sure that this edge can't
285 possibly already exist. */
288 unchecked_make_edge (basic_block src, basic_block dst, int flags)
291 e = pool_alloc (edge_pool);
292 memset (e, 0, sizeof (*e));
295 e->succ_next = src->succ;
296 e->pred_next = dst->pred;
307 /* Create an edge connecting SRC and DST with FLAGS optionally using
308 edge cache CACHE. Return the new edge, NULL if already exist. */
311 cached_make_edge (sbitmap *edge_cache, basic_block src, basic_block dst, int flags)
316 /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
317 many edges to them, or we didn't allocate memory for it. */
318 use_edge_cache = (edge_cache
319 && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR);
321 /* Make sure we don't add duplicate edges. */
322 switch (use_edge_cache)
325 /* Quick test for non-existence of the edge. */
326 if (! TEST_BIT (edge_cache[src->index], dst->index))
329 /* The edge exists; early exit if no work to do. */
335 for (e = src->succ; e; e = e->succ_next)
344 e = unchecked_make_edge (src, dst, flags);
347 SET_BIT (edge_cache[src->index], dst->index);
352 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
353 created edge or NULL if already exist. */
356 make_edge (basic_block src, basic_block dest, int flags)
358 return cached_make_edge (NULL, src, dest, flags);
361 /* Create an edge connecting SRC to DEST and set probability by knowing
362 that it is the single edge leaving SRC. */
365 make_single_succ_edge (basic_block src, basic_block dest, int flags)
367 edge e = make_edge (src, dest, flags);
369 e->probability = REG_BR_PROB_BASE;
370 e->count = src->count;
374 /* This function will remove an edge from the flow graph. */
379 edge last_pred = NULL;
380 edge last_succ = NULL;
382 basic_block src, dest;
386 for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
392 last_succ->succ_next = e->succ_next;
394 src->succ = e->succ_next;
396 for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
402 last_pred->pred_next = e->pred_next;
404 dest->pred = e->pred_next;
409 /* Redirect an edge's successor from one block to another. */
412 redirect_edge_succ (edge e, basic_block new_succ)
416 /* Disconnect the edge from the old successor block. */
417 for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next)
419 *pe = (*pe)->pred_next;
421 /* Reconnect the edge to the new successor block. */
422 e->pred_next = new_succ->pred;
427 /* Like previous but avoid possible duplicate edge. */
430 redirect_edge_succ_nodup (edge e, basic_block new_succ)
434 /* Check whether the edge is already present. */
435 for (s = e->src->succ; s; s = s->succ_next)
436 if (s->dest == new_succ && s != e)
441 s->flags |= e->flags;
442 s->probability += e->probability;
443 if (s->probability > REG_BR_PROB_BASE)
444 s->probability = REG_BR_PROB_BASE;
445 s->count += e->count;
450 redirect_edge_succ (e, new_succ);
455 /* Redirect an edge's predecessor from one block to another. */
458 redirect_edge_pred (edge e, basic_block new_pred)
462 /* Disconnect the edge from the old predecessor block. */
463 for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next)
466 *pe = (*pe)->succ_next;
468 /* Reconnect the edge to the new predecessor block. */
469 e->succ_next = new_pred->succ;
475 clear_bb_flags (void)
479 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
484 dump_flow_info (FILE *file)
487 int max_regno = max_reg_num ();
489 static const char * const reg_class_names[] = REG_CLASS_NAMES;
491 fprintf (file, "%d registers.\n", max_regno);
492 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
495 enum reg_class class, altclass;
497 fprintf (file, "\nRegister %d used %d times across %d insns",
498 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
499 if (REG_BASIC_BLOCK (i) >= 0)
500 fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
502 fprintf (file, "; set %d time%s", REG_N_SETS (i),
503 (REG_N_SETS (i) == 1) ? "" : "s");
504 if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
505 fprintf (file, "; user var");
506 if (REG_N_DEATHS (i) != 1)
507 fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
508 if (REG_N_CALLS_CROSSED (i) == 1)
509 fprintf (file, "; crosses 1 call");
510 else if (REG_N_CALLS_CROSSED (i))
511 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
512 if (regno_reg_rtx[i] != NULL
513 && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
514 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
516 class = reg_preferred_class (i);
517 altclass = reg_alternate_class (i);
518 if (class != GENERAL_REGS || altclass != ALL_REGS)
520 if (altclass == ALL_REGS || class == ALL_REGS)
521 fprintf (file, "; pref %s", reg_class_names[(int) class]);
522 else if (altclass == NO_REGS)
523 fprintf (file, "; %s or none", reg_class_names[(int) class]);
525 fprintf (file, "; pref %s, else %s",
526 reg_class_names[(int) class],
527 reg_class_names[(int) altclass]);
530 if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
531 fprintf (file, "; pointer");
532 fprintf (file, ".\n");
535 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
542 fprintf (file, "\nBasic block %d: first insn %d, last %d, ",
543 bb->index, INSN_UID (bb->head), INSN_UID (bb->end));
544 fprintf (file, "prev %d, next %d, ",
545 bb->prev_bb->index, bb->next_bb->index);
546 fprintf (file, "loop_depth %d, count ", bb->loop_depth);
547 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
548 fprintf (file, ", freq %i", bb->frequency);
549 if (maybe_hot_bb_p (bb))
550 fprintf (file, ", maybe hot");
551 if (probably_never_executed_bb_p (bb))
552 fprintf (file, ", probably never executed");
553 fprintf (file, ".\n");
555 fprintf (file, "Predecessors: ");
556 for (e = bb->pred; e; e = e->pred_next)
557 dump_edge_info (file, e, 0);
559 fprintf (file, "\nSuccessors: ");
560 for (e = bb->succ; e; e = e->succ_next)
561 dump_edge_info (file, e, 1);
563 fprintf (file, "\nRegisters live at start:");
564 dump_regset (bb->global_live_at_start, file);
566 fprintf (file, "\nRegisters live at end:");
567 dump_regset (bb->global_live_at_end, file);
571 /* Check the consistency of profile information. We can't do that
572 in verify_flow_info, as the counts may get invalid for incompletely
573 solved graphs, later eliminating of conditionals or roundoff errors.
574 It is still practical to have them reported for debugging of simple
577 for (e = bb->succ; e; e = e->succ_next)
578 sum += e->probability;
579 if (bb->succ && abs (sum - REG_BR_PROB_BASE) > 100)
580 fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
581 sum * 100.0 / REG_BR_PROB_BASE);
583 for (e = bb->pred; e; e = e->pred_next)
584 sum += EDGE_FREQUENCY (e);
585 if (abs (sum - bb->frequency) > 100)
587 "Invalid sum of incomming frequencies %i, should be %i\n",
590 for (e = bb->pred; e; e = e->pred_next)
592 if (lsum - bb->count > 100 || lsum - bb->count < -100)
593 fprintf (file, "Invalid sum of incomming counts %i, should be %i\n",
594 (int)lsum, (int)bb->count);
596 for (e = bb->succ; e; e = e->succ_next)
598 if (bb->succ && (lsum - bb->count > 100 || lsum - bb->count < -100))
599 fprintf (file, "Invalid sum of incomming counts %i, should be %i\n",
600 (int)lsum, (int)bb->count);
607 debug_flow_info (void)
609 dump_flow_info (stderr);
613 dump_edge_info (FILE *file, edge e, int do_succ)
615 basic_block side = (do_succ ? e->dest : e->src);
617 if (side == ENTRY_BLOCK_PTR)
618 fputs (" ENTRY", file);
619 else if (side == EXIT_BLOCK_PTR)
620 fputs (" EXIT", file);
622 fprintf (file, " %d", side->index);
625 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
629 fprintf (file, " count:");
630 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
635 static const char * const bitnames[] = {
636 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
637 "can_fallthru", "irreducible", "sibcall"
640 int i, flags = e->flags;
643 for (i = 0; flags; i++)
644 if (flags & (1 << i))
650 if (i < (int) ARRAY_SIZE (bitnames))
651 fputs (bitnames[i], file);
653 fprintf (file, "%d", i);
661 /* Simple routines to easily allocate AUX fields of basic blocks. */
663 static struct obstack block_aux_obstack;
664 static void *first_block_aux_obj = 0;
665 static struct obstack edge_aux_obstack;
666 static void *first_edge_aux_obj = 0;
668 /* Allocate a memory block of SIZE as BB->aux. The obstack must
669 be first initialized by alloc_aux_for_blocks. */
672 alloc_aux_for_block (basic_block bb, int size)
674 /* Verify that aux field is clear. */
675 if (bb->aux || !first_block_aux_obj)
677 bb->aux = obstack_alloc (&block_aux_obstack, size);
678 memset (bb->aux, 0, size);
681 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
682 alloc_aux_for_block for each basic block. */
685 alloc_aux_for_blocks (int size)
687 static int initialized;
691 gcc_obstack_init (&block_aux_obstack);
695 /* Check whether AUX data are still allocated. */
696 else if (first_block_aux_obj)
698 first_block_aux_obj = (char *) obstack_alloc (&block_aux_obstack, 0);
703 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
704 alloc_aux_for_block (bb, size);
708 /* Clear AUX pointers of all blocks. */
711 clear_aux_for_blocks (void)
715 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
719 /* Free data allocated in block_aux_obstack and clear AUX pointers
723 free_aux_for_blocks (void)
725 if (!first_block_aux_obj)
727 obstack_free (&block_aux_obstack, first_block_aux_obj);
728 first_block_aux_obj = NULL;
730 clear_aux_for_blocks ();
733 /* Allocate a memory edge of SIZE as BB->aux. The obstack must
734 be first initialized by alloc_aux_for_edges. */
737 alloc_aux_for_edge (edge e, int size)
739 /* Verify that aux field is clear. */
740 if (e->aux || !first_edge_aux_obj)
742 e->aux = obstack_alloc (&edge_aux_obstack, size);
743 memset (e->aux, 0, size);
746 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
747 alloc_aux_for_edge for each basic edge. */
750 alloc_aux_for_edges (int size)
752 static int initialized;
756 gcc_obstack_init (&edge_aux_obstack);
760 /* Check whether AUX data are still allocated. */
761 else if (first_edge_aux_obj)
764 first_edge_aux_obj = (char *) obstack_alloc (&edge_aux_obstack, 0);
769 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
773 for (e = bb->succ; e; e = e->succ_next)
774 alloc_aux_for_edge (e, size);
779 /* Clear AUX pointers of all edges. */
782 clear_aux_for_edges (void)
787 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
789 for (e = bb->succ; e; e = e->succ_next)
794 /* Free data allocated in edge_aux_obstack and clear AUX pointers
798 free_aux_for_edges (void)
800 if (!first_edge_aux_obj)
802 obstack_free (&edge_aux_obstack, first_edge_aux_obj);
803 first_edge_aux_obj = NULL;
805 clear_aux_for_edges ();
808 /* Verify the CFG consistency.
810 Currently it does following checks edge and basic block list correctness
811 and calls into IL dependent checking then. */
813 verify_flow_info (void)
815 size_t *edge_checksum;
816 int num_bb_notes, err = 0;
817 basic_block bb, last_bb_seen;
818 basic_block *last_visited;
820 last_visited = (basic_block *) xcalloc (last_basic_block + 2,
821 sizeof (basic_block));
822 edge_checksum = (size_t *) xcalloc (last_basic_block + 2, sizeof (size_t));
824 /* Check bb chain & numbers. */
825 last_bb_seen = ENTRY_BLOCK_PTR;
826 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
828 if (bb != EXIT_BLOCK_PTR
829 && bb != BASIC_BLOCK (bb->index))
831 error ("bb %d on wrong place", bb->index);
835 if (bb->prev_bb != last_bb_seen)
837 error ("prev_bb of %d should be %d, not %d",
838 bb->index, last_bb_seen->index, bb->prev_bb->index);
845 /* Now check the basic blocks (boundaries etc.) */
846 FOR_EACH_BB_REVERSE (bb)
853 error ("verify_flow_info: Wrong count of block %i %i",
854 bb->index, (int)bb->count);
857 if (bb->frequency < 0)
859 error ("verify_flow_info: Wrong frequency of block %i %i",
860 bb->index, bb->frequency);
863 for (e = bb->succ; e; e = e->succ_next)
865 if (last_visited [e->dest->index + 2] == bb)
867 error ("verify_flow_info: Duplicate edge %i->%i",
868 e->src->index, e->dest->index);
871 if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
873 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
874 e->src->index, e->dest->index, e->probability);
879 error ("verify_flow_info: Wrong count of edge %i->%i %i",
880 e->src->index, e->dest->index, (int)e->count);
884 last_visited [e->dest->index + 2] = bb;
886 if (e->flags & EDGE_FALLTHRU)
891 error ("verify_flow_info: Basic block %d succ edge is corrupted",
893 fprintf (stderr, "Predecessor: ");
894 dump_edge_info (stderr, e, 0);
895 fprintf (stderr, "\nSuccessor: ");
896 dump_edge_info (stderr, e, 1);
897 fprintf (stderr, "\n");
901 edge_checksum[e->dest->index + 2] += (size_t) e;
905 error ("Wrong amount of branch edges after unconditional jump %i", bb->index);
909 for (e = bb->pred; e; e = e->pred_next)
913 error ("basic block %d pred edge is corrupted", bb->index);
914 fputs ("Predecessor: ", stderr);
915 dump_edge_info (stderr, e, 0);
916 fputs ("\nSuccessor: ", stderr);
917 dump_edge_info (stderr, e, 1);
918 fputc ('\n', stderr);
921 edge_checksum[e->dest->index + 2] -= (size_t) e;
925 /* Complete edge checksumming for ENTRY and EXIT. */
929 for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
930 edge_checksum[e->dest->index + 2] += (size_t) e;
932 for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
933 edge_checksum[e->dest->index + 2] -= (size_t) e;
936 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
937 if (edge_checksum[bb->index + 2])
939 error ("basic block %i edge lists are corrupted", bb->index);
944 last_bb_seen = ENTRY_BLOCK_PTR;
948 free (edge_checksum);
949 err |= cfg_hooks->cfgh_verify_flow_info ();
951 internal_error ("verify_flow_info failed");
954 /* Print out one basic block with live information at start and end. */
957 dump_bb (basic_block bb, FILE *outf)
961 fprintf (outf, ";; Basic block %d, loop depth %d, count ",
962 bb->index, bb->loop_depth);
963 fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
966 cfg_hooks->dump_bb (bb, outf);
968 fputs (";; Successors: ", outf);
969 for (e = bb->succ; e; e = e->succ_next)
970 dump_edge_info (outf, e, 1);
975 debug_bb (basic_block bb)
977 dump_bb (bb, stderr);
983 basic_block bb = BASIC_BLOCK (n);
984 dump_bb (bb, stderr);