X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fcfganal.c;h=7732efa979ef4ee8456442102bc8301c28681196;hb=69dc2fad595f3ab6d3f3aeb4fad283a09ef1f604;hp=679a6e67fda4099960a936c79ce5bdbad78ca72a;hpb=4a82352a84766c06cff20385665f3f3828163a19;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/cfganal.c b/gcc/cfganal.c index 679a6e67fda..7732efa979e 100644 --- a/gcc/cfganal.c +++ b/gcc/cfganal.c @@ -1,6 +1,6 @@ /* Control flow graph analysis code for GNU compiler. Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, - 1999, 2000, 2001 Free Software Foundation, Inc. + 1999, 2000, 2001, 2003, 2004 Free Software Foundation, Inc. This file is part of GCC. @@ -22,12 +22,17 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA /* This file contains various simple utilities to analyze the CFG. */ #include "config.h" #include "system.h" +#include "coretypes.h" +#include "tm.h" #include "rtl.h" +#include "obstack.h" #include "hard-reg-set.h" #include "basic-block.h" +#include "insn-config.h" +#include "recog.h" #include "toplev.h" - -#include "obstack.h" +#include "tm_p.h" +#include "timevar.h" /* Store the data structures necessary for depth-first search. */ struct depth_first_search_dsS { @@ -43,55 +48,104 @@ struct depth_first_search_dsS { }; typedef struct depth_first_search_dsS *depth_first_search_ds; -static void flow_dfs_compute_reverse_init - PARAMS ((depth_first_search_ds)); -static void flow_dfs_compute_reverse_add_bb - PARAMS ((depth_first_search_ds, basic_block)); -static basic_block flow_dfs_compute_reverse_execute - PARAMS ((depth_first_search_ds)); -static void flow_dfs_compute_reverse_finish - PARAMS ((depth_first_search_ds)); -static void remove_fake_successors PARAMS ((basic_block)); -static bool need_fake_edge_p PARAMS ((rtx)); +static void flow_dfs_compute_reverse_init (depth_first_search_ds); +static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds, + basic_block); +static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds, + basic_block); +static void flow_dfs_compute_reverse_finish (depth_first_search_ds); +static bool flow_active_insn_p (rtx); +/* Like active_insn_p, except keep the return value clobber around + even after reload. */ + +static bool +flow_active_insn_p (rtx insn) +{ + if (active_insn_p (insn)) + return true; + + /* A clobber of the function return value exists for buggy + programs that fail to return a value. Its effect is to + keep the return value from being live across the entire + function. If we allow it to be skipped, we introduce the + possibility for register livetime aborts. */ + if (GET_CODE (PATTERN (insn)) == CLOBBER + && REG_P (XEXP (PATTERN (insn), 0)) + && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0))) + return true; + + return false; +} + /* Return true if the block has no effect and only forwards control flow to its single destination. */ + bool -forwarder_block_p (bb) - basic_block bb; +forwarder_block_p (basic_block bb) { - rtx insn = bb->head; + rtx insn; + if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR - || !bb->succ || bb->succ->succ_next) + || EDGE_COUNT (bb->succs) != 1) return false; - while (insn != bb->end) - { - if (INSN_P (insn) && active_insn_p (insn)) - return false; - insn = NEXT_INSN (insn); - } + for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn)) + if (INSN_P (insn) && flow_active_insn_p (insn)) + return false; + return (!INSN_P (insn) - || (GET_CODE (insn) == JUMP_INSN && simplejump_p (insn)) - || !active_insn_p (insn)); + || (JUMP_P (insn) && simplejump_p (insn)) + || !flow_active_insn_p (insn)); } /* Return nonzero if we can reach target from src by falling through. */ + bool -can_fallthru (src, target) - basic_block src, target; +can_fallthru (basic_block src, basic_block target) { - rtx insn = src->end; - rtx insn2 = target->head; + rtx insn = BB_END (src); + rtx insn2; + edge e; + edge_iterator ei; - if (src->index + 1 == target->index && !active_insn_p (insn2)) + if (target == EXIT_BLOCK_PTR) + return true; + if (src->next_bb != target) + return 0; + FOR_EACH_EDGE (e, ei, src->succs) + if (e->dest == EXIT_BLOCK_PTR + && e->flags & EDGE_FALLTHRU) + return 0; + + insn2 = BB_HEAD (target); + if (insn2 && !active_insn_p (insn2)) insn2 = next_active_insn (insn2); + /* ??? Later we may add code to move jump tables offline. */ return next_active_insn (insn) == insn2; } + +/* Return nonzero if we could reach target from src by falling through, + if the target was made adjacent. If we already have a fall-through + edge to the exit block, we can't do that. */ +bool +could_fall_through (basic_block src, basic_block target) +{ + edge e; + edge_iterator ei; + + if (target == EXIT_BLOCK_PTR) + return true; + FOR_EACH_EDGE (e, ei, src->succs) + if (e->dest == EXIT_BLOCK_PTR + && e->flags & EDGE_FALLTHRU) + return 0; + return true; +} /* Mark the back edges in DFS traversal. - Return non-zero if a loop (natural or otherwise) is present. + Return nonzero if a loop (natural or otherwise) is present. Inspired by Depth_First_Search_PP described in: Advanced Compiler Design and Implementation @@ -101,9 +155,9 @@ can_fallthru (src, target) and heavily borrowed from flow_depth_first_order_compute. */ bool -mark_dfs_back_edges () +mark_dfs_back_edges (void) { - edge *stack; + edge_iterator *stack; int *pre; int *post; int sp; @@ -113,33 +167,33 @@ mark_dfs_back_edges () bool found = false; /* Allocate the preorder and postorder number arrays. */ - pre = (int *) xcalloc (n_basic_blocks, sizeof (int)); - post = (int *) xcalloc (n_basic_blocks, sizeof (int)); + pre = xcalloc (last_basic_block, sizeof (int)); + post = xcalloc (last_basic_block, sizeof (int)); /* Allocate stack for back-tracking up CFG. */ - stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge)); + stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator)); sp = 0; /* Allocate bitmap to track nodes that have been visited. */ - visited = sbitmap_alloc (n_basic_blocks); + visited = sbitmap_alloc (last_basic_block); /* None of the nodes in the CFG have been visited yet. */ sbitmap_zero (visited); /* Push the first edge on to the stack. */ - stack[sp++] = ENTRY_BLOCK_PTR->succ; + stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); while (sp) { - edge e; + edge_iterator ei; basic_block src; basic_block dest; /* Look at the edge on the top of the stack. */ - e = stack[sp - 1]; - src = e->src; - dest = e->dest; - e->flags &= ~EDGE_DFS_BACK; + ei = stack[sp - 1]; + src = ei_edge (ei)->src; + dest = ei_edge (ei)->dest; + ei_edge (ei)->flags &= ~EDGE_DFS_BACK; /* Check if the edge destination has been visited yet. */ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) @@ -148,12 +202,11 @@ mark_dfs_back_edges () SET_BIT (visited, dest->index); pre[dest->index] = prenum++; - - if (dest->succ) + if (EDGE_COUNT (dest->succs) > 0) { /* Since the DEST node has been visited for the first time, check its successors. */ - stack[sp++] = dest->succ; + stack[sp++] = ei_start (dest->succs); } else post[dest->index] = postnum++; @@ -163,13 +216,13 @@ mark_dfs_back_edges () if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR && pre[src->index] >= pre[dest->index] && post[dest->index] == 0) - e->flags |= EDGE_DFS_BACK, found = true; + ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true; - if (! e->succ_next && src != ENTRY_BLOCK_PTR) + if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR) post[src->index] = postnum++; - if (e->succ_next) - stack[sp - 1] = e->succ_next; + if (!ei_one_before_end_p (ei)) + ei_next (&stack[sp - 1]); else sp--; } @@ -183,165 +236,64 @@ mark_dfs_back_edges () return found; } -/* Return true if we need to add fake edge to exit. - Helper function for the flow_call_edges_add. */ - -static bool -need_fake_edge_p (insn) - rtx insn; -{ - if (!INSN_P (insn)) - return false; - - if ((GET_CODE (insn) == CALL_INSN - && !SIBLING_CALL_P (insn) - && !find_reg_note (insn, REG_NORETURN, NULL) - && !find_reg_note (insn, REG_ALWAYS_RETURN, NULL) - && !CONST_OR_PURE_CALL_P (insn))) - return true; - - return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS - && MEM_VOLATILE_P (PATTERN (insn))) - || (GET_CODE (PATTERN (insn)) == PARALLEL - && asm_noperands (insn) != -1 - && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0))) - || GET_CODE (PATTERN (insn)) == ASM_INPUT); -} +/* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */ -/* Add fake edges to the function exit for any non constant and non noreturn - calls, volatile inline assembly in the bitmap of blocks specified by - BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks - that were split. - - The goal is to expose cases in which entering a basic block does not imply - that all subsequent instructions must be executed. */ - -int -flow_call_edges_add (blocks) - sbitmap blocks; +void +set_edge_can_fallthru_flag (void) { - int i; - int blocks_split = 0; - int bb_num = 0; - basic_block *bbs; - bool check_last_block = false; - - /* Map bb indices into basic block pointers since split_block - will renumber the basic blocks. */ - - bbs = xmalloc (n_basic_blocks * sizeof (*bbs)); - - if (! blocks) - { - for (i = 0; i < n_basic_blocks; i++) - bbs[bb_num++] = BASIC_BLOCK (i); - check_last_block = true; - } - else - { - EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i, - { - bbs[bb_num++] = BASIC_BLOCK (i); - if (i == n_basic_blocks - 1) - check_last_block = true; - }); - } - - /* In the last basic block, before epilogue generation, there will be - a fallthru edge to EXIT. Special care is required if the last insn - of the last basic block is a call because make_edge folds duplicate - edges, which would result in the fallthru edge also being marked - fake, which would result in the fallthru edge being removed by - remove_fake_edges, which would result in an invalid CFG. - - Moreover, we can't elide the outgoing fake edge, since the block - profiler needs to take this into account in order to solve the minimal - spanning tree in the case that the call doesn't return. - - Handle this by adding a dummy instruction in a new last basic block. */ - if (check_last_block - && need_fake_edge_p (BASIC_BLOCK (n_basic_blocks - 1)->end)) - { - edge e; - for (e = BASIC_BLOCK (n_basic_blocks - 1)->succ; e; e = e->succ_next) - if (e->dest == EXIT_BLOCK_PTR) - break; - insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e); - commit_edge_insertions (); - } - - - /* Now add fake edges to the function exit for any non constant - calls since there is no way that we can determine if they will - return or not... */ + basic_block bb; - for (i = 0; i < bb_num; i++) + FOR_EACH_BB (bb) { - basic_block bb = bbs[i]; - rtx insn; - rtx prev_insn; + edge e; + edge_iterator ei; - for (insn = bb->end; ; insn = prev_insn) + FOR_EACH_EDGE (e, ei, bb->succs) { - prev_insn = PREV_INSN (insn); - if (need_fake_edge_p (insn)) - { - edge e; - - /* The above condition should be enough to verify that there is - no edge to the exit block in CFG already. Calling make_edge in - such case would make us to mark that edge as fake and remove it - later. */ -#ifdef ENABLE_CHECKING - if (insn == bb->end) - for (e = bb->succ; e; e = e->succ_next) - if (e->dest == EXIT_BLOCK_PTR) - abort (); -#endif - - /* Note that the following may create a new basic block - and renumber the existing basic blocks. */ - e = split_block (bb, insn); - if (e) - blocks_split++; - - make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); - } - if (insn == bb->head) - break; - } - } + e->flags &= ~EDGE_CAN_FALLTHRU; - if (blocks_split) - verify_flow_info (); + /* The FALLTHRU edge is also CAN_FALLTHRU edge. */ + if (e->flags & EDGE_FALLTHRU) + e->flags |= EDGE_CAN_FALLTHRU; + } - free (bbs); - return blocks_split; + /* If the BB ends with an invertible condjump all (2) edges are + CAN_FALLTHRU edges. */ + if (EDGE_COUNT (bb->succs) != 2) + continue; + if (!any_condjump_p (BB_END (bb))) + continue; + if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0)) + continue; + invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0); + EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU; + EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU; + } } + /* Find unreachable blocks. An unreachable block will have 0 in - the reachable bit in block->flags. A non-zero value indicates the + the reachable bit in block->flags. A nonzero value indicates the block is reachable. */ void -find_unreachable_blocks () +find_unreachable_blocks (void) { edge e; - int i, n; - basic_block *tos, *worklist; + edge_iterator ei; + basic_block *tos, *worklist, bb; - n = n_basic_blocks; - tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n); + tos = worklist = xmalloc (sizeof (basic_block) * n_basic_blocks); /* Clear all the reachability flags. */ - for (i = 0; i < n; ++i) - BASIC_BLOCK (i)->flags &= ~BB_REACHABLE; + FOR_EACH_BB (bb) + bb->flags &= ~BB_REACHABLE; /* Add our starting points to the worklist. Almost always there will be only one. It isn't inconceivable that we might one day directly support Fortran alternate entry points. */ - for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) + FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) { *tos++ = e->dest; @@ -355,7 +307,7 @@ find_unreachable_blocks () { basic_block b = *--tos; - for (e = b->succ; e; e = e->succ_next) + FOR_EACH_EDGE (e, ei, b->succs) if (!(e->dest->flags & BB_REACHABLE)) { *tos++ = e->dest; @@ -380,13 +332,14 @@ find_unreachable_blocks () and the data structure is filled in. */ struct edge_list * -create_edge_list () +create_edge_list (void) { struct edge_list *elist; edge e; int num_edges; - int x; int block_count; + basic_block bb; + edge_iterator ei; block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */ @@ -394,50 +347,30 @@ create_edge_list () /* Determine the number of edges in the flow graph by counting successor edges on each basic block. */ - for (x = 0; x < n_basic_blocks; x++) + FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) { - basic_block bb = BASIC_BLOCK (x); - - for (e = bb->succ; e; e = e->succ_next) - num_edges++; + num_edges += EDGE_COUNT (bb->succs); } - /* Don't forget successors of the entry block. */ - for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) - num_edges++; - elist = (struct edge_list *) xmalloc (sizeof (struct edge_list)); + elist = xmalloc (sizeof (struct edge_list)); elist->num_blocks = block_count; elist->num_edges = num_edges; - elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges); + elist->index_to_edge = xmalloc (sizeof (edge) * num_edges); num_edges = 0; - /* Follow successors of the entry block, and register these edges. */ - for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) - { - elist->index_to_edge[num_edges] = e; - num_edges++; - } - - for (x = 0; x < n_basic_blocks; x++) - { - basic_block bb = BASIC_BLOCK (x); + /* Follow successors of blocks, and register these edges. */ + FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) + FOR_EACH_EDGE (e, ei, bb->succs) + elist->index_to_edge[num_edges++] = e; - /* Follow all successors of blocks, and register these edges. */ - for (e = bb->succ; e; e = e->succ_next) - { - elist->index_to_edge[num_edges] = e; - num_edges++; - } - } return elist; } /* This function free's memory associated with an edge list. */ void -free_edge_list (elist) - struct edge_list *elist; +free_edge_list (struct edge_list *elist) { if (elist) { @@ -449,11 +382,10 @@ free_edge_list (elist) /* This function provides debug output showing an edge list. */ void -print_edge_list (f, elist) - FILE *f; - struct edge_list *elist; +print_edge_list (FILE *f, struct edge_list *elist) { int x; + fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n", elist->num_blocks - 2, elist->num_edges); @@ -477,18 +409,16 @@ print_edge_list (f, elist) extra edges. */ void -verify_edge_list (f, elist) - FILE *f; - struct edge_list *elist; +verify_edge_list (FILE *f, struct edge_list *elist) { - int x, pred, succ, index; + int pred, succ, index; edge e; + basic_block bb, p, s; + edge_iterator ei; - for (x = 0; x < n_basic_blocks; x++) + FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) { - basic_block bb = BASIC_BLOCK (x); - - for (e = bb->succ; e; e = e->succ_next) + FOR_EACH_EDGE (e, ei, bb->succs) { pred = e->src->index; succ = e->dest->index; @@ -498,6 +428,7 @@ verify_edge_list (f, elist) fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ); continue; } + if (INDEX_EDGE_PRED_BB (elist, index)->index != pred) fprintf (f, "*p* Pred for index %d should be %d not %d\n", index, pred, INDEX_EDGE_PRED_BB (elist, index)->index); @@ -506,141 +437,85 @@ verify_edge_list (f, elist) index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index); } } - for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) - { - pred = e->src->index; - succ = e->dest->index; - index = EDGE_INDEX (elist, e->src, e->dest); - if (index == EDGE_INDEX_NO_EDGE) - { - fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ); - continue; - } - if (INDEX_EDGE_PRED_BB (elist, index)->index != pred) - fprintf (f, "*p* Pred for index %d should be %d not %d\n", - index, pred, INDEX_EDGE_PRED_BB (elist, index)->index); - if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ) - fprintf (f, "*p* Succ for index %d should be %d not %d\n", - index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index); - } - /* We've verified that all the edges are in the list, no lets make sure + + /* We've verified that all the edges are in the list, now lets make sure there are no spurious edges in the list. */ - for (pred = 0; pred < n_basic_blocks; pred++) - for (succ = 0; succ < n_basic_blocks; succ++) + FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) + FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) { - basic_block p = BASIC_BLOCK (pred); - basic_block s = BASIC_BLOCK (succ); - int found_edge = 0; - for (e = p->succ; e; e = e->succ_next) + FOR_EACH_EDGE (e, ei, p->succs) if (e->dest == s) { found_edge = 1; break; } - for (e = s->pred; e; e = e->pred_next) + + FOR_EACH_EDGE (e, ei, s->preds) if (e->src == p) { found_edge = 1; break; } - if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ)) + + if (EDGE_INDEX (elist, p, s) == EDGE_INDEX_NO_EDGE && found_edge != 0) fprintf (f, "*** Edge (%d, %d) appears to not have an index\n", - pred, succ); - if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ)) + p->index, s->index); + if (EDGE_INDEX (elist, p, s) != EDGE_INDEX_NO_EDGE && found_edge == 0) fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n", - pred, succ, EDGE_INDEX (elist, BASIC_BLOCK (pred), - BASIC_BLOCK (succ))); + p->index, s->index, EDGE_INDEX (elist, p, s)); } - for (succ = 0; succ < n_basic_blocks; succ++) - { - basic_block p = ENTRY_BLOCK_PTR; - basic_block s = BASIC_BLOCK (succ); +} - int found_edge = 0; +/* Given PRED and SUCC blocks, return the edge which connects the blocks. + If no such edge exists, return NULL. */ - for (e = p->succ; e; e = e->succ_next) - if (e->dest == s) - { - found_edge = 1; - break; - } - for (e = s->pred; e; e = e->pred_next) - if (e->src == p) - { - found_edge = 1; - break; - } - if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ)) - == EDGE_INDEX_NO_EDGE && found_edge != 0) - fprintf (f, "*** Edge (entry, %d) appears to not have an index\n", - succ); - if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ)) - != EDGE_INDEX_NO_EDGE && found_edge == 0) - fprintf (f, "*** Edge (entry, %d) has index %d, but no edge exists\n", - succ, EDGE_INDEX (elist, ENTRY_BLOCK_PTR, - BASIC_BLOCK (succ))); +edge +find_edge (basic_block pred, basic_block succ) +{ + edge e; + edge_iterator ei; + + if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds)) + { + FOR_EACH_EDGE (e, ei, pred->succs) + if (e->dest == succ) + return e; } - for (pred = 0; pred < n_basic_blocks; pred++) + else { - basic_block p = BASIC_BLOCK (pred); - basic_block s = EXIT_BLOCK_PTR; - - int found_edge = 0; - - for (e = p->succ; e; e = e->succ_next) - if (e->dest == s) - { - found_edge = 1; - break; - } - for (e = s->pred; e; e = e->pred_next) - if (e->src == p) - { - found_edge = 1; - break; - } - if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR) - == EDGE_INDEX_NO_EDGE && found_edge != 0) - fprintf (f, "*** Edge (%d, exit) appears to not have an index\n", - pred); - if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR) - != EDGE_INDEX_NO_EDGE && found_edge == 0) - fprintf (f, "*** Edge (%d, exit) has index %d, but no edge exists\n", - pred, EDGE_INDEX (elist, BASIC_BLOCK (pred), - EXIT_BLOCK_PTR)); + FOR_EACH_EDGE (e, ei, succ->preds) + if (e->src == pred) + return e; } + + return NULL; } /* This routine will determine what, if any, edge there is between a specified predecessor and successor. */ int -find_edge_index (edge_list, pred, succ) - struct edge_list *edge_list; - basic_block pred, succ; +find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ) { int x; + for (x = 0; x < NUM_EDGES (edge_list); x++) - { - if (INDEX_EDGE_PRED_BB (edge_list, x) == pred - && INDEX_EDGE_SUCC_BB (edge_list, x) == succ) - return x; - } + if (INDEX_EDGE_PRED_BB (edge_list, x) == pred + && INDEX_EDGE_SUCC_BB (edge_list, x) == succ) + return x; + return (EDGE_INDEX_NO_EDGE); } /* Dump the list of basic blocks in the bitmap NODES. */ void -flow_nodes_print (str, nodes, file) - const char *str; - const sbitmap nodes; - FILE *file; +flow_nodes_print (const char *str, const sbitmap nodes, FILE *file) { int node; @@ -655,11 +530,7 @@ flow_nodes_print (str, nodes, file) /* Dump the list of edges in the array EDGE_LIST. */ void -flow_edge_list_print (str, edge_list, num_edges, file) - const char *str; - const edge *edge_list; - int num_edges; - FILE *file; +flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file) { int i; @@ -670,25 +541,27 @@ flow_edge_list_print (str, edge_list, num_edges, file) for (i = 0; i < num_edges; i++) fprintf (file, "%d->%d ", edge_list[i]->src->index, edge_list[i]->dest->index); + fputs ("}\n", file); } -/* This routine will remove any fake successor edges for a basic block. - When the edge is removed, it is also removed from whatever predecessor +/* This routine will remove any fake predecessor edges for a basic block. + When the edge is removed, it is also removed from whatever successor list it is in. */ static void -remove_fake_successors (bb) - basic_block bb; +remove_fake_predecessors (basic_block bb) { edge e; - for (e = bb->succ; e;) + edge_iterator ei; + + for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) { - edge tmp = e; - e = e->succ_next; - if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE) - remove_edge (tmp); + if ((e->flags & EDGE_FAKE) == EDGE_FAKE) + remove_edge (e); + else + ei_next (&ei); } } @@ -697,29 +570,35 @@ remove_fake_successors (bb) fake predecessors. */ void -remove_fake_edges () +remove_fake_edges (void) { - int x; + basic_block bb; + + FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) + remove_fake_predecessors (bb); +} - for (x = 0; x < n_basic_blocks; x++) - remove_fake_successors (BASIC_BLOCK (x)); +/* This routine will remove all fake edges to the EXIT_BLOCK. */ - /* We've handled all successors except the entry block's. */ - remove_fake_successors (ENTRY_BLOCK_PTR); +void +remove_fake_exit_edges (void) +{ + remove_fake_predecessors (EXIT_BLOCK_PTR); } + /* This function will add a fake edge between any block which has no successors, and the exit block. Some data flow equations require these edges to exist. */ void -add_noreturn_fake_exit_edges () +add_noreturn_fake_exit_edges (void) { - int x; + basic_block bb; - for (x = 0; x < n_basic_blocks; x++) - if (BASIC_BLOCK (x)->succ == NULL) - make_single_succ_edge (BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE); + FOR_EACH_BB (bb) + if (EDGE_COUNT (bb->succs) == 0) + make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); } /* This function adds a fake edge between any infinite loops to the @@ -734,65 +613,65 @@ add_noreturn_fake_exit_edges () nodes not reachable from the exit block. */ void -connect_infinite_loops_to_exit () +connect_infinite_loops_to_exit (void) { - basic_block unvisited_block; + basic_block unvisited_block = EXIT_BLOCK_PTR; + struct depth_first_search_dsS dfs_ds; /* Perform depth-first search in the reverse graph to find nodes reachable from the exit block. */ - struct depth_first_search_dsS dfs_ds; - flow_dfs_compute_reverse_init (&dfs_ds); flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR); /* Repeatedly add fake edges, updating the unreachable nodes. */ while (1) { - unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds); + unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds, + unvisited_block); if (!unvisited_block) break; + make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE); flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block); } flow_dfs_compute_reverse_finish (&dfs_ds); - return; } -/* Compute reverse top sort order */ +/* Compute reverse top sort order. */ + void -flow_reverse_top_sort_order_compute (rts_order) - int *rts_order; +flow_reverse_top_sort_order_compute (int *rts_order) { - edge *stack; + edge_iterator *stack; int sp; int postnum = 0; sbitmap visited; /* Allocate stack for back-tracking up CFG. */ - stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge)); + stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator)); sp = 0; /* Allocate bitmap to track nodes that have been visited. */ - visited = sbitmap_alloc (n_basic_blocks); + visited = sbitmap_alloc (last_basic_block); /* None of the nodes in the CFG have been visited yet. */ sbitmap_zero (visited); /* Push the first edge on to the stack. */ - stack[sp++] = ENTRY_BLOCK_PTR->succ; + stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); while (sp) { - edge e; + edge_iterator ei; basic_block src; basic_block dest; /* Look at the edge on the top of the stack. */ - e = stack[sp - 1]; - src = e->src; - dest = e->dest; + ei = stack[sp - 1]; + src = ei_edge (ei)->src; + dest = ei_edge (ei)->dest; /* Check if the edge destination has been visited yet. */ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) @@ -800,22 +679,20 @@ flow_reverse_top_sort_order_compute (rts_order) /* Mark that we have visited the destination. */ SET_BIT (visited, dest->index); - if (dest->succ) - { - /* Since the DEST node has been visited for the first - time, check its successors. */ - stack[sp++] = dest->succ; - } + if (EDGE_COUNT (dest->succs) > 0) + /* Since the DEST node has been visited for the first + time, check its successors. */ + stack[sp++] = ei_start (dest->succs); else rts_order[postnum++] = dest->index; } else { - if (! e->succ_next && src != ENTRY_BLOCK_PTR) + if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR) rts_order[postnum++] = src->index; - if (e->succ_next) - stack[sp - 1] = e->succ_next; + if (!ei_one_before_end_p (ei)) + ei_next (&stack[sp - 1]); else sp--; } @@ -826,46 +703,44 @@ flow_reverse_top_sort_order_compute (rts_order) } /* Compute the depth first search order and store in the array - DFS_ORDER if non-zero, marking the nodes visited in VISITED. If - RC_ORDER is non-zero, return the reverse completion number for each + DFS_ORDER if nonzero, marking the nodes visited in VISITED. If + RC_ORDER is nonzero, return the reverse completion number for each node. Returns the number of nodes visited. A depth first search tries to get as far away from the starting point as quickly as possible. */ int -flow_depth_first_order_compute (dfs_order, rc_order) - int *dfs_order; - int *rc_order; +flow_depth_first_order_compute (int *dfs_order, int *rc_order) { - edge *stack; + edge_iterator *stack; int sp; int dfsnum = 0; int rcnum = n_basic_blocks - 1; sbitmap visited; /* Allocate stack for back-tracking up CFG. */ - stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge)); + stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator)); sp = 0; /* Allocate bitmap to track nodes that have been visited. */ - visited = sbitmap_alloc (n_basic_blocks); + visited = sbitmap_alloc (last_basic_block); /* None of the nodes in the CFG have been visited yet. */ sbitmap_zero (visited); /* Push the first edge on to the stack. */ - stack[sp++] = ENTRY_BLOCK_PTR->succ; + stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); while (sp) { - edge e; + edge_iterator ei; basic_block src; basic_block dest; /* Look at the edge on the top of the stack. */ - e = stack[sp - 1]; - src = e->src; - dest = e->dest; + ei = stack[sp - 1]; + src = ei_edge (ei)->src; + dest = ei_edge (ei)->dest; /* Check if the edge destination has been visited yet. */ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) @@ -874,34 +749,29 @@ flow_depth_first_order_compute (dfs_order, rc_order) SET_BIT (visited, dest->index); if (dfs_order) - dfs_order[dfsnum++] = dest->index; - - if (dest->succ) - { - /* Since the DEST node has been visited for the first - time, check its successors. */ - stack[sp++] = dest->succ; - } - else - { - /* There are no successors for the DEST node so assign - its reverse completion number. */ - if (rc_order) - rc_order[rcnum--] = dest->index; - } + dfs_order[dfsnum] = dest->index; + + dfsnum++; + + if (EDGE_COUNT (dest->succs) > 0) + /* Since the DEST node has been visited for the first + time, check its successors. */ + stack[sp++] = ei_start (dest->succs); + else if (rc_order) + /* There are no successors for the DEST node so assign + its reverse completion number. */ + rc_order[rcnum--] = dest->index; } else { - if (! e->succ_next && src != ENTRY_BLOCK_PTR) - { - /* There are no more successors for the SRC node - so assign its reverse completion number. */ - if (rc_order) - rc_order[rcnum--] = src->index; - } - - if (e->succ_next) - stack[sp - 1] = e->succ_next; + if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR + && rc_order) + /* There are no more successors for the SRC node + so assign its reverse completion number. */ + rc_order[rcnum--] = src->index; + + if (!ei_one_before_end_p (ei)) + ei_next (&stack[sp - 1]); else sp--; } @@ -910,14 +780,9 @@ flow_depth_first_order_compute (dfs_order, rc_order) free (stack); sbitmap_free (visited); - /* The number of nodes visited should not be greater than - n_basic_blocks. */ - if (dfsnum > n_basic_blocks) - abort (); + /* The number of nodes visited should be the number of blocks. */ + gcc_assert (dfsnum == n_basic_blocks); - /* There are some nodes left in the CFG that are unreachable. */ - if (dfsnum < n_basic_blocks) - abort (); return dfsnum; } @@ -948,21 +813,19 @@ flow_depth_first_order_compute (dfs_order, rc_order) /* Initialize the data structures used for depth-first search on the reverse graph. If INITIALIZE_STACK is nonzero, the exit block is added to the basic block stack. DATA is the current depth-first - search context. If INITIALIZE_STACK is non-zero, there is an + search context. If INITIALIZE_STACK is nonzero, there is an element on the stack. */ static void -flow_dfs_compute_reverse_init (data) - depth_first_search_ds data; +flow_dfs_compute_reverse_init (depth_first_search_ds data) { /* Allocate stack for back-tracking up CFG. */ - data->stack = - (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1)) - * sizeof (basic_block)); + data->stack = xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1)) + * sizeof (basic_block)); data->sp = 0; /* Allocate bitmap to track nodes that have been visited. */ - data->visited_blocks = sbitmap_alloc (n_basic_blocks - (INVALID_BLOCK + 1)); + data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1)); /* None of the nodes in the CFG have been visited yet. */ sbitmap_zero (data->visited_blocks); @@ -975,46 +838,41 @@ flow_dfs_compute_reverse_init (data) block. */ static void -flow_dfs_compute_reverse_add_bb (data, bb) - depth_first_search_ds data; - basic_block bb; +flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb) { data->stack[data->sp++] = bb; - return; + SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)); } -/* Continue the depth-first search through the reverse graph starting - with the block at the stack's top and ending when the stack is - empty. Visited nodes are marked. Returns an unvisited basic - block, or NULL if there is none available. */ +/* Continue the depth-first search through the reverse graph starting with the + block at the stack's top and ending when the stack is empty. Visited nodes + are marked. Returns an unvisited basic block, or NULL if there is none + available. */ static basic_block -flow_dfs_compute_reverse_execute (data) - depth_first_search_ds data; +flow_dfs_compute_reverse_execute (depth_first_search_ds data, + basic_block last_unvisited) { basic_block bb; edge e; - int i; + edge_iterator ei; while (data->sp > 0) { bb = data->stack[--data->sp]; - /* Mark that we have visited this node. */ - if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1))) - { - SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)); - - /* Perform depth-first search on adjacent vertices. */ - for (e = bb->pred; e; e = e->pred_next) - flow_dfs_compute_reverse_add_bb (data, e->src); - } + /* Perform depth-first search on adjacent vertices. */ + FOR_EACH_EDGE (e, ei, bb->preds) + if (!TEST_BIT (data->visited_blocks, + e->src->index - (INVALID_BLOCK + 1))) + flow_dfs_compute_reverse_add_bb (data, e->src); } /* Determine if there are unvisited basic blocks. */ - for (i = n_basic_blocks - (INVALID_BLOCK + 1); --i >= 0;) - if (!TEST_BIT (data->visited_blocks, i)) - return BASIC_BLOCK (i + (INVALID_BLOCK + 1)); + FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb) + if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1))) + return bb; + return NULL; } @@ -1022,10 +880,134 @@ flow_dfs_compute_reverse_execute (data) reverse graph. */ static void -flow_dfs_compute_reverse_finish (data) - depth_first_search_ds data; +flow_dfs_compute_reverse_finish (depth_first_search_ds data) { free (data->stack); sbitmap_free (data->visited_blocks); - return; } + +/* Performs dfs search from BB over vertices satisfying PREDICATE; + if REVERSE, go against direction of edges. Returns number of blocks + found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */ +int +dfs_enumerate_from (basic_block bb, int reverse, + bool (*predicate) (basic_block, void *), + basic_block *rslt, int rslt_max, void *data) +{ + basic_block *st, lbb; + int sp = 0, tv = 0; + + st = xcalloc (rslt_max, sizeof (basic_block)); + rslt[tv++] = st[sp++] = bb; + bb->flags |= BB_VISITED; + while (sp) + { + edge e; + edge_iterator ei; + lbb = st[--sp]; + if (reverse) + { + FOR_EACH_EDGE (e, ei, lbb->preds) + if (!(e->src->flags & BB_VISITED) && predicate (e->src, data)) + { + gcc_assert (tv != rslt_max); + rslt[tv++] = st[sp++] = e->src; + e->src->flags |= BB_VISITED; + } + } + else + { + FOR_EACH_EDGE (e, ei, lbb->succs) + if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data)) + { + gcc_assert (tv != rslt_max); + rslt[tv++] = st[sp++] = e->dest; + e->dest->flags |= BB_VISITED; + } + } + } + free (st); + for (sp = 0; sp < tv; sp++) + rslt[sp]->flags &= ~BB_VISITED; + return tv; +} + + +/* Computing the Dominance Frontier: + + As described in Morgan, section 3.5, this may be done simply by + walking the dominator tree bottom-up, computing the frontier for + the children before the parent. When considering a block B, + there are two cases: + + (1) A flow graph edge leaving B that does not lead to a child + of B in the dominator tree must be a block that is either equal + to B or not dominated by B. Such blocks belong in the frontier + of B. + + (2) Consider a block X in the frontier of one of the children C + of B. If X is not equal to B and is not dominated by B, it + is in the frontier of B. */ + +static void +compute_dominance_frontiers_1 (bitmap *frontiers, basic_block bb, sbitmap done) +{ + edge e; + edge_iterator ei; + basic_block c; + + SET_BIT (done, bb->index); + + /* Do the frontier of the children first. Not all children in the + dominator tree (blocks dominated by this one) are children in the + CFG, so check all blocks. */ + for (c = first_dom_son (CDI_DOMINATORS, bb); + c; + c = next_dom_son (CDI_DOMINATORS, c)) + { + if (! TEST_BIT (done, c->index)) + compute_dominance_frontiers_1 (frontiers, c, done); + } + + /* Find blocks conforming to rule (1) above. */ + FOR_EACH_EDGE (e, ei, bb->succs) + { + if (e->dest == EXIT_BLOCK_PTR) + continue; + if (get_immediate_dominator (CDI_DOMINATORS, e->dest) != bb) + bitmap_set_bit (frontiers[bb->index], e->dest->index); + } + + /* Find blocks conforming to rule (2). */ + for (c = first_dom_son (CDI_DOMINATORS, bb); + c; + c = next_dom_son (CDI_DOMINATORS, c)) + { + unsigned x; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x, bi) + { + if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb) + bitmap_set_bit (frontiers[bb->index], x); + } + } +} + + +void +compute_dominance_frontiers (bitmap *frontiers) +{ + sbitmap done = sbitmap_alloc (last_basic_block); + + timevar_push (TV_DOM_FRONTIERS); + + sbitmap_zero (done); + + compute_dominance_frontiers_1 (frontiers, EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest, done); + + sbitmap_free (done); + + timevar_pop (TV_DOM_FRONTIERS); +} +