[Graphite-Branch] Skeleton for new SCoP detection.

[Tobias Grosser <grosser at fim dot uni-passau dot de>]

Hi,

I would like to start the development of a region based SCoP detection in
Graphite. As discussed in the Graphite phone call today, I submit the first
patch for review.

This patch adds the skeleton of the new SCoP detection. It will be executed in
parallel to the old one SCoP detection to gain test coverage. 

2010-06-02  Tobias Grosser  <grosser@fim.uni-passau.de>

	* graphite-scop-detection.c (is_scop_p): New.
	(build_scops_new): New. A skeleton for the new scop detection.
	(build_scops_old): Renamed from build_scops.
	(build_scops): New version. Call the new and the old scop
	detection.

The patch survived C/C++/Fortran bootstrap on Linux 64bit.

OK for graphite branch for further testing?

Tobi

---
 gcc/ChangeLog.graphite        |    8 ++++
 gcc/graphite-scop-detection.c |   87 +++++++++++++++++++++++++++++++++++++---
 2 files changed, 88 insertions(+), 7 deletions(-)

diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index 3f7d97b..50c8ea1 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -1318,18 +1318,80 @@ canonicalize_loop_closed_ssa_form (void)
 #endif
 }
 
-/* Find Static Control Parts (SCoP) in the current function and pushes
-   them to SCOPS.  */
+/* Check if REGION is a valid SCoP.  */
 
-void
-build_scops (VEC (scop_p, heap) **scops)
+static bool
+is_scop_p (ATTRIBUTE_UNUSED refined_region_p region)
 {
-  struct loop *loop = current_loops->tree_root;
-  VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
+  /* TODO: Are there any harmful bbs in the region?  */
+  /* TODO: Have all loops a # of iterations that can be expressed
+	   by an affine linear function.  */
+  /* TODO: Is there only well structured control flow in the region?
+	   * All loops have just one exit?
+	   * All loops are detected by gcc's loop detection?
+	   * All conditions are well nested?  */
+
+  return false;
+}
+
+/* Find Static Control Parts (SCoP) in the current function.
+   (New version using a more structured approach)  */
 
-  /* Run new scop detection in parallel.  */
+static void
+build_scops_new (void)
+{
+
+  VEC (refined_region_p, heap) *scops = VEC_alloc (refined_region_p, heap, 3);
+  VEC (refined_region_p, heap) *check = VEC_alloc (refined_region_p, heap, 3);
+
+  /* TODO: Do we need to call canonicalize_loop_closed_ssa_form()?  */
+
+  /* Build new region tree.  */
   refined_region_p new_region = calculate_region_tree ();
+
+  /* Find the maximal valid regions.  */
+  VEC_safe_push (refined_region_p, heap, check, new_region);
+
+  while (VEC_length (refined_region_p, check) != 0)
+    {
+      refined_region_p region = VEC_last (refined_region_p, check);
+      VEC_pop (refined_region_p, check);
+
+      if (is_scop_p (region))
+	VEC_safe_push (refined_region_p, heap, scops, region);
+      else
+	{
+	  int ix;
+	  refined_region_p subregion;
+
+	  for (ix = 0;
+	       VEC_iterate (refined_region_p, region->children, ix, subregion);
+	       ix++)
+	    {
+	      VEC_safe_push (refined_region_p, heap, check, subregion);
+	    }
+	}
+    }
+
+  /* TODO: Check if we can create even bigger regions by combining
+	   canonical regions,  that are executed one after another.  */
+  /* TODO: Create sese edges.  */
+  /* TODO: Create graphite scops.  */
+
+  VEC_free (refined_region_p, heap, check);
+  VEC_free (refined_region_p, heap, scops);
   free_region_tree (new_region);
+}
+
+
+/* Find Static Control Parts (SCoP) in the current function and pushes
+   them to SCOPS.  (Old version)  */
+
+static void
+build_scops_old (VEC (scop_p, heap) **scops)
+{
+  struct loop *loop = current_loops->tree_root;
+  VEC (sd_region, heap) *regions = VEC_alloc (sd_region, heap, 3);
 
   canonicalize_loop_closed_ssa_form ();
   build_scops_1 (single_succ (ENTRY_BLOCK_PTR), ENTRY_BLOCK_PTR->loop_father,
@@ -1348,6 +1410,17 @@ build_scops (VEC (scop_p, heap) **scops)
 	     VEC_length (scop_p, *scops));
 }
 
+/* Find Static Control Parts (SCoP) in the current function and pushes
+   them to SCOPS.  */
+
+void
+build_scops (VEC (scop_p, heap) **scops)
+{
+  /* Run the new version in parallel to check it.  */
+  build_scops_new ();
+  build_scops_old (scops);
+}
+
 /* Pretty print to FILE all the SCoPs in DOT format and mark them with
    different colors.  If there are not enough colors, paint the
    remaining SCoPs in gray.
-- 
1.6.4.4