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 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 with CFG and analyze it.
23 All other modules should not transform the datastructure directly and use
24 abstraction instead. The file is supposed to be ordered bottom-up and should
25 not contain any code dependent on particular intermediate language (RTL or trees)
27 Available functionality:
28 - Initialization/deallocation
29 init_flow, clear_edges
30 - Low level basic block manipulation
31 alloc_block, expunge_block
33 make_edge, make_single_succ_edge, cached_make_edge, remove_edge
34 - Low level edge redirection (without updating instruction chain)
35 redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
36 - Dumpipng and debugging
37 dump_flow_info, debug_flow_info, dump_edge_info
38 - Allocation of AUX fields for basic blocks
39 alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
46 #include "hard-reg-set.h"
47 #include "basic-block.h"
57 /* The obstack on which the flow graph components are allocated. */
59 struct obstack flow_obstack;
60 static char *flow_firstobj;
62 /* Number of basic blocks in the current function. */
66 /* Number of edges in the current function. */
70 /* First edge in the deleted edges chain. */
72 edge first_deleted_edge;
73 static basic_block first_deleted_block;
75 /* The basic block array. */
77 varray_type basic_block_info;
79 /* The special entry and exit blocks. */
81 struct basic_block_def entry_exit_blocks[2]
89 NULL, /* cond_local_set */
90 NULL, /* global_live_at_start */
91 NULL, /* global_live_at_end */
93 ENTRY_BLOCK, /* index */
102 NULL, /* head_tree */
106 NULL, /* local_set */
107 NULL, /* cond_local_set */
108 NULL, /* global_live_at_start */
109 NULL, /* global_live_at_end */
111 EXIT_BLOCK, /* index */
119 void debug_flow_info PARAMS ((void));
120 static void free_edge PARAMS ((edge));
122 /* Called once at intialization time. */
127 static int initialized;
129 first_deleted_edge = 0;
130 first_deleted_block = 0;
135 gcc_obstack_init (&flow_obstack);
136 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
141 obstack_free (&flow_obstack, flow_firstobj);
142 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
146 /* Helper function for remove_edge and clear_edges. Frees edge structure
147 without actually unlinking it from the pred/succ lists. */
154 memset (e, 0, sizeof (*e));
155 e->succ_next = first_deleted_edge;
156 first_deleted_edge = e;
159 /* Free the memory associated with the edge structures. */
167 for (i = 0; i < n_basic_blocks; ++i)
169 basic_block bb = BASIC_BLOCK (i);
174 edge next = e->succ_next;
183 e = ENTRY_BLOCK_PTR->succ;
186 edge next = e->succ_next;
191 EXIT_BLOCK_PTR->pred = NULL;
192 ENTRY_BLOCK_PTR->succ = NULL;
198 /* Allocate memory for basic_block. */
205 if (first_deleted_block)
207 bb = first_deleted_block;
208 first_deleted_block = (basic_block) bb->succ;
213 bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*bb));
214 memset (bb, 0, sizeof (*bb));
219 /* Remove block B from the basic block array and compact behind it. */
225 int i, n = n_basic_blocks;
227 for (i = b->index; i + 1 < n; ++i)
229 basic_block x = BASIC_BLOCK (i + 1);
234 /* Invalidate data to make bughunting easier. */
235 memset (b, 0, sizeof (*b));
237 basic_block_info->num_elements--;
239 b->succ = (edge) first_deleted_block;
240 first_deleted_block = (basic_block) b;
243 /* Create an edge connecting SRC and DST with FLAGS optionally using
244 edge cache CACHE. Return the new edge, NULL if already exist. */
247 cached_make_edge (edge_cache, src, dst, flags)
249 basic_block src, dst;
255 /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
256 many edges to them, and we didn't allocate memory for it. */
257 use_edge_cache = (edge_cache
258 && src != ENTRY_BLOCK_PTR
259 && dst != EXIT_BLOCK_PTR);
261 /* Make sure we don't add duplicate edges. */
262 switch (use_edge_cache)
265 /* Quick test for non-existence of the edge. */
266 if (! TEST_BIT (edge_cache[src->index], dst->index))
269 /* The edge exists; early exit if no work to do. */
275 for (e = src->succ; e; e = e->succ_next)
284 if (first_deleted_edge)
286 e = first_deleted_edge;
287 first_deleted_edge = e->succ_next;
291 e = (edge) obstack_alloc (&flow_obstack, sizeof (*e));
292 memset (e, 0, sizeof (*e));
296 e->succ_next = src->succ;
297 e->pred_next = dst->pred;
306 SET_BIT (edge_cache[src->index], dst->index);
311 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
312 created edge or NULL if already exist. */
315 make_edge (src, dest, flags)
316 basic_block src, dest;
319 return cached_make_edge (NULL, src, dest, flags);
322 /* Create an edge connecting SRC to DEST and set probability by knowling
323 that it is the single edge leaving SRC. */
326 make_single_succ_edge (src, dest, flags)
327 basic_block src, dest;
330 edge e = make_edge (src, dest, flags);
332 e->probability = REG_BR_PROB_BASE;
333 e->count = src->count;
337 /* This function will remove an edge from the flow graph. */
343 edge last_pred = NULL;
344 edge last_succ = NULL;
346 basic_block src, dest;
349 for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
355 last_succ->succ_next = e->succ_next;
357 src->succ = e->succ_next;
359 for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
365 last_pred->pred_next = e->pred_next;
367 dest->pred = e->pred_next;
372 /* Redirect an edge's successor from one block to another. */
375 redirect_edge_succ (e, new_succ)
377 basic_block new_succ;
381 /* Disconnect the edge from the old successor block. */
382 for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next)
384 *pe = (*pe)->pred_next;
386 /* Reconnect the edge to the new successor block. */
387 e->pred_next = new_succ->pred;
392 /* Like previous but avoid possible dupplicate edge. */
395 redirect_edge_succ_nodup (e, new_succ)
397 basic_block new_succ;
400 /* Check whether the edge is already present. */
401 for (s = e->src->succ; s; s = s->succ_next)
402 if (s->dest == new_succ && s != e)
406 s->flags |= e->flags;
407 s->probability += e->probability;
408 s->count += e->count;
413 redirect_edge_succ (e, new_succ);
417 /* Redirect an edge's predecessor from one block to another. */
420 redirect_edge_pred (e, new_pred)
422 basic_block new_pred;
426 /* Disconnect the edge from the old predecessor block. */
427 for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next)
429 *pe = (*pe)->succ_next;
431 /* Reconnect the edge to the new predecessor block. */
432 e->succ_next = new_pred->succ;
438 dump_flow_info (file)
442 static const char * const reg_class_names[] = REG_CLASS_NAMES;
444 fprintf (file, "%d registers.\n", max_regno);
445 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
448 enum reg_class class, altclass;
449 fprintf (file, "\nRegister %d used %d times across %d insns",
450 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
451 if (REG_BASIC_BLOCK (i) >= 0)
452 fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
454 fprintf (file, "; set %d time%s", REG_N_SETS (i),
455 (REG_N_SETS (i) == 1) ? "" : "s");
456 if (REG_USERVAR_P (regno_reg_rtx[i]))
457 fprintf (file, "; user var");
458 if (REG_N_DEATHS (i) != 1)
459 fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
460 if (REG_N_CALLS_CROSSED (i) == 1)
461 fprintf (file, "; crosses 1 call");
462 else if (REG_N_CALLS_CROSSED (i))
463 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
464 if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
465 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
466 class = reg_preferred_class (i);
467 altclass = reg_alternate_class (i);
468 if (class != GENERAL_REGS || altclass != ALL_REGS)
470 if (altclass == ALL_REGS || class == ALL_REGS)
471 fprintf (file, "; pref %s", reg_class_names[(int) class]);
472 else if (altclass == NO_REGS)
473 fprintf (file, "; %s or none", reg_class_names[(int) class]);
475 fprintf (file, "; pref %s, else %s",
476 reg_class_names[(int) class],
477 reg_class_names[(int) altclass]);
479 if (REG_POINTER (regno_reg_rtx[i]))
480 fprintf (file, "; pointer");
481 fprintf (file, ".\n");
484 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
485 for (i = 0; i < n_basic_blocks; i++)
487 basic_block bb = BASIC_BLOCK (i);
490 fprintf (file, "\nBasic block %d: first insn %d, last %d, loop_depth %d, count ",
491 i, INSN_UID (bb->head), INSN_UID (bb->end), bb->loop_depth);
492 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
493 fprintf (file, ", freq %i.\n", bb->frequency);
495 fprintf (file, "Predecessors: ");
496 for (e = bb->pred; e; e = e->pred_next)
497 dump_edge_info (file, e, 0);
499 fprintf (file, "\nSuccessors: ");
500 for (e = bb->succ; e; e = e->succ_next)
501 dump_edge_info (file, e, 1);
503 fprintf (file, "\nRegisters live at start:");
504 dump_regset (bb->global_live_at_start, file);
506 fprintf (file, "\nRegisters live at end:");
507 dump_regset (bb->global_live_at_end, file);
518 dump_flow_info (stderr);
522 dump_edge_info (file, e, do_succ)
527 basic_block side = (do_succ ? e->dest : e->src);
529 if (side == ENTRY_BLOCK_PTR)
530 fputs (" ENTRY", file);
531 else if (side == EXIT_BLOCK_PTR)
532 fputs (" EXIT", file);
534 fprintf (file, " %d", side->index);
537 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
541 fprintf (file, " count:");
542 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) e->count);
547 static const char * const bitnames[] = {
548 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back"
551 int i, flags = e->flags;
555 for (i = 0; flags; i++)
556 if (flags & (1 << i))
562 if (i < (int) ARRAY_SIZE (bitnames))
563 fputs (bitnames[i], file);
565 fprintf (file, "%d", i);
572 /* Simple routines to easily allocate AUX fields of basic blocks. */
573 static struct obstack block_aux_obstack;
574 static void *first_block_aux_obj = 0;
575 static struct obstack edge_aux_obstack;
576 static void *first_edge_aux_obj = 0;
578 /* Allocate an memory block of SIZE as BB->aux. The obstack must
579 be first initialized by alloc_aux_for_blocks. */
582 alloc_aux_for_block (bb, size)
586 /* Verify that aux field is clear. */
587 if (bb->aux || !first_block_aux_obj)
589 bb->aux = obstack_alloc (&block_aux_obstack, size);
590 memset (bb->aux, 0, size);
593 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
594 alloc_aux_for_block for each basic block. */
597 alloc_aux_for_blocks (size)
600 static int initialized;
604 gcc_obstack_init (&block_aux_obstack);
607 /* Check whether AUX data are still allocated. */
608 else if (first_block_aux_obj)
610 first_block_aux_obj = (char *) obstack_alloc (&block_aux_obstack, 0);
614 for (i = 0; i < n_basic_blocks; i++)
615 alloc_aux_for_block (BASIC_BLOCK (i), size);
616 alloc_aux_for_block (ENTRY_BLOCK_PTR, size);
617 alloc_aux_for_block (EXIT_BLOCK_PTR, size);
621 /* Clear AUX pointers of all blocks. */
624 clear_aux_for_blocks ()
628 for (i = 0; i < n_basic_blocks; i++)
629 BASIC_BLOCK (i)->aux = NULL;
630 ENTRY_BLOCK_PTR->aux = NULL;
631 EXIT_BLOCK_PTR->aux = NULL;
634 /* Free data allocated in block_aux_obstack and clear AUX pointers
638 free_aux_for_blocks ()
640 if (!first_block_aux_obj)
642 obstack_free (&block_aux_obstack, first_block_aux_obj);
643 first_block_aux_obj = NULL;
645 clear_aux_for_blocks ();
648 /* Allocate an memory edge of SIZE as BB->aux. The obstack must
649 be first initialized by alloc_aux_for_edges. */
652 alloc_aux_for_edge (e, size)
656 /* Verify that aux field is clear. */
657 if (e->aux || !first_edge_aux_obj)
659 e->aux = obstack_alloc (&edge_aux_obstack, size);
660 memset (e->aux, 0, size);
663 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
664 alloc_aux_for_edge for each basic edge. */
667 alloc_aux_for_edges (size)
670 static int initialized;
674 gcc_obstack_init (&edge_aux_obstack);
677 /* Check whether AUX data are still allocated. */
678 else if (first_edge_aux_obj)
680 first_edge_aux_obj = (char *) obstack_alloc (&edge_aux_obstack, 0);
684 for (i = -1; i < n_basic_blocks; i++)
690 bb = BASIC_BLOCK (i);
692 bb = ENTRY_BLOCK_PTR;
693 for (e = bb->succ; e; e = e->succ_next)
694 alloc_aux_for_edge (e, size);
699 /* Clear AUX pointers of all edges. */
702 clear_aux_for_edges ()
706 for (i = -1; i < n_basic_blocks; i++)
712 bb = BASIC_BLOCK (i);
714 bb = ENTRY_BLOCK_PTR;
715 for (e = bb->succ; e; e = e->succ_next)
720 /* Free data allocated in edge_aux_obstack and clear AUX pointers
724 free_aux_for_edges ()
726 if (!first_edge_aux_obj)
728 obstack_free (&edge_aux_obstack, first_edge_aux_obj);
729 first_edge_aux_obj = NULL;
731 clear_aux_for_edges ();