* df-problems.c (df_rd_confluence_n, df_lr_confluence_n, df_live_confluence_n,

	df_byte_lr_confluence_n, df_md_confluence_n): Return true if something changed.
	* df.h (df_confluence_function_n): Return bool.
	* df-core.c (df_worklist_propagate_forward, df_worklist_propagate_backward):
	track changes and ages.
	(df_worklist_dataflow_doublequeue): Use bitmap iterator for main walk;
	track ages.
	* dse.c (dse_confluence_n): Return always true.


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

5 files changed, 105 insertions, 51 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index b3aae11cf09..fdd72da1c60 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,4 +1,15 @@
-2010-06-22  Uros Bizjak  <ubizjak@gmail.com>
+2010-06-22  Jan Hubicka  <jh@suse.cz>
+
+	* df-problems.c (df_rd_confluence_n, df_lr_confluence_n, df_live_confluence_n,
+	df_byte_lr_confluence_n, df_md_confluence_n): Return true if something changed.
+	* df.h (df_confluence_function_n): Return bool.
+	* df-core.c (df_worklist_propagate_forward, df_worklist_propagate_backward):
+	track changes and ages.
+	(df_worklist_dataflow_doublequeue): Use bitmap iterator for main walk;
+	track ages.
+	* dse.c (dse_confluence_n): Return always true.
+
+2010-06-22  Jan Hubicka  <jh@suse.cz>
 
 	* bitmap.c (bitmap_clear_bit): Micro optimize.
 
diff --git a/gcc/df-core.c b/gcc/df-core.c
index 5ffee9c8b99..814eaf41ccf 100644
--- a/gcc/df-core.c
+++ b/gcc/df-core.c
@@ -858,28 +858,35 @@ struct rtl_opt_pass pass_df_finish =
    and set bits on for successors in PENDING
    if the out set of the dataflow has changed. */
 
-static void
+static bool
 df_worklist_propagate_forward (struct dataflow *dataflow,
                                unsigned bb_index,
                                unsigned *bbindex_to_postorder,
                                bitmap pending,
-                               sbitmap considered)
+                               sbitmap considered,
+			       size_t age)
 {
   edge e;
   edge_iterator ei;
   basic_block bb = BASIC_BLOCK (bb_index);
+  bool changed = !age;
 
   /*  Calculate <conf_op> of incoming edges.  */
   if (EDGE_COUNT (bb->preds) > 0)
     FOR_EACH_EDGE (e, ei, bb->preds)
       {
-        if (TEST_BIT (considered, e->src->index))
-          dataflow->problem->con_fun_n (e);
+        if ((age <= (size_t)e->src->aux)
+	     && TEST_BIT (considered, e->src->index))
+          changed |= dataflow->problem->con_fun_n (e);
       }
   else if (dataflow->problem->con_fun_0)
-    dataflow->problem->con_fun_0 (bb);
+    {
+      dataflow->problem->con_fun_0 (bb);
+      changed = true;
+    }
 
-  if (dataflow->problem->trans_fun (bb_index))
+  if (changed
+      && dataflow->problem->trans_fun (bb_index))
     {
       /* The out set of this block has changed.
          Propagate to the outgoing blocks.  */
@@ -890,35 +897,44 @@ df_worklist_propagate_forward (struct dataflow *dataflow,
           if (TEST_BIT (considered, ob_index))
             bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
         }
+      return true;
     }
+  return false;
 }
 
 
 /* Helper function for df_worklist_dataflow.
    Propagate the dataflow backward.  */
 
-static void
+static bool
 df_worklist_propagate_backward (struct dataflow *dataflow,
                                 unsigned bb_index,
                                 unsigned *bbindex_to_postorder,
                                 bitmap pending,
-                                sbitmap considered)
+                                sbitmap considered,
+			        size_t age)
 {
   edge e;
   edge_iterator ei;
   basic_block bb = BASIC_BLOCK (bb_index);
+  bool changed = !age;
 
   /*  Calculate <conf_op> of incoming edges.  */
   if (EDGE_COUNT (bb->succs) > 0)
     FOR_EACH_EDGE (e, ei, bb->succs)
       {
-        if (TEST_BIT (considered, e->dest->index))
-          dataflow->problem->con_fun_n (e);
+        if ((age <= (size_t)e->dest->aux)
+	     && TEST_BIT (considered, e->dest->index))
+          changed |= dataflow->problem->con_fun_n (e);
       }
   else if (dataflow->problem->con_fun_0)
-    dataflow->problem->con_fun_0 (bb);
+    {
+      dataflow->problem->con_fun_0 (bb);
+      changed = true;
+    }
 
-  if (dataflow->problem->trans_fun (bb_index))
+  if (changed
+      && dataflow->problem->trans_fun (bb_index))
     {
       /* The out set of this block has changed.
          Propagate to the outgoing blocks.  */
@@ -929,10 +945,13 @@ df_worklist_propagate_backward (struct dataflow *dataflow,
           if (TEST_BIT (considered, ob_index))
             bitmap_set_bit (pending, bbindex_to_postorder[ob_index]);
         }
+      return true;
     }
+  return false;
 }
 
