Index: df-core.c =================================================================== --- df-core.c (revision 161199) +++ df-core.c (working copy) @@ -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 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 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); }