* bitmap.h (bitmap_and_into): Update prototype.

	* bitmap.c (bitmap_and_into): Return true if the target bitmap
	changed, false otherwise.

	* df.h (df_dump_insn_problem_function): New function type.
	(struct df_problem): Add two functions, to dump just before and
	just after an insn.
	(DF_RD_PRUNE_DEAD_DEFS): New changable flag.
	(df_dump_insn_top, df_dump_insn_bottom): New prototypes.
	* df-core (df_dump_region): Use dump_bb.
	(df_dump_bb_problem_data): New function.
	(df_dump_top, df_dump_bottom): Rewrite using df_dump_bb_problem_data.
	(df_dump_insn_problem_data): New function.
	(df_dump_insn_top, df_dump_insn_bottom): New functions.
	* df-scan.c (problem_SCAN): Add NULL fields for new members.
	* df-problems.c (df_rd_local_compute): Ignore hard registers if
	DF_NO_HARD_REGS is in effect.
	(df_rd_transfer_function): If DF_RD_PRUNE_DEAD_DEFS is in effect,
	prune reaching defs using the LR problem.
	(df_rd_start_dump): Fix dumping of DEFs map.
	(df_rd_dump_defs_set): New function.
	(df_rd_top_dump, df_rd_bottom_dump): Use it.
	(problem_RD): Add NULL fields for new members.
	(problem_LR, problem_LIVE): Likewise.
	(df_chain_bb_dump): New function.
	(df_chain_top_dump): Dump only for artificial DEFs and USEs,
	using df_chain_bb_dump.
	(df_chain_bottom_dump): Likewise.
	(df_chain_insn_top_dump, df_chain_insn_bottom_dump): New functions.
	(problem_CHAIN): Add them as new members.
	(problem_WORD_LR, problem_NOTE): Add NULL fields for new members.
	(problem_MD): Likewise.
	* cfgrtl.c (rtl_dump_bb): Use df_dump_insn_top and df_dump_insn_bottom.
	(print_rtl_with_bb): Likewise.

	* dce.c (init_dce): Use DF_RD_PRUNE_DEAD_DEFS.
	* loop-invariant.c (find_defs): Likewise.
	* loop-iv.c (iv_analysis_loop_init): Likewise.
	* ree.c (find_and_remove_re): Likewise.
	* web.c (web_main): Likewise.



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

13 files changed, 371 insertions, 124 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 87cf9e82b44..39e23bdc22c 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,46 @@
+2012-10-08  Steven Bosscher  <steven@gcc.gnu.org>
+
+	* bitmap.h (bitmap_and_into): Update prototype.
+	* bitmap.c (bitmap_and_into): Return true if the target bitmap
+	changed, false otherwise.
+
+	* df.h (df_dump_insn_problem_function): New function type.
+	(struct df_problem): Add two functions, to dump just before and
+	just after an insn.
+	(DF_RD_PRUNE_DEAD_DEFS): New changable flag.
+	(df_dump_insn_top, df_dump_insn_bottom): New prototypes.
+	* df-core (df_dump_region): Use dump_bb.
+	(df_dump_bb_problem_data): New function.
+	(df_dump_top, df_dump_bottom): Rewrite using df_dump_bb_problem_data.
+	(df_dump_insn_problem_data): New function.
+	(df_dump_insn_top, df_dump_insn_bottom): New functions.
+	* df-scan.c (problem_SCAN): Add NULL fields for new members.
+	* df-problems.c (df_rd_local_compute): Ignore hard registers if
+	DF_NO_HARD_REGS is in effect.
+	(df_rd_transfer_function): If DF_RD_PRUNE_DEAD_DEFS is in effect,
+	prune reaching defs using the LR problem.
+	(df_rd_start_dump): Fix dumping of DEFs map.
+	(df_rd_dump_defs_set): New function.
+	(df_rd_top_dump, df_rd_bottom_dump): Use it.
+	(problem_RD): Add NULL fields for new members.
+	(problem_LR, problem_LIVE): Likewise.
+	(df_chain_bb_dump): New function.
+	(df_chain_top_dump): Dump only for artificial DEFs and USEs,
+	using df_chain_bb_dump.
+	(df_chain_bottom_dump): Likewise.
+	(df_chain_insn_top_dump, df_chain_insn_bottom_dump): New functions.
+	(problem_CHAIN): Add them as new members.
+	(problem_WORD_LR, problem_NOTE): Add NULL fields for new members.
+	(problem_MD): Likewise.
+	* cfgrtl.c (rtl_dump_bb): Use df_dump_insn_top and df_dump_insn_bottom.
+	(print_rtl_with_bb): Likewise.
+
+	* dce.c (init_dce): Use DF_RD_PRUNE_DEAD_DEFS.
+	* loop-invariant.c (find_defs): Likewise.
+	* loop-iv.c (iv_analysis_loop_init): Likewise.
+	* ree.c (find_and_remove_re): Likewise.
+	* web.c (web_main): Likewise.
+
 2012-10-08  Jason Merrill  <jason@redhat.com>
 
 	* config/rs6000/rs6000.c (rs6000_code_end): Protect the use of
