/* Control flow graph analysis code for GNU compiler.
Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008
+ 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2010
Free Software Foundation, Inc.
This file is part of GCC.
#include "basic-block.h"
#include "insn-config.h"
#include "recog.h"
-#include "toplev.h"
+#include "diagnostic-core.h"
#include "tm_p.h"
#include "vec.h"
#include "vecprim.h"
+#include "bitmap.h"
+#include "sbitmap.h"
#include "timevar.h"
/* Store the data structures necessary for depth-first search. */
/* This function provides debug output showing an edge list. */
-void
+DEBUG_FUNCTION void
print_edge_list (FILE *f, struct edge_list *elist)
{
int x;
verifying that all edges are present, and that there are no
extra edges. */
-void
+DEBUG_FUNCTION void
verify_edge_list (FILE *f, struct edge_list *elist)
{
int pred, succ, index;
}
\f
/* Compute reverse top sort order. This is computing a post order
- numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then then
+ numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then
ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
true, unreachable blocks are deleted. */
int
-post_order_compute (int *post_order, bool include_entry_exit,
+post_order_compute (int *post_order, bool include_entry_exit,
bool delete_unreachable)
{
edge_iterator *stack;
post_order[post_order_num++] = ENTRY_BLOCK;
count = post_order_num;
}
- else
+ else
count = post_order_num + 2;
-
+
/* Delete the unreachable blocks if some were found and we are
supposed to do it. */
if (delete_unreachable && (count != n_basic_blocks))
for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
{
next_bb = b->next_bb;
-
+
if (!(TEST_BIT (visited, b->index)))
delete_basic_block (b);
}
-
+
tidy_fallthru_edges ();
}
}
-/* Helper routine for inverted_post_order_compute.
+/* Helper routine for inverted_post_order_compute.
BB has to belong to a region of CFG
unreachable by inverted traversal from the exit.
i.e. there's no control flow path from ENTRY to EXIT
This can happen in two cases - if there's an infinite loop
or if there's a block that has no successor
(call to a function with no return).
- Some RTL passes deal with this condition by
- calling connect_infinite_loops_to_exit () and/or
+ Some RTL passes deal with this condition by
+ calling connect_infinite_loops_to_exit () and/or
add_noreturn_fake_exit_edges ().
However, those methods involve modifying the CFG itself
which may not be desirable.
with no successors can't visit all blocks.
To solve this problem, we first do inverted traversal
starting from the blocks with no successor.
- And if there's any block left that's not visited by the regular
+ And if there's any block left that's not visited by the regular
inverted traversal from EXIT,
those blocks are in such problematic region.
- Among those, we find one block that has
+ Among those, we find one block that has
any visited predecessor (which is an entry into such a region),
- and start looking for a "dead end" from that block
+ and start looking for a "dead end" from that block
and do another inverted traversal from that block. */
int
if (EDGE_COUNT (bb->succs) == 0)
{
/* Push the initial edge on to the stack. */
- if (EDGE_COUNT (bb->preds) > 0)
+ if (EDGE_COUNT (bb->preds) > 0)
{
stack[sp++] = ei_start (bb->preds);
SET_BIT (visited, bb->index);
}
}
- do
+ do
{
bool has_unvisited_bb = false;
}
}
- /* Detect any infinite loop and activate the kludge.
+ /* Detect any infinite loop and activate the kludge.
Note that this doesn't check EXIT_BLOCK itself
since EXIT_BLOCK is always added after the outer do-while loop. */
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
if (has_unvisited_bb && sp == 0)
{
- /* No blocks are reachable from EXIT at all.
+ /* No blocks are reachable from EXIT at all.
Find a dead-end from the ENTRY, and restart the iteration. */
basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR);
gcc_assert (be != NULL);
stack[sp++] = ei_start (be->preds);
}
- /* The only case the below while fires is
+ /* The only case the below while fires is
when there's an infinite loop. */
}
while (sp);
REV_POST_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.
+ possible.
pre_order is a really a preorder numbering of the graph.
rev_post_order is really a reverse postorder numbering of the graph.
*/
int
-pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
+pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
bool include_entry_exit)
{
edge_iterator *stack;
if (rev_post_order)
rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
}
- else
+ else
rev_post_order_num -= NUM_FIXED_BLOCKS;
/* Allocate bitmap to track nodes that have been visited. */
static sbitmap visited;
static unsigned v_size;
-#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
-#define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index))
-#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
+#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
+#define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index))
+#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
/* Resize the VISITED sbitmap if necessary. */
- size = last_basic_block;
+ size = last_basic_block;
if (size < 10)
size = 10;
static void
-compute_dominance_frontiers_1 (bitmap *frontiers)
+compute_dominance_frontiers_1 (bitmap_head *frontiers)
{
edge p;
edge_iterator ei;
domsb = get_immediate_dominator (CDI_DOMINATORS, b);
while (runner != domsb)
{
- if (bitmap_bit_p (frontiers[runner->index], b->index))
+ if (!bitmap_set_bit (&frontiers[runner->index],
+ b->index))
break;
- bitmap_set_bit (frontiers[runner->index],
- b->index);
runner = get_immediate_dominator (CDI_DOMINATORS,
runner);
}
void
-compute_dominance_frontiers (bitmap *frontiers)
+compute_dominance_frontiers (bitmap_head *frontiers)
{
timevar_push (TV_DOM_FRONTIERS);
allocated for the return value. */
bitmap
-compute_idf (bitmap def_blocks, bitmap *dfs)
+compute_idf (bitmap def_blocks, bitmap_head *dfs)
{
bitmap_iterator bi;
unsigned bb_index, i;
we may pull a non-existing block from the work stack. */
gcc_assert (bb_index < (unsigned) last_basic_block);
- EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points,
+ EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points,
0, i, bi)
{
/* Use a safe push because if there is a definition of VAR
OSDN Git Service
