2009-06-07 Paolo Bonzini <bonzini@gnu.org>

	PR rtl-optimization/26854
        * timevar.def: Remove TV_DF_RU, add TV_DF_MD.
        * df-problems.c (df_rd_add_problem): Fix comment.
        (df_md_set_bb_info, df_md_free_bb_info, df_md_alloc,
        df_md_simulate_artificial_defs_at_top,
        df_md_simulate_one_insn, df_md_bb_local_compute_process_def,
        df_md_bb_local_compute, df_md_local_compute, df_md_reset,
        df_md_transfer_function, df_md_init, df_md_confluence_0,
        df_md_confluence_n, df_md_free, df_md_top_dump, df_md_bottom_dump,
        problem_MD, df_md_add_problem): New.
        * df.h (DF_MD, DF_MD_BB_INFO, struct df_md_bb_info, df_md,
        df_md_get_bb_info): New.
        DF_LAST_PROBLEM_PLUS1): Adjust.

        * Makefile.in (fwprop.o): Include domwalk.h.
        * fwprop.c: Include domwalk.h.
        (reg_defs, reg_defs_stack): New.
        (bitmap_only_bit_between): Remove.
        (process_defs): New.
        (process_uses): Use reg_defs and local_md instead of
        bitmap_only_bit_between and local_rd.
        (single_def_use_enter_block): New, from build_single_def_use_links.
        (single_def_use_leave_block): New.
        (build_single_def_use_links): Remove code moved to
        single_def_use_enter_block, invoke domwalk.
        (use_killed_between): Adjust comment.



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

6 files changed, 658 insertions, 69 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index f7fdd4fa464..4134a2cf66e 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,32 @@
+2009-06-07  Paolo Bonzini  <bonzini@gnu.org>
+
+	PR rtl-optimization/26854
+        * timevar.def: Remove TV_DF_RU, add TV_DF_MD.
+        * df-problems.c (df_rd_add_problem): Fix comment.
+        (df_md_set_bb_info, df_md_free_bb_info, df_md_alloc,
+        df_md_simulate_artificial_defs_at_top,
+        df_md_simulate_one_insn, df_md_bb_local_compute_process_def,
+        df_md_bb_local_compute, df_md_local_compute, df_md_reset,
+        df_md_transfer_function, df_md_init, df_md_confluence_0,
+        df_md_confluence_n, df_md_free, df_md_top_dump, df_md_bottom_dump,
+        problem_MD, df_md_add_problem): New.
+        * df.h (DF_MD, DF_MD_BB_INFO, struct df_md_bb_info, df_md,
+        df_md_get_bb_info): New.
+        DF_LAST_PROBLEM_PLUS1): Adjust.
+
+        * Makefile.in (fwprop.o): Include domwalk.h.
+        * fwprop.c: Include domwalk.h.
+        (reg_defs, reg_defs_stack): New.
+        (bitmap_only_bit_between): Remove.
+        (process_defs): New.
+        (process_uses): Use reg_defs and local_md instead of
+        bitmap_only_bit_between and local_rd.
+        (single_def_use_enter_block): New, from build_single_def_use_links.
+        (single_def_use_leave_block): New.
+        (build_single_def_use_links): Remove code moved to
+        single_def_use_enter_block, invoke domwalk.
+        (use_killed_between): Adjust comment.
+
 2009-06-27  Paolo Bonzini  <bonzini@gnu.org>
 
 	* bitmap.h (bitmap_ior_and_into): New.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index d621d7fb52f..d8bbc681146 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -2761,7 +2761,7 @@ dse.o : dse.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
 fwprop.o : fwprop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    $(TOPLEV_H) insn-config.h $(RECOG_H) $(FLAGS_H) $(OBSTACK_H) $(BASIC_BLOCK_H) \
    output.h $(DF_H) alloc-pool.h $(TIMEVAR_H) $(TREE_PASS_H) $(TARGET_H) \