@@ -319,7 +362,7 @@
 
 2012-10-04  Jeff Law  <law@redhat.com>
 
-	* PR target/50356
+	PR target/50356
 	* config/h8300/h8300.c (h8300_rtx_costs): Fix typo in CONST_INT case.
 
 2012-10-04  Jason Merrill  <jason@redhat.com>
@@ -329,8 +372,8 @@
 
 2012-10-04  Basile Starynkevitch  <basile@starynkevitch.net>
 
-        * gengtype.c (walk_type): Emit mark_hook when inside a
-          struct of a union member.
+	* gengtype.c (walk_type): Emit mark_hook when inside a
+	struct of a union member.
 
 2012-10-04  Georg-Johann Lay  <avr@gjlay.de>
 
diff --git a/gcc/bitmap.c b/gcc/bitmap.c
index 63f0e099a05..76f70fcdb84 100644
--- a/gcc/bitmap.c
+++ b/gcc/bitmap.c
@@ -916,17 +916,18 @@ bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
     dst->indx = dst->current->indx;
 }
 
-/* A &= B.  */
+/* A &= B.  Return true if A changed.  */
 
-void
+bool
 bitmap_and_into (bitmap a, const_bitmap b)
 {
   bitmap_element *a_elt = a->first;
   const bitmap_element *b_elt = b->first;
   bitmap_element *next;
+  bool changed = false;
 
   if (a == b)
-    return;
+    return false;
 
   while (a_elt && b_elt)
     {
@@ -935,6 +936,7 @@ bitmap_and_into (bitmap a, const_bitmap b)
 	  next = a_elt->next;
 	  bitmap_element_free (a, a_elt);
 	  a_elt = next;
+	  changed = true;
 	}
       else if (b_elt->indx < a_elt->indx)
 	b_elt = b_elt->next;
@@ -947,7 +949,8 @@ bitmap_and_into (bitmap a, const_bitmap b)
 	  for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
 	    {
 	      BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
-
+	      if (a_elt->bits[ix] != r)
+		changed = true;
 	      a_elt->bits[ix] = r;
 	      ior |= r;
 	    }
@@ -958,9 +961,17 @@ bitmap_and_into (bitmap a, const_bitmap b)
 	  b_elt = b_elt->next;
 	}
     }
-  bitmap_elt_clear_from (a, a_elt);
+
+  if (a_elt)
+    {
+      changed = true;
+      bitmap_elt_clear_from (a, a_elt);
+    }
+
   gcc_checking_assert (!a->current == !a->first
 		       && (!a->current || a->indx == a->current->indx));
+
+  return changed;
 }
 
 
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index 1c39cd49efd..3e369b077c6 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -224,7 +224,7 @@ extern unsigned long bitmap_count_bits (const_bitmap);
    are three operand versions that to not destroy the source bitmaps.
    The operations supported are &, & ~, |, ^.  */
 extern void bitmap_and (bitmap, const_bitmap, const_bitmap);
-extern void bitmap_and_into (bitmap, const_bitmap);
+extern bool bitmap_and_into (bitmap, const_bitmap);
 extern bool bitmap_and_compl (bitmap, const_bitmap, const_bitmap);
 extern bool bitmap_and_compl_into (bitmap, const_bitmap);
 #define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
diff --git a/gcc/cfgrtl.c b/gcc/cfgrtl.c
index ad18400a064..7946a3fe9f4 100644
--- a/gcc/cfgrtl.c
+++ b/gcc/cfgrtl.c
@@ -1856,11 +1856,14 @@ rtl_dump_bb (FILE *outf, basic_block bb, int indent, int flags)
     for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last;
 	 insn = NEXT_INSN (insn))
       {
+	if (flags & TDF_DETAILS)
+	  df_dump_insn_top (insn, outf);
 	if (! (flags & TDF_SLIM))
 	  print_rtl_single (outf, insn);
 	else
 	  dump_insn_slim (outf, insn);
-
+	if (flags & TDF_DETAILS)
+	  df_dump_insn_bottom (insn, outf);
       }
 
   if (df && (flags & TDF_DETAILS))
@@ -1941,10 +1944,14 @@ print_rtl_with_bb (FILE *outf, const_rtx rtx_first, int flags)
 		fprintf (outf, ";; Insn is in multiple basic blocks\n");
 	    }
 
+	  if (flags & TDF_DETAILS)
+	    df_dump_insn_top (tmp_rtx, outf);
 	  if (! (flags & TDF_SLIM))
 	    print_rtl_single (outf, tmp_rtx);
 	  else
 	    dump_insn_slim (outf, tmp_rtx);
