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"
60 #include "alloc-pool.h"
62 /* The obstack on which the flow graph components are allocated. */
64 struct obstack flow_obstack
;
65 static char *flow_firstobj
;
67 /* Basic block object pool. */
69 static alloc_pool bb_pool
;
71 /* Edge object pool. */
73 static alloc_pool edge_pool
;
75 /* Number of basic blocks in the current function. */
79 /* First free basic block number. */
83 /* Number of edges in the current function. */
87 /* The basic block array. */
89 varray_type basic_block_info
;
91 /* The special entry and exit blocks. */
93 struct basic_block_def entry_exit_blocks
[2]
100 NULL
, /* local_set */
101 NULL
, /* cond_local_set */
102 NULL
, /* global_live_at_start */
103 NULL
, /* global_live_at_end */
105 ENTRY_BLOCK
, /* index */
107 EXIT_BLOCK_PTR
, /* next_bb */
109 NULL
, /* loop_father */
117 NULL
, /* head_tree */
121 NULL
, /* local_set */
122 NULL
, /* cond_local_set */
123 NULL
, /* global_live_at_start */
124 NULL
, /* global_live_at_end */
126 EXIT_BLOCK
, /* index */
127 ENTRY_BLOCK_PTR
, /* prev_bb */
130 NULL
, /* loop_father */
137 void debug_flow_info
PARAMS ((void));
138 static void free_edge
PARAMS ((edge
));
140 /* Called once at initialization time. */
145 static int initialized
;
151 gcc_obstack_init (&flow_obstack
);
152 flow_firstobj
= (char *) obstack_alloc (&flow_obstack
, 0);
157 free_alloc_pool (bb_pool
);
158 free_alloc_pool (edge_pool
);
159 obstack_free (&flow_obstack
, flow_firstobj
);
160 flow_firstobj
= (char *) obstack_alloc (&flow_obstack
, 0);
162 bb_pool
= create_alloc_pool ("Basic block pool",
163 sizeof (struct basic_block_def
), 100);
164 edge_pool
= create_alloc_pool ("Edge pool",
165 sizeof (struct edge_def
), 100);
168 /* Helper function for remove_edge and clear_edges. Frees edge structure
169 without actually unlinking it from the pred/succ lists. */
176 pool_free (edge_pool
, e
);
179 /* Free the memory associated with the edge structures. */
193 edge next
= e
->succ_next
;
203 e
= ENTRY_BLOCK_PTR
->succ
;
206 edge next
= e
->succ_next
;
212 EXIT_BLOCK_PTR
->pred
= NULL
;
213 ENTRY_BLOCK_PTR
->succ
= NULL
;
219 /* Allocate memory for basic_block. */
225 bb
= pool_alloc (bb_pool
);
226 memset (bb
, 0, sizeof (*bb
));
230 /* Link block B to chain after AFTER. */
232 link_block (b
, after
)
233 basic_block b
, after
;
235 b
->next_bb
= after
->next_bb
;
238 b
->next_bb
->prev_bb
= b
;
241 /* Unlink block B from chain. */
246 b
->next_bb
->prev_bb
= b
->prev_bb
;
247 b
->prev_bb
->next_bb
= b
->next_bb
;
250 /* Sequentially order blocks and compact the arrays. */
260 BASIC_BLOCK (i
) = bb
;
265 if (i
!= n_basic_blocks
)
268 last_basic_block
= n_basic_blocks
;
271 /* Remove block B from the basic block array. */
278 BASIC_BLOCK (b
->index
) = NULL
;
280 pool_free (bb_pool
, b
);
283 /* Create an edge connecting SRC and DST with FLAGS optionally using
284 edge cache CACHE. Return the new edge, NULL if already exist. */
287 cached_make_edge (edge_cache
, src
, dst
, flags
)
289 basic_block src
, dst
;
295 /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
296 many edges to them, or we didn't allocate memory for it. */
297 use_edge_cache
= (edge_cache
298 && src
!= ENTRY_BLOCK_PTR
&& dst
!= EXIT_BLOCK_PTR
);
300 /* Make sure we don't add duplicate edges. */
301 switch (use_edge_cache
)
304 /* Quick test for non-existence of the edge. */
305 if (! TEST_BIT (edge_cache
[src
->index
], dst
->index
))
308 /* The edge exists; early exit if no work to do. */
314 for (e
= src
->succ
; e
; e
= e
->succ_next
)
324 e
= pool_alloc (edge_pool
);
325 memset (e
, 0, sizeof (*e
));
328 e
->succ_next
= src
->succ
;
329 e
->pred_next
= dst
->pred
;
338 SET_BIT (edge_cache
[src
->index
], dst
->index
);
343 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
344 created edge or NULL if already exist. */
347 make_edge (src
, dest
, flags
)
348 basic_block src
, dest
;
351 return cached_make_edge (NULL
, src
, dest
, flags
);
354 /* Create an edge connecting SRC to DEST and set probability by knowing
355 that it is the single edge leaving SRC. */
358 make_single_succ_edge (src
, dest
, flags
)
359 basic_block src
, dest
;
362 edge e
= make_edge (src
, dest
, flags
);
364 e
->probability
= REG_BR_PROB_BASE
;
365 e
->count
= src
->count
;
369 /* This function will remove an edge from the flow graph. */
375 edge last_pred
= NULL
;
376 edge last_succ
= NULL
;
378 basic_block src
, dest
;
382 for (tmp
= src
->succ
; tmp
&& tmp
!= e
; tmp
= tmp
->succ_next
)
388 last_succ
->succ_next
= e
->succ_next
;
390 src
->succ
= e
->succ_next
;
392 for (tmp
= dest
->pred
; tmp
&& tmp
!= e
; tmp
= tmp
->pred_next
)
398 last_pred
->pred_next
= e
->pred_next
;
400 dest
->pred
= e
->pred_next
;
405 /* Redirect an edge's successor from one block to another. */
408 redirect_edge_succ (e
, new_succ
)
410 basic_block new_succ
;
414 /* Disconnect the edge from the old successor block. */
415 for (pe
= &e
->dest
->pred
; *pe
!= e
; pe
= &(*pe
)->pred_next
)
417 *pe
= (*pe
)->pred_next
;
419 /* Reconnect the edge to the new successor block. */
420 e
->pred_next
= new_succ
->pred
;
425 /* Like previous but avoid possible duplicate edge. */
428 redirect_edge_succ_nodup (e
, new_succ
)
430 basic_block new_succ
;
434 /* Check whether the edge is already present. */
435 for (s
= e
->src
->succ
; s
; s
= s
->succ_next
)
436 if (s
->dest
== new_succ
&& s
!= e
)
441 s
->flags
|= e
->flags
;
442 s
->probability
+= e
->probability
;
443 if (s
->probability
> REG_BR_PROB_BASE
)
444 s
->probability
= REG_BR_PROB_BASE
;
445 s
->count
+= e
->count
;
450 redirect_edge_succ (e
, new_succ
);
455 /* Redirect an edge's predecessor from one block to another. */
458 redirect_edge_pred (e
, new_pred
)
460 basic_block new_pred
;
464 /* Disconnect the edge from the old predecessor block. */
465 for (pe
= &e
->src
->succ
; *pe
!= e
; pe
= &(*pe
)->succ_next
)
468 *pe
= (*pe
)->succ_next
;
470 /* Reconnect the edge to the new predecessor block. */
471 e
->succ_next
= new_pred
->succ
;
481 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
486 dump_flow_info (file
)
490 int max_regno
= max_reg_num ();
492 static const char * const reg_class_names
[] = REG_CLASS_NAMES
;
494 fprintf (file
, "%d registers.\n", max_regno
);
495 for (i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
498 enum reg_class
class, altclass
;
500 fprintf (file
, "\nRegister %d used %d times across %d insns",
501 i
, REG_N_REFS (i
), REG_LIVE_LENGTH (i
));
502 if (REG_BASIC_BLOCK (i
) >= 0)
503 fprintf (file
, " in block %d", REG_BASIC_BLOCK (i
));
505 fprintf (file
, "; set %d time%s", REG_N_SETS (i
),
506 (REG_N_SETS (i
) == 1) ? "" : "s");
507 if (regno_reg_rtx
[i
] != NULL
&& REG_USERVAR_P (regno_reg_rtx
[i
]))
508 fprintf (file
, "; user var");
509 if (REG_N_DEATHS (i
) != 1)
510 fprintf (file
, "; dies in %d places", REG_N_DEATHS (i
));
511 if (REG_N_CALLS_CROSSED (i
) == 1)
512 fprintf (file
, "; crosses 1 call");
513 else if (REG_N_CALLS_CROSSED (i
))
514 fprintf (file
, "; crosses %d calls", REG_N_CALLS_CROSSED (i
));
515 if (regno_reg_rtx
[i
] != NULL
516 && PSEUDO_REGNO_BYTES (i
) != UNITS_PER_WORD
)
517 fprintf (file
, "; %d bytes", PSEUDO_REGNO_BYTES (i
));
519 class = reg_preferred_class (i
);
520 altclass
= reg_alternate_class (i
);
521 if (class != GENERAL_REGS
|| altclass
!= ALL_REGS
)
523 if (altclass
== ALL_REGS
|| class == ALL_REGS
)
524 fprintf (file
, "; pref %s", reg_class_names
[(int) class]);
525 else if (altclass
== NO_REGS
)
526 fprintf (file
, "; %s or none", reg_class_names
[(int) class]);
528 fprintf (file
, "; pref %s, else %s",
529 reg_class_names
[(int) class],
530 reg_class_names
[(int) altclass
]);
533 if (regno_reg_rtx
[i
] != NULL
&& REG_POINTER (regno_reg_rtx
[i
]))
534 fprintf (file
, "; pointer");
535 fprintf (file
, ".\n");
538 fprintf (file
, "\n%d basic blocks, %d edges.\n", n_basic_blocks
, n_edges
);
545 fprintf (file
, "\nBasic block %d: first insn %d, last %d, ",
546 bb
->index
, INSN_UID (bb
->head
), INSN_UID (bb
->end
));
547 fprintf (file
, "prev %d, next %d, ",
548 bb
->prev_bb
->index
, bb
->next_bb
->index
);
549 fprintf (file
, "loop_depth %d, count ", bb
->loop_depth
);
550 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
551 fprintf (file
, ", freq %i", bb
->frequency
);
552 if (maybe_hot_bb_p (bb
))
553 fprintf (file
, ", maybe hot");
554 if (probably_never_executed_bb_p (bb
))
555 fprintf (file
, ", probably never executed");
556 fprintf (file
, ".\n");
558 fprintf (file
, "Predecessors: ");
559 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
560 dump_edge_info (file
, e
, 0);
562 fprintf (file
, "\nSuccessors: ");
563 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
564 dump_edge_info (file
, e
, 1);
566 fprintf (file
, "\nRegisters live at start:");
567 dump_regset (bb
->global_live_at_start
, file
);
569 fprintf (file
, "\nRegisters live at end:");
570 dump_regset (bb
->global_live_at_end
, file
);
574 /* Check the consistency of profile information. We can't do that
575 in verify_flow_info, as the counts may get invalid for incompletely
576 solved graphs, later eliminating of conditionals or roundoff errors.
577 It is still practical to have them reported for debugging of simple
580 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
581 sum
+= e
->probability
;
582 if (bb
->succ
&& abs (sum
- REG_BR_PROB_BASE
) > 100)
583 fprintf (file
, "Invalid sum of outgoing probabilities %.1f%%\n",
584 sum
* 100.0 / REG_BR_PROB_BASE
);
586 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
587 sum
+= EDGE_FREQUENCY (e
);
588 if (abs (sum
- bb
->frequency
) > 100)
590 "Invalid sum of incomming frequencies %i, should be %i\n",
593 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
595 if (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100)
596 fprintf (file
, "Invalid sum of incomming counts %i, should be %i\n",
597 (int)lsum
, (int)bb
->count
);
599 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
601 if (bb
->succ
&& (lsum
- bb
->count
> 100 || lsum
- bb
->count
< -100))
602 fprintf (file
, "Invalid sum of incomming counts %i, should be %i\n",
603 (int)lsum
, (int)bb
->count
);
612 dump_flow_info (stderr
);
616 dump_edge_info (file
, e
, do_succ
)
621 basic_block side
= (do_succ
? e
->dest
: e
->src
);
623 if (side
== ENTRY_BLOCK_PTR
)
624 fputs (" ENTRY", file
);
625 else if (side
== EXIT_BLOCK_PTR
)
626 fputs (" EXIT", file
);
628 fprintf (file
, " %d", side
->index
);
631 fprintf (file
, " [%.1f%%] ", e
->probability
* 100.0 / REG_BR_PROB_BASE
);
635 fprintf (file
, " count:");
636 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
641 static const char * const bitnames
[]
642 = {"fallthru", "ab", "abcall", "eh", "fake", "dfs_back", "can_fallthru"};
644 int i
, flags
= e
->flags
;
647 for (i
= 0; flags
; i
++)
648 if (flags
& (1 << i
))
654 if (i
< (int) ARRAY_SIZE (bitnames
))
655 fputs (bitnames
[i
], file
);
657 fprintf (file
, "%d", i
);
665 /* Simple routines to easily allocate AUX fields of basic blocks. */
667 static struct obstack block_aux_obstack
;
668 static void *first_block_aux_obj
= 0;
669 static struct obstack edge_aux_obstack
;
670 static void *first_edge_aux_obj
= 0;
672 /* Allocate a memory block of SIZE as BB->aux. The obstack must
673 be first initialized by alloc_aux_for_blocks. */
676 alloc_aux_for_block (bb
, size
)
680 /* Verify that aux field is clear. */
681 if (bb
->aux
|| !first_block_aux_obj
)
683 bb
->aux
= obstack_alloc (&block_aux_obstack
, size
);
684 memset (bb
->aux
, 0, size
);
687 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
688 alloc_aux_for_block for each basic block. */
691 alloc_aux_for_blocks (size
)
694 static int initialized
;
698 gcc_obstack_init (&block_aux_obstack
);
702 /* Check whether AUX data are still allocated. */
703 else if (first_block_aux_obj
)
705 first_block_aux_obj
= (char *) obstack_alloc (&block_aux_obstack
, 0);
710 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
711 alloc_aux_for_block (bb
, size
);
715 /* Clear AUX pointers of all blocks. */
718 clear_aux_for_blocks ()
722 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
726 /* Free data allocated in block_aux_obstack and clear AUX pointers
730 free_aux_for_blocks ()
732 if (!first_block_aux_obj
)
734 obstack_free (&block_aux_obstack
, first_block_aux_obj
);
735 first_block_aux_obj
= NULL
;
737 clear_aux_for_blocks ();
740 /* Allocate a memory edge of SIZE as BB->aux. The obstack must
741 be first initialized by alloc_aux_for_edges. */
744 alloc_aux_for_edge (e
, size
)
748 /* Verify that aux field is clear. */
749 if (e
->aux
|| !first_edge_aux_obj
)
751 e
->aux
= obstack_alloc (&edge_aux_obstack
, size
);
752 memset (e
->aux
, 0, size
);
755 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
756 alloc_aux_for_edge for each basic edge. */
759 alloc_aux_for_edges (size
)
762 static int initialized
;
766 gcc_obstack_init (&edge_aux_obstack
);
770 /* Check whether AUX data are still allocated. */
771 else if (first_edge_aux_obj
)
774 first_edge_aux_obj
= (char *) obstack_alloc (&edge_aux_obstack
, 0);
779 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
783 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
784 alloc_aux_for_edge (e
, size
);
789 /* Clear AUX pointers of all edges. */
792 clear_aux_for_edges ()
797 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
799 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
804 /* Free data allocated in edge_aux_obstack and clear AUX pointers
808 free_aux_for_edges ()
810 if (!first_edge_aux_obj
)
812 obstack_free (&edge_aux_obstack
, first_edge_aux_obj
);
813 first_edge_aux_obj
= NULL
;
815 clear_aux_for_edges ();