re PR rtl-optimization/38518 (Excessive compile time with -O3)

2014-01-17  Richard Biener  <rguenther@suse.de>

	PR rtl-optimization/38518
	* df.h (df_analyze_loop): Declare.
	* df-core.c: Include cfgloop.h.
	(df_analyze_1): Split out main part of df_analyze.
	(df_analyze): Adjust.
	(loop_inverted_post_order_compute): New function.
	(loop_post_order_compute): Likewise.
	(df_analyze_loop): New function avoiding whole-function
	postorder computes.
	* loop-invariant.c (find_defs): Use df_analyze_loop.
	(find_invariants): Adjust.
	* loop-iv.c (iv_analysis_loop_init): Use df_analyze_loop.

From-SVN: r206702

5 files changed, 223 insertions, 65 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 3037ef64b94..76a37e9b368 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,18 @@
+2014-01-17  Richard Biener  <rguenther@suse.de>
+
+	PR rtl-optimization/38518
+	* df.h (df_analyze_loop): Declare.
+	* df-core.c: Include cfgloop.h.
+	(df_analyze_1): Split out main part of df_analyze.
+	(df_analyze): Adjust.
+	(loop_inverted_post_order_compute): New function.
+	(loop_post_order_compute): Likewise.
+	(df_analyze_loop): New function avoiding whole-function
+	postorder computes.
+	* loop-invariant.c (find_defs): Use df_analyze_loop.
+	(find_invariants): Adjust.
+	* loop-iv.c (iv_analysis_loop_init): Use df_analyze_loop.
+
 2014-01-17  Zhenqiang Chen  <zhenqiang.chen@arm.com>
 
 	* config/arm/arm.c (arm_v7m_tune): Set max_insns_skipped to 2.
diff --git a/gcc/df-core.c b/gcc/df-core.c
index a3085c174ec..edb3b25727a 100644
--- a/gcc/df-core.c
+++ b/gcc/df-core.c
@@ -393,6 +393,7 @@ are write-only operations.
 #include "df.h"
 #include "tree-pass.h"
 #include "params.h"
+#include "cfgloop.h"
 
 static void *df_get_bb_info (struct dataflow *, unsigned int);
 static void df_set_bb_info (struct dataflow *, unsigned int, void *);
@@ -1225,23 +1226,13 @@ df_analyze_problem (struct dataflow *dflow,
 }
 
 
-/* Analyze dataflow info for the basic blocks specified by the bitmap
-   BLOCKS, or for the whole CFG if BLOCKS is zero.  */
+/* Analyze dataflow info.  */
 
