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 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
48 #include "hard-reg-set.h"
49 #include "basic-block.h"
59 /* The obstack on which the flow graph components are allocated. */
61 struct obstack flow_obstack;
62 static char *flow_firstobj;
64 /* Number of basic blocks in the current function. */
68 /* First free basic block number. */
71 /* Number of edges in the current function. */
75 /* First edge in the deleted edges chain. */
77 edge first_deleted_edge;
78 static basic_block first_deleted_block;
80 /* The basic block array. */
82 varray_type basic_block_info;
84 /* The special entry and exit blocks. */
86 struct basic_block_def entry_exit_blocks[2]
94 NULL, /* cond_local_set */
95 NULL, /* global_live_at_start */
96 NULL, /* global_live_at_end */
98 ENTRY_BLOCK, /* index */
100 EXIT_BLOCK_PTR, /* next_bb */
109 NULL, /* head_tree */
113 NULL, /* local_set */
114 NULL, /* cond_local_set */
115 NULL, /* global_live_at_start */
116 NULL, /* global_live_at_end */
118 EXIT_BLOCK, /* index */
119 ENTRY_BLOCK_PTR, /* prev_bb */
128 void debug_flow_info PARAMS ((void));
129 static void free_edge PARAMS ((edge));
131 /* Called once at initialization time. */
136 static int initialized;
138 first_deleted_edge = 0;
139 first_deleted_block = 0;
144 gcc_obstack_init (&flow_obstack);
145 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
150 obstack_free (&flow_obstack, flow_firstobj);
151 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
155 /* Helper function for remove_edge and clear_edges. Frees edge structure
156 without actually unlinking it from the pred/succ lists. */
163 memset (e, 0, sizeof *e);
164 e->succ_next = first_deleted_edge;
165 first_deleted_edge = e;
168 /* Free the memory associated with the edge structures. */
182 edge next = e->succ_next;
192 e = ENTRY_BLOCK_PTR->succ;
195 edge next = e->succ_next;
201 EXIT_BLOCK_PTR->pred = NULL;
202 ENTRY_BLOCK_PTR->succ = NULL;
208 /* Allocate memory for basic_block. */
215 if (first_deleted_block)
217 bb = first_deleted_block;
218 first_deleted_block = (basic_block) bb->succ;
223 bb = (basic_block) obstack_alloc (&flow_obstack, sizeof *bb);
224 memset (bb, 0, sizeof *bb);
229 /* Link block B to chain after AFTER. */
231 link_block (b, after)
232 basic_block b, after;
234 b->next_bb = after->next_bb;
237 b->next_bb->prev_bb = b;
240 /* Unlink block B from chain. */
245 b->next_bb->prev_bb = b->prev_bb;
246 b->prev_bb->next_bb = b->next_bb;
249 /* Sequentially order blocks and compact the arrays. */
253 basic_block *bbs = xcalloc (num_basic_blocks, sizeof (basic_block));
261 if (i != num_basic_blocks)
264 for (i = 0; i < num_basic_blocks; i++)
267 BASIC_BLOCK (i) = bbs[i];
269 last_basic_block = num_basic_blocks;
274 /* Remove block B from the basic block array. */
281 BASIC_BLOCK (b->sindex) = NULL;
284 /* Invalidate data to make bughunting easier. */
285 memset (b, 0, sizeof *b);
287 b->succ = (edge) first_deleted_block;
288 first_deleted_block = (basic_block) b;
291 /* Create an edge connecting SRC and DST with FLAGS optionally using
292 edge cache CACHE. Return the new edge, NULL if already exist. */
295 cached_make_edge (edge_cache, src, dst, flags)
297 basic_block src, dst;
303 /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
304 many edges to them, or we didn't allocate memory for it. */
305 use_edge_cache = (edge_cache
306 && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR);
308 /* Make sure we don't add duplicate edges. */
309 switch (use_edge_cache)
312 /* Quick test for non-existence of the edge. */
313 if (! TEST_BIT (edge_cache[src->sindex], dst->sindex))
316 /* The edge exists; early exit if no work to do. */
322 for (e = src->succ; e; e = e->succ_next)
331 if (first_deleted_edge)
333 e = first_deleted_edge;
334 first_deleted_edge = e->succ_next;
338 e = (edge) obstack_alloc (&flow_obstack, sizeof *e);
339 memset (e, 0, sizeof *e);
343 e->succ_next = src->succ;
344 e->pred_next = dst->pred;
353 SET_BIT (edge_cache[src->sindex], dst->sindex);
358 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
359 created edge or NULL if already exist. */
362 make_edge (src, dest, flags)
363 basic_block src, dest;
366 return cached_make_edge (NULL, src, dest, flags);
369 /* Create an edge connecting SRC to DEST and set probability by knowing
370 that it is the single edge leaving SRC. */
373 make_single_succ_edge (src, dest, flags)
374 basic_block src, dest;
377 edge e = make_edge (src, dest, flags);
379 e->probability = REG_BR_PROB_BASE;
380 e->count = src->count;
384 /* This function will remove an edge from the flow graph. */
390 edge last_pred = NULL;
391 edge last_succ = NULL;
393 basic_block src, dest;
397 for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
403 last_succ->succ_next = e->succ_next;
405 src->succ = e->succ_next;
407 for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
413 last_pred->pred_next = e->pred_next;
415 dest->pred = e->pred_next;
420 /* Redirect an edge's successor from one block to another. */
423 redirect_edge_succ (e, new_succ)
425 basic_block new_succ;
429 /* Disconnect the edge from the old successor block. */
430 for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next)
432 *pe = (*pe)->pred_next;
434 /* Reconnect the edge to the new successor block. */
435 e->pred_next = new_succ->pred;
440 /* Like previous but avoid possible duplicate edge. */
443 redirect_edge_succ_nodup (e, new_succ)
445 basic_block new_succ;
449 /* Check whether the edge is already present. */
450 for (s = e->src->succ; s; s = s->succ_next)
451 if (s->dest == new_succ && s != e)
456 s->flags |= e->flags;
457 s->probability += e->probability;
458 s->count += e->count;
463 redirect_edge_succ (e, new_succ);
468 /* Redirect an edge's predecessor from one block to another. */
471 redirect_edge_pred (e, new_pred)
473 basic_block new_pred;
477 /* Disconnect the edge from the old predecessor block. */
478 for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next)
481 *pe = (*pe)->succ_next;
483 /* Reconnect the edge to the new predecessor block. */
484 e->succ_next = new_pred->succ;
494 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
499 dump_flow_info (file)
504 static const char * const reg_class_names[] = REG_CLASS_NAMES;
506 fprintf (file, "%d registers.\n", max_regno);
507 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
510 enum reg_class class, altclass;
512 fprintf (file, "\nRegister %d used %d times across %d insns",
513 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
514 if (REG_BASIC_BLOCK (i) >= 0)
515 fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
517 fprintf (file, "; set %d time%s", REG_N_SETS (i),
518 (REG_N_SETS (i) == 1) ? "" : "s");
519 if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
520 fprintf (file, "; user var");
521 if (REG_N_DEATHS (i) != 1)
522 fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
523 if (REG_N_CALLS_CROSSED (i) == 1)
524 fprintf (file, "; crosses 1 call");
525 else if (REG_N_CALLS_CROSSED (i))
526 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
527 if (regno_reg_rtx[i] != NULL
528 && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
529 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
531 class = reg_preferred_class (i);
532 altclass = reg_alternate_class (i);
533 if (class != GENERAL_REGS || altclass != ALL_REGS)
535 if (altclass == ALL_REGS || class == ALL_REGS)
536 fprintf (file, "; pref %s", reg_class_names[(int) class]);
537 else if (altclass == NO_REGS)
538 fprintf (file, "; %s or none", reg_class_names[(int) class]);
540 fprintf (file, "; pref %s, else %s",
541 reg_class_names[(int) class],
542 reg_class_names[(int) altclass]);
545 if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
546 fprintf (file, "; pointer");
547 fprintf (file, ".\n");
550 fprintf (file, "\n%d basic blocks, %d edges.\n", num_basic_blocks, n_edges);
557 fprintf (file, "\nBasic block %d: first insn %d, last %d, ",
558 bb->sindex, INSN_UID (bb->head), INSN_UID (bb->end));
559 fprintf (file, "prev %d, next %d, ",
560 bb->prev_bb->sindex, bb->next_bb->sindex);
561 fprintf (file, "loop_depth %d, count ", bb->loop_depth);
562 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
563 fprintf (file, ", freq %i.\n", bb->frequency);
565 fprintf (file, "Predecessors: ");
566 for (e = bb->pred; e; e = e->pred_next)
567 dump_edge_info (file, e, 0);
569 fprintf (file, "\nSuccessors: ");
570 for (e = bb->succ; e; e = e->succ_next)
571 dump_edge_info (file, e, 1);
573 fprintf (file, "\nRegisters live at start:");
574 dump_regset (bb->global_live_at_start, file);
576 fprintf (file, "\nRegisters live at end:");
577 dump_regset (bb->global_live_at_end, file);
581 /* Check the consistency of profile information. We can't do that
582 in verify_flow_info, as the counts may get invalid for incompletely
583 solved graphs, later elliminating of conditionals or roundoff errors.
584 It is still practical to have them reported for debugging of simple
587 for (e = bb->succ; e; e = e->succ_next)
588 sum += e->probability;
589 if (bb->succ && abs (sum - REG_BR_PROB_BASE) > 100)
590 fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
591 sum * 100.0 / REG_BR_PROB_BASE);
593 for (e = bb->pred; e; e = e->pred_next)
594 sum += EDGE_FREQUENCY (e);
595 if (abs (sum - bb->frequency) > 100)
597 "Invalid sum of incomming frequencies %i, should be %i\n",
600 for (e = bb->pred; e; e = e->pred_next)
602 if (lsum - bb->count > 100 || lsum - bb->count < -100)
603 fprintf (file, "Invalid sum of incomming counts %i, should be %i\n",
604 (int)lsum, (int)bb->count);
606 for (e = bb->succ; e; e = e->succ_next)
608 if (bb->succ && (lsum - bb->count > 100 || lsum - bb->count < -100))
609 fprintf (file, "Invalid sum of incomming counts %i, should be %i\n",
610 (int)lsum, (int)bb->count);
619 dump_flow_info (stderr);
623 dump_edge_info (file, e, do_succ)
628 basic_block side = (do_succ ? e->dest : e->src);
630 if (side == ENTRY_BLOCK_PTR)
631 fputs (" ENTRY", file);
632 else if (side == EXIT_BLOCK_PTR)
633 fputs (" EXIT", file);
635 fprintf (file, " %d", side->sindex);
638 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
642 fprintf (file, " count:");
643 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
648 static const char * const bitnames[]
649 = {"fallthru", "ab", "abcall", "eh", "fake", "dfs_back", "can_fallthru"};
651 int i, flags = e->flags;
654 for (i = 0; flags; i++)
655 if (flags & (1 << i))
661 if (i < (int) ARRAY_SIZE (bitnames))
662 fputs (bitnames[i], file);
664 fprintf (file, "%d", i);
672 /* Simple routines to easily allocate AUX fields of basic blocks. */
674 static struct obstack block_aux_obstack;
675 static void *first_block_aux_obj = 0;
676 static struct obstack edge_aux_obstack;
677 static void *first_edge_aux_obj = 0;
679 /* Allocate an memory block of SIZE as BB->aux. The obstack must
680 be first initialized by alloc_aux_for_blocks. */
683 alloc_aux_for_block (bb, size)
687 /* Verify that aux field is clear. */
688 if (bb->aux || !first_block_aux_obj)
690 bb->aux = obstack_alloc (&block_aux_obstack, size);
691 memset (bb->aux, 0, size);
694 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
695 alloc_aux_for_block for each basic block. */
698 alloc_aux_for_blocks (size)
701 static int initialized;
705 gcc_obstack_init (&block_aux_obstack);
709 /* Check whether AUX data are still allocated. */
710 else if (first_block_aux_obj)
712 first_block_aux_obj = (char *) obstack_alloc (&block_aux_obstack, 0);
718 alloc_aux_for_block (bb, size);
720 alloc_aux_for_block (ENTRY_BLOCK_PTR, size);
721 alloc_aux_for_block (EXIT_BLOCK_PTR, size);
725 /* Clear AUX pointers of all blocks. */
728 clear_aux_for_blocks ()
732 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
736 /* Free data allocated in block_aux_obstack and clear AUX pointers
740 free_aux_for_blocks ()
742 if (!first_block_aux_obj)
744 obstack_free (&block_aux_obstack, first_block_aux_obj);
745 first_block_aux_obj = NULL;
747 clear_aux_for_blocks ();
750 /* Allocate an memory edge of SIZE as BB->aux. The obstack must
751 be first initialized by alloc_aux_for_edges. */
754 alloc_aux_for_edge (e, size)
758 /* Verify that aux field is clear. */
759 if (e->aux || !first_edge_aux_obj)
761 e->aux = obstack_alloc (&edge_aux_obstack, size);
762 memset (e->aux, 0, size);
765 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
766 alloc_aux_for_edge for each basic edge. */
769 alloc_aux_for_edges (size)
772 static int initialized;
776 gcc_obstack_init (&edge_aux_obstack);
780 /* Check whether AUX data are still allocated. */
781 else if (first_edge_aux_obj)
784 first_edge_aux_obj = (char *) obstack_alloc (&edge_aux_obstack, 0);
789 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
793 for (e = bb->succ; e; e = e->succ_next)
794 alloc_aux_for_edge (e, size);
799 /* Clear AUX pointers of all edges. */
802 clear_aux_for_edges ()
806 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
810 for (e = bb->succ; e; e = e->succ_next)
815 /* Free data allocated in edge_aux_obstack and clear AUX pointers
819 free_aux_for_edges ()
821 if (!first_edge_aux_obj)
823 obstack_free (&edge_aux_obstack, first_edge_aux_obj);
824 first_edge_aux_obj = NULL;
826 clear_aux_for_edges ();
829 /* The same as BASIC_BLOCK, but usable from debugger. */
834 return BASIC_BLOCK (num);