2009-11-30 Paolo Bonzini <bonzini@gnu.org>

	PR rtl-optimization/41812
	* fwprop.c (local_md, local_lr): New globals.
	(process_defs, process_uses): Remove local_md argument.  Never
	consider dead pseudos to have singleton def-use chains.
	(single_def_use_enter_block): Perform LR simulation.
	(build_single_def_use_links): Remove local_md local variable.
	Add DF_NOTE.  Allocate local_lr.
	(fwprop_done): Do not remove DF_CHAIN, we do not use it anymore.
	* df-problems.c (df_md_scratch): New.
	(df_md_alloc, df_md_free): Allocate/free it.
	(df_md_local_compute): Only include live registers in init.
	(df_md_transfer_function): Prune the in-set computed by
	the confluence function, and the gen-set too.
	(df_simulate_one_insn_forwards): Fix typo.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154753 138bc75d-0d04-0410-961f-82ee72b054a4

3 files changed, 73 insertions, 29 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 2004c7f4c4e..a2a90f8b2a5 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,20 @@
+2009-11-30  Paolo Bonzini  <bonzini@gnu.org>
+
+	PR rtl-optimization/41812
+	* fwprop.c (local_md, local_lr): New globals.
+	(process_defs, process_uses): Remove local_md argument.  Never
+	consider dead pseudos to have singleton def-use chains.
+	(single_def_use_enter_block): Perform LR simulation.
+	(build_single_def_use_links): Remove local_md local variable.
+	Add DF_NOTE.  Allocate local_lr.
+	(fwprop_done): Do not remove DF_CHAIN, we do not use it anymore.
+	* df-problems.c (df_md_scratch): New.
+	(df_md_alloc, df_md_free): Allocate/free it.
+	(df_md_local_compute): Only include live registers in init.
+	(df_md_transfer_function): Prune the in-set computed by
+	the confluence function, and the gen-set too.
+	(df_simulate_one_insn_forwards): Fix typo.
+
 2009-11-30  Hans-Peter Nilsson  <hp@axis.com>
 
 	PR rtl-optimization/40086
diff --git a/gcc/df-problems.c b/gcc/df-problems.c
index cc7ab882a36..e0ec16778f0 100644
--- a/gcc/df-problems.c
+++ b/gcc/df-problems.c
@@ -1574,10 +1574,9 @@ df_live_transfer_function (int bb_index)
   bitmap gen = bb_info->gen;
   bitmap kill = bb_info->kill;
 
-  /* We need to use a scratch set here so that the value returned from
-     this function invocation properly reflects if the sets changed in
-     a significant way; i.e. not just because the lr set was anded
-     in.  */
+  /* We need to use a scratch set here so that the value returned from this
+     function invocation properly reflects whether the sets changed in a
+     significant way; i.e. not just because the lr set was anded in.  */
   bitmap_and (df_live_scratch, gen, bb_lr_info->out);
   /* No register may reach a location where it is not used.  Thus
      we trim the rr result to the places where it is used.  */
@@ -3975,8 +3974,8 @@ df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
    MULTIPLE DEFINITIONS
 
    Find the locations in the function reached by multiple definition sites
-   for a pseudo.  In and out bitvectors are built for each basic
-   block.
+   for a live pseudo.  In and out bitvectors are built for each basic
+   block.  They are restricted for efficiency to live registers.
 
    The gen and kill sets for the problem are obvious.  Together they
    include all defined registers in a basic block; the gen set includes
@@ -4018,6 +4017,10 @@ df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
     propagating the information to BB3's successors.
    ---------------------------------------------------------------------------*/
 
+/* Scratch var used by transfer functions.  This is used to do md analysis
+   only for live registers.  */
+static bitmap df_md_scratch;
+
 /* Set basic block info.  */
 
 static void
@@ -4061,6 +4064,7 @@ df_md_alloc (bitmap all_blocks)
                                            sizeof (struct df_md_bb_info), 50);
 
   df_grow_bb_info (df_md);
