diff options
| -rw-r--r-- | gcc/ChangeLog | 13 | ||||
| -rw-r--r-- | gcc/df-core.c | 96 | ||||
| -rw-r--r-- | gcc/df-problems.c | 42 | ||||
| -rw-r--r-- | gcc/df.h | 2 | ||||
| -rw-r--r-- | gcc/dse.c | 3 |
5 files changed, 105 insertions, 51 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b3aae11cf09..fdd72da1c60 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,4 +1,15 @@ -2010-06-22 Uros Bizjak <ubizjak@gmail.com> +2010-06-22 Jan Hubicka <jh@suse.cz> + + * 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. + +2010-06-22 Jan Hubicka <jh@suse.cz> * bitmap.c (bitmap_clear_bit): Micro optimize. diff --git a/gcc/df-core.c b/gcc/df-core.c index 5ffee9c8b99..814eaf41ccf 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 <conf_op> 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 <conf_op> 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); } diff --git a/gcc/df-problems.c b/gcc/df-problems.c index f9d5f6bd848..431027a41e0 100644 --- a/gcc/df-problems.c +++ b/gcc/df-problems.c @@ -479,14 +479,15 @@ df_rd_init_solution (bitmap all_blocks) /* In of target gets or of out of source. */ -static void +static bool df_rd_confluence_n (edge e) { bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in; bitmap op2 = &df_rd_get_bb_info (e->src->index)->out; + bool changed = false; if (e->flags & EDGE_FAKE) - return; + return false; if (e->flags & EDGE_EH) { @@ -508,11 +509,12 @@ df_rd_confluence_n (edge e) DF_DEFS_BEGIN (regno), DF_DEFS_COUNT (regno)); } - bitmap_ior_into (op1, &tmp); + changed |= bitmap_ior_into (op1, &tmp); bitmap_clear (&tmp); + return changed; } else - bitmap_ior_into (op1, op2); + return bitmap_ior_into (op1, op2); } @@ -966,21 +968,22 @@ df_lr_confluence_0 (basic_block bb) /* Confluence function that ignores fake edges. */ -static void +static bool df_lr_confluence_n (edge e) { bitmap op1 = &df_lr_get_bb_info (e->src->index)->out; bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in; + bool changed = false; /* Call-clobbered registers die across exception and call edges. */ /* ??? Abnormal call edges ignored for the moment, as this gets confused by sibling call edges, which crashes reg-stack. */ if (e->flags & EDGE_EH) - bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset); + changed = bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset); else - bitmap_ior_into (op1, op2); + changed = bitmap_ior_into (op1, op2); - bitmap_ior_into (op1, &df->hardware_regs_used); + return bitmap_ior_into (op1, &df->hardware_regs_used) || changed; } @@ -1503,16 +1506,16 @@ df_live_init (bitmap all_blocks) /* Forward confluence function that ignores fake edges. */ -static void +static bool df_live_confluence_n (edge e) { bitmap op1 = &df_live_get_bb_info (e->dest->index)->in; bitmap op2 = &df_live_get_bb_info (e->src->index)->out; if (e->flags & EDGE_FAKE) - return; + return false; - bitmap_ior_into (op1, op2); + return bitmap_ior_into (op1, op2); } @@ -2710,23 +2713,24 @@ df_byte_lr_confluence_0 (basic_block bb) /* Confluence function that ignores fake edges. */ -static void +static bool df_byte_lr_confluence_n (edge e) { struct df_byte_lr_problem_data *problem_data = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data; bitmap op1 = &df_byte_lr_get_bb_info (e->src->index)->out; bitmap op2 = &df_byte_lr_get_bb_info (e->dest->index)->in; + bool changed = false; /* Call-clobbered registers die across exception and call edges. */ /* ??? Abnormal call edges ignored for the moment, as this gets confused by sibling call edges, which crashes reg-stack. */ if (e->flags & EDGE_EH) - bitmap_ior_and_compl_into (op1, op2, &problem_data->invalidated_by_call); + changed = bitmap_ior_and_compl_into (op1, op2, &problem_data->invalidated_by_call); else - bitmap_ior_into (op1, op2); + changed = bitmap_ior_into (op1, op2); - bitmap_ior_into (op1, &problem_data->hardware_regs_used); + return bitmap_ior_into (op1, &problem_data->hardware_regs_used) || changed; } @@ -4426,19 +4430,19 @@ df_md_confluence_0 (basic_block bb) /* In of target gets or of out of source. */ -static void +static bool df_md_confluence_n (edge e) { bitmap op1 = &df_md_get_bb_info (e->dest->index)->in; bitmap op2 = &df_md_get_bb_info (e->src->index)->out; if (e->flags & EDGE_FAKE) - return; + return false; if (e->flags & EDGE_EH) - bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset); + return bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset); else - bitmap_ior_into (op1, op2); + return bitmap_ior_into (op1, op2); } /* Free all storage associated with the problem. */ @@ -223,7 +223,7 @@ typedef void (*df_dataflow_function) (struct dataflow *, bitmap, int *, int); typedef void (*df_confluence_function_0) (basic_block); /* Confluence operator for blocks with 1 or more out (or in) edges. */ -typedef void (*df_confluence_function_n) (edge); +typedef bool (*df_confluence_function_n) (edge); /* Transfer function for blocks. */ typedef bool (*df_transfer_function) (int); diff --git a/gcc/dse.c b/gcc/dse.c index 2be8a942c75..5cb467c934d 100644 --- a/gcc/dse.c +++ b/gcc/dse.c @@ -3396,7 +3396,7 @@ dse_confluence_0 (basic_block bb) out set of the src of E. If the various in or out sets are not there, that means they are all ones. */ -static void +static bool dse_confluence_n (edge e) { bb_info_t src_info = bb_table[e->src->index]; @@ -3412,6 +3412,7 @@ dse_confluence_n (edge e) bitmap_copy (src_info->out, dest_info->in); } } + return true; } |