+	  if (flags & TDF_DETAILS)
+	    df_dump_insn_bottom (tmp_rtx, outf);
 
 	  if (flags & TDF_BLOCKS)
 	    {
diff --git a/gcc/dce.c b/gcc/dce.c
index 11f8edb7b70..9a42da761c2 100644
--- a/gcc/dce.c
+++ b/gcc/dce.c
@@ -704,7 +704,10 @@ init_dce (bool fast)
   if (!df_in_progress)
     {
       if (!fast)
-	df_chain_add_problem (DF_UD_CHAIN);
+	{
+	  df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
+	  df_chain_add_problem (DF_UD_CHAIN);
+	}
       df_analyze ();
     }
 
diff --git a/gcc/df-core.c b/gcc/df-core.c
index 6613d2aebc3..34f1ea351c1 100644
--- a/gcc/df-core.c
+++ b/gcc/df-core.c
@@ -1994,10 +1994,7 @@ df_dump_region (FILE *file)
       EXECUTE_IF_SET_IN_BITMAP (df->blocks_to_analyze, 0, bb_index, bi)
 	{
 	  basic_block bb = BASIC_BLOCK (bb_index);
-
-	  df_print_bb_index (bb, file);
-	  df_dump_top (bb, file);
-	  df_dump_bottom (bb, file);
+	  dump_bb (file, bb, 0, TDF_DETAILS);
 	}
       fprintf (file, "\n");
     }
@@ -2035,10 +2032,9 @@ df_dump_start (FILE *file)
 }
 
 
-/* Dump the top of the block information for BB.  */
-
-void
-df_dump_top (basic_block bb, FILE *file)
+/* Dump the top or bottom of the block information for BB.  */
+static void
+df_dump_bb_problem_data (basic_block bb, FILE *file, bool top)
 {
   int i;
 
@@ -2050,19 +2046,40 @@ df_dump_top (basic_block bb, FILE *file)
       struct dataflow *dflow = df->problems_in_order[i];
       if (dflow->computed)
 	{
-	  df_dump_bb_problem_function bbfun = dflow->problem->dump_top_fun;
+	  df_dump_bb_problem_function bbfun;
+
+	  if (top)
+	    bbfun = dflow->problem->dump_top_fun;
+	  else
+	    bbfun = dflow->problem->dump_bottom_fun;
+
 	  if (bbfun)
 	    bbfun (bb, file);
 	}
     }
 }
 
+/* Dump the top of the block information for BB.  */
+
+void
+df_dump_top (basic_block bb, FILE *file)
+{
+  df_dump_bb_problem_data (bb, file, /*top=*/true);
+}
 
 /* Dump the bottom of the block information for BB.  */
 
 void
 df_dump_bottom (basic_block bb, FILE *file)
 {
+  df_dump_bb_problem_data (bb, file, /*top=*/false);
+}
+
+
+/* Dump information about INSN just before or after dumping INSN itself.  */
+static void
+df_dump_insn_problem_data (const_rtx insn, FILE *file, bool top)
+{
   int i;
 
   if (!df || !file)
@@ -2073,13 +2090,35 @@ df_dump_bottom (basic_block bb, FILE *file)
       struct dataflow *dflow = df->problems_in_order[i];
       if (dflow->computed)
 	{
-	  df_dump_bb_problem_function bbfun = dflow->problem->dump_bottom_fun;
-	  if (bbfun)
-	    bbfun (bb, file);
+	  df_dump_insn_problem_function insnfun;
+
+	  if (top)
+	    insnfun = dflow->problem->dump_insn_top_fun;
+	  else
+	    insnfun = dflow->problem->dump_insn_bottom_fun;
+
+	  if (insnfun)
+	    insnfun (insn, file);
 	}
     }
 }
 
+/* Dump information about INSN before dumping INSN itself.  */
+
+void
+df_dump_insn_top (const_rtx insn, FILE *file)
+{
+  df_dump_insn_problem_data (insn,  file, /*top=*/true);
+}
+
+/* Dump information about INSN after dumping INSN itself.  */
+
+void
+df_dump_insn_bottom (const_rtx insn, FILE *file)
+{
+  df_dump_insn_problem_data (insn,  file, /*top=*/false);
+}
+
 
 static void
 df_ref_dump (df_ref ref, FILE *file)
diff --git a/gcc/df-problems.c b/gcc/df-problems.c
index a1a0e71422d..53e77388f02 100644
--- a/gcc/df-problems.c
+++ b/gcc/df-problems.c
@@ -152,6 +152,17 @@ df_print_bb_index (basic_block bb, FILE *file)
    pseudo reaches.  In and out bitvectors are built for each basic
    block.  The id field in the ref is used to index into these sets.
    See df.h for details.
