[graphite] Extend the refined region tree print function

[Vladimir Kargov <kargov at gmail dot com>]

Hello,

I would like to submit the following patch to the Graphite branch. It
makes possible to display the numbers of basic blocks included in
regions of a refined region tree. This modification can be considered
a small step towards the new SCoP detection mechanism used in
Graphite.

The patch successfully passed the bootstrap and the graphite-related tests.

2010-06-26  Vladimir Kargov  <kargov@gmail.com>

	* gcc/refined-regions.c:
	(get_bbs_in_region): New. A function that calculates basic blocks
	constituting a specified region.
	(print_bbs_in_region): Add a new argument that allows to print all
	basic blocks contained in regions.
	* gcc/refined-regions.h: Update function declarations.
	* gcc/graphite-scop-detection.c: Print the refined region tree
	into the Grahite dump file.

Index: gcc/refined-regions.c
===================================================================
--- gcc/refined-regions.c	(revision 161389)
+++ gcc/refined-regions.c	(working copy)
@@ -30,10 +30,80 @@
 #include "refined-regions.h"
 #include "domwalk.h"
 
+/* Auxiliary function for qsort() that compares two basic blocks
+   according to the values of their indices.  */
+
+static int
+bb_index_compare (const void *bbv1, const void *bbv2)
+{
+  basic_block bb1 = *(const basic_block *)bbv1;
+  basic_block bb2 = *(const basic_block *)bbv2;
+
+  gcc_assert (bbv1 && bbv2);
+
+  if (bb1->index < bb2->index)
+    return -1;
+  else 
+    return bb1->index > bb2->index;
+}
+
+/* Put all the basic blocks contained in REGION into BBLIST
+   The order in which BBs are put is not defined.  */
+
+void
+get_bbs_in_region (refined_region_p region, VEC (basic_block, heap) **bblist)
+{
+  basic_block bb_iter;
+
+  VEC (basic_block, heap) *bbstack = VEC_alloc (basic_block, heap, 3);
+  VEC_safe_push (basic_block, heap, bbstack, region->entry);
+
+  while (VEC_length (basic_block, bbstack) != 0)
+    {
+      basic_block bb = VEC_pop (basic_block, bbstack);
+      VEC_safe_push (basic_block, heap, *bblist, bb);
+
+      /* Push to stack all BB's successors.  */
+      for (bb_iter = first_dom_son (CDI_DOMINATORS, bb);
+	   bb_iter != NULL;
+	   bb_iter = next_dom_son (CDI_DOMINATORS, bb_iter))
+	if (bb_iter != region->exit)
+	  VEC_safe_push (basic_block, heap, bbstack, bb_iter);
+    }
+
+  VEC_free (basic_block, heap, bbstack);
+}
+
+/* Print all basic block indices of REGION into FILE.  */
+
+static void
+print_bbs_in_region (FILE* file, refined_region_p region)
+{
+  VEC (basic_block, heap) *bblist = VEC_alloc (basic_block, heap, 3);
+  int i;
+  basic_block bb_iter;
+
+  get_bbs_in_region (region, &bblist);
+
+  /* Sort all BBs in the region.  */
+  qsort (VEC_address (basic_block, bblist), VEC_length (basic_block, bblist),
+  	 sizeof(basic_block), bb_index_compare);
+
+  for (i = 0; VEC_iterate (basic_block, bblist, i, bb_iter); i++)
+    if (i == 0)
+      fprintf (file, "[%d", bb_iter->index);
+    else
+      fprintf (file, ", %d", bb_iter->index);
+
+  fprintf (file, "]\n");
+
+  VEC_free (basic_block, heap, bblist);
+}
+
 /* Print REGION to F with indention level INDENT.  */
 
 void
-print_refined_region (FILE *F, refined_region_p region, int indent)
+print_refined_region (FILE *F, refined_region_p region, int indent, bool print_bbs)
 {
   int ix, i;
   refined_region_p subregion;
@@ -42,13 +112,18 @@
     fprintf (F, " ");
 
   if (region->exit)
-    fprintf (F, "%d => %d \n", region->entry->index, region->exit->index);
+    fprintf (F, "%d => %d ", region->entry->index, region->exit->index);
   else
-    fprintf (F, "%d => End\n", region->entry->index);
+    fprintf (F, "%d => End ", region->entry->index);
 
+  if (print_bbs == true)
+    print_bbs_in_region(F, region);
+  else
+    fprintf (F, "\n");
+
   for (ix = 0; VEC_iterate (refined_region_p, region->children, ix, subregion);
        ix++)
-    print_refined_region (F, subregion, indent + 1);
+    print_refined_region (F, subregion, indent + 1, print_bbs);
 }
 
 /* Print REGION and all its subregions to stderr.  */
@@ -57,7 +132,7 @@
 debug_refined_region (refined_region_p region)
 {
   fprintf (stderr, "\n");
-  print_refined_region (stderr, region, 0);
+  print_refined_region (stderr, region, 0, true);
 }
 
 /* Check that BB is contained in REGION.  */
Index: gcc/refined-regions.h
===================================================================
--- gcc/refined-regions.h	(revision 161389)
+++ gcc/refined-regions.h	(working copy)
@@ -89,7 +89,8 @@
 extern bool refined_region_contains_bb_p (refined_region_p, basic_block);
 extern bool refined_region_contains_region_p (refined_region_p,
 					      refined_region_p);
-extern void print_refined_region (FILE*, refined_region_p, int);
+extern void print_refined_region (FILE*, refined_region_p, int, bool);
 extern void debug_refined_region (refined_region_p);
+extern void get_bbs_in_region (refined_region_p, VEC (basic_block, heap) **);
 
 #endif  /* GCC_REFINED_REGIONS_H */
Index: gcc/graphite-scop-detection.c
===================================================================
--- gcc/graphite-scop-detection.c	(revision 161389)
+++ gcc/graphite-scop-detection.c	(working copy)
@@ -1349,6 +1349,14 @@
   /* Build new region tree.  */
   refined_region_p new_region = calculate_region_tree ();
 
+  /* Print the region tree with all the basic blocks its regions contain.  */
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Refined region tree structure:\n\n");
+      print_refined_region (dump_file, new_region, 0, true);
+      fprintf (dump_file, "\n");
+    }
+
   /* Find the maximal valid regions.  */
   VEC_safe_push (refined_region_p, heap, check, new_region);