+  df_md_scratch = BITMAP_ALLOC (NULL);
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
@@ -4236,8 +4240,10 @@ df_md_local_compute (bitmap all_blocks)
       bitmap kill = df_md_get_bb_info (bb_index)->kill;
       EXECUTE_IF_SET_IN_BITMAP (frontiers[bb_index], 0, df_bb_index, bi2)
 	{
+	  basic_block bb = BASIC_BLOCK (df_bb_index);
 	  if (bitmap_bit_p (all_blocks, df_bb_index))
-	    bitmap_ior_into (df_md_get_bb_info (df_bb_index)->init, kill);
+	    bitmap_ior_and_into (df_md_get_bb_info (df_bb_index)->init, kill,
+				 df_get_live_in (bb));
 	}
     }
 
@@ -4267,13 +4273,23 @@ df_md_reset (bitmap all_blocks)
 static bool
 df_md_transfer_function (int bb_index)
 {
+  basic_block bb = BASIC_BLOCK (bb_index);
   struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
   bitmap in = bb_info->in;
   bitmap out = bb_info->out;
   bitmap gen = bb_info->gen;
   bitmap kill = bb_info->kill;
 
-  return bitmap_ior_and_compl (out, gen, in, kill);
+  /* We need to use a scratch set here so that the value returned from this
+     function invocation properly reflects whether the sets changed in a
+     significant way; i.e. not just because the live set was anded in.  */
+  bitmap_and (df_md_scratch, gen, df_get_live_out (bb));
+
+  /* Multiple definitions of a register are not relevant if it is not
+     live.  Thus we trim the result to the places where it is live.  */
+  bitmap_and_into (in, df_get_live_in (bb));
+
+  return bitmap_ior_and_compl (out, df_md_scratch, in, kill);
 }
 
 /* Initialize the solution bit vectors for problem.  */
@@ -4336,6 +4352,7 @@ df_md_free (void)
 	}
     }
 
+  BITMAP_FREE (df_md_scratch);
   free_alloc_pool (df_md->block_pool);
 
   df_md->block_info_size = 0;
diff --git a/gcc/fwprop.c b/gcc/fwprop.c
index 1159211ae98..32264cda90c 100644
--- a/gcc/fwprop.c
+++ b/gcc/fwprop.c
@@ -118,10 +118,16 @@ static int num_changes;
 
 DEF_VEC_P(df_ref);
 DEF_VEC_ALLOC_P(df_ref,heap);
-VEC(df_ref,heap) *use_def_ref;
-VEC(df_ref,heap) *reg_defs;
-VEC(df_ref,heap) *reg_defs_stack;
+static VEC(df_ref,heap) *use_def_ref;
+static VEC(df_ref,heap) *reg_defs;
+static VEC(df_ref,heap) *reg_defs_stack;
 
+/* The MD bitmaps are trimmed to include only live registers to cut
+   memory usage on testcases like insn-recog.c.  Track live registers
+   in the basic block and do not perform forward propagation if the
+   destination is a dead pseudo occurring in a note.  */
+static bitmap local_md;
+static bitmap local_lr;
 
 /* Return the only def in USE's use-def chain, or NULL if there is
    more than one def in the chain.  */
@@ -143,7 +149,7 @@ get_def_for_use (df_ref use)
 	(DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)
 
 static void
