From 1a0f3fa13745c4052c53e6d84c64539fb5f57e00 Mon Sep 17 00:00:00 2001 From: Jan Hubicka Date: Tue, 22 Jun 2010 17:51:15 +0200 Subject: df-problems.c (df_rd_confluence_n, [...]): Return true if something changed. * df-problems.c (df_rd_confluence_n, df_lr_confluence_n, df_live_confluence_n, df_byte_lr_confluence_n, df_md_confluence_n): Return true if something changed. * df.h (df_confluence_function_n): Return bool. * df-core.c (df_worklist_propagate_forward, df_worklist_propagate_backward): track changes and ages. (df_worklist_dataflow_doublequeue): Use bitmap iterator for main walk; track ages. * dse.c (dse_confluence_n): Return always true. From-SVN: r161197 --- gcc/df-core.c | 96 +++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 67 insertions(+), 29 deletions(-) (limited to 'gcc/df-core.c') diff --git a/gcc/df-core.c b/gcc/df-core.c index 5ffee9c..814eaf4 100644 --- a/gcc/df-core.c +++ b/gcc/df-core.c @@ -858,28 +858,35 @@ struct rtl_opt_pass pass_df_finish = and set bits on for successors in PENDING if the out set of the dataflow has changed. */ -static void +static bool df_worklist_propagate_forward (struct dataflow *dataflow, unsigned bb_index, unsigned *bbindex_to_postorder, bitmap pending, - sbitmap considered) + sbitmap considered, + size_t age) { edge e; edge_iterator ei; basic_block bb = BASIC_BLOCK (bb_index); + bool changed = !age; /* Calculate of incoming edges. */ if (EDGE_COUNT (bb->preds) > 0) FOR_EACH_EDGE (e, ei, bb->preds) { - if (TEST_BIT (considered, e->src->index)) - dataflow->problem->con_fun_n (e); + if ((age <= (size_t)e->src->aux) + && TEST_BIT (considered, e->src->index)) + changed |= dataflow->problem->con_fun_n (e); } else if (dataflow->problem->con_fun_0) - dataflow->problem->con_fun_0 (bb); + { + dataflow->problem->con_fun_0 (bb); + changed = true; + } - if (dataflow->problem->trans_fun (bb_index)) + if (changed + && dataflow->problem->trans_fun (bb_index)) { /* The out set of this block has changed. Propagate to the outgoing blocks. */ @@ -890,35 +897,44 @@ df_worklist_propagate_forward (struct dataflow *dataflow, if (TEST_BIT (considered, ob_index)) bitmap_set_bit (pending, bbindex_to_postorder[ob_index]); } + return true; } + return false; } /* Helper function for df_worklist_dataflow. Propagate the dataflow backward. */ -static void +static bool df_worklist_propagate_backward (struct dataflow *dataflow, unsigned bb_index, unsigned *bbindex_to_postorder, bitmap pending, - sbitmap considered) + sbitmap considered, + size_t age) { edge e; edge_iterator ei; basic_block bb = BASIC_BLOCK (bb_index); + bool changed = !age; /* Calculate of incoming edges. */ if (EDGE_COUNT (bb->succs) > 0) FOR_EACH_EDGE (e, ei, bb->succs) { - if (TEST_BIT (considered, e->dest->index)) - dataflow->problem->con_fun_n (e); + if ((age <= (size_t)e->dest->aux) + && TEST_BIT (considered, e->dest->index)) + changed |= dataflow->problem->con_fun_n (e); } else if (dataflow->problem->con_fun_0) - dataflow->problem->con_fun_0 (bb); + { + dataflow->problem->con_fun_0 (bb); + changed = true; + } - if (dataflow->problem->trans_fun (bb_index)) + if (changed + && dataflow->problem->trans_fun (bb_index)) { /* The out set of this block has changed. Propagate to the outgoing blocks. */ @@ -929,10 +945,13 @@ df_worklist_propagate_backward (struct dataflow *dataflow, if (TEST_BIT (considered, ob_index)) bitmap_set_bit (pending, bbindex_to_postorder[ob_index]); } + return true; } + return false; } - +DEF_VEC_I(size_t); +DEF_VEC_ALLOC_I(size_t,heap); /* This will free "pending". */ @@ -941,46 +960,65 @@ df_worklist_dataflow_doublequeue (struct dataflow *dataflow, bitmap pending, sbitmap considered, int *blocks_in_postorder, - unsigned *bbindex_to_postorder) + unsigned *bbindex_to_postorder, + int n_blocks) { enum df_flow_dir dir = dataflow->problem->dir; int dcount = 0; bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack); + size_t age = 0; + bool changed; + VEC(size_t, heap) *last_age = NULL; + size_t prev_age; + basic_block bb; + int i; + + VEC_safe_grow_cleared (size_t, heap, last_age, n_blocks); /* Double-queueing. Worklist is for the current iteration, and pending is for the next. */ while (!bitmap_empty_p (pending)) { + bitmap_iterator bi; + unsigned int index; + /* Swap pending and worklist. */ bitmap temp = worklist; worklist = pending; pending = temp; - do + EXECUTE_IF_SET_IN_BITMAP (worklist, 0, index, bi) { - int index; unsigned bb_index; dcount++; - index = bitmap_first_set_bit (worklist); - bitmap_clear_bit (worklist, index); - bb_index = blocks_in_postorder[index]; - + bb = BASIC_BLOCK (bb_index); + prev_age = VEC_index (size_t, last_age, index); if (dir == DF_FORWARD) - df_worklist_propagate_forward (dataflow, bb_index, - bbindex_to_postorder, - pending, considered); + changed = df_worklist_propagate_forward (dataflow, bb_index, + bbindex_to_postorder, + pending, considered, + prev_age); else - df_worklist_propagate_backward (dataflow, bb_index, - bbindex_to_postorder, - pending, considered); + changed = df_worklist_propagate_backward (dataflow, bb_index, + bbindex_to_postorder, + pending, considered, + prev_age); + age++; + if (changed) + bb->aux = (void *)age; + VEC_replace (size_t, last_age, index, age); + age++; } - while (!bitmap_empty_p (worklist)); + bitmap_clear (worklist); } + for (i = 0; i < n_blocks; i++) + BASIC_BLOCK (blocks_in_postorder[i])->aux = NULL; BITMAP_FREE (worklist); BITMAP_FREE (pending); + VEC_free (size_t, heap, last_age); /* Dump statistics. */ if (dump_file) @@ -1044,8 +1082,8 @@ df_worklist_dataflow (struct dataflow *dataflow, /* Solve it. */ df_worklist_dataflow_doublequeue (dataflow, pending, considered, blocks_in_postorder, - bbindex_to_postorder); - + bbindex_to_postorder, + n_blocks); sbitmap_free (considered); free (bbindex_to_postorder); } -- cgit v1.1