-   $(TM_P_H) $(CFGLOOP_H) $(EMIT_RTL_H)
+   $(TM_P_H) $(CFGLOOP_H) $(EMIT_RTL_H) domwalk.h
 web.o : web.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    hard-reg-set.h $(FLAGS_H) $(BASIC_BLOCK_H) $(FUNCTION_H) output.h $(TOPLEV_H) \
    $(DF_H) $(OBSTACK_H) $(TIMEVAR_H) $(TREE_PASS_H)
diff --git a/gcc/df-problems.c b/gcc/df-problems.c
index 84dc42a1361..5e56025ed8b 100644
--- a/gcc/df-problems.c
+++ b/gcc/df-problems.c
@@ -726,9 +726,8 @@ static struct df_problem problem_RD =
 
 
 
-/* Create a new DATAFLOW instance and add it to an existing instance
-   of DF.  The returned structure is what is used to get at the
-   solution.  */
+/* Create a new RD instance and add it to the existing instance
+   of DF.  */
 
 void
 df_rd_add_problem (void)
@@ -3952,3 +3951,448 @@ df_simulate_finalize_forwards (basic_block bb, bitmap live)
 	bitmap_clear_bit (live, DF_REF_REGNO (def));
     }
 }
+
+
+
+/*----------------------------------------------------------------------------
+   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.
+
+   The gen and kill sets for the problem are obvious.  Together they
+   include all defined registers in a basic block; the gen set includes
+   registers where a partial or conditional or may-clobber definition is
+   last in the BB, while the kill set includes registers with a complete
+   definition coming last.  However, the computation of the dataflow
+   itself is interesting.
+
+   The idea behind it comes from SSA form's iterated dominance frontier
+   criterion for inserting PHI functions.  Just like in that case, we can use
+   the dominance frontier to find places where multiple definitions meet;
+   a register X defined in a basic block BB1 has multiple definitions in
+   basic blocks in BB1's dominance frontier.
+
+   So, the in-set of a basic block BB2 is not just the union of the
+   out-sets of BB2's predecessors, but includes some more bits that come
+   from the basic blocks of whose dominance frontier BB2 is part (BB1 in
+   the previous paragraph).  I called this set the init-set of BB2.
+
+      (Note: I actually use the kill-set only to build the init-set.
+      gen bits are anyway propagated from BB1 to BB2 by dataflow).
+
+    For example, if you have
+
+       BB1 : r10 = 0
+             r11 = 0
+             if <...> goto BB2 else goto BB3;
+
+       BB2 : r10 = 1
+             r12 = 1
+             goto BB3;
+
+       BB3 :
+
+    you have BB3 in BB2's dominance frontier but not in BB1's, so that the
+    init-set of BB3 includes r10 and r12, but not r11.  Note that we do
+    not need to iterate the dominance frontier, because we do not insert
+    anything like PHI functions there!  Instead, dataflow will take care of
+    propagating the information to BB3's successors. 
+   ---------------------------------------------------------------------------*/
+
+/* Set basic block info.  */
+
+static void
+df_md_set_bb_info (unsigned int index, 
+                   struct df_md_bb_info *bb_info)
+{
+  gcc_assert (df_md);
+  gcc_assert (index < df_md->block_info_size);
+  df_md->block_info[index] = bb_info;
+}
+
+
+static void
+df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, 
+                    void *vbb_info)
+{
+  struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
+  if (bb_info)
+    {
+      BITMAP_FREE (bb_info->kill);
+      BITMAP_FREE (bb_info->gen);
+      BITMAP_FREE (bb_info->init);
+      BITMAP_FREE (bb_info->in);
+      BITMAP_FREE (bb_info->out);
+      pool_free (df_md->block_pool, bb_info);
+    }
+}
+
+
+/* Allocate or reset bitmaps for DF_MD. The solution bits are
+   not touched unless the block is new.  */
+
+static void 
+df_md_alloc (bitmap all_blocks)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+
+  if (!df_md->block_pool)
+    df_md->block_pool = create_alloc_pool ("df_md_block pool", 
+                                           sizeof (struct df_md_bb_info), 50);
+
+  df_grow_bb_info (df_md);
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+      if (bb_info)
+        { 
+          bitmap_clear (bb_info->init);
+          bitmap_clear (bb_info->gen);
+          bitmap_clear (bb_info->kill);
+          bitmap_clear (bb_info->in);
+          bitmap_clear (bb_info->out);
+        }
+      else
+        { 
+          bb_info = (struct df_md_bb_info *) pool_alloc (df_md->block_pool);
+          df_md_set_bb_info (bb_index, bb_info);
+          bb_info->init = BITMAP_ALLOC (NULL);
+          bb_info->gen = BITMAP_ALLOC (NULL);
+          bb_info->kill = BITMAP_ALLOC (NULL);
+          bb_info->in = BITMAP_ALLOC (NULL);
+          bb_info->out = BITMAP_ALLOC (NULL);
+        }
+    }
+
+  df_md->optional_p = true;
+}
+
+/* Add the effect of the top artificial defs of BB to the multiple definitions
+   bitmap LOCAL_MD.  */
+
+void
+df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
+{
+  int bb_index = bb->index;
+  df_ref *def_rec;
+  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+	{
+	  unsigned int dregno = DF_REF_REGNO (def);
+	  if (DF_REF_FLAGS (def)
+	      & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
+	    bitmap_set_bit (local_md, dregno);
+	  else
+	    bitmap_clear_bit (local_md, dregno);
+	}
+    }
+}
+
+
+/* Add the effect of the defs of INSN to the reaching definitions bitmap
+   LOCAL_MD.  */
+
+void
+df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn,
+                        bitmap local_md)
+{
+  unsigned uid = INSN_UID (insn);
+  df_ref *def_rec;
+
+  for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+    {
+      df_ref def = *def_rec;
+      unsigned int dregno = DF_REF_REGNO (def);
+      if ((!(df->changeable_flags & DF_NO_HARD_REGS))
+          || (dregno >= FIRST_PSEUDO_REGISTER))
+        {
+          if (DF_REF_FLAGS (def)
+	      & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
+           bitmap_set_bit (local_md, DF_REF_ID (def));
+         else
+           bitmap_clear_bit (local_md, DF_REF_ID (def));
+        }
+    }
+}
+
+static void
+df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info, 
+                                    df_ref *def_rec,
+                                    int top_flag)
+{
+  df_ref def;
+  bitmap_clear (seen_in_insn);
+
+  while ((def = *def_rec++) != NULL)
+    {
+      unsigned int dregno = DF_REF_REGNO (def);
+      if (((!(df->changeable_flags & DF_NO_HARD_REGS))
+	    || (dregno >= FIRST_PSEUDO_REGISTER))
+	  && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
+	{
+          if (!bitmap_bit_p (seen_in_insn, dregno))
+	    {
+	      if (DF_REF_FLAGS (def)
+	          & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
+	        {
+	          bitmap_set_bit (bb_info->gen, dregno);
+	          bitmap_clear_bit (bb_info->kill, dregno);
+	        }
+	      else
+	        {
+		  /* When we find a clobber and a regular def,
+		     make sure the regular def wins.  */
+	          bitmap_set_bit (seen_in_insn, dregno);
+	          bitmap_set_bit (bb_info->kill, dregno);
+	          bitmap_clear_bit (bb_info->gen, dregno);
+	        }
+	    }
+	}
+    }
+}
+
+
+/* Compute local multiple def info for basic block BB.  */
+
+static void
+df_md_bb_local_compute (unsigned int bb_index)
+{
+  basic_block bb = BASIC_BLOCK (bb_index);
+  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+  rtx insn;
+
+  /* Artificials are only hard regs.  */
+  if (!(df->changeable_flags & DF_NO_HARD_REGS))
+    df_md_bb_local_compute_process_def (bb_info, 
+                                        df_get_artificial_defs (bb_index),
+                                        DF_REF_AT_TOP);
+
+  FOR_BB_INSNS (bb, insn)
+    {
+      unsigned int uid = INSN_UID (insn);
+      if (!INSN_P (insn))
+        continue;
+
+      df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
+    }
+
+  if (!(df->changeable_flags & DF_NO_HARD_REGS))
+    df_md_bb_local_compute_process_def (bb_info, 
+                                        df_get_artificial_defs (bb_index),
+                                        0);
+}
+
+/* Compute local reaching def info for each basic block within BLOCKS.  */
+
+static void
+df_md_local_compute (bitmap all_blocks)
+{
+  unsigned int bb_index, df_bb_index;
+  bitmap_iterator bi1, bi2;
+  basic_block bb;
+  bitmap *frontiers;
+
+  df_set_seen ();
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
+    {
+      df_md_bb_local_compute (bb_index);
+    }
+  
+  df_unset_seen ();
+
+  frontiers = XNEWVEC (bitmap, last_basic_block);
+  FOR_ALL_BB (bb)
+    frontiers[bb->index] = BITMAP_ALLOC (NULL);
+
+  compute_dominance_frontiers (frontiers);
+
+  /* Add each basic block's kills to the nodes in the frontier of the BB.  */
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
+    {
+      bitmap kill = df_md_get_bb_info (bb_index)->kill;
+      EXECUTE_IF_SET_IN_BITMAP (frontiers[bb_index], 0, df_bb_index, bi2)
+	{
+	  if (bitmap_bit_p (all_blocks, df_bb_index))
+	    bitmap_ior_into (df_md_get_bb_info (df_bb_index)->init, kill);
+	}
+    }
+
+  FOR_ALL_BB (bb)
+    BITMAP_FREE (frontiers[bb->index]);
+  free (frontiers);
+}
+
+
+/* Reset the global solution for recalculation.  */
+
+static void 
+df_md_reset (bitmap all_blocks)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+      gcc_assert (bb_info);
+      bitmap_clear (bb_info->in);
+      bitmap_clear (bb_info->out);
+    }
+}
+
+static bool
+df_md_transfer_function (int 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);
+}
+
+/* Initialize the solution bit vectors for problem.  */
+
+static void 
+df_md_init (bitmap all_blocks)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
+      
+      bitmap_copy (bb_info->in, bb_info->init);
+      df_md_transfer_function (bb_index);
+    }
+}
+
+static void
+df_md_confluence_0 (basic_block bb)
+{
+  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
+  bitmap_copy (bb_info->in, bb_info->init);
+} 
+
+/* In of target gets or of out of source.  */
+
+static void
+df_md_confluence_n (edge e)
+{
+  bitmap op1 = df_md_get_bb_info (e->dest->index)->in;
+  bitmap op2 = df_md_get_bb_info (e->src->index)->out;
+
+  if (e->flags & EDGE_FAKE) 
+    return;
+
+  if (e->flags & EDGE_EH)
+    bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
+  else
+    bitmap_ior_into (op1, op2);
+}
+
+/* Free all storage associated with the problem.  */
+
+static void
+df_md_free (void)
+{
+  unsigned int i;
+  for (i = 0; i < df_md->block_info_size; i++)
+    {
+      struct df_md_bb_info *bb_info = df_md_get_bb_info (i);
+      if (bb_info)
+	{
+	  BITMAP_FREE (bb_info->kill);
+	  BITMAP_FREE (bb_info->gen);
+	  BITMAP_FREE (bb_info->init);
+	  BITMAP_FREE (bb_info->in);
+	  BITMAP_FREE (bb_info->out);
+	}
+    }
+
+  free_alloc_pool (df_md->block_pool);
+
+  df_md->block_info_size = 0;
+  free (df_md->block_info);
+  free (df_md);
+}
+
+
+/* Debugging info at top of bb.  */
+
+static void
+df_md_top_dump (basic_block bb, FILE *file)
+{
+  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
+  if (!bb_info || !bb_info->in)
+    return;
+      
+  fprintf (file, ";; md  in  \t");
+  df_print_regset (file, bb_info->in);
+  fprintf (file, ";; md  init  \t");
+  df_print_regset (file, bb_info->init);
+  fprintf (file, ";; md  gen \t");
+  df_print_regset (file, bb_info->gen);
+  fprintf (file, ";; md  kill \t");
+  df_print_regset (file, bb_info->kill);
+}
+
+/* Debugging info at bottom of bb.  */
+
+static void
+df_md_bottom_dump (basic_block bb, FILE *file)
+{
+  struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
+  if (!bb_info || !bb_info->out)
+    return;
+  
+  fprintf (file, ";; md  out \t");
+  df_print_regset (file, bb_info->out);
+}  
+
+static struct df_problem problem_MD =
+{
+  DF_MD,                      /* Problem id.  */
+  DF_FORWARD,                 /* Direction.  */
+  df_md_alloc,                /* Allocate the problem specific data.  */
+  df_md_reset,                /* Reset global information.  */
+  df_md_free_bb_info,         /* Free basic block info.  */
+  df_md_local_compute,        /* Local compute function.  */
+  df_md_init,                 /* Init the solution specific data.  */
+  df_worklist_dataflow,       /* Worklist solver.  */
+  df_md_confluence_0,         /* Confluence operator 0.  */ 
+  df_md_confluence_n,         /* Confluence operator n.  */ 
+  df_md_transfer_function,    /* Transfer function.  */
+  NULL,                       /* Finalize function.  */
+  df_md_free,                 /* Free all of the problem information.  */
+  df_md_free,                 /* Remove this problem from the stack of dataflow problems.  */
+  NULL,                       /* Debugging.  */
+  df_md_top_dump,             /* Debugging start block.  */
+  df_md_bottom_dump,          /* Debugging end block.  */
+  NULL,			      /* Incremental solution verify start.  */
+  NULL,			      /* Incremental solution verify end.  */
+  NULL,                       /* Dependent problem.  */
+  TV_DF_MD,                   /* Timing variable.  */ 
+  false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
+};
+
+/* Create a new MD instance and add it to the existing instance
+   of DF.  */
+
+void
+df_md_add_problem (void)
+{
+  df_add_problem (&problem_MD);
+}
+
+
+
diff --git a/gcc/df.h b/gcc/df.h
index f8084e022d0..f1c581248d3 100644
--- a/gcc/df.h
+++ b/gcc/df.h
@@ -52,8 +52,9 @@ union df_ref_d;
 #define DF_CHAIN   4      /* Def-Use and/or Use-Def Chains. */
 #define DF_BYTE_LR 5      /* Subreg tracking lr.  */
 #define DF_NOTE    6      /* REG_DEF and REG_UNUSED notes. */
