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
