[dataflow]: PATCH: worklist based dataflow solver
Seongbae Park
seongbae.park@gmail.com
Tue Jan 9 17:00:00 GMT 2007
This patch cuts the time spent in dataflow solver in half, when
compiling top 5 largest files for building cc1. For one analysis
(reaching store problem used during dse),
traversing in the order of the reverse postorder of inverted CFG
for the forward problems reduces the block visit count by 90%.
The worklist based algorithm reduces it by couple % further.
Bootstrapped and regression tested on x86-64. OK?
2007-01-09 Seongbae Park <seongbae.park@gmail.com>
* df-core.c (rest_of_handle_df_initialize): Allocate and free new
fields struct dataflow::{postorder_inverted,n_blocks_inverted}.
(df_hybrid_search_forward, df_hybrid_search_backward): Pass visited,
pending, considered as parameters instead of fields of struct df.
(df_worklist_propagate_forward, df_worklist_propagate_backward,
df_worklist_dataflow): New functions.
(df_iterative_dataflow): Remove visited, pending, considered
fields from struct dataflow.
(df_analyze): Allocate and free new fields
df::{postorder_inverted,n_blocks_inverted}.
(df_get_n_blocks, df_get_postorder): Make them return
different values depending on the direction of the dataflow problem.
(df_simple_dataflow): Renamed from df_simple_iterative_dataflow.
Call df_worklist_dataflow instead of df_iterative_dataflow.
* cfganal.c (dfs_find_deadend, inverted_post_order_compute):
New functions.
* df.h (struct dataflow): Remove fields visited, pending, considered.
Add new fields postorder_inverted, n_blocks_inverted.
(df_get_nblocks, df_get_postorder): Prototype change.
(df_simple_dataflow): Renamed from df_simple_iterative_dataflow.
(df_worklist_dataflow): New function prototype.
* df-problems.c: Use df_worklist_dataflow instead of
df_iterative_dataflow for solver.
* basic-block.h (inverted_post_order_compute): New function prototype.
* dce.c (dce_process_block): Pass extra parameter to df_get_n_blocks
and df_get_postorder.
(calculate_reaching_stores): Call df_simple_dataflow,
renamed from df_simple_iterative_dataflow.
--
#pragma ident "Seongbae Park, compiler, http://seongbae.blogspot.com"
-------------- next part --------------
Index: gcc/df-core.c
===================================================================
--- gcc/df-core.c (revision 120620)
+++ gcc/df-core.c (working copy)
@@ -686,7 +686,10 @@ rest_of_handle_df_initialize (void)
df_live_add_problem ();
df->postorder = XNEWVEC (int, last_basic_block);
+ df->postorder_inverted = XNEWVEC (int, last_basic_block);
df->n_blocks = post_order_compute (df->postorder, true, true);
+ df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
+ gcc_assert (df->n_blocks == df->n_blocks_inverted);
df->hard_regs_live_count = XNEWVEC (unsigned int, FIRST_PSEUDO_REGISTER);
memset (df->hard_regs_live_count, 0,
@@ -738,6 +741,8 @@ rest_of_handle_df_finish (void)
if (df->postorder)
free (df->postorder);
+ if (df->postorder_inverted)
+ free (df->postorder_inverted);
free (df->hard_regs_live_count);
free (df);
df = NULL;
@@ -777,6 +782,9 @@ struct tree_opt_pass pass_df_finish =
static void
df_hybrid_search_forward (basic_block bb,
+ sbitmap pending,
+ sbitmap visited,
+ sbitmap considered,
struct dataflow *dataflow)
{
int result_changed;
@@ -784,15 +792,15 @@ df_hybrid_search_forward (basic_block bb
edge e;
edge_iterator ei;
- SET_BIT (dataflow->visited, bb->index);
- gcc_assert (TEST_BIT (dataflow->pending, bb->index));
- RESET_BIT (dataflow->pending, i);
+ SET_BIT (visited, bb->index);
+ gcc_assert (TEST_BIT (pending, bb->index));
+ RESET_BIT (pending, i);
/* Calculate <conf_op> of predecessor_outs. */
if (EDGE_COUNT (bb->preds) > 0)
FOR_EACH_EDGE (e, ei, bb->preds)
{
- if (!TEST_BIT (dataflow->considered, e->src->index))
+ if (!TEST_BIT (considered, e->src->index))
continue;
dataflow->problem->con_fun_n (e);
@@ -809,25 +817,37 @@ df_hybrid_search_forward (basic_block bb
{
if (e->dest->index == i)
continue;
- if (!TEST_BIT (dataflow->considered, e->dest->index))
+ if (!TEST_BIT (considered, e->dest->index))
continue;
- SET_BIT (dataflow->pending, e->dest->index);
+ SET_BIT (pending, e->dest->index);
}
-
+
+ /* This loop below defeats the reverse postorder traversal completely,
+ because on the first block of the CFG,
+ this code visits the block by the DFS order
+ all the way down to the bottom. */
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e->dest->index == i)
continue;
- if (!TEST_BIT (dataflow->considered, e->dest->index))
+ if (!TEST_BIT (considered, e->dest->index))
continue;
- if (!TEST_BIT (dataflow->visited, e->dest->index))
- df_hybrid_search_forward (e->dest, dataflow);
+
+ if (!TEST_BIT (visited, e->dest->index))
+ df_hybrid_search_forward (e->dest,
+ pending,
+ visited,
+ considered,
+ dataflow);
}
}
static void
df_hybrid_search_backward (basic_block bb,
+ sbitmap pending,
+ sbitmap visited,
+ sbitmap considered,
struct dataflow *dataflow)
{
int result_changed;
@@ -835,15 +855,15 @@ df_hybrid_search_backward (basic_block b
edge e;
edge_iterator ei;
- SET_BIT (dataflow->visited, bb->index);
- gcc_assert (TEST_BIT (dataflow->pending, bb->index));
- RESET_BIT (dataflow->pending, i);
+ SET_BIT (visited, bb->index);
+ gcc_assert (TEST_BIT (pending, bb->index));
+ RESET_BIT (pending, i);
/* Calculate <conf_op> of predecessor_outs. */
if (EDGE_COUNT (bb->succs) > 0)
FOR_EACH_EDGE (e, ei, bb->succs)
{
- if (!TEST_BIT (dataflow->considered, e->dest->index))
+ if (!TEST_BIT (considered, e->dest->index))
continue;
dataflow->problem->con_fun_n (e);
@@ -861,26 +881,189 @@ df_hybrid_search_backward (basic_block b
if (e->src->index == i)
continue;
- if (!TEST_BIT (dataflow->considered, e->src->index))
+ if (!TEST_BIT (considered, e->src->index))
continue;
- SET_BIT (dataflow->pending, e->src->index);
+ SET_BIT (pending, e->src->index);
}
+ /* This loop below defeats the reverse postorder traversal completely,
+ because on the first block of the CFG,
+ this code visits the block by the DFS order
+ all the way down to the bottom. */
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (e->src->index == i)
continue;
- if (!TEST_BIT (dataflow->considered, e->src->index))
+ if (!TEST_BIT (considered, e->src->index))
continue;
-
- if (!TEST_BIT (dataflow->visited, e->src->index))
- df_hybrid_search_backward (e->src, dataflow);
+
+ if (!TEST_BIT (visited, e->src->index))
+ df_hybrid_search_backward (e->src,
+ pending,
+ visited,
+ considered,
+ dataflow);
}
}
+/* Helper function for df_worklist_dataflow.
+ Propagate the dataflow forward.
+ Given a BB_INDEX, do the dataflow propagation
+ and set bits on for successors in PENDING
+ if the out set of the dataflow has changed. */
+
+static void
+df_worklist_propagate_forward (struct dataflow *dataflow,
+ unsigned bb_index,
+ unsigned *bbindex_to_postorder,
+ bitmap pending,
+ sbitmap considered)
+{
+ edge e;
+ edge_iterator ei;
+ basic_block bb = BASIC_BLOCK (bb_index);
+
+ /* Calculate <conf_op> of incoming edges. */
+ if (EDGE_COUNT (bb->preds) > 0)
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (TEST_BIT (considered, e->src->index))
+ dataflow->problem->con_fun_n (e);
+ }
+ else if (dataflow->problem->con_fun_0)
+ dataflow->problem->con_fun_0 (bb);
+
+ if (dataflow->problem->trans_fun (bb_index))
+ {
+ /* The out set of this block has changed.
+ Propagate to the outgoing blocks. */
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ unsigned ob_index = e->dest->index;
+
+ if (TEST_BIT (considered, ob_index))
+ bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
+ }
+ }
+}
+
+
+/* Helper function for df_worklist_dataflow.
+ Propagate the dataflow backward. */
+
+static void
+df_worklist_propagate_backward (struct dataflow *dataflow,
+ unsigned bb_index,
+ unsigned *bbindex_to_postorder,
+ bitmap pending,
+ sbitmap considered)
+{
+ edge e;
+ edge_iterator ei;
+ basic_block bb = BASIC_BLOCK (bb_index);
+
+ /* Calculate <conf_op> of incoming edges. */
+ if (EDGE_COUNT (bb->succs) > 0)
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (TEST_BIT (considered, e->dest->index))
+ dataflow->problem->con_fun_n (e);
+ }
+ else if (dataflow->problem->con_fun_0)
+ dataflow->problem->con_fun_0 (bb);
+
+ if (dataflow->problem->trans_fun (bb_index))
+ {
+ /* The out set of this block has changed.
+ Propagate to the outgoing blocks. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ unsigned ob_index = e->src->index;
+
+ if (TEST_BIT (considered, ob_index))
+ bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
+ }
+ }
+}
+
+
+/* Worklist-based dataflow solver. It uses sbitmap as a worklist,
+ with "n"-th bit representing the n-th block in the reverse-postorder order.
+ This is so-called over-eager algorithm where it propagates
+ changes on demand. This algorithm may visit blocks more than
+ iterative method if there are deeply nested loops.
+ Worklist algorithm works better than iterative algorithm
+ for CFGs with no nested loops.
+ In practice, the measurement shows worklist algorithm beats
+ iterative algorithm by some margin overall. */
+
+void
+df_worklist_dataflow (struct dataflow *dataflow,
+ bitmap blocks_to_consider,
+ int *blocks_in_postorder,
+ int n_blocks)
+{
+ bitmap pending = BITMAP_ALLOC (NULL);
+ sbitmap considered = sbitmap_alloc (last_basic_block);
+ bitmap_iterator bi;
+ unsigned int *bbindex_to_postorder;
+ int i;
+ unsigned int index;
+ enum df_flow_dir dir = dataflow->problem->dir;
+
+ gcc_assert (dir);
+
+ /* BBINDEX_TO_POSTORDER maps the bb->index to the reverse postorder. */
+ bbindex_to_postorder = (unsigned int *)xmalloc (last_basic_block * sizeof (unsigned int));
+
+ /* Initialize the array to an out-of-bound value. */
+ for (i = 0; i < last_basic_block; i++)
+ bbindex_to_postorder[i] = last_basic_block;
+
+ sbitmap_zero (considered);
+
+ EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
+ {
+ SET_BIT (considered, index);
+ }
+
+ for (i = 0; i < n_blocks; i++)
+ {
+ bbindex_to_postorder[blocks_in_postorder[i]] = i;
+ /* Add all blocks to the worklist. */
+ bitmap_set_bit (pending, i);
+ }
+
+ dataflow->problem->init_fun (blocks_to_consider);
+
+ while (!bitmap_empty_p (pending))
+ {
+ unsigned bb_index;
+
+ index = bitmap_first_set_bit (pending);
+ bitmap_clear_bit (pending, index);
+
+ bb_index = blocks_in_postorder[index];
+
+ if (dir == DF_FORWARD)
+ df_worklist_propagate_forward (dataflow, bb_index,
+ bbindex_to_postorder,
+ pending, considered);
+ else
+ df_worklist_propagate_backward (dataflow, bb_index,
+ bbindex_to_postorder,
+ pending, considered);
+ }
+
+ BITMAP_FREE (pending);
+ sbitmap_free (considered);
+ free (bbindex_to_postorder);
+}
+
+
/* This function will perform iterative bitvector dataflow described
by DATAFLOW, producing the in and out sets. Only the part of the
cfg induced by blocks in DATAFLOW->order is taken into account. */
@@ -897,10 +1080,6 @@ df_iterative_dataflow (struct dataflow *
sbitmap considered = sbitmap_alloc (last_basic_block);
bitmap_iterator bi;
- dataflow->visited = visited;
- dataflow->pending = pending;
- dataflow->considered = considered;
-
sbitmap_zero (visited);
sbitmap_zero (pending);
sbitmap_zero (considered);
@@ -930,27 +1109,26 @@ df_iterative_dataflow (struct dataflow *
The nodes are passed into this function in postorder. */
- if (dataflow->problem->dir == DF_FORWARD)
- {
- for (i = n_blocks - 1 ; i >= 0 ; i--)
- {
- idx = blocks_in_postorder[i];
-
- if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
- df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow);
- }
- }
- else
- {
- for (i = 0; i < n_blocks; i++)
- {
- idx = blocks_in_postorder[i];
-
- if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
- df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow);
- }
- }
-
+ for (i = 0; i < n_blocks; i++)
+ {
+ idx = blocks_in_postorder[i];
+
+ if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
+ {
+ if (dataflow->problem->dir == DF_FORWARD)
+ df_hybrid_search_forward (BASIC_BLOCK (idx),
+ pending,
+ visited,
+ considered,
+ dataflow);
+ else
+ df_hybrid_search_backward (BASIC_BLOCK (idx),
+ pending,
+ visited,
+ considered,
+ dataflow);
+ }
+ }
if (sbitmap_first_set_bit (pending) == -1)
break;
@@ -1035,8 +1213,12 @@ df_analyze (void)
if (df->postorder)
free (df->postorder);
+ if (df->postorder_inverted)
+ free (df->postorder_inverted);
df->postorder = XNEWVEC (int, last_basic_block);
+ df->postorder_inverted = XNEWVEC (int, last_basic_block);
df->n_blocks = post_order_compute (df->postorder, true, true);
+ df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
/* We need to do this before the df_verify_all because this is
not kept incrementally up to date. */
@@ -1051,6 +1233,8 @@ df_analyze (void)
for (i = 0; i < df->n_blocks; i++)
bitmap_set_bit (current_all_blocks, df->postorder[i]);
+ for (i = 0; i < df->n_blocks_inverted; i++)
+ gcc_assert (bitmap_bit_p (current_all_blocks, df->postorder_inverted[i]));
/* Make sure that we have pruned any unreachable blocks from these
sets. */
@@ -1060,6 +1244,9 @@ df_analyze (void)
bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
df->n_blocks = df_prune_to_subcfg (df->postorder,
df->n_blocks, df->blocks_to_analyze);
+ df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted,
+ df->n_blocks_inverted,
+ df->blocks_to_analyze);
BITMAP_FREE (current_all_blocks);
}
else
@@ -1074,9 +1261,18 @@ df_analyze (void)
{
struct dataflow *dflow = df->problems_in_order[i];
if (dflow->solutions_dirty)
- df_analyze_problem (dflow,
- df->blocks_to_analyze,
- df->postorder, df->n_blocks);
+ {
+ if (dflow->problem->dir == DF_FORWARD)
+ df_analyze_problem (dflow,
+ df->blocks_to_analyze,
+ df->postorder_inverted,
+ df->n_blocks_inverted);
+ else
+ df_analyze_problem (dflow,
+ df->blocks_to_analyze,
+ df->postorder,
+ df->n_blocks);
+ }
}
if (everything)
@@ -1094,17 +1290,35 @@ df_analyze (void)
/* Return the number of basic blocks from the last call to df_analyze. */
int
-df_get_n_blocks (void)
+df_get_n_blocks (enum df_flow_dir dir)
{
+ gcc_assert (dir != DF_NONE);
+
+ if (dir == DF_FORWARD)
+ {
+ gcc_assert (df->postorder_inverted);
+ return df->n_blocks_inverted;
+ }
+
gcc_assert (df->postorder);
return df->n_blocks;
}
-/* Return a pointer to the array of basic blocks from the last call to df_analyze. */
+/* Return a pointer to the array of basic blocks in the reverse postorder.
+ Depending on the direction of the dataflow problem,
+ it returns either the usual reverse postorder array
+ or the reverse postorder of inverted traversal. */
int *
-df_get_postorder (void)
+df_get_postorder (enum df_flow_dir dir)
{
+ gcc_assert (dir != DF_NONE);
+
+ if (dir == DF_FORWARD)
+ {
+ gcc_assert (df->postorder_inverted);
+ return df->postorder_inverted;
+ }
gcc_assert (df->postorder);
return df->postorder;
}
@@ -1121,12 +1335,12 @@ static struct dataflow user_dflow;
postorder, and N_BLOCKS, the number of blocks in POSTORDER. */
void
-df_simple_iterative_dataflow (enum df_flow_dir dir,
- df_init_function init_fun,
- df_confluence_function_0 con_fun_0,
- df_confluence_function_n con_fun_n,
- df_transfer_function trans_fun,
- bitmap blocks, int * postorder, int n_blocks)
+df_simple_dataflow (enum df_flow_dir dir,
+ df_init_function init_fun,
+ df_confluence_function_0 con_fun_0,
+ df_confluence_function_n con_fun_n,
+ df_transfer_function trans_fun,
+ bitmap blocks, int * postorder, int n_blocks)
{
memset (&user_problem, 0, sizeof (struct df_problem));
user_problem.dir = dir;
@@ -1135,7 +1349,7 @@ df_simple_iterative_dataflow (enum df_fl
user_problem.con_fun_n = con_fun_n;
user_problem.trans_fun = trans_fun;
user_dflow.problem = &user_problem;
- df_iterative_dataflow (&user_dflow, blocks, postorder, n_blocks);
+ df_worklist_dataflow (&user_dflow, blocks, postorder, n_blocks);
}
@@ -2005,4 +2219,3 @@ debug_df_chain (struct df_link *link)
df_chain_dump (link, stderr);
fputc ('\n', stderr);
}
-
Index: gcc/cfganal.c
===================================================================
--- gcc/cfganal.c (revision 120620)
+++ gcc/cfganal.c (working copy)
@@ -742,6 +742,209 @@ post_order_compute (int *post_order, boo
return post_order_num;
}
+
+/* Helper routine for inverted_post_order_compute.
+ BB has to belong to an region of CFG
+ unreachable by inverted traversal of the CFG from the exit.
+ i.e. there's no control flow path from ENTRY to EXIT
+ that contains this BB.
+ 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).
+ Other part of the RTL passes deal with this by
+ calling connect_infinite_loops_to_exit () or
+ add_noreturn_fake_exit_edges (),
+ but this function is used for the dataflow computation
+ which might be used by a pass that requires
+ not to change the CFG. Hence, we deal with
+ the infinite loop/no return cases by identifying
+ a unique basic block that can reach all blocks
+ in the region when traversed in inverted CFG.
+ This function returns a basic block that satisfies:
+ 1) the block has no successor
+ or
+ 2) the block that is at the bottom of the infinite loop
+ in a DFS search.
+
+ It's guaranteed that all blocks in the region
+ that BB belongs to are reachable
+ by an inverted traversal on the returned basic block.
+ */
+
+static basic_block
+dfs_find_deadend (basic_block bb)
+{
+ sbitmap visited = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (visited);
+
+ for (;;)
+ {
+ SET_BIT (visited, bb->index);
+ if (EDGE_COUNT (bb->succs) == 0
+ || TEST_BIT (visited, EDGE_SUCC (bb, 0)->dest->index))
+ {
+ sbitmap_free (visited);
+ return bb;
+ }
+
+ bb = EDGE_SUCC (bb, 0)->dest;
+ }
+
+ sbitmap_free (visited);
+ return NULL;
+}
+
+
+/* Compute reverse top sort order with the inverted CFG
+ i.e. starting from the exit block and following the edges backward
+ (from successors to predecessors.
+ This is mainly used for getting the reverse post-order
+ for forward dataflow problems.
+
+ This function assumes that all blocks in the CFG are reachable
+ from the entry (but not necessarily from EXIT by traversal of inverted CFG).
+
+ The problematic condition occurs when there's an infinite loop
+ or a non-exit block with no successor in the CFG,
+ which means a simple inverted traversal starting from the exit
+ can't assign the order for all reachable blocks.
+ To solve this problem, we first start with the exit block
+ and do the usual traversal from the exit.
+ If there are any block left that's not visited by this method,
+ those blocks are in such problematic region.
+ 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 do another inverted traversal from that block. */
+
+int
+inverted_post_order_compute (int *post_order)
+{
+ basic_block bb;
+ edge_iterator *stack;
+ int sp;
+ int post_order_num = 0;
+ sbitmap visited;
+
+ /* Allocate stack for back-tracking up CFG. */
+ stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
+ sp = 0;
+
+ /* Allocate bitmap to track nodes that have been visited. */
+ visited = sbitmap_alloc (last_basic_block);
+
+ /* None of the nodes in the CFG have been visited yet. */
+ sbitmap_zero (visited);
+
+ /* Put all blocks that have no successor into the initial work list. */
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+ if (EDGE_COUNT (bb->succs) == 0)
+ {
+ /* Push the initial edge on to the stack. */
+ if (EDGE_COUNT (bb->preds) > 0)
+ {
+ stack[sp++] = ei_start (bb->preds);
+ SET_BIT (visited, bb->index);
+ }
+ }
+
+ do
+ {
+ bool has_unvisited_bb = false;
+
+ /* The inverted traversal loop. */
+ while (sp)
+ {
+ edge_iterator ei;
+ basic_block src;
+ basic_block dest;
+
+ /* Look at the edge on the top of the stack. */
+ ei = stack[sp - 1];
+ src = ei_edge (ei)->dest;
+ dest = ei_edge (ei)->src;
+
+ /* Check if the edge destination has been visited yet. */
+ if (! TEST_BIT (visited, dest->index))
+ {
+ /* Mark that we have visited the destination. */
+ SET_BIT (visited, dest->index);
+
+ if (EDGE_COUNT (dest->preds) > 0)
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack[sp++] = ei_start (dest->preds);
+ else
+ post_order[post_order_num++] = dest->index;
+ }
+ else
+ {
+ if (src != EXIT_BLOCK_PTR && ei_one_before_end_p (ei))
+ post_order[post_order_num++] = src->index;
+
+ if (!ei_one_before_end_p (ei))
+ ei_next (&stack[sp - 1]);
+ else
+ sp--;
+ }
+ }
+
+ /* Detect inifinite loop and activate the kludge.
+ Note that this loop doesn't check EXIT_BLOCK itself.
+ It is always added after the outer do-while loop below. */
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ if (!TEST_BIT (visited, bb->index))
+ {
+ has_unvisited_bb = true;
+
+ if (EDGE_COUNT (bb->preds) > 0)
+ {
+ edge_iterator ei;
+ edge e;
+ basic_block visited_pred = NULL;
+
+
+ /* Find an already visited predecessor. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (TEST_BIT (visited, e->src->index))
+ visited_pred = e->src;
+ }
+
+ if (visited_pred)
+ {
+ basic_block be = dfs_find_deadend (bb);
+ gcc_assert (be != NULL);
+ SET_BIT (visited, be->index);
+ stack[sp++] = ei_start (be->preds);
+ break;
+ }
+ }
+ }
+
+ if (has_unvisited_bb == true && sp == 0)
+ {
+ /* 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);
+ SET_BIT (visited, be->index);
+ stack[sp++] = ei_start (be->preds);
+ }
+
+ /* The only case the below while fires is
+ when there's an infinite loop. */
+ }
+ while (sp);
+
+ /* EXIT_BLOCK is always included. */
+ post_order[post_order_num++] = EXIT_BLOCK;
+
+ free (stack);
+ sbitmap_free (visited);
+ return post_order_num;
+}
+
/* Compute the depth first search order and store in the array
PRE_ORDER if nonzero, marking the nodes visited in VISITED. If
REV_POST_ORDER is nonzero, return the reverse completion number for each
@@ -1102,4 +1305,3 @@ compute_dominance_frontiers (bitmap *fro
timevar_pop (TV_DOM_FRONTIERS);
}
-
Index: gcc/df.h
===================================================================
--- gcc/df.h (revision 120620)
+++ gcc/df.h (working copy)
@@ -237,9 +237,6 @@ struct dataflow
{
struct df_problem *problem; /* The problem to be solved. */
- /* Communication between iterative_dataflow and hybrid_search. */
- sbitmap visited, pending, considered;
-
/* Array indexed by bb->index, that contains basic block problem and
solution specific information. */
void **block_info;
@@ -487,8 +484,13 @@ struct df
bitmap insns_to_delete;
bitmap insns_to_rescan;
bitmap insns_to_notes_rescan;
- int *postorder; /* The current set of basic blocks in postorder. */
- int n_blocks; /* The number of blocks in postorder. */
+ int *postorder; /* The current set of basic blocks
+ in reverse postorder. */
+ int *postorder_inverted; /* The current set of basic blocks
+ in reverse postorder of inverted CFG. */
+ int n_blocks; /* The number of blocks in reverse postorder. */
+ int n_blocks_inverted; /* The number of blocks
+ in reverse postorder of inverted CFG. */
/* An array [FIRST_PSEUDO_REGISTER], indexed by regno, of the number of
refs that qualify as being in regs_ever_live. */
@@ -808,11 +810,11 @@ extern void df_remove_problem (struct da
extern void df_finish_pass (void);
extern void df_analyze_problem (struct dataflow *, bitmap, int *, int);
extern void df_analyze (void);
-extern int df_get_n_blocks (void);
-extern int *df_get_postorder (void);
-extern void df_simple_iterative_dataflow (enum df_flow_dir, df_init_function,
- df_confluence_function_0, df_confluence_function_n,
- df_transfer_function, bitmap, int *, int);
+extern int df_get_n_blocks (enum df_flow_dir);
+extern int *df_get_postorder (enum df_flow_dir);
+extern void df_simple_dataflow (enum df_flow_dir, df_init_function,
+ df_confluence_function_0, df_confluence_function_n,
+ df_transfer_function, bitmap, int *, int);
extern void df_mark_solutions_dirty (void);
extern bool df_get_bb_dirty (basic_block);
extern void df_set_bb_dirty (basic_block);
@@ -832,6 +834,7 @@ extern bool df_reg_defined (rtx, rtx);
extern struct df_ref *df_find_use (rtx, rtx);
extern bool df_reg_used (rtx, rtx);
extern void df_iterative_dataflow (struct dataflow *,bitmap, int *, int);
+extern void df_worklist_dataflow (struct dataflow *,bitmap, int *, int);
extern void df_print_regset (FILE *file, bitmap r);
extern void df_dump (FILE *);
extern void df_dump_start (FILE *);
Index: gcc/df-problems.c
===================================================================
--- gcc/df-problems.c (revision 120620)
+++ gcc/df-problems.c (working copy)
@@ -743,7 +743,7 @@ static struct df_problem problem_RU =
df_ru_free_bb_info, /* Free basic block info. */
df_ru_local_compute, /* Local compute function. */
df_ru_init_solution, /* Init the solution specific data. */
- df_iterative_dataflow, /* Iterative solver. */
+ df_worklist_dataflow, /* Worklist solver. */
NULL, /* Confluence operator 0. */
df_ru_confluence_n, /* Confluence operator n. */
df_ru_transfer_function, /* Transfer function. */
@@ -1285,7 +1285,7 @@ static struct df_problem problem_RD =
df_rd_free_bb_info, /* Free basic block info. */
df_rd_local_compute, /* Local compute function. */
df_rd_init_solution, /* Init the solution specific data. */
- df_iterative_dataflow, /* Iterative solver. */
+ df_worklist_dataflow, /* Worklist solver. */
NULL, /* Confluence operator 0. */
df_rd_confluence_n, /* Confluence operator n. */
df_rd_transfer_function, /* Transfer function. */
@@ -1966,7 +1966,7 @@ static struct df_problem problem_LR =
df_lr_free_bb_info, /* Free basic block info. */
df_lr_local_compute, /* Local compute function. */
df_lr_init, /* Init the solution specific data. */
- df_iterative_dataflow, /* Iterative solver. */
+ df_worklist_dataflow, /* Worklist solver. */
df_lr_confluence_0, /* Confluence operator 0. */
df_lr_confluence_n, /* Confluence operator n. */
df_lr_transfer_function, /* Transfer function. */
@@ -2517,7 +2517,7 @@ static struct df_problem problem_UR =
df_ur_free_bb_info, /* Free basic block info. */
df_ur_local_compute, /* Local compute function. */
df_ur_init, /* Init the solution specific data. */
- df_iterative_dataflow, /* Iterative solver. */
+ df_worklist_dataflow, /* Worklist solver. */
NULL, /* Confluence operator 0. */
df_ur_confluence_n, /* Confluence operator n. */
df_ur_transfer_function, /* Transfer function. */
@@ -3396,7 +3396,7 @@ static struct df_problem problem_UREC =
df_urec_free_bb_info, /* Free basic block info. */
df_urec_local_compute, /* Local compute function. */
df_urec_init, /* Init the solution specific data. */
- df_iterative_dataflow, /* Iterative solver. */
+ df_worklist_dataflow, /* Worklist solver. */
NULL, /* Confluence operator 0. */
df_urec_confluence_n, /* Confluence operator n. */
df_urec_transfer_function, /* Transfer function. */
Index: gcc/basic-block.h
===================================================================
--- gcc/basic-block.h (revision 120620)
+++ gcc/basic-block.h (working copy)
@@ -513,6 +513,7 @@ extern void redirect_edge_pred (edge, ba
extern basic_block create_basic_block_structure (rtx, rtx, rtx, basic_block);
extern void clear_bb_flags (void);
extern int post_order_compute (int *, bool, bool);
+extern int inverted_post_order_compute (int *);
extern int pre_and_rev_post_order_compute (int *, int *, bool);
extern int dfs_enumerate_from (basic_block, int,
bool (*)(basic_block, void *),
Index: gcc/dce.c
===================================================================
--- gcc/dce.c (revision 120620)
+++ gcc/dce.c (working copy)
@@ -604,8 +604,8 @@ dce_process_block (basic_block bb, bool
static void
fast_dce (void)
{
- int *postorder = df_get_postorder ();
- int n_blocks = df_get_n_blocks ();
+ int *postorder = df_get_postorder (DF_BACKWARD);
+ int n_blocks = df_get_n_blocks (DF_BACKWARD);
int i;
/* The set of blocks that have been seen on this iteration. */
bitmap processed = BITMAP_ALLOC (NULL);
@@ -1043,8 +1043,8 @@ init_rs_dflow (void)
out_vec = XNEWVEC (bitmap, last_basic_block);
gen_vec = XNEWVEC (bitmap, last_basic_block);
kill_vec = XNEWVEC (bitmap, last_basic_block);
- n_blocks = df_get_n_blocks ();
- postorder = df_get_postorder ();
+ n_blocks = df_get_n_blocks (DF_FORWARD);
+ postorder = df_get_postorder (DF_FORWARD);
iterating = BITMAP_ALLOC (NULL);
num_stores = VEC_length (store_info, stores.stores);
@@ -1492,9 +1492,9 @@ static void
calculate_reaching_stores (void)
{
htab_traverse (stores.bases, store_base_global, NULL);
- df_simple_iterative_dataflow (DF_FORWARD, rs_init, NULL,
- rs_confluence, rs_transfer_function,
- iterating, postorder, n_blocks);
+ df_simple_dataflow (DF_FORWARD, rs_init, NULL,
+ rs_confluence, rs_transfer_function,
+ iterating, postorder, n_blocks);
finish_max_in_luid ();
if (dump_file)
dump_stores (dump_file);
More information about the Gcc-patches
mailing list