This is the mail archive of the
mailing list for the GCC project.
Iterative dataflow function
- To: gcc at gcc dot gnu dot org
- Subject: Iterative dataflow function
- From: Daniel Berlin <dan at cgsoftware dot com>
- Date: Wed, 01 Aug 2001 12:43:03 -0400
So i got tired of seeing 8 million different implementations of
worklist algorithms, and made a function that performs iterative
bitvector dataflow for us.
The prototypes look like this:
/* UNION = meet over any path.
INTERSECTION = meet over all paths.
typedef void (*transfer_function_sbitmap) (int, int *, sbitmap, sbitmap,
sbitmap, sbitmap, void *);
typedef void (*transfer_function_bitmap) (int, int *, bitmap, bitmap,
bitmap, bitmap, void *);
extern void iterative_dataflow_sbitmap PARAMS ((sbitmap
*, sbitmap *, sbitmap *, sbitmap *, sbitmap, enum df_flow_dir, enum
df_confluence_op, transfer_function_sbitmap, void *));
extern void iterative_dataflow_bitmap PARAMS ((bitmap *, bitmap *,
bitmap *, bitmap *, sbitmap, enum df_flow_dir, enum df_confluence_op,
transfer_function_bitmap, void *));
And for something like reaching defs, you'd do:
df_rd_trans_fun (bbnum, changed, in, out, gen, kill, data)
sbitmap in, out, gen, kill;
*changed = sbitmap_union_of_diff (out, gen, in, kill);
void df_rd_global_compute_new (df)
struct df *df;
sbitmap *in, *out, *gen, *kill;
in = sbitmap_vector_alloc (n_basic_blocks, df->n_defs);
out = sbitmap_vector_alloc (n_basic_blocks, df->n_defs);
gen = sbitmap_vector_alloc (n_basic_blocks, df->n_defs);
kill = sbitmap_vector_alloc (n_basic_blocks, df->n_defs);
blocks = sbitmap_alloc (n_basic_blocks);
sbitmap_vector_zero (in, n_basic_blocks);
sbitmap_vector_zero (out, n_basic_blocks);
sbitmap_vector_zero (gen, n_basic_blocks);
sbitmap_vector_zero (kill, n_basic_blocks);
/* We already have gen and kill from the df analyzer's computation,
so just copy them here, since this is an example */
EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
EXECUTE_IF_SET_IN_BITMAP (DF_BB_INFO (df, BASIC_BLOCK (i))->rd_gen, 0, j,
SET_BIT (gen[i], j);
EXECUTE_IF_SET_IN_BITMAP (DF_BB_INFO (df, BASIC_BLOCK (i))->rd_kill, 0, j,
SET_BIT (kill[i], j);
iterative_dataflow_sbitmap (df, in, out, gen, kill, blocks, FORWARD, UNION,
Is something like this useful enough? It seriously cuts down on the
amount of code in most of our dataflow algorithms (LCM, etc).
I originally did this because just in df.c alone, there are 4
implementations of the
same iterative worklist algorithm. In other files, we have slightly
different worklist types (lcm uses a queue), etc.
If it is useful, are their improvements people would like to see
before I submit it for approval?
I've already got it doing iteration in reverse completion order, using a
fibheap based priority queue as the worklist (df_visit_next is, right
"Last time I went to the movies I was thrown out for bringing my
own food. My argument was that the concession stand prices are
outrageous. Besides, I haven't had a Bar-B-Que in a long time.