+#define DF_MD      7      /* Multiple Definitions. */
 
-#define DF_LAST_PROBLEM_PLUS1 (DF_NOTE + 1)
+#define DF_LAST_PROBLEM_PLUS1 (DF_MD + 1)
 
 /* Dataflow direction.  */
 enum df_flow_dir
@@ -619,6 +620,7 @@ struct df
 #define DF_LR_BB_INFO(BB) (df_lr_get_bb_info((BB)->index))
 #define DF_LIVE_BB_INFO(BB) (df_live_get_bb_info((BB)->index))
 #define DF_BYTE_LR_BB_INFO(BB) (df_byte_lr_get_bb_info((BB)->index))
+#define DF_MD_BB_INFO(BB) (df_md_get_bb_info((BB)->index))
 
 /* Most transformations that wish to use live register analysis will
    use these macros.  This info is the and of the lr and live sets.  */
@@ -802,6 +804,22 @@ struct df_rd_bb_info
 };
 
 
+/* Multiple reaching definitions.  All bitmaps are referenced by the
+   register number.  */
+
+struct df_md_bb_info 
+{
+  /* Local sets to describe the basic blocks.  */
+  bitmap gen;    /* Partial/conditional definitions live at BB out.  */
+  bitmap kill;   /* Other definitions that are live at BB out.  */
+  bitmap init;   /* Definitions coming from dominance frontier edges. */
+
+  /* The results of the dataflow problem.  */
+  bitmap in;    /* Just before the block itself. */
+  bitmap out;   /* At the bottom of the block.  */
+};
+
+
 /* Live registers, a backwards dataflow problem.  All bitmaps are
    referenced by the register number.  */
 
