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

1 files changed, 148 insertions, 63 deletions

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))