+
+   If the DF_RD_PRUNE_DEAD_DEFS changable flag is set, only DEFs reaching
+   existing uses are included in the global reaching DEFs set, or in other
+   words only DEFs that are still live.  This is a kind of pruned version
+   of the traditional reaching definitions problem that is much less
+   complex to compute and produces enough information to compute UD-chains.
+   In this context, live must be interpreted in the DF_LR sense: Uses that
+   are upward exposed but maybe not initialized on all paths through the
+   CFG.  For a USE that is not reached by a DEF on all paths, we still want
+   to make those DEFs that do reach the USE visible, and pruning based on
+   DF_LIVE would make that impossible.
    ----------------------------------------------------------------------------*/
 
 /* This problem plays a large number of games for the sake of
@@ -239,8 +250,7 @@ df_rd_alloc (bitmap all_blocks)
   df_grow_bb_info (df_rd);
 
   /* Because of the clustering of all use sites for the same pseudo,
-     we have to process all of the blocks before doing the
-     analysis.  */
+     we have to process all of the blocks before doing the analysis.  */
 
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
@@ -450,12 +460,16 @@ df_rd_local_compute (bitmap all_blocks)
   /* Set up the knockout bit vectors to be applied across EH_EDGES.  */
   EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, regno, bi)
     {
-      if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
-	bitmap_set_bit (sparse_invalidated, regno);
-      else
-	bitmap_set_range (dense_invalidated,
-			  DF_DEFS_BEGIN (regno),
-			  DF_DEFS_COUNT (regno));
+      if (! HARD_REGISTER_NUM_P (regno)
+	  || !(df->changeable_flags & DF_NO_HARD_REGS))
+	{
+	  if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
+	    bitmap_set_bit (sparse_invalidated, regno);
+	  else
+	    bitmap_set_range (dense_invalidated,
+			      DF_DEFS_BEGIN (regno),
+			      DF_DEFS_COUNT (regno));
+	}
     }
 
   bitmap_clear (&seen_in_block);
@@ -534,13 +548,13 @@ df_rd_transfer_function (int bb_index)
   bitmap gen = &bb_info->gen;
   bitmap kill = &bb_info->kill;
   bitmap sparse_kill = &bb_info->sparse_kill;
+  bool changed = false;
 
   if (bitmap_empty_p (sparse_kill))
-    return  bitmap_ior_and_compl (out, gen, in, kill);
+    changed = bitmap_ior_and_compl (out, gen, in, kill);
   else
     {
       struct df_rd_problem_data *problem_data;
-      bool changed = false;
       bitmap_head tmp;
 
       /* Note that TMP is _not_ a temporary bitmap if we end up replacing
@@ -564,11 +578,31 @@ df_rd_transfer_function (int bb_index)
 	  bb_info->out = tmp;
 	}
       else
-	  bitmap_clear (&tmp);
-      return changed;
+	bitmap_clear (&tmp);
     }
-}
 
+  if (df->changeable_flags & DF_RD_PRUNE_DEAD_DEFS)
+    {
+      /* Create a mask of DEFs for all registers live at the end of this
+	 basic block, and mask out DEFs of registers that are not live.
+	 Computing the mask looks costly, but the benefit of the pruning
+	 outweighs the cost.  */
+      struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
+      bitmap regs_live_out = &df_lr_get_bb_info (bb_index)->out;
+      bitmap live_defs = BITMAP_ALLOC (&df_bitmap_obstack);
+      unsigned int regno;
+      bitmap_iterator bi;
+
+      EXECUTE_IF_SET_IN_BITMAP (regs_live_out, 0, regno, bi)
+	bitmap_set_range (live_defs,
+			  DF_DEFS_BEGIN (regno),
+			  DF_DEFS_COUNT (regno));
+      changed |= bitmap_and_into (&bb_info->out, live_defs);
+      BITMAP_FREE (live_defs);
+    }
+
+  return changed;
+}
 
 /* Free all storage associated with the problem.  */
 
@@ -604,23 +638,66 @@ df_rd_start_dump (FILE *file)
   if (!df_rd->block_info)
     return;
 
-  fprintf (file, ";; Reaching defs:\n\n");
+  fprintf (file, ";; Reaching defs:\n");
 
-  fprintf (file, "  sparse invalidated \t");
+  fprintf (file, ";;  sparse invalidated \t");
   dump_bitmap (file, &problem_data->sparse_invalidated_by_call);
-  fprintf (file, "  dense invalidated \t");
+  fprintf (file, ";;  dense invalidated \t");
   dump_bitmap (file, &problem_data->dense_invalidated_by_call);
 
+  fprintf (file, ";;  reg->defs[] map:\t");
   for (regno = 0; regno < m; regno++)
     if (DF_DEFS_COUNT (regno))
       fprintf (file, "%d[%d,%d] ", regno,
 	       DF_DEFS_BEGIN (regno),
-	       DF_DEFS_COUNT (regno));
+	       DF_DEFS_BEGIN (regno) + DF_DEFS_COUNT (regno) - 1);
   fprintf (file, "\n");
-
 }
 
 