-void
-df_analyze (void)
+static void
+df_analyze_1 (void)
 {
-  bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
-  bool everything;
   int i;
 
-  free (df->postorder);
-  free (df->postorder_inverted);
-  df->postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
-  df->postorder_inverted = XNEWVEC (int, last_basic_block_for_fn (cfun));
-  df->n_blocks = post_order_compute (df->postorder, true, true);
-  df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
-
   /* These should be the same.  */
   gcc_assert (df->n_blocks == df->n_blocks_inverted);
 
@@ -1258,6 +1249,51 @@ df_analyze (void)
 #endif
     df_verify ();
 
+  /* Skip over the DF_SCAN problem. */
+  for (i = 1; i < df->num_problems_defined; i++)
+    {
+      struct dataflow *dflow = df->problems_in_order[i];
+      if (dflow->solutions_dirty)
+        {
+          if (dflow->problem->dir == DF_FORWARD)
+            df_analyze_problem (dflow,
+                                df->blocks_to_analyze,
+                                df->postorder_inverted,
+                                df->n_blocks_inverted);
+          else
+            df_analyze_problem (dflow,
+                                df->blocks_to_analyze,
+                                df->postorder,
+                                df->n_blocks);
+        }
+    }
+
+  if (!df->analyze_subset)
+    {
+      BITMAP_FREE (df->blocks_to_analyze);
+      df->blocks_to_analyze = NULL;
+    }
+
+#ifdef DF_DEBUG_CFG
+  df_set_clean_cfg ();
+#endif
+}
+
+/* Analyze dataflow info.  */
+
+void
+df_analyze (void)
+{
+  bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
+  int i;
+
+  free (df->postorder);
+  free (df->postorder_inverted);
+  df->postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
+  df->postorder_inverted = XNEWVEC (int, last_basic_block_for_fn (cfun));
+  df->n_blocks = post_order_compute (df->postorder, true, true);
+  df->n_blocks_inverted = inverted_post_order_compute (df->postorder_inverted);
+
   for (i = 0; i < df->n_blocks; i++)
     bitmap_set_bit (current_all_blocks, df->postorder[i]);
 
@@ -1272,50 +1308,177 @@ df_analyze (void)
      sets.  */
   if (df->analyze_subset)
     {
-      everything = false;
       bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
       df->n_blocks = df_prune_to_subcfg (df->postorder,
 					 df->n_blocks, df->blocks_to_analyze);
       df->n_blocks_inverted = df_prune_to_subcfg (df->postorder_inverted,
-			                          df->n_blocks_inverted,
-                                                  df->blocks_to_analyze);
+						  df->n_blocks_inverted,
+						  df->blocks_to_analyze);
       BITMAP_FREE (current_all_blocks);
     }
   else
     {
-      everything = true;
       df->blocks_to_analyze = current_all_blocks;
       current_all_blocks = NULL;
     }
 
