[lno][PATCH]: get loop body in BFS order

Devang Patel dpatel@apple.com
Thu May 13 21:19:00 GMT 2004


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.  */



More information about the Gcc-patches mailing list