@@ -862,6 +880,7 @@ extern struct df *df;
 #define df_chain   (df->problems_by_index[DF_CHAIN])
 #define df_byte_lr (df->problems_by_index[DF_BYTE_LR])
 #define df_note    (df->problems_by_index[DF_NOTE])
+#define df_md      (df->problems_by_index[DF_MD])
 
 /* This symbol turns on checking that each modification of the cfg has
   been identified to the appropriate df routines.  It is not part of
@@ -955,6 +974,9 @@ extern void df_byte_lr_simulate_uses (rtx, bitmap);
 extern void df_byte_lr_simulate_artificial_refs_at_top (basic_block, bitmap);
 extern void df_byte_lr_simulate_artificial_refs_at_end (basic_block, bitmap);
 extern void df_note_add_problem (void);
+extern void df_md_add_problem (void);
+extern void df_md_simulate_artificial_defs_at_top (basic_block, bitmap);
+extern void df_md_simulate_one_insn (basic_block, rtx, bitmap);
 extern void df_simulate_find_defs (rtx, bitmap);
 extern void df_simulate_defs (rtx, bitmap);
 extern void df_simulate_uses (rtx, bitmap);
@@ -1034,6 +1056,15 @@ df_lr_get_bb_info (unsigned int index)
     return NULL;
 }
 
+static inline struct df_md_bb_info *
+df_md_get_bb_info (unsigned int index)
+{
+  if (index < df_md->block_info_size)
+    return (struct df_md_bb_info *) df_md->block_info[index];
+  else
+    return NULL;
+}
+
 static inline struct df_live_bb_info *
 df_live_get_bb_info (unsigned int index)
 {
diff --git a/gcc/fwprop.c b/gcc/fwprop.c
index 58cc9b0b552..df4edf93574 100644
--- a/gcc/fwprop.c
+++ b/gcc/fwprop.c
@@ -38,6 +38,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "target.h"
 #include "cfgloop.h"
 #include "tree-pass.h"
+#include "domwalk.h"
 
 
 /* This pass does simple forward propagation and simplification when an
@@ -100,7 +101,17 @@ along with GCC; see the file COPYING3.  If not see
      (set (reg:QI 121) (subreg:QI (reg:SI 119) 0))
      (set (reg:SI 122) (plus:SI (reg:SI 118) (reg:SI 119)))
 
-   where the first two insns are now dead.  */
+   where the first two insns are now dead.
+
+   We used to use reaching definitions to find which uses have a
+   single reaching definition (sounds obvious...), but this is too
+   complex a problem in nasty testcases like PR33928.  Now we use the
+   multiple definitions problem in df-problems.c.  The similarity
+   between that problem and SSA form creation is taken further, in
+   that fwprop does a dominator walk to create its chains; however,
+   instead of creating a PHI function where multiple definitions meet
+   I just punt and record only singleton use-def chains, which is
+   all that is needed by fwprop.  */
 
 
 static int num_changes;
