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]

Fix incorrect DFS traversal in dfs function


When looking into an optimization, I noticed that dfs_enumerate_from
(cfganal.c) is not doing a DFS search.  It is traversing
the CFG in some non-standard order.  This patch changes
dfs_enumerate_from to a correct DFS search.

Bootstrapped and tested on i486-linux.

Thanks,
Mark

2007-12-03  Mark Heffernan  <meheff@google.com>

      * cfganal.c (dfs_enumerate_from): changed to do correct DFS search.


Index: gcc/cfganal.c
===================================================================
--- gcc/cfganal.c       (revision 130596)
+++ gcc/cfganal.c       (working copy)
@@ -1144,13 +1144,15 @@ flow_dfs_compute_reverse_finish (depth_f

 /* Performs dfs search from BB over vertices satisfying PREDICATE;
    if REVERSE, go against direction of edges.  Returns number of blocks
-   found and their list in RSLT.  RSLT can contain at most RSLT_MAX items.  */
+   found and their list in DFS pre-order in RSLT.  RSLT can contain at
+   most RSLT_MAX items.  */
 int
 dfs_enumerate_from (basic_block bb, int reverse,
                    bool (*predicate) (const_basic_block, const void *),
                    basic_block *rslt, int rslt_max, const void *data)
 {
-  basic_block *st, lbb;
+  edge_iterator *st;
+  basic_block lbb;
   int sp = 0, tv = 0;
   unsigned size;

@@ -1188,34 +1190,47 @@ dfs_enumerate_from (basic_block bb, int
       v_size = size;
     }

-  st = XCNEWVEC (basic_block, rslt_max);
-  rslt[tv++] = st[sp++] = bb;
+  /* st is a stack of unvisited branches (edge_iterators) from the DFS path.
+     Each level in the DFS path includes one branch: the first unvisited
+     branch in the preds/succs list. */
+  st = XNEWVEC (edge_iterator, rslt_max);
+  rslt[tv++] = bb;
   MARK_VISITED (bb);
+  if (reverse)
+    st[sp++] = ei_start (bb->preds);
+  else
+    st[sp++] = ei_start (bb->succs);
+
   while (sp)
     {
-      edge e;
-      edge_iterator ei;
-      lbb = st[--sp];
+      edge_iterator ei, next_ei;
+      ei = st[--sp];
+      if (ei_end_p (ei))
+       continue;
+
+      /* Increment this level's unvisited branch to the next sibling. */
+      next_ei = ei;
+      ei_next (&next_ei);
+      st[sp++] = next_ei;
+
       if (reverse)
-       {
-         FOR_EACH_EDGE (e, ei, lbb->preds)
-           if (!VISITED_P (e->src) && predicate (e->src, data))
-             {
-               gcc_assert (tv != rslt_max);
-               rslt[tv++] = st[sp++] = e->src;
-               MARK_VISITED (e->src);
-             }
-       }
+       lbb = ei_edge (ei)->src;
       else
-       {
-         FOR_EACH_EDGE (e, ei, lbb->succs)
-           if (!VISITED_P (e->dest) && predicate (e->dest, data))
-             {
-               gcc_assert (tv != rslt_max);
-               rslt[tv++] = st[sp++] = e->dest;
-               MARK_VISITED (e->dest);
-             }
-       }
+       lbb = ei_edge (ei)->dest;
+      if (VISITED_P (lbb) || !predicate (lbb, data))
+       continue;
+
+      gcc_assert (tv != rslt_max);
+      rslt[tv++] = lbb;
+      MARK_VISITED (lbb);
+
+      /* Advance forward in the search.  No need to bounds check st, because
+         number of elements in st is always less than or equal to tv which
+         is checked above. */
+      if (reverse)
+       st[sp++] = ei_start (lbb->preds);
+      else
+       st[sp++] = ei_start (lbb->succs);
     }
   free (st);
   for (sp = 0; sp < tv; sp++)


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