Iterative dataflow function

[Daniel Berlin <dan at cgsoftware dot com>]

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. 
*/
enum df_confluence_op
  {
    UNION, 
    INTERSECTION 
  };
enum df_flow_dir
  {
    FORWARD, 
    BACKWARD
  };
 
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:

static void
df_rd_trans_fun (bbnum, changed, in, out, gen, kill, data)
     int bbnum;
     int *changed;
     sbitmap in, out, gen, kill;
     void *data;
{
  *changed = sbitmap_union_of_diff (out, gen, in, kill);
}

void df_rd_global_compute_new (df)
   struct df *df;
{

   sbitmap *in, *out, *gen, *kill;
  sbitmap blocks;
  int i;
  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_ones (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, 
  {
    int j;
    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, 
			      df_rd_trans_fun, 0);
  sbitmap_vector_free (gen);
  sbitmap_vector_free (kill);
  sbitmap_vector_free (in);
  sbitmap_vector_free (out);  
}


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
now, O(n)).

--Dan

-- 
"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.
"-Steven Wright