@@ -108,6 +119,8 @@ 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;
 
 
 /* Return the only def in USE's use-def chain, or NULL if there is
@@ -120,96 +133,168 @@ get_def_for_use (df_ref use)
 }
 
 
-/* Return the only bit between FIRST and LAST that is set in B,
-   or -1 if there are zero or more than one such bits.  */
+/* Update the reg_defs vector with non-partial definitions in DEF_REC.
+   TOP_FLAG says which artificials uses should be used, when DEF_REC
+   is an artificial def vector.  LOCAL_MD is modified as after a
+   df_md_simulate_* function; we do more or less the same processing
+   done there, so we do not use those functions.  */
+
+#define DF_MD_GEN_FLAGS \
+	(DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)
 
-static inline int
-bitmap_only_bit_between (const_bitmap b, unsigned first, unsigned last)
+static void
+process_defs (bitmap local_md, df_ref *def_rec, int top_flag)
 {
-  bitmap_iterator bi;
-  unsigned bit, bit2;
+  df_ref def;
+  while ((def = *def_rec++) != NULL)
+    {
+      df_ref curr_def = VEC_index (df_ref, reg_defs, DF_REF_REGNO (def));
+      unsigned int dregno;
 
-  if (last < first)
-    return -1;
+      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag)
+	continue;
 
-  bmp_iter_set_init (&bi, b, first, &bit);
-  if (bmp_iter_set (&bi, &bit) && bit <= last)
-    {
-      bit2 = bit;
-      bmp_iter_next (&bi, &bit2);
-      if (!bmp_iter_set (&bi, &bit2) || bit2 > last)
-        return bit;
+      dregno = DF_REF_REGNO (def);
+      if (curr_def)
+	VEC_safe_push (df_ref, heap, reg_defs_stack, curr_def);
+      else
+	{
+	  /* Do not store anything if "transitioning" from NULL to NULL.  But
+             otherwise, push a special entry on the stack to tell the
+	     leave_block callback that the entry in reg_defs was NULL.  */
+	  if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
+	    ;
+	  else
+	    VEC_safe_push (df_ref, heap, reg_defs_stack, def);
+	}
+
+      if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
+	{
+	  bitmap_set_bit (local_md, dregno);
+	  VEC_replace (df_ref, reg_defs, dregno, NULL);
+	}
+      else
+	{
+	  bitmap_clear_bit (local_md, dregno);
+	  VEC_replace (df_ref, reg_defs, dregno, def);
+	}
     }
-  return -1;
 }
 
 
 /* Fill the use_def_ref vector with values for the uses in USE_REC,
-   taking reaching definitions info from LOCAL_RD.  TOP_FLAG says
-   which artificials uses should be used, when USE_REC is an
-   artificial use vector.  */
+   taking reaching definitions info from LOCAL_MD and REG_DEFS.
+   TOP_FLAG says which artificials uses should be used, when USE_REC
+   is an artificial use vector.  */
 
 static void