+static void
+df_rd_dump_defs_set (bitmap defs_set, const char *prefix, FILE *file)
+{
+  bitmap_head tmp;
+  unsigned int regno;
+  unsigned int m = DF_REG_SIZE(df);
+  bool first_reg = true;
+
+  fprintf (file, "%s\t(%d) ", prefix, (int) bitmap_count_bits (defs_set));
+
+  bitmap_initialize (&tmp, &df_bitmap_obstack);
+  for (regno = 0; regno < m; regno++)
+    {
+      if (HARD_REGISTER_NUM_P (regno)
+	  && (df->changeable_flags & DF_NO_HARD_REGS))
+	continue;
+      bitmap_set_range (&tmp, DF_DEFS_BEGIN (regno), DF_DEFS_COUNT (regno));
+      bitmap_and_into (&tmp, defs_set);
+      if (! bitmap_empty_p (&tmp))
+	{
+	  bitmap_iterator bi;
+	  unsigned int ix;
+	  bool first_def = true;
+
+	  if (! first_reg)
+	    fprintf (file, ",");
+	  first_reg = false;
+
+	  fprintf (file, "%u[", regno);
+	  EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, ix, bi)
+	    {
+	      fprintf (file, "%s%u", first_def ? "" : ",", ix);
+	      first_def = false;
+	    }
+	  fprintf (file, "]");
+	}
+      bitmap_clear (&tmp);
+    }
+
+  fprintf (file, "\n");
+  bitmap_clear (&tmp);
+}
+
 /* Debugging info at top of bb.  */
 
 static void
@@ -630,16 +707,13 @@ df_rd_top_dump (basic_block bb, FILE *file)
   if (!bb_info)
     return;
 
-  fprintf (file, ";; rd  in  \t(%d)\n", (int) bitmap_count_bits (&bb_info->in));
-  dump_bitmap (file, &bb_info->in);
-  fprintf (file, ";; rd  gen \t(%d)\n", (int) bitmap_count_bits (&bb_info->gen));
-  dump_bitmap (file, &bb_info->gen);
-  fprintf (file, ";; rd  kill\t(%d)\n", (int) bitmap_count_bits (&bb_info->kill));
-  dump_bitmap (file, &bb_info->kill);
+  df_rd_dump_defs_set (&bb_info->in, ";; rd  in  ", file);
+  df_rd_dump_defs_set (&bb_info->gen, ";; rd  gen ", file);
+  df_rd_dump_defs_set (&bb_info->kill, ";; rd  kill", file);
 }
 
 
-/* Debugging info at top of bb.  */
+/* Debugging info at bottom of bb.  */
 
 static void
 df_rd_bottom_dump (basic_block bb, FILE *file)
@@ -648,8 +722,7 @@ df_rd_bottom_dump (basic_block bb, FILE *file)
   if (!bb_info)
     return;
 
-  fprintf (file, ";; rd  out \t(%d)\n", (int) bitmap_count_bits (&bb_info->out));
-  dump_bitmap (file, &bb_info->out);
+  df_rd_dump_defs_set (&bb_info->out, ";; rd  out ", file);
 }
 
 /* All of the information associated with every instance of the problem.  */
@@ -673,6 +746,8 @@ static struct df_problem problem_RD =
   df_rd_start_dump,           /* Debugging.  */
   df_rd_top_dump,             /* Debugging start block.  */
   df_rd_bottom_dump,          /* Debugging end block.  */
+  NULL,                       /* Debugging start insn.  */
+  NULL,                       /* Debugging end insn.  */
   NULL,                       /* Incremental solution verify start.  */
   NULL,                       /* Incremental solution verify end.  */
   NULL,                       /* Dependent problem.  */
@@ -1209,6 +1284,8 @@ static struct df_problem problem_LR =
   NULL,                       /* Debugging.  */
   df_lr_top_dump,             /* Debugging start block.  */
   df_lr_bottom_dump,          /* Debugging end block.  */
+  NULL,                       /* Debugging start insn.  */
+  NULL,                       /* Debugging end insn.  */
   df_lr_verify_solution_start,/* Incremental solution verify start.  */
   df_lr_verify_solution_end,  /* Incremental solution verify end.  */
   NULL,                       /* Dependent problem.  */
@@ -1738,6 +1815,8 @@ static struct df_problem problem_LIVE =
   NULL,                         /* Debugging.  */
   df_live_top_dump,             /* Debugging start block.  */
   df_live_bottom_dump,          /* Debugging end block.  */
+  NULL,                         /* Debugging start insn.  */
+  NULL,                         /* Debugging end insn.  */
   df_live_verify_solution_start,/* Incremental solution verify start.  */
   df_live_verify_solution_end,  /* Incremental solution verify end.  */
   &problem_LR,                  /* Dependent problem.  */
@@ -2140,112 +2219,142 @@ df_chain_free (void)
 /* Debugging info.  */
 
 static void
