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]

[graphite] Fix scop detection


Hi,

I've committed the attached patch for fixing the detection of SCoP's.
This patch also fixes another minor problem with the definition of
loops contained in a SCoP: a loop is in a scop if both its header and
its latch bbs are in the SCoP.

I tested the patch with
make -k check RUNTESTFLAGS=graphite.exp
on i686-linux.

Sebastian
-- 
AMD - GNU Tools
2008-03-02  Sebastian Pop  <sebastian.pop@amd.com>

	* tree-scalar-evolution.c (instantiate_parameters_1): An SSA_NAME
	defined in a loop at depth 0 is invariant.
	* tree-chrec.c (evolution_function_is_invariant_rec_p): Ditto.
	* tree-ssa-loop-ivopts.c (expr_invariant_in_loop_p): Should never
	be called at loop depth 0.

	* graphite.c (basic_block_simple_for_scop_p): Take the scop as
	a parameter.
	(dot_all_scops_1): Update use of basic_block_simple_for_scop_p.
	(down_open_scop): Removed.
	(loop_in_scop_p): Redefined.
	(scop_affine_expr): New argument: scop.
	(stmt_simple_for_scop_p): New argument: scop.  RETURN_EXPR is not
	a harmful statement ending a scop.
	(basic_block_simple_for_scop_p): New argument: scop.
	(get_loop_start): Removed.
	(new_scop): Initialize SCOP_LOOPS.
	(free_scop): Free SCOP_LOOPS.
	(succs_at_same_depth, preds_at_same_depth): New.
	(end_scop): Test the validity of a scop.
	(add_dominators_to_open_scops): New.
	(test_for_scop_bound): Call add_dominators_to_open_scops.
	Add cases for opening and closing multiple scops.
	(build_scops, build_scop_bbs): Iterate over basic blocks in depth first.
	(build_graphite_bb): Pass scop directly.
	(dfs_bb_in_scop_p): New.
	(scop_record_loop): Use SCOP_LOOPS for not recording the same loop
	several times.
	(nb_loops_around_gb): Use loop_in_scop_p.
	(schedule_to_scattering): Disabled for the moment the code computing
	the "textual order for outer loop".

	* graphite.h (struct scop): New field loops.
	(SCOP_LOOPS): New.
	(scop_loop_index): Test that the given loop belongs to SCOP_LOOPS.

	* testsuite/gcc.dg/graphite/scop-{1,...,7}.c: Updated.