-process_defs (bitmap local_md, df_ref *def_rec, int top_flag)
+process_defs (df_ref *def_rec, int top_flag)
 {
   df_ref def;
   while ((def = *def_rec++) != NULL)
@@ -188,7 +194,7 @@ process_defs (bitmap local_md, df_ref *def_rec, int top_flag)
    is an artificial use vector.  */
 
 static void
-process_uses (bitmap local_md, df_ref *use_rec, int top_flag)
+process_uses (df_ref *use_rec, int top_flag)
 {
   df_ref use;
   while ((use = *use_rec++) != NULL)
@@ -196,7 +202,8 @@ process_uses (bitmap local_md, df_ref *use_rec, int top_flag)
       {
         unsigned int uregno = DF_REF_REGNO (use);
         if (VEC_index (df_ref, reg_defs, uregno)
-	    && !bitmap_bit_p (local_md, uregno))
+	    && !bitmap_bit_p (local_md, uregno)
+	    && bitmap_bit_p (local_lr, uregno))
 	  VEC_replace (df_ref, use_def_ref, DF_REF_ID (use),
 		       VEC_index (df_ref, reg_defs, uregno));
       }
@@ -204,32 +211,36 @@ process_uses (bitmap local_md, df_ref *use_rec, int top_flag)
 
 
 static void
-single_def_use_enter_block (struct dom_walk_data *walk_data, basic_block bb)
+single_def_use_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+			    basic_block bb)
 {
-  bitmap local_md = (bitmap) walk_data->global_data;
   int bb_index = bb->index;
-  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+  struct df_md_bb_info *md_bb_info = df_md_get_bb_info (bb_index);
+  struct df_lr_bb_info *lr_bb_info = df_lr_get_bb_info (bb_index);
   rtx insn;
 
-  bitmap_copy (local_md, bb_info->in);
+  bitmap_copy (local_md, md_bb_info->in);
+  bitmap_copy (local_lr, lr_bb_info->in);
 
   /* Push a marker for the leave_block callback.  */
   VEC_safe_push (df_ref, heap, reg_defs_stack, NULL);
 
-  process_uses (local_md, df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
-  process_defs (local_md, df_get_artificial_defs (bb_index), DF_REF_AT_TOP);
+  process_uses (df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
+  process_defs (df_get_artificial_defs (bb_index), DF_REF_AT_TOP);
+  df_simulate_initialize_forwards (bb, local_lr);
 
   FOR_BB_INSNS (bb, insn)
     if (INSN_P (insn))
       {
         unsigned int uid = INSN_UID (insn);
-        process_uses (local_md, DF_INSN_UID_USES (uid), 0);
-        process_uses (local_md, DF_INSN_UID_EQ_USES (uid), 0);
-        process_defs (local_md, DF_INSN_UID_DEFS (uid), 0);
+        process_uses (DF_INSN_UID_USES (uid), 0);
+        process_uses (DF_INSN_UID_EQ_USES (uid), 0);
+        process_defs (DF_INSN_UID_DEFS (uid), 0);
+	df_simulate_one_insn_forwards (bb, insn, local_lr);
       }
 
-  process_uses (local_md, df_get_artificial_uses (bb_index), 0);
-  process_defs (local_md, df_get_artificial_defs (bb_index), 0);
+  process_uses (df_get_artificial_uses (bb_index), 0);
+  process_defs (df_get_artificial_defs (bb_index), 0);
 }
 
 /* Pop the definitions created in this basic block when leaving its
@@ -260,12 +271,12 @@ static void
 build_single_def_use_links (void)
 {
   struct dom_walk_data walk_data;
-  bitmap local_md;
 
   /* We use the multiple definitions problem to compute our restricted
      use-def chains.  */
   df_set_flags (DF_EQ_NOTES);
   df_md_add_problem ();
+  df_note_add_problem ();
   df_analyze ();
   df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
 
@@ -277,6 +288,7 @@ build_single_def_use_links (void)
 
   reg_defs_stack = VEC_alloc (df_ref, heap, n_basic_blocks * 10);
   local_md = BITMAP_ALLOC (NULL);
+  local_lr = BITMAP_ALLOC (NULL);
 
   /* Walk the dominator tree looking for single reaching definitions
      dominating the uses.  This is similar to how SSA form is built.  */
@@ -284,12 +296,12 @@ build_single_def_use_links (void)
   walk_data.initialize_block_local_data = NULL;
   walk_data.before_dom_children = single_def_use_enter_block;
   walk_data.after_dom_children = single_def_use_leave_block;
-  walk_data.global_data = local_md;
 
   init_walk_dominator_tree (&walk_data);
   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
   fini_walk_dominator_tree (&walk_data);
 
+  BITMAP_FREE (local_lr);
   BITMAP_FREE (local_md);
   VEC_free (df_ref, heap, reg_defs);
   VEC_free (df_ref, heap, reg_defs_stack);
@@ -1385,11 +1397,9 @@ fwprop_done (void)
     fprintf (dump_file,
 	     "\nNumber of successful forward propagations: %d\n\n",
 	     num_changes);
-  df_remove_problem (df_chain);
 }
 
 
-
 /* Main entry point.  */
 
 static bool