===================================================================
@@ -851,8 +851,26 @@ struct rtl_opt_pass pass_df_finish =
The general data flow analysis engine.
----------------------------------------------------------------------------*/
+/* We use bb->aux to store information about age and worklist. We always inspect BB structure
+ when accessing those, so this leads to good memory locality.
+
+ First bit of bb->aux is used to indicate whther BB is in worklist. BBs are all having
+ aux 0 and they are initially in worklist, so value of 0 indicate that BB is in worklist
+ and value of 1 indicate that BB is not. This is because we want to pretend BBs not
+ considered to be in worklist (to avoid inserting them) and this way we save need
+ to initialize their AUX fields.
+
+ Other bits of AUX are used to represent age. */
+
/* Return time BB when it was visited for last time. */
-#define BB_LAST_CHANGE_AGE(bb) ((ptrdiff_t)(bb)->aux)
+#define BB_LAST_CHANGE_AGE(bb) (((ptrdiff_t)(bb)->aux) >> 1)
+/* Set BB's visit time. */
+#define SET_BB_LAST_CHANGE_AGE(bb, age) (bb)->aux = (void *)(ptrdiff_t)((age) << 1 | ((ptrdiff_t)bb->aux & 1))
+/* Return true when BB scheduled for processing, either in worklist or pending. */
+#define BB_IN_WORKLIST(bb) (!((ptrdiff_t)(bb)->aux & 1))
+/* Set and clear BB in worklist flag. */
+#define SET_BB_IN_WORKLIST(bb) ((bb)->aux = (void *)((ptrdiff_t)(bb)->aux & ~1))
+#define CLEAR_BB_IN_WORKLIST(bb) ((bb)->aux = (void *)((ptrdiff_t)(bb)->aux | 1))
/* Helper function for df_worklist_dataflow.
Propagate the dataflow forward.
@@ -876,21 +894,19 @@ df_worklist_propagate_forward (struct da
unsigned bb_index,
unsigned *bbindex_to_postorder,
bitmap pending,
- sbitmap considered,
ptrdiff_t age)
{
edge e;
edge_iterator ei;
basic_block bb = BASIC_BLOCK (bb_index);
- bool changed = !age;
+ bool changed = age == 1;
/* Calculate <conf_op> of incoming edges. */
if (EDGE_COUNT (bb->preds) > 0)
FOR_EACH_EDGE (e, ei, bb->preds)
{
- if (age <= BB_LAST_CHANGE_AGE (e->src)
- && TEST_BIT (considered, e->src->index))
- changed |= dataflow->problem->con_fun_n (e);
+ if (age <= BB_LAST_CHANGE_AGE (e->src))
+ changed |= dataflow->problem->con_fun_n (e);
}
else if (dataflow->problem->con_fun_0)
dataflow->problem->con_fun_0 (bb);
@@ -901,12 +917,13 @@ df_worklist_propagate_forward (struct da
/* The out set of this block has changed.
Propagate to the outgoing blocks. */
FOR_EACH_EDGE (e, ei, bb->succs)
- {
- unsigned ob_index = e->dest->index;
-
- if (TEST_BIT (considered, ob_index))
- bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
- }
+ if (!BB_IN_WORKLIST (e->dest))
+ {
+ unsigned ob_index = e->dest->index;
+
+ SET_BB_IN_WORKLIST (e->dest);
+ bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
+ }
return true;
}
return false;
@@ -921,20 +938,18 @@ df_worklist_propagate_backward (struct d
unsigned bb_index,
unsigned *bbindex_to_postorder,
bitmap pending,
- sbitmap considered,
ptrdiff_t age)
{
edge e;
edge_iterator ei;
basic_block bb = BASIC_BLOCK (bb_index);
- bool changed = !age;
+ bool changed = age == 1;
/* Calculate <conf_op> of incoming edges. */
if (EDGE_COUNT (bb->succs) > 0)
FOR_EACH_EDGE (e, ei, bb->succs)
{
- if (age <= BB_LAST_CHANGE_AGE (e->dest)
- && TEST_BIT (considered, e->dest->index))
+ if (age <= BB_LAST_CHANGE_AGE (e->dest))
changed |= dataflow->problem->con_fun_n (e);
}
else if (dataflow->problem->con_fun_0)
@@ -946,12 +961,13 @@ df_worklist_propagate_backward (struct d
/* The out set of this block has changed.
Propagate to the outgoing blocks. */
FOR_EACH_EDGE (e, ei, bb->preds)
- {
- unsigned ob_index = e->src->index;
-
- if (TEST_BIT (considered, ob_index))
- bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
- }
+ if (!BB_IN_WORKLIST (e->src))
+ {
+ unsigned ob_index = e->src->index;
+
+ SET_BB_IN_WORKLIST (e->src);
+ bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
+ }
return true;
}
return false;
@@ -979,7 +995,6 @@ df_worklist_propagate_backward (struct d
static void
df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
bitmap pending,
- sbitmap considered,
int *blocks_in_postorder,
unsigned *bbindex_to_postorder,
int n_blocks)
@@ -987,12 +1002,11 @@ df_worklist_dataflow_doublequeue (struct
enum df_flow_dir dir = dataflow->problem->dir;
int dcount = 0;
bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
- int age = 0;
+ int age = 1;
bool changed;
VEC(int, heap) *last_visit_age = NULL;
int prev_age;
basic_block bb;
- int i;
VEC_safe_grow_cleared (int, heap, last_visit_age, n_blocks);
@@ -1013,28 +1027,26 @@ df_worklist_dataflow_doublequeue (struct
unsigned bb_index;
dcount++;
- bitmap_clear_bit (pending, index);
bb_index = blocks_in_postorder[index];
bb = BASIC_BLOCK (bb_index);
- prev_age = VEC_index (int, last_visit_age, index);
+ prev_age = VEC_index (int, last_visit_age, index) + 1;
+ CLEAR_BB_IN_WORKLIST (bb);
if (dir == DF_FORWARD)
changed = df_worklist_propagate_forward (dataflow, bb_index,
bbindex_to_postorder,
- pending, considered,
+ pending,
prev_age);
else
changed = df_worklist_propagate_backward (dataflow, bb_index,
bbindex_to_postorder,
- pending, considered,
+ pending,
prev_age);
- VEC_replace (int, last_visit_age, index, ++age);
+ VEC_replace (int, last_visit_age, index, age++);
if (changed)
- bb->aux = (void *)(ptrdiff_t)age;
+ SET_BB_LAST_CHANGE_AGE (bb, age);
}
bitmap_clear (worklist);
}
- for (i = 0; i < n_blocks; i++)
- BASIC_BLOCK (blocks_in_postorder[i])->aux = NULL;
BITMAP_FREE (worklist);
BITMAP_FREE (pending);
@@ -1063,11 +1075,8 @@ df_worklist_dataflow (struct dataflow *d
int n_blocks)
{
bitmap pending = BITMAP_ALLOC (&df_bitmap_obstack);
- sbitmap considered = sbitmap_alloc (last_basic_block);
- bitmap_iterator bi;
unsigned int *bbindex_to_postorder;
int i;
- unsigned int index;
enum df_flow_dir dir = dataflow->problem->dir;
gcc_assert (dir != DF_NONE);
@@ -1076,21 +1085,20 @@ df_worklist_dataflow (struct dataflow *d
bbindex_to_postorder =
(unsigned int *)xmalloc (last_basic_block * sizeof (unsigned int));
+#ifdef ENABLE_CHECKING
/* Initialize the array to an out-of-bound value. */
for (i = 0; i < last_basic_block; i++)
bbindex_to_postorder[i] = last_basic_block;
-
- /* Initialize the considered map. */
- sbitmap_zero (considered);
- EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, index, bi)
- {
- SET_BIT (considered, index);
- }
+#endif
/* Initialize the mapping of block index to postorder. */
for (i = 0; i < n_blocks; i++)
{
bbindex_to_postorder[blocks_in_postorder[i]] = i;
+ /* Start with Age of 1. Blocks not considered for dataflow
+ will all have age of 0 that will prevent us from computing
+ confluence on them. */
+ SET_BB_LAST_CHANGE_AGE (BASIC_BLOCK (blocks_in_postorder[i]), 1);
/* Add all blocks to the worklist. */
bitmap_set_bit (pending, i);
}
@@ -1100,11 +1108,14 @@ df_worklist_dataflow (struct dataflow *d
dataflow->problem->init_fun (blocks_to_consider);
/* Solve it. */
- df_worklist_dataflow_doublequeue (dataflow, pending, considered,
+ df_worklist_dataflow_doublequeue (dataflow, pending,
blocks_in_postorder,
bbindex_to_postorder,
n_blocks);
- sbitmap_free (considered);
+
+ for (i = 0; i < n_blocks; i++)
+ BASIC_BLOCK (blocks_in_postorder[i])->aux = NULL;
+
free (bbindex_to_postorder);
}