Index: tree-scalar-evolution.c
===================================================================
--- tree-scalar-evolution.c	(revision 131611)
+++ tree-scalar-evolution.c	(working copy)
@@ -1971,6 +1971,7 @@ instantiate_parameters_1 (struct loop *l
       /* A parameter (or loop invariant and we do not want to include
 	 evolutions in outer loops), nothing to do.  */
       if (!def_bb
+	  || loop_depth (def_bb->loop_father) == 0
 	  || (!(flags & INSERT_SUPERLOOP_CHRECS)
 	      && !flow_bb_inside_loop_p (loop, def_bb)))
 	return chrec;
Index: tree-chrec.c
===================================================================
--- tree-chrec.c	(revision 131611)
+++ tree-chrec.c	(working copy)
@@ -948,8 +948,9 @@ evolution_function_is_invariant_rec_p (t
   if (evolution_function_is_constant_p (chrec))
     return true;
 
-  if (TREE_CODE (chrec) == SSA_NAME 
-      && expr_invariant_in_loop_p (get_loop (loopnum), chrec))
+  if (TREE_CODE (chrec) == SSA_NAME
+      && (loopnum == 0
+	  || expr_invariant_in_loop_p (get_loop (loopnum), chrec)))
     return true;
 
   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
Index: testsuite/gcc.dg/graphite/scop-1.c
===================================================================
--- testsuite/gcc.dg/graphite/scop-1.c	(revision 131611)
+++ testsuite/gcc.dg/graphite/scop-1.c	(working copy)
@@ -5,24 +5,19 @@ void bar (void);
 
 int toto()
 {
-  /* Scop 1. */
   int i, j, k;
   int a[100][100];
   int b[100];
-  /* End scop 1. */
 
   for (i = 1; i < 100; i++)
     {
-      /* Scop 2. */
       for (j = 1; j < 100; j++)
 	a[j][i] = a[j+1][i-1] + 2;
 
       b[i] = b[i-1] + 2;
-      /* End scop 2. */
 
       bar ();
 
-      /* Scop 3. */
       for (j = 1; j < 100; j++)
 	a[j][i] = a[j+1][i-1] + 2;
 
@@ -30,13 +25,10 @@ int toto()
 
       for (j = 1; j < 100; j++)
 	a[j][i] = a[j+1][i-1] + 2;
-      /* End scop 3. */
     }
 
-  /* Scop 4. */
   return a[3][5] + b[1];
-  /* End scop 4. */
 }
 
-/* { dg-final { scan-tree-dump-times "number of SCoPs: 4" 1 "graphite"} } */ 
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 5" 1 "graphite"} } */ 
 /* { dg-final { cleanup-tree-dump "graphite" } } */
Index: testsuite/gcc.dg/graphite/scop-2.c
===================================================================
--- testsuite/gcc.dg/graphite/scop-2.c	(revision 131611)
+++ testsuite/gcc.dg/graphite/scop-2.c	(working copy)
@@ -5,34 +5,27 @@ void bar (void);
 
 int toto()
 {
-  /* Scop 1. */
   int i, j, k;
   int a[100][100];
   int b[100];
-  /* End scop 1. */
 
   for (i = 1; i < 100; i++)
     {
-      /* Scop 5. */
       for (j = 1; j < 100; j++)
 	for (k = 1; k < 100; k++)
 	  a[j][k] = a[j+1][i-1] + 2;
 
       b[i] = b[i-1] + 2;
-      /* End scop 5. */
 
       bar ();
 
-      /* Scop 2. */
       for (j = 1; j < 100; j++)
 	a[j][i] = a[j+1][i-1] + 2;
 
       b[i] = b[i-1] + 2;
-      /* End scop 2. */
 
       bar ();
 
-      /* Scop 3. */
       for (j = 1; j < 100; j++)
 	a[j][i] = a[j+1][i-1] + 2;
 
@@ -40,13 +33,10 @@ int toto()
 
       for (j = 1; j < 100; j++)
 	a[j][i] = a[j+1][i-1] + 2;
-      /* End scop 3. */
     }
 
-  /* Scop 4. */
   return a[3][5] + b[1];
-  /* End scop 4. */
 }
 
-/* { dg-final { scan-tree-dump-times "number of SCoPs: 5" 1 "graphite"} } */ 
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 9" 1 "graphite"} } */ 
 /* { dg-final { cleanup-tree-dump "graphite" } } */
Index: testsuite/gcc.dg/graphite/scop-3.c
===================================================================
--- testsuite/gcc.dg/graphite/scop-3.c	(revision 131611)
+++ testsuite/gcc.dg/graphite/scop-3.c	(working copy)
@@ -3,13 +3,10 @@
 
 int toto()
 {
-  /* Scop 1. */
-  /* End scop 1. */
   int i, j, k;
   int a[100][100];
   int b[100];
 
-  /* Scop 2. */
   for (i = 1; i < 100; i++)
     {
       for (j = 1; j < 80; j++)
@@ -26,12 +23,9 @@ int toto()
       for (j = 1; j < 40; j++)
 	a[j][i] = a[j+1][i-1] + 4;
     }
-  /* End scop 2. */
 
-  /* Scop 3. */
   return a[3][5] + b[1];
-  /* End scop 3. */
 }
 
-/* { dg-final { scan-tree-dump-times "number of SCoPs: 3" 1 "graphite"} } */ 
-/* { dg- final { cleanup-tree-dump "graphite" } } */
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite"} } */ 
+/* { dg-final { cleanup-tree-dump "graphite" } } */
Index: testsuite/gcc.dg/graphite/scop-4.c
===================================================================
--- testsuite/gcc.dg/graphite/scop-4.c	(revision 131611)
+++ testsuite/gcc.dg/graphite/scop-4.c	(working copy)
@@ -5,17 +5,12 @@ void bar ();
 
 int toto()
 {
-  /* Scop 1. */
-  /* End scop 1. */
   int i, j, k;
   int a[100][100];
   int b[100];
 
-  /* Scop 4. */
   for (i = 1; i < 100; i++)
-  /* End scop 4. */
     {
-      /* Scop 2. */
       for (j = 1; j < 80; j++)
 	a[j][i] = a[j+1][2*i-1*j] + 12;
 
@@ -23,20 +18,15 @@ int toto()
 
       for (j = 1; j < 60; j++)
 	a[j][i] = a[j+1][i-1] + 8;
-      /* End scop 2. */
 
       bar ();
 
-      /* Scop 3. */
       if (i == 23)
 	b[i] = a[i-1][i] + 6;
-      /* End scop 3. */
     }
 
-  /* Scop 5. */
   return a[3][5] + b[1];
-  /* End scop 5. */
 }
 
-/* { dg-final { scan-tree-dump-times "number of SCoPs: 5" 1 "graphite"} } */ 
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 6" 1 "graphite"} } */ 
 /* { dg-final { cleanup-tree-dump "graphite" } } */
Index: tree-ssa-loop-ivopts.c
===================================================================
--- tree-ssa-loop-ivopts.c	(revision 131611)
+++ tree-ssa-loop-ivopts.c	(working copy)
@@ -1241,7 +1241,8 @@ find_interesting_uses_cond (struct ivopt
 }
 
 /* Returns true if expression EXPR is obviously invariant in LOOP,
-   i.e. if all its operands are defined outside of the LOOP.  */
+   i.e. if all its operands are defined outside of the LOOP.  LOOP
+   should not be the function body.  */
 
 bool
 expr_invariant_in_loop_p (struct loop *loop, tree expr)
@@ -1249,6 +1250,8 @@ expr_invariant_in_loop_p (struct loop *l
   basic_block def_bb;
   unsigned i, len;
 
+  gcc_assert (loop_depth (loop) > 0);
+
   if (is_gimple_min_invariant (expr))
     return true;
 
Index: graphite.c
===================================================================
--- graphite.c	(revision 132556)
+++ graphite.c	(working copy)
@@ -48,7 +48,7 @@ Software Foundation, 51 Franklin Street,
 
 VEC (scop_p, heap) *current_scops;
 
-static bool basic_block_simple_for_scop_p (basic_block);
+static bool basic_block_simple_for_scop_p (scop_p, basic_block);
 static CloogMatrix *schedule_to_scattering (graphite_bb_p);
 
 /* Returns a new loop_to_cloog_loop_str structure.  */
@@ -292,11 +292,12 @@ dot_all_scops_1 (FILE *file)
 	    else
   	      fprintf (file, "%d [style=\"bold\",color=\"%s\"];\n", bb->index,
 		       color);
-	  }
 
-      /* Mark blocks not allowed in SCoP.  */
-      if (!basic_block_simple_for_scop_p (bb))
-	fprintf (file, "%d [style=\"bold,diagonals,filled\"];\n", bb->index);
+	    /* Mark blocks not allowed in SCoP.  */
+	    if (!basic_block_simple_for_scop_p (scop, bb))
+	      fprintf (file, "%d [style=\"bold,diagonals,filled\"];\n",
+		       bb->index);
+	  }
 
       /* Print edges.  */
       FOR_EACH_EDGE (e, ei, bb->succs)
@@ -330,21 +331,13 @@ dot_all_scops (void)
 
 
 
-static scop_p down_open_scop;
-
 /* Returns true when LOOP is in SCOP.  */
 
-static bool 
+static inline bool 
 loop_in_scop_p (struct loop *loop, scop_p scop)
 {
-  unsigned i;
-  struct loop *l;
-
-  for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, l); i++)
-    if (l == loop)
-      return true;
-
-  return false;
+  return (bb_in_scop_p (loop->header, scop)
+	  && bb_in_scop_p (loop->latch, scop));
 }
 
 /* Returns the outermost loop in SCOP that contains BB.  */
