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 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
47 #include "hard-reg-set.h"
48 #include "basic-block.h"
58 /* The obstack on which the flow graph components are allocated. */
60 struct obstack flow_obstack
;
61 static char *flow_firstobj
;
63 /* Number of basic blocks in the current function. */
67 /* Number of edges in the current function. */
71 /* First edge in the deleted edges chain. */
73 edge first_deleted_edge
;
74 static basic_block first_deleted_block
;
76 /* The basic block array. */
78 varray_type basic_block_info
;
80 /* The special entry and exit blocks. */
82 struct basic_block_def entry_exit_blocks
[2]
90 NULL
, /* cond_local_set */
91 NULL
, /* global_live_at_start */
92 NULL
, /* global_live_at_end */
94 ENTRY_BLOCK
, /* index */
103 NULL
, /* head_tree */
107 NULL
, /* local_set */
108 NULL
, /* cond_local_set */
109 NULL
, /* global_live_at_start */
110 NULL
, /* global_live_at_end */
112 EXIT_BLOCK
, /* index */
120 void debug_flow_info
PARAMS ((void));
121 static void free_edge
PARAMS ((edge
));
123 /* Called once at initialization time. */
128 static int initialized
;
130 first_deleted_edge
= 0;
131 first_deleted_block
= 0;
136 gcc_obstack_init (&flow_obstack
);
137 flow_firstobj
= (char *) obstack_alloc (&flow_obstack
, 0);
142 obstack_free (&flow_obstack
, flow_firstobj
);
143 flow_firstobj
= (char *) obstack_alloc (&flow_obstack
, 0);
147 /* Helper function for remove_edge and clear_edges. Frees edge structure
148 without actually unlinking it from the pred/succ lists. */
155 memset (e
, 0, sizeof *e
);
156 e
->succ_next
= first_deleted_edge
;
157 first_deleted_edge
= e
;
160 /* Free the memory associated with the edge structures. */
168 for (i
= 0; i
< n_basic_blocks
; ++i
)
170 basic_block bb
= BASIC_BLOCK (i
);
175 edge next
= e
->succ_next
;
185 e
= ENTRY_BLOCK_PTR
->succ
;
188 edge next
= e
->succ_next
;
194 EXIT_BLOCK_PTR
->pred
= NULL
;
195 ENTRY_BLOCK_PTR
->succ
= NULL
;
201 /* Allocate memory for basic_block. */
208 if (first_deleted_block
)
210 bb
= first_deleted_block
;
211 first_deleted_block
= (basic_block
) bb
->succ
;
216 bb
= (basic_block
) obstack_alloc (&flow_obstack
, sizeof *bb
);
217 memset (bb
, 0, sizeof *bb
);
222 /* Remove block B from the basic block array and compact behind it. */
228 int i
, n
= n_basic_blocks
;
230 for (i
= b
->index
; i
+ 1 < n
; ++i
)
232 basic_block x
= BASIC_BLOCK (i
+ 1);
237 /* Invalidate data to make bughunting easier. */
238 memset (b
, 0, sizeof *b
);
240 basic_block_info
->num_elements
--;
242 b
->succ
= (edge
) first_deleted_block
;
243 first_deleted_block
= (basic_block
) b
;
246 /* Create an edge connecting SRC and DST with FLAGS optionally using
247 edge cache CACHE. Return the new edge, NULL if already exist. */
250 cached_make_edge (edge_cache
, src
, dst
, flags
)
252 basic_block src
, dst
;
258 /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
259 many edges to them, or we didn't allocate memory for it. */
260 use_edge_cache
= (edge_cache
261 && src
!= ENTRY_BLOCK_PTR
&& dst
!= EXIT_BLOCK_PTR
);
263 /* Make sure we don't add duplicate edges. */
264 switch (use_edge_cache
)
267 /* Quick test for non-existence of the edge. */
268 if (! TEST_BIT (edge_cache
[src
->index
], dst
->index
))
271 /* The edge exists; early exit if no work to do. */
277 for (e
= src
->succ
; e
; e
= e
->succ_next
)
286 if (first_deleted_edge
)
288 e
= first_deleted_edge
;
289 first_deleted_edge
= e
->succ_next
;
293 e
= (edge
) obstack_alloc (&flow_obstack
, sizeof *e
);
294 memset (e
, 0, sizeof *e
);
298 e
->succ_next
= src
->succ
;
299 e
->pred_next
= dst
->pred
;
308 SET_BIT (edge_cache
[src
->index
], dst
->index
);
313 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
314 created edge or NULL if already exist. */
317 make_edge (src
, dest
, flags
)
318 basic_block src
, dest
;
321 return cached_make_edge (NULL
, src
, dest
, flags
);
324 /* Create an edge connecting SRC to DEST and set probability by knowing
325 that it is the single edge leaving SRC. */
328 make_single_succ_edge (src
, dest
, flags
)
329 basic_block src
, dest
;
332 edge e
= make_edge (src
, dest
, flags
);
334 e
->probability
= REG_BR_PROB_BASE
;
335 e
->count
= src
->count
;
339 /* This function will remove an edge from the flow graph. */
345 edge last_pred
= NULL
;
346 edge last_succ
= NULL
;
348 basic_block src
, dest
;
352 for (tmp
= src
->succ
; tmp
&& tmp
!= e
; tmp
= tmp
->succ_next
)
358 last_succ
->succ_next
= e
->succ_next
;
360 src
->succ
= e
->succ_next
;
362 for (tmp
= dest
->pred
; tmp
&& tmp
!= e
; tmp
= tmp
->pred_next
)
368 last_pred
->pred_next
= e
->pred_next
;
370 dest
->pred
= e
->pred_next
;
375 /* Redirect an edge's successor from one block to another. */
378 redirect_edge_succ (e
, new_succ
)
380 basic_block new_succ
;
384 /* Disconnect the edge from the old successor block. */
385 for (pe
= &e
->dest
->pred
; *pe
!= e
; pe
= &(*pe
)->pred_next
)
387 *pe
= (*pe
)->pred_next
;
389 /* Reconnect the edge to the new successor block. */
390 e
->pred_next
= new_succ
->pred
;
395 /* Like previous but avoid possible duplicate edge. */
398 redirect_edge_succ_nodup (e
, new_succ
)
400 basic_block new_succ
;
404 /* Check whether the edge is already present. */
405 for (s
= e
->src
->succ
; s
; s
= s
->succ_next
)
406 if (s
->dest
== new_succ
&& s
!= e
)
411 s
->flags
|= e
->flags
;
412 s
->probability
+= e
->probability
;
413 s
->count
+= e
->count
;
418 redirect_edge_succ (e
, new_succ
);
423 /* Redirect an edge's predecessor from one block to another. */
426 redirect_edge_pred (e
, new_pred
)
428 basic_block new_pred
;
432 /* Disconnect the edge from the old predecessor block. */
433 for (pe
= &e
->src
->succ
; *pe
!= e
; pe
= &(*pe
)->succ_next
)
436 *pe
= (*pe
)->succ_next
;
438 /* Reconnect the edge to the new predecessor block. */
439 e
->succ_next
= new_pred
->succ
;
445 dump_flow_info (file
)
449 static const char * const reg_class_names
[] = REG_CLASS_NAMES
;
451 fprintf (file
, "%d registers.\n", max_regno
);
452 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
455 enum reg_class
class, altclass
;
457 fprintf (file
, "\nRegister %d used %d times across %d insns",
458 i
, REG_N_REFS (i
), REG_LIVE_LENGTH (i
));
459 if (REG_BASIC_BLOCK (i
) >= 0)
460 fprintf (file
, " in block %d", REG_BASIC_BLOCK (i
));
462 fprintf (file
, "; set %d time%s", REG_N_SETS (i
),
463 (REG_N_SETS (i
) == 1) ? "" : "s");
464 if (REG_USERVAR_P (regno_reg_rtx
[i
]))
465 fprintf (file
, "; user var");
466 if (REG_N_DEATHS (i
) != 1)
467 fprintf (file
, "; dies in %d places", REG_N_DEATHS (i
));
468 if (REG_N_CALLS_CROSSED (i
) == 1)
469 fprintf (file
, "; crosses 1 call");
470 else if (REG_N_CALLS_CROSSED (i
))
471 fprintf (file
, "; crosses %d calls", REG_N_CALLS_CROSSED (i
));
472 if (PSEUDO_REGNO_BYTES (i
) != UNITS_PER_WORD
)
473 fprintf (file
, "; %d bytes", PSEUDO_REGNO_BYTES (i
));
475 class = reg_preferred_class (i
);
476 altclass
= reg_alternate_class (i
);
477 if (class != GENERAL_REGS
|| altclass
!= ALL_REGS
)
479 if (altclass
== ALL_REGS
|| class == ALL_REGS
)
480 fprintf (file
, "; pref %s", reg_class_names
[(int) class]);
481 else if (altclass
== NO_REGS
)
482 fprintf (file
, "; %s or none", reg_class_names
[(int) class]);
484 fprintf (file
, "; pref %s, else %s",
485 reg_class_names
[(int) class],
486 reg_class_names
[(int) altclass
]);
489 if (REG_POINTER (regno_reg_rtx
[i
]))
490 fprintf (file
, "; pointer");
491 fprintf (file
, ".\n");
494 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks
, n_edges
);
495 for (i
= 0; i
< n_basic_blocks
; i
++)
497 basic_block bb
= BASIC_BLOCK (i
);
500 fprintf (file
, "\nBasic block %d: first insn %d, last %d, ",
501 i
, INSN_UID (bb
->head
), INSN_UID (bb
->end
));
502 fprintf (file
, "loop_depth %d, count ", bb
->loop_depth
);
503 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
504 fprintf (file
, ", freq %i.\n", bb
->frequency
);
506 fprintf (file
, "Predecessors: ");
507 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
508 dump_edge_info (file
, e
, 0);
510 fprintf (file
, "\nSuccessors: ");
511 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
512 dump_edge_info (file
, e
, 1);
514 fprintf (file
, "\nRegisters live at start:");
515 dump_regset (bb
->global_live_at_start
, file
);
517 fprintf (file
, "\nRegisters live at end:");
518 dump_regset (bb
->global_live_at_end
, file
);
529 dump_flow_info (stderr
);
533 dump_edge_info (file
, e
, do_succ
)
538 basic_block side
= (do_succ
? e
->dest
: e
->src
);
540 if (side
== ENTRY_BLOCK_PTR
)
541 fputs (" ENTRY", file
);
542 else if (side
== EXIT_BLOCK_PTR
)
543 fputs (" EXIT", file
);
545 fprintf (file
, " %d", side
->index
);
548 fprintf (file
, " [%.1f%%] ", e
->probability
* 100.0 / REG_BR_PROB_BASE
);
552 fprintf (file
, " count:");
553 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
558 static const char * const bitnames
[]
559 = {"fallthru", "ab", "abcall", "eh", "fake", "dfs_back"};
561 int i
, flags
= e
->flags
;
564 for (i
= 0; flags
; i
++)
565 if (flags
& (1 << i
))
571 if (i
< (int) ARRAY_SIZE (bitnames
))
572 fputs (bitnames
[i
], file
);
574 fprintf (file
, "%d", i
);
582 /* Simple routines to easily allocate AUX fields of basic blocks. */
584 static struct obstack block_aux_obstack
;
585 static void *first_block_aux_obj
= 0;
586 static struct obstack edge_aux_obstack
;
587 static void *first_edge_aux_obj
= 0;
589 /* Allocate an memory block of SIZE as BB->aux. The obstack must
590 be first initialized by alloc_aux_for_blocks. */
593 alloc_aux_for_block (bb
, size
)
597 /* Verify that aux field is clear. */
598 if (bb
->aux
|| !first_block_aux_obj
)
600 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
601 memset (bb
->aux
, 0, size
);
604 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
605 alloc_aux_for_block for each basic block. */
608 alloc_aux_for_blocks (size
)
611 static int initialized
;
615 gcc_obstack_init (&block_aux_obstack
);
619 /* Check whether AUX data are still allocated. */
620 else if (first_block_aux_obj
)
622 first_block_aux_obj
= (char *) obstack_alloc (&block_aux_obstack
, 0);
627 for (i
= 0; i
< n_basic_blocks
; i
++)
628 alloc_aux_for_block (BASIC_BLOCK (i
), size
);
630 alloc_aux_for_block (ENTRY_BLOCK_PTR
, size
);
631 alloc_aux_for_block (EXIT_BLOCK_PTR
, size
);
635 /* Clear AUX pointers of all blocks. */
638 clear_aux_for_blocks ()
642 for (i
= 0; i
< n_basic_blocks
; i
++)
643 BASIC_BLOCK (i
)->aux
= NULL
;
645 ENTRY_BLOCK_PTR
->aux
= NULL
;
646 EXIT_BLOCK_PTR
->aux
= NULL
;
649 /* Free data allocated in block_aux_obstack and clear AUX pointers
653 free_aux_for_blocks ()
655 if (!first_block_aux_obj
)
657 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
658 first_block_aux_obj
= NULL
;
660 clear_aux_for_blocks ();
663 /* Allocate an memory edge of SIZE as BB->aux. The obstack must
664 be first initialized by alloc_aux_for_edges. */
667 alloc_aux_for_edge (e
, size
)
671 /* Verify that aux field is clear. */
672 if (e
->aux
|| !first_edge_aux_obj
)
674 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
675 memset (e
->aux
, 0, size
);
678 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
679 alloc_aux_for_edge for each basic edge. */
682 alloc_aux_for_edges (size
)
685 static int initialized
;
689 gcc_obstack_init (&edge_aux_obstack
);
693 /* Check whether AUX data are still allocated. */
694 else if (first_edge_aux_obj
)
697 first_edge_aux_obj
= (char *) obstack_alloc (&edge_aux_obstack
, 0);
701 for (i
= -1; i
< n_basic_blocks
; i
++)
707 bb
= BASIC_BLOCK (i
);
709 bb
= ENTRY_BLOCK_PTR
;
711 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
712 alloc_aux_for_edge (e
, size
);
717 /* Clear AUX pointers of all edges. */
720 clear_aux_for_edges ()
724 for (i
= -1; i
< n_basic_blocks
; i
++)
730 bb
= BASIC_BLOCK (i
);
732 bb
= ENTRY_BLOCK_PTR
;
734 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
739 /* Free data allocated in edge_aux_obstack and clear AUX pointers
743 free_aux_for_edges ()
745 if (!first_edge_aux_obj
)
747 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
748 first_edge_aux_obj
= NULL
;
750 clear_aux_for_edges ();