+\f
+
+/* Perform the set operation OP1 OP OP2, using set representation REPR, and
+ storing the result in OP1. */
+
+static void
+dataflow_set_a_op_b (enum set_representation repr,
+ enum df_confluence_op op,
+ void *op1, void *op2)
+{
+ switch (repr)
+ {
+ case SR_SBITMAP:
+ switch (op)
+ {
+ case DF_UNION:
+ sbitmap_a_or_b (op1, op1, op2);
+ break;
+
+ case DF_INTERSECTION:
+ sbitmap_a_and_b (op1, op1, op2);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ break;
+
+ case SR_BITMAP:
+ switch (op)
+ {
+ case DF_UNION:
+ bitmap_ior_into (op1, op2);
+ break;
+
+ case DF_INTERSECTION:
+ bitmap_and_into (op1, op2);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+}
+
+static void
+dataflow_set_copy (enum set_representation repr, void *dest, void *src)
+{
+ switch (repr)
+ {
+ case SR_SBITMAP:
+ sbitmap_copy (dest, src);
+ break;
+
+ case SR_BITMAP:
+ bitmap_copy (dest, src);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+}
+
+/* Hybrid search algorithm from "Implementation Techniques for
+ Efficient Data-Flow Analysis of Large Programs". */
+
+static void
+hybrid_search (basic_block bb, struct dataflow *dataflow,
+ sbitmap visited, sbitmap pending, sbitmap considered)
+{
+ int changed;
+ int i = bb->index;
+ edge e;
+ edge_iterator ei;
+
+ SET_BIT (visited, bb->index);
+ gcc_assert (TEST_BIT (pending, bb->index));
+ RESET_BIT (pending, i);
+
+#define HS(E_ANTI, E_ANTI_BB, E_ANTI_START_BB, IN_SET, \
+ E, E_BB, E_START_BB, OUT_SET) \
+ do \
+ { \
+ /* Calculate <conf_op> of predecessor_outs. */ \
+ bitmap_zero (IN_SET[i]); \
+ FOR_EACH_EDGE (e, ei, bb->E_ANTI) \
+ { \
+ if (e->E_ANTI_BB == E_ANTI_START_BB) \
+ continue; \
+ if (!TEST_BIT (considered, e->E_ANTI_BB->index)) \
+ continue; \
+ \
+ dataflow_set_a_op_b (dataflow->repr, dataflow->conf_op, \
+ IN_SET[i], \
+ OUT_SET[e->E_ANTI_BB->index]); \
+ } \
+ \
+ (*dataflow->transfun)(i, &changed, \
+ dataflow->in[i], dataflow->out[i], \
+ dataflow->gen[i], dataflow->kill[i], \
+ dataflow->data); \
+ \
+ if (!changed) \
+ break; \
+ \
+ FOR_EACH_EDGE (e, ei, bb->E) \
+ { \
+ if (e->E_BB == E_START_BB || e->E_BB->index == i) \
+ continue; \
+ \
+ if (!TEST_BIT (considered, e->E_BB->index)) \
+ continue; \
+ \
+ SET_BIT (pending, e->E_BB->index); \
+ } \
+ \
+ FOR_EACH_EDGE (e, ei, bb->E) \
+ { \
+ if (e->E_BB == E_START_BB || e->E_BB->index == i) \
+ continue; \
+ \
+ if (!TEST_BIT (considered, e->E_BB->index)) \
+ continue; \
+ \
+ if (!TEST_BIT (visited, e->E_BB->index)) \
+ hybrid_search (e->E_BB, dataflow, visited, pending, considered); \
+ } \
+ } while (0)
+
+ if (dataflow->dir == DF_FORWARD)
+ HS (preds, src, ENTRY_BLOCK_PTR, dataflow->in,
+ succs, dest, EXIT_BLOCK_PTR, dataflow->out);
+ else
+ HS (succs, dest, EXIT_BLOCK_PTR, dataflow->out,
+ preds, src, ENTRY_BLOCK_PTR, dataflow->in);
+}
+
+/* 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.
+
+ 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 (struct dataflow *dataflow)
+{
+ unsigned i, idx;
+ sbitmap visited, pending, considered;
+
+ pending = sbitmap_alloc (last_basic_block);
+ visited = sbitmap_alloc (last_basic_block);
+ considered = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (pending);
+ sbitmap_zero (visited);
+ sbitmap_zero (considered);
+
+ for (i = 0; i < dataflow->n_blocks; i++)
+ {
+ idx = dataflow->order[i];
+ SET_BIT (pending, idx);
+ SET_BIT (considered, idx);
+ if (dataflow->dir == DF_FORWARD)
+ dataflow_set_copy (dataflow->repr,
+ dataflow->out[idx], dataflow->gen[idx]);
+ else
+ dataflow_set_copy (dataflow->repr,
+ dataflow->in[idx], dataflow->gen[idx]);
+ };
+
+ while (1)
+ {
+ for (i = 0; i < dataflow->n_blocks; i++)
+ {
+ idx = dataflow->order[i];
+
+ if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
+ hybrid_search (BASIC_BLOCK (idx), dataflow,
+ visited, pending, considered);
+ }
+
+ if (sbitmap_first_set_bit (pending) == -1)
+ break;
+
+ sbitmap_zero (visited);
+ }
+
+ sbitmap_free (pending);
+ sbitmap_free (visited);
+ sbitmap_free (considered);
+}