This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH]: Improve iterative dataflow iteration algorithm
- From: Daniel Berlin <dan at cgsoftware dot com>
- To: <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 22 Nov 2001 12:15:58 -0500 (EST)
- Subject: [PATCH]: Improve iterative dataflow iteration algorithm
Jan pointed out a testcase where it takes a long time for the iteration to
converge.
This is because currently, in some cases, we'd end up redoing blocks as
soon as they were marked changed, becuase they were earlier in the DFS
order.
When you have 490 blcks where 400 of them have 50 preds and succs, this
causes a problem. :)
This changes the algotihm to be a hybrid worklist/iterative search
algorithm from "Implementation techniques for efficient dataflow analysis
of large programs".
It makes sure a given block is only touched at most once per iteration,
and by recording changed blocks on a different list, and adding them to
the worklist after the current iteration.
It used to take 230,000 iterations to converge, it now takes 2 (and 15
seconds vs 0.86).
Verified to not change the results, and bootstrapped on
powerpc-unknown-linux-gnu.
--Dan
2001-11-20 Daniel Berlin <dan@cgsoftware.com>
* df.c: Add prototypes for hybrid_search_bitmap and
hybrid_search_sbitmap.
(hybrid_search_bitmap): New function.
(hybrid_search_sbitmap): New function.
(iterative_dataflow_sbitmap): Change to use hybrid_search_sbitmap.
(iterative_dataflow_bitmap): Ditto.
Index: df.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/df.c,v
retrieving revision 1.18
diff -c -3 -p -w -B -b -r1.18 df.c
*** df.c 2001/11/19 17:08:47 1.18
--- df.c 2001/11/22 17:07:47
*************** static void df_ru_transfer_function PARA
*** 301,306 ****
--- 301,316 ----
bitmap, bitmap, void *));
static void df_lr_transfer_function PARAMS ((int, int *, bitmap, bitmap,
bitmap, bitmap, void *));
+ static void hybrid_search_bitmap PARAMS ((basic_block, bitmap *, bitmap *,
+ bitmap *, bitmap *, enum df_flow_dir,
+ enum df_confluence_op,
+ transfer_function_bitmap,
+ sbitmap, sbitmap, void *));
+ static void hybrid_search_sbitmap PARAMS ((basic_block, sbitmap *, sbitmap *,
+ sbitmap *, sbitmap *, enum df_flow_dir,
+ enum df_confluence_op,
+ transfer_function_sbitmap,
+ sbitmap, sbitmap, void *));
static inline bool read_modify_subreg_p PARAMS ((rtx));
*************** debug_df_chain (link)
*** 3587,3669 ****
df_chain_dump (link, stderr);
fputc ('\n', stderr);
}
-
- /* gen = GEN set.
- kill = KILL set.
- in, out = Filled in by function.
- blocks = Blocks to analyze.
- dir = Dataflow direction.
- conf_op = Confluence operation.
- transfun = Transfer function.
- order = Order to iterate in. (Should map block numbers -> order)
- data = Whatever you want. It's passed to the transfer function.
-
- This function will perform iterative bitvector dataflow, producing
- the in and out sets. Even if you only want to perform it for a
- small number of blocks, the vectors for in and out must be large
- enough for *all* blocks, because changing one block might affect
- others. However, it'll only put what you say to analyze on the
- initial worklist.
! For forward problems, you probably want to pass in a mapping of
! block number to rc_order (like df->inverse_rc_map).
! */
!
! void
! iterative_dataflow_sbitmap (in, out, gen, kill, blocks,
! dir, conf_op, transfun, order, data)
! sbitmap *in, *out, *gen, *kill;
! bitmap blocks;
enum df_flow_dir dir;
enum df_confluence_op conf_op;
! transfer_function_sbitmap transfun;
! int *order;
void *data;
{
int changed;
! int i;
! fibheap_t worklist;
! sbitmap onqueue;
! basic_block bb;
! onqueue = sbitmap_alloc (n_basic_blocks);
! sbitmap_zero (onqueue);
! worklist = fibheap_new ();
! EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
! {
! fibheap_insert (worklist, order[i], (void *) i);
! SET_BIT (onqueue, i);
! if (dir == FORWARD)
! {
! sbitmap_copy (out[i], gen[i]);
! }
! else
! {
! sbitmap_copy (in[i], gen[i]);
! }
!
! });
! while (!fibheap_empty (worklist))
! {
edge e;
! i = (int) fibheap_extract_min (worklist);
! changed = 0;
! bb = BASIC_BLOCK (i);
! RESET_BIT (onqueue, i);
if (dir == FORWARD)
{
/* Calculate <conf_op> of predecessor_outs */
! for (e = bb->pred; e != 0; e = e->pred_next)
! {
! if (e->src == ENTRY_BLOCK_PTR)
! {
! sbitmap_zero (in[i]);
! continue;
! }
! sbitmap_copy (in[i], out[e->src->index]);
! break;
! }
! if (e == 0)
! sbitmap_zero (in[i]);
for (e = bb->pred; e != 0; e = e->pred_next)
{
if (e->src == ENTRY_BLOCK_PTR)
--- 3595,3626 ----
df_chain_dump (link, stderr);
fputc ('\n', stderr);
}
! /* Hybrid search algorithm from "Implementation Techniques for
! Efficient Data-Flow Analysis of Large Programs". */
! static void hybrid_search_bitmap (block, in, out, gen, kill, dir,
! conf_op, transfun, visited, pending,
! data)
! basic_block block;
! bitmap *in, *out, *gen, *kill;
enum df_flow_dir dir;
enum df_confluence_op conf_op;
! transfer_function_bitmap transfun;
! sbitmap visited;
! sbitmap pending;
void *data;
{
int changed;
! int i = block->index;
edge e;
! basic_block bb= block;
! SET_BIT (visited, block->index);
! if (TEST_BIT (pending, block->index))
! {
if (dir == FORWARD)
{
/* Calculate <conf_op> of predecessor_outs */
! bitmap_zero (in[i]);
for (e = bb->pred; e != 0; e = e->pred_next)
{
if (e->src == ENTRY_BLOCK_PTR)
*************** iterative_dataflow_sbitmap (in, out, gen
*** 3671,3680 ****
switch (conf_op)
{
case UNION:
! sbitmap_a_or_b (in[i], in[i], out[e->src->index]);
break;
case INTERSECTION:
! sbitmap_a_and_b (in[i], in[i], out[e->src->index]);
break;
}
}
--- 3628,3637 ----
switch (conf_op)
{
case UNION:
! bitmap_a_or_b (in[i], in[i], out[e->src->index]);
break;
case INTERSECTION:
! bitmap_a_and_b (in[i], in[i], out[e->src->index]);
break;
}
}
*************** iterative_dataflow_sbitmap (in, out, gen
*** 3682,3688 ****
else
{
/* Calculate <conf_op> of successor ins */
! sbitmap_zero (out[i]);
for (e = bb->succ; e != 0; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR)
--- 3639,3645 ----
else
{
/* Calculate <conf_op> of successor ins */
! bitmap_zero(out[i]);
for (e = bb->succ; e != 0; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR)
*************** iterative_dataflow_sbitmap (in, out, gen
*** 3690,3793 ****
switch (conf_op)
{
case UNION:
! sbitmap_a_or_b (out[i], out[i], in[e->dest->index]);
break;
case INTERSECTION:
! sbitmap_a_and_b (out[i], out[i], in[e->dest->index]);
break;
}
}
}
/* Common part */
(*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
!
if (changed)
{
if (dir == FORWARD)
{
for (e = bb->succ; e != 0; e = e->succ_next)
{
! if (e->dest == EXIT_BLOCK_PTR)
continue;
! if (!TEST_BIT (onqueue, e->dest->index))
! {
! SET_BIT (onqueue, e->dest->index);
! fibheap_insert (worklist,
! order[e->dest->index],
! (void *)e->dest->index);
}
}
- }
else
{
for (e = bb->pred; e != 0; e = e->pred_next)
{
! if (e->src == ENTRY_BLOCK_PTR)
continue;
! if (!TEST_BIT (onqueue, e->src->index))
! {
! SET_BIT (onqueue, e->src->index);
! fibheap_insert (worklist,
! order[e->src->index],
! (void *)e->src->index);
! }
!
! }
}
}
}
- sbitmap_free (onqueue);
- fibheap_delete (worklist);
-
}
- /* Exactly the same as iterative_dataflow_sbitmap, except it works on
- bitmaps instead */
- void
- iterative_dataflow_bitmap (in, out, gen, kill, blocks,
- dir, conf_op, transfun, order, data)
- bitmap *in, *out, *gen, *kill;
- bitmap blocks;
- enum df_flow_dir dir;
- enum df_confluence_op conf_op;
- transfer_function_bitmap transfun;
- int *order;
- void *data;
- {
- int changed;
- int i;
- fibheap_t worklist;
- sbitmap onqueue;
- basic_block bb;
-
- onqueue = sbitmap_alloc (n_basic_blocks);
- sbitmap_zero (onqueue);
- worklist = fibheap_new ();
- EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
- {
- fibheap_insert (worklist, order[i], (void *) i);
- SET_BIT (onqueue, i);
if (dir == FORWARD)
{
! bitmap_copy (out[i], gen[i]);
}
else
{
! bitmap_copy (in[i], gen[i]);
}
! });
! while (!fibheap_empty (worklist))
{
edge e;
! i = (int) fibheap_extract_min (worklist);
! changed = 0;
! bb = BASIC_BLOCK (i);
! RESET_BIT (onqueue, i);
!
if (dir == FORWARD)
{
/* Calculate <conf_op> of predecessor_outs */
! bitmap_zero (in[i]);
for (e = bb->pred; e != 0; e = e->pred_next)
{
if (e->src == ENTRY_BLOCK_PTR)
--- 3647,3736 ----
switch (conf_op)
{
case UNION:
! bitmap_a_or_b (out[i], out[i], in[e->dest->index]);
break;
case INTERSECTION:
! bitmap_a_and_b (out[i], out[i], in[e->dest->index]);
break;
}
}
}
/* Common part */
(*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
! RESET_BIT (pending, i);
if (changed)
{
if (dir == FORWARD)
{
for (e = bb->succ; e != 0; e = e->succ_next)
{
! if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
continue;
! SET_BIT (pending, e->dest->index);
}
}
else
{
for (e = bb->pred; e != 0; e = e->pred_next)
{
! if (e->src == ENTRY_BLOCK_PTR || e->dest->index == i)
continue;
! SET_BIT (pending, e->src->index);
}
}
}
}
if (dir == FORWARD)
{
! for (e = bb->succ; e != 0; e = e->succ_next)
! {
! if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
! continue;
! if (!TEST_BIT (visited, e->dest->index))
! hybrid_search_bitmap (e->dest, in, out, gen, kill, dir,
! conf_op, transfun, visited, pending,
! data);
}
+ }
else
{
! for (e = bb->pred; e != 0; e = e->pred_next)
! {
! if (e->src == ENTRY_BLOCK_PTR || e->src->index == i)
! continue;
! if (!TEST_BIT (visited, e->src->index))
! hybrid_search_bitmap (e->src, in, out, gen, kill, dir,
! conf_op, transfun, visited, pending,
! data);
! }
}
+ }
!
! /* Hybrid search for sbitmaps, rather than bitmaps. */
! static void hybrid_search_sbitmap (block, in, out, gen, kill, dir,
! conf_op, transfun, visited, pending,
! data)
! basic_block block;
! sbitmap *in, *out, *gen, *kill;
! enum df_flow_dir dir;
! enum df_confluence_op conf_op;
! transfer_function_sbitmap transfun;
! sbitmap visited;
! sbitmap pending;
! void *data;
{
+ int changed;
+ int i = block->index;
edge e;
! basic_block bb= block;
! SET_BIT (visited, block->index);
! if (TEST_BIT (pending, block->index))
! {
if (dir == FORWARD)
{
/* Calculate <conf_op> of predecessor_outs */
! sbitmap_zero (in[i]);
for (e = bb->pred; e != 0; e = e->pred_next)
{
if (e->src == ENTRY_BLOCK_PTR)
*************** iterative_dataflow_bitmap (in, out, gen,
*** 3795,3804 ****
switch (conf_op)
{
case UNION:
! bitmap_a_or_b (in[i], in[i], out[e->src->index]);
break;
case INTERSECTION:
! bitmap_a_and_b (in[i], in[i], out[e->src->index]);
break;
}
}
--- 3738,3747 ----
switch (conf_op)
{
case UNION:
! sbitmap_a_or_b (in[i], in[i], out[e->src->index]);
break;
case INTERSECTION:
! sbitmap_a_and_b (in[i], in[i], out[e->src->index]);
break;
}
}
*************** iterative_dataflow_bitmap (in, out, gen,
*** 3806,3812 ****
else
{
/* Calculate <conf_op> of successor ins */
! bitmap_zero(out[i]);
for (e = bb->succ; e != 0; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR)
--- 3749,3755 ----
else
{
/* Calculate <conf_op> of successor ins */
! sbitmap_zero(out[i]);
for (e = bb->succ; e != 0; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR)
*************** iterative_dataflow_bitmap (in, out, gen,
*** 3814,3866 ****
switch (conf_op)
{
case UNION:
! bitmap_a_or_b (out[i], out[i], in[e->dest->index]);
break;
case INTERSECTION:
! bitmap_a_and_b (out[i], out[i], in[e->dest->index]);
break;
}
}
}
/* Common part */
(*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
!
if (changed)
{
if (dir == FORWARD)
{
for (e = bb->succ; e != 0; e = e->succ_next)
{
! if (e->dest == EXIT_BLOCK_PTR)
continue;
! if (!TEST_BIT (onqueue, e->dest->index))
{
! SET_BIT (onqueue, e->dest->index);
! fibheap_insert (worklist,
! order[e->dest->index],
! (void *)e->dest->index);
}
}
}
else
{
for (e = bb->pred; e != 0; e = e->pred_next)
{
! if (e->src == ENTRY_BLOCK_PTR)
continue;
! if (!TEST_BIT (onqueue, e->src->index))
! {
! SET_BIT (onqueue, e->src->index);
! fibheap_insert (worklist,
! order[e->src->index],
! (void *)e->src->index);
}
}
}
}
}
! sbitmap_free (onqueue);
fibheap_delete (worklist);
}
--- 3757,3958 ----
switch (conf_op)
{
case UNION:
! sbitmap_a_or_b (out[i], out[i], in[e->dest->index]);
break;
case INTERSECTION:
! sbitmap_a_and_b (out[i], out[i], in[e->dest->index]);
break;
}
}
}
/* Common part */
(*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
! RESET_BIT (pending, i);
if (changed)
{
if (dir == FORWARD)
{
for (e = bb->succ; e != 0; e = e->succ_next)
{
! if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
continue;
! SET_BIT (pending, e->dest->index);
! }
! }
! else
! {
! for (e = bb->pred; e != 0; e = e->pred_next)
{
! if (e->src == ENTRY_BLOCK_PTR || e->dest->index == i)
! continue;
! SET_BIT (pending, e->src->index);
! }
! }
}
}
+ if (dir == FORWARD)
+ {
+ for (e = bb->succ; e != 0; e = e->succ_next)
+ {
+ if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
+ continue;
+ if (!TEST_BIT (visited, e->dest->index))
+ hybrid_search_sbitmap (e->dest, in, out, gen, kill, dir,
+ conf_op, transfun, visited, pending,
+ data);
+ }
}
else
{
for (e = bb->pred; e != 0; e = e->pred_next)
{
! if (e->src == ENTRY_BLOCK_PTR || e->src->index == i)
continue;
! if (!TEST_BIT (visited, e->src->index))
! hybrid_search_sbitmap (e->src, in, out, gen, kill, dir,
! conf_op, transfun, visited, pending,
! data);
! }
! }
}
+
+
+
+ /* gen = GEN set.
+ kill = KILL set.
+ in, out = Filled in by function.
+ blocks = Blocks to analyze.
+ dir = Dataflow direction.
+ conf_op = Confluence operation.
+ transfun = Transfer function.
+ order = Order to iterate in. (Should map block numbers -> order)
+ data = Whatever you want. It's passed to the transfer function.
+
+ This function will perform iterative bitvector dataflow, producing
+ the in and out sets. Even if you only want to perform it for a
+ small number of blocks, the vectors for in and out must be large
+ enough for *all* blocks, because changing one block might affect
+ others. However, it'll only put what you say to analyze on the
+ initial worklist.
+
+ For forward problems, you probably want to pass in a mapping of
+ block number to rc_order (like df->inverse_rc_map).
+ */
+ void
+ iterative_dataflow_sbitmap (in, out, gen, kill, blocks,
+ dir, conf_op, transfun, order, data)
+ sbitmap *in, *out, *gen, *kill;
+ bitmap blocks;
+ enum df_flow_dir dir;
+ enum df_confluence_op conf_op;
+ transfer_function_sbitmap transfun;
+ int *order;
+ void *data;
+ {
+ int i;
+ fibheap_t worklist;
+ basic_block bb;
+ sbitmap visited, pending;
+ pending = sbitmap_alloc (n_basic_blocks);
+ visited = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (pending);
+ sbitmap_zero (visited);
+ worklist = fibheap_new ();
+ EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
+ {
+ fibheap_insert (worklist, order[i], (void *) i);
+ SET_BIT (pending, i);
+ if (dir == FORWARD)
+ sbitmap_copy (out[i], gen[i]);
+ else
+ sbitmap_copy (in[i], gen[i]);
+ });
+ while (sbitmap_first_set_bit (pending) != -1)
+ {
+ while (!fibheap_empty (worklist))
+ {
+ i = (int) fibheap_extract_min (worklist);
+ bb = BASIC_BLOCK (i);
+ if (!TEST_BIT (visited, bb->index))
+ hybrid_search_sbitmap (bb, in, out, gen, kill, dir,
+ conf_op, transfun, visited, pending,
+ data);
}
+ if (sbitmap_first_set_bit (pending) != -1)
+ {
+ EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
+ {
+ fibheap_insert (worklist, order[i], (void *) i);
+ });
+ sbitmap_zero (visited);
}
+ else
+ {
+ break;
}
}
! sbitmap_free (pending);
! sbitmap_free (visited);
fibheap_delete (worklist);
+ }
+ /* Exactly the same as iterative_dataflow_sbitmap, except it works on
+ bitmaps instead */
+ void
+ iterative_dataflow_bitmap (in, out, gen, kill, blocks,
+ dir, conf_op, transfun, order, data)
+ bitmap *in, *out, *gen, *kill;
+ bitmap blocks;
+ enum df_flow_dir dir;
+ enum df_confluence_op conf_op;
+ transfer_function_bitmap transfun;
+ int *order;
+ void *data;
+ {
+ int i;
+ fibheap_t worklist;
+ basic_block bb;
+ sbitmap visited, pending;
+ pending = sbitmap_alloc (n_basic_blocks);
+ visited = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (pending);
+ sbitmap_zero (visited);
+ worklist = fibheap_new ();
+ EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
+ {
+ fibheap_insert (worklist, order[i], (void *) i);
+ SET_BIT (pending, i);
+ if (dir == FORWARD)
+ bitmap_copy (out[i], gen[i]);
+ else
+ bitmap_copy (in[i], gen[i]);
+ });
+ while (sbitmap_first_set_bit (pending) != -1)
+ {
+ while (!fibheap_empty (worklist))
+ {
+ i = (int) fibheap_extract_min (worklist);
+ bb = BASIC_BLOCK (i);
+ if (!TEST_BIT (visited, bb->index))
+ hybrid_search_bitmap (bb, in, out, gen, kill, dir,
+ conf_op, transfun, visited, pending,
+ data);
+ }
+ if (sbitmap_first_set_bit (pending) != -1)
+ {
+ EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
+ {
+ fibheap_insert (worklist, order[i], (void *) i);
+ });
+ sbitmap_zero (visited);
+ }
+ else
+ {
+ break;
+ }
+ }
+ sbitmap_free (pending);
+ sbitmap_free (visited);
+ fibheap_delete (worklist);
}