From patchwork Tue Jun 8 12:15:24 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tobias Grosser X-Patchwork-Id: 54964 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 DB0A7B7D47 for ; Tue, 8 Jun 2010 22:16:36 +1000 (EST) Received: (qmail 29696 invoked by alias); 8 Jun 2010 12:16:33 -0000 Received: (qmail 29684 invoked by uid 22791); 8 Jun 2010 12:16:32 -0000 X-SWARE-Spam-Status: No, hits=-1.1 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS X-Spam-Check-By: sourceware.org Received: from smtprelay02.ispgateway.de (HELO smtprelay02.ispgateway.de) (80.67.31.29) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 08 Jun 2010 12:16:25 +0000 Received: from [91.67.199.77] (helo=tobias) by smtprelay02.ispgateway.de with esmtpsa (TLSv1:AES256-SHA:256) (Exim 4.68) (envelope-from ) id 1OLxjC-0007lq-8P; Tue, 08 Jun 2010 14:16:23 +0200 Received: by tobias (sSMTP sendmail emulation); Tue, 08 Jun 2010 14:16:24 +0200 From: Tobias Grosser To: gcc-graphite@googlegroups.com, gcc-patches@gcc.gnu.org Cc: Tobias Grosser Subject: [Graphite-Branch] Fix refined region tree nesting. Date: Tue, 8 Jun 2010 14:15:24 +0200 Message-Id: <1275999324-25862-1-git-send-email-grosser@fim.uni-passau.de> X-Df-Sender: imapboxtobias@web-wahnsinn.de 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 Hi, I would like to commit this patch to the graphite branch. It fixes two bugs in the region nesting, found by Vladimir. I checked the refined-region.c code against all the scop-*.c testcases in the graphite test suite. All of them now return a consistent result. Bootstrapped on x86_64 Linux. OK, to commit to the graphite branch for testing? Tobias 2010-06-07 Tobias Grosser * refined-regions.c (create_region): Only initialize the region. (find_regions_with_entry): Initialize parent relation and bbmap correctly. (build_regions_tree): Set outermost_region to region instead of topmost_region. (calculate_region_tree): Remove unneeded parameters. --- gcc/ChangeLog.graphite | 9 +++++++++ gcc/refined-regions.c | 43 +++++++++++++++++++++---------------------- 2 files changed, 30 insertions(+), 22 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 3da3c5b..1c24de9 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,3 +1,12 @@ +2010-06-07 Tobias Grosser + + * refined-regions.c (create_region): Only initialize the region. + (find_regions_with_entry): Initialize parent relation and bbmap + correctly. + (build_regions_tree): Set outermost_region to region instead of + topmost_region. + (calculate_region_tree): Remove unneeded parameters. + 2010-06-02 Tobias Grosser * graphite-scop-detection.c (is_scop_p): New. diff --git a/gcc/refined-regions.c b/gcc/refined-regions.c index 36edc5c..8ec2747 100644 --- a/gcc/refined-regions.c +++ b/gcc/refined-regions.c @@ -337,29 +337,17 @@ get_next_postdom (basic_block bb, htab_t shortcut) return get_immediate_dominator (CDI_POST_DOMINATORS, bb); } -/* Create a new region starting at ENTRY, finishing at EXIT and - being a subregion of parent. The region is automatically inserted - in the parent region. If parent is NULL no parent is assigned to - the new region. - Also a mapping from entry to the new region into the BBMAP. */ +/* Create a new region starting at ENTRY and finishing at EXIT. */ static refined_region_p -create_region (basic_block entry, basic_block exit, refined_region_p parent, - htab_t bbmap) +create_region (basic_block entry, basic_block exit) { refined_region_p r = XNEW (struct refined_region); r->entry = entry; r->exit = exit; - r->parent = parent; + r->parent = 0; r->children = VEC_alloc (refined_region_p, heap, 16); - if (parent) - VEC_safe_push (refined_region_p, heap, parent->children, r); - - /* Do not insert the outermost region in the bbmap. */ - if (exit) - insert_new_reg (entry, r, bbmap); - return r; } @@ -379,8 +367,18 @@ find_regions_with_entry (basic_block entry, struct find_regions_global_data *gd) if (is_region (entry, exit, gd->dfs)) { - refined_region_p new_region = create_region (entry, exit, last_region, - gd->bbmap); + refined_region_p new_region = create_region (entry, exit); + + /* new_region becomes the parent of last_region. */ + if (last_region) + { + VEC_safe_push (refined_region_p, heap, new_region->children, + last_region); + last_region->parent = new_region; + } + else + insert_new_reg (entry, new_region, gd->bbmap); + last_region = new_region; last_exit = exit; } @@ -463,17 +461,18 @@ build_regions_tree (basic_block bb, refined_region_p outer_region, htab_t bbmap) refined_region_p region; VEC (basic_block, heap) *dominated_bbs = get_dominated_by (CDI_DOMINATORS, bb); - /* Passed region exit. */ while (bb == outer_region->exit) outer_region = outer_region->parent; - region = get_topmost_parent (find_new_region (bb, bbmap)); + region = find_new_region (bb, bbmap); if (region) { - VEC_safe_push (refined_region_p, heap, outer_region->children, region); - region->parent = outer_region; + refined_region_p topmost_parent = get_topmost_parent (region); + VEC_safe_push (refined_region_p, heap, outer_region->children, + topmost_parent); + topmost_parent->parent = outer_region; outer_region = region; } @@ -511,7 +510,7 @@ calculate_region_tree (void) compute_dominance_frontiers (dfs); find_regions (dfs, bbmap); - outermost_region = create_region (ENTRY_BLOCK_PTR, 0, 0, bbmap); + outermost_region = create_region (ENTRY_BLOCK_PTR, 0); build_regions_tree (ENTRY_BLOCK_PTR, outermost_region, bbmap); /* Free dominance frontier */