From patchwork Tue Jun 8 12:15:24 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: [Graphite-Branch] Fix refined region tree nesting. Date: Tue, 08 Jun 2010 02:15:24 -0000 From: Tobias Grosser X-Patchwork-Id: 54964 Message-Id: <1275999324-25862-1-git-send-email-grosser@fim.uni-passau.de> To: gcc-graphite@googlegroups.com, gcc-patches@gcc.gnu.org Cc: Tobias Grosser 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 */