[PATCH] Reduce number of pre_and_rev_post_order_compute calls via domwalk

[PATCH] Reduce number of pre_and_rev_post_order_compute calls via domwalk

[Richard Biener]

This enhances the domwalk interface to allow disabling of RPO sorting
of dom children (after I've recently enhanced it to allow passing in
the RPO order).  Then it attacks the most prominent and often-called
infrastructure helper - update_ssa - which doesn't really need any
special ordering of dom children.

This reduces the number of pre_and_rev_post_order_compute calls
significantly.

There are more low-hanging opportunities which could pass along
the RPO array between functions but this is the biggest and IMHO
only one worth tackling for GCC 8 via the usual compile-time-regression
argument.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

If you are curious, domwalk does sorting of dom children since GCC 4.9 
only.

After this patch the most-calling pass is IRA which calls the function
5 times - mostly because it builds and tears down loop structures
three times ... for whatever reason (and init_alias_analysis calls
it which is called by IRA as well).

Richard.

2018-02-01  Richard Biener  <rguenther@suse.de>

	* domwalk.h (dom_walker::dom_walker): Add additional constructor
	for specifying RPO order and allow NULL for that.
	* domwalk.c (dom_walker::dom_walker): Likewise.
	(dom_walker::walk): Handle NULL RPO order.
	* tree-into-ssa.c (rewrite_dom_walker): Do not walk dom children
	in RPO order.
	(rewrite_update_dom_walker): Likewise.
	(mark_def_dom_walker): Likewise.

Index: gcc/domwalk.c
===================================================================
--- gcc/domwalk.c	(revision 257233)
+++ gcc/domwalk.c	(working copy)
@@ -191,13 +191,41 @@ dom_walker::dom_walker (cdi_direction di
 			int *bb_index_to_rpo)
   : m_dom_direction (direction),
     m_skip_unreachable_blocks (reachability != ALL_BLOCKS),
-    m_user_bb_to_rpo (bb_index_to_rpo != NULL),
+    m_user_bb_to_rpo (true),
     m_unreachable_dom (NULL),
     m_bb_to_rpo (bb_index_to_rpo)
 {
-  /* Compute the basic-block index to RPO mapping if not provided by
-     the user.  */
-  if (! m_bb_to_rpo && direction == CDI_DOMINATORS)
+  /* Set up edge flags if need be.  */
+  switch (reachability)
+    {
+    default:
+      gcc_unreachable ();
+    case ALL_BLOCKS:
+      /* No need to touch edge flags.  */
+      break;
+
+    case REACHABLE_BLOCKS:
+      set_all_edges_as_executable (cfun);
+      break;
+
+    case REACHABLE_BLOCKS_PRESERVING_FLAGS:
+      /* Preserve the edge flags.  */
+      break;
+    }
+}
+
+/* Constructor for a dom walker.  */
+
+dom_walker::dom_walker (cdi_direction direction,
+			enum reachability reachability)
+  : m_dom_direction (direction),
+    m_skip_unreachable_blocks (reachability != ALL_BLOCKS),
+    m_user_bb_to_rpo (false),
+    m_unreachable_dom (NULL),
+    m_bb_to_rpo (NULL)
+{
+  /* Compute the basic-block index to RPO mapping.  */
+  if (direction == CDI_DOMINATORS)
     {
       int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
       int postorder_num = pre_and_rev_post_order_compute (NULL, postorder,
@@ -348,7 +376,10 @@ dom_walker::walk (basic_block bb)
 	      for (dest = first_dom_son (m_dom_direction, bb);
 		   dest; dest = next_dom_son (m_dom_direction, dest))
 		worklist[sp++] = dest;
-	      if (sp - saved_sp > 1 && m_dom_direction == CDI_DOMINATORS)
+	      /* Sort worklist after RPO order if requested.  */
+	      if (sp - saved_sp > 1
+		  && m_dom_direction == CDI_DOMINATORS
+		  && m_bb_to_rpo)
 		sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp);
 	    }
 	}
Index: gcc/domwalk.h
===================================================================
--- gcc/domwalk.h	(revision 257233)
+++ gcc/domwalk.h	(working copy)
@@ -60,10 +60,13 @@ public:
     REACHABLE_BLOCKS_PRESERVING_FLAGS
   };
 
+  dom_walker (cdi_direction direction, enum reachability = ALL_BLOCKS);
+
   /* You can provide a mapping of basic-block index to RPO if you
-     have that readily available or you do multiple walks.  */
-  dom_walker (cdi_direction direction, enum reachability = ALL_BLOCKS,
-	      int *bb_index_to_rpo = NULL);
+     have that readily available or you do multiple walks.  If you
+     specify NULL as BB_INDEX_TO_RPO dominator children will not be
+     walked in RPO order.  */
+  dom_walker (cdi_direction direction, enum reachability, int *bb_index_to_rpo);
 
   ~dom_walker ();
 
Index: gcc/tree-into-ssa.c
===================================================================
--- gcc/tree-into-ssa.c	(revision 257233)
+++ gcc/tree-into-ssa.c	(working copy)
@@ -1463,7 +1463,8 @@ rewrite_add_phi_arguments (basic_block b
 class rewrite_dom_walker : public dom_walker
 {
 public:
-  rewrite_dom_walker (cdi_direction direction) : dom_walker (direction) {}
+  rewrite_dom_walker (cdi_direction direction)
+    : dom_walker (direction, ALL_BLOCKS, NULL) {}
 
   virtual edge before_dom_children (basic_block);
   virtual void after_dom_children (basic_block);
@@ -2153,7 +2154,8 @@ rewrite_update_phi_arguments (basic_bloc
 class rewrite_update_dom_walker : public dom_walker
 {
 public:
-  rewrite_update_dom_walker (cdi_direction direction) : dom_walker (direction) {}
+  rewrite_update_dom_walker (cdi_direction direction)
+    : dom_walker (direction, ALL_BLOCKS, NULL) {}
 
   virtual edge before_dom_children (basic_block);
   virtual void after_dom_children (basic_block);
@@ -2322,7 +2324,7 @@ private:
 };
 
 mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction)
-  : dom_walker (direction), m_kills (BITMAP_ALLOC (NULL))
+  : dom_walker (direction, ALL_BLOCKS, NULL), m_kills (BITMAP_ALLOC (NULL))
 {
 }