This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [dataflow]: PATCH: worklist based dataflow solver


Commited after Kenny's approval.

Seongbae

On 1/9/07, Seongbae Park <seongbae.park@gmail.com> wrote:
This patch cuts the time spent in dataflow solver in half, when
compiling top 5 largest files for building cc1. For one analysis
(reaching store problem used during dse),
traversing in the order of the reverse postorder of inverted CFG
for the forward problems reduces the block visit count by 90%.
The worklist based algorithm reduces it by couple % further.

Bootstrapped and regression tested on x86-64. OK?


2007-01-09 Seongbae Park <seongbae.park@gmail.com> * df-core.c (rest_of_handle_df_initialize): Allocate and free new fields struct dataflow::{postorder_inverted,n_blocks_inverted}. (df_hybrid_search_forward, df_hybrid_search_backward): Pass visited, pending, considered as parameters instead of fields of struct df. (df_worklist_propagate_forward, df_worklist_propagate_backward, df_worklist_dataflow): New functions. (df_iterative_dataflow): Remove visited, pending, considered fields from struct dataflow. (df_analyze): Allocate and free new fields df::{postorder_inverted,n_blocks_inverted}. (df_get_n_blocks, df_get_postorder): Make them return different values depending on the direction of the dataflow problem. (df_simple_dataflow): Renamed from df_simple_iterative_dataflow. Call df_worklist_dataflow instead of df_iterative_dataflow. * cfganal.c (dfs_find_deadend, inverted_post_order_compute): New functions. * df.h (struct dataflow): Remove fields visited, pending, considered. Add new fields postorder_inverted, n_blocks_inverted. (df_get_nblocks, df_get_postorder): Prototype change. (df_simple_dataflow): Renamed from df_simple_iterative_dataflow. (df_worklist_dataflow): New function prototype. * df-problems.c: Use df_worklist_dataflow instead of df_iterative_dataflow for solver. * basic-block.h (inverted_post_order_compute): New function prototype. * dce.c (dce_process_block): Pass extra parameter to df_get_n_blocks and df_get_postorder. (calculate_reaching_stores): Call df_simple_dataflow, renamed from df_simple_iterative_dataflow.

--
#pragma ident "Seongbae Park, compiler, http://seongbae.blogspot.com";





--
#pragma ident "Seongbae Park, compiler, http://seongbae.blogspot.com";


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]