[PATCH 2/3] Add get_loop_body_in_rpo

[Richard Biener <rguenther@suse.de>]

The following adds another get_loop_body variant, one to get blocks
in RPO.

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

	* cfgloop.h (get_loop_body_in_rpo): Declare.
	* cfgloop.cc (get_loop_body_in_rpo): Compute loop body in RPO.
---
 gcc/cfgloop.cc | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/cfgloop.h  |  1 +
 2 files changed, 69 insertions(+)

diff --git a/gcc/cfgloop.cc b/gcc/cfgloop.cc
index 5202c3865d1..d79a006554f 100644
--- a/gcc/cfgloop.cc
+++ b/gcc/cfgloop.cc
@@ -1021,6 +1021,74 @@ get_loop_body_in_bfs_order (const class loop *loop)
   return blocks;
 }
 
+/* Get the body of LOOP in FN in reverse post order.  */
+
+basic_block *
+get_loop_body_in_rpo (function *fn, const class loop *loop)
+{
+  auto_vec<edge_iterator, 20> stack (loop->num_nodes + 1);
+  auto_bb_flag visited (fn);
+
+  basic_block *blocks = XNEWVEC (basic_block, loop->num_nodes);
+  int rev_post_order_num = loop->num_nodes - 1;
+
+  /* Find a block leading to the loop header.  */
+  edge_iterator ei;
+  edge e;
+  FOR_EACH_EDGE (e, ei, loop->header->preds)
+    if (!flow_bb_inside_loop_p (loop, e->src))
+      break;
+  basic_block preheader = e->src;
+
+  stack.quick_push (ei_start (preheader->succs));
+
+  while (!stack.is_empty ())
+    {
+      basic_block src;
+      basic_block dest;
+
+      /* Look at the edge on the top of the stack.  */
+      edge_iterator ei = stack.last ();
+      src = ei_edge (ei)->src;
+      dest = ei_edge (ei)->dest;
+
+      /* Check if the edge destination has been visited yet.  */
+      if (flow_bb_inside_loop_p (loop, dest)
+	  && ! (dest->flags & visited))
+	{
+	  /* Mark that we have visited the destination.  */
+	  dest->flags |= visited;
+
+	  if (EDGE_COUNT (dest->succs) > 0)
+	    /* Since the DEST node has been visited for the first
+	       time, check its successors.  */
+	    stack.quick_push (ei_start (dest->succs));
+	  else
+	    /* There are no successors for the DEST node so record
+	       the block.  */
+	    blocks[rev_post_order_num--] = dest;
+	}
+      else
+	{
+	  if (ei_one_before_end_p (ei)
+	      && src != preheader)
+	    /* There are no more successors for the SRC node
+	       so record the block.  */
+	    blocks[rev_post_order_num--] = src;
+
+	  if (!ei_one_before_end_p (ei))
+	    ei_next (&stack.last ());
+	  else
+	    stack.pop ();
+	}
+    }
+
+  for (int i = rev_post_order_num + 1; i < (int) loop->num_nodes; ++i)
+    blocks[i]->flags &= ~visited;
+
+  return blocks;
+}
+
 /* Hash function for struct loop_exit.  */
 
 hashval_t
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index 30b5e40d0d9..42f3079102d 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -385,6 +385,7 @@ extern basic_block *get_loop_body_in_custom_order (const class loop *,
 			       int (*) (const void *, const void *));
 extern basic_block *get_loop_body_in_custom_order (const class loop *, void *,
 			       int (*) (const void *, const void *, void *));
+extern basic_block *get_loop_body_in_rpo (function *, const class loop *);
 
 extern auto_vec<edge> get_loop_exit_edges (const class loop *, basic_block * = NULL);
 extern edge single_exit (const class loop *);
-- 
2.35.3