-df_chain_top_dump (basic_block bb, FILE *file)
+df_chain_bb_dump (basic_block bb, FILE *file, bool top)
 {
+  /* Artificials are only hard regs.  */
+  if (df->changeable_flags & DF_NO_HARD_REGS)
+    return;
+  if (df_chain_problem_p (DF_UD_CHAIN))
+    {
+      fprintf (file,
+	       ";;  UD chains for artificial uses at %s\n",
+	       top ? "top" : "bottom");
+      df_ref *use_rec = df_get_artificial_uses (bb->index);
+      if (*use_rec)
+	{
+	  while (*use_rec)
+	    {
+	      df_ref use = *use_rec;
+	      if ((top && (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
+		  || (!top && !(DF_REF_FLAGS (use) & DF_REF_AT_TOP)))
+		{
+		  fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
+		  df_chain_dump (DF_REF_CHAIN (use), file);
+		  fprintf (file, "\n");
+		}
+	      use_rec++;
+	    }
+	}
+    }
   if (df_chain_problem_p (DF_DU_CHAIN))
     {
-      rtx insn;
+      fprintf (file,
+	       ";;  DU chains for artificial defs at %s\n",
+	       top ? "top" : "bottom");
       df_ref *def_rec = df_get_artificial_defs (bb->index);
       if (*def_rec)
 	{
-
-	  fprintf (file, ";;  DU chains for artificial defs\n");
 	  while (*def_rec)
 	    {
 	      df_ref def = *def_rec;
-	      fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
-	      df_chain_dump (DF_REF_CHAIN (def), file);
-	      fprintf (file, "\n");
-	      def_rec++;
-	    }
-	}
 
-      FOR_BB_INSNS (bb, insn)
-	{
-	  if (INSN_P (insn))
-	    {
-	      struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
-	      def_rec = DF_INSN_INFO_DEFS (insn_info);
-	      if (*def_rec)
+	      if ((top && (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
+		  || (!top && !(DF_REF_FLAGS (def) & DF_REF_AT_TOP)))
 		{
-		  fprintf (file, ";;   DU chains for insn luid %d uid %d\n",
-			   DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
-
-		  while (*def_rec)
-		    {
-		      df_ref def = *def_rec;
-		      fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
-		      if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
-			fprintf (file, "read/write ");
-		      df_chain_dump (DF_REF_CHAIN (def), file);
-		      fprintf (file, "\n");
-		      def_rec++;
-		    }
+		  fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
+		  df_chain_dump (DF_REF_CHAIN (def), file);
+		  fprintf (file, "\n");
 		}
+	      def_rec++;
 	    }
 	}
     }
 }
 
+static void
+df_chain_top_dump (basic_block bb, FILE *file)
+{
+  df_chain_bb_dump (bb, file, /*top=*/true);
+}
 
 static void
 df_chain_bottom_dump (basic_block bb, FILE *file)
 {
-  if (df_chain_problem_p (DF_UD_CHAIN))
-    {
-      rtx insn;
-      df_ref *use_rec = df_get_artificial_uses (bb->index);
+  df_chain_bb_dump (bb, file, /*top=*/false);
+}
 
-      if (*use_rec)
+static void
+df_chain_insn_top_dump (const_rtx insn, FILE *file)
+{
+  if (df_chain_problem_p (DF_UD_CHAIN) && INSN_P (insn))
+    {
+      struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
+      df_ref *use_rec = DF_INSN_INFO_USES (insn_info);
+      df_ref *eq_use_rec = DF_INSN_INFO_EQ_USES (insn_info);
+      fprintf (file, ";;   UD chains for insn luid %d uid %d\n",
+	       DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
+      if (*use_rec || *eq_use_rec)
 	{
-	  fprintf (file, ";;  UD chains for artificial uses\n");
 	  while (*use_rec)
 	    {
 	      df_ref use = *use_rec;
-	      fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
-	      df_chain_dump (DF_REF_CHAIN (use), file);
-	      fprintf (file, "\n");
+	      if (! HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
+		  || !(df->changeable_flags & DF_NO_HARD_REGS))
+		{
+		  fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
+		  if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
+		    fprintf (file, "read/write ");
+		  df_chain_dump (DF_REF_CHAIN (use), file);
+		  fprintf (file, "\n");
+		}
 	      use_rec++;
 	    }
+	  while (*eq_use_rec)
+	    {
+	      df_ref use = *eq_use_rec;
+	      if (! HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
+		  || !(df->changeable_flags & DF_NO_HARD_REGS))
+		{
+		  fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
+		  df_chain_dump (DF_REF_CHAIN (use), file);
+		  fprintf (file, "\n");
+		}
+	      eq_use_rec++;
+	    }
 	}
+    }
+}
 
-      FOR_BB_INSNS (bb, insn)
+static void
+df_chain_insn_bottom_dump (const_rtx insn, FILE *file)
+{
+  if (df_chain_problem_p (DF_DU_CHAIN) && INSN_P (insn))
+    {
+      struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
+      df_ref *def_rec = DF_INSN_INFO_DEFS (insn_info);
+      fprintf (file, ";;   DU chains for insn luid %d uid %d\n",
+	       DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
+      if (*def_rec)
 	{
-	  if (INSN_P (insn))
+	  while (*def_rec)
 	    {
-	      struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
-	      df_ref *eq_use_rec = DF_INSN_INFO_EQ_USES (insn_info);
-	      use_rec = DF_INSN_INFO_USES (insn_info);
-	      if (*use_rec || *eq_use_rec)
+	      df_ref def = *def_rec;
+	      if (! HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
+		  || !(df->changeable_flags & DF_NO_HARD_REGS))
 		{
-		  fprintf (file, ";;   UD chains for insn luid %d uid %d\n",
-			   DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
-
-		  while (*use_rec)
-		    {
-		      df_ref use = *use_rec;
-		      fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
-		      if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
-			fprintf (file, "read/write ");
-		      df_chain_dump (DF_REF_CHAIN (use), file);
-		      fprintf (file, "\n");
-		      use_rec++;
-		    }
-		  while (*eq_use_rec)
-		    {
-		      df_ref use = *eq_use_rec;
-		      fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
-		      df_chain_dump (DF_REF_CHAIN (use), file);
-		      fprintf (file, "\n");
-		      eq_use_rec++;
-		    }
+		  fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
+		  if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
+		    fprintf (file, "read/write ");
+		  df_chain_dump (DF_REF_CHAIN (def), file);
+		  fprintf (file, "\n");
 		}
+	      def_rec++;
 	    }
 	}
+      fprintf (file, "\n");
     }
 }
 
-
 static struct df_problem problem_CHAIN =
 {
   DF_CHAIN,                   /* Problem id.  */
@@ -2265,6 +2374,8 @@ static struct df_problem problem_CHAIN =
   NULL,                       /* Debugging.  */
   df_chain_top_dump,          /* Debugging start block.  */
   df_chain_bottom_dump,       /* Debugging end block.  */
+  df_chain_insn_top_dump,     /* Debugging start insn.  */
+  df_chain_insn_bottom_dump,  /* Debugging end insn.  */
   NULL,                       /* Incremental solution verify start.  */
   NULL,                       /* Incremental solution verify end.  */
   &problem_RD,                /* Dependent problem.  */
@@ -2643,9 +2754,11 @@ static struct df_problem problem_WORD_LR =
   NULL,                            /* Debugging.  */
   df_word_lr_top_dump,             /* Debugging start block.  */
   df_word_lr_bottom_dump,          /* Debugging end block.  */
+  NULL,                            /* Debugging start insn.  */
+  NULL,                            /* Debugging end insn.  */
   NULL,                            /* Incremental solution verify start.  */
   NULL,                            /* Incremental solution verify end.  */
-  NULL,                       /* Dependent problem.  */
+  NULL,                            /* Dependent problem.  */
   sizeof (struct df_word_lr_bb_info),/* Size of entry of block_info array.  */
   TV_DF_WORD_LR,                   /* Timing variable.  */
   false                            /* Reset blocks on dropping out of blocks_to_analyze.  */
@@ -3330,6 +3443,8 @@ static struct df_problem problem_NOTE =
   NULL,                       /* Debugging.  */
   NULL,                       /* Debugging start block.  */
   NULL,                       /* Debugging end block.  */
+  NULL,                       /* Debugging start insn.  */
+  NULL,                       /* Debugging end insn.  */
   NULL,                       /* Incremental solution verify start.  */
   NULL,                       /* Incremental solution verify end.  */
   &problem_LR,                /* Dependent problem.  */
@@ -4382,6 +4497,8 @@ static struct df_problem problem_MD =
   NULL,                       /* Debugging.  */
   df_md_top_dump,             /* Debugging start block.  */
   df_md_bottom_dump,          /* Debugging end block.  */
+  NULL,                       /* Debugging start insn.  */
+  NULL,                       /* Debugging end insn.  */
   NULL,			      /* Incremental solution verify start.  */
   NULL,			      /* Incremental solution verify end.  */
   NULL,                       /* Dependent problem.  */
diff --git a/gcc/df-scan.c b/gcc/df-scan.c
index 0fb1f640d9b..23da115f178 100644
--- a/gcc/df-scan.c
+++ b/gcc/df-scan.c
@@ -510,6 +510,8 @@ static struct df_problem problem_SCAN =
   df_scan_start_dump,         /* Debugging.  */
   df_scan_start_block,        /* Debugging start block.  */
   NULL,                       /* Debugging end block.  */
+  NULL,                       /* Debugging start insn.  */
+  NULL,                       /* Debugging end insn.  */
   NULL,                       /* Incremental solution verify start.  */
   NULL,                       /* Incremental solution verify end.  */
   NULL,                       /* Dependent problem.  */
diff --git a/gcc/df.h b/gcc/df.h
index e59ae126f2e..e7031d0bb2f 100644
--- a/gcc/df.h
+++ b/gcc/df.h
@@ -239,6 +239,9 @@ typedef void (*df_dump_problem_function) (FILE *);
 /* Function to dump top or bottom of basic block results to FILE.  */
 typedef void (*df_dump_bb_problem_function) (basic_block, FILE *);
 
+/* Function to dump before or after an insn to FILE.  */
+typedef void (*df_dump_insn_problem_function) (const_rtx, FILE *);
+
 /* Function to dump top or bottom of basic block results to FILE.  */
 typedef void (*df_verify_solution_start) (void);
 
@@ -268,6 +271,8 @@ struct df_problem {
   df_dump_problem_function dump_start_fun;
   df_dump_bb_problem_function dump_top_fun;
   df_dump_bb_problem_function dump_bottom_fun;
+  df_dump_insn_problem_function dump_insn_top_fun;
+  df_dump_insn_problem_function dump_insn_bottom_fun;
   df_verify_solution_start verify_start_fun;
   df_verify_solution_end verify_end_fun;
   struct df_problem *dependent_problem;
@@ -463,7 +468,12 @@ enum df_changeable_flags
   rescans to be batched.  */
   DF_DEFER_INSN_RESCAN    = 1 << 5,
 
-  DF_VERIFY_SCHEDULED     = 1 << 6
+  /* Compute the reaching defs problem as "live and reaching defs" (LR&RD).
+     A DEF is reaching and live at insn I if DEF reaches I and REGNO(DEF)
+     is in LR_IN of the basic block containing I.  */
+  DF_RD_PRUNE_DEAD_DEFS   = 1 << 6,
+
+  DF_VERIFY_SCHEDULED     = 1 << 7
 };
 
 /* Two of these structures are inline in df, one for the uses and one
@@ -773,7 +783,9 @@ struct df_scan_bb_info
 
 
 /* Reaching definitions.  All bitmaps are indexed by the id field of
-   the ref except sparse_kill which is indexed by regno.  */
+   the ref except sparse_kill which is indexed by regno.  For the
+   LR&RD problem, the kill set is not complete: It does not contain
+   DEFs killed because the set register has died in the LR set.  */
 struct df_rd_bb_info
 {
   /* Local sets to describe the basic blocks.   */
@@ -918,6 +930,8 @@ extern void df_dump_region (FILE *);
 extern void df_dump_start (FILE *);
 extern void df_dump_top (basic_block, FILE *);
 extern void df_dump_bottom (basic_block, FILE *);
+extern void df_dump_insn_top (const_rtx, FILE *);
+extern void df_dump_insn_bottom (const_rtx, FILE *);
 extern void df_refs_chain_dump (df_ref *, bool, FILE *);
 extern void df_regs_chain_dump (df_ref,  FILE *);
 extern void df_insn_debug (rtx, bool, FILE *);
diff --git a/gcc/loop-invariant.c b/gcc/loop-invariant.c
index 4cc1ea6f0cc..a420569fd43 100644
--- a/gcc/loop-invariant.c
+++ b/gcc/loop-invariant.c
@@ -659,20 +659,28 @@ find_defs (struct loop *loop, basic_block *body)
   for (i = 0; i < loop->num_nodes; i++)
     bitmap_set_bit (blocks, body[i]->index);
 
+  if (dump_file)
+    {
+      fprintf (dump_file,
+	       "*****starting processing of loop %d ******\n",
+	       loop->num);
+    }
+
   df_remove_problem (df_chain);
   df_process_deferred_rescans ();
   df_chain_add_problem (DF_UD_CHAIN);
   df_set_blocks (blocks);
+  df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
   df_analyze ();
+  check_invariant_table_size ();
 
   if (dump_file)
     {
       df_dump_region (dump_file);
-      fprintf (dump_file, "*****starting processing of loop  ******\n");
-      print_rtl_with_bb (dump_file, get_insns (), dump_flags);
-      fprintf (dump_file, "*****ending processing of loop  ******\n");
+      fprintf (dump_file,
+	       "*****ending processing of loop %d ******\n",
+	       loop->num);
     }
-  check_invariant_table_size ();
 
   BITMAP_FREE (blocks);
 }
diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c
index 145056e6d41..e5c72596a32 100644
--- a/gcc/loop-iv.c
+++ b/gcc/loop-iv.c
@@ -293,6 +293,7 @@ iv_analysis_loop_init (struct loop *loop)
      the problem back.  */
   df_remove_problem (df_chain);
   df_process_deferred_rescans ();
+  df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
   df_chain_add_problem (DF_UD_CHAIN);
   df_note_add_problem ();
   df_set_blocks (blocks);
diff --git a/gcc/ree.c b/gcc/ree.c
index 99ecd578097..167efa3fe1d 100644
--- a/gcc/ree.c
+++ b/gcc/ree.c
@@ -868,6 +868,7 @@ find_and_remove_re (void)
 
   /* Construct DU chain to get all reaching definitions of each
      extension instruction.  */
+  df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
   df_chain_add_problem (DF_UD_CHAIN + DF_DU_CHAIN);
   df_analyze ();
   df_set_flags (DF_DEFER_INSN_RESCAN);
diff --git a/gcc/web.c b/gcc/web.c
index 041f0f38633..f60b4b6ad84 100644
--- a/gcc/web.c
+++ b/gcc/web.c
@@ -313,6 +313,7 @@ web_main (void)
   rtx insn;
 
   df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
+  df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
   df_chain_add_problem (DF_UD_CHAIN);
   df_analyze ();
   df_set_flags (DF_DEFER_INSN_RESCAN);