@@ -365,16 +358,16 @@ outermost_loop_in_scop (scop_p scop, bas
    open scop.  EXPR is contained in BB.  */
 
 static bool
-scop_affine_expr (struct loop *loop, tree expr, basic_block bb)
+scop_affine_expr (scop_p scop, struct loop *loop, tree expr, basic_block bb)
 {
   tree scev = analyze_scalar_evolution (loop, expr);
-  int outermost_loop = outermost_loop_in_scop (down_open_scop, bb)->num;
+  struct loop *outermost_loop = outermost_loop_in_scop (scop, bb);
 
-  scev = instantiate_parameters (loop, scev);
+  scev = instantiate_parameters (outermost_loop, scev);
 
-  return (evolution_function_is_constant_p (scev)
+  return (evolution_function_is_invariant_p (scev, outermost_loop->num)
 	  || evolution_function_is_affine_multivariate_p (scev,
-							  outermost_loop));
+							  outermost_loop->num));
 }
 
 
@@ -382,7 +375,7 @@ scop_affine_expr (struct loop *loop, tre
    GRAPHITE.  */
 
 static bool
-stmt_simple_for_scop_p (tree stmt)
+stmt_simple_for_scop_p (scop_p scop, tree stmt)
 {
   basic_block bb = bb_for_stmt (stmt);
   struct loop *loop = bb->loop_father;
@@ -398,6 +391,7 @@ stmt_simple_for_scop_p (tree stmt)
 
   switch (TREE_CODE (stmt))
     {
+    case RETURN_EXPR:
     case LABEL_EXPR:
       return true;
 
@@ -413,8 +407,8 @@ stmt_simple_for_scop_p (tree stmt)
 	  case GT_EXPR:
 	  case LE_EXPR:
 	  case GE_EXPR:
-	    return (scop_affine_expr (loop, TREE_OPERAND (opnd0, 0), bb) 
-		    && scop_affine_expr (loop, TREE_OPERAND (opnd0, 1), bb));
+	    return (scop_affine_expr (scop, loop, TREE_OPERAND (opnd0, 0), bb)
+		    && scop_affine_expr (scop, loop, TREE_OPERAND (opnd0, 1), bb));
 	  default:
 	    return false;
 	  }
@@ -504,7 +498,6 @@ stmt_simple_for_scop_p (tree stmt)
 	return true;
       }
 
-    case RETURN_EXPR:
     default:
       /* These nodes cut a new scope.  */
       return false;
@@ -513,47 +506,35 @@ stmt_simple_for_scop_p (tree stmt)
   return false;
 }
 
