From 2b49e1a09d063e655ae02b6ab788cefe58b0d723 Mon Sep 17 00:00:00 2001 From: Kenneth Zadeck Date: Sun, 20 Jan 2008 01:48:25 +0000 Subject: re PR tree-optimization/26854 (Inordinate compile times on large routines) 2008-01-19 Kenneth Zadeck PR rtl-optimization/26854 PR rtl-optimization/34400 * ddg.c (create_ddg_dep_from_intra_loop_link): Do not use DF_RD->gen. * df.h (df_changeable_flags.DF_RD_NO_TRIM): New. (df_rd_bb_info.expanded_lr_out): New. * loop_invariant.c (find_defs): Added DF_RD_NO_TRIM flag. * loop_iv.c (iv_analysis_loop_init): Ditto. * df-problems.c (df_rd_free_bb_info, df_rd_alloc, df_rd_confluence_n, df_rd_bb_local_compute, df_rd_transfer_function, df_rd_free): Added code to allocate, initialize or free expanded_lr_out. (df_rd_bb_local_compute_process_def): Restructured to make more understandable. (df_rd_confluence_n): Add code to do nothing with fake edges and code to no apply invalidate_by_call sets if the sets are being trimmed. (df_lr_local_finalize): Renamed to df_lr_finalize. (df_live_local_finalize): Renamed to df_live_finalize. From-SVN: r131670 --- gcc/df.h | 59 +++++++++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 47 insertions(+), 12 deletions(-) (limited to 'gcc/df.h') diff --git a/gcc/df.h b/gcc/df.h index 04bac49..e5c6870 100644 --- a/gcc/df.h +++ b/gcc/df.h @@ -402,22 +402,30 @@ enum df_changeable_flags { /* Scanning flags. */ /* Flag to control the running of dce as a side effect of building LR. */ - DF_LR_RUN_DCE = 1, /* Run DCE. */ - DF_NO_HARD_REGS = 2, /* Skip hard registers in RD and CHAIN Building. */ - DF_EQ_NOTES = 4, /* Build chains with uses present in EQUIV/EQUAL notes. */ - DF_NO_REGS_EVER_LIVE = 8, /* Do not compute the regs_ever_live. */ + DF_LR_RUN_DCE = 1 << 0, /* Run DCE. */ + DF_NO_HARD_REGS = 1 << 1, /* Skip hard registers in RD and CHAIN Building. */ + + /* Do not trim the solution using the LR result. This can make the + solution take much longer and take more memory. This is + necessary for the loop optimizations, but has a very small time + and space penalty because the loop optimizations process only a + single loop at a time. Any pass that looks at the entire + function should not set this flag. */ + DF_RD_NO_TRIM = 1 << 2, + DF_EQ_NOTES = 1 << 3, /* Build chains with uses present in EQUIV/EQUAL notes. */ + DF_NO_REGS_EVER_LIVE = 1 << 4, /* Do not compute the regs_ever_live. */ /* Cause df_insn_rescan df_notes_rescan and df_insn_delete, to return immediately. This is used by passes that know how to update the scanning them selves. */ - DF_NO_INSN_RESCAN = 16, + DF_NO_INSN_RESCAN = 1 << 5, /* Cause df_insn_rescan df_notes_rescan and df_insn_delete, to return after marking the insn for later processing. This allows all rescans to be batched. */ - DF_DEFER_INSN_RESCAN = 32, + DF_DEFER_INSN_RESCAN = 1 << 6, - DF_VERIFY_SCHEDULED = 64 + DF_VERIFY_SCHEDULED = 1 << 7 }; /* Two of these structures are inline in df, one for the uses and one @@ -705,16 +713,43 @@ struct df_scan_bb_info /* Reaching definitions. All bitmaps are indexed by the id field of - the ref except sparse_kill (see above). */ + the ref except sparse_kill which is indexed by regno. */ struct df_rd_bb_info { - /* Local sets to describe the basic blocks. See the note in the RU - datastructures for kill and sparse_kill. */ + /* Local sets to describe the basic blocks. */ bitmap kill; bitmap sparse_kill; - bitmap gen; /* The set of defs generated in this block. */ - /* The results of the dataflow problem. */ + /* Expanded version of the DF_LT->out bitmap to match the positions + of gen, in and out here. Only allocated if DF_RD_NO_TRIM is + false. */ + bitmap expanded_lr_out; + + /* The set of defs generated in this block. This is not set unless + the def reaches the end of the block. */ + bitmap gen; + + /* The results of the dataflow problem. + + If DF_RD_NO_TRIM is not set, these sets are SOMEWHAT trimmed by + the output of the DF_LR problem. The out set is precisely + trimmed during propagation which means that the result is also + trimmed when the propagation terminates. The in set is not + explicitly trimmed, because this is expensive (adding about 5% to + the cost of a bootstrap). However since the out sets are trimmed + and the in sets are built from the out of the pred, the in set is + MOSTLY trimmed. + + The counter case happens at a branch where the variable V is in + DF_LR->in the true branch but not the false branch. If V is + defined before the branch, RD will propagate that into the + DF_RD_in sets of both branches. When the block is processed, the + DF_RD->out set will have V trimmed out of it but it will still be + left in DF_RD->in. + + If this not a problem for the current optimizers since they were + designed before any trimming was available. This can be fixed by + checking the DF_LR->in set directly. */ bitmap in; /* At the top of the block. */ bitmap out; /* At the bottom of the block. */ }; -- cgit v1.1