re PR tree-optimization/26854 (Inordinate compile times on large routines)

2008-01-19  Kenneth Zadeck <zadeck@naturalbridge.com>

	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

1 files changed, 47 insertions, 12 deletions

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.  */
 };