+
+/* 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)
+ continue;
+ 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;
+ }
+ }
+ }
+ 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)
+ continue;
+ 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)
+ continue;
+ 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;
+ }
+ }
+ }
+ 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)
+ continue;
+ 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);
+
+}