-
+DEF_VEC_I(size_t);
+DEF_VEC_ALLOC_I(size_t,heap);
 
 /* This will free "pending". */
 
@@ -941,46 +960,65 @@ df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
 			  	  bitmap pending,
                                   sbitmap considered,
                                   int *blocks_in_postorder,
-				  unsigned *bbindex_to_postorder)
+				  unsigned *bbindex_to_postorder,
+				  int n_blocks)
 {
   enum df_flow_dir dir = dataflow->problem->dir;
   int dcount = 0;
   bitmap worklist = BITMAP_ALLOC (&df_bitmap_obstack);
+  size_t age = 0;
+  bool changed;
+  VEC(size_t, heap) *last_age = NULL;
+  size_t prev_age;
+  basic_block bb;
+  int i;
+
+  VEC_safe_grow_cleared (size_t, heap, last_age, n_blocks);
 
   /* Double-queueing. Worklist is for the current iteration,
      and pending is for the next. */
   while (!bitmap_empty_p (pending))
     {
+      bitmap_iterator bi;
+      unsigned int index;
+
       /* Swap pending and worklist. */
       bitmap temp = worklist;
       worklist = pending;
       pending = temp;
 
-      do
+      EXECUTE_IF_SET_IN_BITMAP (worklist, 0, index, bi)
 	{
-	  int index;
 	  unsigned bb_index;
 	  dcount++;
 
-	  index = bitmap_first_set_bit (worklist);
-	  bitmap_clear_bit (worklist, index);
-
 	  bb_index = blocks_in_postorder[index];
-
+	  bb = BASIC_BLOCK (bb_index);
+	  prev_age = VEC_index (size_t, last_age, index);
 	  if (dir == DF_FORWARD)
-	    df_worklist_propagate_forward (dataflow, bb_index,
-					   bbindex_to_postorder,
-					   pending, considered);
+	    changed = df_worklist_propagate_forward (dataflow, bb_index,
+						     bbindex_to_postorder,
+						     pending, considered,
+						     prev_age);
 	  else
-	    df_worklist_propagate_backward (dataflow, bb_index,
-					    bbindex_to_postorder,
-					    pending, considered);
+	    changed = df_worklist_propagate_backward (dataflow, bb_index,
+						      bbindex_to_postorder,
+						      pending, considered,
+						      prev_age);
+	  age++;
+	  if (changed)
+	    bb->aux = (void *)age;
+	  VEC_replace (size_t, last_age, index, age);
+	  age++;
 	}
-      while (!bitmap_empty_p (worklist));
+      bitmap_clear (worklist);
     }
+  for (i = 0; i < n_blocks; i++)
+    BASIC_BLOCK (blocks_in_postorder[i])->aux = NULL;
 
   BITMAP_FREE (worklist);
   BITMAP_FREE (pending);
+  VEC_free (size_t, heap, last_age);
 
   /* Dump statistics. */
   if (dump_file)
@@ -1044,8 +1082,8 @@ df_worklist_dataflow (struct dataflow *dataflow,
   /* Solve it.  */
   df_worklist_dataflow_doublequeue (dataflow, pending, considered,
 				    blocks_in_postorder,
-				    bbindex_to_postorder);
-
+				    bbindex_to_postorder,
+				    n_blocks);
   sbitmap_free (considered);
   free (bbindex_to_postorder);
 }
diff --git a/gcc/df-problems.c b/gcc/df-problems.c
index f9d5f6bd848..431027a41e0 100644
--- a/gcc/df-problems.c
+++ b/gcc/df-problems.c
@@ -479,14 +479,15 @@ df_rd_init_solution (bitmap all_blocks)
 
 /* In of target gets or of out of source.  */
 
-static void
+static bool
 df_rd_confluence_n (edge e)
 {
   bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in;
   bitmap op2 = &df_rd_get_bb_info (e->src->index)->out;
+  bool changed = false;
 
   if (e->flags & EDGE_FAKE)
-    return;
+    return false;
 
   if (e->flags & EDGE_EH)
     {
@@ -508,11 +509,12 @@ df_rd_confluence_n (edge e)
  			      DF_DEFS_BEGIN (regno),
  			      DF_DEFS_COUNT (regno));
 	}
