This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]