-/* This function verify if a basic block contains simple statements,
-   returns true if a BB contains only simple statements.  */
+/* Returns true if BB contains only simple statements with respect
+   to SCOP.  */
 
 static bool
-basic_block_simple_for_scop_p (basic_block bb)
+basic_block_simple_for_scop_p (scop_p scop, basic_block bb)
 {
   block_stmt_iterator bsi;
 
   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
-    if (!stmt_simple_for_scop_p (bsi_stmt (bsi)))
+    if (!stmt_simple_for_scop_p (scop, bsi_stmt (bsi)))
       return false;
 
   return true;
 }
 
-/* Find the first basic block that dominates BB and that exits the
-   current loop.  */
-static basic_block
-get_loop_start (basic_block bb)
-{
-  basic_block res = bb;
-  unsigned depth;
-
-  do {
-    res = get_immediate_dominator (CDI_DOMINATORS, res);
-    depth = loop_depth (res->loop_father);
-  } while (depth != 0 && depth >= loop_depth (bb->loop_father));
-
-  return res;
-}
-
-/* Creates a new scop starting with BB.  */
+/* Creates a new scop starting with ENTRY.  */
 
 static scop_p
-new_scop (basic_block bb)
+new_scop (basic_block entry)
 {
   scop_p scop = XNEW (struct scop);
 
-  SCOP_ENTRY (scop) = bb;
+  if (0)
+    fprintf (stdout, "open_scop (%d)\n", entry->index);
+
+  SCOP_ENTRY (scop) = entry;
   SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
   SCOP_BBS_B (scop) = BITMAP_ALLOC (NULL);
+  SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
   SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
   SCOP_PARAMS (scop) = VEC_alloc (tree, heap, 3);
   SCOP_PROG (scop) = cloog_program_malloc ();
@@ -571,6 +552,7 @@ free_scop (scop_p scop)
 {
   VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
   BITMAP_FREE (SCOP_BBS_B (scop));
+  BITMAP_FREE (SCOP_LOOPS (scop));
   VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
   VEC_free (tree, heap, SCOP_PARAMS (scop));
   cloog_program_free (SCOP_PROG (scop));
@@ -598,66 +580,174 @@ save_scop (scop_p scop)
   VEC_safe_push (scop_p, heap, current_scops, scop);
 }
 
-/* Build the SCoP ending with BB.  */
+/* Returns true when the predecessors of BB are at the same loop depth as BB.  */
+
+static bool
+preds_at_same_depth (basic_block bb)
+{
+  edge e;
+  edge_iterator ei;
+  unsigned entry_depth = loop_depth (bb->loop_father);
+
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    if (loop_depth (e->src->loop_father) != entry_depth)
+      return false;
+
+  return true;
+}
+
+/* Returns true when the successors of BB are at the same loop depth as BB.  */
+
+static bool
+succs_at_same_depth (basic_block bb)
+{
+  edge e;
+  edge_iterator ei;
+  unsigned entry_depth = loop_depth (bb->loop_father);
+
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    if (loop_depth (e->dest->loop_father) != entry_depth)
+      return false;
+
+  return true;
+}
+
+/* Build the SCoP ending with EXIT.  */
 
 static void
-end_scop (basic_block bb)
+end_scop (scop_p scop, basic_block exit, VEC (scop_p, heap) **open_scops)
 {
-  scop_p scop;
-  basic_block loop_start = get_loop_start (bb);
+  if (0)
+    fprintf (stdout, "close_scop (%d, %d) \n", SCOP_ENTRY (scop)->index, exit->index);
 
-  if (dominated_by_p (CDI_DOMINATORS, SCOP_ENTRY (down_open_scop), loop_start))
-    {
-      scop = down_open_scop;
-      SCOP_EXIT (scop) = bb;
-    }
+  /* Invariant: the SCoP exit should be dominated by its entry, and
+     the SCoP entry should be postdominated by the exit, unless the
+     exit is an exceptional one, that is a block that cannot be
+     represented in graphite.  */
+  gcc_assert ((dominated_by_p (CDI_DOMINATORS, exit, SCOP_ENTRY (scop))
+	       || !basic_block_simple_for_scop_p (scop, SCOP_ENTRY (scop)))
+	      && (dominated_by_p (CDI_POST_DOMINATORS, SCOP_ENTRY (scop), exit)
+		  || !basic_block_simple_for_scop_p (scop, exit)));
+
+  if (VEC_length (edge, SCOP_ENTRY (scop)->succs) >= 2
+      && succs_at_same_depth (SCOP_ENTRY (scop))
+      && (!dominated_by_p (CDI_DOMINATORS, exit, SCOP_ENTRY (scop))
+	  || !dominated_by_p (CDI_POST_DOMINATORS, SCOP_ENTRY (scop), exit)))
+    scop = new_scop (SCOP_ENTRY (scop));
   else
-    {
-      scop = new_scop (loop_start);
-      SCOP_EXIT (scop) = bb;
-      end_scop (loop_start);
-    }
+    VEC_pop (scop_p, *open_scops);
 
+  SCOP_EXIT (scop) = exit;
   save_scop (scop);
 }
 
-/* Mark difficult constructs as boundaries of SCoPs.  Callback for
-   walk_dominator_tree.  */
+/* Add to OPEN_SCOPS the dominators that don't dominate the LAST scop.
+   First elements in OPEN_SCOPS dominate the remaining elements.  */
 
 static void
-test_for_scop_bound (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
-		     basic_block bb)
+add_dominators_to_open_scops (VEC (scop_p, heap) **open_scops,
+			      scop_p last, basic_block bb)
 {
-  if (bb == ENTRY_BLOCK_PTR)
-    return;
+  basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
 
-  if (debug_p ())
-    fprintf (dump_file, "down bb_%d\n", bb->index);
+  while (dominated_by_p (CDI_DOMINATORS, dom, SCOP_ENTRY (last))
+	 && VEC_length (edge, dom->succs) < 2
+	 && VEC_length (edge, dom->preds) < 2
+	 && dom != SCOP_ENTRY (last))
+    dom = get_immediate_dominator (CDI_DOMINATORS, dom);
 
-  /* Exiting the loop containing the open scop ends the scop.  */
-  if (loop_depth (SCOP_ENTRY (down_open_scop)->loop_father) 
-      > loop_depth (bb->loop_father))
-    {
-      SCOP_EXIT (down_open_scop) = bb;
-      save_scop (down_open_scop);
-      down_open_scop = new_scop (bb);
+  if (dom == SCOP_ENTRY (last))
+    return;
 
-      if (debug_p ())
-	fprintf (dump_file, "dom bound bb_%d\n\n", bb->index);
+  if (dominated_by_p (CDI_DOMINATORS, dom, SCOP_ENTRY (last)))
+    {
+      /* Add outer dominators first.  */
+      add_dominators_to_open_scops (open_scops, last, dom);
 
-      return;
+      /* Add a scop from last dominator to the current one.  */
+      last = VEC_last (scop_p, *open_scops);
+      end_scop (last, dom, open_scops);
+
+      /* Push an open scop for branches originating from DOM.  */
+      VEC_safe_push (scop_p, heap, *open_scops, new_scop (dom));
     }
+}
 
-  if (!basic_block_simple_for_scop_p (bb))
+/* Mark difficult constructs as boundaries of SCoPs.  Callback for
+   walk_dominator_tree.  */
+
+static bool
+test_for_scop_bound (const_basic_block cbb, const void *data)
+{
+  basic_block bb = (basic_block) cbb;
+  VEC (scop_p, heap) **open_scops = (VEC (scop_p, heap) **) data;
+  scop_p last = VEC_last (scop_p, *open_scops);
+
+  if (!basic_block_simple_for_scop_p (last, bb))
     {
-      end_scop (bb);
-      down_open_scop = new_scop (bb);
+      if (0)
+	fprintf (stdout, "harmful_bb (%d) \n", bb->index);
+
+      add_dominators_to_open_scops (open_scops, last, bb);
+
+      /* Add a scop from last dominator to the harmful BB.  */
+      last = VEC_last (scop_p, *open_scops);
+      end_scop (last, bb, open_scops);
+
+      /* Push an open scop for all the code after the harmful BB.  */
+      VEC_safe_push (scop_p, heap, *open_scops, new_scop (bb));
 
       if (debug_p ())
 	fprintf (dump_file, "difficult bound bb_%d\n\n", bb->index);
 
-      return;
+      return true;
     }
+
+  /* The current BB closes several open scops when it postdominates
+     at least the last two open scops.  */
+  /* A merge of several branches.  */
+  if (VEC_length (scop_p, *open_scops) >= 2
+      && VEC_length (edge, bb->preds) >= 2
+      && preds_at_same_depth (bb))
+    {
+      scop_p before_last = VEC_index (scop_p, *open_scops,
+				      VEC_length (scop_p, *open_scops) - 2);
+
+      if (dominated_by_p (CDI_POST_DOMINATORS, SCOP_ENTRY (before_last), bb)
+	  && dominated_by_p (CDI_POST_DOMINATORS, SCOP_ENTRY (last), bb))
+	while (dominated_by_p (CDI_POST_DOMINATORS, SCOP_ENTRY (last), bb))
+	  {
+	    end_scop (last, bb, open_scops);
+	    if (VEC_length (scop_p, *open_scops) > 0)
+	      last = VEC_last (scop_p, *open_scops);
+	    else
+	      break;
+	  }
+
+      /* Push an open scop for all the code after BB.  */
+      VEC_safe_push (scop_p, heap, *open_scops, new_scop (bb));
+
+      return true;
+    }
+
+  /* A loop exit ends a scop when the scop entry is in the loop.  */
+  if (VEC_length (edge, bb->succs) >= 2)
+    {
+      edge e;
+      edge_iterator ei;
+      unsigned entry_depth = loop_depth (SCOP_ENTRY (last)->loop_father);
+
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	{
+	  if (loop_depth (e->dest->loop_father) < entry_depth)
+	    {
+	      end_scop (last, bb, open_scops);
+	      VEC_safe_push (scop_p, heap, *open_scops, new_scop (bb));
+	    }
+	}
+    }
+
+  return true;
 }
 
 /* Find static control parts.  */
@@ -665,35 +755,29 @@ test_for_scop_bound (struct dom_walk_dat
 static void
 build_scops (void)
 {
-  struct dom_walk_data walk_data;
+  basic_block *bbs = XCNEWVEC (basic_block, n_basic_blocks);
+  scop_p last;
+  VEC (scop_p, heap) *open_scops = VEC_alloc (scop_p, heap, 3);
 
-  down_open_scop = new_scop (ENTRY_BLOCK_PTR);
-  memset (&walk_data, 0, sizeof (struct dom_walk_data));
-  walk_data.dom_direction = CDI_DOMINATORS;
-  walk_data.before_dom_children_before_stmts = test_for_scop_bound;
+  VEC_safe_push (scop_p, heap, open_scops, new_scop (ENTRY_BLOCK_PTR->next_bb));
 
-  init_walk_dominator_tree (&walk_data);
-  walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
-  fini_walk_dominator_tree (&walk_data);
+  dfs_enumerate_from (ENTRY_BLOCK_PTR, 0, test_for_scop_bound, bbs,
+		      n_basic_blocks, &open_scops);
 
-  /* End the last open scop.  */
-  SCOP_EXIT (down_open_scop) = EXIT_BLOCK_PTR;
-  save_scop (down_open_scop);
+  free (bbs);
+  last = VEC_last (scop_p, open_scops);
+  end_scop (last, EXIT_BLOCK_PTR->prev_bb, &open_scops);
+
+  gcc_assert (VEC_empty (scop_p, open_scops));
+  VEC_free (scop_p, heap, open_scops);
 }
 
 /* Store the GRAPHITE representation of BB.  */
 
 static void
-build_graphite_bb (struct dom_walk_data *dw_data, basic_block bb)
+build_graphite_bb (scop_p scop, basic_block bb)
 {
   struct graphite_bb *gb;
-  scop_p scop = (scop_p) dw_data->global_data;
-
-  /* Scop's exit is not in the scop.  */
-  if (bb == SCOP_EXIT (scop)
-      /* Every block in the scop is postdominated by scop's exit.  */
-      || !dominated_by_p (CDI_POST_DOMINATORS, bb, SCOP_EXIT (scop)))
-    return;
 
   /* Build the new representation for the basic block.  */
   gb = XNEW (struct graphite_bb);
@@ -706,26 +790,41 @@ build_graphite_bb (struct dom_walk_data 
   bitmap_set_bit (SCOP_BBS_B (scop), bb->index);
 }
 
+/* Predicate for dfs order traversal of bbs in a scop.  */
+
+static bool
+dfs_bb_in_scop_p (const_basic_block bb, const void *data)
+{
+  scop_p scop = (scop_p) data;
+
+  /* Scop's exit is not in the scop.  */
+  if (bb == SCOP_EXIT (scop)
+      /* Every block in the scop is dominated by scop's entry.  */
+      || !dominated_by_p (CDI_DOMINATORS, bb, SCOP_ENTRY (scop))
+      /* Every block in the scop is postdominated by scop's exit.  */
+      || !dominated_by_p (CDI_POST_DOMINATORS, bb, SCOP_EXIT (scop)))
+    return false;
+
+  build_graphite_bb (scop, (basic_block) bb);
+  return true;
+}
+
 /* Gather the basic blocks belonging to the SCOP.  */
 
 static void
 build_scop_bbs (scop_p scop)
 {
-  struct dom_walk_data walk_data;
-
-  memset (&walk_data, 0, sizeof (struct dom_walk_data));
+  basic_block *bbs = XCNEWVEC (basic_block, n_basic_blocks);
 
   /* Iterate over all the basic blocks of the scop in their pseudo
      execution order, and associate to each bb a static schedule.
      (pseudo exec order = the branches of a condition are scheduled
      sequentially: the then clause comes before the else clause.)  */
-  walk_data.before_dom_children_before_stmts = build_graphite_bb;
-  walk_data.dom_direction = CDI_DOMINATORS;
 
-  walk_data.global_data = scop;
-  init_walk_dominator_tree (&walk_data);
-  walk_dominator_tree (&walk_data, SCOP_ENTRY (scop));
-  fini_walk_dominator_tree (&walk_data);
+  dfs_enumerate_from (SCOP_ENTRY (scop), 0, dfs_bb_in_scop_p, bbs,
+		      n_basic_blocks, scop);
+
+  free (bbs);
 }
 
 /* Record LOOP as occuring in SCOP.  */
@@ -733,10 +832,11 @@ build_scop_bbs (scop_p scop)
 static void
 scop_record_loop (scop_p scop, struct loop *loop)
 {
-  if (loop_in_scop_p (loop, scop))
-    return;
-
-  VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
+  if (!bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
+    {
+      bitmap_set_bit (SCOP_LOOPS (scop), loop->num);
+      VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
+    }
 }
 
 /* Build the loop nests contained in SCOP.  */
@@ -1115,10 +1215,13 @@ first_loop_in_scop (scop_p scop)
 static inline int
 nb_loops_around_gb (graphite_bb_p gb)
 {
-  struct loop *loop = gbb_loop (gb);
-  struct loop *outer_loop = SCOP_ENTRY (GBB_SCOP (gb))->loop_father;
+  scop_p scop = GBB_SCOP (gb);
+  struct loop *l = gbb_loop (gb);
+  int d = 0;
+
+  for (; loop_in_scop_p (l, scop); d++, l = loop_outer (l));
 
-  return loop_depth (loop) - loop_depth (outer_loop);
+  return d;
 }
 
 /* Converts LOOP in SCOP to cloog's format.  NB_OUTER_LOOPS is the
@@ -1311,12 +1414,14 @@ schedule_to_scattering (graphite_bb_p gb
     }
 
   /* Set textual order for outer loop.  */
+#if 0
   loop_index = scop_loop_index (GBB_SCOP (gb), loop);
 
   value_init (scat->p[row][1]);
   value_set_si (scat->p[row][1], 1);
   value_init (scat->p[row][col_const]);
   value_set_si (scat->p[row][col_const], GBB_STATIC_SCHEDULE (gb)[loop_index]);
+#endif
 
  return scat; 
 }
Index: graphite.h
===================================================================
--- graphite.h	(revision 132318)
+++ graphite.h	(working copy)
@@ -76,6 +76,7 @@ struct scop
   VEC (tree, heap) *params;
 
   /* Loops contained in the scop.  */
+  bitmap loops;
   VEC (loop_p, heap) *loop_nest;
 
   htab_t loop2cloog_loop;
@@ -89,6 +90,7 @@ struct scop
 #define SCOP_ENTRY(S) S->entry
 #define SCOP_EXIT(S) S->exit
 #define SCOP_STATIC_SCHEDULE(S) S->static_schedule
+#define SCOP_LOOPS(S) S->loops
 #define SCOP_LOOP_NEST(S) S->loop_nest
 #define SCOP_PARAMS(S) S->params
 #define SCOP_PROG(S) S->program
@@ -140,6 +142,8 @@ scop_loop_index (scop_p scop, struct loo
   unsigned i;
   struct loop *l;
 
+  gcc_assert (bitmap_bit_p (SCOP_LOOPS (scop), loop->num));
+
   for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, l); i++)
     if (l == loop)
       return i;

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