-process_uses (bitmap local_rd, df_ref *use_rec, int top_flag)
+process_uses (bitmap local_md, df_ref *use_rec, int top_flag)
 {
   df_ref use;
   while ((use = *use_rec++) != NULL)
-    if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
+    if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag)
       {
-	unsigned int uregno = DF_REF_REGNO (use);
-	unsigned int first = DF_DEFS_BEGIN (uregno);
-	unsigned int last = first + DF_DEFS_COUNT (uregno) - 1;
-	int defno = bitmap_only_bit_between (local_rd, first, last);
-	df_ref def = (defno == -1) ? NULL : DF_DEFS_GET (defno);
+        unsigned int uregno = DF_REF_REGNO (use);
+        if (VEC_index (df_ref, reg_defs, uregno)
+	    && !bitmap_bit_p (local_md, uregno))
+	  VEC_replace (df_ref, use_def_ref, DF_REF_ID (use),
+		       VEC_index (df_ref, reg_defs, uregno));
+      }
+}
+
+
+static void
+single_def_use_enter_block (struct dom_walk_data *walk_data, 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);
+  rtx insn;
+
+  bitmap_copy (local_md, bb_info->in);
 
-	VEC_replace (df_ref, use_def_ref, DF_REF_ID (use), def);
+  /* 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);
+
+  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 (local_md, df_get_artificial_uses (bb_index), 0);
+  process_defs (local_md, df_get_artificial_defs (bb_index), 0);
+}
+
+/* Pop the definitions created in this basic block when leaving its
+   dominated parts.  */
+
+static void
+single_def_use_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+			    basic_block bb ATTRIBUTE_UNUSED)
+{
+  df_ref saved_def;
+  while ((saved_def = VEC_pop (df_ref, reg_defs_stack)) != NULL)
+    {
+      unsigned int dregno = DF_REF_REGNO (saved_def);
+
+      /* See also process_defs.  */
+      if (saved_def == VEC_index (df_ref, reg_defs, dregno))
+	VEC_replace (df_ref, reg_defs, dregno, NULL);
+      else
+	VEC_replace (df_ref, reg_defs, dregno, saved_def);
+    }
 }
 
 
