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 /* Number of edges in the current function. */
72 /* First edge in the deleted edges chain. */
74 edge first_deleted_edge;
75 static basic_block first_deleted_block;
77 /* The basic block array. */
79 varray_type basic_block_info;
81 /* The special entry and exit blocks. */
83 struct basic_block_def entry_exit_blocks[2]
91 NULL, /* cond_local_set */
92 NULL, /* global_live_at_start */
93 NULL, /* global_live_at_end */
95 ENTRY_BLOCK, /* index */
104 NULL, /* head_tree */
108 NULL, /* local_set */
109 NULL, /* cond_local_set */
110 NULL, /* global_live_at_start */
111 NULL, /* global_live_at_end */
113 EXIT_BLOCK, /* index */
121 void debug_flow_info PARAMS ((void));
122 static void free_edge PARAMS ((edge));
124 /* Called once at initialization time. */
129 static int initialized;
131 first_deleted_edge = 0;
132 first_deleted_block = 0;
137 gcc_obstack_init (&flow_obstack);
138 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
143 obstack_free (&flow_obstack, flow_firstobj);
144 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
148 /* Helper function for remove_edge and clear_edges. Frees edge structure
149 without actually unlinking it from the pred/succ lists. */
156 memset (e, 0, sizeof *e);
157 e->succ_next = first_deleted_edge;
158 first_deleted_edge = e;
161 /* Free the memory associated with the edge structures. */
169 for (i = 0; i < n_basic_blocks; ++i)
171 basic_block bb = BASIC_BLOCK (i);
176 edge next = e->succ_next;
186 e = ENTRY_BLOCK_PTR->succ;
189 edge next = e->succ_next;
195 EXIT_BLOCK_PTR->pred = NULL;
196 ENTRY_BLOCK_PTR->succ = NULL;
202 /* Allocate memory for basic_block. */
209 if (first_deleted_block)
211 bb = first_deleted_block;
212 first_deleted_block = (basic_block) bb->succ;
217 bb = (basic_block) obstack_alloc (&flow_obstack, sizeof *bb);
218 memset (bb, 0, sizeof *bb);
223 /* Remove block B from the basic block array and compact behind it. */
229 int i, n = n_basic_blocks;
231 for (i = b->index; i + 1 < n; ++i)
233 basic_block x = BASIC_BLOCK (i + 1);
238 /* Invalidate data to make bughunting easier. */
239 memset (b, 0, sizeof *b);
241 basic_block_info->num_elements--;
243 b->succ = (edge) first_deleted_block;
244 first_deleted_block = (basic_block) b;
247 /* Create an edge connecting SRC and DST with FLAGS optionally using
248 edge cache CACHE. Return the new edge, NULL if already exist. */
251 cached_make_edge (edge_cache, src, dst, flags)
253 basic_block src, dst;
259 /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
260 many edges to them, or we didn't allocate memory for it. */
261 use_edge_cache = (edge_cache
262 && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR);
264 /* Make sure we don't add duplicate edges. */
265 switch (use_edge_cache)
268 /* Quick test for non-existence of the edge. */
269 if (! TEST_BIT (edge_cache[src->index], dst->index))
272 /* The edge exists; early exit if no work to do. */
278 for (e = src->succ; e; e = e->succ_next)
287 if (first_deleted_edge)
289 e = first_deleted_edge;
290 first_deleted_edge = e->succ_next;
294 e = (edge) obstack_alloc (&flow_obstack, sizeof *e);
295 memset (e, 0, sizeof *e);
299 e->succ_next = src->succ;
300 e->pred_next = dst->pred;
309 SET_BIT (edge_cache[src->index], dst->index);
314 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
315 created edge or NULL if already exist. */
318 make_edge (src, dest, flags)
319 basic_block src, dest;
322 return cached_make_edge (NULL, src, dest, flags);
325 /* Create an edge connecting SRC to DEST and set probability by knowing
326 that it is the single edge leaving SRC. */
329 make_single_succ_edge (src, dest, flags)
330 basic_block src, dest;
333 edge e = make_edge (src, dest, flags);
335 e->probability = REG_BR_PROB_BASE;
336 e->count = src->count;
340 /* This function will remove an edge from the flow graph. */
346 edge last_pred = NULL;
347 edge last_succ = NULL;
349 basic_block src, dest;
353 for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
359 last_succ->succ_next = e->succ_next;
361 src->succ = e->succ_next;
363 for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
369 last_pred->pred_next = e->pred_next;
371 dest->pred = e->pred_next;
376 /* Redirect an edge's successor from one block to another. */
379 redirect_edge_succ (e, new_succ)
381 basic_block new_succ;
385 /* Disconnect the edge from the old successor block. */
386 for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next)
388 *pe = (*pe)->pred_next;
390 /* Reconnect the edge to the new successor block. */
391 e->pred_next = new_succ->pred;
396 /* Like previous but avoid possible duplicate edge. */
399 redirect_edge_succ_nodup (e, new_succ)
401 basic_block new_succ;
405 /* Check whether the edge is already present. */
406 for (s = e->src->succ; s; s = s->succ_next)
407 if (s->dest == new_succ && s != e)
412 s->flags |= e->flags;
413 s->probability += e->probability;
414 s->count += e->count;
419 redirect_edge_succ (e, new_succ);
424 /* Redirect an edge's predecessor from one block to another. */
427 redirect_edge_pred (e, new_pred)
429 basic_block new_pred;
433 /* Disconnect the edge from the old predecessor block. */
434 for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next)
437 *pe = (*pe)->succ_next;
439 /* Reconnect the edge to the new predecessor block. */
440 e->succ_next = new_pred->succ;
449 ENTRY_BLOCK_PTR->flags = 0;
450 EXIT_BLOCK_PTR->flags = 0;
451 for (i = 0; i < n_basic_blocks; i++)
452 BASIC_BLOCK (i)->flags = 0;
456 dump_flow_info (file)
460 static const char * const reg_class_names[] = REG_CLASS_NAMES;
462 fprintf (file, "%d registers.\n", max_regno);
463 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
466 enum reg_class class, altclass;
468 fprintf (file, "\nRegister %d used %d times across %d insns",
469 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
470 if (REG_BASIC_BLOCK (i) >= 0)
471 fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
473 fprintf (file, "; set %d time%s", REG_N_SETS (i),
474 (REG_N_SETS (i) == 1) ? "" : "s");
475 if (REG_USERVAR_P (regno_reg_rtx[i]))
476 fprintf (file, "; user var");
477 if (REG_N_DEATHS (i) != 1)
478 fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
479 if (REG_N_CALLS_CROSSED (i) == 1)
480 fprintf (file, "; crosses 1 call");
481 else if (REG_N_CALLS_CROSSED (i))
482 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
483 if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
484 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
486 class = reg_preferred_class (i);
487 altclass = reg_alternate_class (i);
488 if (class != GENERAL_REGS || altclass != ALL_REGS)
490 if (altclass == ALL_REGS || class == ALL_REGS)
491 fprintf (file, "; pref %s", reg_class_names[(int) class]);
492 else if (altclass == NO_REGS)
493 fprintf (file, "; %s or none", reg_class_names[(int) class]);
495 fprintf (file, "; pref %s, else %s",
496 reg_class_names[(int) class],
497 reg_class_names[(int) altclass]);
500 if (REG_POINTER (regno_reg_rtx[i]))
501 fprintf (file, "; pointer");
502 fprintf (file, ".\n");
505 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
506 for (i = 0; i < n_basic_blocks; i++)
508 basic_block bb = BASIC_BLOCK (i);
513 fprintf (file, "\nBasic block %d: first insn %d, last %d, ",
514 i, INSN_UID (bb->head), INSN_UID (bb->end));
515 fprintf (file, "loop_depth %d, count ", bb->loop_depth);
516 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
517 fprintf (file, ", freq %i.\n", bb->frequency);
519 fprintf (file, "Predecessors: ");
520 for (e = bb->pred; e; e = e->pred_next)
521 dump_edge_info (file, e, 0);
523 fprintf (file, "\nSuccessors: ");
524 for (e = bb->succ; e; e = e->succ_next)
525 dump_edge_info (file, e, 1);
527 fprintf (file, "\nRegisters live at start:");
528 dump_regset (bb->global_live_at_start, file);
530 fprintf (file, "\nRegisters live at end:");
531 dump_regset (bb->global_live_at_end, file);
535 /* Check the consistency of profile information. We can't do that
536 in verify_flow_info, as the counts may get invalid for incompletely
537 solved graphs, later elliminating of conditionals or roundoff errors.
538 It is still practical to have them reported for debugging of simple
541 for (e = bb->succ; e; e = e->succ_next)
542 sum += e->probability;
543 if (bb->succ && abs (sum - REG_BR_PROB_BASE) > 100)
544 fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
545 sum * 100.0 / REG_BR_PROB_BASE);
547 for (e = bb->pred; e; e = e->pred_next)
548 sum += EDGE_FREQUENCY (e);
549 if (abs (sum - bb->frequency) > 100)
551 "Invalid sum of incomming frequencies %i, should be %i\n",
554 for (e = bb->pred; e; e = e->pred_next)
556 if (lsum - bb->count > 100 || lsum - bb->count < -100)
557 fprintf (file, "Invalid sum of incomming counts %i, should be %i\n",
558 (int)lsum, (int)bb->count);
560 for (e = bb->succ; e; e = e->succ_next)
562 if (bb->succ && (lsum - bb->count > 100 || lsum - bb->count < -100))
563 fprintf (file, "Invalid sum of incomming counts %i, should be %i\n",
564 (int)lsum, (int)bb->count);
573 dump_flow_info (stderr);
577 dump_edge_info (file, e, do_succ)
582 basic_block side = (do_succ ? e->dest : e->src);
584 if (side == ENTRY_BLOCK_PTR)
585 fputs (" ENTRY", file);
586 else if (side == EXIT_BLOCK_PTR)
587 fputs (" EXIT", file);
589 fprintf (file, " %d", side->index);
592 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
596 fprintf (file, " count:");
597 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
602 static const char * const bitnames[]
603 = {"fallthru", "ab", "abcall", "eh", "fake", "dfs_back"};
605 int i, flags = e->flags;
608 for (i = 0; flags; i++)
609 if (flags & (1 << i))
615 if (i < (int) ARRAY_SIZE (bitnames))
616 fputs (bitnames[i], file);
618 fprintf (file, "%d", i);
626 /* Simple routines to easily allocate AUX fields of basic blocks. */
628 static struct obstack block_aux_obstack;
629 static void *first_block_aux_obj = 0;
630 static struct obstack edge_aux_obstack;
631 static void *first_edge_aux_obj = 0;
633 /* Allocate an memory block of SIZE as BB->aux. The obstack must
634 be first initialized by alloc_aux_for_blocks. */
637 alloc_aux_for_block (bb, size)
641 /* Verify that aux field is clear. */
642 if (bb->aux || !first_block_aux_obj)
644 bb->aux = obstack_alloc (&block_aux_obstack, size);
645 memset (bb->aux, 0, size);
648 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
649 alloc_aux_for_block for each basic block. */
652 alloc_aux_for_blocks (size)
655 static int initialized;
659 gcc_obstack_init (&block_aux_obstack);
663 /* Check whether AUX data are still allocated. */
664 else if (first_block_aux_obj)
666 first_block_aux_obj = (char *) obstack_alloc (&block_aux_obstack, 0);
671 for (i = 0; i < n_basic_blocks; i++)
672 alloc_aux_for_block (BASIC_BLOCK (i), size);
674 alloc_aux_for_block (ENTRY_BLOCK_PTR, size);
675 alloc_aux_for_block (EXIT_BLOCK_PTR, size);
679 /* Clear AUX pointers of all blocks. */
682 clear_aux_for_blocks ()
686 for (i = 0; i < n_basic_blocks; i++)
687 BASIC_BLOCK (i)->aux = NULL;
689 ENTRY_BLOCK_PTR->aux = NULL;
690 EXIT_BLOCK_PTR->aux = NULL;
693 /* Free data allocated in block_aux_obstack and clear AUX pointers
697 free_aux_for_blocks ()
699 if (!first_block_aux_obj)
701 obstack_free (&block_aux_obstack, first_block_aux_obj);
702 first_block_aux_obj = NULL;
704 clear_aux_for_blocks ();
707 /* Allocate an memory edge of SIZE as BB->aux. The obstack must
708 be first initialized by alloc_aux_for_edges. */
711 alloc_aux_for_edge (e, size)
715 /* Verify that aux field is clear. */
716 if (e->aux || !first_edge_aux_obj)
718 e->aux = obstack_alloc (&edge_aux_obstack, size);
719 memset (e->aux, 0, size);
722 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
723 alloc_aux_for_edge for each basic edge. */
726 alloc_aux_for_edges (size)
729 static int initialized;
733 gcc_obstack_init (&edge_aux_obstack);
737 /* Check whether AUX data are still allocated. */
738 else if (first_edge_aux_obj)
741 first_edge_aux_obj = (char *) obstack_alloc (&edge_aux_obstack, 0);
745 for (i = -1; i < n_basic_blocks; i++)
751 bb = BASIC_BLOCK (i);
753 bb = ENTRY_BLOCK_PTR;
755 for (e = bb->succ; e; e = e->succ_next)
756 alloc_aux_for_edge (e, size);
761 /* Clear AUX pointers of all edges. */
764 clear_aux_for_edges ()
768 for (i = -1; i < n_basic_blocks; i++)
774 bb = BASIC_BLOCK (i);
776 bb = ENTRY_BLOCK_PTR;
778 for (e = bb->succ; e; e = e->succ_next)
783 /* Free data allocated in edge_aux_obstack and clear AUX pointers
787 free_aux_for_edges ()
789 if (!first_edge_aux_obj)
791 obstack_free (&edge_aux_obstack, first_edge_aux_obj);
792 first_edge_aux_obj = NULL;
794 clear_aux_for_edges ();