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
46 #include "coretypes.h"
50 #include "hard-reg-set.h"
51 #include "basic-block.h"
61 /* The obstack on which the flow graph components are allocated. */
63 struct obstack flow_obstack;
64 static char *flow_firstobj;
66 /* Number of basic blocks in the current function. */
70 /* First free basic block number. */
74 /* Number of edges in the current function. */
78 /* First edge in the deleted edges chain. */
80 edge first_deleted_edge;
81 static basic_block first_deleted_block;
83 /* The basic block array. */
85 varray_type basic_block_info;
87 /* The special entry and exit blocks. */
89 struct basic_block_def entry_exit_blocks[2]
97 NULL, /* cond_local_set */
98 NULL, /* global_live_at_start */
99 NULL, /* global_live_at_end */
101 ENTRY_BLOCK, /* index */
103 EXIT_BLOCK_PTR, /* next_bb */
105 NULL, /* loop_father */
113 NULL, /* head_tree */
117 NULL, /* local_set */
118 NULL, /* cond_local_set */
119 NULL, /* global_live_at_start */
120 NULL, /* global_live_at_end */
122 EXIT_BLOCK, /* index */
123 ENTRY_BLOCK_PTR, /* prev_bb */
126 NULL, /* loop_father */
133 void debug_flow_info PARAMS ((void));
134 static void free_edge PARAMS ((edge));
136 /* Called once at initialization time. */
141 static int initialized;
143 first_deleted_edge = 0;
144 first_deleted_block = 0;
149 gcc_obstack_init (&flow_obstack);
150 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
155 obstack_free (&flow_obstack, flow_firstobj);
156 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
160 /* Helper function for remove_edge and clear_edges. Frees edge structure
161 without actually unlinking it from the pred/succ lists. */
168 memset (e, 0, sizeof *e);
169 e->succ_next = first_deleted_edge;
170 first_deleted_edge = e;
173 /* Free the memory associated with the edge structures. */
187 edge next = e->succ_next;
197 e = ENTRY_BLOCK_PTR->succ;
200 edge next = e->succ_next;
206 EXIT_BLOCK_PTR->pred = NULL;
207 ENTRY_BLOCK_PTR->succ = NULL;
213 /* Allocate memory for basic_block. */
220 if (first_deleted_block)
222 bb = first_deleted_block;
223 first_deleted_block = (basic_block) bb->succ;
228 bb = (basic_block) obstack_alloc (&flow_obstack, sizeof *bb);
229 memset (bb, 0, sizeof *bb);
234 /* Link block B to chain after AFTER. */
236 link_block (b, after)
237 basic_block b, after;
239 b->next_bb = after->next_bb;
242 b->next_bb->prev_bb = b;
245 /* Unlink block B from chain. */
250 b->next_bb->prev_bb = b->prev_bb;
251 b->prev_bb->next_bb = b->next_bb;
254 /* Sequentially order blocks and compact the arrays. */
264 BASIC_BLOCK (i) = bb;
269 if (i != n_basic_blocks)
272 last_basic_block = n_basic_blocks;
276 /* Remove block B from the basic block array. */
283 BASIC_BLOCK (b->index) = NULL;
286 /* Invalidate data to make bughunting easier. */
287 memset (b, 0, sizeof *b);
289 b->succ = (edge) first_deleted_block;
290 first_deleted_block = (basic_block) b;
293 /* Create an edge connecting SRC and DST with FLAGS optionally using
294 edge cache CACHE. Return the new edge, NULL if already exist. */
297 cached_make_edge (edge_cache, src, dst, flags)
299 basic_block src, dst;
305 /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
306 many edges to them, or we didn't allocate memory for it. */
307 use_edge_cache = (edge_cache
308 && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR);
310 /* Make sure we don't add duplicate edges. */
311 switch (use_edge_cache)
314 /* Quick test for non-existence of the edge. */
315 if (! TEST_BIT (edge_cache[src->index], dst->index))
318 /* The edge exists; early exit if no work to do. */
324 for (e = src->succ; e; e = e->succ_next)
333 if (first_deleted_edge)
335 e = first_deleted_edge;
336 first_deleted_edge = e->succ_next;
340 e = (edge) obstack_alloc (&flow_obstack, sizeof *e);
341 memset (e, 0, sizeof *e);
345 e->succ_next = src->succ;
346 e->pred_next = dst->pred;
355 SET_BIT (edge_cache[src->index], dst->index);
360 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
361 created edge or NULL if already exist. */
364 make_edge (src, dest, flags)
365 basic_block src, dest;
368 return cached_make_edge (NULL, src, dest, flags);
371 /* Create an edge connecting SRC to DEST and set probability by knowing
372 that it is the single edge leaving SRC. */
375 make_single_succ_edge (src, dest, flags)
376 basic_block src, dest;
379 edge e = make_edge (src, dest, flags);
381 e->probability = REG_BR_PROB_BASE;
382 e->count = src->count;
386 /* This function will remove an edge from the flow graph. */
392 edge last_pred = NULL;
393 edge last_succ = NULL;
395 basic_block src, dest;
399 for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
405 last_succ->succ_next = e->succ_next;
407 src->succ = e->succ_next;
409 for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
415 last_pred->pred_next = e->pred_next;
417 dest->pred = e->pred_next;
422 /* Redirect an edge's successor from one block to another. */
425 redirect_edge_succ (e, new_succ)
427 basic_block new_succ;
431 /* Disconnect the edge from the old successor block. */
432 for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next)
434 *pe = (*pe)->pred_next;
436 /* Reconnect the edge to the new successor block. */
437 e->pred_next = new_succ->pred;
442 /* Like previous but avoid possible duplicate edge. */
445 redirect_edge_succ_nodup (e, new_succ)
447 basic_block new_succ;
451 /* Check whether the edge is already present. */
452 for (s = e->src->succ; s; s = s->succ_next)
453 if (s->dest == new_succ && s != e)
458 s->flags |= e->flags;
459 s->probability += e->probability;
460 if (s->probability > REG_BR_PROB_BASE)
461 s->probability = REG_BR_PROB_BASE;
462 s->count += e->count;
467 redirect_edge_succ (e, new_succ);
472 /* Redirect an edge's predecessor from one block to another. */
475 redirect_edge_pred (e, new_pred)
477 basic_block new_pred;
481 /* Disconnect the edge from the old predecessor block. */
482 for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next)
485 *pe = (*pe)->succ_next;
487 /* Reconnect the edge to the new predecessor block. */
488 e->succ_next = new_pred->succ;
498 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
503 dump_flow_info (file)
507 int max_regno = max_reg_num ();
509 static const char * const reg_class_names[] = REG_CLASS_NAMES;
511 fprintf (file, "%d registers.\n", max_regno);
512 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
515 enum reg_class class, altclass;
517 fprintf (file, "\nRegister %d used %d times across %d insns",
518 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
519 if (REG_BASIC_BLOCK (i) >= 0)
520 fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
522 fprintf (file, "; set %d time%s", REG_N_SETS (i),
523 (REG_N_SETS (i) == 1) ? "" : "s");
524 if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
525 fprintf (file, "; user var");
526 if (REG_N_DEATHS (i) != 1)
527 fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
528 if (REG_N_CALLS_CROSSED (i) == 1)
529 fprintf (file, "; crosses 1 call");
530 else if (REG_N_CALLS_CROSSED (i))
531 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
532 if (regno_reg_rtx[i] != NULL
533 && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
534 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
536 class = reg_preferred_class (i);
537 altclass = reg_alternate_class (i);
538 if (class != GENERAL_REGS || altclass != ALL_REGS)
540 if (altclass == ALL_REGS || class == ALL_REGS)
541 fprintf (file, "; pref %s", reg_class_names[(int) class]);
542 else if (altclass == NO_REGS)
543 fprintf (file, "; %s or none", reg_class_names[(int) class]);
545 fprintf (file, "; pref %s, else %s",
546 reg_class_names[(int) class],
547 reg_class_names[(int) altclass]);
550 if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
551 fprintf (file, "; pointer");
552 fprintf (file, ".\n");
555 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
562 fprintf (file, "\nBasic block %d: first insn %d, last %d, ",
563 bb->index, INSN_UID (bb->head), INSN_UID (bb->end));
564 fprintf (file, "prev %d, next %d, ",
565 bb->prev_bb->index, bb->next_bb->index);
566 fprintf (file, "loop_depth %d, count ", bb->loop_depth);
567 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
568 fprintf (file, ", freq %i", bb->frequency);
569 if (maybe_hot_bb_p (bb))
570 fprintf (file, ", maybe hot");
571 if (probably_never_executed_bb_p (bb))
572 fprintf (file, ", probably never executed");
573 fprintf (file, ".\n");
575 fprintf (file, "Predecessors: ");
576 for (e = bb->pred; e; e = e->pred_next)
577 dump_edge_info (file, e, 0);
579 fprintf (file, "\nSuccessors: ");
580 for (e = bb->succ; e; e = e->succ_next)
581 dump_edge_info (file, e, 1);
583 fprintf (file, "\nRegisters live at start:");
584 dump_regset (bb->global_live_at_start, file);
586 fprintf (file, "\nRegisters live at end:");
587 dump_regset (bb->global_live_at_end, file);
591 /* Check the consistency of profile information. We can't do that
592 in verify_flow_info, as the counts may get invalid for incompletely
593 solved graphs, later elliminating of conditionals or roundoff errors.
594 It is still practical to have them reported for debugging of simple
597 for (e = bb->succ; e; e = e->succ_next)
598 sum += e->probability;
599 if (bb->succ && abs (sum - REG_BR_PROB_BASE) > 100)
600 fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
601 sum * 100.0 / REG_BR_PROB_BASE);
603 for (e = bb->pred; e; e = e->pred_next)
604 sum += EDGE_FREQUENCY (e);
605 if (abs (sum - bb->frequency) > 100)
607 "Invalid sum of incomming frequencies %i, should be %i\n",
610 for (e = bb->pred; e; e = e->pred_next)
612 if (lsum - bb->count > 100 || lsum - bb->count < -100)
613 fprintf (file, "Invalid sum of incomming counts %i, should be %i\n",
614 (int)lsum, (int)bb->count);
616 for (e = bb->succ; e; e = e->succ_next)
618 if (bb->succ && (lsum - bb->count > 100 || lsum - bb->count < -100))
619 fprintf (file, "Invalid sum of incomming counts %i, should be %i\n",
620 (int)lsum, (int)bb->count);
629 dump_flow_info (stderr);
633 dump_edge_info (file, e, do_succ)
638 basic_block side = (do_succ ? e->dest : e->src);
640 if (side == ENTRY_BLOCK_PTR)
641 fputs (" ENTRY", file);
642 else if (side == EXIT_BLOCK_PTR)
643 fputs (" EXIT", file);
645 fprintf (file, " %d", side->index);
648 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
652 fprintf (file, " count:");
653 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
658 static const char * const bitnames[]
659 = {"fallthru", "ab", "abcall", "eh", "fake", "dfs_back", "can_fallthru"};
661 int i, flags = e->flags;
664 for (i = 0; flags; i++)
665 if (flags & (1 << i))
671 if (i < (int) ARRAY_SIZE (bitnames))
672 fputs (bitnames[i], file);
674 fprintf (file, "%d", i);
682 /* Simple routines to easily allocate AUX fields of basic blocks. */
684 static struct obstack block_aux_obstack;
685 static void *first_block_aux_obj = 0;
686 static struct obstack edge_aux_obstack;
687 static void *first_edge_aux_obj = 0;
689 /* Allocate a memory block of SIZE as BB->aux. The obstack must
690 be first initialized by alloc_aux_for_blocks. */
693 alloc_aux_for_block (bb, size)
697 /* Verify that aux field is clear. */
698 if (bb->aux || !first_block_aux_obj)
700 bb->aux = obstack_alloc (&block_aux_obstack, size);
701 memset (bb->aux, 0, size);
704 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
705 alloc_aux_for_block for each basic block. */
708 alloc_aux_for_blocks (size)
711 static int initialized;
715 gcc_obstack_init (&block_aux_obstack);
719 /* Check whether AUX data are still allocated. */
720 else if (first_block_aux_obj)
722 first_block_aux_obj = (char *) obstack_alloc (&block_aux_obstack, 0);
727 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
728 alloc_aux_for_block (bb, size);
732 /* Clear AUX pointers of all blocks. */
735 clear_aux_for_blocks ()
739 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
743 /* Free data allocated in block_aux_obstack and clear AUX pointers
747 free_aux_for_blocks ()
749 if (!first_block_aux_obj)
751 obstack_free (&block_aux_obstack, first_block_aux_obj);
752 first_block_aux_obj = NULL;
754 clear_aux_for_blocks ();
757 /* Allocate a memory edge of SIZE as BB->aux. The obstack must
758 be first initialized by alloc_aux_for_edges. */
761 alloc_aux_for_edge (e, size)
765 /* Verify that aux field is clear. */
766 if (e->aux || !first_edge_aux_obj)
768 e->aux = obstack_alloc (&edge_aux_obstack, size);
769 memset (e->aux, 0, size);
772 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
773 alloc_aux_for_edge for each basic edge. */
776 alloc_aux_for_edges (size)
779 static int initialized;
783 gcc_obstack_init (&edge_aux_obstack);
787 /* Check whether AUX data are still allocated. */
788 else if (first_edge_aux_obj)
791 first_edge_aux_obj = (char *) obstack_alloc (&edge_aux_obstack, 0);
796 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
800 for (e = bb->succ; e; e = e->succ_next)
801 alloc_aux_for_edge (e, size);
806 /* Clear AUX pointers of all edges. */
809 clear_aux_for_edges ()
814 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
816 for (e = bb->succ; e; e = e->succ_next)
821 /* Free data allocated in edge_aux_obstack and clear AUX pointers
825 free_aux_for_edges ()
827 if (!first_edge_aux_obj)
829 obstack_free (&edge_aux_obstack, first_edge_aux_obj);
830 first_edge_aux_obj = NULL;
832 clear_aux_for_edges ();