-      bitmap_ior_into (op1, &tmp);
+      changed |= bitmap_ior_into (op1, &tmp);
       bitmap_clear (&tmp);
+      return changed;
     }
   else
-    bitmap_ior_into (op1, op2);
+    return bitmap_ior_into (op1, op2);
 }
 
 
@@ -966,21 +968,22 @@ df_lr_confluence_0 (basic_block bb)
 
 /* Confluence function that ignores fake edges.  */
 
-static void
+static bool
 df_lr_confluence_n (edge e)
 {
   bitmap op1 = &df_lr_get_bb_info (e->src->index)->out;
   bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in;
+  bool changed = false;
 
   /* Call-clobbered registers die across exception and call edges.  */
   /* ??? Abnormal call edges ignored for the moment, as this gets
      confused by sibling call edges, which crashes reg-stack.  */
   if (e->flags & EDGE_EH)
-    bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
+    changed = bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
   else
-    bitmap_ior_into (op1, op2);
+    changed = bitmap_ior_into (op1, op2);
 
-  bitmap_ior_into (op1, &df->hardware_regs_used);
+  return bitmap_ior_into (op1, &df->hardware_regs_used) || changed;
 }
 
 
@@ -1503,16 +1506,16 @@ df_live_init (bitmap all_blocks)
 
 /* Forward confluence function that ignores fake edges.  */
 
-static void
+static bool
 df_live_confluence_n (edge e)
 {
   bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
   bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
 
   if (e->flags & EDGE_FAKE)
-    return;
+    return false;
 
-  bitmap_ior_into (op1, op2);
+  return bitmap_ior_into (op1, op2);
 }
 
 
@@ -2710,23 +2713,24 @@ df_byte_lr_confluence_0 (basic_block bb)
 
 /* Confluence function that ignores fake edges.  */
 
-static void
+static bool
 df_byte_lr_confluence_n (edge e)
 {
   struct df_byte_lr_problem_data *problem_data
     = (struct df_byte_lr_problem_data *)df_byte_lr->problem_data;
   bitmap op1 = &df_byte_lr_get_bb_info (e->src->index)->out;
   bitmap op2 = &df_byte_lr_get_bb_info (e->dest->index)->in;
+  bool changed = false;
 
   /* Call-clobbered registers die across exception and call edges.  */
   /* ??? Abnormal call edges ignored for the moment, as this gets
      confused by sibling call edges, which crashes reg-stack.  */
   if (e->flags & EDGE_EH)
-    bitmap_ior_and_compl_into (op1, op2, &problem_data->invalidated_by_call);
+    changed = bitmap_ior_and_compl_into (op1, op2, &problem_data->invalidated_by_call);
   else
-    bitmap_ior_into (op1, op2);
+    changed = bitmap_ior_into (op1, op2);
 
-  bitmap_ior_into (op1, &problem_data->hardware_regs_used);
+  return bitmap_ior_into (op1, &problem_data->hardware_regs_used) || changed;
 }
 
 
@@ -4426,19 +4430,19 @@ df_md_confluence_0 (basic_block bb)
 
 /* In of target gets or of out of source.  */
 
-static void
+static bool
 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;
+    return false;
 
   if (e->flags & EDGE_EH)
-    bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
+    return bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
   else
-    bitmap_ior_into (op1, op2);
+    return bitmap_ior_into (op1, op2);
 }
 
 /* Free all storage associated with the problem.  */
diff --git a/gcc/df.h b/gcc/df.h
index 060b52f6076..b778c0f060c 100644
--- a/gcc/df.h
+++ b/gcc/df.h
@@ -223,7 +223,7 @@ typedef void (*df_dataflow_function) (struct dataflow *, bitmap, int *, int);
 typedef void (*df_confluence_function_0) (basic_block);
 
 /* Confluence operator for blocks with 1 or more out (or in) edges.  */
-typedef void (*df_confluence_function_n) (edge);
+typedef bool (*df_confluence_function_n) (edge);
 
 /* Transfer function for blocks.  */
 typedef bool (*df_transfer_function) (int);
diff --git a/gcc/dse.c b/gcc/dse.c
index 2be8a942c75..5cb467c934d 100644
--- a/gcc/dse.c
+++ b/gcc/dse.c
@@ -3396,7 +3396,7 @@ dse_confluence_0 (basic_block bb)
    out set of the src of E.  If the various in or out sets are not
    there, that means they are all ones.  */
 
-static void
+static bool
 dse_confluence_n (edge e)
 {
   bb_info_t src_info = bb_table[e->src->index];
@@ -3412,6 +3412,7 @@ dse_confluence_n (edge e)
 	  bitmap_copy (src_info->out, dest_info->in);
 	}
     }
+  return true;
 }