-/* Do dataflow analysis and use reaching definitions to build
-   a vector holding the reaching definitions of uses that have a
-   single RD.  */
+/* Build a vector holding the reaching definitions of uses reached by a
+   single dominating definition.  */
 
 static void
 build_single_def_use_links (void)
 {
-  basic_block bb;
-  bitmap local_rd = BITMAP_ALLOC (NULL);
+  struct dom_walk_data walk_data;
+  bitmap local_md;
 
-  /* We use reaching definitions to compute our restricted use-def chains.  */
+  /* We use the multiple definitions problem to compute our restricted
+     use-def chains.  */
   df_set_flags (DF_EQ_NOTES);
-  df_rd_add_problem ();
+  df_md_add_problem ();
   df_analyze ();
   df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
 
   use_def_ref = VEC_alloc (df_ref, heap, DF_USES_TABLE_SIZE ());
-  VEC_safe_grow (df_ref, heap, use_def_ref, DF_USES_TABLE_SIZE ());
+  VEC_safe_grow_cleared (df_ref, heap, use_def_ref, DF_USES_TABLE_SIZE ());
 
-  FOR_EACH_BB (bb)
-    {
-      int bb_index = bb->index;
-      struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
-      rtx insn;
-
-      bitmap_copy (local_rd, bb_info->in);
-      process_uses (local_rd, df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
-
-      df_rd_simulate_artificial_defs_at_top (bb, local_rd);
-      FOR_BB_INSNS (bb, insn)
-        if (INSN_P (insn))
-          {
-            unsigned int uid = INSN_UID (insn);
-            process_uses (local_rd, DF_INSN_UID_USES (uid), 0);
-            process_uses (local_rd, DF_INSN_UID_EQ_USES (uid), 0);
-            df_rd_simulate_one_insn (bb, insn, local_rd);
-	  }
+  reg_defs = VEC_alloc (df_ref, heap, max_reg_num ());
+  VEC_safe_grow_cleared (df_ref, heap, reg_defs, max_reg_num ());
 
-      process_uses (local_rd, df_get_artificial_uses (bb_index), 0);
-    }
+  reg_defs_stack = VEC_alloc (df_ref, heap, n_basic_blocks * 10);
+  local_md = BITMAP_ALLOC (NULL);
+
+  /* Walk the dominator tree looking for single reaching definitions
+     dominating the uses.  This is similar to how SSA form is built.  */
+  walk_data.dom_direction = CDI_DOMINATORS;
+  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;
 
-  BITMAP_FREE (local_rd);
+  init_walk_dominator_tree (&walk_data);
+  walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+  fini_walk_dominator_tree (&walk_data);
+
+  BITMAP_FREE (local_md);
+  VEC_free (df_ref, heap, reg_defs);
+  VEC_free (df_ref, heap, reg_defs_stack);
 }
+
 
 /* Do not try to replace constant addresses or addresses of local and
    argument slots.  These MEM expressions are made only once and inserted
@@ -629,12 +714,12 @@ use_killed_between (df_ref use, rtx def_insn, rtx target_insn)
   int regno;
   df_ref def;
 
-  /* In some obscure situations we can have a def reaching a use
-     that is _before_ the def.  In other words the def does not
-     dominate the use even though the use and def are in the same
-     basic block.  This can happen when a register may be used
-     uninitialized in a loop.  In such cases, we must assume that
-     DEF is not available.  */
+  /* We used to have a def reaching a use that is _before_ the def,
+     with the def not dominating the use even though the use and def
+     are in the same basic block, when a register may be used
+     uninitialized in a loop.  This should not happen anymore since
+     we do not use reaching definitions, but still we test for such
+     cases and assume that DEF is not available.  */
   if (def_bb == target_bb
       ? DF_INSN_LUID (def_insn) >= DF_INSN_LUID (target_insn)
       : !dominated_by_p (CDI_DOMINATORS, target_bb, def_bb))
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 9d727639db6..938447f03b1 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -58,7 +58,7 @@ DEFTIMEVAR (TV_LIFE_UPDATE	     , "life info update")
 
 /* Time spent in dataflow problems.  */
 DEFTIMEVAR (TV_DF_SCAN		     , "df scan insns")
-DEFTIMEVAR (TV_DF_RU		     , "df reaching uses")
+DEFTIMEVAR (TV_DF_MD		     , "df multiple defs")
 DEFTIMEVAR (TV_DF_RD		     , "df reaching defs")
 DEFTIMEVAR (TV_DF_LR		     , "df live regs")
 DEFTIMEVAR (TV_DF_LIVE		     , "df live&initialized regs")