-  /* Skip over the DF_SCAN problem. */
-  for (i = 1; i < df->num_problems_defined; i++)
+  df_analyze_1 ();
+}
+
+/* Compute the reverse top sort order of the sub-CFG specified by LOOP.
+   Returns the number of blocks which is always loop->num_nodes.  */
+
+static int
+loop_post_order_compute (int *post_order, struct loop *loop)
+{
+  edge_iterator *stack;
+  int sp;
+  int post_order_num = 0;
+  bitmap visited;
+
+  /* Allocate stack for back-tracking up CFG.  */
+  stack = XNEWVEC (edge_iterator, loop->num_nodes + 1);
+  sp = 0;
+
+  /* Allocate bitmap to track nodes that have been visited.  */
+  visited = BITMAP_ALLOC (NULL);
+
+  /* Push the first edge on to the stack.  */
+  stack[sp++] = ei_start (loop_preheader_edge (loop)->src->succs);
+
+  while (sp)
     {
-      struct dataflow *dflow = df->problems_in_order[i];
-      if (dflow->solutions_dirty)
-        {
-          if (dflow->problem->dir == DF_FORWARD)
-            df_analyze_problem (dflow,
-                                df->blocks_to_analyze,
-                                df->postorder_inverted,
-                                df->n_blocks_inverted);
-          else
-            df_analyze_problem (dflow,
-                                df->blocks_to_analyze,
-                                df->postorder,
-                                df->n_blocks);
-        }
+      edge_iterator ei;
+      basic_block src;
+      basic_block dest;
+
+      /* Look at the edge on the top of the stack.  */
+      ei = stack[sp - 1];
+      src = ei_edge (ei)->src;
+      dest = ei_edge (ei)->dest;
+
+      /* Check if the edge destination has been visited yet and mark it
+         if not so.  */
+      if (flow_bb_inside_loop_p (loop, dest)
+	  && bitmap_set_bit (visited, dest->index))
+	{
+	  if (EDGE_COUNT (dest->succs) > 0)
+	    /* Since the DEST node has been visited for the first
+	       time, check its successors.  */
+	    stack[sp++] = ei_start (dest->succs);
+	  else
+	    post_order[post_order_num++] = dest->index;
+	}
+      else
+	{
+	  if (ei_one_before_end_p (ei)
+	      && src != loop_preheader_edge (loop)->src)
+	    post_order[post_order_num++] = src->index;
+
+	  if (!ei_one_before_end_p (ei))
+	    ei_next (&stack[sp - 1]);
+	  else
+	    sp--;
+	}
     }
 
-  if (everything)
+  free (stack);
+  BITMAP_FREE (visited);
+
+  return post_order_num;
+}
+
+/* Compute the reverse top sort order of the inverted sub-CFG specified
+   by LOOP.  Returns the number of blocks which is always loop->num_nodes.  */
+
+static int
+loop_inverted_post_order_compute (int *post_order, struct loop *loop)
+{
+  basic_block bb;
+  edge_iterator *stack;
+  int sp;
+  int post_order_num = 0;
+  bitmap visited;
+
+  /* Allocate stack for back-tracking up CFG.  */
+  stack = XNEWVEC (edge_iterator, loop->num_nodes + 1);
+  sp = 0;
+
+  /* Allocate bitmap to track nodes that have been visited.  */
+  visited = BITMAP_ALLOC (NULL);
+
+  /* Put all latches into the initial work list.  In theory we'd want
+     to start from loop exits but then we'd have the special case of
+     endless loops.  It doesn't really matter for DF iteration order and
+     handling latches last is probably even better.  */
+  stack[sp++] = ei_start (loop->header->preds);
+  bitmap_set_bit (visited, loop->header->index);
+
+  /* The inverted traversal loop. */
+  while (sp)
     {
-      BITMAP_FREE (df->blocks_to_analyze);
-      df->blocks_to_analyze = NULL;
+      edge_iterator ei;
+      basic_block pred;
+
+      /* Look at the edge on the top of the stack.  */
+      ei = stack[sp - 1];
+      bb = ei_edge (ei)->dest;
+      pred = ei_edge (ei)->src;
+
+      /* Check if the predecessor has been visited yet and mark it
+	 if not so.  */
+      if (flow_bb_inside_loop_p (loop, pred)
+	  && bitmap_set_bit (visited, pred->index))
+	{
+	  if (EDGE_COUNT (pred->preds) > 0)
+	    /* Since the predecessor node has been visited for the first
+	       time, check its predecessors.  */
+	    stack[sp++] = ei_start (pred->preds);
+	  else
+	    post_order[post_order_num++] = pred->index;
+	}
+      else
+	{
+	  if (flow_bb_inside_loop_p (loop, bb)
+	      && ei_one_before_end_p (ei))
+	    post_order[post_order_num++] = bb->index;
+
+	  if (!ei_one_before_end_p (ei))
+	    ei_next (&stack[sp - 1]);
+	  else
+	    sp--;
+	}
     }
 
-#ifdef DF_DEBUG_CFG
-  df_set_clean_cfg ();
-#endif
+  free (stack);
+  BITMAP_FREE (visited);
+  return post_order_num;
+}
+
+
+/* Analyze dataflow info for the basic blocks contained in LOOP.  */
+
+void
+df_analyze_loop (struct loop *loop)
+{
+  free (df->postorder);
+  free (df->postorder_inverted);
+
+  df->postorder = XNEWVEC (int, loop->num_nodes);
+  df->postorder_inverted = XNEWVEC (int, loop->num_nodes);
+  df->n_blocks = loop_post_order_compute (df->postorder, loop);
+  df->n_blocks_inverted
+    = loop_inverted_post_order_compute (df->postorder_inverted, loop);
+  gcc_assert ((unsigned) df->n_blocks == loop->num_nodes);
+  gcc_assert ((unsigned) df->n_blocks_inverted == loop->num_nodes);
+
+  bitmap blocks = BITMAP_ALLOC (&df_bitmap_obstack);
+  for (int i = 0; i < df->n_blocks; ++i)
+    bitmap_set_bit (blocks, df->postorder[i]);
+  df_set_blocks (blocks);
+  BITMAP_FREE (blocks);
+
+  df_analyze_1 ();
 }
 
 
