From patchwork Fri Jun 25 22:10:36 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 56995 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 65BBCB6F0C for ; Sat, 26 Jun 2010 08:11:20 +1000 (EST) Received: (qmail 29184 invoked by alias); 25 Jun 2010 22:11:18 -0000 Received: (qmail 29169 invoked by uid 22791); 25 Jun 2010 22:11:15 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, TW_SV X-Spam-Check-By: sourceware.org Received: from mail-qw0-f47.google.com (HELO mail-qw0-f47.google.com) (209.85.216.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 25 Jun 2010 22:11:08 +0000 Received: by qwi2 with SMTP id 2so771001qwi.20 for ; Fri, 25 Jun 2010 15:11:07 -0700 (PDT) Received: by 10.224.59.160 with SMTP id l32mr1118682qah.5.1277503866326; Fri, 25 Jun 2010 15:11:06 -0700 (PDT) MIME-Version: 1.0 Received: by 10.224.74.18 with HTTP; Fri, 25 Jun 2010 15:10:36 -0700 (PDT) In-Reply-To: References: From: Sebastian Pop Date: Fri, 25 Jun 2010 17:10:36 -0500 Message-ID: Subject: Re: [graphite] Extend the refined region tree print function To: Vladimir Kargov Cc: GCC GRAPHITE , gcc-patches@gcc.gnu.org, Tobias Grosser X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org On Fri, Jun 25, 2010 at 16:33, Vladimir Kargov 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   > >        * 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 * 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 From 3e5d4c7130b1236e653f56f9c56176b8e759fbc0 Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Fri, 25 Jun 2010 17:08:39 -0500 Subject: [PATCH] Print bbs in refined region tree. 2010-06-25 Vladimir Kargov * 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 + + * 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 * 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