This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[lno][PATCH]: get loop body in BFS order
- From: Devang Patel <dpatel at apple dot com>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 13 May 2004 13:58:36 -0700
- Subject: [lno][PATCH]: get loop body in BFS order
This patch add routines to get loop body in BFS order.
Bootstrapped and tested on powerpc-darwin.
2004-05-13 Devang Patel <dpatel@apple.com>
* cfgloop.c (get_loop_body_in_bfs_order): New.
(flow_loop_exit_edges_find): Set EDGE_LOOP_EXIT.
* cfgloop.h (get_loop_body_in_bfs_order): New.
--
Devang
Index: gcc/cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.2.4.9.2.14
diff -Idpatel.pbxuser -c -3 -p -r1.2.4.9.2.14 cfgloop.h
*** gcc/cfgloop.h 30 Apr 2004 23:38:49 -0000 1.2.4.9.2.14
--- gcc/cfgloop.h 11 May 2004 19:21:45 -0000
*************** extern unsigned get_loop_level (const st
*** 263,268 ****
--- 263,269 ----
/* Loops & cfg manipulation. */
extern basic_block *get_loop_body (const struct loop *);
extern basic_block *get_loop_body_in_dom_order (const struct loop *);
+ extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
extern edge *get_loop_exit_edges (const struct loop *, unsigned *);
extern unsigned num_loop_branches (const struct loop *);
Index: gcc/cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.14.2.12.2.4
diff -Idpatel.pbxuser -c -3 -p -r1.14.2.12.2.4 cfgloop.c
*** gcc/cfgloop.c 21 Feb 2004 23:09:31 -0000 1.14.2.12.2.4
--- gcc/cfgloop.c 11 May 2004 19:21:46 -0000
*************** flow_loop_exit_edges_find (struct loop *
*** 314,320 ****
basic_block dest = e->dest;
if (!flow_bb_inside_loop_p (loop, dest))
! loop->exit_edges[num_exits++] = e;
}
}
free (bbs);
--- 314,323 ----
basic_block dest = e->dest;
if (!flow_bb_inside_loop_p (loop, dest))
! {
! e->flags |= EDGE_LOOP_EXIT;
! loop->exit_edges[num_exits++] = e;
! }
}
}
free (bbs);
*************** get_loop_body_in_dom_order (const struct
*** 1030,1035 ****
--- 1033,1092 ----
abort ();
return tovisit;
+ }
+
+ /* Get body of a LOOP in breadth first sort order. */
+
+ basic_block *
+ get_loop_body_in_bfs_order (const struct loop *loop)
+ {
+ basic_block *blocks;
+ basic_block bb;
+ bitmap visited;
+ unsigned int i = 0;
+ unsigned int vc = 1;
+
+ if (!loop->num_nodes)
+ abort ();
+
+ if (loop->latch == EXIT_BLOCK_PTR)
+ abort ();
+
+ blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
+ visited = BITMAP_XMALLOC ();
+
+ bb = loop->header;
+ while (i < loop->num_nodes)
+ {
+ edge e;
+
+ if (!bitmap_bit_p (visited, bb->index))
+ {
+ /* This basic block is now visited */
+ bitmap_set_bit (visited, bb->index);
+ blocks[i++] = bb;
+ }
+
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ if (! (e->flags & EDGE_LOOP_EXIT))
+ {
+ if (!bitmap_bit_p (visited, e->dest->index))
+ {
+ bitmap_set_bit (visited, e->dest->index);
+ blocks[i++] = e->dest;
+ }
+ }
+ }
+
+ if (i < vc)
+ abort ();
+
+ bb = blocks[vc++];
+ }
+
+ BITMAP_XFREE (visited);
+ return blocks;
}
/* Gets exit edges of a LOOP, returning their number in N_EDGES. */