diff --git a/gcc/df.h b/gcc/df.h
index 6c4b3391429..878f507698f 100644
--- a/gcc/df.h
+++ b/gcc/df.h
@@ -900,7 +900,8 @@ extern void df_set_blocks (bitmap);
 extern void df_remove_problem (struct dataflow *);
 extern void df_finish_pass (bool);
 extern void df_analyze_problem (struct dataflow *, bitmap, int *, int);
-extern void df_analyze (void);
+extern void df_analyze ();
+extern void df_analyze_loop (struct loop *);
 extern int df_get_n_blocks (enum df_flow_dir);
 extern int *df_get_postorder (enum df_flow_dir);
 extern void df_simple_dataflow (enum df_flow_dir, df_init_function,
diff --git a/gcc/loop-invariant.c b/gcc/loop-invariant.c
index b31b9268ead..100a2c1b7ff 100644
--- a/gcc/loop-invariant.c
+++ b/gcc/loop-invariant.c
@@ -652,14 +652,8 @@ may_assign_reg_p (rtx x)
    BODY.  */
 
 static void
-find_defs (struct loop *loop, basic_block *body)
+find_defs (struct loop *loop)
 {
-  unsigned i;
-  bitmap blocks = BITMAP_ALLOC (NULL);
-
-  for (i = 0; i < loop->num_nodes; i++)
-    bitmap_set_bit (blocks, body[i]->index);
-
   if (dump_file)
     {
       fprintf (dump_file,
@@ -670,9 +664,8 @@ find_defs (struct loop *loop, basic_block *body)
   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 ();
+  df_analyze_loop (loop);
   check_invariant_table_size ();
 
   if (dump_file)
@@ -682,8 +675,6 @@ find_defs (struct loop *loop, basic_block *body)
 	       "*****ending processing of loop %d ******\n",
 	       loop->num);
     }
-
-  BITMAP_FREE (blocks);
 }
 
 /* Creates a new invariant for definition DEF in INSN, depending on invariants
@@ -1005,7 +996,7 @@ find_invariants (struct loop *loop)
   compute_always_reached (loop, body, may_exit, always_reached);
   compute_always_reached (loop, body, has_exit, always_executed);
 
-  find_defs (loop, body);
+  find_defs (loop);
   find_invariants_body (loop, body, always_reached, always_executed);
   merge_identical_invariants ();
 
diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c
index d03cc406ee2..9091220642c 100644
--- a/gcc/loop-iv.c
+++ b/gcc/loop-iv.c
@@ -278,10 +278,6 @@ clear_iv_info (void)
 void
 iv_analysis_loop_init (struct loop *loop)
 {
-  basic_block *body = get_loop_body_in_dom_order (loop), bb;
-  bitmap blocks = BITMAP_ALLOC (NULL);
-  unsigned i;
-
   current_loop = loop;
 
   /* Clear the information from the analysis of the previous loop.  */
@@ -294,11 +290,6 @@ iv_analysis_loop_init (struct loop *loop)
   else
     clear_iv_info ();
 
-  for (i = 0; i < loop->num_nodes; i++)
-    {
-      bb = body[i];
-      bitmap_set_bit (blocks, bb->index);
-    }
   /* Get rid of the ud chains before processing the rescans.  Then add
      the problem back.  */
   df_remove_problem (df_chain);
@@ -306,14 +297,11 @@ iv_analysis_loop_init (struct loop *loop)
   df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
   df_chain_add_problem (DF_UD_CHAIN);
   df_note_add_problem ();
-  df_set_blocks (blocks);
-  df_analyze ();
+  df_analyze_loop (loop);
   if (dump_file)
     df_dump_region (dump_file);
 
   check_iv_ref_table_size ();
-  BITMAP_FREE (blocks);
-  free (body);
 }
 
 /* Finds the definition of REG that dominates loop latch and stores