Patchwork [graphite] Extend the refined region tree print function

login
register
mail settings
Submitter Sebastian Pop
Date June 25, 2010, 10:10 p.m.
Message ID <AANLkTimjtXpQvqwOeu0fl4lxME7CLlKJSkgJu2GbepD1@mail.gmail.com>
Download mbox | patch
Permalink /patch/56995/
State New
Headers show

Comments

Sebastian Pop - June 25, 2010, 10:10 p.m.
On Fri, Jun 25, 2010 at 16:33, Vladimir Kargov <kargov@gmail.com> wrote:
> 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.
>

I committed the attached patch to the graphite branch.
Here is the correct form for the Changelog:

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

	* refined-regions.c (bb_index_compare): New.
	(get_bbs_in_region): New.
	(print_bbs_in_region): New.
	(print_refined_region): Add an argument that allows to print
	all basic blocks contained in regions.
	(debug_refined_region): Update call to print_refined_region.
	* refined-regions.h (print_refined_region): Update declaration.
	(get_bbs_in_region): Declared.
	* graphite-scop-detection.c (build_scops_new): Print the refined
	region tree into the Grahite dump file.

Also please add -p to the diff that svn uses, see the instructions to
"Configure an external diff utility" here:
http://gcc.gnu.org/wiki/SvnSetup

Thanks,
Sebastian
Vladimir Kargov - June 25, 2010, 10:31 p.m.
On 26 June 2010 02:10, Sebastian Pop <sebpop@gmail.com> wrote:
> I committed the attached patch to the graphite branch.
> Here is the correct form for the Changelog:
>
> 2010-06-25  Vladimir Kargov  <kargov@gmail.com>
>
>        * refined-regions.c (bb_index_compare): New.
>        (get_bbs_in_region): New.
>        (print_bbs_in_region): New.
>        (print_refined_region): Add an argument that allows to print
>        all basic blocks contained in regions.
>        (debug_refined_region): Update call to print_refined_region.
>        * refined-regions.h (print_refined_region): Update declaration.
>        (get_bbs_in_region): Declared.
>        * graphite-scop-detection.c (build_scops_new): Print the refined
>        region tree into the Grahite dump file.
>
> Also please add -p to the diff that svn uses, see the instructions to
> "Configure an external diff utility" here:
> http://gcc.gnu.org/wiki/SvnSetup
>
> Thanks,
> Sebastian
>

Thank you for the corrections! I will do my best to focus on the
guidelines next time.

Patch

From 3e5d4c7130b1236e653f56f9c56176b8e759fbc0 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Fri, 25 Jun 2010 17:08:39 -0500
Subject: [PATCH] Print bbs in refined region tree.

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

	* refined-regions.c (bb_index_compare): New.
	(get_bbs_in_region): New.
	(print_bbs_in_region): New.
	(print_refined_region): Add an argument that allows to print
	all basic blocks contained in regions.
	(debug_refined_region): Update call to print_refined_region.
	* refined-regions.h (print_refined_region): Update declaration.
	(get_bbs_in_region): Declared.
	* graphite-scop-detection.c (build_scops_new): Print the refined
	region tree into the Grahite dump file.
---
 gcc/ChangeLog.graphite        |   13 ++++++
 gcc/graphite-scop-detection.c |    8 ++++
 gcc/refined-regions.c         |   85 ++++++++++++++++++++++++++++++++++++++--
 gcc/refined-regions.h         |    3 +-
 4 files changed, 103 insertions(+), 6 deletions(-)

diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite
index 0b38c43..bafbacc 100644
--- a/gcc/ChangeLog.graphite
+++ b/gcc/ChangeLog.graphite
@@ -1,3 +1,16 @@ 
+2010-06-25  Vladimir Kargov  <kargov@gmail.com>
+
+	* refined-regions.c (bb_index_compare): New.
+	(get_bbs_in_region): New.
+	(print_bbs_in_region): New.
+	(print_refined_region): Add an argument that allows to print
+	all basic blocks contained in regions.
+	(debug_refined_region): Update call to print_refined_region.
+	* refined-regions.h (print_refined_region): Update declaration.
+	(get_bbs_in_region): Declared.
+	* graphite-scop-detection.c (build_scops_new): Print the refined
+	region tree into the Grahite dump file.
+
 2010-06-24  Sebastian Pop  <sebastian.pop@amd.com>
 
 	* graphite-sese-to-poly.c (rewrite_degenerate_phi): New.
diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index 117892f..77ec488 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -1349,6 +1349,14 @@  build_scops_new (void)
   /* 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);
 
diff --git a/gcc/refined-regions.c b/gcc/refined-regions.c
index 8ec2747..b10daea 100644
--- a/gcc/refined-regions.c
+++ b/gcc/refined-regions.c
@@ -30,10 +30,80 @@  along with GCC; see the file COPYING3.  If not see
 #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 @@  print_refined_region (FILE *F, refined_region_p region, int indent)
     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 ", region->entry->index);
+
+  if (print_bbs == true)
+    print_bbs_in_region (F, region);
   else
-    fprintf (F, "%d => End\n", region->entry->index);
+    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 @@  void
 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.  */
diff --git a/gcc/refined-regions.h b/gcc/refined-regions.h
index 43f5e84..534e3a4 100644
--- a/gcc/refined-regions.h
+++ b/gcc/refined-regions.h
@@ -89,7 +89,8 @@  extern void free_region_tree (refined_region_p);
 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 */
-- 
1.7.0.4